[Math Lair] Zero-Sum Games

Math Lair Home > Topics > Zero-Sum Games

A zero-sum game is a type of game in game theory, where one player's loss is always equal to the other player's gain. Many things that we refer to in everyday language as "games" are zero-sum games. As an example, if you play a game of chess, or football, or baseball, one person or side will win (+1) and the other will lose (−1); in some games it is possible for the two sides to draw (0). Or, if you play poker for money with a friend, or make a bet with a friend, every dollar that you win is a dollar that he loses and vice versa. In general, scenarios where two parties are competing for a fixed amount of a resource (wins, money, etc.) are good candidates to be modelled with a zero-sum game.

Most real-life scenarios that game theory deals with are non-zero-sum games, where options may be mutually beneficial or mutually destructive, or where one player's gain is not equal to another player's loss. As an example, if management and labour are at the bargaining table, some courses of action may help both sides, or help one side more than they hurt the other. Prisoner's Dilemma is another example of a non-zero-sum game.

A zero-sum game always has a solution. There are four scenarios to consider:

  1. Both players have a dominating strategy
  2. Only one player has a dominating strategy
  3. Neither player has a dominating strategy, but there is a saddle point
  4. Neither player has a dominating strategy, and there is no saddle point.

The first and easiest case to consider is where both players have a dominating strategy. A dominating strategy is a strategy that always results in the greatest gain regardless of what option the other player chooses. In this case, both players will always choose their dominating strategy. As an example, consider the following payoff matrix:
A1 4, −4 −1, 1 3, −3
A2 0, 0 −2, 2 2, −2
A3 0, 0 −3, 3 1, −1

Looking at the payoff matrix, no matter what player B chooses, A can maximize his gain by selecting strategy A1. Similarly, no matter what A chooses, B maximizes his gain by selecting strategy B2. So, A will always select A1 and B will always select B2, with the result that A gets −1 and B gets 1. Neither side can do better.

The second case is where only one player has a dominating strategy. That player should always select the dominating strategy; the other player should always select whichever strategy provides the best results against the first player's dominating strategy. Consider the following payoff matrix, which is the same as the above except for one square:
A14, −4 −1, 1 3, −3
A2−3, 3 −2, 2 2, −2
A30, 0 −3, 3 1, −1

As in the above example, A has a dominating strategy: Strategy A1 dominates A2 and A3. However B does not have a dominating strategy: Strategy B2 does best against A1 and A3, but strategy B1 does best against A2. However, since B knows that A will always select his dominant strategy A1, he should always select B2, with the result that A gets −1 and B gets 1.

The third scenario is where neither player has a dominating strategy, but there is a saddle point. The following example will illustrate what a saddle point is:
A1+5, −5−1, +1+4, −4
A2−3, +3−2, +25, −5
A3+10, −10−3, +3−20, +20

You can see here that neither player has a dominating strategy. Here, both players have to take into account the other's decision-making process. One way to go about it is to find the best of the worst possible outcomes. For A, the safest choice would be to choose A1, since the worst that could happen is that A scores −1 (if B chooses B2). If A chooses strategy A2, he could score −3, and with strategy A3 he could score −20.

By choosing strategy A1, A has minimized the maximum loss; such a strategy is called a minimax strategy. You could also look at it as maximizing the minimum gain, in which case you would refer to it as a maximin strategy; in game theory, both terms refer to the same strategy.

Now, if B knew that A was going to select strategy A1, then his best strategy would be strategy B2.

Performing the same analysis for B, the strategy that minimizes the maximum loss is B2.

Now, if A knew that B was going to select B2, A would select strategy A1.

If there is an outcome in which the payoffs to both players are the "best of the worst," this outcome is called a saddle point or a minimax. In this game, if A chooses A1 and B chooses B2, both payoffs meet this criterion. Such a choice of strategies would be the best for both players. Neither player can do better unless the other player acts irrationally.

The last scenario to consider is where neither player has a dominating strategy and there is no saddle point. Let's consider a different example this time:
A12, −2−1, 1
A2−5, 53, −3

A's minimax is −1, in the upper right corner, while B's minimax is −2, in the upper left corner. Now, A's thought process might go like this: He might decide to select A1, since the worst payoff is −1. So, if B is able to figure out that A will select A1, then B would select B2. But if B selects B2, then it would be best for A to select A2, to gain 3 points. But if A is going to select A2, then it would be best for B to select B1 to get 5 points. In which case it would be best for A to select A1... Trying to find a single option results in going around in a circle.

How do you break the endless cycle? As it turns out, the way that both players can get the best possible results for themselves is through a mixed strategy, by randomizing their choices. In this case, if A selects strategy A1 811 of the time, then he will get an average payoff of at least 111. B can ensure that A's average payoff is no more than 111 by selecting strategy B1 411 of the time.