Goodies

	Matrix Algebra Tool			Game Theory Tool
	Extensive Reading on Game Theory in Wikipedia

First, here are some basic definitions.

Two-Person Zero-Sum Game A two-person zero-sum game is a game with two players (Player A and Player B) such that: One player's loss equals the other's gain ("zero sum"). The outcome of the game is determined by each player's choice from among a fixed, finite set of moves. (The possible moves may be different for the two players.) . The outcome of the game is a score,called the payoff. A positive payoff indicates a win for Player A, a negative payoff indicates a win for Player B, and zero indicates a draw. . If Player A has m moves to choose from and Player B has n, we can represent the game using a payoff matrix, the m × n matrix showing the payoff resulting from each possible pair of choices of moves. In the payoff matrix, Player A's strategies, or moves, are listed on the left, while Player B's strategies are listed on top. We think of Player A as the row player and playe B as the column player. Example: Paper, Scissors, Rock Each player has the same three moves: paper, scissors, and 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? You are Player A and I am Player B. Click on a row move... Player B Player A 0 -1 1 1 0 -1 -1 1 0 Click on a row move. More Terms: In each round of the game, the way a player chooses a move is called a strategy. A player using a pure strategy makes the same move each round of the game. For example, if a player in the above game chooses to play scissors (s) at each turn, then that player is using the pure strategy s. A player using a mixed strategy chooses each move a certain percentage of the time in a random fashion; for instance, Player A might choose to play p 50% of the time, and each of s and r 25% of the time. When a player uses a mixed strategy we represent it by a row matrix (for the row player) or a column matrix (for the column player). Example If, in the above game, the row player (Player A) uses p 50% of the time, and each of s and r 25% of the time, then the row player mixed stratgegy is written as R = [0.50     0.25     0.25] If, on the other hand, the column player (Player B) uses p 20% of the time, s 50% of the time, and r 30% of the time, then the column player mixed stratgegy is written as C = 0.20 0.50 0.30

You are the head coach of the Alphas (Team A), and are attempting to come up with a strategy to deal with your rivals, the Betas (Team B). Team A is on offense, and Team B is on defense. You have five preferred plays, but are not sure which to select. You know, however, that Team B usually employs one of three defensive plays. Over the years, you have diligently recorded the yardage gained by your team for each combination of plays used, and have come up with the following table.

			Team B:
			1	2	3
	1		0	-1	5
	2		7	5	10
Team A:	3		15	-4	-5
	4		5	0	10
	5		-5	-10	10

Q If you play offence #2 and Team B plays defence #3, you can expect to:

	gain 10 yards			lose 4 yards
	gain 5 yards			lose 5 yards

Q You have decided to use a mixed strategy that uses offence #1 and #3 each 30% of the time, and offence #5 the rest of the time. The matrix form of the corresponding mixed strategy is:

	R = [30     0     30     0     40]			C = 30 0 30 0 60
	C = 0.30 0 0.30 0 0.60			R = [0.30     0     0.30     0     0.40]

Q Unbeknownst to you, the Team B coach is using a mixed strategy that uses defense #1 and #2 each 20% of the time. The matrix form of the corresponding mixed strategy is:

	R = [0.20     0.20     0]			C = 0.20 0.20 0
	C = 0.20 0.20 0.60			R = [0.20     0     0.20     0.60]

Q Suppose, both coaches play the mixed strategies in the above example. How many yards will be gained by offence each play?
A That depends on what specific choice each coach makes at each play. A better question to ask is: On average, how many yards will be gained by the offence each play? This quantity (average number of points gained by the row player) is called the expected value of the game and the method of calculation is shown below:

Recall that the payoff matrix for paper, scissors, rock is   P

=

0     -1     1   1 0 -1 -1 1 0

Q You are a non-violent person and so have an aversion to "rock", which you tend to play only 20% of the time. You play the other two options equally often the rest of the time. Your opponent, on the other hand, has an even stronger aversion to "scissors" (the result of an unfortunate experience at the barber as a child) and so never plays scissors, but plays the other two options 50% of the time. The row- and column mixed strategies are (Remember that the order of the moves we are using is paper, scissors and then rock):

R =

C =

Q If the two of you continue to use the mixed strategies described above, the expected vale of the game is

	0.1			0.35			-0.1
	Undefined			0

Q This means that

	You will lose 0.1 points each round of the game.
	You will win 0.1 points each round of the game.
	You will lose an average of 0.1 points each round of the game.
	You will win an average of 0.1 points each round of the game.
	The payoff indicates that the game is not defined.

In the above discussion, we assumed that both players' mixed strategy was known. What if only one of the strategies is known? Let us go back to the football scenario. Here it is again:

You are the head coach of the Alphas (Team A), and are attempting to come up with a strategy to deal with your rivals, the Betas (Team B). Team A is on offense, and Team B is on defense. The payoffs are given by the following table:

			Team B:
			1	2	3
	1		0	-1	5
	2		7	5	10
Team A:	3		15	-4	-5
	4		5	0	10
	5		-5	-10	10

Q As a result of having observed the Team B coach for many years, you know that he tends to use defense #1 and 2 each 20% of the time, and defense #3 60% of the time. Which of your five possible offences should you play?

A This time, you know beforehand that the Team B strategy is C =

0.20 0.20 0.60

.

Since you do not know what your own strategy should be, take its entries to be unknowns. That is, use the following strategy:

R = [x     y     z     u     v]

P =

0 -1 5   7     5     10   15 -4 -5 5 0 10 -5 -10 10

,

R = [x     y     z     u     v],

C = 0.20 0.20 0.60

e	=	RPC
	=	[x     y     z     u     v] 0 -1 5   7     5     10   15 -4 -5 5 0 10 -5 -10 10 0.20 0.20 0.60
	=	[x     y     z     u     v] 2.8 8.4 -0.8 7 3 We first calculated PC thinking of the product as R(PC). The reason for this choice is that P and C have no letters in them. (It is often easier to first multiply the matrices that contain no letters.)
	=	[2.8x + 8.4y - 0.8z + 7u + 3v]

2.8x + 8.4y - 0.8z + 7u + 3v

x = 0, y = 1, z = 0, u = 0, v = 0

2.8(0) + 8.4(1) - 0.8(0) + 7(0) + 3(0) = 8.4

As y = 1 and all the other values are zero, the best row strategy is

[x     y     z     u     v] = [0     1     0     0     0]

Now here is one for you to do, where, this time, you must calculate the best strategy from the column player's point of view, given a knowledge of the row strategy.

You (the row player as usual) are playing paper, scissors, rock against a very observant opponent. Although you think you are playing purely at random, your opponent has noticed that you tend to play paper 25% of the time, scissors 35% of the time, and rock 40% of the time.

Q In order to compute the best counter-strategy for the column player, we set up R and C as follows [Use x, y, z for entries of any strategy that is currently unknown]:

R =

C =

Q Using these strategies, the value of the game is [Use graphing calculator input for formulas, eg. 2x - 3y + 8z]:

Q Based on the above answer, the column player should:

	Always play paper			Always play scissors
	Always play rock		Play paper, scissors, rock in the ratio -0.05, 0.15, and -0.1

Q If your opponent uses that strategy, she can expect to:

	Lose 10% of the time			Win 10% of the time
	Lose 90% of the time			Win 90% of the time
	Lose 0.10 points per game on average			Win 0.10 points per game on average

Q Duh! If my opponent knows I am playing rock most of the time, then obviously she should play paper to beat me. Who needs all this nonsense about matrices to figure that out, especially when it gives the wrong answer?
A Yes, most of the time you are playing rock, and so you would lose to paper. However, you are playing scissors almost as often as rock, so a decision by your opponent to play paper would carry some risk, as paper would only earn her an average of 40 - 35 = 5 points for every hundred plays. A better bet is for your opponent to play rock, which ties every time you play rock and beats your scissors, meaning that your opponent would win an average of 35 - 25 = 10 points for every hundred plays.

Now go on to Part B of this tutorial. Alternatively, try the exercises in Section 3.4 of Finite Mathematics and Finite Mathematics and Applied Calculus that pertain to setting up a game and mixed strategies.