Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 42 (Contest Theory)

Use the usual independent private values model, quasilinear utility, and voluntary participation with zero outside utility. These assumptions matter: without individual rationality, arbitrary type-independent entry charges make revenue unbounded, and correlated types cannot in general be described by their marginal priors alone.

The revelation principle lets us optimize over direct revelation mechanisms satisfying Bayesian incentive compatibility. Write $x(v)\in [0,1]$ for the common project allocation, $X_i(t)={\mathbb{E}}_{V_{-i}}x(t,V_{-i})$ for player $i$'s interim allocation, and $P_i(t)$ for its interim payment. The interim payment identity givesSince interim individual rationality requires $U_i({\underline{v}}_i)\ge 0$, the virtual-surplus revenue identity bounds expected revenue byThe best feasible common allocation at each valuation profile therefore provides the project when total virtual surplus is nonnegative:Because each regular prior has a nondecreasing virtual valuation, this allocation is a nondecreasing function of each player's report. Hold $v_{-i}$ fixed and charge the critical-value paymentThis is the winning threshold when it lies in the support, the lowest allowed value if every type wins, and zero if the player loses. A truthful winner never pays more than its value; a losing type cannot profit by crossing the threshold. Thus the mechanism has dominant-strategy incentive compatibility and ex post individual rationality, with zero utility at every lowest type. It attains the revenue bound, proving optimality even among mechanisms requiring only Bayesian incentive compatibility. At a zero-virtual-surplus tie, choose any fixed rule that preserves monotonicity.

For independent uniform distributions on $[0,1]$, the virtual valuations are ${\varphi }_i(v_i)=2v_i-1$. The revenue-optimal public-project auction becomesWhen it is provided, player $i$ paysotherwise every payment is zero. If the displayed threshold exceeds one, player $i$ cannot induce provision within its allowed support; if it is negative, provision is independent of its own report and its payment is zero. For $n=1$, this specializes to a reserve value and payment of $1/2$.

Assume the usual continuous nonnegative valuation distribution, so ties occur only on zero-probability events. Put $t=F(v)$. In a monotone symmetric Bayesian Nash equilibrium, a type $v$ is first with probability $t^{n-1}$ and second with probability $(n-1)(1-t)t^{n-2}$. Its rank-order expected prize allocation in $G_1$ is thereforeThe all-pay effort identity gives $b_1(v)={\int }_{\underline{v}}^{v}s{a}_1^{\prime }(s)ds$. It also verifies equilibrium directly: a type $v$ imitating type $z$ has utility $v{a}_1(z)-b_1(z)$, whose derivative is $(v-z)a_1^{\prime }(z)$, so the true type is a best response.

In the first version of $G_2$, the two contests have expected allocationsThere is no common effort budget, and quasilinear utility makes the two effort choices separable. Since $a_{21}+a_{22}=a_1$, adding their all-pay effort identities yieldsThe equality holds type by type for aggregate effort, rather than only after taking expectations. The within-player correlation of the two efforts does not enter these additive expected payoffs.

For the second version of $G_2$, let $V_{[1]}\ge \cdots \ge V_{[n]}$ denote descending order statistics. The expected effort in a rank-order contest with prize vector $(2,1,0,\dots )$ isEquivalently, decompose the allocation into a unit award to the best player and a unit award to each of the best two players, then use revenue equivalence: the corresponding total auction payments are $V_{[2]}$ and $2V_{[3]}$. Two separate first-place contests with prize values one and two instead generateConsequentlyFor a nondegenerate continuous distribution, the inequality is strict. No regularity of virtual valuations is needed for this comparison. With a uniform distribution on $[0,1]$, the two totals are $(3n-5)/(n+1)$ and $3(n-1)/(n+1)$, giving a difference of $4/(n+1)$.

Interpret the contests as standard all-pay auctions: the highest effort among entrants wins, ties are shared uniformly, and an unentered contest awards no prize. The printed question does not specify a prize allocation rule; the highest-effort convention is the one used for standard all-pay contests in the course author's 2014 lecture slides. Under this convention, we can characterize the unique symmetric participation probabilities and bid marginals. Uniqueness of the entire joint mixed strategy requires a further restriction on dependence, as explained below.

Let $q_j$ be the probability that a player omits contest $j$. Since every player enters exactly two contests, $q_1+q_2+q_3=1$. Let $G_j(b)$ be the probability that a rival is absent from contest $j$ or enters it with effort at most $b$. Rivals' strategy draws are independent between players. For a positive bid $b$ outside a measure atom, the expected payoff from this contest isAn all-pay auction cannot have a positive-effort measure atom in a symmetric equilibrium: slightly overbidding that measure atom gives a positive discrete increase in the winning probability at an arbitrarily small extra cost. Nor can active bids have a measure atom at zero when entry has positive probability, because a small positive bid beats tied zero bids. Gaps inside the active effort support are impossible: moving a bid from the top of a gap to just above its bottom preserves its winning probability and lowers its cost. The effort support starts at zero, because lowering its positive lower endpoint would preserve the chance that every rival is absent.

The all-pay indifference equation with random entry consequently gives the maximal per-contest payoffEvery $q_j$ lies strictly between zero and one. First, if $q_j=1$, the other two contests have certain entry and zero per-contest payoff, while deviating into the unused contest wins a positive prize. This contradicts equilibrium. Next, if $q_j=0$, the remaining omission probabilities sum to one and neither can equal one, so both are positive. Contest $j$ has zero per-contest payoff, whereas both other contests have strictly positive payoffs. Every pair containing $j$ is then worse than omitting it and entering the other two, contradicting certain entry in $j$.

Every omission therefore occurs with positive probability. The three entered pairs must give the same maximal payoff, which forces $u_1=u_2=u_3=u>0$. Normalizing the omission probabilities gives the two-of-three all-pay participation equilibrium:Conditional on entering contest $j$, the effort has distribution functionextended by zero below this interval and one above it. The inequalities $q_1\le q_2\le q_3$ show that the larger prizes are entered more often.

To construct an equilibrium, omit $j$ with probability $q_j$, then draw the two active efforts independently with their respective conditional distributions $H_k$. Every bid in a contest's effort support earns $u$; a bid above $w_j-u$ earns at most $w_j-b<u$. Thus no effort deviation or choice of a different pair improves on total payoff $2u$. This proves existence and verifies the Nash equilibrium without relying only on the indifference equations. The arguments above also prove uniqueness of the omission probabilities and the per-contest marginal distributions.

For the full joint strategy law, however, the printed uniqueness claim is too strong. Given an entered pair $k,\ell$, either use two independent uniform random variables $U,V$ and bids $(H_k^{-1}(U),H_{\ell }^{-1}(V))$, or use a single uniform $U$ and bids $(H_k^{-1}(U),H_{\ell }^{-1}(U))$. These are different copulas with the same conditional marginals. A fixed deviation's expected additive payoff only uses the rivals' per-contest marginal distributions, so both constructions remain Nash equilibria. This is the marginal-equivalent equilibria in additive contests phenomenon. The participation probabilities and bid marginals are unique; the full joint mixed strategy is not unique unless a dependence convention is imposed. Independent conditional sampling gives one canonical representative.

First exclude boundary profiles. At $(0,0)$, player $i$ can replace its payoff $v_i/2$ by $v_i-{\epsilon }^2>v_i/2$ using a sufficiently small positive effort. If one effort is positive and the other is zero, the positive bidder can lower its effort while retaining the entire prize. Thus a pure Nash equilibrium of this proportional allocation contest must have both efforts positive.

Against $b_j>0$, player $i$'s payoff is a strictly concave function of $b_i\ge 0$, sinceIts derivative at zero is positive and its payoff tends to negative infinity as its own effort tends to infinity. Hence its unique best response is the positive solution of the first-order condition. At an equilibrium, writing $B=b_1+b_2$, these conditions areDividing them gives $b_1/b_2=\sqrt{v_1/v_2}$, and multiplying them gives $B^4=v_1{v}_2/4$. Therefore the quadratic-cost two-player proportional contest hasBoth efforts are positive, and strict concavity makes them global best responses. The first-order conditions have only this positive solution, while the boundary profiles have already been excluded. This proves both existence and uniqueness. The resulting winning probabilities are $x_i^{\ast }=\sqrt{v_i}/(\sqrt{v_1}+\sqrt{v_2})$; for equal values $v$, each effort is $\sqrt{v/8}$.

Use positive ability parameters in the Bradley-Terry model, so $\mathbb{P}(i\text{ beats }j)={\theta }_i/({\theta }_i+{\theta }_j)$. If the course instead denotes log abilities by ${\theta }_i$, apply the following calculation to their exponentials; the ordering is unchanged. Up to a factor independent of the abilities, the likelihood function isThe observed wins form a directed cycle, so a finite maximum exists. The Bradley-Terry likelihood Hessian is negative definite on contrasts of log abilities, giving uniqueness up to common scaling. We can therefore find the maximum-likelihood estimate through the Bradley-Terry score equations.

Player 1 has one observed win in two comparisons. Its score equation iswhich simplifies to ${\theta }_1^2={\theta }_2{\theta }_3$. By the model's scale invariance, set ${\theta }_2=1$ and write ${\theta }_1=r$, ${\theta }_3=r^2$, with $r>0$. Player 2's score equation becomesThe left side of the polynomial equation is strictly increasing on $r>0$, starts at zero, and tends to infinity. For $k=1$, its unique solution is $r=1$. For $k>1$, its value at one is $2k-1>1$, so its solution satisfies $0<r<1$. The Three-player Bradley-Terry comparison cycle consequently givesThus there is a complete tie when each directed edge is observed once, and otherwise the decreasing ranking is 2, 1, 3.