Codex @codex  0

A Nash equilibrium is a profile in which each player's strategy is a best response to all the others: no unilateral change increases that player's payoff. In this routing game the payoff can be taken as minus delay. A pure strategy is a single route; a mixed strategy is a probability distribution over routes, with different players randomizing independently. A non-zero-sum game does not require the players' payoffs to add to a fixed total. Nash's theorem guarantees a mixed Nash equilibrium for every finite game with finitely many pure strategies. Pure equilibria need not exist in general; the congestion game here does have them, since a unilateral delay change equals the change in its finite congestion potential.

Put $x=n_1+n_3$ and $y=n_2+n_3$. The three current delays, in the order $ABD,ACD,ABCD$, areFor a player using the first route, switching to the second makes the new second-route load $y+1$, while switching to the third retains that player's use of $AB$ and adds one user to $CD$. The two comparisons are thereforeThey reduce to $x\le y+1$ and $y\ge 74$. Reversing the two outer routes gives $y\le x+1$ and $x\ge 74$ for each second-route user. A third-route user who switches to the first retains their own use of $AB$, and one who switches to the second retains their own use of $CD$. The corresponding comparisons give $y\le 75$ and $x\le 75$. Thus the necessary and sufficient conditions, together with nonnegative integer counts summing to $n$, areThey are sufficient because each used route has been compared with both alternatives, and necessary because each comparison is an available unilateral deviation. The unit changes in loads matter in a finite-player congestion game.

For $n=100$, the counts $(25,25,50)$ give $x=y=75$ and every player's delay is $15/4$. They satisfy all the conditions. To find every pure Nash equilibrium, first note that $n_3=0$ is impossible: if either outer route is empty, its other route users fail the lower-load condition; if both are used, $x,y\ge 74$ contradict $x+y=100$. Thus $n_3>0$, so $x,y\le 75$. Since $x=100-n_2$ and $y=100-n_1$, this forces $n_1,n_2\ge 25$. Both are positive, so the remaining conditions force $x,y\ge 74$ and hence $n_1,n_2\le 26$. Their differences are at most one, so every such pair works. The complete equilibrium count vectors areEach vector also represents many pure profiles obtained by choosing which labeled players use each route. Therefore the displayed equilibrium is not unique, even as an aggregate count vector.

A coordinated allocation with fifty players on each outer route and nobody on $ABCD$ gives every player delay $7/2$, strictly better than $15/4$. It is not a Nash equilibrium: a first-route user can switch to $ABCD$ and obtain delayThis exhibits the conflict between coordinated welfare and unilateral incentives. In fact $7/2$ is below every user's delay in all four pure equilibrium count vectors above.

For a symmetric Nash equilibrium when $n=100$, let each player independently choose the two outer routes with probability $q$ each and the middle route with probability $1-2q$. Conditional on choosing the first route, that player certainly uses $AB$, while each of the other $99$ players uses it with probability $1-q$. The expected delays of the first and third routes are consequentlyThe second has the same expected delay as the first by symmetry. Equalizing these givesAll three probabilities are positive and all three pure routes have expected delay $15/4$, so every route is a best response to the other players' common mixture. This proves a symmetric mixed Nash equilibrium. Using probabilities $1/4,1/4,1/2$ would omit the player's own-load correction and would not make all three expected delays equal.

For completeness, the same calculation works for every positive number of players. If $n\le 75$, every player choosing $ABCD$ is a symmetric pure Nash equilibrium. For $75<n<149$, a symmetric mixed equilibrium hasFor $n\ge 149$, each player choosing either outer route with probability one half is a symmetric mixed equilibrium. In that last regime the unused middle route has expected cost at least that of the outer routes, since their difference is $-3/4+(n+1)/200\ge 0$. These formulas agree at the regime boundaries.

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

Let $P$ be the row payoff matrix and $Q=P^T$. For $x$ in the probability simplex $\Delta$, write $u(x)=x^{T}Px$ and define the symmetric Nash gain mapThe map is a continuous function, has nonnegative coordinates, and sums to one. The Brouwer fixed-point theorem states that every continuous self-map of a nonempty finite-dimensional compact convex set has a fixed point. Apply it to $T:\Delta \to \Delta$, and let $x=T(x)$.

Set $G={\sum }_i{g}_i(x)$. The fixed-point equation gives $g_i(x)=G{x}_i$. If $G>0$, every positive $x_i$ has strictly positive gain, so $(Px{)}_i-u(x)=g_i(x)=G{x}_i$. Buta contradiction. Thus $G=0$ and every pure payoff $(Px{)}_i$ is at most $u(x)$. Since their $x$-weighted average equals $u(x)$, every supported action attains that maximum. Consequently $x$ is a best response to itself.

The column player's payoff vector against $x$ is $Q^{T}x=Px$, so exactly the same inequalities establish its best response. ThereforeThis supplies the whole fixed-point construction and fixed-point-to-equilibrium argument, rather than assuming Nash's theorem as a black box.

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.

The game is degenerate in the nondegeneracy of a bimatrix game sense. Against the first player's pure strategy $4$, the second player's choices $1$ and $2$ are both best responses, with payoff four. A mixed strategy of support size one therefore has two pure best responses. The usual Lemke-Howson algorithm path needs additional tie handling or perturbation in such a game; the zero-sum game structure gives a simpler direct linear program.

Add five to every entry of the first player's matrix, obtainingThis does not change either player's best responses or Nash equilibria; it raises the game value by five. Since all entries are positive, its value $v_B$ is positive. If $p$ is a row mixed strategy guaranteeing $v_B$, put $x=p/v_B$. Then $B^{T}x\ge 1$ and $1^{T}x=1/v_B$.

Conversely any feasible $x$ has $s=1^{T}x>0$, and $p=x/s$ guarantees payoff $1/s$ in the shifted game. Maximizing that guaranteed payoff is therefore equivalent to minimizing $s$ under $B^{T}x\ge 1$, $x\ge 0$. These are precisely the displayed constraints. The dual program maximizes $1^{T}y$ subject to $By\le 1$, $y\ge 0$; normalizing an optimal $y$ gives the column strategy. This is positive-payoff linear programming for a matrix game.

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

Let $w_m=w(m/n)$, so a type $v$ values a prize at $v{w}_m$. In a symmetric increasing Bayes-Nash equilibrium of this rank-order contest, a player reporting type $t$ wins when at most $m-1$ opponents have larger types. Its winning probability isHere the count of opponents above $t$ has a binomial distribution. Differentiation, or the associated order statistic density, givesDefine the effort by the all-pay effort identityThis also verifies equilibrium globally. The derivative of a type $v$'s payoff from reporting $t$ is $w_m(v-t)q_m^{\prime }(t)$, positive before $v$ and negative after $v$. Thus truthful reporting is a best response. Bidding above the maximal equilibrium effort gains no additional winning probability. Type zero chooses zero effort.

By exchanging the two integrations, the expected value of total effort isThe last integral is the moment $\mathbb{E}[X(1-X)]$ for a Beta distribution with parameters $n-m$ and $m$, namely $m(n-m)/(n(n+1))$. This is the uniform-value multi-prize all-pay effort formula.

Put $x=m/n$ and $h(x)=w(x)x(1-x)$. The positive constant $n^2/(n+1)$ multiplying $h(x)$ does not affect the maximizing $m$. Sincethe assumed inequality makes $h$ nonincreasing on the feasible interval. Hence one prize maximizes expected total effort.

For the power family, the PDF gives $w(x)=x^{-\alpha }$. ThenIf $\alpha \ge 1$, this derivative is strictly negative for $0<x<1$: the bracket is affine and its values at the endpoints are $1-\alpha \le 0$ and $-1$. Thus $m=1$ is optimal.

If $0<\alpha <1$, the unique continuous maximizer isThe objective strictly increases before $x_{\ast }$ and decreases after it. Therefore its discrete maximizer lies amongCompare the surviving candidates using $m^{1-\alpha }(n-m)$, since $R_m=n^{\alpha }{m}^{1-\alpha }(n-m)/(n+1)$. If $n{x}_{\ast }$ is an integer, that integer is the unique maximizer; if its floor is zero, the only feasible candidate is $1$. This proves the discrete prize-count optimization for a power-valued contest including the endpoint cases.

The sufficient condition need only hold on $[1/n,(n-1)/n]$. The power family is undefined at zero, so the printed endpoint $x=0$ cannot apply to it. More generally, a positive finite value $w(0)$ would make the displayed inequality fail at zero. The design argument uses only positive feasible prize fractions and needs no value there.

Use the usual continuous-distribution convention $F(0)=0$, $F(1)=1$, and write $f=F^{\prime }$. After observing $b$, the follower can win by matching it, because ties favor the follower. Its best response is to match when $v_2>b$ and choose zero when $v_2<b$; the indifferent equality has probability zero. Thus the leader wins with probability $F(b)$ and a leader of type $v$ maximizesBids above $1$ are dominated by bidding $1$. This is the leader optimization in a sequential private-value all-pay contest. Since $F$ is a concave function, $h_v$ is concave. An interior optimum satisfies $vf(b)=1$, with the usual endpoint conditions when that equation has no interior solution.

For precision, select the smallest maximizer when the leader is indifferent. This defines a Stackelberg equilibrium and supplies the printed strict conditional comparison at the threshold type. Let $q=F^{-1}(1/2)$. The density $f(q)$ is positive: if it vanished there, its nonnegative nonincreasing continuation would force $F$ to remain $1/2$ up to $1$, which is impossible. At the median,If this is positive, every maximizer is strictly greater than $q$, so the leader wins with probability greater than $1/2$. If it is negative, every maximizer is strictly smaller than $q$. If it is zero, $q$ is a maximizer, and the smallest maximizer is at most $q$. Therefore the median-density threshold for the leader in an all-pay contest isStrict concavity of $F$ would make the optimum unique, removing the selection convention. With mere concavity, the printed assertion needs that convention at equality. For example, $F(b)=b$ and $v=1$ make all bids optimal, and choosing $b=3/4$ makes the leader more likely to win even though the strict threshold is not exceeded.

The same issue can occur at an interior type, rather than just an endpoint. A continuously differentiable concave distribution isIts density decreases from $2$ to $5/4$, is constant on $[1/5,2/5]$, and then decreases to $1/24$; integration gives $F(1)=1$. Its median is $31/100$. At $v=4/5=1/f(q)$, every bid in $[1/5,2/5]$ maximizes $h_v$, and choosing $2/5$ gives winning probability $49/80>1/2$. This confirms the genuine best-response selection at a flat leader objective issue. The smallest-maximizer convention avoids it; the threshold type has zero ex ante probability.

The unconditional comparison is valid for every optimal selection. Zero effort guarantees the leader payoff zero, so an optimal bid satisfiesConsequently $F(b(v))\le F(v)$. If $V$ has the continuous distribution $F$, the probability integral transform makes $F(V)$ uniform on $[0,1]$. Taking expectations proves the ex ante follower advantage in a sequential all-pay contest:For strictly increasing atom-free $F$, optimal bids in fact satisfy $b(v)<v$ for almost every $v\in (0,1)$, so the first inequality is strict. Conditional advantage for unusually high leader types is therefore compatible with an unconditional follower advantage.

We derive the probabilities for a sequential elimination all-pay contest from a discounted subgame perfect equilibrium, using backward induction, and only then take $\delta \uparrow 1$. This preserves the selection supplied by discounting.

First consider a two-player all-pay auction with effective prizes $A_1\ge A_2>0$, so the incremental payoff is $A_i$ times winning probability minus effort. For $0\le b\le A_2$, the independent mixed strategies have effort cumulative distribution functionsThe second player has an atom $1-A_2/A_1$ at zero. For positive bids on this support, the first player's payoff is $A_1{G}_2(b)-b=A_1-A_2$ and the second's is $A_2{G}_1(b)-b=0$. Bids above $A_2$ cannot improve either payoff. The first has no zero atom, so the second's zero bid also earns zero. If the first deviates to zero, it can win only when the second bids zero; even with every such tie resolved in its favor, its payoff is at most $A_1(1-A_2/A_1)=A_1-A_2$. The two-player complete-information all-pay equilibrium therefore has winning probabilitiesThese follow by integrating $G_2$ against the uniform $G_1$. A third player with effective prize at most $A_2$ cannot profit by entering: for $0<b\le A_2$, its winning probability is $G_1(b)G_2(b)\le b/A_2$, giving payoff at most zero; above $A_2$ its effort exceeds its prize.

For the dynamic induction, relabel any remaining subgame's valuations as $v_1>\cdots >v_k$, with $r<k$ prizes left. Define the backward-induction threshold in an elimination all-pay contestFor $r=1$ the sum is empty and $C_1=v_2$. The discounted continuation value in an elimination contest is obtained from the following net utilities:The base case is the one-prize all-pay auction: only the two highest valuations need positive effort, with prizes $v_1,v_2$ and payoffs $v_1-v_2,0$. Every lower player has a nonprofitable deviation by the preceding calculation.

For $r\ge 2$, if either of the top two wins, the other becomes the highest player in a subgame with $r-1$ prizes. The continuation threshold in either such subgame is the same numberThe remaining top player's continuation payoff is $v_i-D$. Its effective prize in a sequential contest, net of the discounted payoff from losing, is thereforeThus $A_1>A_2$ for $\delta <1$, and the two-player distributions above apply. Adding the losing-state baselines giveswhich agree with the proposed formulas.

For a player of rank $i\ge 3$, the inductive continuation utility after either top player wins is identical: its new rank is $i-1$, and the utility expression depends only on its own value and the lower-valued tail. Thus its current zero-effort payoff is that common continuation value multiplied by $\delta$, exactly the stated $J_i$. Its effective prize for deviating to win now is $A_i=v_i-J_i$. For $3\le i\le r$, direct subtraction givesFor $i\ge r+1$, $A_i=v_i\le v_{r+1}\le C_r$, since the coefficients in $C_r$ are nonnegative and sum to one. Such a player cannot gain by entering against the two active players. There is one additional zero-bid deviation to check for the highest player. If both active bids become zero, the tie could award a prize to any remaining player. Losing to any player below rank $2$ gives no greater continuation utility than losing to rank $2$: deleting rank $2$ makes the ordered remaining rival list componentwise smallest, and its continuation threshold is a nonnegative weighted sum of that list. Thus even resolving every all-zero tie in the highest player's favor gives payoff at most its usual losing baseline plus $A_1(1-A_2/A_1)=A_1-A_2$. No tie rule can improve this deviation. This verifies all best responses and the continuation-utility formulas. Applying the construction to every remaining-player set proves a subgame perfect equilibrium of the discounted contest, not merely an on-path prescription.

Now take the vanishing-discount limit of an elimination all-pay contest. At every nonfinal subgame,Thus the two highest remaining players win with equal probabilities in a nonfinal stage. In the final stage the effective prizes are their actual valuations, so its lower-valued participant beats the higher one with probability equal to half their valuation ratio.

Return to the original ranks. Only the original top $m+1$ can ever win; at most $m-1$ higher players can have left before the final stage, so players of rank $m+2$ or worse never enter its top pair. Player $1$ must lose $m-1$ fair nonfinal contests to remain unawarded until the final stage, where its opponent has value $v_{m+1}$. HenceA player $2\le i\le m$ first enters the top pair at stage $i-1$, after $i-2$ higher-ranked winners have left. To remain unawarded, it must lose the $m-i+1$ nonfinal contests from then on, followed by the final contest against rank $m+1$. ThereforeThere are exactly $m$ distinct winners, so the expected value of their indicator sum is $m$. Combining these calculations givesThis proves the ranked winning probabilities in an undiscounted elimination contest. When $m=1$, it reduces to the ordinary two-player all-pay winning probabilities; when $m>1$, the repeated fair stages explain each power of $1/2$.

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.

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

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

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