Solution Set 15 (Ex: 2,3,4,5,6,8,9) – Extensive Games with Perfect Information

2. (SPE of Stackelberg game)

Suppose that the problem max_a2’ÎA2 u₂(a₁,a₂’) has a solution for any a₁ÎA₁. Let (a₁*,a₂*) be a solution of the maximization problem: max_{(a1,a2)’ÎA1´A2} u₁(a₁,a₂) subject to a₂Î argmax_a2’ÎA2 u₂(a₁,a₂’). Define a corresponding strategy profile (s₁*,s₂*) of the extensive game by s₁*(Æ)= a₁*, s₂*(< a₁*>)= a₂* and s₂*(< a₁>)Î argmax_a2’ÎA2 u₂(a₁,a₂’) if a₁¹a₁*, using the axiom of choice for the latter. By construction (s₁*,s₂*) is a SPE of the Stackelberg game. For a counter-example showing that not every SPE of the extensive game corresponds to a solution of the above maximization problem, consider the game:

In this game (L, AD) is a subgame perfect equilibrium, with a payoff of (1, 0), while the solution of the maximization problem is (R, C), with a payoff of (2, 1).

3. (Necessity of finite horizon for one deviation property)

In the (one-player) game

the strategy in which the player chooses d after every history satisfies the condition in Lemma 98.2 but is not a subgame perfect equilibrium.

4. (Necessity of finiteness for Kuhn's theorem)

Consider the one-player game in which the player chooses a number in the interval [0, 1), and prefers larger numbers to smaller ones. That is, consider the game á{1}, {Æ} È [0, 1), P, {₁}ñ in which P(Æ) = 1 and x ₁ y if and only if x > y. This game has a finite horizon (the length of the longest history is 1) but has no subgame perfect equilibrium (since [0, 1) has no maximal element).

In the infinite-horizon one-player game the beginning of which is shown in the following figure

the single player chooses between two actions after every history. After any history of length k the player can choose to stop and obtain a payoff of k + 1 or to continue; the payoff if she continues for ever is 0. The game has no subgame perfect equilibrium.

5. (SPE of games satisfying no indifference condition)

The hypothesis is true for all subgames of length one. Assume the hypothesis for all subgames with length at most k. Consider a subgame G(h) with l(G(h)) = k + 1 and P(h) = i. For all actions a of player i such that (h, a) Î H define R(h, a) to be the outcome of some subgame perfect equilibrium of the subgame G(h, a). By hypothesis all subgame perfect equilibria outcomes of G(h, a) are preference equivalent; in a subgame perfect equilibrium of G(h) player i takes an action that maximizes _i over {R(h, a) : a Î A(h)}. Therefore player i is indifferent between any two subgame perfect equilibrium outcomes of G(h); by the no indifference condition all players are indifferent among all subgame perfect equilibrium outcomes of G(h).

We now show that the equilibria are interchangeable. For any subgame perfect equilibrium we can attach to every subgame the outcome according to the subgame perfect equilibrium if that subgame is reached. By the first part of the exercise the outcomes that we attach (or at least the rankings of these outcomes in the players' preferences) are independent of the subgame perfect equilibrium that we select. Thus by the one deviation property (Lemma 98.2), any strategy profile s¢¢ in which for each player i the strategy s_i¢¢ is equal to either s_i or s_i¢ is a subgame perfect equilibrium.

6. (Armies)

We model the situation as an extensive game in which at each history at which player i occupies the island and player j has at least two battalions left, player j has two choices: conquer the island or terminate the game. The first player to move is player 1. (We do not specify the game formally.)

We show that in every subgame in which army i is left with y_i battalions (i = 1, 2) and army j occupies the island, army i attacks if and only if either y_i > y_j, or y_i = y_j and y_i is even.

The proof is by induction on min{y₁, y₂}. The claim is clearly correct if min{y₁, y₂} £ 1. Now assume that we have proved the claim whenever min{y₁, y₂} £ m for some m ³ 1. Suppose that min{y₁, y₂} = m+1. There are two cases.

• either y_i > y_j, or y_i = y_j and y_i is even: If army i attacks then it occupies the island and is left with y_i-1 battalions. By the induction hypothesis army j does not launch a counterattack in any subgame perfect equilibrium, so that the attack is worthwhile.
• either y_i < y_j, or y_i = y_j and y_i is odd: If army i attacks then it occupies the island and is left with y_i-1 battalions; army j is left with y_j battalions. Since either y_i - 1 < y_j - 1 or y_i - 1 = y_j - 1 and is even, it follows from the inductive hypothesis that in all subgame perfect equilibria there is a counterattack. Thus army i is better off not attacking.

Thus the claim is correct whenever min{y₁, y₂} £ m + 1, completing the inductive argument.

8. (ODP and Kuhn's theorem with chance moves)

One deviation property: The argument is the same as in the proof of Lemma 98.2.

Kuhn's theorem: The argument is the same as in the proof of Proposition 99.2 with the following addition. If P(h*) = c then R(h*) is the lottery in which R(h*, a) occurs with probability  f _c(a ½ h) for each a Î A(h*).

9. (Naming numbers)

The game is given by

• N = {1, 2}
• H = {Æ} È {Stop, Continue} È {(Continue, y) : y Î Z × Z} where Z is the set of nonnegative integers
• P(Æ) = 1 and P(Continue) = {1, 2}
• the preference relation of each player is determined by the payoffs given in the question.

In the subgame that follows the history Continue there is a unique subgame perfect equilibrium, in which both players choose 0. Thus the game has a unique subgame perfect equilibrium, in which player 1 chooses Stop and, if she chooses Continue, both players choose 0.

Note that if the set of actions of each player after player 1 chooses Continue were bounded by some number M then there would be an additional subgame perfect equilibrium in which player~1 chooses Continue and each player names M, with the payoff profile (M²,M²).