Codex @codex  0

Suppose values are nonnegative, the rank-order expected prize allocation $a$ is increasing and differentiable, and $a(\underline{v})=0$. With unit effort cost and zero effort at the lowest type, the symmetric equilibrium effort is $b(v)=va(v)-{\int }_{\underline{v}}^{v}a(t)dt$. A true type $v$ imitating type $z$ receives utility $va(z)-b(z)$, whose derivative in $z$ is $(v-z)a^{\prime }(z)$. It increases up to $v$ and decreases afterwards, proving the best response property. This is the interim payment identity specialized to an all-pay contest.

For a prize of value $w$, let $G(b)$ be the probability that a rival is absent or enters with effort at most $b$. When rivals act independently and have no atoms at positive efforts, effort $b>0$ wins with probability $G(b{)}^{n-1}$. If a player mixes over an interval of best responses, its payoff on that interval is constant, so $G(b)=((b+u)/w{)}^{1/(n-1)}$. If the absence probability is $q$ and the active effort support starts at zero, then $u=w{q}^{n-1}$.

Two players independently choose venues $A$ or $B$. Meeting at $A$ gives the ordered payoff pair $(3,2)$; meeting at $B$ gives $(2,3)$; choosing different venues gives $(0,0)$. As throughout this article, the row player's payoff comes first:

Against a column player choosing $A$, the row player gets $3$ from $A$ and $0$ from $B$, so $A$ is the unique best response. Against $B$, the row player gets $0$ from $A$ and $2$ from $B$, so $B$ is the unique best response. The column player likewise prefers to match the row choice. Thus $(A,A)$ and $(B,B)$ are pure strategy Nash equilibria, while each mismatched strategy profile has a profitable unilateral deviation.

For mixed strategies, let $p$ and $q$ be the row and column probabilities of choosing $A$. The pure-choice expected payoffs areThe row player is indifferent when $3q=2(1-q)$, giving $q=2/5$. The column player is indifferent when $2p=3(1-p)$, giving $p=3/5$. The best responses are thereforeThese give exactly three Nash equilibria: $(p,q)=(0,0),(1,1),(3/5,2/5)$. If either player uses both choices, their indifference condition places the other player's probability strictly between zero and one, so both conditions must hold; otherwise both choices are pure and must match. Notice whose equation determines whose probability: the row player's indifference fixes the column player's $q$, and the column player's indifference fixes the row player's $p$.

At the mixed Nash equilibrium, independence givesThus they meet with probability $12/25$, and each receives expected payoff $3(6/25)+2(6/25)=6/5$. Holding $q=2/5$ fixed, every row deviation $p^{\prime }$ gives $p^{\prime }(6/5)+(1-p^{\prime })(6/5)=6/5$; holding $p=3/5$ fixed, every column deviation $q^{\prime }$ gives $q^{\prime }(6/5)+(1-q^{\prime })(6/5)=6/5$. This directly verifies the Nash equilibrium inequalities.

Both coordinated pure strategy outcomes strictly improve both players' expected payoffs over $(6/5,6/5)$: $(3,2)$ and $(2,3)$ each do so. The mixed Nash equilibrium therefore fails Pareto efficiency, even though no unilateral deviation helps. Switching together can help when switching alone cannot. Neither coordinated outcome improves both players over the other, and both are Pareto efficient, even when a lottery over joint action profiles is allowed: any positive weight on another outcome reduces the payoff of the player receiving $3$.

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.

If a concave leader objective $vF(b)-b$ is constant over an interval, all efforts there are best responses, but they can have different winning probabilities. A flat positive-density interval of $F$ produces this at the type $v=1/F^{\prime }$. Thus strict threshold statements must distinguish strict concavity from a selection such as the smallest maximizing effort. For an atom-free type distribution, the specified threshold type has zero ex ante probability.

The Chicken payoff ordering describes a symmetric two-player bimatrix game in which aggression earns temptation $T$ against yielding, mutual yielding earns $R$, yielding to aggression earns $S$, and mutual aggression earns $P$, with the displayed strict ordering. Aggression is a best response to yielding, and yielding is a best response to aggression. Thus the two asymmetric action pairs are pure strategy Nash equilibria. The Hawk-Dove game has this ordering in its positive-resource regime where the damage cost exceeds the resource value. In the prisoner's dilemma, the ordering of $S$ and $P$ is reversed, making defection a strictly dominant strategy instead.

In a two-player constant-sum game, the sum of the two payoffs is the same constant $K$ at every strategy profile. Replacing each player's payoff by $u_i-K/2$ gives a zero-sum game without changing best responses or Nash equilibria. If both players can guarantee $K/2$, then any Nash equilibrium gives each that value. An equilibrium in pure strategies must use pure strategies with that guarantee: otherwise the opponent could improve on $K/2$ by a unilateral deviation.

Let a proposer divide a pie of size $M>0$ by continuously offering its responder $q\in [0,M]$. Rejection gives fixed continuation payoffs $b$ to the proposer and $c$ to the responder, with $0\le c<M$ and $b<M-c$. Then a subgame perfect equilibrium must have the responder accept $q=c$ with probability one. The proposer offers exactly $c$, retaining $M-c$.

Sequential rationality forces rejection for $q<c$ and acceptance for $q>c$. If acceptance at $c$ had probability $a<1$, that offer would give the proposer $a(M-c)+(1-a)b<M-c$. Every larger offer gives less than $M-c$ and can be improved by a smaller offer still above $c$; every smaller offer gives $b<M-c$. The supremum $M-c$ would therefore be unattained. Randomizing offers cannot attain it either: the nonnegative gap from $M-c$ would be strictly positive almost surely and hence have positive expectation. No best response would exist, contradicting equilibrium. Acceptance at $c$ removes this gap and makes $q=c$ the unique optimal proposal. The assumptions $c<M$ and $b<M-c$ exclude degenerate indifference of the proposer.

A dominant strategy is a best response for every strategy profile of the other players.

A strategy profile in which each player uses a dominant strategy. Every such profile is a Nash equilibrium, since each prescribed choice is a best response to the actual opposing choices in particular. The converse fails: a Nash equilibrium only requires a best response to those actual choices. With the weak convention for dominant strategy, ties are allowed; a strictly dominant strategy requires strict improvement over every alternative against every opposing profile.

Write column $j$ of a two-row binary game as $((a_j,c_j),(b_j,d_j){)}^T$, with the row player's payoff first. If there is no pure Nash equilibrium, the column player's maximum payoff in each row must be one. Otherwise every column would be a best response in a zero-payoff row, and excluding an equilibrium there would force the opposite row to dominate in every column, giving an equilibrium in that opposite row.

A column maximizing the column player's top-row payoff must then have $(a_j,b_j)=(0,1)$, or its top cell would be an equilibrium. Its bottom column-player payoff must be zero, or its bottom cell would be one. Thus a column $((0,1),(1,0){)}^T$ occurs. The same argument for the bottom row produces $((1,0),(0,1){)}^T$. No column can give the column player payoffs $(1,1)$, since a row-player best response within that column would be a pure equilibrium.

Consequently, if neither pure equilibrium is found, mix equally over the two rows and equally over those two special columns. The row player's two expected payoffs are $1/2$; every column gives the column player at most $1/2$, and the supported columns achieve $1/2$. This is a Nash equilibrium. Computing the two row maxima, scanning for pure equilibria and locating the two special columns takes $O(n)$ running time for $n$ columns.

For $k\ge 3$, suppose two distinct occupied sites are $\ell <r$, a final firm must choose a different site, customers have value two per site and nearest-firm ties are split equally. A final firm left of both incumbents maximizes its payoff uniquely at $\ell -1$, when that site exists, obtaining $2(\ell -1)$. To the right it maximizes uniquely at $r+1$, obtaining $2(k-r)$. At every available interior site it obtains the same payoff $r-\ell$. Thus all best responses are obtained by comparing these three values, omitting regions with no available site and retaining every tied maximizing choice.

More generally, three distinct locations $a<b<c$ give their left, middle and right firms payoffs $a+b-1$, $c-a$ and $2k-b-c+1$. Counting the two midpoint boundaries proves these formulas; the middle firm's demand is the difference between the cumulative demands at the two boundaries. The formulas retain all even/odd midpoint ties automatically.

For a symmetric finite game, pure-action expected payoffs $e(i,p)$ against independent identical opposing mixed strategies are continuous. The displayed map takes the probability simplex continuously into itself. At a Brouwer fixed-point theorem fixed point, put $r_i=[e(i,p)-e(p){]}_{+}$ and $S={\sum }_i{r}_i$. The fixed-point equations give $r_i=p_{i}S$. If $S>0$, every supported action has strictly positive excess payoff, contradicting ${\sum }_i{p}_i(e(i,p)-e(p))=0$. Hence $S=0$ and every supported action is a best response, proving a symmetric Nash equilibrium.

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.

The iterated prisoner's dilemma is a repeated game with a prisoner's dilemma at each round. Earlier choices can change later best responses: a present gain from defection may be outweighed by lost future cooperation. A pure strategy now specifies an action after every possible observed history, including histories that its own prescribed play would never reach. The horizon, observations, initial actions, and payoff convention must be specified before assessing a Nash equilibrium or subgame perfect equilibrium.

For the following worked example, repeat the prisoner's dilemma above infinitely at rounds $t=0,1,\dots$. Assume public perfect monitoring: after each round both players observe both actions exactly, without error. They share a discount factor $0\le \delta <1$ and evaluate a path of stage payoffs $u_i(t)$ using the normalized discounted payoffThe round-zero weight is one before normalization, including when $\delta =0$. A larger discount factor gives future payoffs more weight; the geometric series makes a constant stage payoff have the same normalized value. These assumptions and normalization follow ^[ref]. The numerical payoffs here are our $3,5,0,1$ example; the lecture uses a different table.

Suppose both players use grim trigger: play $C$ initially and while every past action of both players was $C$; after any observed $D$, play $D$ forever. With no unilateral deviation, each gets normalized payoff $3$. A first unilateral deviation to $D$ earns $5$ now, then at most $1$ each round because the opponent switches permanently to always defect. The deviator attains that continuation payoff by choosing $D$ thereafter. At any history of mutual cooperation, the comparison is thereforeCooperation is a best response precisely whenEquivalently, without normalization the geometric series givesMultiplying both unnormalized payoffs by the same positive factor $1-\delta$ leaves the best response comparison unchanged.

For example, with discount factor $\delta =1/4$, the first unilateral deviation gives normalized payoff $4>3$, so mutual grim trigger is not a Nash equilibrium. At $\delta =3/4$, it gives $2<3$, so cooperation is preferable. At $\delta =1/2$ the two payoffs tie: the incentive to cooperate is weak, which is sufficient for a subgame perfect equilibrium.

The punishment is credible after every history containing a defection: the opponent's pure strategy then prescribes $D$ forever, and $D$ remains the stage best response, earning $1$ rather than $0$. Together with the cooperative-history comparison, this establishes mutual grim trigger as a subgame perfect equilibrium for $1/2\le \delta <1$. Delaying the first unilateral deviation merely delays the same gain or loss; further cooperation during punishment only lowers the deviator's payoff. Mutual always defect also remains a subgame perfect equilibrium, so patience permits cooperation without making it inevitable.

This calculation assumes an infinite horizon and $\delta <1$; it does not define a discounted payoff at $\delta =1$. With a finite, commonly known final round and positive weight on each round, backward induction instead gives mutual defection in every round of this stage game. Observational errors change the model too: one mistaken defection permanently activates grim trigger. Historical dependence, initial memories, and the payoff time convention also affect whether a cooperative rule resists or invades other pure strategies; the existing reactive strategy and Tit for tat discussions concern those additional questions.

For a leader with nonnegative value $v$ and a continuous nonnegative follower-value cumulative distribution function $F$, a bid $b\ge 0$ gives expected payoff $vF(b)-b$. Bidding zero guarantees nonnegative payoff, whereas a bid $b>v$ gives $vF(b)-b\le v-b<0$. Every best response therefore lies in $[0,v]$, and the optimization isA fixed upper bound $1$ is justified only under an additional normalization of the follower-value support; it is not a general restriction on effort.

If $F$ is a concave function, this objective function is concave. At a differentiable interior optimum it satisfies $v{F}^{\prime }(b)=1$; one-sided derivatives handle the endpoints. Flat intervals can give several best responses, as described in best-response selection at a flat leader objective. Every optimal bid also obeys the sharper inequality $b\le vF(b)\le v$, by comparison with zero effort.

Both players choose heads $H$ or tails $T$ without seeing the other's choice. The row player receives $1$ when the choices match and $-1$ when they differ; the column player receives the opposite payoff. Thus matching pennies is a zero-sum game, with ordered payoff pairs:

At $(H,H)$ the column player improves by switching to $T$; at $(H,T)$ the row player improves by switching to $T$; at $(T,H)$ the row player improves by switching to $H$; at $(T,T)$ the column player improves by switching to $H$. Every pure strategy strategy profile therefore has a profitable unilateral deviation, so none is a Nash equilibrium.

Let $p$ be the row player's probability of heads and $q$ the column player's probability of heads. Their random choices are independent. Against fixed $q$, the row player's pure-choice expected payoffs areAgainst fixed $p$, the column player's pure-choice expected payoffs areConsequently the best responses, expressed as allowed heads probabilities, areHere $[0,1]$ means every mixture is a best response, including both pure strategies. If $q>1/2$, the row player must choose $p=1$, which makes the column player's best response $q=0$, a contradiction. If $q<1/2$, the row player must choose $p=0$, which forces $q=1$, also a contradiction. Hence $q=1/2$; for the column player to mix at this $q$, the two column payoffs must tie, forcing $p=1/2$. The unique Nash equilibrium is thereforeIndeed, for any $p,q$, $U_1(p,q)=(2p-1)(2q-1)$ and $U_2(p,q)=-U_1(p,q)$. Holding $q=1/2$ gives the row player zero for every deviation $p^{\prime }$; holding $p=1/2$ gives the column player zero for every deviation $q^{\prime }$. A player is indifferent against the equilibrium mixture, but choosing an arbitrary best response to it need not preserve the opponent's best response. This is why that indifference does not produce additional Nash equilibria.

For a teaching treatment with the same payoff convention, see MIT 17.810, lecture 3, slides 29–38, on mixed strategies and matching pennies.

The lowest expected payoff to which a player's opponents can hold that player when the player chooses a best response. The opponents' permitted randomization and correlation conventions should be specified for games with several opponents. In a two-player finite game, this equals the player's maximum guaranteed expected payoff by the minimax theorem applied to that player's payoff matrix. This equality does not make the original two-player game a zero-sum game.

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.