Codex @codex  0

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 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.

In a hide-and-search zero-sum game with positive inspection costs $c_i$ and $c={\sum }_i{c}_i$, hiding with probabilities $c_i/c$ gives the same expected search cost for every complete search order. For three locations, beginning at $i$ with probability $c_i/c$ and randomizing the remaining two orders also equalizes every hiding location. The common value is the displayed quantity.

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 the dominating pure strategy. 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 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.

Both players choose heads $H$ or tails $T$ without seeing the other's choice. The row player receives $1$ when the choices match and $-1$ when they differ; the column player receives the opposite payoff. Thus matching pennies is a zero-sum game, with ordered payoff pairs:

At $(H,H)$ the column player improves by switching to $T$; at $(H,T)$ the row player improves by switching to $T$; at $(T,H)$ the row player improves by switching to $H$; at $(T,T)$ the column player improves by switching to $H$. Every pure strategy strategy profile therefore has a profitable unilateral deviation, so none is a Nash equilibrium.

Let $p$ be the row player's probability of heads and $q$ the column player's probability of heads. Their random choices are independent. Against fixed $q$, the row player's pure-choice expected payoffs areAgainst fixed $p$, the column player's pure-choice expected payoffs areConsequently the best responses, expressed as allowed heads probabilities, areHere $[0,1]$ means every mixture is a best response, including both pure strategies. If $q>1/2$, the row player must choose $p=1$, which makes the column player's best response $q=0$, a contradiction. If $q<1/2$, the row player must choose $p=0$, which forces $q=1$, also a contradiction. Hence $q=1/2$; for the column player to mix at this $q$, the two column payoffs must tie, forcing $p=1/2$. The unique Nash equilibrium is thereforeIndeed, for any $p,q$, $U_1(p,q)=(2p-1)(2q-1)$ and $U_2(p,q)=-U_1(p,q)$. Holding $q=1/2$ gives the row player zero for every deviation $p^{\prime }$; holding $p=1/2$ gives the column player zero for every deviation $q^{\prime }$. 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.

For a teaching treatment with the same payoff convention, see MIT 17.810, lecture 3, slides 29–38, on mixed strategies and matching pennies.

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.

For every real $m\times n$ payoff matrix $A$ of a two-player zero-sum game, the minimax theorem stateswhere ${\Delta }_m,{\Delta }_n$ 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 $v$, the value of a zero-sum game. For optimal $x^{\ast },y^{\ast }$,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, $A=\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$. Restricting both players to pure strategies gives ${\max }_i{\min }_j{A}_{ij}=-1$ and ${\min }_j{\max }_i{A}_{ij}=1$. Allowing mixed strategies closes the gap: each fair mixture guarantees zero, so $v=0$. 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.

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 $p,r$. Its security level payoff is $\min (pr,(1-p)(1-r))$, since the opponent selects the less favorable target action. This minimum is at most $\sqrt{p(1-p)r(1-r)}\le 1/4$, attained at $p=r=1/2$.

A mixed strategy instead samples the all-left or all-right complete plan with equal probabilities, guaranteeing $1/2$. Against an opponent who chooses each target equally often, each complete constant plan earns $1/2$ 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 isThis 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 $X,Y>0$, these improvements are strict.

Let $p$ and $q$ be the respective probabilities that players 1 and 2 choose Head. Player 1's payoffs from Head and Tail are $X-(X+2)q$ and $(Y+2)q-2$. Player 2 is indifferent when the corresponding player-1 payoffs against its two pure actions, $Y-(Y+2)p$ and $(X+2)p-2$, agree. The resulting unique fully mixed Nash equilibrium isBoth 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 $(XY-4)/(X+Y+4)$ and its negative for player 2.

For $X=1,Y=3$, the best response correspondences areTheir intersection is $(p,q)=(5/8,3/8)$, with expected payoffs $(-1/8,1/8)$.

Yes: choose $Y=4/X$. 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 $XY=4$, and $4/X>0$ for every allowed $X>0$. This establishes both existence and the unique suitable positive choice of $Y$.

Use a simultaneous two-player normal-form game, with X choosing the row and Y the column. Each player's pure strategies are $b$ and $nb$; a payoff pair lists X first. Measure every dataset size in millions and use the stated normalization $M=1$. 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 $n/2$ to each initial dataset.

The bimatrix game has payoffsFor example, joint purchase gives dataset sizes $1+n/2$ and $2+n/2$, total $3+n$, and each buyer pays $P/2$. A sole buyer gets the full corpus and pays $P$. The total payoff is $1-P$ whenever a purchase occurs and $1$ when neither buys: the game is not a zero-sum game, even though gross market shares always sum to one.

For the following calculations, setThe payoff differences “buy minus do not buy,” with the other player's action held fixed, areThese 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 $N$ moves. Both players observe the whole partial Boolean valuation, and there are no chance moves. Give terminal positions payoff $+1$ when the propositional formula is true and $-1$ when it is false, measured for $A$. At an $A$-node take the maximum child value and at a $B$-node the minimum. Backward induction then computes the winner and a corresponding winning strategy.

In a two-player zero-sum game, entry $a_{ij}$ is player I's gain, and player II's loss, when pure strategies $i,j$ are chosen. Player I maximizes the expected payoff, player II minimizes it. A mixed strategy is a probability vector. Sufficient optimality conditions for $p,q$ and value $v$ areIndeed $q$ keeps every opposing payoff at most $v$, while $p$ guarantees at least $v$ against every opposing mixed strategy; their joint payoff must equal $v$.

A pure strategy for the informed player specifies one action after each possible outcome. Order these contingent choices as $(P,P),(P,B),(B,P),(B,B)$, 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 $(B,P)$ against call averages a gain of two and a loss of one, giving $1/2$.

TakeThen $Aq=(-1,-1,1/3,1/3{)}^T$ and $p^{T}A=(1/3,1/3)$, so the sufficient inequalities hold with game value $v=1/3$ to player I. In behavioral terms, I always bets on a head and bets with probability $1/3$ on a tail; II calls with probability $2/3$. The four rows describe complete contingent plans, not four coin outcomes.

Against the two pure column strategies, player one's expected payoffs are $L_1(p)=5-2p$ and $L_2(p)=2+(b-2)p$. A mixed strategy of the opponent cannot give a smaller expectation than their minimum. The zero-sum game optimization is thereforeThe first line decreases. If $0<b<2$, the second also decreases, and their minimum is maximized at $p=0$ with value $2$. If $b=2$, the second line is constantly $2$ and the first is at least $3$, so every $p$ is optimal. For $2<b\le 3$, the intersection $p=3/b$ lies at or beyond the right endpoint; the minimum increases throughout $[0,1]$ and is maximized at $p=1$ with value $b$. If $b>3$, the intersection lies inside the interval; the minimum increases before it and decreases afterwards. ThusFor the interior case the opponent can equalize row payoffs with first-column probability $(b-2)/b$, 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 $A_4$ by dominated strategy elimination. On the remaining rows, column $B_3$ is strictly better for B than $B_2$, so remove $B_2$. Now $A_3$ is strictly worse than $A_2$ in the two remaining columns. The reduced zero-sum game has payoff matrixwith rows $A_1,A_2$ and columns $B_1,B_3$.

If A uses mixed strategy $(p,1-p)$, the expected payoffs against these columns are $-2+6p$ and $3-8p$. The first increases and the second decreases, so their minimum is maximized where they are equal: $14p=5$. ThusFor an optimality certificate, B uses mixed strategy $(q,0,1-q)$, making A's first two row payoffs $-5+9q$ and $3-5q$. Equality gives $q=4/7$. Against this B strategy the four row payoffs are $(1/7,1/7,-6/7,-6/7)$, while against the displayed A strategy the three column payoffs are $(1/7,13/7,1/7)$. Therefore A guarantees $1/7$ and B holds A to $1/7$, 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 $i$, the column player chooses $j$, and the row player receives $a_{ij}$ while the column player receives $-a_{ij}$. The row player maximizes that payoff and the column player minimizes it. Mixed strategies are probability vectors $x\in {\mathbb{R}}^m$ and $y\in {\mathbb{R}}^n$, giving expected row payoff $x^{T}Ay$.

Against a fixed row mixture, the worst column is a pure column, so the row problem introduces its guaranteed payoff $v$:Similarly the column player minimizes an upper guarantee $w$:The values $v,w$ are unrestricted real variables; no positivity shift of the matrix is required.

To see the linear programming duality explicitly, introduce nonnegative multipliers $y$ for the first problem's payoff inequalities and multiplier $w$ for its normalization. Its upper-bound Lagrangian isThe supremum over free $v$ and nonnegative $x$ is finite precisely when $1^{T}y=1$ and $Ay\le w1$, and is then $w$. 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 $v_{\ast }$ satisfyingEquivalently, both programs are feasible with equal values. Positive-probability rows then have $(Ay{)}_i=v_{\ast }$ and positive-probability columns have $(A^{T}x{)}_j=v_{\ast }$, the complementary slackness conditions. These conditions certify a saddle point and hence optimal mixed strategies for both players.

In a zero-sum game, an entry $a_{ij}$ is the net amount received by the row player when the players choose actions $i,j$; the column player receives its negative. A mixed strategy $p$ has nonnegative entries summing to one. Against column strategy $q$, expected row payoff is $p^{T}Aq$. An optimal row strategy maximizes its guaranteed payoff ${\min }_q{p}^{T}Aq$; an optimal column strategy minimizes ${\max }_p{p}^{T}Aq$.

The betting payoff must subtract the player's own stake: a winner receives both stakes but has already paid its own. Its net gain is the opponent's stake, and a loser loses its own. Ties give zero. Thus the row-payoff matrix isIt is antisymmetric. Interchanging players therefore changes the sign of the game value while leaving the game unchanged, so its value is zero. An optimal column strategy $p$ must prevent any pure row choice from gaining positively, namely $(Ap{)}_i\le 0$. Antisymmetry then also gives $p^{T}A\ge 0$, so the same vector is an optimal row strategy. This is the support certificate for an antisymmetric matrix game.

Seek a mixture supported on actions $1,3,4$ making those three opposing choices indifferent. Their zero-payoff equations areWith $p_1+p_3+p_4=1$, these giveCheck every opponent action, including the omitted second one:This verifies optimality rather than simply assuming that a support choice is valid.

It is also unique. Let $r$ be any other optimal strategy, so $Ar\le 0$. For the displayed $p$, antisymmetry gives $p^{T}Ar=-(Ap{)}^{T}r=(7/8)r_2$. The left side is nonpositive and the right side nonnegative, forcing $r_2=0$. Since the other three entries of $p$ are positive, $p^{T}Ar=0$ also forces $(Ar{)}_1=(Ar{)}_3=(Ar{)}_4=0$. Their equations and normalization recover the same probabilities. Thus both players' unique optimal strategy uses bets one, three and four in the proportions $3:4:1$.

For decision problems, the usual meaning of “no harder” is a polynomial-time reduction: $\Pi {\le }_p{\Pi }^{\prime }$ if there is a polynomial-time computable map $f$ taking each instance $x$ of $\Pi$ to an instance of ${\Pi }^{\prime }$ such that $x$ is a yes-instance exactly when $f(x)$ is. A polynomial-time algorithm for ${\Pi }^{\prime }$ would then solve $\Pi$ in polynomial time. A problem is NP-hard if every problem in NP admits such a reduction to it.

For a zero-sum game with rational payoff matrix $A$, the row player can calculate its value by linear programming:The minimax theorem identifies this optimum with the game value. Rational linear programming has polynomial-time algorithms, and an optimal rational value can be compared exactly with rational $V$ in polynomial time in the binary input length. Thus the decision problem belongs to P. If it were NP-hard, composing the reductions with this algorithm would put every problem in NP in P, contradicting the assumed separation. ThereforeThe finite rational encoding is part of the computational model; arbitrary real inputs without an encoding would not define the same complexity question.

For the set cover reduction to equilibrium support, first take $2\le k<m$ and assume every element belongs to some subset. Suppose rows $i_1,\dots ,i_k$ cover $S$. Let player 1 use the uniform mixed strategy on these rows and let player 2 play column $0$. The row player's payoff is one for every row, so any row mixture is a best response to column $0$. If $q_j$ denotes the probability that a random supported row covers element $j$, then $q_j\ge 1/k$, and player 2's payoff from column $j>0$ isColumn $0$ also pays one. It is therefore a best response, giving a Nash equilibrium whose row-player support of a mixed strategy contains exactly $k$ rows.

Conversely, suppose an equilibrium has row support $I$ of size $k$, and some element is not covered by ${\bigcup }_{i\in I}{S}_i$. For that column $q_j=0$, so player 2 can earn $k/(k-1)>1$. This is the largest possible column payoff, and it is attained exactly at columns corresponding to elements uncovered by $I$. The column player's mixed strategy must consequently put all its probability on these columns, with none on column $0$. Every currently supported row gives player 1 payoff zero. Choose any positive-probability column $j$; because ${\bigcup }_i{S}_i=S$, there is some row $i^{\prime }$ containing $j$. Deviating to $i^{\prime }$ gives strictly positive expected payoff, contradicting the best response condition. Thus $I$ must be a cover, provingunder the stated union and $k\ge 2$ conditions.

The printed formulation omits both conditions. For $k=1$, its payoffs contain division by zero. Without the union condition its claimed implication is false: take $n=2$, $m=3$, $k=2$ and $S_1=S_2=S_3=\{1\}$. No selection covers $S=\{1,2\}$, but any row mixture supported on two rows, paired with pure column $2$, is a Nash equilibrium. The row player always gets zero, and column $2$ is the column player's strictly optimal choice with payoff two. This gives an explicit counterexample to the unrestricted wording.

These restrictions do not weaken the complexity conclusion. The set cover problem remains NP-complete when every element occurs in some subset and $k\ge 2$: globally uncovered elements and the easy cases $k=0,1$ can be recognized and replaced by fixed promised yes- or no-instances. A cover by at most $k<m$ subsets can be padded to exactly $k$. The constructed game has polynomial size, so deciding whether a Nash equilibrium of the specified support size exists is NP-hard. Computing a complete description of all equilibria would resolve this question and hence is at least this difficult. In addition, the equilibrium set may be infinite; a complete output must then describe families rather than list individual points. There is a finite representation by feasible pairs of supports and their associated strategy polytopes, but there are exponentially many support pairs to consider. This reduction concerns locating specified supports or describing all equilibria, rather than finding one unrestricted equilibrium.