1Lecture 3 Game Theory14.12 Game Theory Muhamet YildizRoad Map1. Quiz2. Representation of games in strategic and extensive forms3. Quiz?2Multi-person Decision Theory• Who are the players?• Who has which options?• Who knows what?• Who gets how much?Knowledge1. If I know something, it must be true.2. If I know x, then I know that I know x.3. If I don’t know x, then I know that I don’t know x.4. If I know something, I know all its logical implications.Common Knowledge: x is common knowledge iff •Each player knows x•Each player knows that each player knows x• Each player knows that each player knows that each player knows x•Each player knows that each player knows that each player knows that each player knows x•… ad infinitum3Representations of gamesNormal-form representationDefinition (Normal form): A game is any list where, for each • Siis the set of all strategies available to i,• is the VNM utility function of player i.},,,2,1{ nNi K=∈()nnuuSSG ,,;,,11KK=ℜ→××niSSu L1:Assumption: G is common knowledge. Definition: A player i is rational iff he tries to maximize the expected value of uigiven his beliefs.4Chicken(1/2,1/2)(0,1)(1,0)(-1,-1)Extensive-form representationDefinition: A tree is a set of nodes connected with directed arcs such that 1. For each node, there is at most one incoming arc; 2. each node can be reached through a unique path;5A tree?A tree??ABCABCD6A treeTerminal NodesNon-terminal nodesExtensive form – definitionDefinition: A game consists of – a set of players–a tree– an allocation of each non-terminal node to a player– an informational partition (to be made precise)– a payoff for each player at each terminal node.7Information setAn information set is a collection of nodes such that1. The same player is to move at each of these nodes;2. The same moves are available at each of these nodes. An informational partition is an allocation of each non-terminal node of the tree to an information set.A game1112(2,2)(1,3) (3,1)(3,3)(1,1)(0,0)LRlrλρΛΡu8Another Game1BTx2L R RLThe same game1 xTB2 LRLR9StrategyA strategy of a player is a complete contingent-plan, determining which action he will take at each information set he is to move (including the information sets that will not be reached according to this strategy).Matching pennies with perfect information2’s Strategies:HH = Head if 1 plays Head, Head if 1 plays Tail;HT = Head if 1 plays Head, Tail if 1 plays Tail;TH = Tail if 1 plays Head, Head if 1 plays Tail;TT = Tail if 1 plays Head, Tail if 1 plays Tail.122HeadTailhead tailhead tail(-1,1) (1,-1)(1,-1) (-1,1)10Matching pennies with perfect informationTailHeadTTTHHTHH12Matching pennies with Imperfect information12HeadTailhead tailhead tail(-1,1) (1,-1)(1,-1) (-1,1)(-1,1)(1,-1)Tail(1,-1)(-1,1)HeadTailHead1211A game with natureNatureHead1Left(5, 0)(2, 2)RightTail2Left(3, 3)Right(0, -5)1/21/2A centipede game12ADαδ(4,4)