Main Page Everything for Finite Math Everything for Applied Calc Everything Topic Summaries On Line Tutorials On Line Utilities               ← Previous Summary Next Summary → Tutorial for This Topic Textbook Lleveme a la Página Español Finite mathematics topic summary: game theory Tools: Matrix Algebra Tool | Pivot and Gauss-Jordan Tool | Game Theory Tool Subtopics: Two-Person Zero Sum Game | Mixed Strategy, Expected Value | Minimax Criterion, Fundamental Principles of Game Theory | Reducing by Dominance | Saddle Point, Strictly Determined Game

Two-Person Zero Sum Game

In a two-person zero sum game, each of the two players is given a choice between several prescribed moves at each turn, and each player's loss is equal to the other player's gain.

The payoff matrix of a two-person zero sum game has rows labeled by the "row player's" moves and columns labeled by the opposing "column player's" moves. The ij entry of the matrix is the payoff that accrues to the row player in the event that the row player uses move i and the column player uses move j.

Top of Page
Example

Paper, Scissors, Rock
Rock beats (crushes) scissors; scissors beat (cut) paper, and paper beats (wraps) rock.
Each +1 entry indicates a win for the row player, -1 indicates a loss, and 0 indicates a tie.

Do you want to play? Click on a row strategy...

 Column Player   Row Player  0 -1 1  1 0 -1 -1 1 0
Click on a row move.

Top of Page
Mixed Strategy, Expected Value

A player uses a pure strategy if he or she uses the same move at each round of the game. A mixed strategy is a method of playing a game where, at each round of the game, the player chooses a move at random so that each is used a predetermined fraction of the time.

We represent a mixed (or pure) strategy for the row player by a row matrix (probability vector)

R = [a   b   c  . . . ]
with the same number of entries as there are rows, where each entry represents the fraction of times the corresponding row is played (or the probability of using that strategy) and where a + b + . . . = 1.

A mixed strategy for the column player is represented by a similar column matrix C. For both row and column players, pure strategies is represented by vectors in with a single 1 and the rest zeros.

The expected value of the game with payoff matrix P corresponding to the mixed strategies R and C is given by

e = RPC
The expected value of the game is the average payoff per round if each player uses their mixed strategy for a large number of rounds.

Top of Page
Example

Here is a variant of "paper, scissors, rock in which "paper/paper" and "rock/rock" is no longer a draw.     2 -1 1  1 0 -1 -1 1 -2

Suppose the row player uses the mixed strategy

R = [0.75   0   0.25]
(play paper 75% of the time, scissors 0% of the time and rock 25% of the time) and the column player plays scissors and rock each 50% of the time;
 C = 0 0.5 0.5 .
Then the expected value of the game is
 e = RPC = [0.75   0   0.25] 2 -1 1  0 1 0 -1 0.5 -1 1 -2 0.5 = -0.125

Top of Page
Minimax Criterion, Fundamental Principles of Game Theory

Minimax Criterion
A player using the minimax criterion chooses a strategy that, among all possible strategies, minimizes the effect of the other player's best counter-strategy. That is, an optimal (best) strategy according to the minimax criterion is one that minimizes the maximum damage the opponent can cause.

Finding the minimax strategy is called solving the game. In the third part of the tutorial for this topic we show a graphical method for solving 2×2 games. For general games, one uses the simplex method (see the next topic summary). However, one can frequently simplify a game and sometimes solve it by "reducing by dominance" and/or checking whether it is "strictly determined" (see below).

Fundamental Principles of Game Theory When analyzing any game, we make the following assumptions about both players:

1. Each player makes the best possible move.
2. Each player knows that his or her opponent is also making the best possible move

Top of Page
Example

Consider the following game.

 Column Strategy A B C RowStrategy 1 0 -1 1 2 0 0 2 3 -1 -2 3

If the row player follows Principle 1, (s)he should never play Move 1 because Move 2 gives better payoffs no matter what move the column player chooses. (The payoffs in Row 2 are all at least as high as the corresponding ones in Row 1.)

Further, following Principle 2, the row player expects that the column player will never play Move A, since Move B gives better payoffs as far as the column player is concerned. (The payoffs in Column B are all at least as low as the corresponding ones in Column A.)

Top of Page
Reducing by Dominance

One move dominates another if all its payoffs are at least as advantageous to the player than the corresponding ones in the other move. In terms of the payoff matrix, we can say it this way:

1. Row r in the payoff matrix dominates row s if each payoff in row r is ≥ the corresponding payoff in row s.
2. Column r in the payoff matrix dominates column s if each payoff in row r is ≤ the corresponding payoff in column s.
Note that if two rows or columns are equal, then each dominates the other. A row or column strictly dominates another if the one dominates the other and they are not equal.

Following the first principle of game theory, the move corresponding to a strictly dominated row or column will never be played, and both players are aware of this by the second principle. Thus each player following the principles of game theory will repeatedly eliminate dominated rows and columns as the case may be. (If two rows or columns are equal, then there is no reason to choose one over the other, so either may be eliminated.) This process is called reduction by dominance.

Top of Page
Example

Consider the above game once again.

 Column Strategy A B C RowStrategy 1 0 -1 1 2 0 0 2 3 -1 -2 3

Since the entries in Row 2 are ≥ the corresponding ones in Row 1, Row 2 dominates Row 1.

Since the entries in Column B are ≤ the corresponding ones in Column A, Column B dominates Column A.

Reducing the Above Game by Dominance

Since Row 2 dominates Row 1 we eliminate Row 1 to obtain

 A B C 2 0 0 2 3 -1 -2 3

Since Column B now dominates both Columns A and C we eliminate both Columns A and C to obtain

 B 2 0 3 -2

Since the top row now dominates the bottom row, we eliminate the bottom row, and we are reduced to the following 1×1 matrix

 B 2 ( 0 )

In this case, we have solved the game by reduction by dominance: The row player should always play 2 and the column player should always play B. Since the corresponding payoff is 0, we say that the game is fair (neither player has an advantage over the other).

Note that we were lucky here: Not all games can be reduced by dominance to a 1×1 game.

Top of Page

A saddle point is a payoff that is simultaneously a row minimum and a column maximum. To locate saddle points, circle the row minima and box the column maxima. The saddle points are those entries that are both circled and boxed.

A game is strictly determined if it has at least one saddle point. The following statements are true about strictly determined games.

1. All saddle points in a game have the same payoff value.
2. Choosing the row and column through any saddle point gives minimax strategies for both players. In other words, the game is solved via the use of these (pure) strategies.

The value of a strictly determined game is the value of the saddle point entry. A fair game has value of zero, otherwise it is unfair or biased.

Top of Page
Example

In the above game, there are two saddle points, shown in color.

 A B C 1 0 -1 1 2 0 0 2 3 -1 -2 3

Since the saddle point entries are zero, this is a fair game.

The on-line game theory utility can be used to check any game (up to 5×5) for saddle points. Try it out.

Top of Page
Last Updated: July 2007