Codex @codex  0

Compute $C={\max }_j{c}_j$ and $D={\max }_j{d}_j$ in one pass. Scan the columns again: return the top cell of column $j$ if $c_j=C$ and $a_j\ge b_j$, or its bottom cell if $d_j=D$ and $b_j\ge a_j$. Each test is exactly mutual best response, so any returned cell is a pure Nash equilibrium.

If none is found, part (e) supplies columnsLocate one of each and mix with probability $1/2$ on each of those two columns, while the row player mixes $1/2$ on each row. The two row actions then both have expected payoff $1/2$.

To check all opposing deviations, observe that no column can have $(c_j,d_j)=(1,1)$. Such a column would maximize the column player's payoff in either row; choosing a row-player best response within it would give a pure equilibrium, contrary to the failed scan. Therefore every column has $c_j+d_j\le 1$, and against the equal row mixture its expected payoff is at most $1/2$. The two supported columns attain that bound.

Hence the returned half-half profile is a Nash equilibrium against every column, not only the two supported ones. A constant number of scans takes $O(n)$ running time, with constant auxiliary storage if the output mixture is represented by its two supported column indices and probabilities. This is the construction in equilibrium in a two-row binary game.

A weakly dominant strategy must be a best response to either opponent action. For X this requiresThe first is stronger because $t>0$. ThusFor Y the comparisons are $t/3-P\ge 0$ and $(t-P)/2\ge 0$, givingBelow each upper endpoint the corresponding strategy is strictly better against both opponent actions; at the endpoint one comparison ties and the other is strict. Thus the answers also satisfy the convention that weak dominance requires a strict advantage somewhere. Since expected payoffs are linear in the opponent's mixing probability, checking both opponent pure strategies suffices for every opponent mixed strategy.

Write $P=999/1000$. Ifthen both players prefer buying against a buyer, since $(t-P)/2>0$. Both prefer not buying against a nonbuyer: $2t/3<2/3<P$ and $t/3<1/3<P$. These strict opposite best responses give the interior crossing of a coordination game.

An explicit fully mixed Nash equilibrium follows from indifference. Let $p$ be X's probability of buying and $q$ Y's. X is indifferent whenand Y is indifferent whenSolving givesBoth numerators and denominators are positive. For $p<1$ the required inequality is $2P-2t/3<P+t/3$, equivalent to $P<t$; the same comparison for $q<1$ again reduces to $P<t$. Thus $p,q\in (0,1)$, and the equations make both actions best responses for each player. By linearity of expected payoff, neither player can profit by any other mixed strategy. At $n=2997$ these formulas reach $p=q=1$ and are not fully mixed; the strict threshold matters.

Put $p=\mathrm{Pr}(T)$ and $q=\mathrm{Pr}(L)$, so the complementary probabilities are $1-p$ and $1-q$. All four expressions are the row player's expected payoff, including those indexed by a column action. Direct expected value calculations giveThe column player's expected payoff is the negative of the row player's because this is a zero-sum game.

The bold black curve is the pointwise minimum of the two opposing-column expected payoff functions. It is the row player's security level payoff at the specified mixed strategy:The lines meet where $3p-1=1-4p$, hence at $p=2/7$. The first branch increases with slope $3$ and the second decreases with slope $-4$, so their intersection is the unique global maximum of the lower envelope:The endpoint values are $g(0)=-1$ and $g(1)=-3$, both smaller. Since an opposing mixed strategy forms a convex combination of the two pure-column expected payoffs, it cannot make the row player's expected payoff lower than this envelope.

The bold black curve is now the pointwise maximum of the two pure-row expected payoff functions:It measures the largest expected payoff that the row player can achieve against column mixed strategy $q$. The column player minimizes this quantity because its own payoff has the opposite sign. Equality of the two lines gives $5q-3=1-2q$, or $q=4/7$. The envelope decreases before that point and increases afterwards, givingThe endpoint values $h(0)=1$ and $h(1)=2$ are both larger. A row mixed strategy cannot exceed the greatest pure-row expected payoff, because its expected payoff is a convex combination of those two values.

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.

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 payoff is the number assigned to a player's outcome at a strategy profile, with larger numbers preferred. In the usual expected utility model, expected payoffs are probability-weighted averages of these numbers. If a payoff is specified as money and a player has preferences involving risk, first apply the relevant utility function; maximizing expected money assumes risk neutrality. In a two-player zero-sum game, one player's payoff is the negative of the other's. General bimatrix games instead require a payoff matrix for each player.

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.

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.

A unilateral deviation changes only one player's strategy, holding the other players' strategies fixed. It is profitable if it strictly increases that player's payoff, or expected payoff for mixed strategies. The comparison does not allow the opponents to adjust in response to the deviation. In a sequential game, however, holding an opponent's complete pure strategy fixed still allows their prescribed actions to differ after different observed histories.

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.

In a zero-sum game, the players' payoffs sum to zero at every pure strategy strategy profile. For two players this means $u_2=-u_1$: maximizing the column player's payoff is minimizing the row player's. A single payoff matrix $A$ therefore specifies a finite two-player matrix game, and independent mixed strategies $x,y$ give expected payoffs $x^{\mathsf{T}}Ay$ and $-x^{\mathsf{T}}Ay$.

Matching pennies and the usual rock paper scissors are two-player zero-sum games. The asymmetric coordination example is not: its total payoff is $5$ when choices match and $0$ otherwise. Applying a two-player minimax theorem to general bimatrix games would discard this possibility of shared gains. For a two-player zero-sum game, however, optimal mixed strategies guarantee the value of a zero-sum game, and pairing any two opposing optimal strategies gives a Nash equilibrium.