# Homework Help: Game theory - need help.

1. Oct 2, 2011

### rajuu

Hi! I really need a help in solving certain task.

Before the Allied invasion of France during WWII [bonus point for the month and the year of this invasion ], the Germans had to decide where to place their defenses. They had three choices: They could concentrate their defenses at Calais (GC), concentrate them at Normandy (GN), or split them between the two locations (GS). The Allies had two choices: They could attack at Calais (AC) or at Normandy (AN). Assume that this is a zero-sum game and that the possible outcomes are ranked as in the following matrix (where larger numbers represent outcomes more favorable for the Allies):

GERMANS
GN GC GS
ALLIES AN 1 4 3
AC 6 2 5

Assume that this game is played sequentially, with the Germans’ having to move first.
a) Draw the game tree. What is the rollback equilibrium of this game? [2+2]
b) How many pure strategies (complete plan of action) are available for the GERMANS and for the ALLIES? List out all of the pure strategies for each player. [2 + 3]
c) What would be rollback equilibrium of this game, with the Allies having to move first? Draw the game tree. [2+2]
d) Use the Minimax method to find Nash equilibrium in simultaneous game. [2]

I know how to draw the game trees for both situations. I just can't list out the pure strategies for both players (point b) and don't know how to find NE (points d).

I hope someone will solve this task.

2. Oct 2, 2011

### HallsofIvy

"Bonus points"? For graded work, you are going to have to show some work of your own. The "pure strategies" are the rows (for the allies) and columns (for the Germans) of the matrix given.

3. Oct 2, 2011

### rajuu

It means that Allies have 2 pure strategies : AN, AC; and Germans have 3 pure strategies: GN, GC, GS. Right?

4. Oct 2, 2011

### HallsofIvy

Yes. Now, what are the definitions of "roll back equilibrium" and "Nash equilibrium"?

(And how does (a) differ from (c)?)

5. Oct 2, 2011

### rajuu

I answered the same on the exam and it was an wrong answer.

The difference, I hope you will get it.

a)
http://imageshack.us/photo/my-images/404/germansfirst0.png/

And the rollback equilibrium of this game.

http://imageshack.us/photo/my-images/143/germansfirst.png/

c)
http://imageshack.us/photo/my-images/849/alliesd.png/

And the rollback equilibrium of this game.

http://imageshack.us/photo/my-images/441/allies1.png/

Rollback (often called backward induction) is an iterative process for solving finite extensive form or sequential games. First, one determines the optimal strategy of the player who makes the last move of the game. Then, the optimal action of the next-to-last moving player is determined taking the last player's action as given. The process continues in this way backwards in time until all players' actions have been determined. Effectively, one determines the Nash equilibrium of each subgame of the original game.

A Nash equilibrium, named after John Nash, is a set of strategies, one for each player, such that no player has incentive to unilaterally change her action. Players are in equilibrium if a change in strategies by any one of them would lead that player to earn less than if she remained with her current strategy. For games in which players randomize (mixed strategies), the expected or average payoff must be at least as large as that obtainable by any other strategy.