Imperfect Information Extensive Form Games

Introduction

Solving extensive form games with perfect information was quite straightforward using backward induction.  Working from the end of the game back to the root of the game tree involved having the player choose a best response to the action that got her to a particular node. In choosing the best response we asked ourselves whether the player's strategy was credible at that point in the game. As a consequence of working backwards through a sequence of best responses we saw that the backward induction solution to an extensive form game was a Nash Equilibrium.

Extensive form games with imperfect information are also solved by working backwards from the end of the game.  However, in this class of games we will be working backwards through a sequence of Nash equilibria.  We will be checking to see if the group of players involved in the Nash equilibrium are playing their best responses.  The motivation is that same as that for games of perfect information: As a group are the strategies that lead to the Nash equilibrium credible, or reasonable?

What is a subgame?

What are the three criteria that must be met by a subgame?

Define best response.

Define Nash Equilibrium.

Building on the notions of subgames and Nash equilibrium, Reinhard Selten created the concept of a subgame perfect equilibrium.  Consider a two person game in extensive form.  A pair of strategies played by the participants is a subgame perfect equilibrium if they have the participants playing a Nash equilibrium when confined to any subgame of the original game.

Bob and Betty: Part I

Betty and Bob are friends.  They will be playing a stage game this weekend.  One round is played on Saturday and one round is played on Sunday.  The question is how will they use the afternoon. They can each choose between 'crash' (take a nap) and 'nosh' (have a beer and chips). Each day they make their decision simultaneously. For either afternoon the game looks like

The payoffs are in utility values, a sense of well being. If they both crash then they both get a payoff of zero since they really haven't spent any quality time together.  If Betty chooses to crash and Bob chooses to Nosh then they payoffs are <7, 2>.  Betty's payoff is 7 because she didn't consume any unwanted calories and she got a much needed rest.  But if Bob is noshing while Betty is crashing his payoff is -2 since he is getting fatter and he feels as though he is being ignored by his friend.  Note that the game is symmetric and it is a Prisoner's dilemma.

The solution to the game as pictured is <Crash, Crash>.  Crash is the dominant strategy for both of them.  Crash is also a best response for both of them.

Bob and Betty are playing this game twice over the weekend and the payoffs are cumulated over the two stages of the game.  The whole game can be pictured in extensive form.

There are five subgames.  What are they?

What are the four Nash equilibria in the four subgames corresponding to the second encounter between Bob and Betty?  You can see by looking at the four subgames labeled one through four that the dominant strategy in each is <Crash, Crash>.  

Are all of the Nash Equilibrium found in the sub-games also Nash equilibria in the whole game?  To answer this question consider the subgame that consists of the entire game, from the root to the ends of the branches.  Since we already know that Bob and Betty each will play Crash in the second round no matter what, we really only need to look at the payoffs at the end of the first round.  Looking only at the first round we know that the dominant strategy is Crash for both of them.  

The subgame perfect equilibrium for the entire game has the strategy profile <Crash1, Crash2 ; Crash1, Crash2>.  This means that Betty plays Crash in round 1 and crash in round 2; same for Bob.  Even if there is a mistake and they find themselves at nodes 2, 3 or 4, they would still play Crash in the second round.   It looks as though Bob and Betty spend a lot of time sleeping.

Bob and Betty: Part II

Consider a somewhat more difficult example. Bob and Betty have other dimensions to their lives together. They must cook, wash dishes, and vacuum.  Bob can't cook very well and just doesn't like to wash dishes, so they have concocted the following game for allocating the tasks.  Betty moves first and she chooses between cooking and doing the dishes.  If she chooses dishes, then Bob chooses to Go Out or Cook.  On the other hand, if Betty chooses to cook, then they simultaneously choose between the remaining two tasks; vacuuming and doing the dishes.  The payoffs are at the end of the tree.  You may conclude whatever you want about the relationships between the payoffs and the preferences of Bob and Betty for doing chores and being together.

There are three subgames: There are two proper subgames; one beginning at node B and one beginning at node A.  The game itself is a subgame.

There are two paths to Nash equilibria.  The first one (Path One) from the root through node A is Betty_Dishes, Bob_Out.  The other one (Path Two) from the root through node B to the information set containing nodes C and D is Betty_Cook, Bob_Vacuum, Betty_Vacuum.  You must use IEDS on the subgame beginning at node B in order to find this second path.

Path Two is supported by the strategy profile ({Cook, Vacuum}, {Out, Vacuum}).  That is, Betty plays Cook at the root and Vacuum at the subgame commencing with node B.  Bob plays Out at node A and Vacuum at node B.  This path is a subgame perfect equilibrium.  For the subgame starting at A the proposed strategy profile reduces to ({.}, {Out}), which is a Nash equilibrium. For the subgame starting at node B the strategy profile reduces to ({.,Vacuum}, {.,Vacuum}), which is a Nash equilibrium.

Are there any other strategy profiles that will support Path Two?

The strategy profile ({Dishes, Vacuum}, {Out, Vacuum}) supports Path One, the road to a Nash equilibrium.  At the root node Betty plays Dishes and at node A Bob plays Out.  If they should happen to find themselves at the subgame starting at node B, then they both play vacuum, which is a Nash Equilibrium.  But this strategy profile is not the only one that supports Path One.

Path One is also supported by the strategy profile ({Dishes, Dishes}, {Out, Dishes}). Betty plays Dishes at the root and Dishes at nodes C or D; Bob plays Out at node A and Dishes at node B. This is a Nash equilibrium profile since Out is Bob's best response to a play of Dishes by Betty at the root node.  But this is not a subgame perfect equilibrium since a play of Dishes by Bob at node B and a play of Dishes by Betty at C or D could be improved upon.  In this case we have a strategy profile that involves a Nash equilibrium in one subgame, but non-credible plays in another subgame.

Consider the strategy profile ({Dishes, Vacuum}, {Out, Dishes}), which also supports Path One. Is this profile a subgame perfect equilibrium?  No.  This profile does result in a Nash equilibrium in the subgame beginning at node A, but there is a hitch.  In the subgame that includes the root Betty would never play Dishes at the root, as called for by the profile.

Are there any more strategic profiles that support Path One?  Consider ({Dishes, Dishes}, {Out, Vacuum}) and explain why this is not a subgame perfect equilibrium.

As in the normal form games we have seen, there may be multiple Nash equilibria in an extensive form game.  The principle of subgame perfect equilibrium is to eliminate those Nash equilibria which may be based on non-credible or unreasonable promises or threats.  In the analysis of the second Bob and Betty example we eliminated two strategy profiles that involved a Nash equilibrium in a subgame, but which also included unreasonable behavior in other subgames.

The normal form representation of the sub-game at B

The solution - Nash Equilibrium in the sub-game is <Vacuum, Vacuum>

The normal form representation of the sub-game at A

The only one with a choice is Bob, so the Nash Equilibrium is <{}, Out>

According to the normal form representation there are four Nash Equilibria.  However, the strategic plan that Bob would have to play in order to produce two of them, {D O}, would result in non-credible play at node B since it produces an outcome that is not a Nash Equilibrium.  Similarly, Bob's strategic plan {V C} would result in non-credible play at node A since he would never to choose to cook if he found himself at A.  Therefore, the only sub-game perfect equilibrium is the strategic pair <{C V}, {V O}>  

For another example see Buck's Bolts hires Les Threads.  A similar model can serve as an explanation for involuntary unemployment.