Recommended books for Game Theory enthusiasts
------------------------------------xx----------------------------------------- A Tutorial on Extensive Form Games Extensive Form Games - Games with Perfect and Imperfect Information These types of games can be further classified into two types:
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.
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
succ(x) = { x’ | x > x’, and there is no x’’ s.t. x > x’’ > x’ }
Pure StrategyFor 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
Behavioural Strategy
a distribution over actions in A(x)
Nash Equilibrium
Centipede Game
stop at the previous 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 InductionAlgorithm
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 InformationGames 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:
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
Ii ⊂ Xa
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 EquilibriumThe 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.
Example: In the Bos game one such sub-game is shown below: Sub-game perfection
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.
Exercises : Solved Problems
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:
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.
5. List all the pure strategy Nash Equilibriums in “Entry Game” discussed in theory. Solution:
If 2 accommodates when 1 enters, it is better for 1 to enter than stay out.
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?
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):
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.
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.
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).
In case you're interested, here are the Game Theory tutorials we have : |