University:
University of Edinburgh
Course:
BUST08004 | Marketing
Academic year:

2015
Views:

376

Pages:

64
Author:

seashelly20016ct4

Game Theory Lecture 8 Reading: Perlo¤ Chapter 13 August 2015 1 / 64 Introduction Game theory is the study of strategic interaction. Game theory is applicable in so many …elds other than economics. Evolutionary biology, international relations, whether or not to open the door for the old lady behind you. 2 / 64 Outline Overview of Game Theory - Terms and De…nitions. Static Games - Look at games when they happen once and everybody must make their decisions at the same time. Dynamic Games - Look at games that don’t happen all at once. Auctions - Auctions are a type of game when bidders need to strategically select the best bid. 3 / 64 Overview of Game Theory A game is a situation in which your payo¤ depends not only on what you do, but what the others do. Tick-tack-toe, whether or not to under price a rival …rm, or to cut carbon emissions are all games. 4 / 64 Overview of Game Theory An action is a move you can make at a stage in a game. Cut emissions or don’t cut emissions are actions. A strategy is a plan conditional on any possible contingency. Cut emissions if everybody else cuts emissions, don’t otherwise is a strategy. An equilibrium is a set of strategies such that neither player wishes to deviate. 5 / 64 Overview of Game Theory A static game is one that is played just once at the same time. A dynamic game is one in which players move sequentially or repeatedly. We assume that everybody knows the rules of the game and that everybody is maximizing there payo¤s with the knowledge their opponents are as well. 6 / 64 Overview of Game Theory EXAMPLE Consider the game rock-paper-scissors. Is this a static or a dynamic game? What are the actions and the strategies in this game? 7 / 64 Static Games It is useful to summarize a game using normal-form representation. We show the players, their strategies and the payo¤ as a combination of strategies in a payo¤ matrix. It is just the summary of the game using a table. 8 / 64 Static Games The most famous game is the prisoner’s dilemma. Two men are arrested, but the police do not possess enough information for a conviction. Following the separation of the two men, the police o¤er both a similar deal— if one testi…es against his partner (defects/betrays), and the other remains silent (cooperates/assists), the betrayer goes free and the one that remains silent receives the full one-year sentence. If both remain silent, both are sentenced to only one month in jail for a minor charge. If each ’rats out’the other, each receives a three-month sentence. Each prisoner must choose either to betray or remain silent; the decision of each is kept quiet. What should they do? 9 / 64 Static Games The row player’s payo¤s are written …rst, and the column player’s payo¤s are written second Nick Tom Silent Betray Silent -1,-1 0, -12 Betray -12, 0 -3, -3 10 / 64 Static Games Sometimes players will have a dominant strategy A dominant strategy is a strategy that produces a higher payo¤ than any other possible strategy. No matter what your opponent might do, you play the dominant strategy. 11 / 64 Static Games In the prisoner’s dilemma, betray is a dominant strategy for both players. If Tom remains silent, Nick will betray getting 0 months in jail rather than 1 month in jail. If Tom betrays, Nick will betray getting 3 months in jail rather than 12 months in jail. No matter what Tom does, Nick will betray. from Tom. The reverse is true This is a dominant strategy equilibrium. - Both players always play their dominant strategy and nobody deviates. 12 / 64 Static Games EXAMPLE Do either players have a dominant strategy? Is there a dominant strategy equilibrium? Row Column Left Up 2,4 Down 1,1 Right 10,0 9,-1 13 / 64 Static Games In many games, the players don’t have a dominant strategy. But players might have dominated strategies. A dominated strategy is a strategy the players will never play, so we can delete them. Denying the crime is a dominated strategy in the prisoner’s dilemma. 14 / 64 Static Games After deleting dominated strategies, we have a smaller game where we might see what happens. Maybe we can delete some more dominated strategies in the smaller game. Hopefully we are left with one set of actions. 15 / 64 Static Games Consider the following game. Player 1 Player 2 Left Up 1,0 Down 0,3 Middle 1,2 0,1 Right 0,1 2,0 16 / 64 Static Games Player 2 will never play Right. Player 1 can eliminate Right from the game. Player 1 Player 2 Left Up 1,0 Down 0,3 Middle 1,2 0,1 Player 1 will never play Down. Player 2 can eliminate down. Keep going and we are left with only fup, middle g . This is called iterated deletion of dominated strategies. 17 / 64 Static Games But this approach wont always work! Suppose I meet stranger for the …rst time and she goes in for a kiss on the cheek. If we both go to our respective rights or our respective lefts... we will kiss on the cheek and everything is …ne. If we go in opposite directions... we will kiss on the lips and that will be humiliating for both of us. 18 / 64 Static Games There are no dominant or dominated strategies in this game. We need to have something stronger. Nick Stranger Right Left Right 5,5 -5,0 Left -5, 0 5, 5 19 / 64 Static Games We can look at best responses. A best response is a best strategy given what you think the other player will do. A dominant strategy is one that is a best response to all possible strategies. 20 / 64 Static Games When players are mutually best responding, we have a Nash equilibrium. A set of strategies is a Nash equilibrium if nobody wishes to deviate from their strategies. There does not exist a pro…table deviation. It is self-enforcing. All dominant strategy equilibria are Nash equilibria, the reverse is not true. 21 / 64 Static Games There is one piece of pie left and Nick and Tom want it. If we both go for the pie, we will …ght and neither of us want that. Nick Tom Take Don’t Take -1,-1 0,1 Don’t 1, 0 0, 0 22 / 64 Static Games If I take the pie, it is Tom’s best response not to. If Tom doesn’t take the pie, it is my best response to. The two Nash equilibria are where one takes the pie and the other doesn’t. There are no pro…table deviations here. 23 / 64 Static Games EXAMPLE Kimon and Rebecca are going out for dinner and they want to wear matching out…ts. They can wear red or white. Find a Nash Equilibrium for the following game . Kimon Rebecca Red Blue Red 10,10 2,2 Blue 2,2 10,10 24 / 64 Static Games A player uses a pure strategy if the player chooses a single action. A mixed strategy is when a player randomizes between two or more actions. For example, a tennis player will randomize between serving to the left or serving to the right. Lets illustrate this with the "battle of the sexes" game. 25 / 64 Static Games Sean and Anna are meeting lunch and they forgot their cell-phones. They want to eat lunch together. Anna Sean Kalpna Red Box Kalpna 5,4 0,0 Red Box 0,0 4,5 26 / 64 Static Games There are two Nash equilibria in pure strategies here, one where they both go to Kalpna and one where they go to Red Box. If Sean goes to Kalpna for sure, Anna will want to go to Kalpna for sure and then Sean wont change. If Sean goes to Red Box for sure, Anna will want to go to Red Box for sure and then Sean wont change. 27 / 64 Static Games There is also a mixed strategy equilibrium. Suppose Sean is randomizing between Kalpna and Red Box with some probability distribution. If Kalpna yields a higher expected payo¤, Anna will go to Kalpna for sure. In order for Anna to play a mixed strategy, she must be indi¤erent between the two actions (or else she wont randomize). 28 / 64 Static Games We must …nd a probability of Sean going to Kalpna that makes Anna indi¤erent. We must …nd a probability of Anna going to Kalpna that makes Sean indi¤erent. 29 / 64 Static Games Let σ be the probability that Sean goes to Kalpna. With probability (1 σ), he goes to Red Box σ must be such that the expected value of going to either place is the same for Anna to randomize. 30 / 64 Static Games The payo¤ to Anna of going to Red Box is 5(1 σ ) + 0( σ ) The payo¤ to Anna of going to Kalpna is 4( σ ) + 0(1 σ) Equalize these 5(1 σ ) + 0( σ ) = 4( σ ) + 0(1 5 = σ 9 σ) 31 / 64 Static Games To make Anna be indi¤erent, Sean must go to Kalpna with probability 59 and go to Red Box with probability 49 . If we complete the same exercise for Anna, we see she must go to Kalpna with probability 49 and to Red Box with probability 95 to make Sean indi¤erent. We can draw best response functions. Anywhere they cross is a Nash Equilibrium (mutual best responding). 32 / 64 Static Games α is the probability Anna goes to Kalpna and σ is the probability Sean goes to Kalpna. 33 / 64 Static Games EXAMPLE Draw the best response functions and show all equilibria for the following matching pennies game. Nick Tom Heads Tails Heads -1,1 1, -1 Tails 1, -1 -1, 1 34 / 64 Dynamic Games Dynamic games are where players move sequentially or repeatedly. It is useful to analyze dynamic games in extensive form. Extensive form games show the sequence of moves and the actions each player can make each move. It is important to understand that an action is a move a player makes at a given point, and a strategy speci…es the actions the player will take for every contingency. 35 / 64 Dynamic Games A sequential game is a game in which one player moves before another. Sequential games contain subgames. A subgame consists of all subsequent decisions the player can make given the action taken. 36 / 64 Dynamic Games 37 / 64 Dynamic Games To predict the outcome of sequential games, we rely on the subgame perfect Nash equilibrium (SPNE) concept. Strategies are a SPNE if the players’strategies a Nash equilibrium in every subgame. 38 / 64 Dynamic Games To …nd the SPNE, we rely on backward induction. We see what the best response of the last player is for every possible subgame. Given the action of the last mover, we then see what the best response is of the next-to-last mover etc. 39 / 64 Dynamic Games In the example American knows what united will do for each action, so it will pick 96 knowing united will pick 48. Not all Nash equilibria are subgame perfect. 40 / 64 Dynamic Games EXAMPLE If this game is played simultaneously, what are the Nash Equilibria? What is the subgame perfect Nash Equilibrium if Firm 1 goes …rst? 41 / 64 Dynamic Games 42 / 64 Dynamic Games Nick is kidnapped by members of a drug cartel. After the ransom is paid, the cartel is faced with an important decision. They can murder Nick, or they can release him. If Nick is released, he can either go to the police and have the cartel members arrested, or he can keep his mouth shut. Being the vengeful type, Nick gets a higher payo¤ from having the cartel members arrested than from staying silent. The members of the cartel gave grown fond of Nick so they get no joy in his murder, but they would rather kill him than go to jail. Nick would rather see the members of the cartel arrested than remain silent (being the vengeful type), but Nick promises that he will not say a word. What does the cartel do? 43 / 64 Dynamic Games 44 / 64 Dynamic Games Nick would love to convince the cartel he won’t go to the police, but this is not a credible threat. The cartel knows it is not in Nick’s best interest to remain silent. Nick needs some way to burn bridges and make it so he can’t go to the police to make this credible. 45 / 64 Dynamic Games Now let’s explore games that are repeated. A repeated game is when a stage game (such as the prisoner’s dilemma) occurs over many time periods. How will this change our results? 46 / 64 Dynamic Games Lets …rst explore the case in which a game is in…nitely or inde…nitely repeated (players don’t know when the …nal game is). We saw in the prisoner’s dilemma that both players betray each other. This is not a nice outcome as both would like to deny the crime and get lighter sentences. If a game is repeated, cooperative behavior can be enforced. 47 / 64 Dynamic Games If Tom betrays me today, I can betray him tomorrow as a punishment. Both players might want to cooperate if the threat of future punishment is strong enough. All of this depends on the punishment strategy adopted and how patient everybody is. 48 / 64 Dynamic Games If there is a de…nite end date in sight, we have a …nitely repeated game. Cooperative behavior cannot be enforced in a …nite game... even if the end is 1,000,000 years away. 49 / 64 Dynamic Games Cooperative behavior occurs because people want to avoid future punishments. Call T the last period of the game. at time T , there are no future periods and no threat of future punishment. at time T , both players will betray each other. There are no future periods in which to be punished. 50 / 64 Dynamic Games As {betrayal, betrayal} is happening for sure at time T , I might as well betray in T 1 because there is no future cooperation possible {Betrayal, Betrayal} is set in stone in T in period T 2. 1. I might as well betray This all unravels and we betray every period. How reasonable do you think this is? 51 / 64 Auctions One frequently studied type of game is an auction. An auction is a sale in which a good or service is sold to the highest bidder. In an auction, I know how much I value the good, but I don’t know how much everybody else values it (I might know the distribution). Each player must devise a bidding strategy without complete information. 52 / 64 Auctions Lets look at a few types of auctions. English auction also called ascending-bid auction The auctioneer starts from a low bid and keeps raising the price until nobody wants to bid more. Sotheby’s and Christie’s use this to sell arts and antiques. 53 / 64 Auctions Dutch auction Also called descending-bid auction. The seller starts at a really high price. If nobody wants to buy, the price is dropped until somebody accepts. Record stores use this. 54 / 64 Auctions Sealed-bid auction everybody submits a bit without seeing the other bids. In a …rst-price auction, the winner payers her own highest bid. In second-price auctions (or Vickrey), the winner with the highest bid pays the second-highest bid. 55 / 64 Auctions Auctioned goods are either have a private value or common value If a good has a private value, each bidder places a personal value on the good, they know exactly how much it is worth to them. If a good has a common value, the good has the same fundamental value to everybody. For example, an oil reserve would have a common value (that not everybody knows). 56 / 64 Auctions What kind of strategies will people adopt in auctions? Second-Price Auction Strategies Bidding your valuation is a weakly dominant strategy. This means you are at least as well o¤ by bidding your valuation as any other bid. Recall that if you have the highest bid, you have to pay the second highest bid. Let’s say there are just two people in the auction. 57 / 64 Auctions Second-Price Auction Strategies Suppose my valuation of a piece of candy is v = $100. Lets consider the case in which I bid $120. There will be three possibilities. First, a rival bids greater than $120. I lose. (same payo¤ as if I bid $100). Second, a rival bids $80. I win and pay $80 (same as if I had bid $100). Third, my rival bids $110. I win, but I pay $110 which is more than my valuation. Bidding above my valuation cannot make me better o¤. 58 / 64 Auctions Second-Price Auction Strategies Should I bid below? Suppose I bid $80. I lower my chances of winning in this case (somebody else might bid $90). In no case are you better o¤ by bidding something other than your valuation. Bidding something other than your valuation might cause you to lose the auction, or have to pay more than you value the good. 59 / 64 Auctions English Auction Strategies I value the good at $100 If the going bid is $85. I should not drop out of the auction. Once the going bid reaches $100, I should stop because I will not be made better o¤ by purchasing the good at $100. Hence I will always bid my valuation in an English Auction as well. The item gets sold at the valuation of the second highest person (same as second price sealed bid). 60 / 64 Auctions First Price Sealed and Dutch For Dutch or sealed …rst-price auctions bidders face a trade-o¤ because they must pay their bid. The lower they make their bid, the more surplus they get if they win. The higher they make their bid, the greater is the probability that they win. Bidders will bid less than their valuations in these auctions. 61 / 64 Auctions You will learn this in the MSc, but the expected selling price in all 4 auctions is the same. This is called the revenue equivalence theorem. 62 / 64 Summary What is the di¤erence between an action and a strategy? What is a dominant strategy equilibrium? What is a Nash equilibrium? What is the di¤erence between pure and mixed strategies (and how do you …nd the mixed strategy)? 63 / 64 Summary How do you …nd the outcome of sequential games? What are the di¤erent types of auctions? What are the optimal bidding strategies in each auction? 64 / 64