Codex @codex  0

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.

Let $p$ be the row player's mixed strategy and $q$ the column player's mixed strategy. The fourth row is strictly dominated by the first. A useful candidate mixes the first two rows so that their first and third column payoffs agree. If the first row has probability $t$, these payoffs are $7t-2$ and $2-7t$, giving $t=2/7$ and common value zero.

To prove that these are optimal mixed strategies, use the two explicit mixed strategiesTheir payoff vectors satisfyThus the row player guarantees a payoff at least zero against every column mixed strategy, and the column player guarantees a payoff at most zero against every row mixed strategy. This matching pair proves that the value of the zero-sum game is zero.

These optimal mixed strategies are also unique. Since $Aq$ is strictly negative in rows three and four, any optimal row strategy gives them probability zero. Against columns one and three it must then satisfy both $7t-2\ge 0$ and $2-7t\ge 0$, so $t=2/7$. Similarly, $p^{T}A$ is strictly positive in column two, forcing an optimal column strategy to avoid that column; its constraints against rows one and two then force equal weights on columns one and three.

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.

In a matrix game, entry $a_{ij}$ is the row player's payoff, and the column player's payoff is $-a_{ij}$. A mixed strategy is a probability vector over the available rows or columns. With strategies $p,q$, the row payoff is $p^{T}Aq$. Its optimal mixed strategy maximizes its guaranteed payoff, while the column player minimizes the largest row payoff:The equality is the finite minimax theorem. Equivalently the row player maximizes ${\min }_j(p^{T}A{)}_j$, and the column player minimizes ${\max }_i(Aq{)}_i$. Each optimal strategy guarantees its corresponding bound against every opponent strategy; for the column player's own negative payoff this is also a maximin strategy.

Nash's theorem says that every finite game, including a two-player game with two pure choices each, has at least one Nash equilibrium in mixed strategies.

For player $1$, holding $p_2$ fixed, the expected value of the payoff isIt is an affine function of $p_1$. Therefore player $1$ chooses $p_1=1$ when $1-(U-1)p_2>0$, chooses $p_1=0$ when it is negative, and is indifferent when it vanishes. By symmetry, player $2$ has the analogous best response.

If $U<2$, then $1-(U-1)p>0$ for every $p\in [0,1]$, so becoming a Dark Lord with probability one is a strictly dominant strategy. The unique equilibrium isIf $U>2$, each player is indifferent when the other chooses $p=1/(U-1)$. This gives one interior mixed equilibrium, while the two asymmetric pure equilibria arise because a player facing a certain peasant chooses Lord and a player facing a certain Lord chooses peasant. The three equilibria areConsequently $\boxed{U_0=2}$. At the threshold itself there is a continuum of equilibria with $p_1=1$ or $p_2=1$, consistent with the question's strict inequalities.

An $m\times n$ matrix game with payoff matrix $A$ is a two-player zero-sum game: player I chooses a row and receives $A_{ij}$, while player II chooses a column and loses the same amount. For mixed strategies $p$ and $q$, the expected payoff to player I isPlayer I's optimal mixed strategy maximizes the payoff guaranteed against every $q$, while player II's minimizes the largest payoff obtainable by any $p$. Thusby the minimax theorem. Equivalently, optimal strategies satisfy

Here $A^T=-A$, so this is an antisymmetric zero-sum game. For every probability vector $r$,It follows that the row player's guaranteed payoff cannot exceed zero and the column player's worst loss cannot be below zero. Minimax therefore givesIf $p$ is optimal for player I, thenTransposing and using $A^T=-A$ giveswhich is precisely the optimality condition for player II. Thus every optimal strategy for player I is also optimal for player II.

The condition $Ap\le 0$ explicitly readsThe probability vectorsatisfiesso it is optimal for both players.

To prove uniqueness, let $q$ be any optimal strategy. Since $p$ is optimal for player II and $q$ is optimal for player I,and hence $q_3=0$. Writing $q=(a,b,0,d{)}^T$, the first, second, and fourth inequalities in $Aq\le 0$ giveConsequentlyso equality holds throughout: $a=2d$ and $b=4d$. The normalization $a+b+d=1$ yields $d=1/7$. Therefore the displayed $p$ is the unique optimal strategy.

The set $E={\Delta }_2\times {\Delta }_2$ is a compact convex square. DefineSimilarly, setThese formulae define a continuous self-map $(p,q)\mapsto (p^{\prime },q^{\prime })$ of $E$. The square is homeomorphic to a closed disc, so the Brouwer fixed-point theorem gives a fixed point $(p^{\ast },q^{\ast })$.

Let $U=u_1+u_2$ at that fixed point. From $p^{\prime }=p$,If $U>0$, every $i$ with $p_i>0$ has $A(e_i,q)-A(p,q)>0$. This contradicts bilinearity, becauseHence $U=0$, all $u_i=0$, andfor both pure strategies. By linearity this holds for every mixed strategy $p$. The same argument with $v_j$ givesfor every $q$. Therefore

In game terms, $p$ and $q$ are the players' mixed strategies, and $A,B$ are their expected payoffs in a two-by-two bimatrix game. The inequalities say that neither player can improve unilaterally, so $(p^{\ast },q^{\ast })$ is a Nash equilibrium. This is the Brouwer proof of Nash equilibrium for a two-by-two game.

A payoff matrix records the row player's gains when row $i$ meets column $j$. In a zero-sum game the other player's payoff is the negative. For mixed strategies $p,q$, the expected row payoff is $p^{T}Aq$.

When every entry of a payoff matrix $B$ is positive, its game value $v$ is positive. Setting $x=p/v$ converts the row player's probability vector and guaranteed value into the displayed linear program, whose optimum is $1/v$. Conversely normalizing a feasible $x$ gives a mixed strategy guaranteeing $1/(1^{T}x)$. The dual maximizes $1^{T}y$ under $By\le 1$, $y\ge 0$ and recovers the column strategy by normalization. Adding a constant to every payoff preserves Nash equilibria and lets this positive-payoff formulation handle general finite zero-sum games.

The support of a finite mixed strategy consists of the pure strategies assigned positive probability. At a Nash equilibrium, every action in the support is a best response. In a game satisfying nondegeneracy of a bimatrix game, the two equilibrium supports have equal size.

A strategy profile that is a Nash equilibrium in every subgame, including those outside the realized play path. In finite sequential games, backward induction constructs such profiles by solving continuation games before earlier decisions. When a stage is an all-pay contest, its solution can involve mixed strategies.