CIT 591 Assignment 9:
Game Theory: Mixed Strategies
Fall 2010, David Matuszek
Combine this assignment with the earlier Saddle Points assignment to create a fairly complete
GameTheory
program.
In your SaddlePoints project, in the saddlepoints
package, create a new class called GameTheory
. This class will sit alongside your SaddlePoints
class and make use of methods from it. You can correct any actual errors you find in your SaddlePoints
class, but you should not make any other changes or additions to it.
Your program should read in arrays, one at a time. For each array, the program should determine (and print out):
You should have a different partner from the earlier assignment, so you should have
two different versions of the SaddlePoints
class to work with. You should use your own SaddlePoints
class, and your partner should use his/her own. Your new GameTheory
class should work equally well with either.
I will provide you with a method to read
in arrays. The SaddlePoints
class already has a method you can use to print the arrays, and other methods you can use.
Remember how the game is played: Max chooses a row, Min chooses a column, and where they intersect is the amount Min pays to Max. In some games there is a saddle pointthat is, a "best" row and a "best" column. Players would be wise to always play to the saddle point.
In other games, there is no single "best" move, because the best move depends on how the opponent is likely to move. In the game below, for example, if Max always chooses the same row, then Min knows which column to choose to get a negative number. Likewise, if Max knows how Min is going to play, Max can always win. Hence, both players should use a mixed strategy, sometimes making one choice and sometimes another.
Although Max and Min should randomize their play, that doesn't mean that every row and every column should be chosen equally often. In this game, Max should choose the first row more than twice as often as the second row, and Min should more often choose the first column. How do we know this?
The purpose of this assignment is not to play the game, but to compute how frequently the players should choose each row and each column, for any size array.
Min


0

1

2


Max  0 


1  
2 
Suppose there is no saddle point, as in this game. Then players must choose between two or more rows or columns. Also, the other player shouldn't be able to predict their moves, so they need to play somewhat randomly, but still choosing the best rows or columns more often than the worse ones. This is called a mixed strategy.
For example, a mixed strategy for Max might be
,
meaning that Max chooses row zero 20% of the time, row one 50% of the time,
and row two 30% of the time (and similarly for Min).
By the way, these numbers don't have to add up to exactly 100. If Max's strategy
is
or
, these
are both equivalent to [20, 50, 30]
(and to each other).
You can compute an approximate best mixed strategy by simply (sort
of) playing the game a large number of times (say, a thousand). Here's how.
Each player starts with a strategy of
(or
,
or however many rows or columns there are to choose from). Then repeatedly
do the following:
In the above example, suppose Max and Min both start with a strategy of
.
[1, 1, 1]

that is, equal probabilities.0
, he will get 1
or 2
or 3
with equal probabilities. So (1*1
+ 1*(2) + 1*3)/3
= 2/3
is his expected payoff.1
, he will get 6
or 5
or 4
with equal probabilities. So (1*(6)
+ 1*(5) + 1*(4))/3
= 5/3
is his expected payoff.2
, he will get 7
or 8
or 9
with equal probabilities. So (1*7
+ 1*(8) + 1*9)/3
= 8/3
is his expected payoff.8/3
, so his choice is row 2
.
He updates his strategy to [1, 1, 2]
.[1, 1, 1]
, which is 3
). Since we
just want to know which number is the largest, we can skip the
division, and just compare the numbers 2
, 5
, and 8
. [1, 1, 2]
.0
, she will get 1
, 6
, or 7
with
odds 1:1:2
. So (1*1 + 1*(6) + 2*7)/4 = 9/4
. Or, skipping the division,
9
.1
, she will get 2
, 5
, or 8
with odds 1:1:2
.
So (1*(2) + 1*5 + 2*(8))/4 = 13/4
; or, just use 13
.2
, she will get 3
, 4
, or 9
with odds 1:1:2
.
So (1*3 + 1*(4) + 2* 9)/4 = 17/4
. Or, just use 17
.13
, so her choice is column
1
. She updates her strategy to [1, 2, 1]
.[1, 2, 1]
.We will have the two players take turns (again, we are not playing the game, we are figuring out the best mixed strategy.) For each turn, the player whose turn it is chooses the best move based on how the opponent has been playing.
To implement this, we need two additional arrays; one to keep track of how
many times the row player has chosen each row, and one to keep track of how
many times the column player has chosen each column. To get things started,
each of these arrays will be filled with 1
s. In Figure 1 (below),
we start by having the row player choose row 0, as indicated by the 1 in
the array on the right.





Figure 1. The initial setup (all rows and columns have equal probability).  Figure 2. Max knows Min's strategy is 1:1,
so he will do better with row 1 row 0 
Figure 3. Now Min knows Max's strategy is 1:2,
so she will do better with column 0 column 1 
Figure 4. Max's turn: row 0: row 1: so choose row 0. 





Figure 5. Min's turn: col 0: col 1: so choose column 0. 
Figure 6. Max's turn: row 0: row 1: so choose row 0. 
Figure 7. Min's turn: col 0: col 1: so choose column 0. 
Figure 8. Max's turn: row 0: row 1: so choose row 0. 
This procedure eventually results in the "best" strategy for each player; the side and bottom arrays give the relative number of times each row and each column, respectively, can be played. In the above game, if the results are given in percentages, they should be(approximately): Max, [70.8%, 29.2%]; Min, [62.5%, 37.5%].
Create a class GameTheory
. This class should have a constructor
.
The constructor will save this array in a local variable, and many of the methods
will use this "game."
Notice that at each turn, one of the players chooses a move randomly, according to his or her current mixed strategy. The other player then chooses the best response to that move, and updates his/her mixed strategy. To implement this, you should have the following methods: The preceding three sentences are cruel and misleading, and should be ignored.
public static void main(String[] args)
main
method, and the program will do whatever the main
method for that class says to do. This main
method should use the provided method to ask the reader for an array to read in, print the array, and tell whether it has a saddle point, and how each player should play. It should repeat this for as many arrays as desired, quitting when the provided method returns null
instead of an array.static int chooseRandomly(int[] weights)
0..weights.length
, chosen randomly
according to the ratios in the weights
array. For example, if
the weights
array is {2, 5, 3}
0
, 20% of the time; 1
,
50% of the time; and 2
, 30% of the time.
Hint: This is most easily done with one call torandom.nextInt(int)
. Can you figure out how?
This method can be used to play the game, but is not used when determining optimal strategies.
int chooseBestRowForMax(int[] minsStrategy)
int chooseBestColumnForMin(int[] maxsStrategy)
void computeMixedStrategies()
int[]
fields of this Game
object.
double[] getStrategyForMax()
computeMixedStrategies()
has been called for this game,
return an array of double
s containing the best mixed strategy
for Max. These double
s should sum to 1.0
. (For example,
if the int array contains {2, 7, 5, 6}
,
the array returned by this method should be {0.10, 0.35, 0.25, 0.3}
.
If computeMixedStrategies()
has not been called, this method
returns null
.
double[] getStrategyForMin()
computeMixedStrategies()
has been called for this game,
return return an array of double
s containing the best mixed strategy
for Min. These double
s should sum to 1.0
. If computeMixedStrategies()
has not been called, this method returns null
.Your SaddlePoints
class should be working properly. You can test it with DavesSaddlePointsTest.java.
In order to read in twodimensional integer arrays, I have supplied a readIntArray
method. It is included in a complete program, IntArrayReader.java, but you should copy just the method (and the necessary import
s) and put them in your GameTheory
class. The readIntArray
method can throw exceptions; you should catch these exceptions in your code, and print a message to the user, but your program should continue to run.
Java is a good languagereally!but it does make file I/O ridiculously complex. Please do not ask me to explain to you how the readIntArray
method works. If you are interested, this would make a good weekend project with a Java book.
Write comprehensive JUnit tests for each of the above methods. Put these in
a class named GameTheoryTest
.
Since it's unwise to test floatingpoint numbers for equality (and since you
won't get exact results in any case), you will need to use the following JUnit
method:
static void assertEquals(double expected,
double actual, double delta)
where the expected
value and the actual
value should
be within delta
of each other in order to be considered approximately
equal.
Include your earlier SaddlePointsTest
class. If you had to make any changes in
your SaddlePoints
methods, make sure your unit tests still work.
Add Javadoc comments to all nonprivate classes, fields, and methods. Javadoc
is optional for private fields and methods. You don't need to document your unit test methodsbut use internal comments for anything unusual or confusing. The Javadoc for your GameTheory
class must include @author
tags for both yourself and your partner.
Be sure your source code is properly formatted, according to Java (not C) standards.
Thursday, November 11, before midnight. Zip your entire project folder, and submit it via Blackboard. The project should contain the new code (GameTheory.java
and GameTheoryTest.java
), and one copy of the previouslywritten SaddlePoints.java
and SaddlePointsTest.java
files (I don't care whose, yours or your partner's). Email submissions will go directly into the trash bin.