Deciding Wisely, Winning Games

Exercises and Projects for Chapter 2: Simultaneous Games

*** a) Write down the matrices of the SIMULTANEOUS LEGISLATORS VOTE game in the variant where each of the three voters has also the option to abstain. The raise only passes if more agree than voting against. The loss of face by abstaining is relatively small, only $200.
b) Solve that game, using the approaches discussed above.

A votes for raise
	C raise	C abstains	C against raise
B raise	10,10,10	10,10,18	10,10,20
B abstains	10,18,10	10,18,18	-10,-2,0
B against raise	10,20,10	-10,0,-2	-10,0,0

A abstains
	C raise	C abstains	C against raise
B raise	18,10,10	18,10,18	-2,-10,0
B abstains	18,18,10	-2,-2,-2	-2,-2,0
B against raise	-2,0,-10	-2,0,-2	-2,0,0

A votes against raise
	C raise	C abstains	C against raise
B raise	20,10,10	0,-10,-2	0,-10,0
B abstains	0,-2,-10	0,-2,-2	0,-2,0
B against raise	0,0,-10	0,0,-2	0,0,0

The Maximin moves are voting against a rise. There is no domination. There are seven pure Nash equilibria, namely when two of them vote for a raise and one opposes, or when one of them votes for the raise and two abstain, or when all three vote against it. The corresponding cells are shaded.

Assume a simultaneous two-player game has the best response digraph shown to the right. Display a possible payoff bimatrix. Can you find a possible zero-sum payoff bimatrix generating this best response digraph?

Here is an example, but there are many more:

	L	M	R
U	-1, 1	1, -1	0, 1
M	-1, 1	0, 0	1, -1
D	1, -1	1, -1	-1, 1

Consider the following two-player game.

	L	M	R
U	1,1	3,4	2,1
M	2,4	2,5	8,1
D	3,3	0,4	0,9

Find the Maximin moves for both players.
Which moves are dominated?
Find the bimatrix obtained by IESD.
Find the bimatrix obtained by IEWD.
Draw the best response digraph.
Are there any Nash equilibria?

Maximin move is "M" for both Ann and Beth, guaranteeing a value of at least 2 for Ann and at least 4 for Beth.

For Ann there is no domination, weak or strong. For Beth, move "M" dominates (strongly, and therefore also weakly) move "L".

After removing option "L" for Beth, suddenly Ann's move "D" is strictly (and therefore also weakly) dominated by both "U" and "M". After eliminating this option as well, we arrive at the following bimatrix:

M R

U 3,4 2,1

M 2,5 8,1

Here again Beth has domination---move "M" stricty dominates move "R". After removing move "R", Ann's move "M" strictly dominates move "M". Therefore the IESD and IEWD matrix, the result after iterated eliminating strictly or weakly dominated moves, is

M

U 3,4

The best responses are U-->M, M-->M, and D-->R for Beth, and L-->D, M-->U, and R-->M for Ann.

Therefore the Nash equilibrium is "U" versus "M", since "M" is Beth's best response against Ann's "U", and "U" is Ann's best response against Beth's "M".

Analyze the following six two-person zero-sum games (Maximin moves, domination, best response digraph, Nash equilibria):

	L	R
U	1	2
D	3	4

	L	R
U	1	2
D	4	3

	L	R
U	1	3
D	2	4

	L	R
U	1	3
D	4	2

	L	R
U	1	4
D	2	3

	L	R
U	1	4
D	3	2

Let's do just the first of these six examples. Note that the matrix of the first one translates into the following bimatrix:

	L	R
U	1, -1	2, -2
D	3, -3	4, -4

Therefore Ann's maximin move is "D", guaranteeing a payoff of at least 3, and Beth's maximin move is "L", guaranteeing at least a payoff of -3. Ann's move "D" dominates her move "U", and Beth's move "L" dominates her move "R". Therefore "D" versus "L" is the IESD result. This is also the Nash equilibrium.

Consider the 2 person variant of the GUESS THE AVERAGE(2,4) game where every player can just choose one of the numbers 1,2,3,4. Create the payoff bimatrix. Decide whether the game has a dominant move equilibrium, an IEWD equilibrium, an IESD equilibrium, or a Nash equilibrium.

The payoff bimatrix looks like this.

	1	2	4	4
1	0.5, 0.5	1, 0	1, 0	1, 0
2	0, 1	0.5, 0.5	1, 0	1, 0
3	0, 1	0, 1	0.5, 0.5	1, 0
4	0, 1	0, 1	0, 1	0.5, 0.5

There is no strict domination, so there is no dominant move equilibrium. However move "1" weakly dominates all others. Therefore the IEWD matrix is

1

1 0.5, 0.5

The pair "1" versus "1" is the only Nash equilibrium of the game.

*** In the TWO BARS example above, it is obvious that lack of tourists make the situation more competitive. Assume the number of natives is fixed as 4000. For which number of tourists would both bars choose $ 4 as price for the beer? For which tourist numbers is $ 2 possible, and for which tourist numbers is $ 5 possible?

Obviously more tourists mean higher prices, since the tourists don't look at the price. Assume there are x thousand tourists. Then the payoffs, in thousands, are as follows:

	2	4	5
2	2·(x/2+2), 2·(x/2+2)	2·(x/2+4), 4·(x/2)	2·(x/2+4), 5·(x/2)
4	4·(x/2), 2·(x/2+4)	4·(x/2+2), 4·(x/2+2)	4·(x/2+4), 5·(x/2)
5	5·(x/2), 2·(x/2+4)	5·(x/2), 4·(x/2+4)	5·(x/2+2), 5·(x/2+2)

Let us look at the condensed best response digraph---remeber that we have a symmetric game.

What is the best response to move 2? Since 5·(x/2) > 4·(x/2), it could only be 2 or 5. Since 5·(x/2) > 2·(x/2+2) is equilvalent to x > 8/3, the best response to move 2 is move 5 if x > 8/3 and otherwise it is move 2.
What is the best response to move 4? Since 4·(x/2+2) > 2·(x/2+4), it could only be 4 or 5. Since 5·(x/2) > 4·(x/2+2) is equivalent to x > 16, the best response to move 4 is 5 if x > 16 and it is move 4 otherwise.
In the same way, the best response to move 5 could only be move 4 or 5. Since 5·(x/2+2) > 4·(x/2+4) is equivalent to x > 12, the best response to move 5 is move 5 if x > 12 and otherwise it is move 4.

Therefore there are three thresholds: x=8/3, x=12, and x=16.

For x < 8/3 there are two pure Nash equilibria: 2 versus 2 and 4 versus 4.
For 8/3 < x < 12 there is one pure Nash equilibrium: 4 versus 4.
For 12 < x < 16 there are again two pure nash equilibria: 4 versus 4 and 5 versus 5.
For 16 < x there is only one pure Nash equilibrium: 5 versus 5.

Write down the payoff bimatrix of the following game. Find Maximin moves, domination, condensed best response digraph, and all pure Nash equilibria.

SCHEDULING A DINNER PARTY: Ann and Beth are not on speaking terms, but have a lot of common friends. Both want to invite these friends to a dinner party this weekend. Possible are Friday or Saturday evening. Both slightly prefer Saturday. If both set the party at the same time, this will be considered a disaster with a payoff of -10 for both. If one plans the party on Friday and the other on Saturday, the one having the Saturday party gets a payoff of 5, and the other of 4.

	friday	saturday
friday	-10,-10	4,5
saturday	5,4	-10,-10

Both moves are Maximin, there is no domination. Since this is a symmetric game, it suffices to show the condensed best response digraph, having only two vertices labeled "Friday" and "Saturday" and arcs from Friday to Saturday and from Saturday to Friday. These are two pure Nash equilibria: Friday versus Saturday and conversely.

Analyze the following game. Create payoff bimatrices consistent to the information given. Explain your choices. Then find the maximin moves, domination, and all pure Nash equilibria.

SELECTING CLASS: Adam, Bill, and Cindy are registering for one foreign language class independently and simultaneously. The available classes are ITA100 and FRE100. All three are almost indifferent between the two choices, but they are not indifferent with whom to share the class. More precisely, Bill and Cindy want to be in the same class, but want to avoid Adam. On the other hand, Adam wants to be in the same class as Bill and Cindy, or even better, both.

The first problem is how the payoffs in the different situations are combined by the preferences described above. The payoff for each person depends on three ingredients: Whether or not the first other player is in the same class, whether or not the second other player is in the same class, and which class it is. We assume that having somebody in the same class counts as +1 (if the other is wanted) or -1 (if the other should be avoided). As discussed in the "Modeling I" section above, we assume additivity of these ingredients. Then we arrive at the folloiwng matrices:

A ITA
	C ITA	C FRE
B ITA	2, 0, 0	1, -1, 0
B FRE	1, 0, -1	0, 1, 1

A FRE
	C ITA	C FRE
B ITA	0, 1, 1	1, 0, -1
B FRE	1, -1, 0	2, 0, 0

There are two pure Nash equilibria: All three going to ITA100 or all three going to FRE100.

DEADLOCK: Two players play a symmetric game where each one can either cooperate or defect. If both cooperate, both get an payoff of 1. If both defect both get a payoff of 2. If one cooperate but the other defects, the one cooperating gets a payoff of 0, and the other defecting a payoff of 3.

Draw the bimatrix of the game. Find the Maximin moves, possible domination, draw the best response digraph, and find all pure Nash equilibria.

	Cooperate	Defect
Cooperate	1, 1	0, 3
Defect	3, 0	2, 2

Both games, PRISONER's DILEMMA and DEADLOCK have exactly one Nash equilibrium of both defecting. The difference is that in DEADLOCK both prefer the outcome over the "both cooperating" outcome, whereas in the PRISONER's DILEMMA they don't.

STAG HUNT: Two players play a symmetric game where each one can either hunt stag or hare. If both hunt stag, both get an payoff of 3. If both hunt hare, both get a payoff of 1. If one hunts stag and the other hare, the stag hunter gets a payoff of 0, and the hare hunter a payoff of 2.

Draw the bimatrix of the game. Find the Maximin moves, possible domination, draw the best response digraph, and find all pure Nash equilibria.

Hunt stag Chase hare

Hunt stag 3, 3 0, 2

Chase hare 2, 0 1, 1

STAG HUNT has two Nash equilibria: Both hunting stag, which is Pareto-optimal, or both chasing hares.

CHICKEN: Two players play a symmetric game where each one can either play Dove or Hawk. If both play Dove, both get an payoff of 2. If both play hawk, both get a payoff of 0. If one plays Dove and the other Hawk, the one playing Dove gets a payoff of 1, and the other one a payoff of 3.

Draw the bimatrix of the game. Find the Maximin moves, possible domination, draw the best response digraph, and find all pure Nash equilibria.

Dove Hawk

Dove 2, 2 1, 3

Hawk 3, 1 0, 0

As our previous example, CHICKEN also has two pure Nash equilibria, but this time they are the asymetric Dove/Hawk and Hawk/Dove combinations.

BULLY: Two players play the following symmetric game

Cooperate Defect

Cooperate 2, 1 1, 3

Defect 3, 0 0, 2

(compare [Poundstone 1993]).

Draw the bimatrix of the game. Find the Maximin moves, possible domination, draw the best response digraph, and find all pure Nash equilibria.

There is one Nash equilibrium, where Ann (the chicken player) cooperates and Beth, the bully, defects.

Two cars are meeting at an intersection and want to proceed as indicated by the arrows in the picture. Each player can proceed or yield. If both proceed, there is an accident. A would have a payoff of -100 in this case, and B a payoff of -1000 (since B would be made responsible for the accident, since A has the right of way). If one yields and the other proceeds, the one yielding has a payoff of -5, and the other one of 5. If both yield, it takes a little longer until they can proceed, so both have a payoff of -10. Analyze this simultaneous game, draw the payoff bimatrix and find pure Nash equilibria.

	proceed	yield
proceed	-100,-1000	5, -5
yield	-5, 5	-10, -10

There are two pure Nash equilibria, where one yields and the other one proceeds. Note that the theory does not distinguish one of them to be more likely, although A has the right of way.

Three cars are meeting at an intersection and want to proceed as indicated by the arrows in the picture. Each player can proceed or yield. If two with intersecting paths proceed, there is an accident. The one having the right of way has a payoff of -100 in this case, the other one a payoff of -1000. If a car proceeds without causing an accident, the payoff for that car is 5. If a car yields and the all others intersecting its path proceed, the yielding car has a payoff of -5. If a car yields and a conflicting path car as well, it takes a little longer until they can proceed, so both have a payoff of -10. Analyze this simultaneous game, draw the payoff bimatrices and find all pure Nash equilibria.

A proceeds
	C proceeds	C yields
B proceeds	-1000, -100, 5*	-1000, -100, -5
B yields	5, 5, -5	5, -10, -10

A yields
	C proceeds	C yields
B proceeds	-5, -1000, -100	-5, 5, -5
B yields	-10, -10, 5	-10, -10, -10

*The payoff attached to this outcome is not really explained above, but we may assume that, since A and B make an accident, C can proceed without problems. One could however also be the opinion that the payoffs in this cell should be -1000, -1000, -100. Which version we choose will however not affect the analysis below.
The Maximin moves for all three is to yield. There is no domination. There are two Nash equilibria. The first where A and C proceed and B yields, and the second one where A and C yield and B proceeds.

Solve the SIMULTANEOUS ULTIMATUM GAME: Display the payoff bimatrix, and investigate Maximin moves, domination, best responses, and whether there are any equilibria.

The payoff bimatrix looks like this.

	0	1	2	3	4	5
0	0, 0	0, 1	0, 2	0, 3	0, 4	0, 5
1	1, 0	1, 1	1, 2	1, 3	1, 4	0, 0
2	2, 0	2, 1	2, 2	2, 3	0, 0	0, 0
3	3, 0	3, 1	3, 2	0, 0	0, 0	0, 0
4	4, 0	4, 1	0, 0	0, 0	0, 0	0, 0
5	5, 0	0, 0	0, 0	0, 0	0, 0	0, 0

All moves are Maximin moves, guaranteeing a safety level of 0.
The best response to move 0 is move 5, the best response to move 1 is move 4, the best response to move 2 is move 3, the best response to move 3 is move 2, the best response to move 4 is move 1, and the best response to move 5 are all other moves. Therefore there are four pure Nash equilibria: 0 versus 5, 2 versus 3, 3 versus 2, and 5 versus 0.

.....

...

Projects

Project: SELECTING CLASS: Adam, Bill, and Cindy are registering for one foreign language class independently and simultaneously. The available classes are ITA100 and FRE100. All three are almost indifferent between the two choices, but they are not indifferent with whom to share the class. More precisely, Bill and Cindy want to be in the same class, but want to avoid Adam. On the other hand, Adam wants to be in the same class as Bill and Cindy, or even better, both.
Assume that the payoff for each player is the sum of the payoffs of having the other two in the same class or not, and the payoff for being in the right class. Assume that the payoff for being in the right class is 0.1 or -0.1, and the payoff for having the other in the same class are 1 or -1. There are 8 possible cases. In which one do we get Nash equilibria, and in which one of them do we get just one Nash equilibrium?

If Bill and Cindy both slightly prefer the same class, all three will register there. There si only this one pure Nash equilibrium in this case. If Bill and Cindy prefer different classes, there is no pure Nash equilibrium.

Project*: GENERALIZED SELECTING CLASS: Adam, Bill, and Cindy are registering for one foreign language class independently and simultaneously. The available classes are ITA100 and FRE100. All three are almost indifferent between the two choices, but they are not indifferent with whom to share the class.
Assume that the payoff for each player is the sum of the payoffs of having the other two in the same class or not, and the payoff for being in the right class. Assume that the payoff for being in the right class is 0.1 or -0.1, and the payoff for having the other in the same class are 1, 0, or -1. There are many cases. Can you classify in which cases we get Nash equilibria, and in which one of them do we get just one Nash equilibrium?
What can be said about the stability of the Nash equilibria obtained? What if these payoffs are not exactly 1, 0, -1, 0.1, -0.1, but about that much?

...

Project*: ELECTION, Part 1:

Ann and Beth are running for president of the USB. There are three states. Similar to the president of the USA, this president is elected by votes from the three states, where states have different numbers of votes, and cannot split their votes. A state votes for that candidate that visited the state more often. In case of a tie, they abstain. We assume that the payoff for the winner is 1, and the payoff for the loser is -1. In case of a tie the payoffs are 0 for both.

It's three days before the election, and the two candidates have to determine now, simultaneously, which states to visit on each on the remaining three days. They have one visit per day, and they have to change states every day, so either they visit all three states, or they visit one twice and one once.

For parts (a) to (d) we also assume that the first state has 7 votes, the second state 8, and the third one 13.

a) Assume each of the three state has seen each candidate equally often so far. What will the candidates do?
b) Assume the small state has seen Ann once more than Beth so far, the medium state has seen Beth once more than Ann, and that the large state has seen both candidates equally often. What will both candidates do in the remaining three days?
c) Assume the small state has seen Ann twice more than Beth so far, the large state has seen Beth once more than Ann, and that the medium state has seen both candidates equally often. What will both candidates do in the remaining three days?
d) Assume the medium state has seen Ann once more than Beth so far, the large state has seen Beth once more than Ann, and that the small state has seen both candidates equally often. What will both candidates do in the remaining three days?
e) How will (a), (b), (c), and (d) change if the small states has 6 votes instead of 7?
f) How will (a), (b), (c) and (d) change if the small states has 5 votes instead of 7?

The recommendation is to find first the possible moves for both players, then compute the Normal form, and then eliminate weakly dominated moves to get the IEWD matrix.

...