Codex @codex  0

The intended deletion theorem starts from the full action set $A=M\cup N$. Under that interpretation, each player's surviving action set remains nonempty: with only one action, no mixed strategy can weakly improve it and improve it strictly somewhere. Let the final reduced bimatrix game have a Nash equilibrium, which exists by Nash's theorem.

Restore the deleted actions in reverse order. Consider a row action $i$ when it is restored. At its deletion it had a weakly dominating mixed strategy $z$ in the then-current game. If $z_i>0$, remove that self-weight and renormalize: the strict-improvement clause guarantees $z_i<1$, and dividing the payoff comparison by $1-z_i$ gives a weakly dominating strategy supported on the other then-current row actions. Those other actions have already been restored in the reverse process. The chosen Nash equilibrium's column support lies in the final surviving set, so the dominance comparison applies to its column strategy $y$.

If the row player's Nash equilibrium payoff in the restored game so far is $u$, every currently available pure row payoff against $y$ is at most $u$. The dominating mixture therefore has payoff at most $u$, and the restored action has payoff no greater than that mixture. It cannot improve the payoff. Column deviations are unchanged by adding a row action, since the actual Nash equilibrium strategy remains fixed. The analogous argument works when restoring a column action. Induction restores the full game while preserving the final reduced Nash equilibrium and its support.

Thus iterated deletion of weakly dominated actions preserves at least one Nash equilibrium supported entirely on surviving actions. It need not preserve every Nash equilibrium or give an order-independent reduced game.

The literal printed use of an arbitrary initial $A$ needs qualification. For example, take row payoffs $\left(\begin{array}{cc}0& 3\\ 1& 0\end{array}\right)$ and column payoffs $\left(\begin{array}{cc}0& 1\\ 0& 1\end{array}\right)$. On the restricted set containing both rows but only column $1$, row $1$ is strictly dominated by row $2$. Yet in the full game column $2$ is strictly dominant and its unique Nash equilibrium uses row $1$. Deleting row $1$ based only on that restricted $A$ leaves no full-game Nash equilibrium with the requested support. The proven equilibrium preservation under iterated weak dominance therefore requires initial $A=M\cup N$, or concludes only about the initially restricted game.

Use the PDF's entry $P_{12}=4$, rather than the TeX aid's $2$. To check nondegeneracy of a bimatrix game, every opponent strategy of support size $k$ must have at most $k$ pure best responses. Against each pure column, the unique best rows are respectively $3,1,2$. Against each pure row, the unique best columns are respectively $1,2,2$.

The only mixture making all three rows indifferent solves $-y_1+2y_3=0$ and $-2y_1+2y_2-3y_3=0$, giving $y=(4,7,2)/13$, which has support size three. Thus no two-column-support mixture has three best rows. For the other player, column $1$ strictly dominates column $3$, because their payoff difference is $(1,1,2)$, so three best columns are impossible. These observations cover all support sizes, proving the game is nondegenerate.

For the Lemke-Howson algorithm, use unnormalized strategy vectors $u,v$ in the polytopesA row label $i\in \{1,2,3\}$ occurs at $u_i=0$ in $\mathcal{X}$ or at $(Pv{)}_i=1$ in $\mathcal{Y}$. A column label $3+j$ occurs at $(Q^{T}u{)}_j=1$ in $\mathcal{X}$ or at $v_j=0$ in $\mathcal{Y}$. The origin pair has all six labels.

Drop row label $3$ by increasing $u_3$. Column $2$ is the first binding payoff constraint, at $u_3=1/4$, so label $5$ becomes duplicated. Drop $5$ in $\mathcal{Y}$ by increasing $v_2$; row $1$ binds first, at $v_2=1/4$, duplicating label $1$. Drop $1$ in $\mathcal{X}$ by increasing $u_1$ while keeping $u_2=0$ and the column-$2$ constraint binding. Since that constraint does not involve $u_1$, $u_3$ stays $1/4$. Column $1$ binds at $u_1=1/4$, duplicating label $4$.

Now drop $4$ in $\mathcal{Y}$ by increasing $v_1$. Keep $v_3=0$ and row $1$ binding, so $v_2=1/4$. Row $3$ reaches payoff $1$ at $v_1=1/6$, earlier than row $2$, which would bind at $v_1=1/4$. The missing label $3$ returns, terminating the path. The successive vertex-label pairs areThe final pair is completely labelled and nonzero. Normalize each vector by its own sum to obtainThe row payoffs against $y$ are $(12/5,2,12/5)$ and the column payoffs against $x$ are $(2,2,1/2)$. Both supported actions are best responses, so this is a Nash equilibrium, with payoffs $\boxed{(12/5,2)}$.

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.

Write $S=R+\delta$ and let $C_i=\delta +{\sum }_{j\ne i}{b}_j$. Player $i$'s payoff in the proportional contest with outside effort is $u_i(b)=v_{i}b/(b+C_i)-b$. When $C_i>0$, this is strictly concave andThe best response is zero when $v_i\le C_i$, and otherwise is $\sqrt{v_i{C}_i}-C_i$. Thus the nonnegative-effort Karush-Kuhn-Tucker conditions at a pure strategy Nash equilibrium giveFor an active player the first-order equation is $v_i(S-b_i)=S^2$. For an inactive player the derivative at zero is $v_i/S-1$. Strict concavity makes these conditions sufficient as well as necessary.

If $\delta =0$, an equilibrium cannot have just one active player: that player would win with certainty and could lower its positive effort. An all-zero profile also cannot be an equilibrium under the usual completion of proportional allocation at zero: at least one player can gain by investing an arbitrarily small amount. Consequently there are at least two active players, so every $C_i$ is positive. If $\delta >0$ this positivity is automatic. The allocation rule's otherwise undefined all-zero value at $\delta =0$ is therefore immaterial to the equilibrium calculation.

Let $k=\hat{n}>0$, $H_k={\sum }_{i=1}^{k}1/v_i$, and use the harmonic mean ${\bar{v}}_k=k/H_k$. Summing the active efforts givesThe positive root supplies the total-effort formula for a proportional contest with outside effort:At $\delta =0$ this reduces to $R=(k-1){\bar{v}}_k/k$. There is also a genuine zero-active case: if $\delta \ge v_1$, then $k=0$ and $R=0$; no harmonic mean of an empty family is needed.

For a fully explicit active-set rule, setThe equilibrium equation is $G(S)=0$. For $\delta >0$, $G$ is strictly decreasing from $+\infty$ to $-1$. For $\delta =0$ its limit at zero is $n-1>0$, and it is strictly decreasing wherever a zero could occur. Hence the positive root is unique. Moreover $S\ge \delta$, since its equation gives $1-\delta /S\ge 0$, and $b_i=S(1-S/v_i{)}_{+}$ supplies an equilibrium with total effort $S-\delta$.

Player $j$ is active exactly when $v_j>S$, equivalently $G(v_j)<0$. Ordering the valuations, including ties, givesTherefore the active-set threshold for a proportional contest with outside effort isThe qualifying indices form a prefix because $G$ is decreasing. Equality excludes the marginal player, as required by strict positivity of effort. Equivalently, the positive root $S_k$ of the displayed quadratic must satisfy $v_k>S_k\ge v_{k+1}$, with $v_{n+1}=0$. These formulas include one active player when $\delta >0$ and exclude that case when $\delta =0$.

Apply positive affine payoff transformations, if necessary, so both payoff matrices have strictly positive entries. Such transformations preserve best responses and Nash equilibria. The Lemke-Howson algorithm uses unnormalized nonnegative strategy vectors and slack variables satisfyingThus its two polytopes are $\{x\ge 0:Q^{T}x\le 1\}$ and $\{y\ge 0:Py\le 1\}$. A label $i\le m$ occurs when $x_i=0$ or $r_i=0$; a label $m+j$ occurs when $y_j=0$ or $s_j=0$. The complementary pivoting path drops one label from the artificial zero pair and resolves each duplicated label until all labels return.

Terminate at a completely labelled pair other than the artificial zero pair. This is equivalent to complementary slacknessA nonzero completely labelled pair has both vectors nonzero: if $x=0$, then $s=1$ forces $y=0$, and the converse is analogous. Normalize to mixed strategiesThe inequalities $Py\le 1$ imply that every row payoff against $q$ is at most $1/(1^{T}y)$, with equality on every row receiving positive probability in $p$. Thus $p$ is a best response to $q$. Likewise $q$ is a best response to $p$ using $Q^{T}x+s=1$. Hence $(p,q)$ is a Nash equilibrium. Nondegeneracy of a bimatrix game ensures the usual complementary pivoting path has a unique continuation after the label choice.

In the first tableau the basis is $(x_2,s_5,x_1)$, givingThe second basis is $(r_1,y_6,r_3)$, giving $y=(0,0,1/4)$ and $r=(3/4,0,1/4)$. This pair is not yet a Nash equilibrium: label $1$ is missing and label $4$ is duplicated.

Resolve the duplicate by bringing $y_4$ into the second tableau. Its column is $(3/4,1/4,9/4{)}^T$, so the simplex ratio test givesVariable $r_3$ leaves, givingNow label $3$ is duplicated. Bring $x_3$ into the first tableau; its column is $(0,3,1{)}^T$. The positive-entry ratios are $(2/3)/3=2/9$ and $(1/9)/1=1/9$. Thus $x_1$ leaves, givingAll labels are now present and $x_i{r}_i=y_j{s}_j=0$. Each unnormalized strategy has total mass $1/3$, so the Lemke-Howson algorithm produces

Row operations multiply each original tableau equation by an invertible matrix. The slack variable block therefore records that matrix and allows the original payoff matrix to be recovered without guessing.

From the first tableau, let $X$ be the coefficient block of $x$ and $S$ that of $s$. Since its original equations were $Q^{T}x+s=1$, we have $Q^T=S^{-1}X$. HeresoFor the second tableau, writing its $y$ and $r$ blocks as $Y,R$, the original equations $Py+r=1$ give $P=R^{-1}Y$. We obtainThus a representative pair of payoff matrices isBoth reconstructed right-hand sides are $1$, as a check on the tableau normalization. Independent transformations $P\mapsto aP+b11^T$, $Q\mapsto cQ+d11^T$, with $a,c>0$, preserve best responses and hence identify the same strategic solution up to positive affine payoff transformations.

Directly,The supports of $x^{\prime }$ and $y^{\prime }$ lie entirely among their respective best-response coordinates, confirming the Nash equilibrium found above. Since this representative is a symmetric bimatrix game, swapping the players' strategies preserves the Nash equilibrium conditions. Explicitly, $P{x}^{\prime }=(3,2,3{)}^T$ is maximized on the support of $y^{\prime }$, and $Q^T{y}^{\prime }=P{y}^{\prime }=(1,3,3{)}^T$ is maximized on the support of $x^{\prime }$. Therefore

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}$.

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.

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.

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.