Monday, May 28, 2012

What is a solution to a zero-sum game?

What is a solution to a zero-sum game?

In a two-person zero-sum game, the payoff to one player is the negative of that going to the other. Although zero-sum games are not terribly interesting to economists, who typically study situations where there are gains to trade, most common parlor games such as poker and chess are zero sum: one player wins, one loses. According to Von-Neumann's theory, every zero sum game has a value. Each player can guarantee himself this value against any play of his opponent, and can prevent the other player from doing any better than this. We typically write a zero-sum game by forming a matrix and allowing one player to choose the rows and the other the columns. The entries in the matrix are the payoffs to the row player. For example in the game of matching pennies, we can write the payoff matrix
1 -1
-1 1
so that the row player is trying to match the column player and the column player is trying to guess the opposite of the row player. The value of the game may be calculated as either the minimum of what the row player can achieve knowing the strategy of the column player (the minmax for the row player) or the maximum of what the column player can hold the row player to, knowing the strategy of the row player (the maxmin for the row player). Von Neumann's famous minmax theorem shows that these two quantities are the same.
It is possible to solve a zero-sum game using the simplex algorithm or any other algorithm that can solve a linear programming problem. This is implemented below. To solve a zero sum game, fill in the payoffs to the row player in the blank area below separated by commas. Do not enter blank lines. The program will then find the strategy for the column player that holds the row player's payoff to a minimum. For example in the game of matching pennies:

1, -1
-1, 1

Enter the payoffs to the row player:


The program finds the column player strategy that holds the row player's payoff to a minimum, and reports the value of the game to the row player.
If you have questions about the program or about zero-sum games, you should check out discussion on the forum.

No comments:

Post a Comment