MS&E246:Lecture8DynamicgamesofcompleteandimperfectinformationRamesh JohariOutline• Imperfect information• Information sets• Perfect recall•Moves by nature•Strategies• Subgames and subgame perfectionImperfectinformationInformally:In perfect information games, the history is common knowledge.In imperfect information games, players move without necessarily knowing the past.GametreesWe adhere to the same model ofa game tree as in Lecture 6.1) Each non-leaf node v is identified with aunique player I(v).2) All edges out from a node v correspond to actions available to I(v).3) All leaves are labeled with the payoffsfor all players.InformationsetsWe represent imperfect information by combining nodes into information sets.An information set h is:-a subset of nodes of the game tree-all identified with the same player I(h)-with the same actions available toI(h) at each node in hInformationsetsIdea:When player I(h) is in information set h, she cannot distinguish betweenthe nodes of h.InformationsetsLet H denote all information sets.The union of all sets h ∈ Hgives all nodes in the tree.(We use h(v) to denote the information set corresponding to a node v.)PerfectinformationFormal definition of perfect information:All information sets are singletons.(1,2)ExampleCoordination game without observation:122RLlrRL(2,1)(0,0)(0,0): Player 2 cannot distinguish between these nodesPerfectrecallWe restrict attention to games ofperfect recall:These are games where the information sets ensure a player never forgets whatshe once knew, or what she played.[Formally:If v, v’ are in the same information set h, neither is a predecessor of the other in the game tree.Also, if v’, v’’ are in the same information set, and v is a predecessor of v’, then there must exist a node w ∈ h(v) that is a predecessor of v’’, such that the action taken on the path from v to v’ is the same as the action taken on the path from w to v’’. ]MovesbynatureWe allow one additional possibility:At some nodes, Nature moves.At such a node v, the edges are labeled with probabilities of being selected.Any such node v models an exogenous event.[Note: Players use expected payoffs.]StrategiesThe strategy of a player is a function from information sets of that playerto an action in each information set.(In perfect information games,strategies are mappings from nodes to actions.)Example1222lmrLRRBLAExample1222lmrLRRBLAPlayer 1: 1 information set3 strategies – l, m, rExample1222lmrLRRBLAPlayer 2: 2 information sets4 strategies – LA, LB, RA, RBSubgamesA (proper) subgame is a subtree that:-begins at a singleton information set;-includes all subsequent nodes;-and does not cut any information sets.Idea:Once a subgame begins, subsequent structure is common knowledge.Example1.12.22.12.1lmrLRRBLAThis game has two subgames, rooted at1.1 and 2.2.ExtendingbackwardinductionIn games of perfect information,any subtree is a subgame.What is the analog of backward induction?Try to find “equilibrium” behavior from the “bottom” of the tree upwards.SubgameperfectionA strategy vector (s1, …, sN) is a subgame perfect Nash equilibrium (SPNE)if it induces a Nash equilibrium in (the strategic form of) every subgame.(In games of perfect information,SPNE reduces to backward induction.)Subgameperfection“Every subgame” includes the game itself.Idea:-Find NE for “lowest” subgame-Replace subgame subtree with equilibrium payoffs-Repeat until we reach the root nodeof the original gameSubgameperfection• As before, a SPNE specificies a complete contingent plan for each player.•The equilibrium path is the actual play of the game under the SPNE strategies.• As long as the game has finitely many stages, and finitely many actions at each information set, an SPNE always