Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 37 (Mathematics of Operational Research)

A decision problem is in NP if every yes-instance has a complexity certificate of length bounded by a polynomial in the input length, and a deterministic verifier can check that certificate in polynomial time. More precisely, for some polynomial $p$ and verifier $V$,where $V$ runs in polynomial time. Equivalently, a nondeterministic machine decides the problem in polynomial time. A problem is NP-complete if it belongs to NP and is NP-hard: every problem in NP has a polynomial-time many-one reduction to it. Such a reduction maps instances $w$ to instances $r(w)$ with $w\in L$ if and only if $r(w)$ is a yes-instance of the target problem.

For 3-SAT, the complexity certificate is one truth value for each Boolean variable. Check every Boolean literal, negate its variable's truth value when appropriate, evaluate the disjunction in each Boolean clause, and check their conjunction. This takes time linear in the encoded Boolean formula, apart from equally polynomial bookkeeping for variable names. A satisfying assignment passes; an unsatisfiable Boolean formula has no passing assignment. Thus 3-SAT belongs to NP.

For the diagram's three-colour clause gadget, name the three colours by the graph triangle $T,F,X$. Each input $a,b,\bar{c}$ is adjacent to $X$, so each has colour $T$ or $F$. Suppose that none has colour $T$. Then all three have colour $F$. Because $x_1$ is adjacent to $a$ and $x_2$ to $b$, neither has colour $F$. The edge $x_1{x}_2$ forces these two colours to be $T$ and $X$ in some order. The graph triangle $x_1,x_2,x_3$ now forces $x_3$ to have colour $F$. Since $x_4$ is adjacent to $x_3$ and $T$, it must have colour $X$. The graph triangle $x_4,x_5,T$ forces $x_5$ to have colour $F$. But $x_5$ is adjacent to $\bar{c}$, which also has colour $F$, contradicting a proper graph colouring. Therefore at least one input has colour $T$.

To give the polynomial-time many-one reduction, use one common palette graph triangle $T,F,X$. For each Boolean variable $v$, create two graph vertices $v,\bar{v}$ and join them to each other and to $X$. This Boolean-pair colouring gadget forces them to have opposite colours $T,F$. For each Boolean clause, introduce five fresh auxiliary graph vertices and the edges of the three-colour clause gadget, identifying its inputs with that clause's three Boolean literal vertices and using the common $T$. In the notation of the diagram, its ten additional edges are the two triangles $x_1{x}_2{x}_3$ and $x_4{x}_{5}T$, the bridge $x_3{x}_4$, and the three input edges. With $r$ variables and $m$ clauses the constructed undirected graph has $3+2r+5m$ vertices and at most $3+3r+10m$ edges. Repeated literals do not affect the argument. Its construction takes polynomial time.

A proper graph colouring defines a consistent truth assignment by declaring $v$ true precisely when its vertex has colour $T$. The only-if result just proved makes every clause true. Conversely, a satisfying assignment colours every literal vertex consistently, and the supplied if-direction extends each satisfied clause's colours to its fresh auxiliary vertices. These extensions do not conflict, since different clauses share only already-coloured palette and literal vertices. Thus the Boolean formula is satisfiable exactly when the constructed undirected graph is three-colourable. Since 3-SAT is NP-complete, composition of reductions proves NP-hardness of the three-colourability problem.

Finally, a list of three colour labels, one for each graph vertex, is a complexity certificate for the three-colourability problem. Checking all edges takes $O(|V|+|E|)$ time. Hence this problem is in NP as well, and the three-colourability problem is NP-complete.

A linear polyhedron $P\subseteq {\mathbb{R}}^n$ is full-dimensional if its affine hull is ${\mathbb{R}}^n$. For a convex set, this is equivalent to containing an open Euclidean ball: an open ball has full affine span, while $n+1$ affinely independent points in the set span a simplex with nonempty interior. In particular, a nonempty linear polyhedron need not be full-dimensional; a singleton or a hyperplane is an example.

Assume $U\ge 1$, increasing the coefficient bound to one if necessary. If $x_0\in P$ and $A_i$ denotes the $i$th row, then $\Vert A_i{\Vert }_2\le \sqrt{n}U$. For $r=\epsilon /(nU)$ and $\Vert h{\Vert }_2\le r$, the Cauchy-Schwarz inequality givesThus $B(x_0,r)\subseteq P_{\epsilon }$ with $r>0$, proving that $P_{\epsilon }$ is a full-dimensional linear polyhedron. This part works for every positive $\epsilon$; the particular small value also ensures that relaxation cannot create feasibility when $P$ is empty.

Here is that exact-feasibility point. Put $D=[(n+1)U{]}^{n+1}$. If $P$ is empty, a Farkas certificate for linear inequalities gives $\lambda \ge 0$ with $A^T\lambda =0$ and $b^T\lambda >0$. Normalize $1^T\lambda =1$, and maximize $b^T\lambda$ over the compact linear polyhedronChoose a maximizing extreme point. Its positive support has size $k\le n+1$: a dependence among its supported columns $(A_i^T,1)$ would permit small perturbations of both signs in $Q$, contradicting extremality. Select $k$ independent equations for those $k$ coordinates. Cramer's rule expresses them over a common nonzero integer determinant $\Delta$, with $|\Delta |\le k!U^k\le D$. Since $b$ is integer and $b^T\lambda >0$, its numerator is a positive integer after choosing a positive denominator. Hence $b^T\lambda \ge 1/D$. This is the normalized integer Farkas infeasibility gap. A point in $P_{\epsilon }$ would implya contradiction. Consequently $P=\varnothing$ if and only if $P_{\epsilon }=\varnothing$.

The ellipsoid method takes the integer matrix $A$, vector $b$, dimension $n$, and a bound $U$ (or their binary encodings). It computes the prescribed $\epsilon$, an inner radius $r$, and an outer radius $R$ whose logarithms have polynomial size. For an explicit outer bound, let $M=(nU{)}^n$. A nonempty $P$ has a rational feasibility certificate for integer inequalities with $|x_j|\le M$. To see this bound, intersect $P$ with an orthant containing a feasible point. This intersection is a nonempty linear polyhedron containing no whole nontrivial affine line, and it has an extreme point. Indeed, if its active rows do not yet span the ambient space, move along a nonzero direction annihilating them. The orthant prevents motion in both directions from being feasible forever, so in at least one direction a new independent row becomes active. Repeating at most $n$ times produces an extreme point. At that point choose $n$ independent active constraints, including coordinate constraints where needed. Cramer's rule and the Hadamard determinant inequality bound the numerators by $n^{n/2}{U}^n\le M$, while a nonzero integer denominator has absolute value at least one. Thus the point has norm at most $nM$. Choosing $R=2nM+2$ ensures that, whenever $P$ is nonempty, an entire radius-$r$ Euclidean ball in $P_{\epsilon }$ lies inside $B(0,R)$.

Start with the ellipsoid $E_0=B(0,R)$ and retain $K=P_{\epsilon }\cap B(0,R)$. At each iteration test the centre $c$ against every relaxed inequality. If it passes all tests, $P_{\epsilon }$ is nonempty and hence so is $P$. Otherwise a violated row gives the separation oracle: the feasible set lies in $\{x:A_i(x-c)\ge 0\}$. Cut the current ellipsoid by this half-space through its centre and replace it by the standard containing ellipsoid. Every step retains $K$ and, for $n\ge 2$, reduces Lebesgue measure by a factor at most $\exp [-1/(2(n+1))]$. In dimension one the corresponding step bisects an interval.

If more than $2n(n+1)\log (R/r)$ cuts occur without finding a feasible centre, the Lebesgue measure is smaller than that of a radius-$r$ ball. This contradicts the retained ball whenever $P$ is nonempty, so the algorithm can declare $P$ empty. Both $\log R$ and $\log (1/r)$ are polynomial in $n$ and $\log U$, and each inequality test uses $O(mn)$ arithmetic operations for $m$ rows. The bit implementation uses rational rounding with outward enlargement of the containing ellipsoids; the encoding bounds allow polynomial precision while keeping a constant fraction of the volume decrease. Detailed update and rounding formulae are not needed for this account. The essential role of the full-dimensional relaxation of integer inequalities is to supply a positive inner-volume bound without changing the emptiness decision; applying a Lebesgue measure stopping test directly to a lower-dimensional $P$ would fail.

Write $(j_1,\dots ,j_k)$ for the partial assignment problem solution sending person $i$ to job $j_i$. The prescribed assignment lower bound from independent task minima isEvery completion must pay at least the minimum in each remaining column, so this is a valid lower bound, even if the minima use the same person several times. At $k=3$, the one remaining job must go to person 4, and the bound is the exact completed cost.

Use branch and bound with the smallest open bound expanded first. The initial bounds areFor example, $L(2)=12+11+13+22=58$. Expand $(2)$, givingExpand $(2,3)$. Its children are $(2,3,1)$ with bound 64 and $(2,3,4)$ with bound 65. Completing the first gives $(2,3,1,4)$ at cost 64, our first incumbent. The second cannot improve it. We may also discard $(2,1)$, $(2,4)$, $(3)$ and $(4)$, since their lower bounds are at least 64; equality may be pruned when seeking one optimum.

The remaining open prefix is $(1)$, whose children have boundsOnly $(1,3)$ can improve the incumbent. Its children $(1,3,2)$ and $(1,3,4)$ have exact completed costs 69 and 61, respectively. The latter completes to $(1,3,4,2)$ and replaces the incumbent. Every other branch has already been bounded above this value. Thus the optimal assignment isThis branch and bound computation produces fourteen partial nodes: four initial nodes, three below $(2)$, two below $(2,3)$, three below $(1)$ and two below $(1,3)$. The last person is assigned automatically at a depth-three node.

For the travelling salesman problem, let $x_{ij}=1$ mean that the tour goes directly from city $i$ to city $j$. Retain only the constraintsThis is an assignment problem between cities as departure points and cities as arrival points, solvable by the Hungarian algorithm. Its optimum is a cycle cover of a directed graph, possibly with several disjoint cycles. Since every tour is such a cover, its cost is a lower bound on the best tour cost. This is the assignment relaxation of the travelling salesman problem.

If the minimizing cover is a single Hamiltonian cycle, it supplies a tour and can update the incumbent. Otherwise choose one proper subtour $C$. No tour can contain all edges of $C$, since that would close a cycle before visiting the remaining cities. Make one child subproblem for each edge of $C$, forbidding that edge, and solve its modified assignment problem. These branches may overlap but together retain every possible tour. Prune a child if it is infeasible or its assignment bound is at least the incumbent cost. Further subtours cause further branching. Each branch adds a new forbidden edge, so the search is finite, and the covering property plus the valid lower bounds proves optimality when no open branch remains. This enforces the effect of subtour elimination constraints through branch and bound.

A Nash bargaining problem consists of a compact convex set $S$ of feasible two-player payoff vectors and a disagreement point $d\in S$. If bargaining fails, the players receive $d$; agreement selects a feasible vector. The convex set allows jointly agreed correlated payoff lotteries over outcomes. Assume essentiality: some feasible vector strictly improves both coordinates of $d$. The admissible answers satisfy bargaining individual rationality, $u_i\ge d_i$.

The four characterizing axioms are Pareto efficiency (no feasible vector weakly improves both chosen payoffs and strictly improves one), bargaining symmetry (interchanging identical player roles leaves the answer unchanged), positive affine invariance in bargaining (independently replacing utilities by $a_i{u}_i+b_i$, $a_i>0$, transforms the answer by the same maps), and bargaining independence of irrelevant alternatives (restricting to an admissible smaller feasible set that still contains the chosen vector leaves the choice unchanged). The last axiom keeps the disagreement point fixed.

The arbitration procedure maximizes the Nash product over individually rational vectors:A maximizer exists by compactness and has positive gains by essentiality. It is unique, since the logarithm of the product is a strictly concave function of the two gains on their positive domain. The product is strictly increasing in either positive gain, giving Pareto efficiency. A positive affine utility change multiplies the product by $a_1{a}_2$, giving positive affine invariance in bargaining. Uniqueness gives bargaining symmetry and bargaining independence of irrelevant alternatives.

For completeness, these axioms also force the procedure. Normalize the product-maximizing vector to $(1,1)$ and $d$ to zero using positive affine invariance in bargaining. For any normalized feasible vector $z$, the directional derivative of the product along the feasible segment from $(1,1)$ to $z$ is $z_1+z_2-2$. The initial part of that segment has positive gains, so optimality implies $z_1+z_2\le 2$. Choose $M$ sufficiently large that the transformed feasible set is contained in the symmetric triangleOn this triangle, bargaining symmetry requires equal coordinates and Pareto efficiency then forces $(1,1)$. By bargaining independence of irrelevant alternatives, restricting from $T_M$ to the original normalized set still selects $(1,1)$. Undoing the normalization proves the Nash bargaining solution characterization. This is the supporting triangle for Nash bargaining argument.

For the numerical game, the maximin disagreement point is the vector of the players' separate security level payoffs. If player I uses its first action with probability $p$, its worst expected payoff isThe two lines meet at $p=1/4$; before that point the increasing second line is smaller and afterwards the decreasing first line is smaller. Hence $d_1=7/2$. If player II uses its first action with probability $q$, its worst payoff ismaximized at $q=1$, giving $d_2=4$. Thus $d=(7/2,4)$. These are separate worst-case guarantees; they need not equal the actual payoffs when both security strategies are used together.

The cooperative feasible set is the convex hull of the four outcome vectors. The outcomes $(2,4)$ and $(2,3)$ are dominated by $C=(4,5)$. Its Pareto frontier is the segment joining $C$ to $B=(8,2)$, with equation $y=8-3x/4$. Any maximizer of the positive Nash product is on this frontier. Bargaining individual rationality restricts its relevant portion to $4\le x\le 16/3$. There we maximizeThe stationary point lies strictly inside that interval and is the unique maximum. Therefore the Nash bargaining solution isThe gains are $11/12$ and $11/16$, with Nash product $121/192$. The arbitration can implement the vector by the agreed correlated payoff lottery assigning probability $5/48$ to outcome $B$ and $43/48$ to outcome $C$. Indeed $4+4(5/48)=53/12$ and $5-3(5/48)=75/16$. This is a correlated payoff lottery; independent mixed strategies are not required to implement the cooperative agreement.

Let $u_i$ denote player $i$'s expected payoff, so the definition also covers mixed strategies. If $p_i^{\ast }$ is a dominant strategy, thenfor every opponents' profile $p_{-i}$ and every alternative $q_i$. In particular this holds at $p_{-i}=p_{-i}^{\ast }$. Thus no player can improve its payoff by a unilateral deviation from $(p_1^{\ast },\dots ,p_n^{\ast })$, which is exactly the definition of a Nash equilibrium. A profile of dominant strategies is a Nash equilibrium.

For the second-price sealed-bid auction, use the usual private-value auction assumptions: a bidder with value $v$ has quasilinear utility $v$ minus its payment if it wins, and zero if it loses. Fix the highest opposing bid $h$. If $h<v$, winning gives $v-h>0$, and bidding $v$ wins. If $h>v$, winning gives $v-h<0$, and bidding $v$ loses. If $h=v$, winning or losing gives zero, irrespective of the tie rule. Any other bid can only change whether the bidder wins, not the payment $h$ conditional on winning. It therefore cannot improve on the truthful bid in any of these cases. Hence bidding the true value is a weakly dominant strategy. Neither symmetry nor independence of the opposing values is needed for this argument.

For part (a), in a first-price sealed-bid auction with $n\ge 2$, continuous nonnegative bids and $v>0$, no fixed bid is a dominant strategy. A positive bid $b$ can be improved against opponents all bidding zero: replace it by $b/2>0$, still win, and increase the payoff by $b/2$. Bid zero can be improved against an opposing highest bid $h=v/2$: bidding $3v/4$ wins and earns $v/4>0$, whereas zero loses. This proves the no dominant positive-value bid in a first-price auction result.

Allowing mixed strategies does not change that conclusion. Against all-zero opponents, a random bid has expected payoff strictly below $v$ unless it is always zero and the tie rule awards this bidder the item with certainty. Any positive bid incurs a strictly positive payment, and any probability of losing at zero also reduces the payoff below $v$. In the strict case choose a sufficiently small positive fixed bid $\delta$ so that $v-\delta$ exceeds the random bid's expected payoff. In the exceptional case the preceding deviation against $h=v/2$ still improves it. The assumptions matter: for value zero, bid zero is weakly dominant; with only one bidder it is also optimal. Consequently there is no dominant strategy for a positive-value bidder in the standard first-price setting.

Part (b)'s printed nonexistence request is false under the stated symmetric independent private values model. Lack of a dominant strategy does not imply lack of a Nash equilibrium. For incomplete private information the appropriate equilibrium is a Bayesian Nash equilibrium, a Nash equilibrium of the game whose strategies are bidding rules as functions of private values. Here is an explicit counterexample with a full deviation check.

Let the $n\ge 2$ risk-neutral bidders have independent valuations with the uniform distribution on $[0,1]$, and put $a=(n-1)/n$. Suppose every opponent bids $\beta (w)=aw$. A bidder with value $v$ who bids $b\in [0,a]$ wins with probability $(b/a{)}^{n-1}$, since the opposing values must all be below $b/a$. Ties have probability zero, including at either endpoint. Its expected quasilinear utility isFor $b>0$,Thus $U_v$ increases up to $b=av$ and decreases thereafter. For $v=0$, bid zero is optimal directly. A bid above $a$ wins with certainty and pays more than bidding $a$, so it cannot improve on the maximum already found in $[0,a]$. A randomized bid is a mixture of these payoffs and also cannot improve on their maximum. The best response for every value is therefore the proposed bidding rule itself. This proves the uniform private-value first-price bidding equilibrium:The value-$v$ expected equilibrium payoff is $v^n/n$. The bidding rule is a pure strategy in the Bayesian game, even though values are random. Therefore the requested general nonexistence claim in (b) has a counterexample, rather than a valid proof. The defect is present in the original PDF, not introduced by the converted text.

In a two-player symmetric finite game, represent mixed strategies by probability vectors and let $e(x,y)=x^{T}Ay$ be the payoff to a player using $x$ against one using $y$. A resident strategy $x^{\ast }$ is an evolutionarily stable strategy if every distinct mutant strategy $y$ has an invasion barrier ${\epsilon }_0(y)>0$ such that, for $0<\epsilon <{\epsilon }_0(y)$,Thus when mutants are sufficiently rare, the resident has strictly larger fitness against the population mixture. The barrier may depend on the mutant; a common barrier is not part of this definition.

For fixed $y\ne x^{\ast }$ putBy bilinearity the resident-minus-mutant fitness difference isIf this is positive for all sufficiently small positive $\epsilon$, taking $\epsilon \downarrow 0$ gives $a_y\ge 0$. If $a_y=0$, strict positivity requires $b_y>0$. Conversely, if $a_y>0$, choose $0<{\epsilon }_0\le a_y/[2(a_y+|b_y|)]$; then the difference is at least $a_y-\epsilon (a_y+|b_y|)>a_y/2>0$. If $a_y=0$ and $b_y>0$, it is $\epsilon b_y>0$ for every $0<\epsilon <1$. This proves the two-condition criterion for evolutionary stability: for every $y\ne x^{\ast }$, eitherorThe weak first comparison is the symmetric Nash equilibrium condition; the second excludes neutrally competitive mutants when that comparison is an equality.

For the Hawk-Dove game, let $x^{\ast }=(1/2,1/2)$ and $y=(p,1-p)$, $0\le p\le 1$. Against the resident, both pure strategies give $1/2$, soDirect multiplication of the payoff matrix givesConsequentlyThe equality case of the two-condition criterion for evolutionary stability therefore applies to every distinct mutant. More explicitly, the fitness difference in a mixed population is $2\epsilon (p-1/2{)}^2$, positive for every $0<\epsilon <1$. Hence $\boxed{(1/2,1/2)\text{ is an evolutionarily stable strategy}}$, with the common invasion barrier one.