Asymmetric coordination example 2026-10-14
Two players independently choose venues or . Meeting at gives the ordered payoff pair ; meeting at gives ; choosing different venues gives . As throughout this article, the row player's payoff comes first:
| Row choice / column choice | ||
|---|---|---|
Against a column player choosing , the row player gets from and from , so is the unique best response. Against , the row player gets from and from , so is the unique best response. The column player likewise prefers to match the row choice. Thus and are pure strategy Nash equilibria, while each mismatched strategy profile has a profitable unilateral deviation.
For mixed strategies, let and be the row and column probabilities of choosing . The pure-choice expected payoffs areThe row player is indifferent when , giving . The column player is indifferent when , giving . The best responses are thereforeThese give exactly three Nash equilibria: . 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 , and the column player's indifference fixes the row player's .
At the mixed Nash equilibrium, independence givesThus they meet with probability , and each receives expected payoff . Holding fixed, every row deviation gives ; holding fixed, every column deviation gives . This directly verifies the Nash equilibrium inequalities.
Both coordinated pure strategy outcomes strictly improve both players' expected payoffs over : and 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 .
Asymmetric coordination: three best-response intersections and the cost of independent mixing
. Details. Behavioural strategy 2026-10-24
An assignment of an action probability distribution to every information set of a player in an extensive-form game. Randomization is fresh at each encounter. It differs from a mixed strategy, which chooses a complete deterministic plan once before play. Perfect recall is central to equivalence of their induced outcome distributions.
Best response Created 2026-10-03 Updated 2026-10-31
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 in matching pennies, the row player's heads and tails expected payoffs are and , so heads is the unique best response. Against , all mixtures are best responses. In the asymmetric coordination example, against the row player gets from and from , so is optimal. A Nash equilibrium requires everyone to be a best response simultaneously; one optimal reply alone does not establish it.
Binary game Created 2026-10-25 Updated 2026-10-31
A binary game is a finite normal-form game in which each player's payoff at every pure strategy profile is either zero or one. This describes the numerical payoffs, not the number of players or available actions. A mixed strategy can have an intermediate expected payoff. If a weighted average of binary payoffs is at least one, every positive-weight term must equal one; this observation makes pure-by-mixed domination unusually simple in binary games.
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.
Dominated strategy Created 2026-09-24 Updated 2026-11-05
A dominated strategy is inferior to another available strategy under a specified comparison of payoffs. The alternative may be a pure strategy or a mixed strategy; allowing mixtures can reveal domination missed by comparing pure actions alone.
A strictly dominated strategy gives strictly smaller expected payoff against every opposing strategy profile. A weakly dominated strategy gives no larger expected payoff against any opposing profile and gives strictly less against at least one. Requiring strict improvement somewhere distinguishes weak domination from payoff-equivalent strategies.
For example, against two opposing actions, a row with payoffs is weakly dominated by and strictly dominated by . Strict dominance excludes an action from the support of a Nash equilibrium, but weak domination does not exclude equilibrium strategies. These different guarantees matter in dominated strategy elimination.
Dominated strategy elimination Created 2026-10-14 Updated 2026-11-05
In a finite zero-sum game, removing a strictly dominated strategy preserves the value of a zero-sum game: replace any probability on it by a dominating mixed strategy, including a pure one. This increases every payoff for the maximizing player, or decreases every payoff for the minimizing player. Repeat on the reduced game; new domination relations may appear after a deletion.
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.
Expected payoff 2026-10-14
For a finite game, let range over all pure strategy strategy profiles, and let be player 's probability of choosing . Under independent mixed strategies, the probability of is . The displayed sum is the expected value of player 's payoff. Holding everyone else's mixed strategy fixed makes a linear function of ; this is why checking pure strategy deviations suffices to check all mixed strategy deviations.
Extensive games and the problem of information by Harold W. Kuhn Created 2026-10-24 Updated 2026-11-05
Original publication: Contributions to the Theory of Games II, pp. 193–216. Publisher record: doi.org/10.1515/9781400881970-012
Publisher record for the reprint in Classics in Game Theory, pp. 46–68: www.degruyterbrill.com/document/doi/10.1515/9781400829156-011/html
The paper develops extensive-form games and Kuhn's theorem relating mixed strategies, behavioural strategies and perfect recall. The finite two-round construction is proved directly in the examination solution.
Feasible payoff set 2026-10-25
The convex hull of the stage game's attainable payoff vectors. Public randomization or deterministic sequences with prescribed limiting frequencies produce such average payoffs. It can be larger than the set attainable using independent mixed strategies in a single stage.
Fully mixed Nash equilibrium 2026-10-25
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.
Fully mixed strategy 2026-10-25
A mixed strategy assigning strictly positive probability to every available pure strategy. Its support of a mixed strategy is the entire action set. A mixed strategy can be non-pure without being fully mixed when there are more than two actions.
Gain-map proof of symmetric equilibrium 2026-10-14
For a symmetric finite game, pure-action expected payoffs 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 and . The fixed-point equations give . If , every supported action has strictly positive excess payoff, contradicting . Hence and every supported action is a best response, proving a symmetric Nash equilibrium.
Game Created 2026-10-20 Updated 2026-11-05
A mathematical game specifies participants, available choices, information and consequences of combined choices. A normal-form game records complete strategies and payoffs; an extensive-form game records the sequence of decisions and what each player knows at them.
For example, matching pennies gives each player two actions and opposing payoffs depending on whether their choices agree. Its equilibrium requires mixed strategies. A puzzle with one decision maker is often called a game informally, but strategic interaction and game theory enter when outcomes depend on several decision makers' choices. The rules determine the mathematical object; a physical board alone does not.
Game theory Created 2026-09-24 Updated 2026-10-13
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 : 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]
https://cs.uwaterloo.ca/~klarson/teaching/F04-886/papers/nash51.pdf. 1951 paper, Non-Cooperative Games, Annals of Mathematics 54, 286–295
developed the theory beyond two-player zero-sum games. The distinction between conflicting and shared interests is fundamental to the subject. Harold W. Kuhn Created 2026-10-14 Updated 2026-11-05
Harold W. Kuhn connected game theory with continuous and discrete optimization. His work with Albert W. Tucker supplied the1951 nonlinear-programming formulation behind the Karush-Kuhn-Tucker conditions, while his1955 Hungarian algorithm addressed the assignment problem. He also developed extensive-form games and the relation between mixed strategies and behavioral strategies.[ref]
https://www.princeton.edu/news/2014/07/05/harold-kuhn-princeton-mathematician-who-advanced-game-theory-dies-88. Princeton University obituary, research on nonlinear programming, extensive games and the1955 assignment paper
These contributions distinguish three mathematical questions: local constrained optimality, a discrete cost-minimizing assignment, and which randomized decisions can represent a player's information-dependent plan.Biography: www.princeton.edu/news/2014/07/05/harold-kuhn-princeton-mathematician-who-advanced-game-theory-dies-88
Portrait of Harold W. Kuhn
. Portrait identified on the Princeton University obituary. Image credit: Princeton University Office of Communications. Individually rational payoff in a repeated game Created 2026-10-25 Updated 2026-11-05
A payoff vector in a repeated game is individually rational when it gives every player at least that player's minmax payoff. It is strictly individually rational when every inequality is strict. These comparisons use each player's own payoff scale.
For a two-player finite stage game, the minimax theorem identifies this bound with the player's maximum guaranteed expected payoff. For example, in a prisoner's dilemma with , defection guarantees , and the cooperative payoff vector is strictly individually rational. This does not by itself prove that cooperation is an equilibrium under any specified horizon or monitoring rule.
With several opponents, the permitted correlation in their punishment strategies matters: a minmax over independent opposing mixed strategies need not equal the player's maximin guarantee against a coordinated coalition. Therefore one must state the repeated-game information and punishment conventions before interpreting the bound as an enforceable guarantee. This use is distinct from the participation constraints called individual rationality in mechanism design.
Kuhn's theorem 2026-10-25
In a finite extensive-form game with perfect recall, each mixed strategy has a realization-equivalent behavioural strategy, and every behavioural strategy has a realization-equivalent mixed strategy. The latter direction samples all contingent actions independently in advance. For the former, condition the random complete plan on the player's own action and information history leading to an information set; perfect recall makes that own history common to its nodes. Conditional action probabilities then reproduce the terminal path factors. At an information set reached with zero probability under that player's own plan distribution, choose any action distribution. The result does not assert equivalence without perfect recall.[ref]
Extensive games and the problem of information by Harold W. Kuhn. original article, pp. 193–216, perfect-recall equivalence
Lottery over joint action profiles Created 2026-10-07 Updated 2026-10-14
A probability distribution over joint action profiles implements a convex combination of their two-player payoff vectors. The attainable expected payoffs form the convex hull of the pure joint payoffs. The distribution need not factor into independent mixed strategies, and a freely enforceable lottery need not satisfy the incentive constraints of a Nash equilibrium.

