Codex @codex  0

The first graph solves the row player's max–min optimization: choose a mixed strategy guaranteeing the greatest possible worst-case expected payoff. The second solves the column player's min–max optimization: choose a mixed strategy placing the smallest upper bound on the row player's expected payoff. Their optimal heights agree, illustrating the minimax theorem.

There is also a direct Nash equilibrium certificate, so the conclusion does not depend on reading coordinates from a plot. At $p^{\ast }=2/7$, both opposing pure columns give row expected payoff $-1/7$; at $q^{\ast }=4/7$, both pure rows give row expected payoff $-1/7$. By linearity, every unilateral deviation, including an arbitrary mixed strategy, leaves the deviator's expected payoff unchanged against the fixed opposing equilibrium mixture. Neither player can improve it. This is a mixed-strategy optimality certificate for a matrix game.

The equilibrium outcome is a probability distribution over cells, rather than one deterministic cell. Independent randomization givesThe resulting row expected payoff is $(16-18-20+15)/49=-1/7$. Finally, each envelope has a unique optimum, so any Nash equilibrium must use the displayed optimal mixed strategies. In particular there is no pure strategy Nash equilibrium.

Use the standard repeated game convention that the first round's joint action is observed before round two. The following original game tree represents simultaneous moves by making row move first in each round while hiding that current move from column. Terminal labels are total payoffs over both rounds, ordered row then column.

Formally, round one starts at a row decision with actions $T,B$. The two ensuing column nodes form one information set $I_2^0$, with available actions $L,R$; column cannot tell which current row action occurred. The four completed first-round histories are $H=\{TL,TR,BL,BR\}$. At each $h\in H$, round two begins at a separate row node. Its two successors, after row's current $T$ or $B$, form a column information set $I_2^h$. Distinct $h$ have distinct information sets: both players know the whole first-round outcome. There are sixteen terminal histories $(h,k)\in H^2$, whose total payoff is $u(h)+u(k)$, as displayed in the tree.

The row player's five information sets are the initial singleton and the four singleton round-two nodes, one per $h$. The column player's five information sets are $I_2^0$ and the four two-node sets $I_2^h$. Thus each player must specify one binary choice at each of five information sets, including histories that its own first choice might prevent:Counting only the four possible two-round action sequences would miss the distinct contingent responses to the opponent's first action.

For a concrete pair of complete pure strategies, order the second-round histories as $(TL,TR,BL,BR)$ and useThe first entry is the initial action, and the four remaining entries prescribe the action after each first-round history. This induces the unique path $TL$ in round one followed by $BR$ in round two. Hence the total payoff isThe off-path entries are part of each pure strategy, even though this pair does not reach them.

For randomization, a mixed strategy is a probability distribution over the $32$ complete plans, with $31$ free probabilities in a general distribution. A behavioural strategy instead gives one binary-action probability at each of five information sets, requiring five parameters. This game has perfect recall: a player never forgets a previous own action or a first-round observation, and the only concealed action is the opponent's current simultaneous choice. Consequently neither kind of randomization has a greater attainable-payoff advantage: Kuhn's theorem gives realization-equivalent strategies against every fixed opposing strategy.^[ref]

The equivalence can be verified directly here. Given a behavioural strategy, sample all five contingent actions independently before play; the resulting product probability distribution over complete plans is an equivalent mixed strategy. Conversely, let $\mu$ be a mixed strategy for player $i$. Use its marginal probability for the initial action. At history $h$ containing own first action $a_i$, choose second action $b_i$ with conditional probabilitywhenever the denominator is positive; if it is zero, choose arbitrarily at that unreachable history. The opponent's first-round action is simultaneous and cannot depend on the sampled hidden plan beyond the chosen first action. Thus conditioning on $h$ preserves exactly these conditional probabilities of actions, and multiplying the first- and second-round factors reproduces each terminal probability. Correlations between prescriptions at mutually exclusive second-round histories have no further observable effect. Behavioural strategies offer the more compact representation, while mixed strategies describe a single random choice of a full plan. Imperfect information here does not mean imperfect recall.

There is no perfect recall. Player 1's later information set joins histories following both of her initial actions, so she has forgotten whether she chose $L$ or $R$. It also hides player 2's intervening action, but failure to observe another player's action is imperfect information, whereas forgetting one's own earlier action is the particular violation of perfect recall. Player 2's two nodes form a single information set because player 2 does not observe the initial choice.

For a behavioural strategy, let $p$ be player 1's initial probability of $L$ and $r$ her later probability of $L$. These are separate information sets, so $p$ and $r$ need not be equal; their random draws are independent. Name player 2's unlabeled branches left and right, and let $q$ be the probability of taking the left branch. The only unit-payoff paths are left–left–left and right–right–right. ConsequentlyBecause this is a zero-sum game, the natural meaning of the claimed best behavioural strategy is its maximum guaranteed expected payoff. Player 2 can choose either branch, so the guarantee at $(p,r)$ isFor nonnegative numbers, their minimum is at most their geometric mean. Also $p(1-p)\le 1/4$ and $r(1-r)\le 1/4$, henceTaking $p=r=1/2$ makes both possible branch-conditioned success probabilities $1/4$, so this upper bound is attained against every $q$. Thus the optimal guaranteed behavioural strategy success probability is $1/4$.

A mixed strategy can instead select the complete plan $LL$ with probability $1/2$ and the complete plan $RR$ with probability $1/2$. The two choices within a sampled plan are correlated. If player 2 chooses left, exactly the sampled plan $LL$ succeeds; if player 2 chooses right, exactly $RR$ succeeds. Therefore the success probability isagainst every opposing mixed strategy. It is optimal among mixed strategies too: player 2's uniform mixture gives success probability $1/2$ to each of $LL,RR$ and zero to $LR,RL$, so no mixture of the four plans can exceed $1/2$ against that opponent. This establishes mixed and behavioural security levels without perfect recall directly.

The guarantee qualification matters: if player 2's branch were known to be left, the deterministic plan $LL$ would succeed with probability one. The number $1/4$ is not an upper bound against every fixed opposing choice separately.

Read the lower-left entry of each cell as player 1's payoff and the upper-right entry as player 2's payoff, as indicated by the source diagram. Against $L$, player 1 strictly prefers $B$ because $2\pi >1$; against $R$, player 1 strictly prefers $T$ because $3>2$. Against $T$, player 2 strictly prefers $R$ because $6>0$; against $B$, player 2 strictly prefers $L$ because $2\sqrt{2}>2$. Thus the pure strategy Nash equilibria are

For a fully mixed strategy Nash equilibrium, write $p=\mathrm{Pr}(T)$ and $q=\mathrm{Pr}(L)$. Player 1's expected payoffs from the two pure strategies areEquality, required when both pure strategies have positive probability, givesPlayer 2's corresponding expected payoffs areso equality givesBoth probabilities lie strictly between zero and one. Hence the unique fully mixed strategy Nash equilibrium iswith complementary probabilities on $B$ and $R$. Its expected payoffs are

These are all three Nash equilibria. There are no equilibria with just one player genuinely mixing: against each opposing pure strategy, the other player's best response is unique, so that player cannot mix. When both players mix, the two linear indifference equations have the unique solution just obtained. This is support enumeration for a bimatrix game with all possible supports checked.

This is an absent-minded decision problem: the two decision nodes belong to the same information set. A behavioural strategy must therefore use the same probability at both visits. Put $p=\mathrm{Pr}(D)$ and $1-p=\mathrm{Pr}(R)$; fresh randomization occurs independently at each visit.

The terminal probabilities are $1-p$ for stopping immediately, $p(1-p)$ for going down once and then right, and $p^2$ for going down twice. Thus the expected payoff isThis expression gives the unique global maximum on $[0,1]$:

The independence of repeated randomizations is essential. A mixed strategy choosing once between the two deterministic plans “always $R$” and “always $D$” gives at most $1$, since their payoffs are $0$ and $1$. It cannot arrange “$D$ first, then $R$” as a deterministic plan respecting this information set. The failure of perfect recall is exactly why mixed strategies and behavioural strategies need not have the same attainable outcome distributions here.

A mixed strategy for Player II is a probability vector $q=(q_1,\dots ,q_n)$, with $q_j\ge 0$ and ${\sum }_j{q}_j=1$. The player chooses pure strategy $j$ with probability $q_j$, independently of the opponent's randomization.

A mixed strategy for Player II is a probability vector $q\ge 0$ with ${\sum }_j{q}_j=1$, specifying the random choice of a column. If Player I chooses row $i$, the expected payment is $(Aq{)}_i$. A mixture of rows cannot exceed the maximum of these row expectations, so the smallest payment Player II can guarantee isAn optimal strategy is a vector attaining that minimum, which exists by compactness of the probability simplex and continuity. The minimax theorem identifies this guaranteed loss with Player I's maximal guaranteed gain, the value of the finite zero-sum game.

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

A player has perfect recall when the information sets never erase that player's previously available information or earlier chosen actions. With perfect recall, randomizing once over complete pure strategies and using suitable independent randomizations at information sets can induce the same outcome distributions.

Without perfect recall, one information set may be encountered twice on the same play path. A behavioural strategy then uses the same probabilities with fresh draws at both encounters; its outcome distribution need not be attainable by any mixed strategy over deterministic plans.

The function taking the lesser value at every common-domain point. It forms the lower envelope of two graphs. For finitely many affine functions it is a concave function: each affine branch is at least the corresponding convex combination of the two endpoint minimum values, so taking the minimum preserves that lower bound. A maximizing mixed strategy in a two-player zero-sum game maximizes such a lower envelope of opposing pure-choice expected payoffs.

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

Two people can each have a clear incentive to choose an outcome that leaves both worse off. The prisoner's dilemma isolates this tension between individual best responses and Pareto efficiency. For example, two partners can each save effort by withholding a promised contribution, yet both would prefer a successful joint project to mutual withholding. The model applies when each person's payoffs really have the ordering below; the names “cooperate” and “defect” alone do not establish a prisoner's dilemma.

In the symmetric two-player normal-form game, each player chooses cooperation $C$ or defection $D$ simultaneously, without observing the other's current choice. The four payoffs are the mutual-cooperation reward $R$, mutual-defection punishment $P$, sole-defector temptation $T$, and sole-cooperator payoff $S$, with $T>R>P>S$. Defection is a strictly dominant strategy: it beats cooperation against either opposing pure strategy. This definition and the resulting one-shot Nash equilibrium are discussed in Steven Kuhn, Prisoner's Dilemma, Stanford Encyclopedia of Philosophy, section 1.

Take the concrete payoffs $T=5$, $R=3$, $P=1$, $S=0$. Each entry below gives the row player's payoff followed by the column player's payoff:

For the row player, switching from $C$ to $D$ improves the payoff from $3$ to $5$ against $C$, and from $0$ to $1$ against $D$. The column player has the same comparisons, so $D$ is a strictly dominant strategy for each. Even against a mixed strategy choosing $C$ with probability $q$, the expected payoff advantage is $2q+(1-q)=1+q>0$. Thus cooperation cannot appear with positive probability in a best response, and $(D,D)$ is the unique one-shot Nash equilibrium, including mixed strategies.

At $(D,D)$, a unilateral deviation to $C$ lowers the deviator's payoff from $1$ to $0$. A joint change to $(C,C)$ instead raises both payoffs from $1$ to $3$: mutual cooperation Pareto dominates mutual defection, making the Nash equilibrium fail Pareto efficiency. A Nash equilibrium tests unilateral deviations, so it need not maximize shared gains. This is the useful lesson: improving the available outcome may require changing incentives, rather than telling each participant to choose a better best response.

The additional inequality $2R\ge T+S$ says that mutual cooperation gives each player at least as much average payoff as equal-time alternation between the two asymmetric outcomes. It is a further assumption, not a consequence of $T>R>P>S$. Here it holds strictly: $6>5$, and alternating exploitation gives each player average payoff $5/2<3$. This comparison concerns equal-time averages, not every discounted sequence. See Kuhn, section 3, on the additional cardinal-payoff condition.

Two strategies for the same player are realization-equivalent when they induce the same probability distribution on terminal histories against every fixed opposing strategy profile. The requirement is stronger than having equal expected payoff against one particular opponent. For a finite extensive-form game with perfect recall, Kuhn's theorem gives this equivalence between appropriate mixed strategies and behavioural strategies.

The replicator equation says that a strategy grows in frequency when its expected payoff exceeds the population's current mean payoff. It is an ordinary differential equation for a composition, rather than for total population size. The subtraction of the mean is what makes relative success matter: even a type growing in absolute number can shrink as a fraction if other types grow faster.

Let $x_i(t)$ be the frequency of pure strategy $i$, with $n$ available pure strategies andIn a symmetric bimatrix game, let the payoff matrix $A$ have entry $a_{ij}$ equal to the payoff to strategy $i$ against $j$. The other player's payoff in that encounter is $a_{ji}$: symmetry between player roles does not require $A=A^T$. Uniform random encounters give the expected payoffs and their population meanAfter choosing the time unit so that the growth-rate scale is one, the continuous-time replicator equation isHere a payoff is measured on a scale proportional to net growth per unit time, not merely as an arbitrary preference ranking. More generally one can specify locally Lipschitz frequency-dependent payoffs $f_i(x)$ directly; the same equation with $\bar{f}={\sum }_i{x}_i{f}_i$ then defines a unique frequency trajectory. The linear pairwise model and its reproductive interpretation are given in Taylor and Jonker (1978), sections 2–3; the formulas here also follow by the following direct normalization.

Suppose the number $N_i$ of type $i$ obeys ${\dot{N}}_i=N_i[b(t)+f_i(x)]$, where the baseline $b(t)$ is identical for all types. Set $N={\sum }_i{N}_i>0$ and $x_i=N_i/N$. The quotient rule givesThus the common baseline cancels. Adding the same constant to every entry of $A$ leaves the replicator equation unchanged; multiplying $A$ by a positive constant changes only the speed along trajectories. The same payoff matrix can therefore describe frequency evolution at different growth-rate baselines and time scales.

The probability simplex is invariant in forward time. On ${\sum }_i{x}_i=1$,Normalization alone would not exclude negative frequencies. Nonnegativity follows as well: along a solution,An absent type remains absent, and a positive frequency remains positive at every finite time. For the fixed payoff matrix model, bounded rates on the compact probability simplex give global forward solutions. Frequencies can still tend to zero as $t\to \infty$. Each face is invariant, so this model has no spontaneous introduction of new pure strategies; mutation or outside introductions would require additional terms. For two present types the logarithm of their frequency ratio satisfies $\frac{d}{dt}\log (x_i/x_j)=f_i-f_j$, directly expressing the accumulated payoff advantage.

For two pure strategies, write the composition as $(x,1-x)$, where $x$ is the frequency of strategy 1, and letTheir payoff difference and the resulting scalar ordinary differential equation areIn the interior $0<x<1$, the sign of the payoff difference determines the direction of motion. The endpoints are always equilibrium points, and an additional interior equilibrium point exists precisely when the affine payoff difference has a zero strictly between them. At a simple interior zero $x_{\ast }$, $F^{\prime }(x_{\ast })=x_{\ast }(1-x_{\ast })\Delta f^{\prime }(x_{\ast })$: a negative value gives asymptotic stability, a positive value gives instability. At the endpoints $F^{\prime }(0)=b-d$ and $F^{\prime }(1)=c-a$, with stability understood relative to $[0,1]$. A zero derivative requires examining the actual flow rather than this strict sign test.

For an original coordination game, imagine two conventions that reward matching, with convention 1 giving the larger matching reward. ChooseThe crossing is $x_{\ast }=2/5$. Below it, convention 1 loses frequency; above it, convention 1 gains frequency. The endpoint equilibrium points $0$ and $1$ have one-sided asymptotic stability, while $2/5$ is unstable: the corresponding derivatives are $-2,-3$ and $6/5$, respectively. Every initial $0<x(0)<2/5$ tends to $0$, every initial $2/5<x(0)<1$ tends to $1$, and exactly $x(0)=2/5$ stays there. Even the convention with the larger matching reward can disappear if it starts below the threshold. This is bistability, not selection of a universally best convention.

The compositions giving a symmetric Nash equilibrium in this coordination game are the two pure conventions and the mixed composition $(2/5,3/5)$. Both pure conventions are evolutionarily stable strategies because a mutant convention has strictly lower payoff against the pure resident. The mixed symmetric Nash equilibrium is not an evolutionarily stable strategy: against that resident both conventions tie, but after a pure convention-1 mutant is introduced its payoff advantage is $5(x-2/5)>0$. Equal payoffs at a symmetric Nash equilibrium need not provide resistance to invasion or asymptotic stability.

For an original coexistence model, choose payoffs making each convention advantageous when sufficiently rare:Here $x_{\ast }=3/4$ attracts every initial composition with both types present: $\dot{x}>0$ below it and $\dot{x}<0$ above it. The interior derivative is $F^{\prime }(3/4)=-3/4$, while $F^{\prime }(0)=3$ and $F^{\prime }(1)=1$ make both endpoints unstable to introduction of the other type. The endpoints nevertheless remain stationary if the other type is exactly absent; the attraction statement excludes those boundary initial states.

The sole symmetric Nash equilibrium in this coexistence model is $p=(3/4,1/4)$. It is also an evolutionarily stable strategy. For any different mixed strategy $q=(y,1-y)$, the first comparison in the two-condition criterion for evolutionary stability ties because $Ap=(3/2,3/2)$. Its second comparison is strictly positive:Thus restoring frequency feedback can protect a mixture even though all present types earn equal payoffs at the mixture. Coexistence here means different individuals using different pure strategies; it does not require every individual to randomize with a mixed strategy.

Frequency evolution need not increase the mean payoff. In the coexistence example $\bar{f}=5x-4x^2$, whose maximum occurs at $x=5/8$, whereas the attracting composition is $3/4$. For $5/8<x<3/4$, the frequency $x$ increases while $\frac{d}{dt}\bar{f}=(5-8x)\dot{x}<0$. Individual payoff advantages drive the equation; maximizing collective mean payoff is a different optimization problem.

More generally, a rest point only equalizes payoffs among present types: $x_i>0$ implies $(Ax{)}_i=x^{T}Ax$. A symmetric Nash equilibrium additionally requires $(Ax{)}_i\le x^{T}Ax$ for every absent type. All vertices are rest points even when an absent type could invade. For finite symmetric bimatrix games, a rest point with Lyapunov stability on the full probability simplex is a symmetric Nash equilibrium; an interior trajectory that converges has a symmetric Nash equilibrium as its limit. These are conditional results, not a convergence theorem for every trajectory. See Cressman and Tao (2014), Theorem 1.

The rock paper scissors payoff matrix gives an explicit obstruction to universal convergence:Since $A^T=-A$, $x^{T}Ax=0$, and in the interior $\frac{d}{dt}\log (x_1{x}_2{x}_3)={\sum }_i(Ax{)}_i=0$. Thus $x_1{x}_2{x}_3$ is conserved. Its maximum on the probability simplex occurs only at $(1/3,1/3,1/3)$, the unique symmetric Nash equilibrium, so an interior trajectory starting elsewhere cannot converge to that composition. Every other interior product level is a closed curve without a rest point, giving a periodic orbit. The existence of these cycles is also discussed in Cressman and Tao (2014), Example 1. The useful lesson is to inspect the specified payoff feedback and dynamical system, rather than infer convergence from the existence of an evolutionarily stable strategy or a Nash equilibrium.

With choices ordered rock, scissors, paper and winner payoff $1$, the row-player payoff matrix is $\left(\begin{array}{ccc}0& 1& -1\\ -1& 0& 1\\ 1& -1& 0\end{array}\right)$. Both the row and column sums vanish. Thus the uniform mixed strategy guarantees expected payoff zero against every opposing strategy; the value of a zero-sum game is zero. A player responding to a known nonuniform mixture can instead optimize its linear expected payoff over pure responses and their ties.

A strategy profile specifies one strategy for every player. A pure strategy strategy profile lies in the Cartesian product $S_1\times \cdots \times S_n$ of the players' strategy sets. A mixed strategy strategy profile specifies one probability distribution ${\sigma }_i$ over each $S_i$. Write $s_{-i}$ or ${\sigma }_{-i}$ for the choices of all players except player $i$.

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

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

For an antisymmetric payoff matrix, such a vector guarantees that an opponent playing rows cannot win positively against it. Antisymmetry also gives $p^{T}A\ge 0$, so the same mixed strategy guarantees nonnegative payoff as a row strategy and proves game value zero. Furthermore $p^{T}Ap=0$ forces $(Ap{)}_i=0$ whenever $p_i>0$. To prove uniqueness, use one certified strategy $q$: any other optimal $p$ satisfies $q^{T}Ap=-(Aq{)}^{T}p$, so a strict negative component of $Aq$ forces the corresponding probability in $p$ to vanish.

In a game invariant under permuting players, a symmetric Nash equilibrium gives every player the same strategy, which may be a mixed strategy. Independent randomization does not require realized resource loads to be equal. When resource delays are affine, a player's expected delay depends on their own certain resource use plus the expected use by the other players; replacing all loads by unconditional total expected loads loses that own-player correction.