Information sets > Information sets are the most important components of an extensive form game > These are collections of decision nodes such that > same choice of decisions are available at every node in an information set (requirement) > Perfect Recall (assumption) ® no node in an information set is a predecessor or successor of another node in the set > Consider a pair of nodes x, x’ in an information set of a player i, Hi(x). If a is a past action taken by player i at decision node x” on the path to x, then there must be x” € H,(x’) such that a is on the path from x’” to x’Past Exam question 1. A criminal has been arrested and brought to a police station where a lonely constable is on guard. ‘The criminal can decide whether to rim away to a hideout to the right of the police station or face further proceedings. If he does not run away, he gets a payoff of -1, and the constable gets a payoff of 0. If he runs away, the constable will chase him. If the constable goes to the right, he is able to catch the criminal — the criminal gets a payoff of -2, and the constable gets a payoff of 1 If the constable goes to the left, the road will return him to the police station. He then chases again, deciding whether to go to the right or left. If he goes to the right, he is able to catch the criminal —— the criminal gets a payoff of -2, and the constable gets a payoff of 1. If he goes to the left, he returns to the police station. At this point, he gives up the chase, and both the criminal and the constable get a payoff of 0. (a) ‘Treat this situation as a dynamic game of perfect information and draw the corresponding game tree. (1) (b) Provide the normal form of the game you deseribed above as a payoff matrix. Identify the Nash equilibrium outcomes. Which Nash equilibria you identified in the last part are “reasonable” and why? (3) (c) Now consider the following twist in the story above: if the consta- ble takes the left road and returns to the station, he forgets that he had taken the wrong road. Draw the game tree corresponding to this new situation, (1) Dh aor ekPerfect vs imperfect information > A game in extensive form having only singleton information sets is a game of perfect information > Example @,0, are games of perfect information > A game having at least one non-singleton information set is a game of imperfect information > Example ©, ©, are games of imperfect information > Every one-shot/static/simultaneous move game is a game of imperfect information, e.g., the one-shot prisoner's dilemmaGame tree for one-shot Prisoner's dilemmaComplete vs Incomplete Information >» A game of incomplete information involves payoff uncertainty for players » These are usually modelled by nature selecting a state of the world using a probability distribution GAZ > A game of complete information may be a game of imperfect information G52 or it may be one of perfect information exp >» A game of incomplete information is always a game of imperfect informationA static game of incomplete information in extensive formStrategies in extensive form > Recall that a strategy of a player is a complete contingent action plan > In extensive form, the information sets of a player represent these contingencies where he must take a decision > Consequently, a (pure) strategy for a player in an extensive form game, denoted s;, maps his information sets to the set of actions that are available to him in these sets: si:H; > A, 5;(H;) € e(Hj). > The collection of all possible strategies of a player / is referred to as his strategy set, denoted 5;Mixed and Behavioral Strategies > A mixed strategy is a probability distribution over pure strategies > A behavioral strategy specifies probability distributions over feasible actions for each information set >» A mixed strategy can induce a behavioral strategy and vice-versa, if the game is one of perfect recallEquivalence of normal and extensive forms > Every tuple of strategies in an extensive form game induce a path of play originating in an initial node and ending in a terminal node: Check Examples ®, ©, » Therefore, we can associate the payoff vector assigned to this terminal node to the tuple of strategies and present the game in the familiar normal /matrix form > As long as each strategy in normal form clearly assigns an action to each contingency, we can convert it into an extensive formNormal form of Example 1 Player E Player | accommodate | fight enter 1,1 -1,-1 not enter 0, 2 0, 2Normal form of Example 5 > Both players have 5 information sets GID > Both players have choice of two actions in each of their information sets > Consequently, there are 2° = 32 strategies for each player in this gameNormal form of Player F wawy | Wow, | wew, | WLwy eHeH Player E | ewer eLeH eetNash equilibrium > The idea of Nash equilibrium generalizes easily from static to dynamic games after acknowledging the general definition of strategies >» A Nash equilibrium for an extensive form game is a collection of strategies s* = (sf,...,s7) such that for all i € /, 5; € S;, uj(s*) > uj(sj, 5" ;) for all s*; > Nash equilibria of are displayed in red