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

Introduce integer-valued slack variables $s_1=11-2x_1-x_2$ and $s_2=6+x_1-2x_2$. Write $Z=4x_1+3x_2$. The initial simplex dictionary isIn the simplex algorithm, let $x_1$ enter. The first constraint is the only limiting one, so $s_1$ leaves at $x_1=11/2$. Substitution givesNow $x_2$ enters and $s_2$ leaves: its ratio $23/5$ is smaller than the first row's ratio $11$. The resulting simplex dictionary isAll nonbasic objective coefficients are nonpositive, and the basic values are nonnegative. Thus the continuous linear program has optimum

For integer programming, a row $x_B+{\sum }_j{a}_j{x}_j=b$ with integer variables yields the Gomory fractional cut ${\sum }_j\{a_j\}{x}_j\ge \{b\}$, where $\{u\}=u-\lfloor u\rfloor$ is the fractional part. In the first row, the coefficient of $s_2$ on the left is $-1/5$, whose fractional part is $4/5$, not $-1/5$. The two possible initial Gomory fractional cuts are thereforeIndeed $s_1+2s_2=23-5x_2$. Choose the second row: $x_2\le 4$ implies $x_2\le 9/2$, so its cut removes a strictly larger portion of the feasible polygon. This compares both printed alternatives before any further integer rounding.

Use the normalized integer slack variable $s_3=4-x_2$, rather than an unnecessarily scaled cut slack. At the current basis,The simplex dictionary is dual feasible but primal infeasible. In the dual simplex algorithm, $s_3$ leaves; the ratios of objective loss to improvement of this negative basic value are $11$ for $s_1$ and $1$ for $s_2$, so $s_2$ enters. The pivot givesThe relaxed optimum is now $(7/2,4)$, still nonintegral. The fractional $x_1$ row gives the next Gomory fractional cutThe negative left-hand coefficient $-1/2$ of $s_3$ also has fractional part $1/2$. Normalize the new integer slack variable as $s_4=7-x_1-x_2$. Its dictionary row is $s_4=-1/2+s_1/2+s_3/2$. The dual simplex algorithm chooses $s_3$ to enter: its ratio is $1/(1/2)=2$, compared with $2/(1/2)=4$ for $s_1$. Substitution givesSetting the nonbasic $s_1,s_4$ to zero gives a feasible integer solution. The final objective row bounds every point in the cut relaxation by $25$, so the integer optimum isBoth cuts are valid for every original integer feasible point, making this also a certificate for the original integer program.

Use the usual finite binary encoding of integer or rational input data. NP consists of decision problems whose yes-instances have polynomial-length certificates in computational complexity verifiable in polynomial time. A decision problem is NP-hard if every problem in NP has a polynomial-time many-one reduction to it. It is NP-complete if it is both NP-hard and in NP. An optimization problem is NP-hard when computing its optimum would solve every NP decision problem through a polynomial-time reduction and an optimum-value query; membership in NP applies directly to decision problems, not to an unqualified optimization task.

Reduce subset sum to the 0-1 knapsack problem by setting $v_i=w_i=s_i$ and $B=t$. Every feasible value is at most $t$, and the optimum equals $t$ exactly when the subset sum answer is yes. The transformation and final comparison take polynomial time. Since subset sum is assumed NP-complete, exact knapsack optimization is NP-hard.

For the half-approximation algorithm for knapsack, use nonnegative weights and profits. Delete overweight items and nonpositive-profit items; take all positive-profit zero-weight items for free. On the remaining positive-weight items, sort decreasing $v_i/w_i$. Take the maximal initial prefix fitting the capacity, and stop at the first item that would overflow. Let $G$ be the prefix profit, and let $M$ be the largest profit of any individually feasible remaining item. Return the better of the prefix and that singleton, together with the free items. If every item fits, take them all.

The fractional knapsack problem fills exactly that prefix and a fraction $\alpha \in [0,1)$ of the first excluded item. Its optimum bounds the integer optimum, and without the free items its value is at most $G+\alpha v_{\mathrm{next}}\le G+M$. ThusWith total free profit $F$, the same inequality is $F+\max (G,M)\ge \frac{1}{2}(F+G+M)$. This gives an approximation ratio of $1/2$ in $O(n\log n)$ sorting time, with polynomial bit complexity for rational data. Nonnegative weights and capacity are the standard knapsack problem assumptions; unrestricted negative weights would not support this argument.

For the quadratic knapsack problem and its fractional row bound for quadratic knapsack, multiply the capacity inequality by the binary $x_i$ and use $x_i^2=x_i$:Remove items with $w_i>B$ first. If $x_i=1$, the remaining coordinates $x_j$ are feasible in the fractional problem defining $q_i$, so ${\sum }_{j\ne i}{p}_{ij}{x}_j\le q_i$. If $x_i=0$, that row's contribution is zero. Hence, with $c_i=v_i+q_i$,The double sum counts each symmetric interaction twice; there is no factor $1/2$ in this problem. Each $q_i$ is a fractional knapsack problem, computable by sorting positive $p_{ij}/w_j$ ratios, also handling zero weights separately. This takes polynomial time even when some interactions are negative, because an optional fractional item with negative profit is omitted.

The resulting 0-1 knapsack problem need not be solved exactly. Relax its capacity constraint with a Lagrange multiplier $\lambda \ge 0$. Its Lagrangian knapsack bound isFor feasible $x$, adding $\lambda (B-{\sum }_i{w}_i{x}_i)$ only increases its objective, and maximizing over independent binary choices produces the displayed expression. It is a convex piecewise-linear function with breakpoints at positive $c_i/w_i$. Evaluate those breakpoints and zero, or use the fractional knapsack problem ordering; the best bound is computable in polynomial time. Thus computing all $q_i$ and one additional Lagrangian relaxation gives the requested upper bound.

For the numerical example, the $q_1$ problem has capacity $3$ and item ratios $10/2=5$ and $12/3=4$. Select $y_2=1$ and $y_3=1/3$. This givesAn exchange argument justifies optimality: capacity used on the lower-ratio item can be transferred to the higher-ratio item until the latter is full. The stated $q_2=20$ and $q_3=15$ similarly follow from residual capacities $2$ and $1$. Therefore $c=(24,40,30)$, with ratios $24,20,10$. The fractional solution takes items $1,2$ and one-third of item $3$, yielding $74$. At $\lambda =10$ the Lagrangian knapsack bound gives the same value:The fractional solution attaining $74$ proves that this is the best bound from this auxiliary Lagrangian relaxation, though it need not be the exact quadratic optimum.

For branch and bound, branch on whether an unresolved $x_i$ is zero or one. If the selected set is $S$, subtract its weight from the residual capacity and retain its exact objective as a constant. For each remaining item replace $v_i$ by $v_i+2{\sum }_{j\in S}{p}_{ij}$, preserving the original interactions between remaining items. Recompute the fractional row bounds and the Lagrangian knapsack bound for that residual problem. Maintain an incumbent from genuine feasible binary solutions evaluated with the quadratic objective; prune infeasible nodes and nodes whose bound is no better than the incumbent. For example, selecting items $1,2$ gives the feasible value $50$. A finite binary branching tree eventually certifies the optimum, but worst-case running time is exponential, as expected for an NP-hard problem.

Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply $1$ and agent vertices demand $1$. An arc from job $i$ to agent $j$ has cost $c_{ij}$ and nonnegative flow $x_{ij}$; an upper bound $1$ may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem isInteger supplies and demands give an integral optimum by integrality of the transportation problem. Its $n$ positive arcs form a perfect matching, hence give one job per agent.

A network simplex algorithm basis for this connected $2n$-vertex network has $2n-1$ tree arcs, whereas an integral assignment has only $n$ positive flows. For $n>1$, at least $n-1$ basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.

Suppose the assignment dual potentials satisfy ${\lambda }_i-{\mu }_j\le c_{ij}$. For every feasible assignment $y$,If the selected assignment $x$ uses only arcs with ${\lambda }_i-{\mu }_j=c_{ij}$, its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by $x_{ij}$; the TeX aid mistakenly replaces it with ${\lambda }_{ij}$.

The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where $r_{ij}=c_{ij}-{\lambda }_i+{\mu }_j\ge 0$. Search for an augmenting path in a matching in this equality graph. If there is none, let $S$ be the reachable jobs and $T$ the reachable agents in the alternating search from unmatched jobs. Every agent in $T$ is matched to a job in $S$. SetReduced costs from $S$ to its complement decrease by $\Delta$, those from outside $S$ into $T$ increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.

For the example, start with the row minima $\lambda =(10,50,50)$ and $\mu =(0,0,0)$. The reduced cost matrix isMatch job $1$ to agent $1$. Searching from both unmatched jobs gives $S=\{1,2,3\}$ and $T=\{1\}$; the minimum cost to an agent outside $T$ is $\Delta =10$. Update to $\lambda =(20,60,60)$ and $\mu =(10,0,0)$:The new equality edge $(2,3)$ augments the matching. From unmatched job $3$, the next alternating search reaches agent $1$ and its matched job $1$, giving $S=\{1,3\}$ and $T=\{1\}$. Now $\Delta =15$. The updated feasible assignment dual potentials and reduced costs areThe augmenting path in a matching $J_3\to A_1\to J_1\to A_2$ uses job $3$ to agent $1$, the reversed matched edge to job $1$, then the new edge to agent $2$. It gives the optimal assignmentThe dual linear program value is $35+60+75-25=145$, an independent optimality certificate.

Let $u,v$ be the row and column mixed strategies, so their entries are nonnegative and sum to one. The payoffs are $u^{\mathsf{T}}Pv$ and $u^{\mathsf{T}}{P}^{\mathsf{T}}v$. A Nash equilibrium is a pair in which each strategy is a best response to the other: neither player can improve its expected payoff by a unilateral change of mixed strategy. Equivalently, every positive-probability pure strategy attains that player's maximum pure-strategy payoff against the opposing mixture.

For the complementarity construction of a symmetric Nash equilibrium put $s={\sum }_i{x}_i>0$ and $u=x/s$. The equation $Px+z=1$ gives $Px\le 1$. Nonnegativity and $x^{\mathsf{T}}z=0$ imply $x_i>0\Rightarrow z_i=0\Rightarrow (Px{)}_i=1$. Therefore every used pure strategy has payoff $1/s$ against $u$, while all other pure strategies have payoff at most $1/s$. The same vector of pure-strategy payoffs applies to the column player in this symmetric bimatrix game. Thus a symmetric Nash equilibrium is

For a genuine Lemke-Howson algorithm path, use two separate vectors, $\xi$ for the row player and $\eta$ for the column player, with slacksGive labels $i=1,2,3$ to ${\xi }_i=0$ or $r_i=0$, and labels $3+j$ to ${\eta }_j=0$ or $s_j=0$. A nonzero completely labeled pair has ${\xi }_i{r}_i=0$ and ${\eta }_j{s}_j=0$, and normalization yields mutual best responses. At the artificial pair $(\xi ,\eta )=(0,0)$ all six labels are present.

Drop label $3$ by increasing ${\xi }_3$. The two limiting rows of $P\xi \le 1$ are $3{\xi }_3\le 1$ and $2{\xi }_3\le 1$, so the minimum-ratio pivot stops at ${\xi }_3=1/3$, where $s_2=0$. Label $5$ is now duplicated, since ${\eta }_2=0$ also carries it. Increase ${\eta }_2$ to remove that duplicate. The limiting inequalities are $3{\eta }_2\le 1$ and $4{\eta }_2\le 1$, so the next pivot stops at ${\eta }_2=1/4$, where $r_3=0$ restores the dropped label $3$. The endpoint isIt has all six labels and satisfies both complementarity conditions. After normalization, the Lemke-Howson algorithm returnsAgainst column strategy $2$, row strategy $3$ pays $4$, exceeding $3$ and $0$. Against row strategy $3$, column strategy $2$ pays $3$, exceeding $0$ and $2$. This verifies the endpoint directly.

To find every other Nash equilibrium, observe that row strategy $3$ strictly dominates row strategy $1$: the payoff differences against the three columns are $(2,1,2)$, all positive. By symmetry, column strategy $1$ is also strictly dominated. Neither can appear in an equilibrium. The reduced strategies $2,3$ have row payoff matrixThe two pure Nash equilibria are $(e_2,e_3)$ and $(e_3,e_2)$. If the opponent uses strategy $2$ with probability $q$, the payoffs of strategies $2,3$ are $3(1-q)$ and $2+2q$. Indifference requires $q=1/5$. The same computation applies to the other player. A player mixing both strategies forces this exact opposing mixture; a player playing a pure strategy has a unique opposing best response, producing one of the two pure equilibria. Hence there are exactly three Nash equilibria:For the symmetric mixed equilibrium, the original complementarity construction can use $x=(0,1/12,1/3)$ and $z=(3/4,0,0)$; it gives payoff $12/5$ to each player after normalization.

Let $A$ be a finite set of alternatives with $|A|\ge 3$, and let each agent report a strict total order on $A$. A profile is the tuple of these orders. The domain is unrestricted: every tuple of orders is allowed. A deterministic social choice function $f$ selects one alternative from each profile. It is onto if every alternative is selected at some profile. It is strategyproof if no agent, holding all other reports fixed, can obtain an outcome strictly preferred according to its true order by reporting another order. A dictatorship in social choice means that one fixed agent's highest-ranked alternative is always selected, regardless of all other reports.

The Gibbard-Satterthwaite theorem says that every onto, deterministic strategyproof social choice function on this unrestricted domain is a dictatorship in social choice. Equivalently, with at least three possible alternatives an onto nondictatorial rule must permit manipulation. Both the number of alternatives and the unrestricted preference domain are essential hypotheses.

For the requested top-bottom decisiveness lemma, suppose $f(R,S)=a$, with $a$ top in $R$ and bottom in $S$. Fix any $R^{\prime }$ with $a$ top. If $f(R^{\prime },S)\ne a$, agent $1$ with true order $R^{\prime }$ could report $R$ and obtain its best outcome $a$, contrary to strategyproofness. Hence $f(R^{\prime },S)=a$. Now fix any $S^{\prime }$. If $f(R^{\prime },S^{\prime })=b\ne a$, agent $2$ with true order $S$ could report $S^{\prime }$ and obtain $b$, which is better than its bottom alternative $a$. ThereforeCall this agent $1$ being decisive for $a$. The same argument with agents interchanged applies to agent $2$.

Here is a complete proof of the two-agent theorem. First, onto plus strategyproofness gives unanimity. If $a$ occurs at some profile, change agent $1$ to any order with $a$ top: a different outcome would allow that agent to obtain $a$ by returning to its old report. Then change agent $2$ to any order with $a$ top in the same way. Thus every profile with both agents ranking $a$ top selects $a$.

We also need Pareto efficiency. A useful rank-raising monotonicity lemma follows from strategyproofness: if the current outcome is $b$, and one agent changes its order without placing above $b$ any alternative previously below $b$, the outcome remains $b$. Otherwise an outcome $c\ne b$ would satisfy $b\succ c$ in the old order, since a profitable deviation is forbidden there, but $c{\succ }^{\prime }b$ in the new order, since reporting the old order is forbidden there. Those comparisons contradict the allowed change. If both agents prefer $a$ to a selected $b$, change their orders one at a time to put $a$ first and $b$ second. These changes only raise $b$ relative to other alternatives, so the outcome remains $b$, contradicting unanimity for $a$. Therefore an alternative unanimously dominated by another cannot be selected.

Choose distinct $a,b$. Give agent $1$ order $b\succ a\succ \text{the rest}$ and agent $2$ order $a\succ b\succ \text{the rest}$. Pareto efficiency forces the outcome to be $a$ or $b$. If it is $b$, move $b$ to the bottom of agent $2$'s order while keeping $a$ top. A switch to $a$ would be a profitable deviation for its old true order. Every other alternative is unanimously dominated by $a$. Hence the outcome stays $b$, and the top-bottom decisiveness lemma makes agent $1$ decisive for $b$. If the outcome is $a$, the symmetric argument makes agent $2$ decisive for $a$. Consequently some agent is decisive for some alternative. Rename that agent $1$ and that alternative $a$.

Both agents cannot be decisive for this same $a$. To see this, choose $b,c\ne a$ distinct, with every remaining alternative below these three, and considerAt $(R,S^{\prime })$, agent $1$ can obtain $a$ by placing it top, so strategyproofness restricts the outcome to $a$ or $b$. Both agents prefer $b$ to $a$, so Pareto efficiency forces $b$. At $(R^{\prime },S^{\prime })$, agent $1$ still ranks $b$ top and can obtain it by reporting $R$, so the outcome must again be $b$. On the other hand, at $(R^{\prime },S)$, decisiveness of agent $2$ for $a$ restricts the outcome to $a$ or $c$. Both agents prefer $c$ to $a$, so it must be $c$. Since $c$ is top in $S^{\prime }$, agent $2$ can obtain it at $(R^{\prime },S^{\prime })$ by reporting $S$, forcing outcome $c$ there. This contradiction proves that agent $2$ is not decisive for $a$.

Now fix $b\ne a$ and any agent-$1$ order $R$ with $b$ first and $a$ second. At every $(R,S)$, agent $1$ can force $a$ by placing it top, so the outcome must lie in $\{a,b\}$. If $a$ occurs for even one report $S$, changing agent $2$ to an order with $a$ first and $b$ second preserves $a$, because it can return to $S$ to obtain its top choice. Lower $a$ to the bottom of agent $1$'s order, keeping $b$ top. A switch to $b$ would be a profitable deviation under its old order, and any other outcome is unanimously dominated by $b$. Thus $a$ remains selected at a profile where agent $2$ ranks it top and agent $1$ ranks it bottom. The top-bottom decisiveness lemma would make agent $2$ decisive for $a$, a contradiction.

Therefore every $(R,S)$ with agent $1$ ranking $b$ first and $a$ second selects $b$. Choose $S$ with $b$ bottom and apply the top-bottom decisiveness lemma once more: agent $1$ is decisive for $b$ in every order placing $b$ top. This holds for each $b\ne a$, and it already holds for $a$. Agent $1$ is a dictator in social choice, proving the two-agent theorem.

With three agents and only two alternatives, the two-alternative majority rule is onto and strategyproof and has no dictator in social choice. An agent whose vote is not pivotal cannot change the outcome. A pivotal agent obtains its preferred alternative by voting truthfully and its less preferred alternative by reversing its vote. No one is a dictator in social choice, since the other two agents can both oppose its preference. There is no tie with three agents. This does not contradict the theorem because its hypothesis $|A|\ge 3$ fails.

Use the standard risk-neutral quasilinear utility model: utility is value received minus payment. A bidder may abstain for utility zero, payments to the seller are nonnegative, and the zero-value type has utility zero. The last normalization is necessary for the requested revenue formula; if arbitrary subsidies were allowed, an additive payment constant would remain undetermined. The independent private values model is symmetric, and each bidder has a unit-demand valuation in the two-item part. Participation satisfies individual rationality.

Let $G(\theta )$ be the interim probability of receiving an item and $m(\theta )$ the interim expected payment of a type $\theta$. Write $u(\theta )=\theta G(\theta )-m(\theta )$. By mimicking the Bayesian Nash equilibrium bid of a type $z$, a type $\theta$ could obtain utility $\theta G(z)-m(z)$. Equilibrium therefore gives, for $\theta >z$,The lower inequality uses type $\theta$'s incentive constraint, and the upper uses type $z$'s. Since $G$ is continuous in these auctions, the inequalities give $u^{\prime }(\theta )=G(\theta )$. With $u(0)=0$,This is the interim payment identity underlying revenue equivalence.

For one item, independence and the uniform distribution give $G(\theta )={\theta }^{n-1}$: all other values must be below $\theta$. Hence the expected payment from a bidder conditional on its value isThis is an unconditional-in-winning interim payment, not the amount paid conditional on winning. In the first-price sealed-bid auction, $m(\theta )=b(\theta )G(\theta )$, so the Bayesian Nash equilibrium bid iswith $b(0)=0$. For $n=1$, the seller's revenue is zero and a zero bid suffices under the stipulated allocation rule.

For two items and three unit-demand bidders, a type $\theta$ wins if at most one of the other two values exceeds it. ThereforeThe interim payment identity gives $m(\theta )={\theta }^2-2{\theta }^3/3$. Dividing by the winning probability gives the symmetric Bayesian Nash equilibrium bidTo check that this is an Bayesian Nash equilibrium rather than just a necessary formula, its derivative is $b^{\prime }(\theta )=2(1-\theta )(3-\theta )/[3(2-\theta {)}^2]$, positive for $0\le \theta <1$. A type $\theta$ mimicking a type $z$ receives utility $\theta G(z)-m(z)$, whose derivative in $z$ is $(\theta -z)G^{\prime }(z)$. It is positive before $z=\theta$ and negative after it, so the truthful type-matching bid is globally optimal. Bids above the highest Bayesian Nash equilibrium bid can only increase payment without increasing the winning probability; the usual nonnegative bid range covers the lower boundary.

By symmetry and the law of total expectation, the seller's expected two-item revenue isFor one item and the same three bidders,More generally the single-item revenue with $n$ bidders is $(n-1)/(n+1)$. Allocating a second item lowers competition enough that it adds no expected revenue in this particular three-bidder uniform model.

The final mechanism is a direct revelation mechanism because the message submitted by bidder $i$ is its valuation report, in the same type space $[0,1]$, and allocation and payment are explicit functions of those reports. It is the Clarke pivot mechanism for selecting two unit-demand winners. Truthful reporting is a dominant strategy: bidder $i$'s utility equals its true allocation value plus the other bidders' reported allocation values, minus a term depending only on the others' reports. Reporting its true value makes the efficient allocation maximize the first two terms, while the last is unaffected by its report.

Let the ordered values be ${\theta }_{(1)}\le {\theta }_{(2)}\le {\theta }_{(3)}$. For a winner $i$, the maximum welfare achievable by the other two bidders is their combined value; in the actual allocation only the other winner receives an item. Thus the difference defining its payment is the excluded bidder's value ${\theta }_{(1)}$. For the loser, both other bidders receive items already, so its payment is zero. Consequently both winners pay the lowest valuation, andThis equals the first-price sealed-bid auction revenue above. A conditional check gives the same interim payment identity: the minimum of the other two values has density $2(1-z)$, and bidder $i$ wins exactly when that minimum is below $\theta$. Its conditional expected pivot payment is ${\int }_0^{\theta }2z(1-z)dz={\theta }^2-2{\theta }^3/3=m(\theta )$. The mechanisms have equal expected revenue, even though their realized payments need not coincide.