Zero-sum Game · aiwiki.page

A zero-sum game is a game in game theory in which the sum of all players’ payoffs is zero for every possible outcome. In the two-player case, one player’s payoff is exactly the negative of the other’s: any gain for one is an equal loss for the other. Two-player zero-sum games provide a mathematical model of completely opposed interests and have particularly strong connections to equilibrium theory and optimization. (learn.mit.edu)

Definition and constant-sum games

For players $1,\ldots,n$ , let $u_i(s)$ denote player $i$ ’s payoff at the strategy profile $s$ , a specification of every player’s strategy. The zero-sum condition is

\sum_{i=1}^{n}u_i(s)=0 \quad\text{for every }s.

For two players this becomes $u_2(s)=-u_1(s)$ . Payoffs represent the numerical rewards or utilities specified by the model; they need not be monetary payments. (cs.cmu.edu)

A constant-sum game instead satisfies $\sum_i u_i(s)=c$ , where $c$ is independent of the outcome. It can be converted into a zero-sum game by subtracting constants from the players’ payoffs whose sum is $c$ . For example, subtracting $c/n$ from each payoff makes the total zero without changing any player’s strategic preferences. Thus constant-sum and zero-sum games are strategically equivalent under this normalization. (bpb-us-e1.wpmucdn.com)

“Zero-sum” does not mean that every player receives zero, that the game is fair, or that its equilibrium value is zero. It describes the sum of payoffs, not their individual magnitudes. (cs.cmu.edu)

Matrix representation and strategies

A finite two-player zero-sum game can be represented by a single payoff matrix $A$ . The row player chooses row $i$ , the column player chooses column $j$ , and their payoffs are $A_{ij}$ and $-A_{ij}$ , respectively. The row player seeks to maximize this entry; the column player seeks to minimize it. (cs.cmu.edu)

A pure strategy selects one available strategy with certainty. A mixed strategy is a probability distribution over pure strategies. If the players randomize independently using probability vectors $x$ and $y$ , the row player’s expected payoff is

x^{\mathsf T}Ay =\sum_i\sum_j x_iA_{ij}y_j,

where all probabilities are nonnegative and each vector sums to one. Randomization can prevent an opponent from exploiting a predictable choice. (cs.cmu.edu)

Minimax theorem and equilibrium

The row player’s maximin payoff is the largest expected payoff that can be guaranteed against every opposing strategy. The column player’s minimax bound is the smallest upper bound that can be imposed on the row player’s payoff. John von Neumann’s minimax theorem, proved in 1928, states that these quantities coincide for every finite two-player zero-sum game:

\max_{x\in\Delta_m}\min_{y\in\Delta_n}x^{\mathsf T}Ay = \min_{y\in\Delta_n}\max_{x\in\Delta_m}x^{\mathsf T}Ay =v,

where $\Delta_m$ and $\Delta_n$ are the sets of probability vectors of the indicated dimensions. The number $v$ is the value of the game to the row player. (web.mit.edu)

Optimal strategies $x^*,y^*$ satisfy

x^{\mathsf T}Ay^* \leq x^{*\mathsf T}Ay^* =v \leq x^{*\mathsf T}Ay \quad\text{for all }x,y.

They form a saddle point and a Nash equilibrium: neither player can improve their payoff by changing strategy alone. Optimal strategies need not be unique, but all equilibrium pairs yield the same value. These guarantees concern expected payoffs, not the result of each individual play. (web.mit.edu)

Example: matching pennies

In matching pennies, each player simultaneously chooses heads or tails. The row player receives $+1$ if the choices match and $-1$ otherwise; the column player receives the opposite payoff:

Row player / Column player	Heads	Tails
Heads	$1$	$-1$
Tails	$-1$	$1$

There is no pure-strategy equilibrium: against any fixed choice, an opponent can select a favorable response. In equilibrium, both players choose heads and tails with probability $1/2$ , giving a game value of zero. A player using this mixture obtains expected payoff zero against either opposing pure choice, although each individual play still produces a winner and a loser. (cs.cmu.edu)

Computation and scope

Finite matrix games can be solved using linear programming. The row player maximizes $v$ subject to

A^{\mathsf T}x\geq v\mathbf 1,\qquad \mathbf 1^{\mathsf T}x=1,\qquad x\geq0.

The column player minimizes $w$ subject to

Ay\leq w\mathbf 1,\qquad \mathbf 1^{\mathsf T}y=1,\qquad y\geq0.

These constraints express payoff guarantees against every opposing pure strategy. The two programs are dual, and strong duality yields $v=w$ , providing a proof of the minimax theorem. (arxiv.org)

The two-player qualification matters. With three or more players, a zero total payoff does not imply that every pair has opposed interests: several players may gain together at another’s expense. Conversely, a non-zero-sum game permits the total payoff to vary across outcomes, allowing shared gains, shared losses, or mixtures of cooperation and conflict. Competition alone therefore does not establish that an interaction is zero-sum; the condition must hold for the payoffs specified in the model. (people.csail.mit.edu)

References

Lecture 7: Zero-Sum Gameslearn.mit.edu
15-859(M): Randomized Algorithmscs.cmu.edu
Leveraging Symmetries in Strategic Gamescs.cmu.edu
853: Topics in Algorithmic Game Theory, Fall 2011people.csail.mit.edu
Lecture 12: February 13bpb-us-e1.wpmucdn.com
Table 1. Matching pennies and coordination matrix gamescs.cmu.edu
S890: Topics in Multiagent Learning, Lecture 3web.mit.edu
Zero-Sum Games and Linear Programming Dualityarxiv.org
Two-Person Gamesmat.tepper.cmu.edu
Non-zero-sum Game Theorycs.cmu.edu