Skip to content

Zero-Sum Games

This article discusses (two-player) zero-sum games.

In zero-sum games, the sum of the two players' payoffs is always zero; one player's gain necessarily implies the other's loss. Zero-sum games can be viewed as a special case of constant-sum games. However, any constant-sum game can be equivalently transformed into a zero-sum game by adding or subtracting a constant from one player's payoff, so it suffices to discuss zero-sum games.

Zero-sum games commonly encountered in algorithm competitions can be roughly divided into two categories: sequential zero-sum games and simultaneous zero-sum games.

Sequential Zero-Sum Games

In sequential zero-sum games, two players take turns making moves until the game ends.

In sequential zero-sum games, the players' payoff functions exhibit a recursive structure. The game state \(S\) can be divided into three types: terminal states \(S_0\), states where player 1 moves \(S_1\), and states where player 2 moves \(S_2\). Assume that at a terminal state \(s\in S_0\), player 1's payoff is \(v(s)\), and correspondingly, player 2's payoff is \(-v(s)\). Therefore, when it is player 2's turn, maximizing its payoff is equivalent to minimizing player 1's payoff. Thus, assuming both players adopt optimal strategies, the maximum payoff \(V(s)\) that player 1 can obtain at state \(s\in S\) satisfies the following recurrence:

\[ V(s) = \begin{cases} v(s), & s \in S_0,\\ \max_{t\in s} V(t), & s\in S_1,\\ \min_{t\in s} V(t), & s\in S_2. \end{cases} \]

Here, \(t\in s\) denotes that \(t\) is a successor state of \(s\). This is the minimax principle.

Applying this algorithm to practical problems, the following specific methods are commonly used:

  • If the number of game states involved is small, directly implement this algorithm via brute force.

  • If the number of game states is large and lacks special structure, consider Alpha–Beta pruning combined with other search pruning algorithms.

  • If a single game state is often a successor of multiple states, to avoid repeated searches, consider memoized search or other dynamic programming algorithms.

  • If the player's final payoff is the sum of payoffs from all actions before the terminal state, the modeling approach can be appropriately optimized. Specifically, suppose that upon reaching terminal state \(s\in S_0\), the action sequences of players \(i=1,2\) are \(\{a^{(i)}_j\}_{j=1}^{k_i}\) respectively, the payoff corresponding to action \(a\) is \(w(a)\), and player 1's payoff function is

    \[ v(s) = \sum_{j=1}^{k_1}w(a_j^{(1)}) - \sum_{j=1}^{k_2}w(a_j^{(2)}). \]

    Then, we can define \(\tilde V(s)\) as the maximum score the current player can achieve in the game after state \(s\in S\). For the initial state \(s_0\), we have \(V(s_0)=\tilde V(s_0)\), so computing \(\tilde V(\cdot)\) is sufficient to solve the original problem. For \(\tilde V(\cdot)\), the following recurrence holds:

    \[ \tilde V(s) = \begin{cases} 0, & s \in S_0, \\ \max_{t\in s} w(a_{s\to t}) - \tilde V(t), & s\in S_1\cup S_2. \end{cases} \]

    Here, \(a_{s\to t}\) denotes the action that can transition the state from \(s\) to \(t\). If there are multiple such actions, take the one with the highest payoff \(w(a)\).

  • Impartial combinatorial games are all sequential zero-sum games; simply set the payoffs of the winning and losing sides as \(+1\) and \(-1\) respectively. In this case, the recurrence for the payoff function \(V(\cdot)\) is precisely the lemma for determining winning and losing states.

    A common variant of such problems is to find the minimum number of rounds needed for the winning side and the maximum number of rounds the losing side can endure. For this, simply note that when performing BFS starting from terminal states and determining winning/losing states according to the lemma, recording the round number at which each state is determined as winning or losing gives the desired number of rounds. This is because a state is determined as winning as long as one successor is losing, and it always transitions from the losing successor with the smallest round number; a state is determined as losing only when all successors are winning, and it always transitions from the winning successor with the largest round number.

    This method can also be generalized to general directed graph games.

Example

Codeforces 794 E. Choosing Carrot

Let there be a sequence \({a_i}\) of length \(n\). Two players, 1 and 2, take turns removing a number from either end of the sequence until only one number remains. Player 1 aims to maximize this last remaining number, while player 2 aims to minimize it. Before the game officially starts, player 1 can additionally make \(k\) moves first. Assume both players adopt optimal strategies throughout the entire process. For each \(k = 0,1,2,\cdots,n-1\), determine the final remaining number at the end of the game. Here, \(1 \le n \le 3\times 10^5\).

Solution

Because regardless of how numbers are removed, the remaining part of the sequence is always a contiguous interval. Therefore, a game state can be described solely by the interval \([l,r]\) and the current player \(i=1,2\) to move, and a dynamic programming algorithm can be used to solve it. Let \(f(l,r,i)\) be the final remaining number when the state is described by \((l,r,i)\). From the previous analysis, when \(l < r\), this function satisfies the state transition equations:

\[ \begin{aligned} f(l,r,1) &= \max\{f(l+1,r,2),f(l,r-1,2)\},\\ f(l,r,2) &= \min\{f(l+1,r,1),f(l,r-1,1)\}. \end{aligned} \]

The terminal condition is \(f(l,l,1)=f(l,l,2) = a_l\). Based on this, the function values for all possible states can be computed in \(\Theta(n^2)\) time. For each \(k\), the answer is

\[ g(k) = \max f(l,r,1) \text{ subject to } r - l + 1 = k. \]

This algorithm cannot pass the data range set by the original problem, so optimization of the transition is needed. There are many ways to handle this; this article only provides one.

View the state transition equations as operations on the entire sequence. The two transition equations represent taking the maximum and minimum of adjacent numbers to obtain a new sequence, referred to as "maximization operation" and "minimization operation" respectively. Each operation reduces the sequence length by one. All intervals of length \(d\) correspond to \((n-d+1)\) results, which is equivalent to the sequence obtained after performing \((d-1)\) operations on the sequence. Additionally, to obtain the result for \(f(l,r,1)\), the last operation must be a maximization operation. Therefore, these operation sequences always end with a maximization operation.

Consider the effect of two consecutive operations on the sequence. Consider first performing a minimization operation, then a maximization operation. In this case, the sequence \(a_1,a_2,a_3\) becomes

\[ \max\{\min\{a_1,a_2\},\min\{a_2,a_3\}\}. \]

Enumerating all possible size relations among \(a_1,a_2,a_3\) shows that, except when \(a_1 < a_2\) and \(a_2 > a_3\) (i.e., \(a_2\) is a strict local maximum), this expression always equals \(a_2\). That is, if a sequence has no strict local maximum points, then the only effect of two consecutive operations is to remove one number from each end of the sequence. This obviously greatly simplifies the transition. The only remaining problem is: how to ensure the sequence has no strict local maximum points? In fact, performing one maximization operation on the sequence guarantees no strict local maximum points. Therefore, all results after an even number of operations can be obtained by performing two operations on the initial sequence and then repeatedly removing numbers from both ends; all results after an odd number of operations can be obtained by performing one operation on the initial sequence and then repeatedly removing numbers from both ends.

Since at most \(3\) full operations on the sequence are needed, and subsequent answer computation only requires \(2\) traversals, the total time complexity of this algorithm is \(\Theta(n)\).

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int& x : a) std::cin >> x;
  std::vector<int> ans(n), tmp;
  tmp = a;
  for (int i = 0; i < n - 1; ++i) {
    tmp[i] = std::max(tmp[i], tmp[i + 1]);
  }
  for (int l = n / 2 - 1, r = (n - 1) / 2, ma = 0; l >= 0; --l, ++r) {
    ma = std::max({ma, tmp[l], tmp[r]});
    ans[r - l] = ma;
  }
  tmp = a;
  for (int i = 0; i < n - 1; ++i) {
    tmp[i] = std::min(tmp[i], tmp[i + 1]);
  }
  for (int i = 0; i < n - 2; ++i) {
    tmp[i] = std::max(tmp[i], tmp[i + 1]);
  }
  for (int l = (n - 3) / 2, r = n / 2 - 1, ma = 0; l >= 0; --l, ++r) {
    ma = std::max({ma, tmp[l], tmp[r]});
    ans[r - l] = ma;
  }
  ans[n - 1] = *std::max_element(a.begin(), a.end());
  for (auto x : ans) std::cout << x << ' ';
  std::cout << std::endl;
  return 0;
}

Exercises

Simultaneous Zero-Sum Games

In simultaneous zero-sum games, two players act at the same time.

Simultaneous zero-sum games are usually represented by a payoff matrix. Suppose player \(i=1,2\) has an action set \(A_i\), and when players \(i=1,2\) take actions \(a_i\in A_i\) respectively, their payoffs are \(v(a_1,a_2)\) and \(-v(a_1,a_2)\).

Example

Consider the Rock-Paper-Scissors game. Assume winning scores \(1\), losing scores \(-1\), and a draw scores \(0\). Then, the players' payoffs can be represented as

\[ \begin{pmatrix} 0,0 & 1,-1 & -1,1 \\ -1,1 & 0,0 & 1,-1 \\ 1,-1 & -1,1 & 0,0 \end{pmatrix}. \]

General two-player simultaneous games can also be represented in a similar form, hence also called bimatrix games. For zero-sum games, since player 1's payoff matrix and player 2's payoff matrix are opposites, we can consider only player 1's payoff matrix:

\[ V = (v(a_1,a_2))_{(a_1,a_2)\in A_1\times A_2} = \begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}. \]

The problem to solve is: given the payoff matrix \(V = (v(a_1,a_2))_{(a_1,a_2)\in A_1\times A_2}\), how to determine the optimal strategies and maximum payoffs for both players?

Mixed Strategies

Compared to sequential zero-sum games, the roles of the two players in simultaneous games are symmetric. However, since sequential zero-sum games have been solved, consider the sequential version of simultaneous games. For example, if we assume player 1 moves first, then player 2 moves, then, according to the previous discussion, player 1's payoff at the end of the game will be given by

\[ w_-=\max_{a_1\in A_1}\min_{a_2\in A_2} v(a_1,a_2) \]

Since player 1's action is transparent to player 2, this should be the worst outcome player 1 can obtain. Symmetrically, if we assume player 2 moves first, then player 1's payoff will be given by

\[ w_+ = \min_{a_2\in A_2}\max_{a_1\in A_1} v(a_1,a_2) \]

Since player 2's action is transparent to player 1, this should be the best outcome player 1 can obtain. Player 1 should expect that in actual play, the obtainable payoff \(w\in[w_-,w_+]\). Although the inequality \(w_-\le w_+\) always holds (proof see Weak Duality Theorem), because equality may not hold, using only the analytical tools of sequential games generally cannot uniquely determine the game outcome.

Example (continued)

In Rock-Paper-Scissors, if moves are sequential, then the first mover always loses, and the second mover always wins. In mathematical terms, this is the inequality:

\[ w_- = -1 \le +1 = w_+. \]

Here, \(w_-\neq w_+\) does not hold.

The above analysis misses a key factor of simultaneous games: players cannot accurately predict their opponent's actions. Formally, this means both sides can adopt some random strategy. This idea does not hold in the context of sequential games because no matter how the first player randomly chooses an action, the second player can always accurately observe this action and respond accordingly. However, for simultaneous games, the strategic ambiguity introduced by random strategies prevents opponents from effectively countering one's own actions.

Example (continued)

In Rock-Paper-Scissors, if player 1 uniformly randomly chooses one of scissors, rock, or paper, then, depending on player 2's action, player 1's possible payoff is

\[ \dfrac{1}{3}(0,1,-1)^T + \dfrac{1}{3}(-1,0,1)^T + \dfrac{1}{3}(1,-1,0)^T = (0,0,0)^T. \]

Now, regardless of how player 2 chooses an action, player 1's expected payoff is always \(0\). This is clearly better than deterministically choosing a single action.

Thus, the concept of mixed strategies is introduced.

Mixed Strategy

In simultaneous games, a mixed strategy (or simply strategy) for player \(i\) is a function \(s_i:A_i\to[0,1]\) satisfying \(\sum_{a_i\in A_i}s_i(a_i)=1\). That is, strategy \(s_i\) is a probability distribution over player \(i\)'s action set \(A_i\). The set of all mixed strategies for player \(i\) is denoted \(S_i=\Delta(A_i)\), where \(\Delta(A_i)\) denotes the set of all probability distributions over \(A_i\). If \(s_i\) is a degenerate probability distribution, i.e., there exists \(a\in A_i\) such that \(s_i(a)=1\), then strategy \(s_i\) is also called a pure strategy.

The payoff of mixed strategies is the expectation of individual action payoffs:

\[ v(s_1,s_2) = \sum_{a_1\in A_1}\sum_{a_2\in A_2}s_1(a_1)s_2(a_2)v(a_1,a_2). \]

Treating individual actions as corresponding pure strategies, we can embed the action set \(A_i\) into the (mixed) strategy set \(S_i\), and the \(v(s_1,s_2)\) defined above can be seen as extending \(v(a_1,a_2)\) from \(A_1\times A_2\) to \(S_1\times S_2\).

von Neumann's Theorem

With mixed strategies introduced, the results of maximin and minimax thinking coincide, and thus the outcome of simultaneous zero-sum games is uniquely determined.

Theorem (von Neumann)

In simultaneous zero-sum games allowing mixed strategies, if both players adopt optimal strategies, then player 1's maximum payoff is

\[ w = \max_{s_1\in S_1}\min_{s_2\in S_2} v(s_1,s_2) = \min_{s_2\in S_2}\max_{s_1\in S_1} v(s_1,s_2), \]

and player 2's maximum payoff is \(-w\).

Proof

Let \(w = \max_{s_1\in S_1}\min_{s_2\in S_2} v(s_1,s_2)\). Consider the inner minimization problem. Since \(v(s_1,s_2)=\sum_{a_2\in A_2}s_2(a_2)v(s_1,a_2)\), we have \(\max_{s_2\in S_2}v(s_1,s_2)=\max_{a_2\in A_2}v(s_1,a_2)\), and the optimal solution of the former is the pure strategy corresponding to the optimal solution of the latter. Therefore, \(w = \max_{s_1\in S_1}\min_{a_2\in A_2} v(s_1,a_2)\). Then, introducing an auxiliary variable \(u\), the problem can be rewritten as

\[ w = \max_{s_1\in S_1} u \text{ subject to }u \le \min_{a_2\in A_2} v(s_1,a_2). \]

Because this constraint is equivalent to \(u\le v(s_1,a_2)\) holding for all \(a_2\in A_2\). Finally, incorporating the definition of mixed strategy \(s_1\) and the expression for payoff function \(v(s_1,a_2)\), the original problem is equivalent to the linear programming problem

\[ (P) \qquad \begin{aligned} w = \max_{u,s_1}\; & u\\ \text{subject to }& \sum_{a_1\in A_1}s_1(a_1)v(a_1,a_2) \ge u,~\forall a_2\in A_2,\\ & \sum_{a_1\in A_1}s_1(a_1) = 1,\\ & s_1(a_1) \ge 0,~\forall a_1\in A_1. \end{aligned} \]

This problem is clearly feasible, and its optimal solution exists. According to the Duality Principle, its optimal value equals the optimal value of its dual problem:

\[ (D) \qquad \begin{aligned} w = \min_{t,s_2}\; & t\\ \text{subject to }&\sum_{a_2\in A_2}s_2(a_2)v(a_1,a_2) \le t,~\forall a_1\in A_1,\\ &\sum_{a_2\in A_2}s_2(a_2) = 1,\\ &s_2(a_2)\ge 0,~\forall a_2\in A_2. \end{aligned} \]

Repeating the previous steps, this problem is equivalent to \(\min_{s_2\in A_2}\min_{s_1\in S_1}v(s_1,s_2)\). The theorem is proved.

This result is precisely the Nash equilibrium of this game. That is, assuming both players choose the optimal strategies in the equilibrium, no player can strictly benefit from deviating from the equilibrium strategy.

Transformation into Linear Programming

The proof of von Neumann's theorem also indicates a method for solving simultaneous zero-sum games. Let \(n\) and \(m\) be the numbers of actions available to players 1 and 2 respectively. Given player 1's payoff matrix \(V\in\mathbf R^{n\times m}\), we can solve the following linear programming problem:

\[ \begin{aligned} w = \max_{(u,s)\in\mathbf R\times\mathbf R^n}\; & u\\ \text{subject to }& V^Ts \ge u\mathbf 1,\\ & \mathbf 1^Ts = 1,\\ & s \ge 0. \end{aligned} \]

This is a linear programming problem of size \(\Theta(n+m)\), which can be efficiently solved by the simplex method. The optimal solution \(s\) obtained by the algorithm is player 1's optimal (mixed) strategy. To obtain player 2's optimal strategy, simply retrieve the dual variables (i.e., shadow prices) of the optimal solution from the simplex tableau.

Exercises

References and Notes

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用