Zero-sum game

In a two-player zero-sum game, one player’s payoff is the other player’s loss.

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.

A matrix game is a finite two-player zero-sum game whose entry $A_{ij}$ is the row player's payoff when the players choose row $i$ and column $j$.

When every entry of a payoff matrix $B$ is positive, its game value $v$ is positive. Setting $x=p/v$ converts the row player's probability vector and guaranteed value into the displayed linear program, whose optimum is $1/v$. Conversely normalizing a feasible $x$ gives a mixed strategy guaranteeing $1/(1^{T}x)$. The dual maximizes $1^{T}y$ under $By\le 1$, $y\ge 0$ and recovers the column strategy by normalization. Adding a constant to every payoff preserves Nash equilibria and lets this positive-payoff formulation handle general finite zero-sum games.

A payoff matrix records the row player's gains when row $i$ meets column $j$. In a zero-sum game the other player's payoff is the negative. For mixed strategies $p,q$, the expected row payoff is $p^{T}Aq$.

The row player solves

If the column player has an optimal strategy at value $v$ and a row probability vector $p$ satisfies $p^{T}A\ge v{e}^T$, then $p$ is optimal: it guarantees $v$, while the optimal column strategy prevents every row strategy from exceeding $v$.

If a symmetric invertible payoff matrix satisfies $A^{-1}e\ge 0$, both players may useand the game value is $(e^T{A}^{-1}e{)}^{-1}$.

Forboth players optimally choose cards $1,2,3$ with probabilities $41/50,2/25,1/10$, and the row player's expected payoff is $57/25$.

The finite minimax theorem equates the maximizing player’s security level with the minimizing player’s security level.

An optimal mixed strategy guarantees the value of the game against every opposing pure strategy.

A square game with antisymmetric payoff matrix has value zero.

In this game the higher of two chosen integers wins one unit if they are consecutive, but pays two units if their difference is at least two. Ties pay zero. For any choices $1,\dots ,n$ with $n\ge 3$, both players can optimally choose $1,2,3$ with probabilities $1/4,1/2,1/4$ and assign zero probability to larger numbers. If $p$ is this vector, $Ap$ is zero in its first three entries, $-5/4$ in its fourth when present, and $-2$ in all later entries. Thus $Ap\le 0$ and $p^{T}A\ge 0$, proving the zero value and both security guarantees.