### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Economic Theory ECON 201A

GPA 3.77

### View Full Document

## 115

## 0

## Popular in Course

## Popular in Economcs

This 36 page Class Notes was uploaded by Dr. Janiya Bernier on Thursday October 22, 2015. The Class Notes belongs to ECON 201A at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 115 views. For similar materials see /class/226722/econ-201a-university-of-california-berkeley in Economcs at University of California - Berkeley.

## Reviews for Economic Theory

### 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/22/15

Econ 201A Part 11 Due Tuesday November 22 Problem Set 2 Homework policy Please try to do the following problems on your own first If you get really stuck feel free to discuss them with other people in the class but acknowledge any discussion or ideas that you get on your homework e g I benefited from discussion with so and so on problem x Please write your solutions clearly and concisely Problem 1Consider a prisoner s dilemma repeated n times D C D C C D A grimtrigger strategy in a Prisoner s dilemma is a strategy that plays C as long as the opponent cooperates and plays D for all subsequent periods after the opponent defects For example if the opponent plays CCDCDDD then a grim trigger strategy will play CCCDDDD a If two grimtrigger strategies are playing against each other what path of play will happen b If a fully rational player has a grimtrigger opponent how will he play In other words what is a best response to a grimtrigger strategy For the next three parts suppose that player 2 can be one of two types normal with probability lp or behavioral with probability p A normal type fully rational but a behavioral type plays the grimtrigger strategy Player 1 is normal Of course the probability that player 1 assigns to player 2 being behavioral can change depending on the path ofplay For parts ce assume that n 2 c How will the normal type of player 2 play d pr 34 what happens in a PBE e Describe what can happen in a PBE for different values of p Part f is a very hard bonus part f Assume that p and n are arbitrary Describe a PBE Problem 2 Consider a Coumot duopoly in which two players simultaneously choose quantities q1 and qz sell at price l2q1qz so that the payoffs of rms 1 and 2 are q1l2q1qz and qzl2q1qz respectively a Flnd tlre unlque pure strategy Nash equlhbnum b Flnd tlre monopoly quanmy whlch maxlmlzes Q12 7 Q Now conslder a erenod game m whlch players play a Coumot oluopoly m penod l and a eoordmatror game shown m tlre gure below m perlod 2 quanquS qland n12 pnee lzeqleqz pram l z ql qz rm 1 d an qz ququz u rml For tlrrs problem please focus excluslvely on pure strategy SPE oftms game e Show that tlrere ls no pure strategy SPE m wmel botlr rms are produemg alfthe monopoly quantaty m penodl a Flnd tlre best SPE m whlch botlr rms choose tlre same quanmy m perlod17 H t Flrms want to produee less eloser to spllmng tlre monopoly quantrty but they are eorrstramed by rewards and pumslrmerrts avallable m the second perroolto provlde tlrem wth meerrtayes agamst oleyrataorrs Fmoltlre smallest palr of quantataes that ear be enforced by tlre avallable rewards and pumslrmerrts m tlre seeorrol penod 5 Problem 3 Consrolertlre followlng two player game m extenswe form Natu re W10 402 Btu 10t73t5 35 llbrla W m set7 A Charaeterrze tlre set ofPerfectBayeslanEqul Fnul lhn Fnul lhrlum lmply about player 239s bellefs m ms lnformanon Problem 4 Consider the following game played by two parties A and B First nature chooses either C or D C is chosen with probability 07 and D is chosen with probability 03 Second party A chooses either E or F Party A does not observe nature s choice when it makes this choice Next party B chooses either G or H Prior to making this choice party B observes the choice of party A party B also observes nature s choice if A has chosen E but does not observe nature s choice if A has chosen F Payoffs are determined as follows A and B always receive the same payoff the payoff is 0 if A chooses E and B chooses G regardless ofnature s choice the payoff is 5 ifA chooses E and B chooses H regardless of nature s choice the payoff is 0 if nature chooses C A chooses F and B chooses G the payoff is 10 if nature chooses C A chooses F and B chooses H the payoffis 10 if nature chooses D A chooses F and B chooses G and the payoffis 0 ifnature chooses D A chooses F and B chooses H A Draw the extensive form of this game B Please write a list of all strategies for each player C Identify all pure strategy Subgame Perfect Equilibria for this game D Identify all pure strategy Perfect Bayesian Equilibria for this game Problem 5 In the game below please find all Perfect Bayesian Equilibria Nature 20 Problem 6 a Consider a monopolist with marginal cost c 0 or 3 who faces a demand of 12 7 Q The monopolist s profit is given by 12 7 Q 7 c Q Find the monopoly quantity and profit b Consider a two firms who play Coumot duopoly Firm 1 has marginal cost 0 and firm 2 has marginal cost c They face a demand of 12 7 q1 7 q and the profits are given by q112 7 q1 7 qz and q212 7 q1 7 qz c Find the Nash equilibrium as a function of c assuming that c 0 or 3 c Consider the following twoperiod game The market demand is given by 12 7 Q in each period In period 1 firm 1 an entrant watches the behavior of firm 2 an incumbent which has cost c 0 or 3 The entrant does not know the incumbent s cost but can see the quantity chosen by incumbent in period 1 Between periods 1 and 2 the entrant decides whether to enter or not Entering involves a fixed cost of 20 If the entrant does not enter she gets a payoff of 0 and the incumbent gets to be a monopolist in period 2 If the entrant enters then she with marginal cost 0 and the incumbent with marginal cost c play Coumot duopoly in period 2 Find all separating PBE in which two types of the incumbent choose different quantities in period 1 and the entrant enters only if the incumbent is highcost Econ 201A Part 11 Solutions to Problem Set 2 Problem lConsider a prisoner s dilemma repeated n times A grimtrigger strategy in a Prisoner s dilemma is a strategy that plays C as long as the opponent cooperates and plays D for all subsequent periods after the opponent defects For example if the opponent plays CCDCDDD then a grimtrigger strategy will play CCCDDDD a If two grimtrigger strategies are playing against each other what path of play will happen The outcome will be C C in everyperiod b If a fully rational player has a grimtrigger opponent how will he play In other words what is a best response to a grimtrigger strategy A fully rational player will cooperate for n 1 periods defect in the last period and gain a total payoff of n1 To see that this is the maximal payoff that a rational player can achieve note that there is at most one period in which the rational player defects and gets a payoff of 2 while the opponent cooperates in all other periods the rational player gets a payoff of at most 1 For the next three parts suppose that player 2 can be one of two types normal with probability lp or behavioral with probability p A normal type fully rational but a behaVioral type plays the grimtrigger strategy Player 1 is normal Of course the probability that player 1 assigns to player 2 being behaVioral can change depending on the path ofplay For parts ce assume that n 2 c How Will the normal type of player 2 play In the period 2 the normal player 2 will always defect there is no incentive to cooperate regardless of player 1 s current or previous actions Likewise in period 2 regardless of what type she is facing player 1 will always defect as well Therefore in period 1 a normal type of player 2 has no incentive to a ect player 1 s beliefs about his type i e to cooperate as a grim trigger player would and will therefore defect in period 1 as well d pr 34 what happens in a PBE e Describe what can happen in a PBE for different values of p Answer to d and e As established above player 1 will defect in period 2 no matter which type of player he faces In period 1 if he plays cooperate he gets an expected total payo of p 1 0 p 1 2 4p 1 against the normal and behavioral type respectively If he plays defect he gets an expected total payoff of 1 p 0 0 p 2 0 2p Therefore player 1 s best first period action is to cooperate if p 2 12 and defect if 12 2 p39 the normal player 2 will defect in period 1 and in the second period both players defect no matter what Part f is a very hard bonus part f Assume that p and n are arbitrary Describe a PBE Let us outline the PBE and justify its main components Some of the details are omitted Denote by pm reputation the probability that player 1 assigns to 2 being behavioral when there are m periods remaining The main ingredient of the PPE below is that there is a balanced path set of values of pm and m with reputation increasing as m decreases on which the players are indifferent between cooperating and defecting 2 Z ifm is even pm 2 m 1 1fm1s odd Roughly speaking if player 2 s reputation is above the balanced path then both players will cooperate As a result player 2 s reputation stays the same and m decreases Eventually players will have to enter the balanced path when m becomes su iciently low If player 2 s reputation is below the balanced path then the normal type of player 2 must defect with su iciently high probability so his reputation reaches the balanced path The PPE is quite complicated but the most important observation about it is this for any positive initial level of reputation players will cooperate in all but finitely many periods in the end of the game The following figure schematically shows the equilibrium dynamics reputation entry to balanced path 4 quotquotquotquotquot quot cooperation balanced at The balanced path If pm 12 when m is even or pm 12m3912 when is odd let us show that there is a PBE in which the following happens along the path of play39 If cooperation has not broken down A Ifan odd number 2k1 ofperiods are remaining player 1 has beliefp2k112k Player 2 cooperates and player 1 mixes with probability 12 Player 1 s belief does not change after this period If there is an even number 2k of period remaining then player 1 cooperates and player 2 cooperates and defects with probability 12 each For player 2 this means that the grim trigger player always cooperates and normal player 2 mixes with such probabilities that the total probability that player 2 both normal and behavioral cooperates is 12 Posterior probability that player 2 is behavioral rises by a factor of 2 If one period remains player 1 defects and player 2 a grim trigger player for sure cooperates Pd 0 If one of the players previously defected then cooperation breaks down both players defect in all subsequent periods Let us show that if cooperation has not broken down then players are indifferent between cooperating and defecting at every stage until the last stage for player 1 and the second to last stage for player 2 This follows because each player is always indifkrent between defecting in the current stage or in the next stage until the end of the game as the following argument shows Player 239 If he defects currently he gets a payoff of 0 in all subsequent periods I f he cooperates currently and defects in the next period then he worsens his current period payoff by 1 but improves his payoff in the next period by 1 because player 1 will cooperate or defect with probability 12 because he mixes in one of the two periods Player 1 If he defects when player 2 is mixing he gets an expected payoff of I currently If he cooperates in the current period and defects in the next he gets an expected payo of 0 currently 1 if player 2 cooperates and 1 if player 2 defects With probability 12 player 2 happens to cooperate and player 1 gets a payoff of 2 in the next period With probability 12 player 2 defects and player 1 gets a payoff of 0 If player I defects when player 2 is cooperating for sure he gets a payoff of 2 currently If he cooperates in the current period with payoff of 1 and defects in the following period with expected payoff of 1 his total payoff is the same The arguments for player 1 apply when there are at least two periods remaining This inductive argument shows that both players are indifkrent between cooperating or breaking down cooperation at any point of the game until the end Let us see what incentives players have in the end of the game if cooperation has not broken down In the second to last period player 1 has belief 12 Player 2 cooperates or defects with probability 12 cooperates if he is behavioral and defects if normal Player 1 cooperates for sure which is fine because he is indifferent In the last period if cooperation has not broken down then player 1 defects and player 2 cooperates bc he is behavioral If one of the players has defected before we also need to check that both players have incentives to defect in all subsequent periods The proof of this fact is omitted It is true for su iciently low probabilities as on the equilibrium path above Reputation greater than on the balanced path I f pm gt 12m3912 when m is odd then player both players cooperate and player 2 s reputation does not change in this period If 22W2gt pm gt12W2 when m is even then player 1 cooperates and player 2 defects with such probability greater than 12 that his reputation rises to pm1 22W2 and the players enter the balanced path If pm 2 22W2 when m is even then both players cooperate Reputation greater than on the balanced path If pm lt 12m3912 when m is odd then player 1 will defect in this period and flat er 2 will mix so that conditional on cooperating his reputation rises to 22 quotH 2 If player 2 happens to defect then player 1 becomes convinced that player 2 is normal and both players defect forever If player 2 happens to cooperate then player 2 defects in the following period because the tit for tat player is supposed to defect and player 1 will mix between cooperating and defecting If player 1 happens to defect then the players defect forever If player 1 happens to cooperate then we enter the balanced path with case A I f pm lt12W2 when m is even then the entry into the balanced path is more complicated than in the previous case but it can be constructed analogously Problem 2 Consider a Coumot duopoly in which two players simultaneously choose quantities q1 and qz sell at price 12q1qz so that the payoffs of rms 1 and 2 are q112q1q2 and qzl2q1qz respectively a Find the unique pure strategy Nash equilibrium The best response functions are q 12 q22 and q2 12 q12 so q1q24 in a unique Nash equilibrium b Find the monopoly quantity which maximizes Q12 7 Q Q 6 Now consider a 2period game in which players play a Coumot duopoly in period 1 and a coordination game shown in the gure below in period 2 quantities ql and qz price 127q17q2 C D profit q112 7q1 7 q to gt C m firm 1 and D m q212 7q1 7 q to firm 2 For this problem please focus exclusively on pure strategy SPE of this game c Show that there is no pure strategy SPE in which both rms are producing half the monopoly quantity in period 1 Suppose there was an SPE with both firms producing 3 in period 1 Then each firm can gain 4512 45 3 312 3 2025 7 18 225 in period 1 by deviating to quantity 45 Yet in period 2 a deviation can cause a loss of at most 1 because the stage game in the secondperiod has two pure strategy Nash equilibria with payo quots 11 and 22 Therefore the immediate gain from a deviation is greater than the loss in future payoff d Find the best SPE in which both firms choose the same quantity in period 1 Hint Firms want to produce less closer to splitting the monopoly quantity but they are constrained by rewards and punishments available in the second period to provide them with incentives against deviations Find the smallest pair of quantities that can be enforced by the available rewards and punishments in the second period Consider a quantity pair q q with q E 0 6 The gainfrom the mostprofitable deviation from this quantity pair is 12q247q122q 367 6q 51247 12q 2512 367 18q 9124 6732 q2 Quantitypair q q can be enforced in period 1 ifand only if67 32q2 lt1 lt9 q 6 103 143 i e the gain in thefirst period is less than or equal to the maximal loss of payoff in period 2 On this range of quantities q 103 is the best in terms of first period payoff Therefore the following SPE maximizes achieves maximal payo quot On the equilibrium path firms are supposed to choose quantities 103 103 in period 1 andplay aNash equilibrium with payoffs 22 in the secondperiod 1fone ofthefirms deviates in period 1 they play aNash equilibrium with payoffs 11 in period 2 Problem 3 Consider the following two player game in extensive form Natu ra 010 402 310 1D73v5 35 A Characterize the set ofPerfectBayesxan Equxhbna B anhhn Wm imply about player 239s behefs m ms mformanon saw a Novmun y mawm m 1 n ma nmu 1 Lawn by m m whm p p m 17 m 7m m the mummy 1 pm n T u m mpmmsy A ung m 2 15 man m m m mmbum 2 shoes mqu Eueixinx lm wlm hue Hamish 2 m u M 17 71 0mm am mm y 1 sluch dammatnu39 m 1 in m w N39E Imd ma 7 m a home FEE whine We m am in as where 1 mm pmmw umhnmhw m r so an 239 mlmmnzmn in u mum wh pmiuw thahmw In um um Em lnwzmvlivs 2 ha k mm In m H mm am pm dawn 2 7 5 4 y 393 stmu v39 139 Inch umng nguaimqr NW 1on m mm when 1 plan my for 1 w mm owr m mm mm msxrmzml an 2 unluqu 7 any i a 7 Wan anhhrmm New 2 a mum wt 11 gamma on 2 5 huh er I 1 e a men 2 must be mdi emni human 1 m 1 mm we hava x m 1n 51111 Thus we hm Pan 139 mew 1 239 snazzy u mew em g Mess 111 M3gtWh9rs 111l 71 M11 1 5 1 I hen 2 mm wwaldy were rw rm we 1m mm lt 311 s Thu WEIMVE FEE 111113 when a 3 me And 113 3 1 mg n which n miaunnuuu set are ruched u alga a immenou mmhbnum so the am Now consider me eqn when 1 pl 1 Univ umem 211 m an mm 1mm mmgy m 1 the new Mama 1 2 mm um UW MKhE hum meuezem n w H Emmi m m seeuem m 11 A There C wen we mm xennunon on 11 u 117 cm W andxdmeSE s 395 zudumdm 139s slum 1 239 quotmeg u when 4 e 1 4 2 AN 11112 c we 11 hm m sluch ma may end mnespnnimg helm mmezge ee me mman Yes We 11m need ee luck we 3 mm mm l mmgmemu mmquot 1 place an 1 en em me man an y he to me Lew wv 17 7e 1 A 1 Lungquot 41 Omezwmuus u 7 am the sunwgm converge m we sqmllb39vum strategy A 11quot em m m it 1 7 y 71 Thehelmmnwrgnmtheeqmbelmi DLhecnndldncuamnhleed SE Problem 4 Consider the following game played by two pames A and B Fxrst nature39 0 3 Second party A chooses extherE orl Party A does not observe nature39s ehmee Next D ehmee quot D H17uikbu 2H1 Hue H mm uUimiu2gt5 u1 2w 70 7H m was H 71215 has chosen E but does not observe nature s choice if A has chosen F Payoffs are determined as follows A and B always receive the same payoff the payoff is 0 if A chooses E and B chooses G regardless ofnature s choice the payoff is 5 ifA chooses E and B chooses H regardless of nature s choice the payoff is 0 if nature chooses C A chooses F and B chooses G the payoff is 10 if nature chooses C A chooses F and B chooses H the payoffis 10 if nature chooses D A chooses F and B chooses G and the payoffis 0 ifnature chooses D A chooses F and B chooses H A Draw the extensive form of this game 0 0 55 1010 0 0 0 0 1010 B Please write a list of all strategies for each player Playerl E F Player B39 GGG GGH GH G GHH H GG H GH HH G HHH where the first letter is the action that follows CE second letter is the action that follows F and third letter is the action that follows DE C Identify all pure strategy Subgame Perfect Equilibria for this game The game has three subgames By looking at the small subgames we conclude that playerB s strategy has to be H GH or HHH in any SPE If playerB plays H GH in the entire game playerA must play E Because H GH is also a best response of player B in the entire game it follows that E H GH is a SPE Similarly if player B plays HHH then playerA must playF We can easily check that F HHH is a SPE also We conclude that there are two SPEs E H GH and F HHH D Identify all pure strategy Perfect Bayesian Equilibria for this game Strategies in any PBE must constitute a SPE Therefore we need to find all PBE in which E HGH or F HHH are played For E HGH to be aPBE player 2 must place a probability of at least 12 on the right node of his information set For F HHH to be a PBP player 2 s beliefs must come from Bayes rule in his information set so he mustputprobability 03 on the right node Remark There is no Sequential equilibrium with strategies E HGH Problem 6 In the game below please nd all Perfect Bayesian Equilibria Nature 20 To find all PBE we consider three cases of what can happen in aPBE Case 1 Suppose player 1 chooses R for sure Then player 2 must put probability 1 on the upper left node by Bayes rule Given those beliefs player 2 must choose b Given 2 s action player 1 must choose L a contradiction Case 239 Suppose player 1 chooses L for sure Then player 2 must put probability 14 on the upper left node by Bayes rule Given those beliefs player 2 must choose a Given 2 s action player 1 must choose R a contradiction Case 3 Suppose player 1 mixes with strictly positive probabilities Then in order for player 1 to be indifferent between L and R player 2 must also mix placing equal probabilities on a and b This strategy of player 2 is optimal only if he puts equal probability on each node in his information set Because those beliefs must satist the Bayes rule player I must chooseL with probability 13 We obtained aPBE only in Case 3 13L 13R 12a 12b 2 s beliefs 12 12 Problem 7 a Consider a monopolist with marginal cost 0 0 or 3 who faces a demand of 12 7 Q The monopolist s pro t is given by 12 7 Q 7 c Q Find the monopoly quantity and profit The monopoly quantity is Q 12 c2 andprofit is 12 c24 b Consider a two rms who play Coumot duopoly Firm 1 has marginal cost 0 and rm 2 has marginal cost c They face a demand of 12 7 q1 7 q and the pro ts are given by q1l2 7 ql 7 qz and q2l2 7 ql 7 q c Find the Nash equilibrium as a function of c assuming that c 0 or 3 The best response function of firm I is given by q I2 q22 The best response function offirm 2 is q2 I2 7 c 7 q12 Solving a system oftwo simultaneous equations wefind that q 4 c3 and q2 4 7 2c3 c Suppose that in period 1 rm 1 watches the behavior of rm 2 which has cost c 0 or 3 and faces demand 12 7 Q Firm 1 does not know rm 2 s cost but can see the quantity chosen by firm 2 in period 1 Between periods 1 and 2 rm 2 decides whether to enter or not Entering involves a xed cost of 20 If rm 1 does not enter rm 2 gets to be a monopolist in period 2 If rm 2 enters then rms 1 with marginal cost 0 and rm 2 with the same marginal cost as in the rst period play Coumot duopoly facing demand 12 7 q1 7 qz Find all separating equilibria In a separating equilibrium the type offirm 2 is revealed in period I Iffirm I enters it gets Cournotprofit againstfirm 2 with cost c which is 4 cj 2 25 and I6for c 0 and 3 respectively Comparing entry profit with entry cost we find that firm I will enter if and only if firm 2 is the high cost type By the standard argument the high cost firm 2 will choose its preferred quantity Q 3 45 in period I After the entrant enters the quantities chosen are 5 2 in period 2 Let us find the range of quantities Q0 of the low cost firm 2 in period I for which there exists a separating equilibrium If we take any separating equilibrium with a quantity pair Q0 Q 3 and change beliefs to c3 everywhere off the equilibrium path then we get a separating equilibrium with the same first period quantity pair In this separating equilibrium the high costfirm might be tempted to imitate the low costfirm Ifit does so it will choose quantity Q in period I and getprofit of9 7 Q0Qg instead of452 In period 2 there is no entry andfirm 2 gets aprofit of452 instead ofI2 8c3 c4 2c34 Such a deviation is notprofitable if9 Q0Qg lt4 lt2 The most tempting deviation of the low cost firm is to choose its preferred quantity 6 and be perceived a high cost type If it deviates the entrant will enter and choose quantity q15 in period 2 The best response to quantity 5 is 35 Such a deviation is not profitable if l2 Q0Q0 362 3635l2 5 35 cgtl2 Q0Q0 Z l225cgtQ0 e We conclude that a separating equilibrium eXists for Q0 5 One can specify a range of offequilibrium path beliefs for any pair of quantities Q0 Q345 with Q6 95 12J95 2 2 but beliefs that assign probability 1 to a highcost incumbent work Econ 201A Part II Due Tuesday November 8 Problem Set 1 Homework policy Please try to do the following problems on your own first If you get stuck feel free to discuss them with other people in the class but acknowledge any discussion or ideas that you get on your homework e g I bene ted from discussion with so and so on problem x Please write your solutions clearly and concisely Problem 1 A twoplayer game with nitely many actions is played repeatedly Imagine the following kind of dynamics In period 1 players choose a given pair of actions a 1 a2 In each even period thereafter player 1 chooses the same action as in the previous period and player 2 chooses a best response to that action eg in period 2 player 2 chooses a best response to a1 In each odd period player 2 keeps the action from the previous period while player 1 chooses a best response to that action a in class no need to submit this part If the game has a unique pure strategy Nash equilibrium will the players always converge to it Prove or give a counterexample b If the game has a unique pair of strategies that survives iterative elimination of strictly dominated strategies will the players converge to it Prove or give a counterexample c Suppose that players never converge Is there always a mixed strategy Nash equilibrium that involves only the actions used along the path of play Prove or give a counterexample Problem 2 Prisoner s dilemma repeated n times and the Battle of the Sexes C D C D B F C C B D D F Consider pure strategy SPE of the game above Is it possible to have cooperation in the first period What is the maximal number of periods that the players can cooperate Specify a SPE in which the players cooperate for the maximal number of periods that is specify their actions in every single subgame Problem 3 Consider the following bargaining situation Two individuals are considering undertaking a business venture that will earn them 100 in profit but they must agree how to split the 100 Bargaining works as follows The two individuals simultaneously make a demand If their demands sum to more than 100 then they fail to agree and each gets nothing If their demands sum to 100 or less they do the project each gets his demand and the rest goes to charity which neither values What are the pure strategy Nash equilibria of this game Problem 4 Consider a game in which a particular player has N information sets indexed by n l 2 N Suppose that he has Mn possible actions at information set n How many strategies does he have in all Problem 5 Consider the following game in normal form where player 1 chooses rows and player 2 chooses columns in each cell player 1 s payoff is listed first and player 2 s second WUOUIJCD A Does either player have strictly dominated strategies If so what are they B What strategies are eliminated through iterative deletion of strictly dominated choices Is the game dominance solvable C Completely characterize the set of pure strategy Nash equilibria for this game D Completely characterize the set of mixed strategy Nash equilibria for this game Bonus Problem Consider the durable goods monopoly example from the lecture There is a monopolist with zero marginal cost and potential customers whose valuations are uniformly distributed on the interval 01 Suppose that there are n periods The timing is represented as follows M p1 CNot M p2 CNot CNot M p c NoL Buy Buy Buyi Buy In each period t the monopolist makes a price offer and every customer who has not bought the good before decides whether to buy or not If a buyer buys at time t he leaves the market and gets utility n1 tv p In other words he pays p and enjoys the good for n1 t periods We showed in class that in equilibrium there will be a decreasing sequence of valuations l v1 2 V2 2 vquot such that in the beginning of period t customers in the interval 0 v are remaining Please provide recursive formulas for v and equilibrium prices p How does the monopolist s pro t in this dynamic monopoly compare with his pro t in a static monopoly where the monopolist sets one price in period 1 for all periods Econ 201a Part II Fall 2005 Problem Set 1 Solutions Problem 1 a not for submission No The game below has a unique PSNE C c Equilibrium dynamics involves a cycle A a A b B b B a A a which never converges to C c b Yes Suppose X Y is a unique pair of strategies that survives iterative elimination of strictly dominated strategies The proof that the players converge to X is 3 contradiction If the dynamics does not converge to X Y then assuming that best responses are unique there is a cycle 31 bl 31 b3 35 b1 35 b4 39 anti bln Fli b2 39 with b3 1b In the process of iterative deletion of strictly dominated strategies one of the actions involved in this cycle must be eliminated rst Without loss of generality it is al Then an is eliminated before b1 This leads to a contradiction because a1 is a best response to bin so we cannot eliminate a1 before b3 Remark It is possible that the best responses are not unique Then there may be no cycle However We can still find identical pairs ofactions a bi 333 1 1 along the path of play because each player has only finitely many actions In the path between a1 b1 and aguil 1 one of the actions must be eliminated rst which leads to a contradiction because each action in this path must be a best response to another action in the same path c No The counterexample from part a works here also 1 A w B V a quot2 b is not a mixed strategy Nash equilibrium because each player has a pro table deviation to c Problem 2 Answer players can cooperate for n2 periods but not more Let us show that there is a SPE in which the equilibrium path is CC7DCecDgte 83 and players switch to punishment path D D D DFF if player 1 deviates and D D D D B B if player 2 deviates Observe that the punishment paths are SPE in all subgames Let us verify that neither player will want to deviate from the path 3 If player 1 deviates in period 17 he gains 1 in peliod n and the last period payoffs become 1 2 instead of 2 1 Therefore this deviation is not pro table prlayer 2 deviates in period 17 he gains 1 immediately but the payoffs in the following subganie change from 1 2 7 l 2 to 0 0 7 l 2 This deviation is not profitable For periods I 517 note that a deviation by player 1 causes payoffs in the last 3 periods to change from 2 171 272 1 m o 07o 0 71 2 Clearly such a deviation is not pro table because it has a loss of at least 2 and gain of 0111 39 1 Similarly we can show that a deviation by player 2 has a loss of at least 1 so it is not pro table either To see that cooperation in period 11 is impossible note that the payoffs in the last period are l 2 or 2 1 In either case one oft e two players gets a payoff of l and we cannot provide incentives to cooperate to both players simultaneously However we can sustain C D and D C because we can provide incentives to one of the players To see that cooperation in period 111 is impossible note that the equilibrium path in the last two periods has payoffs 0 0 7 l 2 00 2 l 2 l 7 l 2 or 1272 l Again in each case one ofthe two layers gets a payoff of 1 so we cannot provide incentives to cooperate to both players simultaneously Problem 3 x 100 x is a NE for any X6 0 l00 We also have equilib a of the form X1 X1 where x1 X3 2 100 Problem 4 A strategy includes one action from each information set Thus the number of strategies X is just HMquot nl Problem 5 a For player I E is strictly dominated by A For player 1 a is strictly dominated by any mixture of b and e or d and e h Iterative deletion leaves 1A C D for player 1 and b c e for player 2 so the game is not dominance solvab e c We only need to check the strategies that survive iterative deletion C c is the unique PSNE cl We don39t need to consider strategies eliminated by iterative deletion of strictly dominated strategies Thus we consider the reduced 3 x 3 gain Fimz mutt that the unique PSNE C r is39 a special case ul a MSE SPL39UIUIL untr ihat neither player has 1m pun bust rospnusvs to any opponent s pure strategy so there will lur nn plll F 11lXPl l F qllllll ll l 34 mm 11 wk for Etlllllllin la 39llPI P each player iuixee wer all 3 strategies Play 139 2 Player 1 A b p 39 2 r 113 quot ll lli llgl D 1 1 r 399 pin down m and 13 by requiring that 11 171 iiulifl39nrtnt lutxvewn v1739 and D 1111 l11 12 21 11 119 MC 2 312 U1 D 21 Equating these three yields 11111 l 3 11 411 1 I21 Analognnsly requiring 2 s indifference yields 11 111 and 23 611 Thus we have the MSE 111 611 411 11 1 611 411 Nuw wn ltmk 1 1r niixud strutvgim in which at least unn player plays nnly 2 Sfl aliogiz s Note the ti39ull 39 ing using dominzmz39e against the strategies in question If 1 pl A and C39 only 2 Will 0111 play C39 0139 r if 1 plays C39 and D only 392 will only play I or c if 1 plays A and D wily 2 will only play 1 ur amp Similarly If 2 plays b and r only 1 Will only play A or C39 if 392 plays 1 and I only I will only play C or D 1139 2 play I and 1 only 1 will only play 1 or D From this we can rule out any 393 x 3 MSE it also see that thr only potential 2 X 2 MSE are of the form Ail 1 MD ill l e pk Using the same technique as in the 3 x 3 ea we nd 2 A Thus we have a third and MSE g D 1 0 Bonus Problem The monopolist s payoff timetion is Z W 11 where x refers to the quantity of sales Before fmding the optimal path of prices we should recall that in period 1 customer 1 must be indifferent between buying in peiiod kJ or It The customer indifference condition is uIkJU vkepH rt1kvr 317 quotk PkJ39 Pk To solve this problem we proceed by backward induction We will transform the problem by incorporating the above equation in the monopolist s payoff function and making it 501er a function of the sequence Oi At period f l we take the value of u as given and solve for the optimal value of v given v This leads to a Dynamic Progranuning problem Let us conjecture and verify inductively that that the mouopolist39s pro t in period k is 1 given by rrk any and the price is given by rm for some sequence 6 and a kJ We will derive a recursive equation for 13k From class we know that the boundary values are 3 4 and 2 ii Assuming that form of pro t and price in period 139 let us deiive it for period 1 1n etiod 1 customer v must be indifferent between buying in period k I or It That customer s indifference condition is fil1I391 k pkl rnvlk vk Si v 5 1 59 quotk Pw In periodi1 the monopolist will Choose price pp to maximize pro t in period k I and future pro t 39H quot391 U 1 A M tquot 9 H IVPH le quot1 Taking 1300 with respect to V we nd l y k VN ler39 721 39tr39r 15 k4 k AB 4 A 2 k Then the principal s pro t inperiod k I is H klvm l kvH imply 1 my 1 v 17 2 quotr lrl Zhgk r 2 k t 2 42 k H Therefore a Also 4 quot aw l lt13r1 Pic r r1 kl we 71524 If e la This proves inductively that A Zak for all periods Answer The recursive formulas me 1 2 r i pk Bkrk where i are de ned 1 in l rectu srvelv by i o k 7 1 1 2 k Let us show that the principal gets less than monopoly pro t Note that the monopoly pro t wuh commitment is quot4 which is obtained by setting the price equal to quot2 for all periods We would like to show that m t2 lt tIJ This follows because 13 and krl k2 k lt k339 Alternatively you could consider the case where T200 Here the problem is not well de ned since the profit mction is unbounded Let39s introduce discounting by discount factor 6 Here in accord with the C ease conjecture as 5 4 the monopolist39s pro t tends to zero Equn39alently to this solution one can also formally write clown the Dynamic Programming problem and solve that by backward induction For flu39ther reference see Sobel and Takahashi 983 A mulListage model of bargainntg Rm39imr ofEronomic Sitlies 50 411426 Chaplet 10 ofFudenberg amp Tirole Game Theory C oasewoujecture on the we Econ 201A PartH Due TuesdayDecember13 Problem Set 3 2g saramirsa on problem r quotP124152 wnze yam salunans clearly and cancxsely Problem 1 Consrolerthe symmetnc auctron enyrronment dlscussedln class There are N bldders wrth yaluatrons unlformly dlstxlbuted on the rnteryal 0 a Consrder an allrpay and all p hlddw Fun n w 39 from the rstpnce auctaon and a second pnce auctron Problem 2 Srmrlarto Kreps Problem 2 ln Chapter 17 Conslder the followlng slgnallng wth ch39gtcp39gto Lquotgt0 and Hquotgt0 The productryrtaes ofthe two types are n2 and mm Assume that cum lt l and cp39w lt l but cLleHoo and cpmeHoo as 24MB 0 leyel ofeducanon7lfthey emst do they satasfy the rnturtrye cntenon7 By a wth posrtrye probabrhty then the other type does not ere any poo b w ere oth b Is th 1mg equlll num h b types choose more than oneleyel of educatron7 By apoollng equlllbnum we mean that eyery educataon leyel chos by one type wth posrtaye probablllty ls chosen by the other type wrth posrtrye probablllty E Problem 3 unslllm39 lhe thuomn model 01 nntml publll cttmhgs There r ml mneprenenr whn would leP m rakP hrs compam39 pnhhr He h39 s prc n v whrwh Lu r pnnr hehel ntlter lugll ttqnltl tn 2 or low equal ht l ls that e 12 15 equally hkeh m he lghm Inw Tlln rtrtreptehenr lhnttse thn tannin y 5 m n the zompauv m mll to II minke quotIth nmkel uhs ms t and tutms l helm Mmm e 39Lu s mth ms 11 Th mmlm ns guE hehvl um that the Colnpum wll 1Lu39eh11hpro h lhml the Dm rlng pnte 11P shale wlll ME 11111011 21 HWN l H le Lula pm izdnhry 15 9 Lth enmpremm hm r m sale and the maxim pm pal4m pme p ho marker gain L5 5 q 7 p q wlulr the umepmmu39s nuhry u 1 1g i 7 q 399 sum m lmxldng lb tpamtmg ethhm ubpu my whm when 9 the entrepreneur o ers a nacuw gquot to the pubhc and the price 15 pH 3 Shaw that 111 Amy swarming mumhnum u L m pL 1 m Dmve oudm a 1739 0115 on mpg such than g H mud b9 pm of amcmg quuhbunm whm Ike Pmrepxeuom39 Image q when a c If quhMHhH 1 a sepamtmg quhbumn what must be me ufplq for all q g qbqy m equlhhnum a hm the ma ef rimm sepmhmg equihbuum Show that n 139 the truly SEDLu mmg quhbnum 11m eurwws the Iunmwr 39ntenon Problem 4 CD dm39 11m same LPO model as above hm now consular puohng ethbnu a Show there 15 a pouling equihhuum m winch q 32 b For What cum mlues of q 15 there a pooling quihhrium7 um actenze these equihbrm It show that any puulmg Pqu lh um fails the Lutumvc Cuwnun Problem 5 Consider Hm folluwmg sequential auction nmdcl At dam 0 11mm Chane35 values v11 2 5 gm mdrpnnrlemly from n distribuuon F and tenants hhm h m mm 1 At an L mm 1 chuo39 0 Tmlt hm 1 v Mk wh re p01 b V has Thvpl plmer wmm1gtiesunripm hnrlud 011 hr My 0 otherwlse A b1 IfIIILUZ 7t quotquot2 lt11 1ib1gtr2 seeuhd pnee auetmhs Prublem a OPTIONAL Cunslda the fulluwmg vers hr hf the phsuhers39 Drlerhrha wnh asymmem pzyuffs Ths game rs repeated rhsmtely WALh arseuuht fastur 5 A rrhpussrhletu aehrevepayuffswursemap Lhuse B C 397 Hrht Thmk ahuut a spa m whreh players alternate between c D and D 0 hr the equrhhhurh path Prublem 7 OPTIONAL Srrmlartu Kreps pruhlem 9 chapter 17 In apzmculzr pupmahuh everyunemns thehsk hf t at t pruhahrhty u a Indnndualsknuwthar types hut rhsurapee cumpzmes du hut Eadp mdwxdual rs vmhlgtn wequot rquott happ Ens A msurance 7 What uhhty dues he get rfhe chuuses tn take msurznce7 R Huw dues a r Dr srhau m Why7 C parameters rs there a puuhhg equlhbnum 7 Please venfyyuur cunjecmre hum part B The Last Problem gamma Consular me follow39mg rmplmr gun The quotboardquot 1 an m ll Player 1 muv and c e 5 1m s A do By choosing a punmllu dol ln mums this do and all llms elbow and m r11 l39lghl r n as lllusLl39zllsd LU ml pmm Flam 2 m basemurl and sm lml Cbnnms l rlul remm39ul ul dots mm and m m g 1 Then playvz l mam lxgam and 50 an A plum Wins hv forming 5L oppunem m mum me bottom hell am a Suppw mm m n so rhe board 15 a sqlmle Fm a min slmnegv m Pmm 1 Hum sun wnh the 2 lt 2 lure and Wm u p h me lhm pllwm39 l has A Wmmng SLIaLEgy m m gensml m x 77 game 0 I I O O O C O I O O 0 C l I I I I Burial 3x3 Board Board arm Cemer Square ls mmml Econ 201A Part 11 Professor Yuliy Sannnikov Solutions to Problem Set 3 Problem 1 Consider the symmetric auction environment discussed in class There are N bidders with valuations uniformly distributed on the interval 0 0c Consider an all pay auction the highest bidder wins and all bidders pay their bid Please nd the equilibrium bidding function Please compute the seller s expected revenue and compare it with that from the first price auction and a second price auction Solution Denote the equilibrium bidding function by 6 Then when a bidder submits bid b he wins the auction with probability Fo bN The bidder s expected payoff is m b vFa bN 1 b This expression has to be maximized when b 01b Taking the first order condition with respect to b we get v NIoquot1b foquot1bF0 1bN 2 10 Substituting b ofv and 0quotb 10quotv we get do vN 1fvFvgt 2 3 W l av The seller s expected revenue is ZN l VN N l vm1 N l N vdv 39N calmq NlotN0 Nl the same as in the first and second price auctions Problem 2 Similar to Kreps Problem 2 in Chapter 17 Consider the following signaling environment from class 2 types that have cost of education cLe and cHe respectively with cL39gtcH39gt0 cL gt0 and cH gt0 The productivities of the two types are xLe and xHe Assume that cL390 lt l and cH390 lt l but cL39e gtoo and cH39e gtoo as eeoo a Are there separating equilibria where one type or both chooses more than one level of education If they exist do they satisfy the intuitive criterion By a separating equilibrium we mean that if one type chooses a given education level with positive probability then the other type does not Solution Such a separating equilibrium can exist but it always fails the intuitive criterion The picture below shows a possible separating equilibrium in which type L chooses the efficient level 6L and type H chooses levels eHand eH with positive probability In this example the market always believes it is type L whenever it sees an offequilibrium education level xH e wcLelI71 wc ek2 xLe To prove that any such equilibrium fails the intuitive criterion note that the low type must always choose only one education level ithe efficient one The high type chooses to levels of education 6 and eH with positive probability Because indifference curves are concave and increasing the low type strictly prefers his education level to any level between 6 and eH even if he is inferred to be the high type Therefore by the intuitive criterion the market must believe that it is the high type whenever it sees any education level between 6 and eH Given that the high type will deviate b Is there any pooling equilibrium where both types choose more than one level of education By a pooling equilibrium we mean that every education level chosen by one type with positive probability is chosen by the other type with positive probability Solution No Suppose such equilibrium existed with education and wage levels 61 W1 and 82 W2 Since both types must choose these education levels with positive probabilities they must be indifferent between choosing e and 82 However it is impossible for two indifference curves for a high and a low type to cross twice at points 61 W1 and 62 W2 because cL39gtcH39 c A hybrid equilibrium is one in which some education levels are chosen by one type only and others are chosen by both types Are there any hybrid equilibria Solution Yes please see the picture below educatlon level 0 and me hlgh type mlxes between 0 and 2 There 15 an Problem 3 Consular me l39ollowlug model of mmal puth allmuge emewuem wllll would Lllce ll ml me e nulllm pubhl He Lu me 2 mu 1 mm m we mformanuu mum le s pun helm enlm mull unal 15 HJAI a g l l l Fqlmllv llkcly m bu ugh ur u u epz uem chooses the lumen q e l of the compam to 11 m a hphvf e lmu 1 en tell m men Thn ulmkm ubsexvs q l llle mm mum pm ls ll the maka Ligns mull lllfl that hr mmpanv m gl pru ls men an olfm39mg pm pm slme val We p1qAltll 2li lql l 11 1110 true prn tnhruw 1s a the amu39prmwm39 min t for m1 tnnl the A 39 eennrt pneb p the 1111th 7 1 mm 0 masz 11 rtt ha1gtnc1 a1wuen39uuhn1K1 11 1 We store In lekmg 0139 Ppamnug Ethbzm 11 pL my when g vlwu t 7 2 r111 nutroprouonr n lra 1t Imruuu tquot tn tho pubhr and he pl xce rs pp Show thnt In my wpamuug equrh hnuut nL 1 and IQ Dmve Gnu111mm 1111 1m 11 5m that op 11 mum he pan uf n SEptxmtmg oqnthhrtum where the run eprt uem39 ohonso np when 1 2 it 139 11 LILpL111JH 1s n sepatnnnn tgtqu1hbnum whm um he mm nt ptq int n11 1 gmquot n1 nqulhbl uuu e1 Whm ts 1112 most et mr m epnmtmg Equilihzium 31th 11an 1t n the 0111 sepamtmn aquihbrium that Sun the unutne cartnrrnn Snnnnn a In a separatrng eanhbnnrn the rnarket rnnstbeheye that e 1 when rt obseryes q so pL1 t 1ble that q lt1beeanse otherwrse the low type would 1 15 rrnposs deyrate to q andlmprove hrs payoff b pp 2 eornes from rnarketrnferenees 1n a separatrng ethbnum Two condmons rnnstho1o1 2 qp 1rqpz1 type H does not dramas a1ways ho1o1s 2 qp 2 mp g 1 typeL does not deyrate eho1o1s 1f ops 13 e We needto make sure thatnerther type would wantto deyrate offreqmlxbnum For q lt q pnee pq eon1o1 be any nnrnberbetween 1 and 2 For q e qp 1 the followmg two condmons rnnst ho1o1 2 qp hop 2 pq 1 14 type H does not deyrate pq g tap1 1 12 pq 1 2 14 type L does not deyrate lt2pq g 12q 12 We rnnsthaye pq Smmq q112q V d t qp 13 In thrs eanhbnnrn the rntnrtrye errtenon does not p1aee any resmcuons on behefs both types wouldhke to deyrate to any q e 13 1 1the rnarket A 13 eyen 1fthe rnarketbeheyedrtwas the hrgh type We a1so needto show that any other equrhbnnrn fads the mmmve enterron Suppose tn lt13 Then the low type won1o1notwantto deyrate to q e qp 13 eyen 1f pq 2 Therefore the rntnrtrye errtenon 1mphes that the rnarket be reyes a deyratorto be the hrg type rfrt obseryes q e qp 13 Gwen those behefs the hrgh type would deyrate rnto thrs range Problem 4 unqdm mu emne LPO mum as have hm nuw crmsldar puunn ethhm a Show them 15 a pooling Cqulhhnum m which 1 1 m1 1 m For whm uthsr hth e 0139 g 15 lhm e u poolmg qulllrnum Chem Attm xzr mm equlhhrm c Show um um pauliug mu ihmxm falls the hmnme me 101 v J Ifthe 1 because payoffs are mcreasmg m 1 and deeeeaemg m p b the low typewouldnotwantto deviateto q11 e 32 new21qu 2 1 2 y Y equmbnum values of q 2 e Even xfngen pnee 2 type 1wouldnotwantto deviate to any q lt3 Type 2 would A F no quotmere Problem 5 quemml emcan mmm At Am 0 mum e e gtpem emIv from a disn39ibuuun F and ah mm m m mumy AL law 1 mm 1 m y r by 5 0x Tm 1an 1 when M39 mm 2 who zmpumk with n ha b2 5 ALgt0 The plave mm Lhr ughpsn bk wms me auction an11 we wlumngtvgt2u1rlpmltherhkl Sou u7 uerm m u 0 mmmse ouzidm39 tbs fulluwmg a L hUl SF S v I re A m was M ltva 15b1gtm Solution The payoff of player 2 is independent of his beliefs about player 1 If player 1 chooses b1 lt vz then player 2 can obtain a positive payoff by winning the auction He makes the smallest bid that allows him to win If b1 gt v2 then player 2 would always obtain a negative payoff if he wins It is best to place a bid less than b1 and let player 1 win B Use your answer to A to solve for the perfect Bayesian equilibrium of the auction Solution For the uniform distribution If player 1 bids b1 he wins the auction in case player 2 s valuation falls in the range 3 b1 with probability 1 X Player 1 s V 2 b1 expected payoff is 2 v1 b1 which is maximized when b1 v v12 v v C Compute the seller s expected revenue and compare it to that in the standard first price and second price auctions Solution For the uniform distribution The seller always receives the bid that player 1 made which is 3 V y 4 in expectation In a standard first and second price auction the seller s revenue would be larger It would be 3 V y 3 as computed in class Problem 6 Consider the following version of the Prisoners Dilemma with asymmetric payoffs This game is repeated infinitely with discount factor 5 A What are the payoffs in the worst possible subgame perfect equilibrium Prove that it is impossible to achieve payoffs worse than those B What is the lowest discount factor 5 for which the players achieve cooperation in a SPE C Is it possible to achieve payoffs better than 0 0 in a SPE for discount factors lower than 5 Hint Think about a SPE in which players alternate between C D and D C on the equilibrium path Solution a The payoffs in the worst SPE are 0 0 They are achieved by the repetition of Nash The reason why it is impossible to achieve payoffs worse than 0 for either player is that each player can guarantee himself a payoff of at least 0 by playing D in every period b We are interested in the SPE that has C C in every period on the equilibrium path We need to check that neither player would want to deviate once from C C According to part a the worst available punishment has payoff 0 so both of the following conditions need to hold 5 0 S 315 cgt 5 2 25 deviation of player 1 3 0 S 215 cgt 5 2 13 deviation ofplayer 2 We nd that 5 25 c Yes Consider a SPE in which player alternate between regimes C D and D C as long as neither player deviates and deviations are punished by Nash equilibrium forever We need to check that single deviations are not profitable 3 0 S 5 5 552 53 5 5l52 always holds player 1 in regime D C 0 s 1 35 552 53 1 351 52 holds if6 2 13 player 2 in regime D C 0 s 1 55 52 553 1 55162 holds if6 2 15 player 1 in regime c D 2 S 3 5 352 53 3 5l52 always holds player 2 in regime C D This shows that alternating between C D and D C can happen on the equilibrium path if 5 2 13 note that 13 lt 5 If players start in regime C D they get strictly positive payoffs of 1 56152 and 3 syn 52 Problem 7 Similar to Kreps Problem 9 Chapter 17 In a particular population everyone runs the risk of losing 1000 randomly Each person s chance to lose 1000 depends on the individual fraction x of the population loses 1000 with probability 1 while the other fraction lx loses 1000 with probability 06 Individuals know their types but insurance companies do not Each individual is risk averse and has the same von Neumann Morgenstem utility function given by ux e39b with 7 gt 0 but the insurance companies are risk neutral Each individual decides whether to seek insurance or not Ifhe chooses to seek insurance he approaches a number of insurance companies who simultaneously name premiums for full insurance P The individual accepts the lowest premium He pays the insurance company P The company covers the 1000 loss in the event it happens A What expected utility does an individual of each type gets if he chooses to go without insurance What utility does he get if he chooses to take insurance Answer Expected utility without insurance is 6100 J q where q is the probability of losing 1000 Expected utility with insurance is ie H B Please think intuitively about whether the less risky individuals get insurance or not How does the answer depend on A and x ie is there a separating equilibrium for large A or small A large x or small x Why Answer The less risky individual definitely gets insurance if 7 is sufficiently large ie he is very risk averse so he would be willing to accept insurance even xf on sugm eauuy unfan39terms Also its easterfor me lowrnsk type to get msueauee 1fxxs large mlum use the pre m apoolmg equuubnum wouldbe H r premium 15 eompeuuve forthe hxghrnsk type e P 0 o x 31000 soon There 15 a separating equuubnum xfthe lowrnsk type prefers to go umnsured e e W e zeem cmo 0 xe xfthe lowrnsktype 15 not too nskraverse Tth con rms our rst guess m pan to take msueauee thh premium P 100 x 600 11 e 7012quot 70 9 Amww cm x wherex 0 1 gt 0 up 15 an deeeeasmg fuueuou ofxthhO 0 00568 and 1 0 Thus con rms our second guess 1 a npartB sxxncreaseStherangewhere equuubnum exist does not change The Last Problem rmpluveu gami Tuu quot1mm moves 1511 md choooes o am By mum 11115 uur 0qu on above m n Lhepirtuze lee 2 muvnssezouu sumLuh shows u m Ibmm mn an rlurc uhuvu and u rlw ugh rm Bonus Cumum mu Lunuuuu m x n ngd u lots Play 1 dmoimg u pummLu am he re 1 Llw uglu of so as Illusrmm uud 3 Theu plum 1 Luqu oguus uud n ran A plum mus bv mm Lus oppomm w mm the bmwm 1m do W Supposr haL m n Lhe board 15 a Squaw Fmd o uuuuug rusegv fm39 Pluwr 1 Hum Wu an1 m 2 x 2 cues and work up m pme uuu pluve L bus 1 Wummg suuregv m we gum 1 m x n gum O O O O O O O C C O O I Initial 3x3 Board Board after Center Square is removed Salmon r 7quot l r motes tln ilppt l right it l x n 1 atlmu t39 with his list more itos un L a mi Con g llr iion of dots After that whenever player 3 I39t39moVC A upper lrts plnvor 1 will impontl ln39 rruiovin thr srunc lllllllllf l o r39 r 39 Dts nioneror plaver 2 removcs k riglltvildt don plnmr 1 will I t spuntl IN nitming tho ltnnio inunlior of upper s n rmilt tlit gtllnpml ror r wnys s 39 tftcr p aycr 139 rnovo In the 9an of the game plity ct 2 will lw urcr nl to l39cmm o the loot tlm 2 E Consider all con gurations oi tlots that Could possibly arise in the Course of rho ploy Let39s on o con guration of lots mummy it the plnyor who moves ironr it has n Winning strategy and losing if his opponent hits a wnui39ui w A egy Wilt ning and losing con gurations can be charactenzetl by the following properties Any move iron a losing con gttmtion leads to n wnnui g n r ti n or the opponent For any Winning con glnatitm there is a movt that leads to a losing con guration Let39s prove that an n x m mmugcmcm oi lots is a winning con guration ie the rst player has a Winning stiategv Supports on the contrary thnt the n x m 39 39 39 Jen Lu 39 canhe obtained in one move is rt winning con guration In pmtit ulm the con guration with the llppt l39 iight tlul ttmmt tl in whining tzuniigurntiun Then lhm t hm i In M uiuvo from l11l39 cuit mlmtlun rhnr lumk tn n losing Ul ll39illllll Ylinttvnr hi niovo lz h lx wing mun with some Ippt i lll unk like in in igluul n gtlt m rcvuulglu it rmle tmnuveil Hmvewr this l Ull gllLMllOll can hit quotminimal ruin llll nrlginnl l UL39lmlgll39 in who muvn 391 L4 n romrmllttlun in tt t x imerl that Ll o 39 39 is a losing cnn gnr ion Therefore the iiist lllnw39l whu LHUW H l rum nu u A m tomnnglv ln n winning otrntrny l 1 gin momngl 47

### 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."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.