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

Let $f(x)=-{\sum }_i\log ({\alpha }_i+x_i)$. The feasible probability simplex is a nonempty compact convex set, so the extreme value theorem guarantees a minimizer. Its Hessian matrix is diagonal with positive entries $({\alpha }_i+x_i{)}^{-2}$, making $f$ a strictly convex function. Hence the minimizer is unique.

Use the Lagrange multipliers $\lambda$ for the sum constraint and ${\nu }_i\ge 0$ for $-x_i\le 0$. The Lagrangian isThe KKT conditions areA strictly positive feasible allocation exists, so the Slater condition holds. These conditions are necessary and sufficient for this convex optimization. At least one coordinate is positive, giving $\lambda >0$. Put $\tau =1/\lambda$. For a positive coordinate, complementary slackness gives ${\alpha }_i+x_i=\tau$. At a zero coordinate, stationarity gives ${\nu }_i=1/\tau -1/{\alpha }_i\ge 0$, or ${\alpha }_i\ge \tau$. ThusHere $(u{)}_{+}=\max (u,0)$. This logarithmic water filling raises the smaller baseline values to a common level. The scalar left side is a continuous function and strictly increasing above ${\min }_i{\alpha }_i$, starts at zero, and tends to infinity, so exactly one $\tau$ solves it. One can find it by interval bisection, or sort the baseline values increasingly and find an index $k$ for whichusing ${\alpha }_{(n+1)}=+\infty$. Equality at the next baseline simply gives a zero allocation. Sorting and a running sum implement the water-filling algorithm in $O(n\log n)$ time.

The increasing baseline order is $1/5,1/4,1/2,3/4$. A water-filling algorithm with three active coordinates givesTherefore, in the original coordinate order,The first three shifted coordinates all equal $13/20$, the fourth remains $3/4$, and the allocations sum to one. For an explicit KKT certificate take $\lambda =20/13$, ${\nu }_1={\nu }_2={\nu }_3=0$, and ${\nu }_4=20/13-4/3=8/39$. The strict convexity established above makes this optimum unique.

Write the primal in the form $\min c^{T}x$ with $Ax\ge b$ and $x\ge 0$. Its dual linear program is $\max b^T\lambda$ with $A^T\lambda \le c$ and $\lambda \ge 0$. Indeed, nonnegative combinations of the primal inequalities give $c^{T}x\ge {\lambda }^{T}Ax\ge {\lambda }^{T}b$, which is weak duality. The specific dual isThe four dual inequalities correspond, in order, to the four primal variables.

Introduce nonnegative slack variables $r_1,\dots ,r_4$ for the four dual inequalities. The initial simplex dictionary isAt the origin all four basic slacks are positive. Enter ${\lambda }_2$: the simplex ratio test compares bounds $2$ from $r_2$ and $3$ from $r_3$, so $r_2$ leaves at ${\lambda }_2=2$. Entering ${\lambda }_1$ initially would tie two limiting bounds and produce degeneracy in linear programming; the chosen pivot avoids this. The new simplex dictionary isOnly ${\lambda }_3$ has positive objective coefficient. Enter it; the limiting bound is $1/3$ from $r_3$, rather than $7$ from $r_4$. Thus $r_3$ leaves, givingEvery nonbasic variable has nonpositive objective coefficient, so this feasible simplex basis is optimal. Setting the nonbasic variables to zero yieldsBoth new basic solutions have strictly positive basic coordinates; neither pivot is degenerate.

The first and fourth dual constraints have positive slacks $8/3$ and $20/3$. Complementary slackness therefore requires $x_1=x_4=0$. Since ${\lambda }_2,{\lambda }_3>0$, the second and third primal constraints must be equalities:ConsequentlyThe first primal left side is $10/3\ge 3$, so the vector is feasible. Its value matches the feasible dual value, giving a linear programming optimality certificate.

For any feasible primal vector, twice the second constraint plus one third of the third givesSince $x_1,x_4\ge 0$,The vector $(0,11/6,1/3,0)$ is feasible and attains this bound. It is optimal, by this direct inequality proof of weak duality, without assuming the simplex method or a duality theorem. Equality forces $x_1=x_4=0$ and both positively weighted constraints tight, so it also proves uniqueness.

Label the vertices $S$ (left), $A$ (upper middle), $B$ (lower middle), $C$ (upper right), $T$ (lower right). Use the flow balance convention outgoing minus incoming equals supply. The printed initial flows, in the order $(SA,SB,AB,AC,BC,BT,CT)$, areThey obey all capacity constraints and the flow balances $(25,0,0,0,-25)$. The four strictly interior edges $SA,AB,BC,BT$ form a spanning tree. The remaining edges are at a bound: $SB$ at zero, $AC$ and $CT$ at their upper bounds. Thus this is already a feasible network simplex tree basis; no artificial feasibility phase is needed. Its total cost is $340$.

For a tree, choose network dual potentials with ${\pi }_S=0$ and zero network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ on each tree edge. InitiallyThe nonbasic lower-bound edge $SB$ has network reduced cost $-6$. Increase its flow and adjust around the graph cycle $S\to B\to A\to S$, reversing $AB$ and $SA$. The available step is $\min (20,15,25)=15$, so $AB$ leaves at zero. This givesThe tree is now $SA,SB,BC,BT$, and the potentials are $(0,-7,-6,-8,-8)$.

Now $AC$ is at its upper bound but has network reduced cost $3>0$, so decreasing it improves cost. Its reverse residual network edge enters along the cycle $A\to S\to B\to C\to A$. The forward edges $SB,BC$ increase; $SA,AC$ decrease. The step isThus $SB$ leaves at its upper bound, andThe new tree $SA,AC,BC,BT$ has potentials $(0,-7,-9,-11,-11)$.

The upper-bound edge $CT$ now has network reduced cost $1>0$. Enter its reverse direction along $T\to C\to B\to T$, decreasing $CT$ and $BC$ and increasing $BT$. The step is $\min (20,15,25-5)=15$, so $BC$ leaves at zero. The resulting flow isThe tree is $SA,AC,BT,CT$, with potentials $(0,-7,-10,-11,-12)$. The nonbasic edges have network reduced costs $r_{SB}=-4$ at its upper bound, $r_{AB}=2$ at its lower bound, and $r_{BC}=1$ at its lower bound. All have the correct signs, so there is no improving network simplex pivot. The next part proves these signs certify optimality.

For a minimum-cost flow with bounds $0\le x_{ij}\le m_{ij}$, the capacitated flow optimality conditions consist of primal feasibility and network dual potentials whose network reduced costs obeyFor a zero-capacity edge both bounds coincide and no sign restriction is needed; all capacities here are positive. These are the bound form of complementary slackness. To derive necessity directly, construct the residual network: a possible increase has original cost $c_{ij}$ and a possible decrease has reverse cost $-c_{ij}$. An optimal flow cannot admit a negative-cost directed cycle, since a positive step around it preserves flow balance and lowers cost. If there is no such cycle, connect a new source by zero-cost edges to every vertex and let $d_i$ be shortest-path distances. They exist because no negative cycle is reachable. For every residual edge $i\to j$, $d_j\le d_i+c_{ij}^{\mathrm{res}}$. Taking ${\pi }_i=-d_i$ makes every residual network reduced cost nonnegative, exactly the displayed sign conditions: both directions exist for an interior edge.

Conversely, for any other feasible flow $y$, equal flow balances giveEach summand is nonnegative at a lower or upper bound, and zero at an interior edge. Hence the sign conditions suffice for optimality as well.

For the final flow, use $\pi =(0,-7,-10,-11,-12)$ in the order $(S,A,B,C,T)$. All four tree edges have zero network reduced cost, while $SB,AB,BC$ have costs $-4,2,1$. More explicitly, every feasible flow satisfiesOur flow attains equality. This gives a direct cost certificate of 220. The strict signs also force $y_{SB}=20$, $y_{AB}=y_{BC}=0$ at any optimum; flow balance then fixes all remaining edges, so this flow is unique.

Use the specified construction as a polynomial-time many-one reduction from 3-SAT. There are $2n+3m$ vertices and $n+6m$ edges: one edge per variable pair, three edges per clause triangle in a graph, and three occurrence edges per clause. Any vertex cover must take at least one vertex from every variable pair and at least two from every clause triangle. Therefore every cover has at least $n+2m$ vertices.

Given a satisfying Boolean valuation, include the vertex corresponding to the true Boolean literal in each variable pair. In each clause choose a true occurrence and omit its clause vertex, including the other two. Every variable edge and triangle edge is covered. An occurrence edge with an included clause endpoint is covered automatically; the only omitted occurrence vertex is joined to the included true-literal vertex. This is a vertex cover with exactly $n+2m$ vertices.

Conversely, a cover of that size must use exactly one vertex in each variable pair and exactly two in each triangle. Declare a variable true precisely when its positive-literal vertex is included. Each clause has one omitted vertex. Its occurrence edge forces the corresponding literal vertex into the cover, so that literal is true. Every clause is therefore satisfied. ThusThe construction and target size are polynomial in the input length. Since 3-SAT is NP-complete, the decision problem is NP-hard. The usual “at most $k$” version has the same equivalence here because $n+2m$ is an unavoidable lower bound. More generally, a cover with fewer than $k\le |V|$ vertices can be padded to exactly $k$. Verifying a proposed cover is polynomial, so the usual vertex-cover decision problem is also in NP and hence NP-complete.

Let the bipartite graph have parts $L,R$. Add a source $s$, a sink $t$, capacity-one edges $s\to u$ for $u\in L$ and $v\to t$ for $v\in R$, and capacity $M=|V|+1$ on each original edge directed $L\to R$. Use the max-flow min-cut theorem: maximum flow value equals minimum cut capacity. Also use Integrality of the Ford-Fulkerson algorithm: integral capacities admit an integral maximum flow, found by integral augmenting paths.

An integral flow selects a matching in a graph, because each left and right vertex carries at most one unit. Conversely every matching gives a unit flow along its selected $s\to u\to v\to t$ paths. Hence maximum flow value equals maximum matching cardinality.

A minimum cut has capacity at most $|L|$, whereas crossing even one original edge would cost $M>|L|$. For its source side $Z$, no edge of the original graph runs from $L\cap Z$ to $R\setminus Z$. Thereforeis a vertex cover, and its cardinality is exactly the cut capacity. Conversely, given any cover $U$, use $Z=\{s\}\cup (L\setminus U)\cup (R\cap U)$. No original edge crosses this cut, because both its endpoints would otherwise be outside the cover; its capacity is $|U|$. Thus minimum cut capacity equals minimum cover size, proving König's theorem for bipartite matching:For the algorithm, repeatedly find augmenting paths in the residual network, then take $Z$ to be the vertices reachable from $s$. Each integral augmentation increases flow by at least one; the total value is at most $\min (|L|,|R|)$. Each reachability search takes $O(|V|+|E|)$ time, so this procedure takes $O(|V|(|V|+|E|))$ time. The network uses only polynomially many edges and integer capacities, yielding the requested polynomial-time algorithm and an explicit cover.

Let $P$ be the row payoff matrix and $Q=P^T$. For $x$ in the probability simplex $\Delta$, write $u(x)=x^{T}Px$ and define the symmetric Nash gain mapThe map is a continuous function, has nonnegative coordinates, and sums to one. The Brouwer fixed-point theorem states that every continuous self-map of a nonempty finite-dimensional compact convex set has a fixed point. Apply it to $T:\Delta \to \Delta$, and let $x=T(x)$.

Set $G={\sum }_i{g}_i(x)$. The fixed-point equation gives $g_i(x)=G{x}_i$. If $G>0$, every positive $x_i$ has strictly positive gain, so $(Px{)}_i-u(x)=g_i(x)=G{x}_i$. Buta contradiction. Thus $G=0$ and every pure payoff $(Px{)}_i$ is at most $u(x)$. Since their $x$-weighted average equals $u(x)$, every supported action attains that maximum. Consequently $x$ is a best response to itself.

The column player's payoff vector against $x$ is $Q^{T}x=Px$, so exactly the same inequalities establish its best response. ThereforeThis supplies the whole fixed-point construction and fixed-point-to-equilibrium argument, rather than assuming Nash's theorem as a black box.

The matrices obey $Q=P^T$, so both players' pure best response vectors have the form $Px$ against opponent mixture $x$. Against pure actions $1,2,3$, the unique best responses are respectively $3,1,2$. This three-cycle has no mutual best-response pair, so there is no pure Nash equilibrium.

In a game satisfying nondegeneracy of a bimatrix game, the two equilibrium strategy supports have equal cardinality: each support consists of best responses to the other strategy, so each size is at most the other. If both supports have size three, $Px$ must have all coordinates equal. The first-minus-second and second-minus-third equations implyThis has no fully positive simplex solution. Thus both supports have size two.

For full support enumeration for a bimatrix game, denote the three possible supports by $12,13,23$. On equal supports $12$ and $23$, indifference requires respectively probabilities $(-1,2)$ and $(2,-1)$, so those pairs fail. Equal support $13$ gives $x_1=x_3=1/2$, whose omitted-action payoff is $1<3/2$. The cross pair $(12,13)$ yieldswith $Pt=(4/3,4/3,1{)}^T$ and $Ps=(7/3,2/3,7/3{)}^T$. Thus the supported actions are best responses. Its reversed pair is also an equilibrium. The remaining unordered cross pairs fail: for $(12,23)$ the necessary $s=(1/4,3/4,0)$ gives $Ps=(11/4,3/2,3/2{)}^T$, so the opponent has a profitable action outside its support. For $(13,23)$, the necessary opponent mixture on $23$ is $(0,-1,2)$, which is infeasible. Reversing either failed pair cannot rescue it.

Hence all three equilibria areTheir payoffs are respectively $(4/3,7/3)$, $(7/3,4/3)$ and $(3/2,3/2)$. The support-size argument and exhaustion above rule out every other equilibrium.

The equilibrium oddness theorem gives a finite odd number of Nash equilibria in a finite nondegenerate bimatrix game. One way to see the parity is through the endpoint argument underlying the Lemke-Howson algorithm. Add sufficiently large constants to each payoff matrix so all entries are positive; this does not change best responses. Form the bounded convex polytopesLabel an $s_i=0$ facet by row label $i$ and a tight $(Q^{T}s{)}_j=1$ facet by column label $n+j$; in $Y$, label a tight $(Pt{)}_i=1$ facet by $i$ and $t_j=0$ by $n+j$. A completely labelled vertex of a polytope pair has either both vectors zero, or both nonzero and normalizes to a Nash equilibrium. In the latter case the labels express exactly the equilibrium best-response and zero-probability conditions. Nondegeneracy makes each vertex of a polytope have exactly $n$ distinct incident labels and each equilibrium correspond to one such pair.

Fix a label to drop and retain all pairs carrying every other label. Include the product-convex polytope edges that retain those labels. At a completely labelled pair there is one possible outgoing edge, obtained by dropping the fixed label. At any other retained vertex of a polytope, that label is missing and one other label is duplicated; dropping either copy gives the two incident edges. Thus this finite graph consists of paths and cycles, with its endpoints precisely the completely labelled pairs. A finite graph has an even number of degree-one vertices. Since one endpoint is the artificial zero pair, the number of genuine equilibrium endpoints is odd. This proves the required equilibrium oddness theorem and finiteness, without claiming that every equilibrium is reached from the zero pair on the same path.

For a symmetric bimatrix game, swapping players maps $(s,t)$ to $(t,s)$. Every nonsymmetric equilibrium lies in a distinct two-element pair; the fixed points of this involution are exactly the symmetric equilibria. Removing even-sized pairs from an odd total leaves an odd number of symmetric equilibria. In the present game, two equilibria form the swapped pair and the remaining one is $(x,x)$ with $x=(1/2,0,1/2)$. There is exactly one symmetric equilibrium, as required.

Use the usual essential two-person Nash bargaining problem: $F\subset {\mathbb{R}}^2$ is a compact convex set, $d\in F$ is the disagreement point, and some $u\in F$ satisfies $u_i>d_i$ for both players. The Nash bargaining solution isThe positive maximum exists by compactness and essentiality. On positive gains, maximizing this Nash product is equivalent to maximizing $\log (u_1-d_1)+\log (u_2-d_2)$, a strictly concave function. Convexity then gives a unique maximizer. The essentiality and compactness hypotheses matter: for example, with $F=[0,1]\times \{0\}$ and $d=0$, the product is zero everywhere and its argmax alone is not a single-valued definition.

The rule satisfies all four axioms. Pareto efficiency: a feasible vector dominating the chosen vector with at least one strict improvement would increase its positive Nash product. Bargaining symmetry: if the problem is unchanged by swapping players, uniqueness makes the answer unchanged, so the two payoffs agree. Positive affine invariance in bargaining: for $v_i=a_i{u}_i+b_i$ with $a_i>0$, gains transform to $a_i(u_i-d_i)$ and the product is multiplied by the positive constant $a_1{a}_2$, preserving its maximizer. Bargaining independence of irrelevant alternatives: if $G\subseteq F$ is another admissible feasible set containing the chosen vector and the same disagreement point, that vector remains the unique product maximizer over $G$.

To prove characterization, let $f$ be any feasible single-valued rule satisfying these axioms, and let $u^{\ast }=N(F,d)$. Normalize payoffs by the positive affine transformationThe transformed set $H$ has disagreement point zero and product maximizer $e=(1,1)$. For any $z\in H$, convexity puts $e+t(z-e)$ in $H$; for sufficiently small $t>0$ both gains remain positive. The one-sided derivative of the product at its maximum is therefore nonpositive:Thus $H\subseteq \{z:z_1+z_2\le 2\}$. By compactness choose $M\ge 0$ so every coordinate of every $z\in H$ is at least $-M$. The supporting triangle for Nash bargaining isIt contains $H$, is compact, convex, symmetric and essential, and contains disagreement zero. Symmetry forces $f(T_M,0)$ onto the diagonal; Pareto efficiency then forces it to be $e=(1,1)$. Since $e\in H\subseteq T_M$, bargaining independence of irrelevant alternatives gives $f(H,0)=e$. Undoing the normalization by positive affine invariance in bargaining gives $f(F,d)=u^{\ast }$. Hence the four axioms uniquely characterize the Nash bargaining solution on this domain.

A security level payoff maximizes what a player guarantees against the opponent. Let $p$ be the row player's probability of the first action. Its guaranteed payoff isThe decreasing and increasing terms cross at $p=1/5$, attaining $d_1=12/5$; moving either way lowers the smaller term. For the column player, any mixture has zero payoff against the first row, while its second-row payoff is nonnegative. Therefore $d_2=0$ andThe feasible set is the convex hull of the four joint pure-action payoff vectors. Its upper Pareto frontier connects $(4,0)$ to $(3,2)$ to $(2,3)$. Write the row payoff as $u$ and column payoff as $v$. On the first Pareto frontier segment, $v=8-2u$ for $3\le u\le 4$. The Nash product isa concave quadratic with derivative $64/5-4u$, maximized at $u=16/5$, $v=8/5$, giving product $32/25$. On the portion of the other Pareto frontier segment satisfying bargaining individual rationality, $12/5\le u\le 3$ and $v=5-u$. Its product derivative $37/5-2u$ is positive throughout, so its largest product is $6/5$ at $(3,2)$, smaller than $32/25$. All dominated points can be discarded by Pareto efficiency. ConsequentlyThis payoff is implemented by a correlated payoff lottery choosing the payoff $(4,0)$ with probability $1/5$ and $(3,2)$ with probability $4/5$. The convex hull permits such lotteries over joint outcomes; it is not restricted to independent mixed strategies.

Transposing the second player's matrix leaves the row player's security level payoff at $12/5$. The column player's second action now yields payoffs $2$ and $3$, while its first yields zero for either row. Its security level payoff is therefore $2$, guaranteed by the second action; against the first row no mixture can guarantee more. Thus $d=(12/5,2)$.

The relevant upper Pareto frontier joins the payoff vectors $(4,2)$ and $(2,3)$, so $v=4-u/2$. On the segment satisfying bargaining individual rationality $12/5\le u\le 4$, the Nash product becomesIts derivative is $16/5-u$ and its second derivative is $-1$. HenceThe implementing correlated payoff lottery chooses $(4,2)$ with probability $3/5$ and $(2,3)$ with probability $2/5$. Both players' gains are strictly positive: $4/5$ and $2/5$. The new disagreement point must be recomputed after transposition; reusing the previous column security payoff would solve a different Nash bargaining problem.