### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# GAMETHEORY ECON1200

Pitt

GPA 3.53

### View Full Document

## 123

## 0

## Popular in Course

## Popular in Economcs

This 159 page Class Notes was uploaded by Quentin Huel Jr. on Monday October 26, 2015. The Class Notes belongs to ECON1200 at University of Pittsburgh taught by Staff in Fall. Since its upload, it has received 123 views. For similar materials see /class/229427/econ1200-university-of-pittsburgh in Economcs at University of Pittsburgh.

## Popular in Economcs

## Reviews for GAMETHEORY

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

Simultaneous Moves Arise when players have to make their strategy choices simultaneousy without knowing the strategies that have been chosen by the other players Student studies for a test the teacher writes questions Two firms independently decide whether or not to develop and market a new product While there is no information about what other players will actually choose we assume that the strategic choices available to each player are known by all players Players must think not only about their own best strategic choice but also the best strategic choice of the other players We will consider both discrete and continuous strategy spaces Normal or Strategic Form A simultaneous move game is depicted in quotNormalquot or Strategic form using a game table that relates the strategic choices of the players to their payoffs The convention is that the row player s payoff is listed first and the column player39s payoff is listed second Column Player Row Strategy C1 Strategy C2 Player Strategy R1 a b c d Strategy R2 e f g h For example if Row player chooses R2 and Column player chooses C1 the Row player s payoff is e and the Column player s payoff is f Special ZeroSum Form For zero or constant sum games knowing the payoffs sum to zero or some other constant allows us to write a simultaneous move game in normal form more sim Warden Guard Wall Inspect Cells Prisoner Climb Wall 1 1 Dig Tunnel 1 1 Payoffs are shown only for the Prisoner the Warden s payoffs are the negative of the prisoner s payoff The Role of Beliefs When players move simultaneously what does it mean to say that in equilibrium strategies are a mutual best response One cannot see what the other is doing and condition your behavior on their move n simultaneous move games rational players consider all of the strategies their opponents may take and they form beliefs subJective I robabilities about the likelihood of each strategy their opponents could take After forming these beliefs rational players maximize their expected payoff by choosing the strategy that is a best response to their beliefs about the play of their opponents The same is true of the opponents Example of the Role of Beliefs Consider the following simultaneousmove game Column Player Row Left Right Player Up 0 O 1 1 Down 1 1 O 0 Suppose Row player assigns probability pgt5 to column player playing Right Then Row s best response to this belief is to play Up Row s expected payoff from playing Up is O1p1pp while Row s expected payoff from playing Down is 11p Op1p Since we assumed pgt5 the expected payoff to Row from playing Up p is greater than the expected payoff to Down 1p How Might Such Beliefs be Formed Players subjective beliefs about the play of an opponent in a simultaneous move game may be formed in one of several ways lntrospection given my knowledge of the opponent s payoffs what would I do if I were the other player History repeated games only what strategy has the same opponent played in the past Imitationlearning from others what strategies have players other than my current opponent chosen in this type of strategic setting Prepay communication Other type of signaling We focus for now on the first introspective method Pure vs Mixed Strategies A player pursues a pure strategy if she always chooses the same strategic action out of all the strategic action choices available to her in every round eg Always refuse to clean the apartment you share with your roommate A la er pursues a mixed strategy if she randomizes in some manner among the strategic action choices available to her in every round eg Sometimes pitch a curveball sometimes a slider quotmix it up quotkeep them guessing We focus for now on pure strategies only Example Battle of the Networks Suppose there are just two television networks Both are battling for shares of viewers 0100 Higher shares are preferred higher advertising revenues Network 1 has an advantage in sitcoms If it runs a sitcom it always gets a higher share than if it runs a game show Network 2 has an advantage in game shows If it runs a game show it always gets a higher share than if it runs a sitcom Network 2 Sitcom Game Show Network 1 Sitcom 55 45 52 48 Game Show 50 50 45 55 Nash Equilibrium We cannot use rollback in a simultaneous move game so how do we find a solution We determine the quotbest response of each player to a particular choice of strategy by the other player We do this for both players Note that in thinking of an opponent s best response we are using introspection to form beliefs about what the rational opponent will do If each player s strategy choice is a best response to the strategy choice ofthe other player then we have found a solution or equilibrium to the game This solution concept is know as a Nash equilibrium after John Nash who first proposed it A game may have 0 1 or more Nash equilibria Best Response Analysis Best response analysis aka cell by cell inspection is the most reliable for method for finding Nash equilibria First Find Network 4 s best response to Network 2 s possible strategies If Network 2 runs a sitcom Network 1 s best response is to run a sitcom Circle Network 1 s payoff in this case 55 If Network 2 runs a game show Network 1 s best response is to run a sitcom Circle Network J payoff in this case 52 Network 2 itcom G n e Show Network 1 Sitcom 45 48 Game Show 50 50 45 55 Best Response Analysis Continued Next we find Network 2 s best response f Network 1 runs a sitcom Network 2 s best response is to run a game show Circle Network 2 s a off in this case 48 f Network 1 runs a game show Network 2 s best response is to run a game show Circle Network 2 s payoff in this case 55 The unique Nash equilibrium is for Network 1 to run a sitcom and Network 2 to run a game show This is found by the cell with the two circled payoffs This is the method Of best response analysis for locating Nash equilibria Network 2 itcom neSw Network 1 sitcom 45 Game Show 50 50 45 Dominant Strategies A player has a dominant strategy if it outperforms has higher I aoff than all other strategies regardless of the strategies chosen by the opposing players For exam leg in the battle of the networks 39ame Network 1 has a dominant strategy of always choosing to run a sitcom Network 2 has a dominant strategy of always choosing to run a game show VVhy Successive elimination of nondominant or quotdominatedquot strategies can help us to find a Nash equilibrium Successive Elimination of Dominated Strategies Another way to find Nash equilibria Draw lines through successively eliminate each player s dominated strategys Ifsuccessive elimination of dominated strategies results in a unique outcome that outcome is the Nash equilibrium ofthe game We call such games dominance solvable But not all games have unique equilibriaare dominance solvable so this method will not work as generally as best response analysis Network 2 Site m Game Show Network 1 Sitcom 55 5 52 48 Gain Show DUo 3 70 45 55 Minimax Method For zero or constantsum games only so not so general Each player reasons that what s good for me is bad for my opponent Suppose payoffs are written for row only Network game is constantsum Row looks only at the lowest payoff in each row and chooses the row with the highest of these lowest a offs maximizes the minimum Network 1 chooses sitcom because 52 gt 48 Column looks only at the highest payoffs in each column and chooses the row with the lowest of these highest I aoffs minimizes the maximum Network 2 chooses game show because 52lt55 Network 2 Sitcom GameShow Row Min Network 1 Sitcom 55 Game Show 50 45 45 Column Max 55 Adding More Strategies Suppose we add a third choice of a quottalent show to Battle of the Networks Network 2 Sitcom Game Show Talent Show Sitcom 55 45 52 48 51 49 Networkl Game Show 50 50 45 55 46 54 TalentShow 5248 4951 4852 What is the Nash equilibrium in this case First ask are there any dominated strategies If so eliminate them from consideration Eliminating the Dominated Strategies Reduces the Set of Strategies that May Comprise Nash Equilibria Network 2 Sitc m Game Show Talent Show Sitcom 55 5 52 48 51 49 NEtwork 1 Galllc Show 5076 Uo 4370 5570 45 54 TalentShow 52 8 4951 4852 A game show is a dominated strategy for Network 1 A sitcom is a dominated strategy for Network 2 Continuing the search for dominated strategies among the remaining choices Network 2 Nash Equilibrium Talent Show 51 49 Sitc 3m Game Show Sitcom 55 45 52 48 NEtwork 1 Galllc SlIUW 5073 Uo 4570 5570 40 54 Talent o39now 540 l o 430 51o 460 540 Talent show is now a dominated strategy for Network 1 Game show is now a dominated strategy for Network 2 Best Response Analysis Also Works Network 2 Nash Equilibrium 39tcom n eShow Ta t no Sitcom 45 48 Network 1 Game Show 50 50 45 46 54 Talent Show 52 48 49 51 48 Adding a Third Player Consider again the case of two strategies sitcom and game show and suppose there is a third player Network 3 The normalform representation of this threeplayer game is Network 3 Sitcom Game Show Network 2 Network 2 Sitcom Game Show Sitcom Game Show Sitcom 342541 323236 Sitcom 342937 383230 Network 1 Network 1 Game Show 323038 333136 Game Show 353827 363925 Network 3 s payoff is now the third percentage given What is the Nasn equilibrium of this game Use Best Response Analysis Network 3 Sitcom Network 2 Sitco Ga Sitcom 257 32 Sitcom Network 1 Network 1 Game Show 3230 Game Show Game Show Network 2 how Sitcom q 342937 30 3827 3625 Pure strategy Nash equilibrium to this game is for Network 1 to run a game show Network 2 to run a game show and Network 3 to run a sitcom NonConstantSum Games The Network Game is an example of a constant sum game The payoffs to both players always add up to the constant sum of 100 We could make that game zero sum by redefining payoffs relative to a 5050 share for each network Nash equilibria also eXIst in nonconstant sum or variable sum games where players may have some common interest For example prisoner s dilemma type games Payoffs are quotprofitsquot so more is better Burger King Value Meals No Value Meals McDonald s Value Meals 1 No Value Meals 1 3 3 More on Sequential and Simultaneous Move Games So far we have studied two types of games 1 sequeuuai mu v c mwusive form games mmc players take turns choosing actions and 2 strategic form normal form games where players simultaneously choose their actions Of course it is possible to combine both game forms as for example happens in the game of football The transformation between game forms may change the set of equilibria as we shall see We will also learn the concept of subgame perfection Combining Sequential and Simultaneous Moves Consider the followinD lslayer Dame where A layer 1 moves rst Stay Out Enter Player 2 A B 393 Player 1 A 292 390 B U Llfl If player 1 chooses to stay out both he and player 2 earn a 1 a off of 3 each but if 1 1a er 1 chooses to enter he plays a simultaneous move game with player 2 Forward Induction The simultaneous move game has 3 equilibria AA BB and a mixed strategy equilibrium Where both players play A with probability 13 and earn expected payoff 83 Stay Out Enter Player 2 A B 393 Player 1 A m 30 oo If player 2 sees that player 1 has chosen to Enter player 2 can use forward induction reasoning since player I chose to forego a payoff of 3 it is likely that he Will choose B so I should also choose B The likely equilibrium of the game is therefore Enter BB The IncumbentRim U39a111c 111 LALUHSiVe and Strategic Form Tlee emry1 I Enter Stay out inm Accnmmlm The Number of Equilibria Appears to be Different Tree emry1 I Subgame Perfection In the strategic form game there is the additional equilibrium Stay Out Figh hat U W an yum using rollback in the extensive form game Equilibria found by applying rollback to the extensive form game are referred to as subgame perfect equilibria every player makes a perfect best response at every subgame of the tree Enter Accommodate is a subgame perfect equilibrium Stay Out Fight is not a subgame perfect equilibrium 39 A subgame IS U16 game that nglflS at any HOGG OIV U16 deCISlon tree39 3 subgames circled are all the games beginning at all tree nodes including the root node game itself Imperfect Strategies are Incredible Strategies and equilibria that fail the test of subgame perfection are called imperfect The imperfection of a strategy that is part of an imperfect equilibrium is that at some point in the game it has an unavoidable credibility problem Consider for example the equilibrium Where the incumbent promises to ght so the rival chooses stay out The incumbent s promise is incredible the rival knows that if he enters the incumbent is sure to accommodate since if the incumbent adheres to his promise to ght both earn zero While if the incumbent accommodates both earn a 1 a off of 2 Thus Stay Out Fight is a Nash equilibrium but it is not a subgame perfect Nash equilibrium Lesson Every subgame perfect equilibrium is a Nash equlibrium but not every Nash equlibrium is a subgame perfect equilibrium Another Example Mutually Assured Destruction MAD Tree Tlltryg Q the rollback V H r 7 lumlnre Escalate I subgame perfCCt v equ111br1um quot xx x a to th1s game liailg Digwnil E 93a3 nunj o quotquot quot 39quotquot 13939L 39i u 39 339 6 L a Ex 37 quot quot Subgames must 336 DOW Elke Lac 070wquot 1 3mg n l l I 39 contain all nodes in an 12 quot I 1 V t infomth set it il 393939 quot quot 10 The Strategic Form Version of the Game Admits 3 Nash Equilibria Which Equiliinan is Subgame Perfect Only the equilibrium Where the strategies Escalate Back Down are played by both the US and Russia is subgmne perfect 7 Why b rom Slmultaneous t0 Sequentlal MOVES Conversion from simultaneous to sequential moves involves determining who moves rst which is not an issue in the simultaneous move game In some games where both players have dominant strategies it does not matter who moves rst For example the prisoner s dilemma game When neither player has a dominant strategy the subgame perfect equilibrium will depend on the order in which players move For example the Senate Race Game the Pittsburgh Left 1 urn uame The Equilibrium in Prisoner s Dilemma is the Same Regardless of Who Moves rst TYEBEIVLIE This simultaneous move game is equivalent to either of the 2 Duncomessl lConfess DumCumess Cm essl sequential move 4 v n gamesbebmt39 ME Dnnl Confess l canfssl Tm A g l cfmessl iciu39lel lnmncl l 1c l imam as mews 2mg 1 l l I v v v i l l v v The Senate Race Game has a Different Subgame Perfect Equilibrium Depending on Who moves rst In the simultaneous move game there is only one Nash equilibrium subgame perfect eq subgame perfect eq Similarly in the Pittsburgh LeftTurn Game Duver 1 Driver 2 gt Yield Yleld Driver 2 Proceed Yield Procee Yield Proceed Yleld Procee Yleld 10 10 1490 1490 5 5 10 10 1490 1490 5 5 These subgame perfect equilibria look the same but if Driver 1 moves first he gets a payoff of 5 While if Driver 2 moves first Driver 1 gets a payoff of 5 and vice versa for Driver 2 Going from a Simultaneous Move to a Sequential Move Game may eliminate the play of a mixed strategy equilibrium This is true in games with a unique mixed strategy Nash equilibrium Example The Tennis Game Venus Williams DL CC Serena DL 50 50 80 20 Williams CC 90 10 20 8O The Pure Strategy Equilibrium is Different Depending on Who Moves First There is no possibility of mixing in a sequential move ame without an information sets Coordination Games and Continuous Strategy Spaces More Complicated Simultaneous Move Games 9302008 Coordination Games I Nonconstant sum games with multiple equilibria I For example the simultaneous move game considered previously Column player Raw Left Right Plzyel Up 00 11 Dawn 1 a a has two Nash equilibria What are they I This is a pure coordination game Other Coordination Games I Suppose you and a partner are asked to choose one element from the following sets ofchoices lfyou both make the same choice you earn 51 otherwise nothing 7 Red ul een Blue 7 Heads Tails 7 710013261555 I Write down an answertothe following questions Ifyour partnerwrites the same answeryou win 51 otherwise not ing 7 Apositive number 7 Amonth of the year 7 Awomansname AntiCoordination Games Not the same dressl Fashion Not the same wordsideas Writing LUPl a Swedish lottery game designed in Choose a positive integertrom 1 to 99 inclusive The winner is the one person who chooses the lowest unique positive integer LUPl it no unique integer ohoioe no winner 9302008 Another Example of Multiple Equilibria in Pure Strategies The AlphaBeta game Alpha SlralegleslorAlpha are Up lu Middle lMl or Down in tretegiesloraete are leltlll or Rightlhl What a rethe multiple Equlllb a in this game Why Finding Equilibria by Eliminating Dominated Strategies Strategies U and M are weakly dominated for Vlaver Alpha by srieregvo Supposewe eliminate srieregvu tiist The iesulringgeme is Ezln Mirna Can Lead to the Wrong Conclusion Suvvnsa instsa ws eiiminate NDha s M stratigv rst The resuitmg Eamsis am mane New n aWEars agtnnugn m We uninus Enmiihrium Lesson ifthere are weakiv dominated stratigies nnsi sr 3H Dnssihis nr arsfor ramnvmgthesa stratigiaswhen seartnmgfnrtne Nash enmiihria amegame 9302008 Finding Equi 39bria via Best Response Analysis Always Works a 390 u i a o o 0 mm There aretwo mutual best responses in and D RThese are the two Nash equilibria enhe game Cournot Competition AgamewnerstwnfirmsidunDnMnmvstsintsrmsnftninuantilvsni mane Fem eeanamwham eaaiea i n aerWeanheaaaamarearaaama a emememarkeareeeeaeemeaammaeme mean if agthin14nli otherwise me en Ma Firm 1 s profits arE min and firm 1 s profits ara wanna where a ME marginal tax apramna 2am um lmegaad Assumebmh rmssaaktnmaximilEDmfits Numerical Example Discrete Choices Suppose P 130q1q2 so a130 b1 The marginal cost per unit c10 for both firms Suppose there are just three possible quantities that each firm i12 can choose qi 30 40 or 60 There are 3x39 possible profit outcomes forthe two f39rms For example if firm 1 chooses 4130 and firm 2 chooses 4260 then P130306040 Firm 1 s profit is then Pcq1401030900 Firm 2 s profit is then Pcqz4010601800 9302008 Cournot Game Payoff Matrix Firm 2 qz30 qz40 qz60 q 30 1oo1oo 15002000 soo1oo 1 Firm 1 q 40 20001500 10001000 01200 1 q 60 quot00300 120mm 0 1 I Depicts all 9 possible profit outcomes for each firm Find the Nash Equilibrium Firm 2 qz30 qz40 qZ 60 q 30 1oo1oo 150 1 Firm 1 q 40 500 01200 1 q160 m Nash Equilibrium q60 is weakly dominatedfor both firms use cellrbyrcell inspection to complete the search for the equilibrium Continuous Pure Strategies In many instances the pure strategies available to players do not consist ofjust 2 or 3 choices but instead consist of linfinilelyl many possibilities We handlethese situations by finding each player s reaction function a continuous function revealing the action the player will choose as a function ofthe action chosen bythe ot er player For illustration purposes let us consider again the two firm ournot quantity competition game Duopoloy ltwo firms onlyl competition leads to an outcome in between monopoly 1 firm maximum possible profit and perfect competition lmanyfirms each earning 0 profits pcl 9302008 Profit Maximization with Continuous Strategies 39 Firm 1 5 profit Hi lPrclqilarblqiq2lrcl qilarqurcl qirblqilz Firm 2395 Pro le lPrcqularblqnqzlrcl qflarbqircl qz blqzlz Both firms seek to maximize profits We find the profit maximizing amount using calcu us Firm 1 d njdqasbq2sc72bq1 At a maximum d njdq0 qlasbq2scl2b This is firm 1 best response function Firm 2 d nzdq2asbqsc72bq2 At a maximum d nzdq20 oflarbquclz b This is firm 239s best response function in our numerical example firm 139s best response function is qfla qu ClZb 1130rq2710l260rq22 Similarly firm 239s best response function in ourexample is qflarbqirclZb 1130rq1710l260rqi2 Equilibrium with Continuous Strategies Equilibrium can be found algebraically or graphically Algebraically q60sq22 and q2 oral2 so substitute out using one ofthese equations qjeboelborqjzlz 60730qj4 so qjllr 14l30 also1540 Similarly you can showthat q240 aswell lthe problem is perfectly symmetric Graphically Multiple Equilibria Fact of Life or Problem to be Resolved Suppose we have multlple Nasn Equilibriz etne Alphasaeta game is an example what canwe say about the behzvlur or players in such games what n 9302008 aiaieaai drlve an me lei tn adapt some addltlond ortena DeyondmutuaDestresponse ror selecting rrom among multlple Equilibriz some criteria used are e raealnesssaieneelweneieareaoyseenmisinrneeaarainanangamesl e Felrnessenwrireenesslwehavedream seen misinmeapnepeagamel e nnaenwvaimaminanee e Rlskdamlnente Efficiency I In selecting from among multiple equilibria economists often make use of efficienc considerations which equilibrium is most efficient I An equilibrium is efficient ifthere exists no other equilibrium in which at least one player earns a higher payoff and no player earns a lower payoff Efficiency considerations require that all players know all payoffs and believe that all other player value efficiency as a selection criterion This may be unrealistic Considerthe Alphas eta game for example many pairs coordinate on DR over DL I Efficiency may be more relevant as a selection criterion if agents can communicatecollude with one another Why Line Formation as an Example There are two ways for a firm to line customers up to conduct business with spatially separated agents of the firm 1 There is a line for even agent and each customer chooseswhich line to get in ias atthe grocew store or a toll plazal or 2 There is one snake linequot and customers at the head of the line go tothe first agentwho becomes available ias at a bankor airport checksin counteri Ef ciency considerations govern the choice between these two line conventions Can you explain why Efficiency Considerations Cannot Always be d to Select an Equilibrium There can be muiti39pie Efficient equi39ii39bri39a Exampie 1 Driving on the ieft iuilti or right hand side iusi otthe road Exampie z The Pittsburgh LeftrTum Game i 9 u e u signai that she pianstu rna Driver 2 by nut signaiing indicates his pian istu prueee thruugh the intersectiun e The iight turnsgreen Drivers 1 and 2 havetu simuitzneuusiy decide whether tn pmcEEd With their piansurtu yieidtu the ether driver 7 what are the payuttstu each strategy 9302008 The Pittsburgh LeftTurn Game e payuers are in terms uf Driver 2 Plan pruceed secundsgaineduriust mmughtntersecuun Witnminussign m w in OLhsznv Prunede meme ss Dnveri man Plan make w s rmng ie tum OLhsznvex Equilibria in the Pittsburgh BathEuuiiihriahmeanedrivervramedimwhiietheatherweids In animate mg in such ssigawmmemsa ennevintaimvaseane V equihhrium bylaw This game is apzmcular Driver 2 Plan pruceed versmn uttne game at Lhmu 1 in ersecnun Chicken Pmmedwx i ta nan OLhsznv Pmceed min Vitamin ss p iml Driver 1 Plan make iemum Risk Considerations and Equilibrium Selection Consider the foiiowing game x Y X 75 75 25 50 Y 50 25 so so What are the Nash equilibria Which equilibrium do you think is the most likely one to be chosen 9302008 Computer Screen View Column Player Row Player Risk Dominance Thetwo equilibria are xx and vv xx is efficient aiso kn own aspayoffdominant but vv is less risky or what we call the risk dominant equilibrium w y x Y X 25 50 Y 50 25 In choosing v each piayer insures ninnseif a payoff of 50 regardiess of ategy whatthe other piayer does V is a riskrfree or quotsafequot str How can we evaluate the expected payoff from playing x The Principle of Insuf cient Reason fyuefe o eompfefefyfgnofam ofwmen ofn possfbfe omeomeswm oeeuf ESSng pmbabfhw 1mm eaen omeomewm oeeuf X X 75 75 25 60 Y 60 25 60 60 Appfyfngfms pnnopfe mmsfwo sxoxegame we ESSng probabmfymo nur opponem hnnsmgx a fenoosfngv nd pmbabfhw yam nur opponen hum pfayfng fne expeoeupayoffffom pfayfng x S Vansymzsleso fne expeoeupayoffffom pfayfng v S msmommeso SWEEME Expeded payoff msofsgfeafennen me expe ed payoff fmm pfayfng x 5m SME preferred EHmEE ff bum pfayep reasnnmfs wayfney end up my 9302008 Incomplete Information Games Games wnefe payoff fnfofmauon f5 fnoomp Consfdennefouowfng game You afefne mw player ete X Y X 75 75 25 a Y 60 25 60 a know 3 yom payoff ffom pfa Suppose you ave tofd tnat game fne payoffs exceptthe payofffne oowmn pfayen face was ffom pfayfng v wnfon f a Sfmffany fne oommn pfayen does not know in V a f39sef39thev 59 BY 51 How do you pfayfnfs Some Games Have No Equmbffum In Pure Strategies Some games naye no pme stvategy eoufffon39a sfden fov examp e fne foHowf39ng quotfennfsgame between fne Wf39Hf39ams 5 Con sfstevs Sevena and Venn Suppose Sevena f39sf39n a posmon to vetum fne baH and and can onoose tween a downrtherh39ne my passfng shot of a cvossrcomt co dfagonaf enus on defensef nas to guess wnaf Sevenawf H do and posmon nefseff accovdfngfy DL posmons Sevena fov the DL shot and Nov tne cc shot Payoff ave fne ffacu39on on of ffmes fnaf eaon pfayef wfns fne pofnf Venus Williams DLcc Serena I DL 50 50 80 20 Williams CC 9010 20 80 In such cases playing a pure strategy is usually not a winning strategy Using cellrbyrcell inspection we see thatthere is no pure strategy Nash equilibrium Serena s best response arrows do not point tothe same cell as Venus s best response arrows ch c n ases it is betterto behave unpredictably using a mixed strategy Venus Williams 9302008 10 More on Sequential and Simultaneous Move Games I So far we have studied two types ofgames 1 sequential move extensive form games where players take turns choosing actions and 2 strategic form normal form games where players simultaneously choose their actions I Ofcourse it is possible to combine both game forms as for example happens in the game of ootball I The transformation between game forms may change the set of equilibria as we shall see I We will also learn the concept ofrubgame perfection 1172008 Combining Sequential and Simultaneous Moves Consider the following 2 player game where Player 1 moves rst Player 2 A B stay Out Enter 33 Player 1 A B prlayer 1 chooses to stay out both he andplayer 2 eam apayoffof3 each but ifplayer 1 chooses to enter he plays a simultaneous move game with player 2 Forward Inductlon The slmultaneous move game has 3 equlllbrla AA 1313 and a mlxed strategy e ulllbnum where both players play A wlth probablllty 13 and eam expectedpayoff 83 Player 2 A B stay Out Enter 33 Player 1 A B prlayer 2 seesthatplayerl has chosen to Enter playerZ can use arwa m ucrtoureasonrng slnceplayerl choseto forego a payoff of 3 lt ls llkely that he wlll choose B so1shoulol also choose B The llkelyequlllbrlum ofthe game ls therefore Enter 1313 The IncumbentRival Game in Extensive and Strategic Form th many equnnma are mere xn39LHegtriteg39p fnrm nfthxs game7 1172008 The Number oquuilibxia Appears to be Different Subgame Perfection In the strateg farm gameLhere x5 are addmnnal eqmlxbnum Stay OutF1ghtLhatxs nut an equrnbnum usmg mllback m the extensive farm game Equxlxbna fnund by applymgmllback re the extensive farm game are refa39redtn as mbgame perfect equxlxbna eyery playexmakes aperfectbestrespnnse at eyery 7 Enter Accammadate is a subgame perm equhbmxn e StayOuL Fxgmnsmtasubgamepufeneqwhmun r any nude nfthe decxsmn tree Mme 5m mm Imperfect Strategies are Incredible Strategies and equilibria that fail the test of subgame perfection are called imperfect The imperfection of a strategy that is part of an imperfect equilibrium is that at some point in the game it has an unavoidable credibility pmblem Consider for example the equilibrium where the incumbent promises to ght so the rival chooses stay out The incumbent s promise is incredible the rival knows that if he enters the incumbent is sure to accommodate since if the incumbent adheres to his promise to fight both earn zero while if the incumbent accommodates both earn a payoff of 2 Thus Stay Out Fight is a Nash equilibrium but it is not a subgamepetfect Nash equilibrium Lesson Every subgame perfect equilibrium is a Nash equlibrium but not every Nash equlibrium is a subgame perfect equilibrium 1172008 Another Example Mutually Assured Destruction MAD quotmag What is the rollback subgame perfect A equilibrium X 7 to this game w nun 1 mummnmumm The Strategic Form Version of the Game Admits 3 Nash Equilibiia Which Equilibrium is Sub game Perfect u 2 i Q m um mm m moi Only the equilibrium where the strategies Escalate Back Down are playedby both the US and Russia is subgameperfecl 7 Why From Simultaneous to Sequential Moves 1172008 involves deeemiihihg who moves rst whieh is hot anissue in me simultaneous move game In some games Where bolh players have dominant strategies It does not matter who moves rst When heilhei player has a domiham strategy lhe subgame perfect equilibn39um will depend on lhe omei in which players move 7 Fur example the Senate Race Game the Flttsburgh Le r Tum Game The Equilibrium in Prisoner s Dilemma is the me Regardless ufWhu Mme F275 ma Tamoms memo who II mmm m m WNW WWquot and u The Senate Raee Game has a Different Subgame Perfect Equilihiium Depending on Who moves rst Similarly in the Pittsburgh Le Tum Game Thesesubgameperfectequilibnalnnk samebutifDnver 1 moves smug gets apaynffnfS while mums 2 moves rst Dnver 1 gets a payoff 75 and vice versa fur DnverZ Going from a Simultaneous Move to a Sequential Move Game may eliminate the play of a mixed strategy equilibrium This is true in games with aunique mixed strategy Nash equilibrium 7 Example The Tennis Game The Pure Strategy Equilibrium is Different Depending on Who Moves Fir t m w There is nu possibility nfmlxmg m a sequential mnve gamewithnut anymfmmaunn sets 1172008 Complete vs Incomplete Information Games K All games can be classified as Complete mfmmanun games or Incomplete mfmmanun games 5 Complete mfurmatzun gamesr the player whose turn it is to move kn ws at least as mu as those who moved before himher Complete information games include i Perfect mfmmanun games rplayers know the full history of the game all moves made by all players etc and all payoffs e g an extensive fonn game without any information sets 39 an me po role but not the actions chosen by otherplayers i Incomplete mfmmanun games At some node in the game the playerwhose tum it is to make a choice knows less than a player who has already moved Also called Bayeszan games 11242008 Imperfect vs Incomplete Information Games I In a game of imperfect information players are simply unaware of the actions chosen players However they know who the other players are what their possible strategiesactions are and the preferencespayoffs of these other players Hence information about the other players in imperfect information is complete In incomplete information games players may or may not know some information about the other players eg their type their strategies payoffs or their preferences Example 1a of an Incomplete Information Game Prisoner sDilemmaGame playerlhasthe standard selfish preferences but player 2 has either selfish preferences or nice preferences player 2 knows her type but player 1 does not know 2 type 2 2 player 2 selfish player 2 nice Recall that ccooperate Ddefect prlayer 2 is selfish then player 1 will want to choose D but ifplayer 2 is nice player 1 s best response is still to choose D since D is adominan strategy for player 1 in this incomplete information gam Example lb of an Incomplete Information Game 11242008 Pnsuner39s Dllemms Game Playerl preferencesbut Player 2 has either sel sh preferences urmce preferences Suppnse player l39sprefermcesnnw dzpmd whether player 2le nice nl sel sh or vice germ 1 C D Play12 sel sh Playerl me IfZ ls sel shthm player l mu Wanttu be sel sh and choose D butlfplayerz ls mee player l39sbestrespunse ls m play cl Example lb in Extensive Form Where PlaVer 2 s TVpe is Due to Nature Mums ems Rm 2 1h ndz s mm hm Example lb Again But With a Higher Probability that Type 2 is Sel sh Analysis of Example lb player 2 knows his type and plays his dominant strategy D ifsel sh c ifnice player 1 choice depends on her expectation concerning the unknown type ofplayer 2 e lfplayer 2 is sel sh player 1 bestresponse is to playD e lfplayer 2 isnice player 1 bestresponse is to play c Suppose player 1 attaches probability p to player 2 being selfish so lep is the probability thatplayer 2 is nice player 1 expectedpayofffrom c is 0polep player 1 expectedpayofffrom D is 2p41p 0polep 2p4lep oop42p 24pp12 player 1 best response is to play c ifplt12 D otherwise In rst version pl3 play c in second p23 play D 11242008 The Nature of Nature What does it mean to add nature as aplayer2 It is simply a I E 0 ing there is some randomness in the yp player with whom you play a game r o 1 a o E E g o 2 a a with nature s move are the subjzcnvzpmbabzlmzs ofthe player facing the uncertainty about the other la er s t p e when thinking about player types two stories can be told e The identity at a player is knuwn but his preference are unkxawn knuw l am playing againstTum but l du nut knuw whetherhe is sellish armee quot Nature whispers tn Tum his type and l the other player have tn gure it nut e Nature seleets hum apupulaaun ufpatenhalplayertype l am guing tn play aganst anutherplayer but l du nutknuwilshe is smart Dr dumb furglvmg urunfurgiying riehurpuur ete Nature eeides Example 2 Michelle and the Two Faces of Jerry J J Dancing Frat party Dancing Frat party Jerry likes company Assume that Jerry knows his true type and therefore which ofthe two games are being played Assume Michelle attaches probability p to Jerry liking company and lp to Jerry being a oner Big assumption Assume Jerry knows Michelle s estimate ofp assumption ofa common prior The Game in Extensive Form 11242008 BayesNash Equilibria BayesNash equilibria is generalization of Nash equilibrium 39 mplete information game First convert the game into a game of imperfect 39 formation informatlo game as Apply this technique to the Michelle and Jerry Game Michelle s pure strategy choices are Dancing D or Party P she can also play a mixed strategy D with probability a Jerry s strategy is a palr one for each type of Jerry the first component is for the Jerry who likes company Jerry type 1 and Second use the Nash equilibria of this imperfect n the solution concept a so as apalr o mixed strategies n and n2 indicating the probability Jerry plays D if type lor if type 2 Focus on pure strategies Pure Strategy BayesNash Equilibria I Suppose Michelle plays D for certain Dl E Type 1 Jerry plays D Type 2 Jerry plays P Jerry DP E Does Michelle maximize her payoffs by playing D against the Jerrys pure strategy of DP with probability p she gets the DD payoff z andwith probability 1p she gets e DP payoff 0 So expectedpayofffrom D against f instead she played P against Jerry DP she would getwith probability p the PD payoff o and with probability 1 p she gets the PP p f 1 So expectedpayofffrom P against Jerry DP is lp Thus playing D against Jerry DP is a best response if p lp or if 3p gt1 or if p gt 13 If pgtl3 it is a BayesNash equilibrium for Michelle to play D while the Jerrys play DP 11242008 Pure Strategy BayesNash Equilibria Contd lNext Suppnse Mlchelle plays P fur certam n0 ype l Jerry plays P Type 2 Jerry plays D Jerry PD the Jerrys39 pure strategy many wlulpmbmlw d1 gmtheRP Wm l l7p sh getsthe an pm n Sn W 12 PD ls and wlth pmbablllty mama mm P agnmst If she lnslzadplayedD agmnstlen39yO D sh wauld getwlth theDD payu 2 Sn the Expectedpaw mn D agmnstleny an ls 21 7p many playmg P agnmstryPD15 abestrwpmse lr pgt 2079 a r zpgt2 anf pgt 2 prgt2Z1Hs aanesN equdlbnu39n fax Mlchzlle m playP whalethz Jen39ysplay D ary pr gt 23 there are 2 purestrategy BayesNash equili xi Mlchelleplays DtheJenys play Dy 51 N amp 1 u bnum w ys D and the me5 play DP In amp ep12 50 Michelle should play D the two Jerry play D pr lt 13 there is no pure strategy BayesNash equilibrium Example 3 Market Entry Game With An Unknown Number of Entrants set nfplayers ynu areplaylng agamst are unknnwn as m cm example I Incumbent dues um i d kmw h faces l 3 migh gh mmabym ammm ni mm 11242008 Analysis of Example 3 Three players rst entrant second entrant incumbent m eeond entrant s strategy accept or decline the invitation by rst entrant for aJoint venture Since the rst entxan and the 39 39 moves we can treat 2player Sxmultaneausrmave games between the rst entrant and the incumbent ant There are two such games Ifthe second entrant declines and ifthe second entrant accepts If the Second Entrant Declines Middlepnyu um ism secand entrant39spaw Secand entumhas nachmceinthssuhgnme Evidzntly m umqueN um yuiuugupuyum 3W7 ash euuumuuu ufthis subgame is ll5lzy um mamme secandentxmt 5m entxmtaf If the Second Entrant Accepts I mum ufthissuhgame is accammadatg uug u paw la m incumbmh secand enumt uf a The unique N ash equd pxwpase Juimveuuxe yiel quotmay 5m What Does the Second Entrant Do The second entrant compares the payoffs in the two Nash equilibria 300 versus 044 she would choose the equilibrium that yields 044 since herr a otfin that e Vuilibn39um 4 is reaterthant e 0 payotfshe gets in the otherequilibnum Therefore the second entrant accepts the first entrant s proposal for a joint venture The unique Nash equilibrium ofthis incomplete information game is e strategy propose joint venture accept accomdoate as played by the first entrant second entrant and the incumbant 11242008 Incomplete Information and the Design of Incentives In many instances we would like for payoff incentives to depend on actions that are unobservable 7 our infonmation ab out such actions are incomplete for example work effort or the care ofa rental car strategic interactions where one players s actions are unobservable or notvenfiable by the other player give rise to moral homtdproblems ve inappropriately from the perspective ofthe otherplayer who is less informed abouthis actions or intentions Examples Aworkerknowshls effort level buthis boss does not A purchaserofmsura ce lmowshow careful hehasbeen secunng his belongings while the insurer is less infonmed In such situations the less informed player mustprovidethe more mfonmed playerwith appropriate incentives that are designed to minimize the moral hazard problem Example 1 Deductibles amp CoPays Suppose there were no cost to you of seeing your doctor ryour insurance company paid for all visitsprescriptions without ar umth In that case you might reason that it is not so important to stay pills would be requested more than in th here your le e ca w efforts to maintain your health were perfech observab Solution Insurance companies chargeyou a deductible or co and improve unobserved efforts at remaining healthy Example 2 Merlt Pay for Teachers We would like to reward teachers for exerting effort but their teaching efforts are m largepart unobservable We do obse39vethe test scores ofthe students ofa teacher so we may try to derive an incentive system based on those observables with standard effort ateachers students willperform above average on tests 50 ofthe time andbelow average 50 ofthe tlme Ifthe teacher exerted more effort sa 20 more hours per school year she could increase the likelihood that her studmts pafor m average on tests to 80 The extra effort however ls costly r the 20 hours come out ofthe teacher s leisure time and are valued to her at herhourly wage of 30 to be Worth 3OXZO6OO amount ofbonus b would inducetheteacherto arert the extra 20 hours ofeffon Wewantb such that 5b lt 8br600 Or 600lt 3bbgt6003 2000 11242008 Merit Pay Continued onsider however where the bonus money comes from Suppose the legisla declares that each classroom wlth above state average test scores can get money from the state equal to 2 7 w 39ch could be passed on to teachers 7 note this is t eir indifference level Suppose further that ifall teacher exerted the extra effort the average test scores would increase so that on average 50 of classes would score above average and the rest below average In this case the exertion ofthe extra effort would not be worth it since there is no change in the percentage pass rate and exerting the extra effort costs 3500 Hence an equilibrium would exist in which no teacher exerted extra effort 50 would get the 2000 onus and the other 50 would not and merit pay would have no effect There would also be a mixed equilibrium where some exerted effort and some did not but all exerting effort is not an equilibrium Can game theory have anything to say aboutbehaviorby participants in elections ormar s We o en imagine that in such environments individual actors cannothave any impact on outcomes i e that they are atomistic Conse uentl39 it seems that strategic behavior doesn t matter For example 7 Fullsshuwthat no not 7 The pneeofuek ts to aFlrates game is by myself am unlikely to affect the pne my candidate is losing lfl vote hewill lose anyway so there is e too high but by refusing to buy aekets l e As we shall see strategy can matter in elections and markets if the number ofplayers is small enou h Strategic Abstention 1 Should you vote Game theory suggests you might strategically abstain from Voting in two cases ase 1 You are unlikely to affect the outcome and Voting is costly e Let p be the probability your vote is pivotal LetB be the benefit you ifyour candidateissue wins Let c be the cost 0 you of voting traveling to the polling place missing work etc 7 Your rational choice is to vote iprgtc and to abstain otherwise In large electorates p an Therefore voting is not ration paradox ofvoting 7 Can be rationalized ifyou add civic dutyfear ofthe sanction of others to the equationpB D gto If Dgto then vote A MI w 7 But here is no good theory ofo Strategic Abstention 2 Cas Ven ifthere is no cost to Voting 6 0 you might strategically abstain from Voting if you are uniformed a out some candidatesissues and you ere Were other more informed Voters Who Were Voting 7 Voters often selectively Vote on some candidatesissues while abstaining on others m the same elzcno 39 we can 39ewt at situation as one where the cost to you ofvotingabstaining is 0 e A poorly informed voter may be better leaving the v t39 uuiuiiniueu may go against the choice ofthe more informed vote 39 39 39 egvotingfor vote for candidates for the top o lcesipresident or govemor which you do know something about Votlng Games Voting games tend to focus on small groups opreople who decide s issue or choose som andidate by holding an election and counting votes There are two s d voting games 7 Possible strategic behavior among the voters themselves ifN is small 7 lfthe voters are choosing candidates as in political elections and the number ofcandidates is small then the candidates have wood reason to behave strategically The s rescribe how the winning issue or winning candidate is determined 7 Majority rule lssudcandldaie with more than halfofvotes wins 7 Pluralit rule issuecandidate withthehighestfrequency ofvotes wins irstpastthe postquot With 3 ormore issuesaltemativescandidatesstratzgzc vatmg behavior becomes an issue An Issue Voting Game Pltt sBoard ofTrustees is comprised of 13 members who have different p sitions on how much Pitt should increasetuition nact year Supposethere are threeposition types TypeX 4 out of 13 thinksPitt should seek a high tuitiun increase in light of this year lfa high increase cannotbe achieved xtypes prefer a medium increase to no increase at all Type 1 5 out of 13 thinksPitt should seek a medium tuitiun increase since too high an increase might reduce student applicants and the state s appropriation lfa medium increase isnotpossible y types prefer no increase at all to a high increase TypeZ 4 outof 13 thinks Pitt should seek no increase intuition and ask the state govemmentto increase its appropnation as a reward However ifit m diiim so in that case Zs prefer a high increase to a medium increase The Voting Outcome Depends on the Rules LeLHhlg1Mmedlum Nno increase Preferences are 413 X H gt M gt N 513 Y M gt N H Z N gt H gt M lfptimlty rules and members vote their first choice then a medi increase in tuition wins as 513 gt 41 3 but it does notcompnse a majority afthe trustees pmtttans an tutttan mcreaxex Ifmafarlry rules are inp unlessmore than half It lace so thattuition policy re r t strategtca y is not implemented vote for it and voters a a ional they may behave e Supposevotingtakes place in a single stage lftypesx and y vote for their first preference andty e z strategicall yvotes for its second preference H en H wins a smctmajorlty ofvotes 813 and type z trustees are strictly better offthan they would have been ifM was the majority winner imagine assigning payoffs based 7 ofcourse the othertypesx an y could alsovote that all 3 options H M N could earn maionty vote on preferences strategically so si The Condorcet Rule I This rule proposed by the Marquis de Condorcet a French Enlightenment philosopher circa 1775 involves a complete roundrobin pairing of all issuescandidates The issuecandidate that Wins majority votes in all pairwise matches is the Condorcet winner a seemingly good approach to eliminating the problems With plurality voting I Alas this rule can lead to a paradox one can devise situations Where there is no Condorcet Winner leading to the socalled Condorcet paradox The Condorcet Paradox Illustrated Conslderagaln the tuition increase issue as described earlier preferences are given by 413 X H gtM gt N 513 Y M gtNgtH H vs M Hwins ltgets a majority of 813 x z preferH Mvs N g s amajonty of913 XX preferM N s H N ins it getsamajonty of913 y Zprefer c l l rCon orct epamdoxlsthatwhlle ol e winner T all types havenonnrrvepreferences Allis B c 2 A c the social preference ordering that follows from application ofthe Condorcetproceoure isnottransitive or intransitive H l M M l N butN ll Hl Other Less Problematic Voting Rules preference voting via a Burda rule named after another French philosopherl Each voter ranks all n issuesalternativescandidates Lquot 0 El g 39 lt 0 E E 0 rm 3 3 E a U 2 o a o o E 5 E Preference voting via instant runoff Each voter ranks all n majority it is adopted rfnot the alternative with the least first preference votes is elinnnateo and its supponer s second preference votes become their new first preference votes rocedure continues until amajority is obtained Approval voting No ranking 7 voters just say yes or no to each alternative The one alternative with the most yes votes wins A TwoCandldate Electlon Egg Suppose there arejusttwo candidates say D and R for president Su e Voters preferences can be described by four main types Left CenterrLe Centerrngit and R1 L 0 gt0 3 E Suppose the distribution oftypes over millions of voters is as follows Wheaten what positions will the two candldmex take ifthey are rational strategic players7 The Medran Voter Theorem Candidates get the vutes quhuse whuse preferences are elusest tn Lh lr ehusen pesitaens Assume the two randidates equally splitthe vetes ufany types thatlie h t h V F all lnu million votes The payufftable ran bewritten as fulluws Type Nimber cimulitivc R l 19 19 l cl cR R CL 3U 49 L CR 34 83 D CL R 17 mil CR Cellrbyreell inspeeaan reveals that CR CR is the umque NE Rut CR 215 voter The median voter in Bur example is a cR type rwhy 7 peliaeal spectrum where the median vuter resides The LheurEm breaks down ifthere are mure than twe candidates Market Games A market is any arrangement in which goods or services are exchanged e For example auctions supermarkets Job markets meet markets Those supplying goods are Supplzers or sellers Those demanding goods are demandersm buyers Do individual buyers or sellers act strategically e If Just one or a few buyers and Just one or a few sellers then strategic behavioris very likely as in a bargaining game e oligopolisticmarkets 7 Just a few firms compete many buyers and sellers individuals still act strategically in lfth re the sense that ey seek prices that maximize their individual surplus Lheyplay individualbestresponsesgt Buyers and Sellers Objectives in the Market for a Certain Good Service I Each buyer il2 has a value vh that they attach to unit nurnberj ofsome good The buyer s surplus is the value ofunitj vh less the price she paid to the seller for that unit p Buyer s surplus viip I Each seller il2 has a cost ofbringing unit nurnberj ofthe good to market ch The seller s surplus is the price received for unitj ofthe good p less the per unit cost cf Seller s surplus pch Example 1 Buyer and 1 Seller I Suppose a buyer Wanw to buy one unit of a good say a used car The buyer values it at v and the seller s cost or reserve value c is such that c lt v I Suppose thatv and c are common knowledge a big assumption We Will relax later I Then any price p such that v gt p gt c will provide a positive surplus to both the buyer and the seller I p could be determined via bargaining but the important point is that there are gains from trade the buyer gem vp gt 0 and the seller gets pc gt 0 p The Example Graphically a v c U 1 yang n r uanulu SellErs Slpply Curve BuyersDEmand Curve E v r quath q Cnnhimarl Swplyan l DEImm l Example 2 2000 Mazda Miata MXS Convertible 20000 miles l Example 2 4 Buyers 4 Sellers 4 buyers 5152 B3 B4and4 sellers sl sz s3 54 MXrS available fur sale Assume all 4 Mlatas are essenually r enueal samemllezge txansmlssluntype red eulur etc Suppeseme 4 buyer39s values canberzn e v 95nu gt vl75 gt v3155 gt Vll elAsuu lt ezl 5 lt cfSlB lt QZSZIIIEIEI Whatwlll be me eqmllbnum market pnce 7 Huw many ears wrll be suld7 Assuming that nu buyens willing tn pay mure mar merr value and nu sellens willingtu sell furless mar cusL we ear nd the answer gaphleally r 1 a Equnhlmu39npnceplssuch39hutl75 gtpgt16ID Equilibrium quannly m2 MndaMlatasbwugmtmd snld Graphical Illustration of Example 2 Mu a Mans 5 With the exception of our discussion of bargaining we have not yet examined the effect of repetition on strategic behavior in games o If a 39ame is A la ed re eatedl39 with the same players the players may behave very differently than if the game is played just once a oneshot game eg borrow friend s car versus rentacar Two types of repeated games Finiter repeated the game is played for a nite and known number of rounds for example 2 rounds In nitely or Inde niter repeated the game has no predetermined 1e115u1 p1aye1S act as though it W111 ue played inde nitely or it ends only with some probability Finitely Repeated Games Writing down the strategy space for repeated games is dif cult even if the game is repeated just 2 rounds For example cons1aer tne 11n1te1y repeated game Strategles Ior the following 2X2 game played just twice R U For a row player D U1 or D1 Two possible moves in round 1 subscript l For each rst round history pick Whether to go U2 or D2 The histories are Ulel Ulle Dlel Dlle 2 X 2 X 2 X 2 16 possible strategies Strategic Form of a 2R0und Finiter Repeated Game This quickly gets messy L2 R2 L2 R2 U2 U 2 L1 11 D 2 P2X U1 L7 R7 L2 R2 U 2 D 1 U2 D 2 D2 F1n1te Repetition of a Game With a Unique Equilibrium 0 Fortunately we may be able to determine how to play a nitely repeated game by looking at the equilibrium or equilibria in the one shot or stage game version of the game 0 For example consider a 2X2 game With a unique equilibrium eg the Prisoner s Dilemma higher numbersyears in prison are worse 0 Does the equilibrium change ifthis game is playedjust 2 rounds A Game with a Uni Aue E Auilibrium Pla ed Finitely Many Times Always Has the Same Subvame Perfect E Auilibrium Outcome To see this apply backward induction to the finitely repeated game to obtain the subgame perfect Nash equilibrium spne In the last round round 2 both players know that the game will not continue further They will therefore both play their dominant strategy of Confess Knowing the results of round 2 are Confess Confess there are no benefits to playing Don t Confess in round 1 Hence both players play Confess in round 1 as well As long as there is a known finite end there will be no change in the equilibrium outcome of a game with a unique equilibrium Also true for zero or constant sum games Finite Repetition of a Stage Game with Multiple Equilibria Consider 2 firms playing the following onestage Chicken game In this game higher numbers are bet er The two firms play the game Ngtl times where N is known What are the possible subgame perfect equilibria 3 Nu m 0 In the oneshot stage game there are 3 equilibria Ab Ba and a mixed strategy where both firms play Aa with probability 2 where the expected payoff to each firm is 2 Games With Multii 1e E iuilibria Plai ed Finiteli Many Times Have Many Subgame Perfect Equilibria Some subgame perfect equilibrium Vi um inter repeateu version of the stage game are 1 Ba Ba N times N is an even number 2 Ab Ab N times N is an even number 3 Ab Ba Ab Ba N times N is an even number 4 Aa Ab Ba i rounds Stratevies Su A ortinv these Subvame Perfect Equilibria 1 Ba Ba Row Firm rst move Play B Second move After every possible history play B AVg PaYOffSI Column Firm rst move Play a 4 1 Second move After ever A ossible histor A la a 2 Ab Ab Row Firm rst move Play A Second move After every possible history play A AVg PaYOffS3 Column Firm rst move Play b 1 4 Second move After every possible history play b 3 Ab Ba Ab Ba Row Firm rst round move Play A Even rounds After every possible history play B Odd rounds After every possible history play A Column Firm rst round move Play b Even rounds After every possible history play a Odd rounds After every possible history play b Avg Payoffs 52 52 What About that 3Round SP Equilibrium 4 Aa Ab Ba 3 Rounds only can be supported by the strategies ROW Firm rst move Play A Second move If history is Aa or Bb play A and play B in round 3 unconditionally If history is Ab play B and play B in round 3 unconditlonally If history is Ba play A and play A in round 3 unconditionally Column Firm rst move Play a Second move If history is Aa or Bb play b and play a in round 3 unconditionally If history is Ab play a and play a in round 3 unconditionally If history is Ba play b and play b in round 3 unconditionally Avi Pa offto Row 3143 Avi Pay off to Column 34l 3 267 More generally if N101 then Aa Aa Aa99 followed by Ab Ba is also a sp eq Why is this a Subgame Perfect E luilibrium Because Aa Ab Ba is each player s best response to the other A la er s stratew at each subgame Consider the column player Suppose he plays b in round 1 and row sticks to the plan of A The round 1 history is Ab According to Row s strategy given a history of Ab Row will play B in round 2 and B in round 3 According to Column s strategy given a history of Ab Column will play a in round 2 and a in round 3 Column player s average payoff is 4ll3 2 This is less than the A a off it earns in the subvame A erfect equilibrium which was found to be 267 Hence column player will not play b in the first round given his strategy and the Row A la er s strategies Similar argument for the row firm Summary A repeated game is a special kind of game in extensive or strategic form Where the same oneshot stage game is played over and over again A nitely repeated game is one in which the game is played a xed and known number of times If the stage game has a unique Nash equilibrium this equilibrium is the urzi ue subvamel er ect eAul39Zl39brl39um of the nitely repeated game If the stage game has multiple equilibria then there are many subgame perfect equilibria of the ni cpeated game Some of these involve the play of strategies that are collectively more pro table for players than the oneshot stage game Nash equilibria e g Aa Ba Ab in the last game studied In nitely Repeated Games Finitely repeated games are interesting but relatively rare how often do we really know tor certain when a game we are playing will end Sometimes but not often Some of the predictions or mum quotrated games do not hold up well in experimental tests The unique subgame perfect equilibrium in the nitely repeated ultimatum game or prisoner s dilemma game always confess are not usually observed in all rounds of nitely repeated games On the other hand we routinely play many games that are inde nitely repeated no known end We call such games in nitely repeated games and we now consider how to nd subgame A erfect e Auilibria in these games Discounting in Infinitely Rel eated Games Recall from our earlier analysis of bargaining that players may discount payoffs received in the future using a constant discount factor 9 II r where 0 lt glt I For example if 980 then a player values 1 received one period in the future as being equivalent to 080 right now gc1 Why Because the implicit one period interest rate r25 so 080 received right now and invested at the oneperiod rate r25 gives 125 x080 1 in the next period Now consider an infinitely repeated game Suppose that an outcome of this game is that a player receives p in every future play round of the game The value of this stream of payoffs right now is 19 99 93 r The exponential terms are due to compounding of interest Discounting in In nitely Repeated Games Cont The in nite sum 6452 53 converges to 5 1 5 Simple proof Let x 6 62 63 Notice thatx 55552 53 5 x solve x 5 xforx 1 5x 5 x 1 1f 5 Hence the present a zscountea value 0 rece1v1ng Ebp 1n every future round is pgIg or 199711 Note further that using the de nition 911r ga g II rIII rIr so the present value of the infinite sum can also be written as pr That is 195709 pr since by de nition 911r The Prisoner s Dilemma Game Again Consider a new version of the prisoner s dilemma game where higher payoffs are now preferred to lower payoffs C D C D uu au ba dd Ccooperate don t confess Ddefect confess To make this a prisoner s dilemma we must have bgtc gtdgta We will use tChis eanmple in what follows C D 0 6 Q94 Suppose the payoffs numbers are 1n dollars Sustaining Coo eration in the Infinitel Repeated Prisoner s Dilemma Game The outcome CC forever yielding payoffs 34 can be a subgame perfect equilibrium of the infinitely repeated prisoner s dilemma game provided that l the discount factor that both players use is sufficiently large and 2 each player uses some kind of contingent or trigger strategy For example the grim trigger strategy First round Play C Second and later rounds so long as the history of play has been CC in every round play C Otherwise play D unconditionally and forever Proof Consider a player who follows a different strategy playing C for awhile and then playing D against a player who adheres to the grim trigger strategy Coo eration in the Infinitel Re eated Prisoner s Dilemma Game Continued Consider the infinite re eated ame startin from the round in which the deviant player first decides to defect In this round the deviant earns 6 or 2 more than from C 642 Since the deviant player chose D the 0th Ilayer s grim trigger strategy requires the other player to play D forever after and so both will play D forever a loss of 422 in all future rounds The present discounted value of a loss of 2 in all future rouuus is 2g1g So the player thinking about deviating must consider Whether the immediate gain of 2 gt 2g1g the present value of all future lost payoffs or if 21g gt 29 or 2 gt49 or 12 gt g If 12 lt 9 lt 1 the ine ua1it does not hold and so the 1a er thinking about deviating is better off playing C forever Other Subgame Perfect Equilibria are Possible 1n the Kepeateo Prisoner s Uilemma Uame The Folk theorem of repeated games says that almost any outcome that on average yields the mutual defection payoff or better to both players can be sustained as a subgame perfect Nash equilibrium of the inde nitely repeated Prisoner s Dilemma game The set of subgame perfect Nash Equilibria is the green area as determined by average payoffs from all rounds played for large enough discount factor 9 The efficient mutual cooperationin allrounds equilibrium outcome is here at 44 The set offeasz39ble C5quot Row Player Avg Payoff 1 Mutual 7 payoffs is the union of the defection 1112111 CI 2 4 5 green and yellow reglons rounds equilibrium Column Player Avg Payoff Must We Use a Grim Trigger Strategy to Support Cooperation as a ouugame Perfect Equilibrium in the In nitely Repeated PD There are nicer strategies that will also support CC as an equilibrium Consider the titfortat TFT strategy row player version First round Play C Second and later rounds If the history from the last round is CC or DC play C If the history from the last round is CD or DD play D This strategy says play C initially and as long as the other player played C last round If the other player played D last round then 1 1a D this round If the other 1 1a er returns to playing C play C at the next opportunity else play D TFT is forgiving While grim trigger GT is not Hence TFT is regarded as being nicer TFT Supports CC forever in the In nitely Repeated PD Proof Suppose both players play TFT Since the strategy specifies that both players start off playing C and continue LU play C so long as the history includes no defections the history of play Will be CC CC CC Now suppose the Row player considers deviating in one round onl and then reverting to A la in C in all further rounds While Player 2 is assumed to play TFT Player l s payoffs starting from the round in which he deviates Av J V I 11 11v 11v va uvv Awuvu 11v vvvwlu Alwvv bvuuvll the sequence of payoffs 4 4 4 4 4 So the relevant comparison is Whether 6gO gt 44g The inequality holds if 2gt4g or 12 gt 9 So if 12 lt glt l the TFT strategy deters deviations by the other player TFT as an Equilibrium Strategy is not Subgame Perfect To be subgame perfect an equilibrium strategy must prescribe best responses after every possible history even those with zero probability under the given strategy Consider two TFT players and suppose that the row player accidentally deviates to playing D for one round a zero probability event but then continues playing TFT as before Starting with the round of the deviation the history of play will look like this DC CD DC CD Why Just apply the TFT strategy Consider the payoffs to the column player 2 starting from round 2 6 05652 053 664 055 6652 54 6652 1 52 2 61 52 TFT is not Subgame Perfect cont d If the column player 2 instead deviated from TFT and played C in round 2 the history would become DC CC CC CC In this case the payoffs to the column player 2 starting from round 2 wouldbei 445452453m 4455263 4451 5 41 5 Column player 2 asks Whether 61 52 gt 4l 452 6 2gtO whichisfalseforany12lt lt1 Column player 2 reasons that it is better to deviate from TFT Must We Discount Payoffs Answer 1 How else can we distinguish between in nite sums of different constant payoff amounts Answer 2 We don t have to assume that players discount future payoffs Instead we can assume that there is some constant known A robabilitd y 0 lt A lt 1 that the game will continue from one round to the next Assuming this probability is independent from one round to the next the 1 robability the game is still being plaJ ed T rounds from right now is qT Hence a payoff of p in every future round of an in nitely repeated ame with a constant A robabilit39 A of continuin from one round to the next has a value right now that is equal to pqq2q3 pq1q Similar to discounting of future payoffs equivalent if qg Play of a Prisoner s Dilemma with an Inde nite End Let s la the Prisoner s Dilemma ame studied toda but with a probability q8 that the game continues from one round to the next What this means is that at the end of each round the computer program draws a random number between 0 and 1 If this number is less than or equal to 80 the game continues with another round Otherwise the game ends We refer to the game with an inde nite number of repetitions of the stage game as a supergame The expected number of rounds in the supergame is lqq2q3 llql2 5 In practice you may play more than 5 rounds or less than 5 rounds in the supergame it just depends on the sequence of random draws Data from an Inde nitelv Rel eated Prisoner s Dilemma Game with Fixed Pairings From Duffy and Ochs Games and Economic Behavior 2009 Fixed Pairings 14 Subjects Average Cooperation Frequency of 7 pairs 1 08 06 04 X Cooperate 02 0 14 7101314 72 2 2 5 8 36 91215182114 3 3 6 9121518212427303 6 9121518 Round Number 1 Corresponds to the Start ofa New Game Discount factor g90 probability of continuation The start of each new supergame a indictaeu U a v utwal um at mum i Cooperation rates start at 30 and increase to 80 over 10 supergames Bargaining Games An Application of Sequential Move mes 9242008 I The quotBargaining Problem arises in economic situations where there are gains from trade for example when a buyervalues an item more than a seller I The problem is how to divide the gains for example what price should be charged I Bargaining problems arise when the size of the market is small and there are no obvious price standards because the good is uni ue e a ouse at a particular location A custom contract to erecta building etc I We can describe bargaining games in extensive form that allow us to better understand the bargaining problem in various economic settings Bargaining Games I A bargaininggame is one in which two or more players bargain over how to divide the gains from trade I The gains from trade are represented by a sum of money M that is llon the table I Players move sequentially making alternating offers I Examples A Seller and a Buyer bargain overthe price ofa house A Labor Union and Firm bargain overwages amp benefits Two countries eg the us and Japan bargain overthe terms ofa trade agreement The Disagreement Value If both players in a erlayer bargaining game disagree as to how to divide the sum of money M and walkaway from the game then each receivestheir disagreement value Let arthe disagreement value to the first player and let bthe disagreement value to the second player In many cases ab0 eg if a movie star and film company cannot come to terms the movie star doesn t get the workand the film company doesn t get the movie star The disagreement value is know by some otherterms eg the best alternative to negotiated agreement quotBAT A By gains from trade we mean that Mgtah 9242008 Take it or Leave it Bargaining Games quotTakeritrorrleaveritquot isthe simplest sequential move bargining game between two players each player makes move Player 1 moves first and proposes a division of M For example x for player 1 and Mix for player 2 Player 2 moves second and must decide whetherto accept or reject Player is proposa f Player 2 accepts the proposal is implemented f Player 2 rejects then both players receive their disagreemen va ues a for Player 1 and b for Player 2 This me has a simple quotrollback equilibrium PlayerZacceptsierxl b her diEgreement value Oftenwe can give an even more precise solution Used Car Example Buyer iswilling to pay a maximum price of8500 Sellerwill not sell fora price less than 8000 M8500758000500 ab0 Suppose the seller moves first and knowsthe maximum value price pgt8500 and will accept any price p i39lS The seller maximizes his profits by proposing p8500 or x50 The buyer accepts since Max l l b The seller gets the entire amount M500 What happens ifthe buyer moves first quotUltimatum Game Version of Take it or Leave it Bargaining Player 1 moves first and proposes a division of 100 Suppose there are just 3 possible divisions limited to 025 increments Player 1 can propose xOtZS X 50 or quotvm s for himself with the remainder l x going to Player 2 Player 2 can then accept or reject Player 1 s proposalt f Player 2 accepts the proposal is implemented f Player 2 rejects both players get 0 each The 100 gains from trade vanish 9242008 Computer Screen View Problems with Ta keitorLeaveit Ta keitorleaveit games are too trivial there is no backandforth bargaining Another problem is the credibility of takeitor leaveit proposalst If player 2 rejects player is offer is it really believable that both players walk away even though there are potential gains from trade Or do they continue bargaining Recall that Mgtab What about fairness Is it really likely that Player 1 will keep as much of M as possible for himself The Dictator Game Are Player 1 s concerned about fairness or are they concerned that Player 2 s will reject their proposals The Dictator Game gets at this issue 9242008 The Alternating Offers Model of Bargaining A sequential move game where players have perfect information at each move Players take turns making alternating offers with one offer per round real backandforth bargaining Round numbers t 123 Let xt be the amount that player 1 asks for in bargaining round t and let yt bethe amount that player 2 asks for in bargaining round t Alternating Offer Rules 39 Player 1 begins in the first round by proposing to keep xl for himselfand giving Player 2 Mxll 39 If Player 2 accepts the deal is struck If Player 2 rejects another bargaining round may be played In round 2 player 2 proposes to keep y2 for herself and My2 for player 1 39 If Player 1 accepts the deal is struck otherwise it is round 3 and Player 1 gets to make another proposal 39 Bargaining continues in this manner until a deal is struck or no agreement is reached an impasse is declared by one player a quotholdout 39 If no agreement is reached Player 1 earns a and Player 2 earns b the disagreement values 9242008 Alternating Offers in Extensive Form Round When Does it End Alternating offer bargaining games could continue indefinitely In reality they do not I Why not Both sides have agreed to a deadline in advance or M0 at a certain date The gains from trade M diminish in value over time and may fall below a The players are impatient time is money I We will focus on this last case of impatience The Period Discount Factor B I The period discount factor 0 lt lt 1 provides a means ofevaluatingfuture money amounts in terms of current equivalent money amounts Suppose a playervalues a 1 offer now as equivalent to 11r one period later The discountfactor in this case is 11r since X111r now 1 later I If r is high is low players discount future money amounts heavily and are therefore vew impatient I If r is low is high players regard future money almost the same as current amounts of money and are more patient less impatient Example Bargaining over a House Suppose the minimum price a sellerwill sell her house for is 150000 and the maximum price the buyer will pay for the house is 160000 Therefore M10000 Suppose both pla ers have the exact same discount factor 80 This implies that r25 Suppose that there are just two rounds of bargaining Why The Seller has to sell by a certain date buying an ther house orthe Buyer has to start a new job and nee s a Suppose the buyer makes a proposal in the first round and the seller makes a proposal in the secon round Work backward starting in the second last round of bargining and apply backward induction 9242008 Infinitely Repeated Analysis Suppose there is no end to the number of bargaining rounds If it is the Buyer s move in round t the amount he proposes to keep for himself xtDM must leave the Seller an amount ha is equivalent to that w ic the Seller can get inthe next roun rejectingand pro osin yt1DMfar herselfnext round The e uivalent amount now in erio t as Va ue to the seller of Dyt1M where Droppingt indexes the Buyer offers 17xMD DyM to the Seller D x1rDy By a similar argument the Seller must offer 17yMDxM to the uyer 17Dx x1rD erx Xlrllrl1 FLU 15y Farm17W Infinitely Repeated Analysis Continued Xy1 1 2 Note xy gt 1 What is X and y x is the amount the Buyer gets if he makes the first proposal in the very first roun is the amountthe Seller gets if she makes the first proposal in the very first round I lfthe Buyer is the first proposer he gets XM and the Seller gets 1XM Price is 1500001XM lfthe Seller is the first proposer she gets yM and the Buyer gets 1yM Price is 150 000yM In our example the Buyerwas the first proposer X18182235555M The Seller gets 1 XM15 444M Since M10000 the price of the house is 154440 15000044410000 Differing Discount Factors suppuse hetwu piavers have oitterent discuuntfzcturs fur exarnpie the buyer s discuunt femur Unis955 than seller s discuunt femur n5 auver isiess patient thanthe seiier whu gets rnure in thisease the when auver isthetirst rnuver he nuw uffers1rxM n y to the seiier anowhen seiier isthetirst rnuver she uffers Hivi EIDXM to the BAA er y and y1rE x twanglemma a X Wlt1rEl1rEl 2x when noth he sarne discuuntfacturs 39x17E17E5E s 333 3 thatx 17D1r n 2236 555 9242008 i a Practical Lessons I k In raalih L 39 J discount factors D or their relative levels a patiencei but may try to guesslhese vaiues Signal thatvou are patient even ifvou are not For example do not respond with counteroffer ri hi 1 a 39 39 39 have a poker face Rememberlhal uul 39 39 39 39 that the more palienlplavergelslhe higher fraction oflhe amount M thatison the table quUCl ltlal lVlOVC uamcs Using Backward Induction Rollback to Find E uilibrium Sequential Move Class Game Century Mark Played by xed pairs of players taking turns At each turn each A la er chooses a number between 1 and 10 inclusive This choice is added to sum of all previous choices initial sum is O The rst player to take the cumulative sum to 100 or more loses the game No talking Who are my rst two volunteers Analysis of the Game What is the Winning strategy Broadly speaking bring the total to 89 Then your OppOncut UCLllllUL PuoSibly Win and you can Win for certain The rst mover can guarantee a Win How to do this to get to 89 need to get to 78 which can be done by getting to 67 56 45 34 23 12 etc Choose 11 minus the number chosen by the second mover a complete plan of action or strategy Sequential Move Games with Perfect Information Models of strategic situations where there is a strict order of play Perfect information implies that players know everything that has happened prior to making a decision Sequential move games are most easily rel resented in extensive form that is using a game tree The investment game we played in class was an example Constructing a sequential mu c come Who are the A la ers What are the action choicesstrategies available to each player When does each player get to move How much do the stand to Vainlose Example 1 The merger game Suppose an industry has siX large rms think airlines Denote the largest rm as rm 1 and the smallest rm as rm 6 Suppose rm 1 proposes a merger with rm 6 Firm 2 must then decide Whether to merge with rm 5 The Merger Game Tree Since Firm 1 moves rst the are 7 laced Don t Buy at the root node of Firm 6 the game tree Don t Buy Firm 5 39 39 Firm 5 1A 2A 1B 2B 1C 2C 1D 2D What payoff values do you assign to rm l s payoffs 1A 1B 1C 1D To rm 2 s payoffs 2A 2B 2C 2D Think about the relative pro tability of the two rms in the four possible outcomes or termlnal nodes of the tree Use your economic intuition to rank the outcomes for each rm Assigning Payoffs Don t Buy Firm 5 39 39 Firm 5 1A 2A 1B 2B 1C 2C 1D 2D Firm 1 s Ranking 1B gt1A gt1D gt 1C Use 4 3 21 Firm 2 s Ranking 2C gt 2A gt 2D gt 2B Use 4 3 2 1 The Completed Game Tree Don t Buy Bu y Firm 6 Firm 6 Buy Firm 5 Don t uu Buy Firm 5 Firm Don L uu Firm 5 What is the equilibrium Why Example 2 The Senate Race Game Incumbant Senator Gray will run for reelection The challenger is Congresswoman Green Senator Gray moves rst and must decide Whether or not to run advertlsements early on The challenger Green moves second and must decide Whether or not to enter the race Issues to think about in modeling the game Players are Gray and Green Gray moves rst Strategies for Gray are Ads No Ads for Green In or Out Ads are costly so Gray would prefer not to run ads Green will nd it easier to Win if Gray does not run ads Computer Screen View What are the strategies A we sz raz ew for a 1 1a er is a com lete 1 Ian of action that speci es the choice to be made at each decision node Gray has two pure strategies Ads or No Ads Green has four pure strategies 1 If Gray chooses Ads choose In and if Gray chooses No Ads choose In 2 If Gray chooses Ads choose Out and if Gray chooses No Ads choose In 3 If Gray chooses Ads choose In and if Gray chooses No Ads choose Out 4 If Gray chooses Ads choose Out and if Gray chooses Ao Ads choose Out Summary Gray s pure strategies Ads No Ads Greens pure strategies In In Out In In Out Out Out Using Rollback or Backward Induction to nd the Equilibrium of a Game Suppose there are two players A and B A moves rst and B moves second Start at each of the terminal nodes of the game tree What action will the last player to move player B choose starting om the immediate prior decision node of the tree Compare the payoffs player B receives at the terminal nodes and assume player B always chooses the action giving him the maximal payoff Place an arrow on these branches of the tree Branches without arrows are A runed away Now treat the nexttolast decision node of the tree as the terminal node Given player B s choices what action will player A choose Again assume that player A always chooses the action giving her the maximal payoff Place an arrow on these branches of the tree Continue rolling back in this same manner until you reach the root node of the tree The path indicated by your arrows is the equilibrium path Illustration of Backward Induction in Senate Race Game Green s Best Response Illustration of Backward Induction in Senate Race Game Gray s Best Response This is the l equilibrium Is There a First Mover Advantage Suppose the sequence of play in the Senate Race Game is changed so that Green gets to move first The payoffs for the four possible outcomes are exactly the same as before except now Green s payoff is listed first Whether there is a rst mover advantage depends on the game To see if the order matters rearrange the sequence of moves as in the senate race game Other examples in which order may matter Adoption of new technology Better to be rst or last Class presentation of a project Better to be rst or last Sometimes order does not matter For example is there a first mover advantage in the merger game as we have modeled it Why or why not Is there such a thing as a second mover advantage Sometimes for example Sequential biding by two contractors Cakecutting One person cuts the other gets to decide now me LWO pieces are allocated Addinv more A la ers Game becomes more complex Backward induction rollback can still be used to determine the equilibrium Example The merger game There are 6 rms If rms 1 and 2 make offers to merge with rms 5 and 6 what should rm 3 do Make an offer to merge with rm 4 Depends on the payoffs 3 Player Merger Game Don t Buy Firm 6 Don t Buy Buy irm 5 Flrm Don t Buy Firm 5 222 441 414 511 144 151 115 333 Solvinv the 3 Plav er Game Buy F1 Don t Buy Firm 6 Don t Buy Buy Firm 39 irm 5 Flrm Don t Buy Firm 5 Buy Don t Firm A Buy Finn A Buy Firm 4 Buy Flnn 4 Buy Flrm 4 Flrm 4 441 414 511 144 151 115 333 Adding More Moves Again the game becomes more complex Consider as an illustration the Game of Nim Two players move sequentially Initially there are two piles of matches with a certain number of matches in each pile Players take turns removing any number of matches from a single pile The winner is the player who removes the last match from either pile Suppose for simplicity mat re c M n t m pile and 1 match in the second pile We will summarize the initial state of the piles as 21 and call the game Nim 21 What does the game look like in extensive form Nim 21 in Extensive Form How reasonable is rollbackbackward induction as a behavioral principle May worK to explam actual outcomes 1n s1mp1e games with few players and moves More difficult to use in complex sequential move games such as Chess We can t draw out the game tree because there are too many possible moves estimated to be on the order of 10120 Need a rule for assigning payoffs to nonterminal nodes a intermediate valuation function May not always predict behavior if players are unduly concerned with fair behavior by other players and do not act so as to maximize their own payoff e g they choose to punish unfair behavior Existence of a Solution to Perfect Information Games Games of perfect lnfOlm39clLlOIl are ones Where every information SUL UUllSlSLS of a single node in the tree Kuhn s Theorem Every game of perfect information with a nit number of nodes 11 has a solution to backward induction Corollar If the A a offs to A la ers at all terminal nodes are une Aual no ties then the backward induction solution is unique Sketch of Proof Consider a game with a maximum number of n nodes Assume the game with just 11 steps has a backward induction solution Think e g 112 Figure out What the best response of the last player to move at step 11 taking into account the terminal payoffs Then prune the tree and assign the appropriate termlnal paonIs to the 111 noae Since the game with just nI steps has a solution by induction so does the entire nstep game Nature as a Player Sometimes we allow for special type of player nature to make random decisions Why Often there are uncertainties that cuU llulcrcllL tu the game that uO not arise from the behavior of other players eg whether you can nd a parking place or not A simple example 1 player game against Nature With probability 12 Nature chooses G and With probability 12 Nature chooses B In this sequential move game nature moves rst Equilibria are Gr and BI Playing Against Nature Cont d Suppose the game is changed to one of simultaneous moves Player doesn t know What nature will do as symbolized by the d line What is your strategy for playing this game if you are the player Coordination Games and Continuous Strategy Spaces Mora Compicated Simultaneoug Move Games Coordination Games Non constant sum games with multiple equilibria For example the simultaneous move game considered previously Column Player Row Left Right Player Up 0 O 1 1 Down 1 1 O O has two Nash equilibria What are they This is a pure coordination game Other Coordination Games Suppose you and a partner are asked to choose one element from the following sets of choices If you both make the same choice you earn S1 otherwise nothing Red Green Blue Heads Tails 7 100 13 261 555 Write down an answer to the following questions If your partner writes the same answer you win S1 otherwise nothing A positive number A month of the year A woman s name AntiCoordination Games Not the same dress Fashion Not the same wordsideas Writing LUPI a Swedish lottery game designed in 2007 Choose a positive integer from 1 to 99 inclusive The winner is the one person who chooses the lowest unique positive integer LUPI If no unique integer choice no winner Another Example of Multiple Equilibria in Pure Strategies The Alpha Beta game Beta Alpha D 5 Strategies for Alpha are Up U Middle M or Down D Strategies for Beta are Left L or Right R What are the multiple equilibria in this game Why Finding Equilibria by Eliminating Dominated Strategies Strategies U and M are weakly dominated for Player Alpha by strategy Suppose we eliminate strategy U first The resulting game is Beta M if n l a A It now appears as though there is a unique equilibrium at DR a l 1 4 Alpha Can Lead to the Wrong Conclusion Suppose instead we eliminated Alpha39s M strategy first The resulting ga me Is Beta L R 1 a u 5 6 o 4 D 5 6 Now it appears as though u is the unique equilibrium Lesson lfthere are weakly dominated strategies consider all possible orders for removing these strategies when searching for the Na equilibria ofthe game Alpha Finding Equilibria via Best Response Analysis Always Works Beta Alpha There are two mutual best responses DL and DRThese are the two Nash equilibria of the game Cournot Competition A game where two firms duopoly compete in terms of the quantity sold market share of a homogeneous good is referred to as a Cournot game after the French economist who first studied it Let q1 and q2 be the number of units of the good that are brought to market by firm 1 and firm 2 Assume the market price P is determined by market demand Pabq1q2 if agtbq1q2 P0 otherwise p a ope b q1qz Firm 1 s profits are Pcq1 and firm 2 s profits are Pcq2 where c is the marginal cost of producing each unit of the good Assume both firms seek to maximize profits Numerical Example Discrete Choices Suppose P 130q1q2 so a130 b1 The marginal cost per unit c10 for both firms Suppose there are just three possible quantities that each firm i12 can choose qi 30 40 or 60 There are 3x39 possible profit outcomes for the two firms For example if firm 1 chooses q130 and firm 2 chooses q26O then P130306040 Firm 1 s profit is then P cq14O 1O30S9OO Firm 2 s profit is then P cq24O SlO6OS1800 Cournot Game Payoff Matrix Firm 2 q230 q240 q260 q 30 18001800 1500 2000 900 1800 1 2000 1500 1600 1600 800 1200 FIrm 1 q140 q 60 1800 900 1200 800 0 0 1 Depicts all 9 possible profit outcomes for each firm Find the Nash Equilibrium th12 q230 q240 q2 60 q30 18001800 150 901800 1 Firm 1 q 40 500 8001200 1 q160 Nash Equilibrium q60 is weakly dominated for both firms use cellbycel inspection to complete the search for the equilibrium Continuous Pure Strategies In many instances the pure strategies available to players do not consist ofjust 2 or 3 choices but instead consist of infinitely many possibilities We handle these situations by finding each player s reaction function a continuous function revealing the action the player will choose as a function of the action chosen by the other I laer For illustration purposes let us consider again the two firm Cournot quantity competition game Duopoloy two firms only competition leads to an outcome in between monopoly 1 firm maximum possible profit and perfect competition man firms each earning 0 rofits I c Profit Maximization with Continuous Strategies Firm 1 s profit n1 Pcq1abq1q2c q1abq2c qlbq12 Firm 2 s profit n2 Pcq2abq1q2c q2abq1c qZ bq22 Both firms seek to maximize profits We find the profit maximizing amount using calculus Firm 1 d nldq1abq2c2bq1 At a maximum d n1 dq10 q1abq2c2b This is firm 1 s best response function Firm 2 d n2 d 2abq1c2bq2 At a maximum d T2 d 2O q2abq1c2b This is firm 2 s best response function In our numerical example firm 1 s best response function is q1a39bq239C2b 13O39q2391026039q22 Similarly firm 2 s best response function in our example is q2a39bq139C2b 13O39q1391026039q12 Equilibrium with Continuous Strategies Equilibrium can be found algebraically or graphicaly Algebraically q16Oq22 and q26Oq12 so substitute out using one of these equations q16O60q122 6030q14 so q11 143o q130754O Similarly you can show that q240 as well the problem is perfectly symmetric Graphically ql 120 60q12 4O 60q22 40 120 q2 Multiple Equilibria Fact of Life or Problem to be Resolved Suppose we have multiple Nash equilibria the AlphaBeta game is an example What can we say about the behavior of players in such games One answer is we can say nothing both equilibria are mutual best responses so what we have is a coordination problem as to which equilibrium players will select Such coordination problems seem endemic to lots of interesting strategic environments For instance there are two ways to drive on the right and on the left and no amount of theorizing has led to the conclusion that one way to drive is better than another The US and France drive on the right the UK and Japan drive on the left A second answer is that if economics strives to be a predictive science then multiplicity of equilibria is a problem that has to be dealt with For those with this view the solution is to adopt some additional criteria beyond mutual best response for selecting from among multiple equilibria Some criteria used are Focalnesssalience we have already seen this in the coordination games Fairness envyfreeness we have already seen this in the alphabeta game Efficiency Payoff dominance Risk dominance Efficiency In selecting from among multiple equilibria economists often make use of efficiency considerations which equilibrium is most efficient An equilibrium is efficient if there exists no other equilibrium in which at least one player earns a higher payoff and no player earns a lower payoff Efficiency considerations require that all players know all payoffs and believe that all other player value efficiency as a selection criterion This may be unrealistic Consider the AlphaBeta game for example many pairs coordinate on DR over DL Efficiency may be more relevant as a selection criterion if agents can communicatecollude with one another Why Line Formation as an Example There are two ways for a firm to line customers up to conduct business with spatially separated agents of the firm 1 There is a line for every agent and each customer chooses which line to get in as at the grocery store or a toll plaza or 2 There is one quotsnake line and customers at the head of the line go to the first agent who becomes available as at a bank or airport checkin counter Efficiency considerations govern the choice between these two line conventions Can you explain why Efficiency Considerations Cannot Always be Used to Select an Equilibrium There can be multiple efficient equilibria Example 1 Driving on the left UK or right hand side US of the road Example 2 The Pittsburgh LeftTurn Game Consider 2 cars who have stopped at an intersection opposite one another Driver 1 is signaling with the turn signal that she plans to make a left turn The other driver Driver 2 by not signaling indicates his plan is to proceed through the intersection The light turns green Drivers 1 and 2 have to simultaneously decide whether to proceed with their plans or to yield to the other driver What are the payoffs to each strategy The Pittsburgh LeftTurn Game 3939quot 39quot39JEWEL Driver 2 gt Payoffs are in terms of Driver 2 Plan proceed seconds gained or lost through intersection With minus Sign Proceed with Yield to Plan Other Driver Proceed with 1490 1490 5 5 Driver 1 Plan Plan make Yield to 5 5 10 10 left turn Other Driver Equilibria in the Pittsburgh LeftTurn Game Both equilibria have one driver proceeding while the other yields Both equilibria are efficient In such cases governments often step in to impose one equilibrium bylaw This game is a particular version of the game of Driver 2 Plan proceed through intersection ChiCken Proceed with Yield to Plan Other Driver Proceed with 1490 l490 5 5 Driver 1 Plan I Plan make Yield to 5 5 10 10 left turn Other Driver Risk Considerations and Equilibrium Selection Consider the following game X Y X 75 75 25 60 Y 60 25 6060 What are the Nash equilibria Which equilibrium do you think is the most likely one to be chosen hogs OE mn mm ltmltlt 2a a d turwrha J J gmwmw a e U iy g msa 3 W3 A Jnfs 3 w a 7 ns q gag 3 i r s 39 3 449 5 g 3 W a gai V mm A r g A Za A 4 94 E 3 u V 59 Risk Dominance The two equilibria are XX and YY XX is efficient also known as payoffdominant but YY is less risky or what we call the risk dominant equilibrium why X Y X 25 60 Y 60 25 6060 In choosing Y each player insures himself a payoff of 60 regardless of what the other player does So Y is a riskfree or quotsafequot strategy How can we evaluate the expected payoff from playing X The Principle of Insufficient Reason Ifyou are completely ignorant of which of n possible outcomes will occur assign probability ln that each outcome will occur X Y X 75 75 25 60 Y 60 25 60 60 Applying this principle to this two state game we assign probability 12 to our opponent choosing X and probability 12 to our opponent choosing Y The expected payofffrom playing X is 1275122550 The expected payofffrom playing Y is 1260126060 Since the expected payoff from playing Y 60 is greater than the expected payoff from playing X 50 Y is the preferred choice If both players reason this way they end up at YY Incomplete Information Games Games where payoff information is incomplete Consider the following game You are the row player X Y X 75 75 25 a Y 60 25 60 a You know all the payoffs except the payoff the column player receives from playing Y which is a Similarly the column player does not know your payoff from playing Y Suppose you are told that a is either 59 or 61 How do you play this game Some Games Have No Equilibrium in Pure Strategies Some games have no pure strategy equilibria Consider for example the following quottennis game between the Williams sisters Serena and Venus Suppose Serena is in a position to return the ball and and can choose between a downtheline DL passing shot or a crosscourt CC diagonal Shot Venus on defense has to guess what Serena will do and position herself accordingly DL positions Serena for the DL shot and CC for the CC shot Payoffs are the fraction of times that each player wins the point Venus Williams DL CC Serena DL 50 50 80 20 Williams CC 90 10 20 8O In such cases la in39 a pure strategy is usually not a winning strategy Using cellbycell inspection we see that there is no pure strategy Nash equilibrium Serena s best response arrows do not point to the same cell as Venus s best response arrows In such cases it is better to behave unpredictany using a mixed strategy Venus Williams DL CC Serena DL 50 20 Williams CC 10 20 9282008 Simultaneous Moves Arise when players have to make their stmtegy choices simultaneously without knowing the strategies that have been chosen bythe other playerlsl Student studies for a teSt the teacher writes questions or anew product While there is no information about what other playerswill actually choosewe assume that the stmtegic choices available to each player are known by all players Players must think not only abouttheir own best strategic choice but also the best strategic choice ofthe other playerlsl r n a L L J u p Normal or Strategic Form A simultaneous move game is depicted in Normal or Strategic form using a game table that relates the strategic choices ofthe players to their payoffs I The convention is that the row player s payoff is listed first and the column player s payoff is listed second column Player Raw Strategy C1 Strategy c2 Player Stlategy R1 a b z a Strategy R2 er g h For example if Row player chooses R2 and Column player chooses C1 the Row player s payoff is e and the Co umn player s payoff is f 9282008 Special ZeroSum Form For zero lor constant sum gamesl knowing the payoffs sum to zero lor some othe conslaml allows us towrite a simultaneous ove game in normal orm more simp y Wooten cusruytsii inspeeceiis prisoner ciinrmii a i oigrumi i ii Payoffs are shown oniy forthe Prison Warden s payoffs are the negative of er the the prisoner39s payoff The Role of Beliefs i when players move simultaneously what does it mean it response3 7 One cannot see what the other is doing and conditionyour behaviu r an heir muve ln sirnuitaneous rnoye garnes rationai oiayers consider all ot the strategies their opponents may take and they torrn oeiiets suoiectiye prooaoiiities aooutthe iixeiihooo ot each strategy their opponents couio lake A Y their apected oayott by choosing the strategy thati oestresoonse to their oeiiets aooutthe play ot their opponents The same is true ot the opponents Example of the Role of Beliefs Consider the toiioWing simultaneuuscmuve garne com psyei new to Right timer or ii in pm to or SupposeRowplayi 39 quot playerplaylngngntTnenRow39sbestresponsetotnls l Up oeiietis to o ay Ruvfs expected payotttiprn piaying up is 017ppp whiie R yrs expected payotttiprn piaying Down is 11sp0 r sincewe assuined pgt sthe expected ayott to Ruwfmm piaying up p is greaterthan the expected payott to Down 17 How Might Such Beliefs be Formed Players subiective beliels about the play oi an eo opponent in a simultan us move game may be lormed in one of several ways e introspection given my knuwledge olthe opponent39s payu s what we llld I do in were the other layer e Historylrepeated games wily what strategy hasthe same opponentpiayedinthe ast e imitationlearning mm others what strategies have players lother than my ourrentopponentl chosen in this type olstrategio setting P Espluy r mmunirotibn e ethertype olsignoling Welocus lot now on thelirst introspective method 9282008 Pure vs Mixed Strategies Aplayerpursues a pure strategy if she always chooses the same strategic action out of all the strategic action choices available to her in every round with yourroommate A player pursues a mixed strategy if she rand miles in 5 me manner among the strategic action choices available to her in every rouncl e e 39 39 metime a slider mix it upquot keep them guessingquot We focus for now on pure strategies only Example Battle of the Networks Supposethere are just twotelevision networks Both are battling lot shares 0 viewers DleD VaJ Higher shares are g nuesy l prelenetl e higher advertlsm reve etwork 1 has an advantage in Sitcoms llit run it alwaysgets a higher share than it it run Sitcomi ow NetworkZ has an advan sa sagame sh tage in game shows llit runs a game show it always getsa higher share than ilit runs a Sitcom Newmrkz siren szeshaw Network 5wch 355mm mm aanesnow 501450 wt 55 Nash Equilibrium We cannot use rollback in a simultaneous move game so how 0 we ind a solution We determine the quotbest response ofeach player to a particular choice ofstrategy by the other player We do this for both players Note that in thinking ofan opponent s best res onse we are usin introspection to form beliefs about what the rational opponent will do If each player s strategy choice is a best response to the oice ofthe other player then we have found a solution or equilibrium to the game This solution concept is know as a Nash equilibrium after John as w o rst proposed it A game may have 01 or more Nash equilibria 9282008 Best Response Analysis I Best response analysis aka cellbycell inspection is the most reliable for method for finding Nash equilibria First Find Network is best response to Network 2 s possible strategies If Network 2 runs a sitcom Network 1 s best response is to run a sitcom circle Network 139s payoffin this case 55 If Network 2 runs a game show Network 1 s best response is to run a sitcom Circle Network 1 s payoffin this case 52 Netwoka m 5m pm 1 sham 45 48 Gains Show SLY41 50 45quot y 55 Best Response Analysis Continued Next we find Network 2 s best response a ifNetwork 1 runs a sitcom Network 2 s bestrespaise is to run a game show circie Network 2 s payoff in this case 48 a ifNetwork 1 runs a game show Network 2 s best responseis to run a game show circie Network 2 s payoff in this case 55 N L to run a game show y pest response ahaiysis for locating Nash equilibria Netwoka Game Show Elfw 5m Dominant Strategies I A player has a dominant strategy i it outperforms has higher payoffthan all other strategies regardless ofthe strategies chosen by the opposing players I For example in the battle of the networks game Network 1 has a dominant strategy of always choosingto run a sitcom Network 2 has a dominant strategy of always choosingto run a game show I Why Successive elimination of nondominant or d m natedquot strategies can help us to find a Nash 9282008 Successive Elimination of Dominated Strategies Ahotherway to nd Nash eoulllbrla Draw llhes through lsuccesslyely ellmlhatel each player soomlhateo strategylsl lfsuccessl39ve ellmlhatloh of oomlhateo strategles results lh a unique outcome that outcome ls the Nash eoulllbrlum ofthe game We call such games dominance solvable but hot all games have um39oue eoulllbrlaare dom method wlll network asgeherally as best re lhahce solvable so thls soohse ahalysls Networkz Network 1 Minimax Method For zero or constantrsum games only so not so general Each player reasohs thatwhat sgooo for me is bad for my opponent the hlghest of these lowestoayotts maximizes the mlm39mum r Netwurk 1 chuuses sltcum because 52 gt 48 row wlth the lowestof these hlghest payoffs minimizes the maximum 7 Network 2 chuusesgame show because smltss Networkl Sltcum szshuw Rulell natal slam sat GameShnw 513 45 45 Culumn Max 55 Adding More Strategies Suppose we add a third choice ofa talent showquot to Battle of the Networks Netwoka Sitcom Game Show Talent Show Sitc m 55 45 52 48 51 49 Network 1 Game snuw 50 5u 45 55 45 54 Talent Show 52 48 49 51 48 52 What is the Nadw equilibrium in this use First adc are there any dominated strategies If so eliminate them from cons39deration 9282008 Eliminating the Dominated Strategies Reducesthe Set of Strategies that May Comprise Nash Equ Netwoka site rri Gameshuw Taientshuw Sitc m 55 5 52 48 51 49 Network 1 raieritsiiriw 52 8 4951 4852 I A game show is a dominated strategyfor Network 1 I A sitcom is a dominated strategy for Network 2 Continuing the search for do among the rem ated strate g choices Netwoka Nash Equilibrium site Sitcum 55 Network 1 Talent show is now a dominated strategy for Network 1 Game show is now a dominated stmtegy for Network 2 Best Response Analysis Also Works Netwoka cum Geshuw Netwolkl Gameshuw snsu 45 4654 Nash Equilibrium Talentshuw 52As ASS 9282008 Adding a Third Player Consider again the case oftwo strategies sitcom and game show and suppose there is a third player Network 3 The normalrform representation ofthis threerplayer game is Nelworka Nelworkz Nawovkz Netwovkl Network Network 3 s payoff is nowthe third percentage given What isthe Nash equilibrium ofthis game Use Best Response Analy5is Nelworka Nelworkz Nawovkz Ma a 3 m a Network Network sawian ma a Q amsm xmm MQM Pure strategy Nash equilibrium tothis game is for Network 1 to run a game show Network 2 to run a game show and Network 3 to run a sitcom NonConstantSum Games T e Network Game is an exampfe of a constantsum game h The paypffs to both pfayefs afways add up to the ephsfahf sum of 100 We epufd make fhafgame Zero sum by fedefrm39hg paypffs fefau39ye to a mam share for each hempm Nash eqm39HbH39a a so eu39st m hpmcohsfaht sum of variable sum games w ere players may have some cammm interest For exampfe ph39sphef s dHemma type games Payoff afe quotpro tsquot so more R he er39 Burger King VafueMeafs Nu VafueMeafs mamas yuuauasu 39 1 Nu VafueMeafs 1 2 9282008

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.