The Learning Point‎ > ‎Mathematics‎ > ‎

A tutorial on Extensive Games- Solved Problems - Extensive Form Games, Backward Induction, Perfect & Incomplete Information



A Tutorial on Extensive Form Games


Extensive Games



 
Extensive Form Games - Games with Perfect and Imperfect Information

These types of games can be further classified into two types:

  • Games with perfect information
  • Games with imperfect information


In the normal form games all the players acted simultaneously. What if say in BoS game one player acted after another. Will the outcome change? These type of games are represented by a TREE.

wife/husband

movie

football

movie

1,3

0,0

football

0,0

3,1



Considering BoS here suppose wife is the row player and she chooses first then the game will be represented by tree as follows:








Games with Perfect Information

  • Game Tree
  • Players associated with nodes
  • Payoffs to each player for terminal nodes
  • A(x) actions available at node x
  • successor nodes

           succ(x) = { x’ | x > x’, and there is no x’’ s.t. x > x’’ > x’ }


  • A 1-1 mapping between A(x) and succ(x)
  • i(x) is the player who chooses at node x.


Pure Strategy

For each i and x s.t. i(x)=i, a choice of action in A(x).


Example: Look at the tree of BoS game. Player 1 has two strategies, at node 1 she has only 2 choices while the player 2 has 4 choices


Mixed Strategy

  • Distribution over pure strategies
  • randomize “in advance”

Behavioural Strategy

  • Randomize choice at each node
  • No advanced randomization!
  • for each i and x s.t. i(x)=i,

           a distribution over actions in A(x)

In games of perfect information no difference between mixed strategy & behavioural strategy but in games of imperfect information difference sometimes exist.


Nash Equilibrium

  • Specification of strategies such that each player is maximizing his/her payoff given the strategies of the others.
  • Each player’s strategy is a best response to the strategies of the others.




Centipede Game




  • In this game each player at his node can either pass or stop the game.
  • If pass to other player, the total size of the pie (sum of payoffs) doubles.
  • If stop, get 4/5 of pie and the other player gets 1/5 of pie.
  • Highest payoff would be to continue at each node.
  • But this isn’t the equilibrium because at last node player 2 would rather stop than pass as his payoffs will be higher in that case.
  • But will the player 1 like the player 2 stop at that particular node? The answer is no.
  • So player 1 will try to stop at a node before
  • In a pure strategy Nash Equilibrium: If expect to stop at some node, then should

           stop at the previous node


  • Therefore, Only possible outcome: stop at first node


Entry Game (Perfect Information)

Suppose there is a firm(company) wants to enter a particular market in which another firm already has a monopoly.

M is the monopoly profit

c is the cost of entry for the new firm

If there is a price war then profits are 0 each

If no price war, profits are P each, and P>c

Game tree will look like this:


New firm chooses either to stay out or enter the market at Node 1. If suppose firm 2 has decided to fight both will 0 profit but firm 2 will be in loss due to cost “c” of entry. So if firm 2 decides to fight then firm 1 will like to stay out which is a Nash equilibrium.

If firm 2 decides not to fight then firm 1 will enter the market and both will share the profits , this being another Nash equilibrium.

One tends to get uncomfortable with what the first Nash Equilibrium suggests. If suppose firm 1 has decided to enter, will firm 2 really fight? Backward Induction suggests not.

So Nash Equilibrium is not always credible.



Backward Induction

Algorithm


  • Start at nodes that precede only terminal nodes
  • Choose a strategy that maximizes utility.
  • Move up the tree and repeat.

Example: Look at the entry game discussed earlier. Now look at the payoffs at terminal node. As before terminal node firm 2 chooses, it would like to maximise its payoffs so firm 2 will accommodate firm 1 in market. Now going to preceding node as Firm 2 has decided to accommodate firm 1 will enter.

For player 1 to make a choice must anticipate what 2 will do if 1 enters.






Incomplete Information

Games with incomplete information are the general case of Extensive Games.

Consider again the BoS game in extensive form discussed it earlier. It can be converted to the Normal Form as shown below:

1/2

MM

MF

FM

FF

movie(M)

1,3

1,3

0,0

0,0

football(F)

0,0

3,1

0,0

3,1




But how do we go about converting a Normal form game to Extensive Form.

This is done with the help of Information Sets.

.

Information Sets

  • Let Xa consist of all nodes x such that i(x)=a
  • A partition Pa of Xa for each player a, i.e., P={I1,I2,..,In} s.t.:

           Ii ⊂ Xa


  • For all I, J in Pa, I and J are disjoint
  • The union of all I in Pa is Xa
  • A(x) = A(x’) for all I in Pa and all x, x’ in I
  • The player cannot distinguish among the nodes in a given information set.

  • Now it is easy to deduce that Games with perfect information(where each information set is singleton) are the special case of game with incomplete information






Example: In the above  tree, player at node 2 can not distinguish between the choice that player 1 has made. It is equivalent to the normal form game whose table is given above.


Sub-Game Perfect Equilibrium

The notion of Nash equilibrium ignores the sequential structure of an extensive game; it treats strategies as choices made once and for all before play begins.


Sub-Game perfect equilibrium makes up for this.


  • A proper subgame is the entire game that remains starting from any nonterminal node.
  • A subgame is the entire remaining game starting from some (nonterminal node) that has a singleton information set.

Example: In the Bos game one such sub-game is shown below:









Sub-game perfection

  • A collection of strategies that form a Nash equilibrium in every proper subgame
  • So not only Nash equilibrium from beginning, but also an equilibrium from further points that are entire subgames

Example: Consider the Entry Game discussed earlier.

Consider the particular lower subgame. There exist only one Nash Equilibrium in this subgame i.e. to accommodate.

Now consider the larger subgame. It will have “Enter-Accommodate” as equilibrium

But as we saw earlier there exist another nash equilibrium of “stayout, fight” it is not an equilibrium in subgame.


  • The set of subgame perfect equilibriums coincide with those found via backward induction.
  • If the payoffs are distinct across terminal nodes, then there is a unique subgame perfect equilibrium.
  • The set of subgame perfect equilibria are a subset of the Nash equilibriums.




Exercises : Solved Problems

  1. What is the number of pure strategies that each player has?

Solution:  Player 1 has 2 pure strategies:

                 {Movie, Football}

                 Player 2 has 4 pure strategies:

                 (movie) movie; (movie) football; (football) movie; (football) football.







What is the number of pure strategies each player has?


Solution:  Player 1 has three pure strategies: A,B,C

                Player 2 has six pure strategies


Consider this centipede game:



Which could be a pure-­‐strategy Nash equilibrium outcome?
Solution: Passing at 1 through 3 and Stopping at 4 with (20, 30) is a pure strategy Nash equilibrium outcome:
  • If 2 anticipates that 1 will stop at 5, then it is a best response for 2 to stop at 4 and get (20, 30) which is better than (50, 20) for player 2.
  • The passing at nodes 1 through 3 are also best responses, as are any actions after node 4           since they are never reached

    4.  
Which are pure-­‐strategy Nash equilibrium outcomes?
a) Stopping at node 1 with (10, 0).
b) Passing at nodes 1 to 5 and Stopping at node 6 with (0, 10).
c) Passing at nodes 1 to 6 with (10, 10).
d) Both (a) and (c).
Solution: It is easy to check that both (a) and (c)are pure strategy Nash equilibrium outcomes since no one could gain by deviating.
  • Checking that (b) is not an equilibrium:if 2 stops at node 6 and to reach (0, 10), then 1 has an incentive to stop at node 5 (or even 1 or 3) to get (10, 0) instead of passing.



 5. List all the pure strategy Nash Equilibriums in “Entry Game” discussed in theory.
Solution:
  • (Stay out, Fight) is a pure strategy Nash equilibrium.
  • (Enter, Accommodate) is another pure strategy Nash equilibrium:
            If 1 enters, it is better for 2 to accommodate than fight;
            If 2 accommodates when 1 enters, it is better for 1 to enter than stay out.
  • Thus, the strategies are best responses to each other.




6.Two people select a policy that affects them both by alternately vetoing policies until only one remains. First person 1 vetoes a policy. If more than one policy remains, person 2 then vetoes a policy. If more than one policy still remains, person 1 then vetoes another policy. The process continues until only one policy has not been vetoed. Suppose there are three possible policies, X, Y, and Z, person 1 prefers X to Y to Z, and person 2 prefers Z to Y to X. Model this situation as an extensive game and find its Nash equilibria

Solution:
Suppose 1 vetoes X , then 2 will veto Y to get maximum payoff while for 1 his payoff will be minimum; so X isnt feasible. Similarly Y isnt feasible.
So 1 will veto Z(also his least favoured policy) and 2 can veto either X or Y but to get max. payoff he will veto X.
Therefore (Z,X) is Nash Equilibrium.




7.Consider this centipede game:
Which is false regarding the backward induction solution?
  1. At node 3, player 1 prefers to stop to get (30, 5).
  2. At node 6, player 2 prefers to stop to get (30, 10).
  3. At node 4, player 2 prefers to stop to get (20, 30).
  4. At node 5, player 1 prefers to stop to get (50, 20).

Solution: 2. is False as player 2 would like to pass to get 40.



8.

What is player 2s knowledge of player 1s choice?
Solution: Looking at the information set of 2 we deduce player 2 knows nothing about 1’s choice.




9.
     What is player 2s knowledge of player 1s choice?
Solution: Looking at the information set player 2 cant distinguish between Choices “B” & “C”.
               But there is also a singleton information set, so player 2 can distinguish between “A” & set {B,C}.




10.

What is the outcome of a subgame perfect equilibrium?
Solution: In the subgame following 1 choosing Football, it is (uniquely) optimal for 2 to choose Football; in the subgame such that 1 chooses Movie, it is (uniquely) optimal for 2 to choose Movie.
Then 1 prefers Football leading to (Football , Football ) with (3, 1) to Movie leading to (Movie , Movie ) with (1, 3).


11. Consider the following game consisting of Players 1 and 2.
Player 1 makes an offer x in {0,1,...10} to player 2. Player 2 can accept or reject. 1 gets 10-x and 2 gets x if accepted; Both get 0 if rejected. Model this game as an Extensive Game.
Solution:




12. Find the Nash Equilibrium in the previous game using backward induction
Solution:  Player 2 will accept every positive x.
If offered 0, Player 2 is indifferent could accept or reject.Player 1 offers either 0 or 1 depending on 2’s decision at 0.



13. Consider the modified bargaining game(previous ques. game):
  • Player A makes an offer x in {0,1,...10} to player B; Player B can accept or reject, if accepted A gets 10-x and B gets x. If rejected both get 2. What are the possible outcomes from backward induction?
Solution: In the subgame, it is optimal for B to accept when x>2, and reject when x<2. ;When x=2, B is indifferent.
So whenever B is offered x>2 it is a possible outcome by backward induction. Note that x=2 isn’t a possible outcome by backward induction because B may accept or reject the offer.



14. Consider the game in previous question. What are the possible outcomes by backward induction if instead of 2 both get 4 on rejection by B
Solution:  Solving on similar lines as the previous question it is easy to see all outcomes with x>4 are possible.



15. Army 1, of country 1, must decide whether to attack army 2, of country 2, which is occupying an    island between the two countries. In the event of an attack, army 2 may fight, or retreat over a bridge to its mainland. Each army prefers to occupy the island than not to occupy it; a fight is the worst outcome for both armies. Model this situation as an extensive game with perfect information .

Solution:



16.show that army 2 can increase its subgame perfect equilibrium payoff (and reduce army 1’s payoff) by burning the bridge to its mainland, eliminating its option to retreat if attacked.
Solution:  Look at the the game tree in previous solution.
Suppose army 2 burns the bridge, they have now only one option available i.e. to fight. as now they can not retreat. So if army 1 attacks it will definitely get a payoff -1. Thus only subgame perfect equilibrium is “Not Attack” and we see army 2 gets maximum payoff possible i.e. 2.


17.An incumbent in an industry faces the possibility of entry by a challenger. First the challenger chooses whether or not to enter. If it does not enter, neither firm has any further action; the incumbent’s payoff is M and the challenger’s payoff is 0. If the challenger enters, it pays the entry cost f > 0, and the incumbent first commits to fight or cooperate with the challenger , then the challenger chooses whether to stay in the industry or to exit. If,  the challenger stays in, each firm obtains in that period the profit −F < 0 if the incumbent fights and C > max{F, f } if it cooperates. If,  the challenger exits, both firms obtain the profit zero (regardless of the incumbent’s action); .  Model this situation as an Extensive Game.
Solution:



18. Find the Subgame Perfect equilibrium in the previous question.
Solution:  There are four subgames as shown below.

In red subgame 1 will prefer to exit while in brown it will choose to stay, but payoffs is higher in the latter . While in yellow subgame 2 is better off cooperating. Clearly in blue subgame 1 will prefer to enter.
1’s actions are therefore {Enter, Stay}
and 2 will cooperate.



19. Tic Tac Toe has subgame perfect equilibria in which the first player puts her first X in a corner. The second player’s move is the same in all these equilibria. What is it?
Solution: By intuition it can be guessed that the answer should be the Middle block as it is the only invariant position w.r.t all corners.
Another approach can be to model this as an extensive game but that can be quite cumbersome because of large number of moves available to each player. We solve this here by rigorous analysis.Player 1 puts a red cross in the corner as shown while player 2 puts circle in the middle. we have to show  now player 1 can not win. Now suppose the player 1 is to put a cross either in upper right corner or at the bottom left(as the positions in a way are equivalent) Suppose it is bottom left. Then player 2 is forced to put a circle in in middle left which in turn forces player 1 to put cross at middle right. Thus game ends in a draw
If player 1 puts a cross at bottom right in his second move and as a counter move if player 2 puts a circle in any corner he will lose so he puts a circle in middle row(either left or right) and the game ends in a draw which is the best player 2 can hope for as the tick tack toe is biased towards the player with first move.



20. An object that two people each value at v (a positive integer) is sold in an auction. In the auction, the people alternately have the opportunity to bid; a bid must be a positive integer greater than the previous bid. On her turn, a player may pass rather than bid, in which case the game ends and the other player receives the object; both players pay their last bids (if any). (If player 1 passes initially,
for example, player 2 receives the object and makes no payment; if player 1 bids 1, player 2 bids 3, and then player 1 passes, player 2 obtains the object and pays 3, and player 1 pays 1.) Each person’s wealth is w, which exceeds v; neither player may bid more than her wealth. For v = 2 and w = 3 model the auction as an extensive game.
Solution: ...................
The game above will continue in a similar fashion until one player does not bid and the game stops.




21. Find the previous game’s subgame perfect equilibrium.
Solution: Consider the smallest subgame. In that player making the choice will rather bid than not because if he does not he will get a negative payoff which we can safely assume will be greater (more negative)than(in any case) than -1 which he will get when he bids 3. So each player is better off bidding(but remember he may still get a negative payoff).
Now consider the beginning of the game. if 1 bids then atleast one of the players will get a negative payoff and each of them will try to avoid it by bidding at each turn hoping other player does not bid(that will not happen) . So player 1 will not bid at all and earn a nonnegative payoff and player 2 gets 2 which is the best possible outcome  for both of them.



22. A set H of sequences (finite or infinite):
Ht : The set of all possible histories up to time t.
H =UHt
Each component of a history is an action taken by a player.
P is the player function, P(h) being the player who takes an action after the history h.
Payoff function for player i is Ui : H →R
Now prove the following lemma:
The strategy profile s*is a subgame perfect equilibrium if and only if for every player i ϵ N and every history h ϵ  H for which P(h) = i and for every ai ϵ  Ai(h), the following holds: Ui(s*|h) ≧ Ui(s* −i|h, si) such that si differs from s* i |h only in the action ai after the history h.
Solution: If s is a subgame perfect equilibrium then it is resilient to any deviation. ( Suppose s is not an Sub Game perfect equilibrium. Then exists a history h in which player P(h) prefers to change her strategy. Let h be the longest history as above. For P(h) = i she can change to some action ai ∊Ai(h) and increase her payoff. Therefore there exists a single action as presented in the lemma.





23. Prove the following theorem: Every extensive game with perfect information has a subgame perfect equilibrium.
Solution: Use a backwards induction procedure.start from the leaves and walk up through the tree layer by layer. For each vertex located at a path determined by history h, player P(h) chooses her best action (Best Response). By previous lemma this profile is a subgame perfect equilibrium.



24. A group of n people have to share k objects that the value differently. Each person assigns values to the objects; no one assigns the same value to two different objects. Each person evaluates a set of objects according to the sum of the values she assigns to the objects in the set.
The following procedure is used to share the objects. The players are ordered 1 through n. Person 1 chooses an object, then person 2 does so, and so on; if k > n, then after person n chooses an object, person 1 chooses a second object, then person 2 chooses a second object, and so on. Objects are chosen until none remain. Denote by G(n, k) the extensive game that models this procedure. If k ≤ n then obviously G(n, k) has a subgame perfect equilibrium in which each player’s strategy is to choose her favorite object among those remaining when her turn comes.Show that if k > n then G(n, k) may have no subgame perfect equilibrium in which person 1 chooses her favorite object on the first round.(use the example where n=2, k=3)

Define xk to be the object least preferred by the person who does not choose at stage k (i.e. who
does not choose the last object); define xk−1 to be the object, among all those except xk, least preferred by the person who does not choose at stage k − 1. Similarly, for any j with 2 ≤ j ≤ k, given xj, . . . , xk, define xj−1 to be the object, among all those excluding {xj, . . . , xk}, least preferred by the person who does not choose at stage j − 1. Show that the game G(2, 3) has a subgame perfect equilibrium in which for every j = 1, . . . , k the object xj is chosen at stage j.

Solution: Let n = 2 and k = 3, and call the objects a, b, and c. Suppose that the values
person 1 attaches to the objects are 3, 2, and 1 respectively,while the values player 2
attaches are 1, 3, 2. If player 1 chooses a on the first round, then in any subgame
perfect equilibrium player 2 chooses b, leaving player 1 with c on the second round.
If instead player 1 chooses b on the first round, in any subgame perfect equilibrium
player 2 chooses c, leaving player 1 with a on the second round. Thus in every
subgame perfect equilibrium player 1 chooses b on the first round (though she
values a more highly.)
Any object chosen by player 1 in round 1, in any subgame perfect equilibrium player 2 chooses her
favorite among the two objects remaining in round 2. Thus player 2 never obtains the object she least prefers; in any subgame perfect equilibrium, player 1 obtains that object. Player 1 can ensure she obtains her more preferred object of the two remaining by choosing that object on the first round. That is, there is a subgame perfect equilibrium in which on the first round player 1 chooses her more preferred object out of the set of objects excluding the object player 2 least prefers, and on
the last round she obtains x3. In this equilibrium, player 2 obtains the object less preferred by player 1 out of the set of objects excluding the object player 2 least prefers. That is, player 2 obtains x2.


25.The set of actions available to player 1 is A1; the set available to player 2 is A2. Player 1’s preferences over pairs (a1, a2) are represented by the payoff u1(a1, a2), and player 2’s preferences are represented by the payoff u2(a1, a2). Compare the Nash equilibria (in pure strategies) of the strategic game in which the players choose actions simultaneously with the subgame perfect equilibria of the extensive game in which player 1 chooses an action, then player 2 does so. (For each history a1 in the extensive game, the set of actions available to player 2 is A2.)
Show that if, for every value of a1, there is a unique member of A2 that maximizes u2(a1, a2), then in every subgame perfect equilibrium of the extensive game, player 1’s payoff is at least equal to her highest payoff in any Nash equilibrium of the strategic game.
Solution: Denote by (a*1, a* 2 ) a Nash equilibrium of the strategic game in which player 1’s payoff is maximal in the set of Nash equilibria. Because (a*1, a* 2 ) is a Nash equilibrium, a* 2 is a best response to a* 1. By assumption, it is the only best response to a* 1. Thus if player 1 chooses a* 1 in the extensive game, player 2 must choose a* 2 in any subgame perfect equilibrium of the extensive game. That is, by choosing a*1, player 1 is assured of a payoff of at least u1(a*1, a*2 ). Thus in any subgame perfect equilibrium player 1’s payoff must be at least u1(a* 1, a* 2).



26. Consider the previous question:
Show that player 2’s payoff in every subgame perfect equilibrium of the extensive game may be higher than her highest payoff in any Nash equilibrium of the strategic game.
Solution: Suppose that A1 = {T, B}, A2 = {L, R}, . The strategic game has a unique Nash equilibrium, (T, L), in which player 2’s payoff is 1. The extensive game has a unique subgame perfect equilibrium, (B, LR) (where the first component of player 2’s strategy is her action after the history T and the second component is her action after the history B). In this subgame perfect equilibrium player 2’s payoff is 2.
1/2LR
T1,14,0
B0,02,2





27. Consider the question 25:
Show that if for some values of a1 more than one member of A2 maximizes u2(a1, a2), then the extensive game may have a subgame perfect equilibrium in which player 1’s payoff is less than her payoff in all Nash equilibria of the strategic game
Solution: Suppose that A1 = {T, B}, A2 = {L, R}, and the payoffs are those given below. The strategic game has a unique Nash equilibrium, (T, L), in which player 2’s payoff is 2. A subgame perfect equilibrium of the extensive game is (B, RL) (where the first component of player 2’s strategy is her action after the history T and the second component is her action after the history B). In this subgame perfect equilibrium player 1’s payoff is 1.

1/2LR
T2,20,2
B1,13,0




28. The ancient game of “Three Men’s Morris” is played on a tic tac toe board. Each player has three counters. The players move alternately. On each of her first three turns, a player places a counter on an unoccupied square. On each subsequent move, a player may move a counter to
an adjacent square (vertically or horizontally, but not diagonally). The first player whose counters are in a row (vertically, horizontally, or diagonally) wins. Find a subgame perfect equilibrium strategy of player 1, and the equilibrium outcome.
Solution: Number the squares 1 through 9, starting at the top left, working across each row.
The following strategy of player 1 guarantees shewins, so that the subgame perfect
equilibrium outcome is that she wins. First player 1 chooses the central square (5).
  • Suppose player 2 then chooses a corner; take it to be square 1. Then player 1 chooses square 6. Now player 2 must choose square 4 to avoid defeat; player 1 must choose square 7 to avoid defeat; and then player 2 must choose square 3 to defeat (otherwise player 1 can move from square 6 to square 3 on her next turn). If player 1 now moves from square 6 to square 9, then whatever player 2 does she can subsequently move her counter from square
           5 to square 8 and win.
  • Suppose player 2 then chooses a noncorner; take it to be square 2. Then player 1 chooses square 7. Now player 2 must choose square 3 to avoid defeat; player 1must choose square 1 to avoid defeat; and then player 2must choose square 4 to avoid defeat (otherwise player 1 can move from square 5 to square 4 on her next turn). If player 1 now moves from square 7 to square 8, then whatever player 2 does she can subsequently move from square 8 to square 9 and win.