Question 1

In the following extensive games, the top payoff at a leaf is to player I and the bottom payoff is to player II.

(a) Find all equilibria of the following game in behaviour strategies (including pure strategies).
[ Hint: Determine first the mixed equilibrium strategies. ]

(b) Consider the following zero-sum game in extensive form. Find a subgame perfect equilibrium (SPE) of this game (by solving the subgames first). Explain why this suffices to determine the value of the game.

(c) Find all equilibria of the game in (b) in randomized strategies. Explain which type of randomized strategy is appropriate for this purpose and why it can be used.
[ Hint: Argue directly with the game tree, not with the strategic form. ]

Question 2

Recall that in the game Nim the two players start with some heaps of chips and alternately remove some chips from one of these heaps. Player I moves first. The player to remove the last chip wins. In the following questions, you may use the known way of determining a winning strategy in Nim.

(a) Consider a Nim game with three heaps of sizes 9, 11, and 12. Find all winning moves from this position, if any. (“Winning move” refers always to the first move made by the player.)

(b) Consider a Nim game with four heaps of chips. What is the maximum number of distinct winning moves, if any?

The following parts of this question refer to a new game called Nim-2-3-all, which is played as follows:

As in Nim, there are heaps of chips, and a possible move is to remove some number of chips from a single heap. However, when removing some chips from a heap, a player may only remove two, three,or all chips from the heap at a time.

(c) Suppose Nim-2-3-all is played with a single heap of size n. Determine the Nim-value (size of
equivalent heap in ordinary Nim) of this game, depending on n, for n ≤ 10.

(d) Suppose Nim-2-3-all is played with three heaps of sizes 2, 3, 4. Is this is a winning position? If
so, what is a winning move? Explain.

(e) Suppose Nim-2-3-all is played with three heaps of sizes 4, 5, 6. Is this is a winning position? If
so, what is a winning move? Explain.

(f) What is the Nim-value of a single heap of size n = 500 of Nim-2-3-all? Explain.