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

Cambridge indexes this paper as 31, although the Part III cover and footers print 34. The network area for Question 4 on page 4 is blank in the Part III PDF and PostScript edition, and in the MPhil PDF and MPhil PostScript edition. All four copies have been checked visually; the example's numerical distances remain unavailable.

In a two-person Nash bargaining problem, an agreement specifies a jointly feasible pair of payoffs $(u,v)$, measured in each player's own utility function. For a finite game, binding agreements can randomize jointly among action pairs, so the feasible payoff region $F$ is the convex hull of the pure-action payoff. This permits correlated joint actions; it is generally larger than the payoff region generated by independent mixed strategies. A disagreement point $d=(d_1,d_2)$ specifies what each player receives if negotiations fail. Assume a compact convex set of feasible agreements and at least one agreement strictly improving both disagreement payoffs.

A vector $(u^{\prime },v^{\prime })$ jointly dominates $(u,v)$ if $u^{\prime }\ge u$, $v^{\prime }\ge v$, and at least one inequality is strict. This is joint dominance of payoff vectors; strict improvement for both is unnecessary. A Pareto optimal agreement is one that has no feasible joint dominator. A jointly dominated agreement wastes a possible gain, but Pareto efficiency alone does not settle how gains should be divided. The negotiation set in two-person bargaining isIts individual-rationality constraints keep either player from accepting less than disagreement; its Pareto efficiency constraint rules out wasted opportunities. This negotiation set is distinct from objection-and-counterobjection bargaining sets for coalitional games.

The Nash arbitration procedure selects the Nash bargaining solution by maximizing gains relative to disagreement:The objective function is the Nash product. Essentiality makes its maximum positive; compactness gives attainment. On positive gains, its logarithm is $\log (u-d_1)+\log (v-d_2)$, whose Hessian is diagonal and negative definite. Thus strict concavity on the feasible convex set makes the maximizing payoff vector unique. Positive gain in either coordinate increases the product, so the solution is Pareto optimal.

The procedure respects feasibility, bargaining individual rationality, Pareto efficiency, bargaining symmetry, positive affine invariance in bargaining, and bargaining independence of irrelevant alternatives. In particular, replacing each player's utility by a separate positive affine rescaling multiplies the product by a positive constant; it does not compare one player's raw utility scale to the other's. Deleting other feasible agreements cannot change a unique maximizer that remains feasible. Symmetry under interchange of the players gives equal selected coordinates when the bargaining problem itself is symmetric.

These properties also explain why the product rule is distinguished. Normalize a positive-gain maximizer to $(1,1)$ and disagreement to $(0,0)$ by positive affine maps. The first-order inequality along a segment from $(1,1)$ to any feasible $(a,b)$ gives $a+b\le 2$. A sufficiently large symmetric triangle, bounded below in each coordinate and above by $a+b=2$, contains the normalized feasible region. Symmetry and Pareto efficiency select $(1,1)$ in that triangle. Independence of irrelevant alternatives then selects the same point in the original normalized region, and affine invariance transforms it back. This is the supporting triangle for Nash bargaining argument; the assumptions of convexity and a strict joint improvement are important. Without strict improvement, a zero product need not select a unique agreement.

For a finite game, a natural disagreement convention is each player's security level payoff:where $A,B$ are the two payoff matrices and $p,q$ are mixed strategies. Each player can independently guarantee at least its own security level. The maximin bargaining solution applies the Nash product rule using this $d$. In this convention, “maximin” determines the disagreement payoffs; it does not replace the arbitration objective function by $\min (u,v)$, which would depend improperly on interpersonal utility scales. The resulting agreement can strictly benefit both players relative to their guarantees, yet need not benefit both relative to a particular noncooperative Nash equilibrium.

Choose the sign conventionThis is the optimization Lagrangian; equality-constraint Lagrange multipliers are unrestricted in sign. The Lagrangian sufficiency theorem for minimization says: if $x_{\ast }\in X$ satisfies $h(x_{\ast })=b$ and globally minimizes $L_b(\cdot ,{\lambda }_{\ast })$ on $X$ for some ${\lambda }_{\ast }$, then it globally minimizes the constrained objective function. Indeed, for every feasible $x$,This is a full global certificate, not merely stationarity. No convexity is needed for the implication, although convexity commonly supplies the required global optimization Lagrangian minimum.

Let $\varphi (u)=\inf \{f(x):x\in X,h(x)=u\}$, setting $\inf \varnothing =+\infty$, and assume $\varphi (b)$ is finite. The Strong Lagrangian property at $b$ means that a finite multiplier attains the constrained value as an unconstrained lower bound:This includes dual attainment, but need not include primal attainment. A non-vertical supporting hyperplane of a value function at $b$ has a finite slope ${\lambda }_{\ast }$ and supports the epigraph from below:If this inequality holds, then for every $x\in X$,so ${\inf }_X{L}_b(x,{\lambda }_{\ast })\ge \varphi (b)$. Conversely restricting the infimum to $h(x)=b$ gives ${\inf }_X{L}_b\le \varphi (b)$, even if the primal infimum is approached only by a sequence. Thus equality holds. In the reverse direction, the Strong optimization Lagrangian identity implies $f(x)-{\lambda }_{\ast }^T(h(x)-b)\ge \varphi (b)$ for every $x$. Taking the infimum over $h(x)=u$ yields the supporting inequality, with empty fibres causing no problem. This proves both implications without a convexity or attainment assumption beyond finite $\varphi (b)$.

For the advertising calculation, measure the budget in thousands of pounds by $B=a/1000$. Requiring the full budget to be spent gives $3x+y=B$, with $x,y\ge 0$. Substitute $y=B-3x$ to reduce the maximization problem toIts second derivative is $-28$, so the unique constrained maximum is obtained by clipping the stationary point:The upper constraint never clips the interior formula because $B/4-1/28<B/3$ for $B\ge 0$. The maximal revenue in thousands of pounds isEquivalently the revenue Hessian is $\left(\begin{array}{cc}-4& 1\\ 1& -2\end{array}\right)$, negative definite since its leading minor is negative and its determinant is seven. Thus the full-budget affine feasible set has a unique global maximum.

At the two requested budgets,The units in the middle columns are minutes; the last column is thousands of pounds. Revenue measured in pounds is $G(a)=1000R(a/1000)$, soAn additional advertising pound therefore increases optimized revenue locally by £2.50 at the smaller budget and £0.25 at the larger budget. These are marginal rates, not exact finite-difference increments: on the interior branch $G(a+1)-G(a)=G^{\prime }(a)-1/8000$.

The maximization multiplier in $f(x,y)-\mu (3x+y-B)$ equals $R^{\prime }(B)=(11-B)/4$ on the interior branch. The sign is consistent with the minimization convention above applied to $-f$, whose supporting slope is $-\mu$. If spending is only capped by the budget, rather than required to equal it, these same answers apply at the two budgets. Beyond £11,000 the unconstrained maximum $(x,y)=(19/7,20/7)$ is affordable, so further allowed spending is unused and the capped-budget value is constant; forced full spending would instead lower revenue.

A reduction must encode primal solutions and infeasibility or unboundedness information; merely declaring a known optimum or subtracting an unknown optimum from the objective function is not a construction. The following homogeneous self-dual embedding of a linear program works without assuming the input problem has an optimum.

First remove linearly dependent equality rows by Gaussian elimination. If an eliminated row has an inconsistent right-hand side, the original problem is already certified infeasible. Return the one-variable special-form program $\min 0$ with $A^{\ast }=0$, $y=1$, and retain that certificate; no original mathematical optimization remains. Otherwise the remaining matrix has full row rank; write it as $A$ again. Put $e=1\in {\mathbb{R}}^n$ andUse nonnegative variables $x,s\in {\mathbb{R}}^n$ and $\tau ,\kappa ,\theta ,\rho \in \mathbb{R}$, with a temporary unrestricted multiplier $\lambda \in {\mathbb{R}}^m$. Impose the homogeneous linear systemAll coefficients are computable from the input. The temporary free multiplier can be eliminated without introducing cancelling positive/negative variables. DefineReplace the second equation by $(I-A^{T}H)q=0$, and substitute $Hq$ in the other equations. Because $A$ has full row rank, $A^T\lambda =q$ is equivalent to these conditions. For no remaining equality rows, simply omit $\lambda$ and its empty equations.

Let $y=(x,s,\tau ,\kappa ,\theta ,\rho )$ and $n^{\ast }=2n+4$. Collect these substituted equations into $A^{\ast }y=0$, impose $1^{T}y=1$, and let $c^{\ast }$ select the coordinate $\theta$. The resulting Karmarkar standard form isThe next two parts prove its known positive starting point and zero optimal value. Notice that normalization is legitimate for any nonzero nonnegative embedding vector because all the equations are homogeneous; it does not require a prior bound on the original optimizer.

In the unnormalized embedding, takeThen the first equation is $Ae-b+\bar{b}=0$, the second is $c-e-\bar{c}=0$, and the third is $-c^{T}e-1+\bar{z}=0$. The fourth becomesThe multiplier elimination preserves this point because $q=c-e-\bar{c}=0$ and hence $Hq=0$. Every coordinate of $y$ is one. Dividing by $n^{\ast }=2n+4$ therefore giveswhich satisfies $A^{\ast }{y}^{(0)}=0$, $1^T{y}^{(0)}=1$, and strict positivity. Its existence is independent of feasibility of the original input problem.

The objective function $\theta$ is nonnegative. We now construct a feasible zero-objective point, distinguishing the input problem's possible states.

If the primal is feasible and bounded below, strong duality and attainment for a linear program give $x_{\ast }\ge 0$, ${\lambda }_{\ast }$ and $s_{\ast }=c-A^T{\lambda }_{\ast }\ge 0$ withSet $\theta =\kappa =0$, $\tau =1$, $x=x_{\ast }$, $s=s_{\ast }$, $\lambda ={\lambda }_{\ast }$, andThe first three embedding equations hold. Substituting their equalities into the fourth gives precisely $-e^T{x}_{\ast }-e^T{s}_{\ast }-1+N\rho =0$.

If the primal is infeasible, the Farkas alternative supplies $\lambda$ with $A^T\lambda \le 0$ and $b^T\lambda >0$. Take $x=\tau =\theta =0$, $s=-A^T\lambda \ge 0$, $\kappa =b^T\lambda >0$, and $\rho =(e^{T}s+\kappa )/N$. These satisfy the same equations. If the primal is feasible and unbounded below, it has a direction in the recession cone $x\ge 0$ with $Ax=0$ and $c^{T}x<0$. Set $\lambda =s=\tau =\theta =0$, $\kappa =-c^{T}x>0$, and $\rho =(e^{T}x+\kappa )/N$. This is again a feasible nonzero embedding vector. Normalize the constructed vector by the sum of its nonnegative coordinates. In every case,The facts about optimal pairs and recession directions follow from the polyhedral alternatives of linear programming duality; they do not require knowing their values or witnesses to write the transformed coefficients.

To recover information from the transformed optimum, multiply the first three original embedding equations by ${\lambda }^T$, $x^T$, and $\tau$, respectively, and add. Their cross terms cancel; the fourth equation givesAt $\theta =0$, nonnegativity forces $x^{T}s=0$ and $\tau \kappa =0$. The equations also implyThus any normalized zero-objective point has $\rho >0$: if $\rho =0$, all these coordinates vanish, and then $q=\lambda =\theta =0$, contradicting normalization.

If $\tau >0$, division by $\tau$ gives a primal-feasible point $x/\tau$ and dual-feasible point $\lambda /\tau$ with equal objective function values; hence they are optimal. If $\kappa >0$, then $\tau =0$, $Ax=0$, $A^T\lambda =-s\le 0$, andTherefore either $b^T\lambda >0$ certifies primal infeasibility, or $c^{T}x<0$ is an improving recession direction certifying dual infeasibility and unboundedness whenever the primal is feasible. If only the latter certificate is obtained and primal feasibility is unknown, apply the same construction to the feasibility problem with objective function $c=0$; it gives either a feasible point or a direct primal infeasibility certificate.

A degenerate optimal point can have $\tau =\kappa =0$ and convey neither conclusion. Choose an optimum in the relative interior of the optimal face of a linear program. The explicit existence argument above gives a point of this face with $\tau +\kappa >0$. A nonnegative coordinate which is positive somewhere on a face of a convex set is positive throughout its relative interior, so the chosen point has $\tau +\kappa >0$ and can be decoded. The assertion follows because a small relative-interior displacement in the direction opposite a positive-coordinate point would otherwise make that coordinate negative. Equivalently one may obtain a maximum-support optimum; choosing an arbitrary degenerate boundary optimum is insufficient.

This reduction is useful because an interior-point method now has a known strictly feasible start, a compact standard simplex slice, and a known target objective function. Projective rescalings can recenter positive iterates, and the transformed problem supplies optimality or infeasibility information without a separate guessed optimum. Polynomial bit-complexity claims need rational data with a finite encoding length. The printed bound $U$ on arbitrary real coefficients by itself does not bound denominators or the size of nonzero determinants; it is not a substitute for that encoding assumption.

The all-to-one shortest path problem asks for the minimum length $v_i$ of a directed path from every vertex $i$ to the root $n$, with $v_n=0$ and $v_i=\infty$ if no such directed path exists. Positive directed edge lengths allow directed cycles to be deleted, so a shortest directed path, when one exists, uses at most $n-1$ directed edges. Its optimality equations areA Bellman-Ford algorithm initializes $d_n^{(0)}=0$ and other labels to infinity, then repeatskeeping the root label zero. Induction on $k$ proves that $d_i^{(k)}$ is the least length among directed paths using at most $k$ directed edges: either the old best directed path remains, or the first directed edge is followed by a directed path with at most $k-1$ directed edges. Thus $n-1$ rounds give the exact distances. An in-place variant repeatedly relaxes $d_i\leftarrow \min (d_i,c_{ij}+d_j)$; each decreased label triggers further incoming-arc relaxations. It terminates when no finite label can improve. The Bellman inequalities then telescope along each directed path to show the labels are lower bounds on all directed path lengths, while every finite label represents a discovered directed path and is an upper bound on the optimum. This proves correctness. The method is a label-correcting shortest-path algorithm: a processed label can be revised many times. Full scans cost $O(n|A|)$.

Let $d={\min }_{i\ne n}{c}_{in}$ and choose $j$ attaining it. Every directed path from a nonroot vertex to $n$ has a final directed edge costing at least $d$, and all preceding directed edges have positive lengths. Therefore every $v_k\ge d$. The direct directed edge from $j$ to $n$ has length $d$, soIf no incoming root directed edge exists, all these distances are infinite and there is no finite next vertex to settle.

The all-to-one Dijkstra algorithm sets the root's label to zero and all others to infinity. Repeatedly choose an unsettled vertex $j$ with least finite label, make that label permanent, and relax every incoming directed edge $(i,j)$ of an unsettled vertex:Store the corresponding successor $j$ whenever the label improves. Stop when all vertices are settled or every remaining label is infinite. This applies the usual source version to the reversed graph; relaxing outgoing original directed edges would solve the wrong direction of the problem.

For its correctness, inductively assume every settled distance is exact. Any directed path from an unsettled vertex to the root must first enter the settled set at some vertex $w$, through an directed edge $(z,w)$. That directed edge has already been relaxed, so $d_z\le c_{zw}+v_w$. The newly selected label $d_j$ is no greater than $d_z$. The directed path's preceding nonnegative lengths therefore make its total length at least $d_j$. On the other hand, $d_j$ itself is the length of a discovered directed path. Hence $d_j=v_j$, and it can never need correction. This is a label-setting shortest-path algorithm. Straight array selection costs $O(n^2+|A|)$.

For four vertices and root 4, the full symbolic execution is as follows. After settling 4, the tentative labels are $(c_{14},c_{24},c_{34},0)$. Selectset $v_j=c_{j4}$, and update the two other labels to $d_i=\min \{c_{i4},c_{ij}+c_{j4}\}$. Select the smaller of those labels at vertex $k$, set $v_k=d_k$, then for the last vertex $\ell$ setThe stored successors give the corresponding shortest routes; infinity conventions handle missing directed edges and disconnected vertices.

The supplied PDF contains no visible network diagram or directed edge lengths in the space for this example, and the converted TeX omits the diagram as well. Numerical distances and route choices cannot be determined from the supplied data. The symbolic run above gives the exact four-node calculation once those lengths are available; no network has been guessed.

Use the two-by-two payoff entries visible in the original PDF. If $q$ is the probability that II uses its first action, I's expected payoffs from its two pure strategies are $4-q$ and $2q$. Their difference $4-3q$ is strictly positive for every $q\in [0,1]$. Thus I's first action strict dominance its second, and every Nash equilibrium has I use the first action with probability one. Against that action, II receives 8 from its first action and 4 from its second, so its first action is uniquely optimal. ThereforeThis excludes nontrivial mixed equilibria as well as the other pure pairs.

For the maximin bargaining solution, first compute the two security level payoffs. If I uses its first action with probability $p$, its payoffs against II's two pure strategies are $2+p$ and $4p$. Both increase with $p$, so its best worst-case payoff is attained at $p=1$ and is $d_1=3$. If II uses its first action with probability $q$, its payoffs against I's two actions are $4+4q$ and $6-6q$. The lower of these is maximized at their intersection,These are separate security calculations, not the expected payoffs from a pair of security strategies.

Cooperation permits jointly chosen lotteries, giving the convex hull of the four payoff. The vector $(3,8)$ dominates $(2,0)$ and $(0,6)$, so the Pareto frontier is the segment from $(3,8)$ to $(4,4)$, with equation $v=20-4u$. Individual rationality relative to $d=(3,24/5)$ restricts this toOn this negotiation set, the Nash product isIts unique maximizer is interior, givingOne implementing binding agreement always uses I's first action and uses II's first action with probability $3/5$, its second with probability $2/5$. This agreement raises both payoffs above their security levels, but II receives $32/5<8$, less than at the noncooperative equilibrium. Thus player II prefers the noncooperative game under the specified maximin bargaining rule. The cooperative feasible set contains the equilibrium payoff; it is the particular arbitration rule, not an inability to cooperate at that payoff, that produces II's lower allocation.

For a transferable utility game, an imputation is an efficient and individually rational payoff allocation:Here it isWriting $z_1=x_1-1$, $z_2=x_2-2$, $z_3=x_3-3$ identifies it with a scaled standard simplex $z_1+z_2+z_3=6$. Its three vertices are $(7,2,3)$, $(1,8,3)$ and $(1,2,9)$.

The core of a cooperative game is the set of efficient allocations for which every coalition receives at least its own value: $x(S)\ge v(S)$ for every $S\subseteq N$. The singleton constraints give individual rationality, and the remaining proper-coalition inequalities areEfficiency turns the second into $x_2\le 2$; together with $x_2\ge 2$ this forces $x_2=2$. Put $x_1=t$ and $x_3=10-t$. The remaining constraints give $t\ge 1$, $t\le 6$, and $t\le 7$ from $x_3\ge 3$. The first pair constraint adds only $t\ge 1$. HenceEach point in this segment satisfies all singleton, pair, and grand-coalition constraints, so the description is sufficient as well as necessary. Its endpoints are $(1,2,9)$ and $(6,2,4)$.

For a coalition $S$, its coalition excess at an allocation is $e(S,x)=v(S)-x(S)$, measuring its complaint. Sort all these excesses of a coalition in decreasing order. The nucleolus is the imputation whose sorted vector is smallest in lexicographic order: minimize the greatest complaint first, then the next among ties, and continue. Including the empty and grand coalitions merely inserts two fixed zero entries and does not change the minimizing allocation.

For every efficient allocation, the excesses of a coalition of $\{2\}$ and $\{1,3\}$ sum to zero:The largest proper-coalition coalition excess is therefore at least zero. Since the core of a cooperative game from part (b) is nonempty, this first-stage minimum is exactly zero and its minimizers are precisely that core of a cooperative game. Restrict to $x=(t,2,10-t)$, $1\le t\le 6$. The six proper-coalition excesses of a coalition areThe two zero excesses of a coalition are fixed. Among the remaining excesses of a coalition, $t-7<t-6$, so the next largest complaint is $\max \{1-t,t-6\}$. It is minimized by equalizing those two affine expressions:This minimizer is unique, so later lexicographic stages cannot change it. ThusIts sorted proper-coalition coalition excess vector is $(0,0,-5/2,-5/2,-5/2,-7/2)$. The calculation both identifies the nucleolus and proves uniqueness for this game without replacing the requested computation by the general uniqueness theorem.