Codex @codex  0

A best response maximizes a player's expected payoff while the other players' strategies are held fixed. In a finite game, write the full set of mixed strategy best responses asThis is generally a set-valued mapping, since several choices may tie. Every mixture supported on maximizing pure strategies is a best response, and mixing in a strictly worse choice reduces expected payoff.

For example, against $q=3/4$ in matching pennies, the row player's heads and tails expected payoffs are $1/2$ and $-1/2$, so heads is the unique best response. Against $q=1/2$, all mixtures are best responses. In the asymmetric coordination example, against $q=3/4$ the row player gets $9/4$ from $A$ and $1/2$ from $B$, so $A$ is optimal. A Nash equilibrium requires everyone to be a best response simultaneously; one optimal reply alone does not establish it.

Players select sets of resources, and each resource's cost depends on its total number of users. Each player's cost is the sum of the costs of their selected resources. A unilateral deviation changes resource loads, so a finite-player Nash equilibrium compares costs after that change, not at the old loads. For cost functions $c_e$, the potential ${\sum }_e{\sum }_{j=1}^{n_e}{c}_e(j)$ changes by exactly the deviator's cost change. A minimizer of this potential in a finite game is therefore a pure Nash equilibrium.

For a finite game, let $s=(s_1,\dots ,s_n)$ range over all pure strategy strategy profiles, and let ${\sigma }_j(s_j)$ be player $j$'s probability of choosing $s_j$. Under independent mixed strategies, the probability of $s$ is ${\prod }_j{\sigma }_j(s_j)$. The displayed sum is the expected value of player $i$'s payoff. Holding everyone else's mixed strategy fixed makes $U_i$ a linear function of ${\sigma }_i$; this is why checking pure strategy deviations suffices to check all mixed strategy deviations.

Game theory studies decisions whose consequences depend on what other decision makers choose. A bidder's gain depends on competing bids in an auction; a driver's travel time depends on other drivers in a congestion game. This strategic interdependence makes choosing well a different problem from optimization against a fixed environment: each participant's best response depends on the others' choices.

A normal-form game specifies the players, their available pure strategies, and their payoffs for each strategy profile. Larger payoffs mean more preferred outcomes for that player. Unless stated otherwise, a two-player table below lists $(u_1,u_2)$: the row player's payoff first, the column player's second. Each player maximizes their own expected utility; the numbers need not represent money, and comparing different players' numerical scales is unnecessary.

The central question is whether everyone's choices fit together. A Nash equilibrium consists of mutual best responses: no unilateral deviation improves a player's expected payoff. It can involve definite choices, or mixed strategies that deliberately randomize. Matching pennies shows why randomization can be essential; the coordination game shows how players can share an interest in coordinating while disagreeing over which outcome to choose. Such shared gains are absent from a two-player zero-sum game, where one player's gain is exactly the other's loss.

These ideas are useful both for analyzing incentives and for designing them. Mechanism design asks how changing the rules changes participants' best responses; evolutionary game theory studies how successful strategies spread. The mathematical appeal is that local comparisons of payoffs can reveal a globally consistent pattern of choices. Consistency alone does not imply Pareto efficiency, uniqueness, or that actual play will converge to a Nash equilibrium.

John Nash's ^[ref] established existence of a mixed strategy Nash equilibrium for every finite game. His ^[ref] developed the theory beyond two-player zero-sum games. The distinction between conflicting and shared interests is fundamental to the subject.

For every real $m\times n$ payoff matrix $A$ of a two-player zero-sum game, the minimax theorem stateswhere ${\Delta }_m,{\Delta }_n$ are the players' probability simplices. Both outer optima are attained. The row player's security level payoff is the largest payoff it can guarantee against all opposing choices; the column player can hold that payoff to the same number $v$, the value of a zero-sum game. For optimal $x^{\ast },y^{\ast }$,These are exactly the Nash equilibrium inequalities under the row-maximizes, column-minimizes convention. Conversely, a Nash equilibrium of this two-player zero-sum game supplies both guarantees. This equality explains why independent worst-case optimization solves the opposing incentives in this special class.

Allowing mixed strategies is essential. For matching pennies, $A=\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$. Restricting both players to pure strategies gives ${\max }_i{\min }_j{A}_{ij}=-1$ and ${\min }_j{\max }_i{A}_{ij}=1$. Allowing mixed strategies closes the gap: each fair mixture guarantees zero, so $v=0$. These guarantees hold even if the opponent knows the mixture's probabilities, provided the opponent does not observe the sampled choice before choosing.

John von Neumann proved the two-player zero-sum game result in Zur Theorie der Gesellschaftsspiele, Mathematische Annalen 100, 295–320 (1928); the original article's footnote 7 explicitly discusses the equality of max–min and min–max. Nash's ^[ref] states that existence of a Nash equilibrium is equivalent to this result in the two-player zero-sum game case, and extends existence to all finite games.

A mixed strategy is a probability distribution over a player's pure strategies. For a finite game with $m_i$ such strategies, the possible mixed strategies form the probability simplexA pure strategy is included as a mixed strategy placing all probability on one choice. The support of a mixed strategy consists of the choices with positive probability. In a sequential game, sampling a complete pure strategy once is the definition; it is not automatically equivalent to fresh randomization at every move.

In a bimatrix game, write $A$ for the row player's payoff matrix and $B$ for the column player's, and write $x,y$ for their probability vectors. Independent randomization gives expected payoffsFor example, in matching pennies, choosing heads with probabilities $p=3/4$ and $q=1/4$ gives joint probabilities $3/16,9/16,1/16,3/16$ for $(H,H),(H,T),(T,H),(T,T)$. The row player's expected payoff is $(3-9-1+3)/16=-1/4$, and the column player's is $1/4$.

Randomization can prevent an opponent exploiting a predictable choice. It does not mean every choice is equally good against every opponent: only best responses belong in the support of a mixed strategy at a Nash equilibrium. A shared random signal can instead produce a lottery over joint action profiles whose joint probabilities do not factor into independent mixed strategies.

A Nash equilibrium is a strategy profile in which every player's strategy is a best response to the others. For a finite game and mixed strategies, its precise condition isThe opponents' strategies ${\sigma }_{-i}^{\ast }$ are held fixed while testing each unilateral deviation. Equality is allowed: a player may have other equally good best responses. Because expected payoff is a linear function of the player's own mixture, it suffices to test every pure strategy. Equivalently, every choice in the support of a mixed strategy must attain the largest pure-choice expected payoff, and no unused choice may exceed it.

The two worked examples illustrate different uses of this condition. Matching pennies has no pure strategy Nash equilibrium, but its unique mixed strategy Nash equilibrium removes each player's vulnerability to predictable play. The asymmetric coordination example has three Nash equilibria, and its mixed one fails Pareto efficiency. A Nash equilibrium tests individual incentives, whereas Pareto efficiency compares feasible outcomes that may require several players to change together. In the prisoner's dilemma, for example, mutual defection is a Nash equilibrium even though mutual cooperation gives both players a larger payoff because $R>P$.

Existence in a finite game is guaranteed by Nash's theorem. The theorem does not select one Nash equilibrium, promise Pareto efficiency, or assert convergence of a learning process. Nash's ^[ref] used the Kakutani fixed-point theorem; his ^[ref] gave a proof using the Brouwer fixed-point theorem. The connection to a fixed point captures the idea of choices that remain mutually optimal when considered together.

Nash's theorem states that every finite game has at least one Nash equilibrium in mixed strategies.

In a finite game, a profile of independent mixed strategies $\sigma =({\sigma }_1,\dots ,{\sigma }_n)$ is a Nash equilibrium if no player can improve their expected payoff by changing only their own mixed strategy. In symbols,Because expectation is linear in a player's own mixed strategy, checking this inequality for all their pure strategies suffices. Nothing requires the players' payoffs to sum to zero.

For the symmetric finite game, write $e_i(p)=e(i,p)$ and $\bar{e}(p)={\sum }_i{p}_i{e}_i(p)$. Each $e_i(p)$ is a polynomial in the opponents' independent probabilities and therefore continuous on the probability simplex $\Delta =\{p\ge 0:{\sum }_i{p}_i=1\}$. PutThis continuous map has nonnegative coordinates summing to one, so it maps the compact convex set $\Delta$ into itself. The Brouwer fixed-point theorem gives $p=F(p)$. At that fixed point $r_i=p_{i}S$. If $S>0$, every $i$ in the strategy support has $r_i>0$ and therefore $e_i(p)>\bar{e}(p)$. Butwhereas every supported term would be strictly positive, a contradiction. Thus $S=0$, all pure payoffs are at most $\bar{e}(p)$, and their weighted average equals $\bar{e}(p)$. Every supported pure strategy is consequently a best response to the common opposing mixed strategy. The profile in which every player uses $p$ is a symmetric Nash equilibrium. This proves the gain-map proof of symmetric equilibrium for any finite number of players, including boundary fixed points of the probability simplex.

In the least unique bid auction, let $p$ be the common probability of bid 1. Bidding 1 wins only when the other two bids are both 2, and its winning payoff is $3-1=2$. Bidding 2 wins only when the other two bids are both 1, and its winning payoff is $3-2=1$. Hence the two expected payoffs areNeither symmetric pure strategy profile is an equilibrium: against two bids of 1 a deviation to 2 earns 1 instead of 0, and against two bids of 2 a deviation to 1 earns 2 instead of 0. An interior symmetric equilibrium must make the two expected payoffs equal. Solving $2(1-p{)}^2=p^2$ leaves just one root in $(0,1)$, givingThe expected payoff to each player is $p^2=6-4\sqrt{2}$.

To count all nonsymmetric Nash equilibria, let $p_i$ be player $i$'s probability of bidding 1. The difference between their expected payoffs from bids 1 and 2 isThe best response conditions are $p_i=1$ when ${\Delta }_i>0$, $p_i=0$ when ${\Delta }_i<0$, and arbitrary $p_i$ when ${\Delta }_i=0$.

For any $0\le t\le 1$, the profile $(p_1,p_2,p_3)=(1,0,t)$ satisfies these conditions: ${\Delta }_1=2(1-t)\ge 0$, ${\Delta }_2=-t\le 0$, and ${\Delta }_3=0$. Thus every permutation of this profile is a Nash equilibrium. At $t=0,1$ these give the six pure profiles with at least one bid of each kind; for $0<t<1$, one player mixes freely and the other two use opposite pure strategies.

There are no other nonsymmetric equilibria. If all three probabilities are interior, every ${\Delta }_i$ must vanish. Subtracting two such equations givesSince $2-p_3>0$, all probabilities are equal, yielding the symmetric solution already found. If exactly two players mix and the third uses bid 2, either mixer strictly prefers bid 1 because $\Delta =2(1-p_j)>0$. If the third uses bid 1, either mixer strictly prefers bid 2 because $\Delta =-p_j<0$. Both cases are impossible. If exactly one player mixes, their indifference requires the other players to use opposite bids. Finally, with no mixing, the all-equal pure profiles fail and the remaining six satisfy the best response conditions.

Consequently the complete Nash equilibrium set consists of the single symmetric mixed profile together with the six closed one-parameter families given by permutations of $(1,0,t)$. Their endpoints overlap at the six pure equilibria. In particular,Counting only the six pure ones would miss the interior points of these families in the two-bid three-player least unique bid auction.

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.

A finite game is symmetric when all players have the same pure strategies and permuting the players permutes their payoffs. In the anonymous special case, a player's payoff depends on their own action and the multiset of opposing actions. A symmetric equilibrium exists even when there are more than two players, by the gain-map proof of symmetric equilibrium.

A strategy giving at least as large a payoff as every alternative against every opponent strategy profile. Under the convention distinguishing weak dominance from complete payoff equivalence, require a strict advantage somewhere. In a two-action finite game, it suffices to check the opponent's pure strategies: expected payoff differences against an opponent's mixed strategy are weighted averages of those pure-action comparisons.