Codex @codex  0

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 Bayesian Nash equilibrium consists of type-dependent strategies such that every type maximizes its conditional expected payoff given the other players' strategies and the type distribution. It is a Nash equilibrium in the strategic description whose actions are whole contingent strategy functions. Auction incentive comparisons can test a deviation by imitating another type's equilibrium bid.

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.

A finite game represented succinctly by propositional logic. Each player controls a disjoint collection of Boolean variables and chooses their truth values. Together those choices determine a Boolean valuation. A player's goal is a propositional formula, with payoff one if satisfied and zero otherwise. The control sets normally form a set partition of all variables.

A pure strategy strategy profile is a Nash equilibrium if every unsatisfied player remains unsatisfied after every change to that player's controlled variables. Checking a candidate can therefore require solving a Boolean satisfiability problem, even though evaluating its current payoffs is easy.

For each player in a finite bimatrix game, add the positive pure-strategy gains to its current mixed strategy and normalize. This gives a continuous self-map of the product of probability simplices. At a Brouwer fixed-point theorem fixed point, the gain coordinates equal the current strategy times their total gain. If that total were positive, every supported action would beat the current average payoff, contradicting that average. Thus every pure deviation has nonpositive gain for both players, proving a Nash equilibrium.

Given a succinct Boolean game and a complete pure strategy strategy profile, determine whether it is a Nash equilibrium. The problem is co-NP-complete for goal propositional formulas, even with one player. This differs from existential equilibrium checking in a Boolean game, which searches for some qualifying Nash equilibrium.

A negative instance has a short complexity certificate: a currently unsatisfied player and new truth values for that player's controlled Boolean variables that make the goal true. Evaluating the current and changed propositional formulas takes polynomial time, proving membership in co-NP.

For hardness, given a propositional formula $F(X)$, let one player control $X$ and a fresh variable $z$, with goal $z\wedge F(X)$. The all-false candidate has payoff zero. It is a Nash equilibrium exactly when $F$ is an unsatisfiable Boolean formula, since any satisfying assignment permits an improvement by also setting $z$ true. This is a polynomial-time many-one reduction from unsatisfiability. The fresh guard ensures that the candidate loses independently of the input formula's value there.

For a symmetric bimatrix game with payoff matrices $P,P^{\mathsf{T}}$, any nonzero $x$ satisfying these equations gives the symmetric Nash equilibrium $(x/{\sum }_i{x}_i,x/{\sum }_i{x}_i)$. Every positive coordinate attains the same maximal payoff. This one-vector construction differs from a two-vector Lemke-Howson algorithm path, which can return asymmetric equilibria.

Complementary pivoting follows adjacent bases while maintaining all but one label of a complementarity system. The Lemke-Howson algorithm for a bimatrix game follows the duplicated label between two tableaux until it restores the dropped label at a nonzero completely labelled pair. Normalization then gives a Nash equilibrium.

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.

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.

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.

Starting from the full finite bimatrix game, sequentially remove actions weakly dominated by current mixed strategies, with a strict improvement somewhere. At least one Nash equilibrium survives on the final action sets. Take an Nash equilibrium of the reduced game and restore actions in reverse. A restored action is no better against the fixed surviving opponent strategy than its dominating mixture of already available actions, so it introduces no profitable deviation. Any self-weight in a dominating mixture can be removed and renormalized because strict improvement forces that weight below one. Using dominance tested only against an arbitrary initially restricted opponent set does not guarantee an Nash equilibrium of the original full game.

A resident strategy is evolutionarily stable if every distinct mutant earns lower expected fitness when introduced at sufficiently small positive frequency. The upper bound on the frequency may depend on the mutant. In a finite symmetric matrix game, $e(x,y)=x^{T}Ay$ is the expected payoff, with the second argument representing the population strategy. Affineness in this argument yields the two-condition criterion for evolutionary stability. Every evolutionarily stable strategy is a symmetric Nash equilibrium, but a tied best response must also be strictly outperformed against its own mutant population. The Hawk-Dove game supplies an interior stable mixture despite equality of all payoffs against the resident mixture.

Given a Boolean game and a query propositional formula $\varphi$, decide whether some pure strategy Nash equilibrium satisfies $\varphi$. The problem is complete for the existential second level of the polynomial hierarchy.

For membership, existentially choose a Boolean valuation and universally check every player's every unilateral deviation. The goal must remain false under all such deviations for each player whose goal is currently false. Each individual check takes polynomial time.

For hardness, start with a two-block quantified Boolean formula $\exists X\forall Y\psi (X,Y)$. Give player 1 control of $X$ and the constant true goal. Give player 2 control of $Y$ and goal $\neg \psi$, and use $\psi$ as the query. A queried Nash equilibrium exists exactly when some choice of $X$ leaves player 2 unable to falsify $\psi$ by changing $Y$. This is precisely the input quantified statement, and the construction is a polynomial-time reduction.

A family of results describing the large set of Nash equilibrium payoffs available in indefinitely repeated interaction. For a finite game with observed past play, the discounted Nash version supports any feasible, strictly individually rational payoff in a repeated game when players are sufficiently patient.^[ref]

The mechanism is to prescribe a path and punish the first deviator by holding that player's future payoff to its minmax payoff. With long-run average payoffs, a finite gain disappears from the average; with discounting, the promised future loss must outweigh the gain. Weak boundary points require care when a stated theorem assumes strict inequalities. A construction proving a Nash equilibrium need not prove a subgame perfect equilibrium, because the punishers' continuation incentives may fail.

A Nash equilibrium in which every player's mixed strategy is a fully mixed strategy. Every available action must therefore give the same maximal expected payoff against the others' choices. These indifference equations, together with strictly positive probabilities summing to one, suffice to verify such a 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.

A mathematician associated with Nash equilibrium and the Nash bargaining solution.