Constant-sum game 2026-10-25
In a two-player constant-sum game, the sum of the two payoffs is the same constant at every strategy profile. Replacing each player's payoff by gives a zero-sum game without changing best responses or Nash equilibria. If both players can guarantee , 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 by a unilateral deviation.
Coordination game 2026-10-14
A coordination game rewards compatible choices. Players can have a common interest in coordinating while having different preferred coordinated outcomes, so their interests need not be opposite as in a zero-sum game.
Cost-weighted finite search game Created 2026-10-07 Updated 2026-11-05
Consider a zero-sum game in which a hider selects one of locations and a searcher inspects locations until finding it. Inspection costs are , paid also at the discovered location; the hider maximizes total cost and the searcher minimizes it. Put . The value of a zero-sum game is
The hider uses probabilities . Every complete search order then has the same expected payoff: summing each cost multiplied by the probability that its location or a later one hides the object gives .
For the searcher's matching guarantee, inspect location first with probability , then inspect the remaining locations in a uniformly random order. For distinct , the probability that precedes is
If the object is at , expected total cost is therefore . Both guarantees hold for every opponent choice, proving optimality for any finite number of locations, including the three-location case.
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.
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] developed the theory beyond two-player zero-sum games. The distinction between conflicting and shared interests is fundamental to the subject.
Game tree Created 2026-10-20 Updated 2026-11-05
A game tree is a rooted tree whose nodes are possible histories of play and whose edges are legal next actions. Internal nodes specify the acting player or a chance move; terminal nodes carry outcomes or payoffs. In an extensive-form game, information sets additionally say which decision histories the acting player can distinguish.
Distinct histories may reach the same board position, so a game tree can contain repeated states that a state graph would merge. For finite two-player zero-sum games with perfect information, minimax search propagates terminal values upward. Chance nodes require expectations instead of maximizing or minimizing their outcomes.
Matching pennies 2026-10-14
Both players choose heads or tails without seeing the other's choice. The row player receives when the choices match and when they differ; the column player receives the opposite payoff. Thus matching pennies is a zero-sum game, with ordered payoff pairs:
Row choice / column choice
At the column player improves by switching to ; at the row player improves by switching to ; at the row player improves by switching to ; at the column player improves by switching to . Every pure strategy strategy profile therefore has a profitable unilateral deviation, so none is a Nash equilibrium.
Let be the row player's probability of heads and the column player's probability of heads. Their random choices are independent. Against fixed , the row player's pure-choice expected payoffs are
Against fixed , the column player's pure-choice expected payoffs are
Consequently the best responses, expressed as allowed heads probabilities, are
Here means every mixture is a best response, including both pure strategies. If , the row player must choose , which makes the column player's best response , a contradiction. If , the row player must choose , which forces , also a contradiction. Hence ; for the column player to mix at this , the two column payoffs must tie, forcing . The unique Nash equilibrium is therefore
Indeed, for any , and . Holding gives the row player zero for every deviation ; holding gives the column player zero for every deviation . 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.
Figure 1.
Matching pennies: pure-choice expected payoffs and the unique intersection of best responses
. Details.
Matrix-game optimization problem Created 2026-09-24 Updated 2026-11-05
For a finite two-player zero-sum game with payoff matrix to the row player, its mixed-strategy optimization problem is
Every column inequality says that the expected payoff against that pure column is at least . A randomized column gives an average of these payoffs, so the same guarantee holds against every mixed opposing strategy. The constraints on make it a probability vector. The corresponding minimizing linear-program dual gives the column player's security problem and the finite minimax value.
Minimax search 2026-10-25
Backward induction on a finite deterministic game tree of a two-player zero-sum game. Terminal payoffs are propagated by maximization at one player's decision nodes and minimization at the other's. With full information, the resulting choices give an optimal strategy against the opposing player's best response. A cyclic state graph requires a winning condition on infinite plays and a graph algorithm rather than unrestricted recursive unfolding.
Minimax theorem Created 2026-09-24 Updated 2026-10-14
For every real payoff matrix of a two-player zero-sum game, the minimax theorem states
where are the players' probability simplices. Both outer optima are attained. The row player's security level payoff is the largest payoff it can guarantee against all opposing choices; the column player can hold that payoff to the same number , the value of a zero-sum game. For optimal ,
These are exactly the Nash equilibrium inequalities under the row-maximizes, column-minimizes convention. Conversely, a Nash equilibrium of this two-player zero-sum game supplies both guarantees. This equality explains why independent worst-case optimization solves the opposing incentives in this special class.
Allowing mixed strategies is essential. For matching pennies, . Restricting both players to pure strategies gives and . Allowing mixed strategies closes the gap: each fair mixture guarantees zero, so . These guarantees hold even if the opponent knows the mixture's probabilities, provided the opponent does not observe the sampled choice before choosing.
John von Neumann proved the two-player zero-sum game result in Zur Theorie der Gesellschaftsspiele, Mathematische Annalen 100, 295–320 (1928); the original article's footnote 7 explicitly discusses the equality of max–min and min–max. Nash's [ref] states that existence of a Nash equilibrium is equivalent to this result in the two-player zero-sum game case, and extends existence to all finite games.
Minmax payoff 2026-10-25
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.
Consider a zero-sum game in which a player chooses a binary action, forgets it, and chooses again, while an opponent makes one hidden binary choice. The first player's payoff is one if all three choices agree and zero otherwise. The later information set merges both initial-action histories. This violates perfect recall without revisiting the same information set, unlike an absent-minded decision problem.
A behavioural strategy chooses the first and second actions with independent left probabilities . Its security level payoff is , since the opponent selects the less favorable target action. This minimum is at most , attained at .
A mixed strategy instead samples the all-left or all-right complete plan with equal probabilities, guaranteeing . Against an opponent who chooses each target equally often, each complete constant plan earns and each nonconstant plan earns zero, so no mixed strategy can guarantee more. The separation comes from correlation between a sampled plan's actions; fresh independent randomizations cannot retain it after the initial action is forgotten.
With rows and columns ordered Head, Tail, the payoff matrix of ordered pairs is
This is a zero-sum game. There is no pure Nash equilibrium: when the coins match, player 1 gains by switching to a mismatch; when they do not match, player 2 gains by making them match. Since , these improvements are strict.
Let and be the respective probabilities that players 1 and 2 choose Head. Player 1's payoffs from Head and Tail are and . Player 2 is indifferent when the corresponding player-1 payoffs against its two pure actions, and , agree. The resulting unique fully mixed Nash equilibrium is
Both numbers lie strictly between zero and one. If either player instead used a pure action, the other's unique best response would force the pure-action cycle above, so there are no additional partly mixed equilibria. Substitution gives player 1's expected payoff and its negative for player 2.
For , the best response correspondences are
Their intersection is , with expected payoffs .
Figure 1.
The two best response correspondences intersect at the unique mixed equilibrium
. The horizontal axis is player 1's Head probability , and the vertical axis is player 2's Head probability . Whole intervals at indifference are included. Details.
Yes: choose . The equilibrium expected payoffs are opposite because this is a zero-sum game. They are equal exactly when both are zero. Part (b)'s value vanishes exactly when , and for every allowed . This establishes both existence and the unique suitable positive choice of .
Use a simultaneous two-player normal-form game, with X choosing the row and Y the column. Each player's pure strategies are and ; a payoff pair lists X first. Measure every dataset size in millions and use the stated normalization . The source's reference to a shared half as “points” is interpreted in the same million-point units as the corpus, so the shared addition is to each initial dataset.
The bimatrix game has payoffs
For example, joint purchase gives dataset sizes and , total , and each buyer pays . A sole buyer gets the full corpus and pays . The total payoff is whenever a purchase occurs and when neither buys: the game is not a zero-sum game, even though gross market shares always sum to one.
For the following calculations, set
The payoff differences “buy minus do not buy,” with the other player's action held fixed, are
These four differences give all the best response comparisons without mixing up row and column payoffs.
Minimax search applies because this is a finite, deterministic two-player zero-sum game with perfect information. Each move assigns a previously unassigned Boolean variable, so play terminates after exactly moves. Both players observe the whole partial Boolean valuation, and there are no chance moves. Give terminal positions payoff when the propositional formula is true and when it is false, measured for . At an -node take the maximum child value and at a -node the minimum. Backward induction then computes the winner and a corresponding winning strategy.
In a two-player zero-sum game, entry is player I's gain, and player II's loss, when pure strategies are chosen. Player I maximizes the expected payoff, player II minimizes it. A mixed strategy is a probability vector. Sufficient optimality conditions for and value are
Indeed keeps every opposing payoff at most , while guarantees at least against every opposing mixed strategy; their joint payoff must equal .
A pure strategy for the informed player specifies one action after each possible outcome. Order these contingent choices as , with the first action for a head. The columns are fold and call. Averaging over the fair coin gives the payoff matrix, in currency units,
For example, row against call averages a gain of two and a loss of one, giving .
Take
Then and , so the sufficient inequalities hold with game value to player I. In behavioral terms, I always bets on a head and bets with probability on a tail; II calls with probability . The four rows describe complete contingent plans, not four coin outcomes.
Against the two pure column strategies, player one's expected payoffs are and . A mixed strategy of the opponent cannot give a smaller expectation than their minimum. The zero-sum game optimization is therefore
The first line decreases. If , the second also decreases, and their minimum is maximized at with value . If , the second line is constantly and the first is at least , so every is optimal. For , the intersection lies at or beyond the right endpoint; the minimum increases throughout and is maximized at with value . If , the intersection lies inside the interval; the minimum increases before it and decreases afterwards. Thus
For the interior case the opponent can equalize row payoffs with first-column probability , confirming the minimax theorem value.
Player A maximizes the payoff, while B minimizes it. The fourth row is strictly worse for A than the first in every column, so remove by dominated strategy elimination. On the remaining rows, column is strictly better for B than , so remove . Now is strictly worse than in the two remaining columns. The reduced zero-sum game has payoff matrix
with rows and columns .
If A uses mixed strategy , the expected payoffs against these columns are and . The first increases and the second decreases, so their minimum is maximized where they are equal: . Thus
For an optimality certificate, B uses mixed strategy , making A's first two row payoffs and . Equality gives . Against this B strategy the four row payoffs are , while against the displayed A strategy the three column payoffs are . Therefore A guarantees and B holds A to , verifying the value of a zero-sum game and the original, unreduced mixed strategy.
In a finite two-person zero-sum game the row player chooses , the column player chooses , and the row player receives while the column player receives . The row player maximizes that payoff and the column player minimizes it. Mixed strategies are probability vectors and , giving expected row payoff .
Against a fixed row mixture, the worst column is a pure column, so the row problem introduces its guaranteed payoff :
Similarly the column player minimizes an upper guarantee :
The values are unrestricted real variables; no positivity shift of the matrix is required.
To see the linear programming duality explicitly, introduce nonnegative multipliers for the first problem's payoff inequalities and multiplier for its normalization. Its upper-bound Lagrangian is
The supremum over free and nonnegative is finite precisely when and , and is then . Minimizing it gives the displayed column problem, proving that the programs are a dual pair.
A sufficient optimality certificate is a pair of probability vectors and a common value satisfying
Equivalently, both programs are feasible with equal values. Positive-probability rows then have and positive-probability columns have , the complementary slackness conditions. These conditions certify a saddle point and hence optimal mixed strategies for both players.