A zero-sum game is a game in which a player's payoff implies the loss of another player. There is a payoff a matrix A∈Rn×mA \in \mathbb{R}^{n \times m}. One player chooses from rows {1,2,...,n}\{1, 2, ..., n\} and the other chooses from columns {1,2,...,m}\{1, 2, ..., m\}. The former is called the row player and the later is called the column player. The entry aija_{ij} of AA is the payoff when the row player chooses ii and the column player chooses jj. In such case the column player loses aija_{ij}.

If one player makes a choice first and the other play follows, then the second player can always respond according the first player choice, to maximize its payoff or minimize its loss.

To make the game more fair, suppose that there are two huge black boxes. We require the row player to go into one black box, and write down her choice ii on a note, and then leave the black box. We require the column player to do the same in another black box. Suppose the row player chooses his row index according to some distribution x∈Rnx \in \mathbb{R}^n, and the column player chooses according to distribution y∈Rmy \in \mathbb{R}^m. The xx and yy are called strategies and the expected payoff is (for the row player) is

xTAy. x^T A y.

What is one player knows the other's strategy? In this scenario, the row player choose its strategy xx first and the column player responds by a strategy yy, or vise versa. Obvious, the strategy of the player who plays first can not be deterministic, i.e., have probability 11 on one index and 00 on others.

The question is, whether the order of choosing a strategy results in different expected payoff.

First we write down what the expected payoff is. If the row player commit to a strategy xx first, the column player will choose a distribution yy minimize it expected loss:

min⁡yxTAy. \min_y x^T A y.

As xx is known, this is equivalent to choosing the column with minimum value:

min⁡j∈[m]xTAej. \min_{j \in [m]} x^T A e_j.

Understanding the expected behavior of the column player, the row player should choose a strategy xx, such that in the worst case, its expected payoff is maximized:

max⁡x(min⁡yxTAy)=max⁡x(min⁡j∈[m]xTAej). \max_{x} (\min_y x^T A y) = \max_{x} (\min_{j \in [m]} x^T A e_j).

Similarly, if the column player play first, the expected payoff is

min⁡y(max⁡xxTAy)=min⁡y(max⁡i∈[n]eiTAy). \min_y (\max_{x} x^T A y) = \min_{y} (\max_{i \in [n]} e_i^T A y).

The minimax-theorem states that

max⁡x(min⁡yxTAy)=min⁡y(max⁡xxTAy). \begin{aligned} \max_{x} (\min_y x^T A y) = &\min_y (\max_{x} x^T A y). \end{aligned}

The proof is not difficult -- by formulating the two optimizing problems as linear programming, and observing that they are dual to each other. If the row player goes first,

max⁡vv−∑i=1naijxi≤0 ,∀j∈[m]∑i=1nxi=1xi≥0 ,∀i∈[n] \begin{array}{lr} \max v \\ v - \sum_{i = 1}^n a_{ij} x_i \le 0 \,, & \forall j \in [m] \\ \sum_{i = 1}^n x_i = 1 \\ x_i \ge 0 \,, & \forall i \in [n] \end{array}

The first constraint just says that vv should be smaller than each column of xTAx^T A.

To upper bound vv, we introduce a variable u∈Ru \in \mathbb{R} (that is associated with constraint ∑i=1nxi=1\sum_{i = 1}^n x_i = 1). Then

u=u(∑i=1nxi)≥u(∑i=1nxi)+∑j=1myj(v−∑i=1naijxi)=v(∑j=1myj)+∑i=1nxi(u−∑j=1maijyj)=v+∑i=1nxi(u−∑j=1maijyj) \begin{array}{ll} u &= u \left( \sum_{i = 1}^n x_i \right) \\ &\ge u \left( \sum_{i = 1}^n x_i \right) + \sum_{j = 1}^m y_j \left( v - \sum_{i = 1}^n a_{ij} x_i \right) \\ &= v \left( \sum_{j = 1}^m y_j \right) + \sum_{i = 1}^n x_i \left( u - \sum_{j = 1}^m a_{ij} y_j \right) \\ &= v + \sum_{i = 1}^n x_i \left( u - \sum_{j = 1}^m a_{ij} y_j \right) \\ \end{array}

The first equality follows from that ∑i=1nxi=1\sum_{i = 1}^n x_i = 1. The second inequality follows from that yj≥0y_j \ge 0 and v−∑i=1naijxi≤0v - \sum_{i = 1}^n a_{ij} x_i \le 0. The last equality follows from that ∑j=1myj=1\sum_{j = 1}^m y_j = 1.

If it holds that u−∑j=1maijyj≥0u - \sum_{j = 1}^m a_{ij} y_j \ge 0 for all i∈[n]i \in [n], as xi≥0x_i \ge 0, then uu is an upper bound of vv:

u≥v+∑i=1nxi(u−∑j=1maijyj)≥v. \begin{array}{ll} u \ge v + \sum_{i = 1}^n x_i \left( u - \sum_{j = 1}^m a_{ij} y_j \right) \ge v. \end{array}

Minimizing uu gives the following linear program:

min⁡uu−∑j=1maijyj≥0 ,∀i∈[n]∑i=1myj=1yj≥0 ,∀j∈[m] \begin{array}{lr} \min u \\ u - \sum_{j = 1}^m a_{ij} y_j \ge 0 \,, & \forall i \in [n] \\ \sum_{i = 1}^m y_j = 1 \\ y_j \ge 0 \,, & \forall j \in [m] \end{array}

Observe this is exactly min⁡ymax⁡xxTAy\min_y \max_x x^T A y. Further, by strong duality, we know that the optimal values of the two program are equal.