Create Presentation
Download Presentation

Download Presentation
## Applied Game Theory Lecture 2

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Applied Game TheoryLecture 2**Pietro Michiardi**Recap …**• We introduced the idea of best response (BR) • do the best you can do, given your belief about what the other players will do • We saw a simple game in which we applied the BR idea and worked with plots**Soccer: Penalty Kick Game (1)**goalie r l • Payoffs approximate the probabilities of scoring for the kicker, and the negative of that for the goalie • Assumption: we ignore the “stay put” option for the goalie • Example: • u1(L,l) = 4 40% chance of scoring • u1(L,r) = 9 90% chance of scoring L kicker M R**Penalty Kick Game (2)**• What would you do here? • Is there any dominated strategy? • If we stopped to the idea of iterative deletion of dominated strategies, we would be stuck! • If you were the kicker, were would you shoot?**Expected Payoff**E[u1(L, p(r) )] E[u1(R, p(r) )] 10 8 6 4 E[u1(L, p(r) )] 2 0 x 0.5 y 1 p(r) “belief”**Penalty Kick Game (3)**• What’s the lesson here? • Assume for a moment these numbers are true • If the goalie is jumping to the right with a probability less than 0.5, then you should shoot …. Lesson: Don’t shoot to the middle**Lesson 1:**Do not choose a strategy that is never a BR to any(*) belief (*) any means all probabilities**Penalty Kick Game (4)**• Notice how we could eliminate one strategy even though nothing was dominated • With deletion of dominated strategies we got nowhere • With BR, we made some progress… • Can we do better? What are we missing here?**Penalty Kick Game (5)**• Right footed players find it easier to shoot to their left! • The goalie might stay in the middle • The probabilities we used before are artificial, what about reality? • What about considering also the speed? • And the precision?**Expected Payoff**10 8 6 4 2 0 0.5 1 p(r) “belief” See what happens? If you are less precise but strong you’d be better off by shooting to the middle**The Partnership Game (1)**• Two individuals (players) who are going to supply an input to a joint project • The two individuals share 50% of the profit • The two individuals supply efforts individually • Each player chooses the effort level to put into the project (e.g. working hours)**The Partnership Game (2)**• Let’s be more formal, and normalize the effort in hours a player chooses • Si = [0,4] • Note: this is a continuous set of strategies**The Partnership Game (3)**• Let’s now define the profit to the partnership Profit = 4 [s1 + s2 + b s1 s2] • Where: • si = the effort level chosen by player i • b = synergy / complementarity • 0 ≤ b ≤ ¼ • Why is there the term s1 s2 ?**The Partnership Game (4)**• What’s missing? Payoffs! u1(s1 , s2) = ½ [4 (s1 + s2 + b s1 s2)] - s12 u2(s1 , s2) = ½ [4 (s1 + s2 + b s1 s2)] - s22 • That is: • Players share the profit in half • They bear a cost proportional to the square of their effort level • Note: payoff = benefit - cost**The Partnership Game (5)**• Alright, how can we proceed now? • Let’s analyze this game with the idea of BR • But how can we draw a graph with a continuous set of strategies? • Recall the definition of best response**The Partnership Game (6)**• We are going to use some calculus here ŝ1 = arg max { 2 (s1 + s2 + b s1 s2) - s12 }**The Partnership Game (7)**• So we differentiate: • F.o.c. : 2 (1 + b s2) - 2s1 = 0 • S.o.c. : -2 < 0 ŝ1 = 1 + b s2 = BR1(s2) ŝ2 = 1 + b s1 = BR2(s1) due to symmetry of the game**The Partnership Game (8)**• Alright, we have the expressions that tell me: • player i best response, given what player j is doing • Now, let’s draw the two functions we found and have a look at what we can say • Let’s also fix the only parameter of the game: b = ¼**s2**5 BR1(s2) 4 3 BR2(s1) 2 1 0 s1 1 3 2 4 5**s2**5 BR1(s2) 4 3 2 1 0 s1 1 3 2 4 5**s2**5 4 3 BR2(s1) 2 1 0 s1 1 3 2 4 5**s2**5 BR1(s2) 4 3 BR2(s1) 2 1 0 s1 1 3 2 4 5**s2**BR1(s2) 2 7/4 BR2(s1) 6/4 5/4 1 s1 5/4 7/4 6/4 2**The Partnership Game (9)**• We started with a game • We found what player 1 BR was for every possible choice of player 2 • We did the same for player 2 • We eliminated all strategies that were never a BR • We looked at the ones that were left, and eliminated those that were never a best response • … • Where are we going to?**The Partnership Game (10)**s*1 = 1 + b s2 s*2 = 1 + b s1 The intersection s*1 = s*2 s*1 = 1/(1-b)**The Partnership Game (11)**• We came up with a prediction on the effort levels • Question: is the amount of work we found previously a good amount of work? • Compared to what? • Question: are the players working more or less than an efficient level?**The Partnership Game (12)**• Why is it that in a joint project we tend to get inefficiently little effort when we figure out what’s the best response in the game? • NOTE: this is not a PD situation • “I’m gonna let the other work and I’ll shirk” • Why?**The Partnership Game (13)**• The problem is not really the amount of work • Also, the problem is not about synergy, i.e. the factor b • The problem is that at the margin, I bear the cost for the extra unit of effort I contribute, but I’m only reaping half of the induced profits, because of profit sharing • This is known as an “externaility” • When I’m figuring out the effort I have to put I don’t take into account that other half of profit that goes to my partner • In other words, my effort benefits my partner, not just me**The Partnership Game (14)**• By the way, how would the situation change by varying the only parameter of the game? • Informally, what we have done so far is to determine the Nash Equilibrium of the game**Introducing NE**• So in the partnership game we’ve seen what a NE is… • Recall the numbers game: what was the NE there? • Did you play a NE? • Although NE is a central idea in game theory, be aware that it is not always going to be played • By repeating the numbers game, however, we’ve seen that we were converging to the NE**Why is it an important concept?**• It’s in textbooks • It’s used in many applications • Don’t jump to the conclusion that now we know NE, everything we’ve done so far is irrelevant**NE: observations**• It is not always the case that players play a NE! • E.g.: in the numbers game, we saw that playing NE is not guaranteed • Rationalitydoes not imply playing NE • What are the motivations for studying NE?**NE: motivations (1)**NO REGRETS • Holding everyone else’s strategies fixed, no individual has a strict incentive to move away • Having played a game, suppose you played a NE: looking back the answer to the question “Do I regret my actions?” would be“No, given what other players did, I did my best”**NE: motivations (2)**Self-fullfilling beliefs • If I believe everyone is going to play their parts of a NE, then everyone will in fact play a NE • Why?**s2**Let’s play a little bit with this graph: - Graphical way of finding NE 5 BR1(s2) 4 3 2 1 0 s1 1 3 2 4 5**Finding NE point(s)**• Next we will play some very simple games involving few players and few strategies • Get familiar with finding NE on normal form games • We will have a glimpse on algorithmic ways of finding NE and their complexity**A simple game (1)**Player 2 c r l • Is there any dominated strategy for player 1/2? • What is the BR for player 1 if player 2 chooses left? • What is the BR if player 2 chooses center? • What about right? • Can you do it for player 2? U Player 1 M D**A simple game (2)**Player 2 c r l • BR1(l) = M BR2(U) = l • BR1(c) = U BR2(M) = c • BR1(r) = D BR2(D) = r What is the NE? Why? U Player 1 M D**A simple game (3)**• It looks like each strategy of player 1 is a BR to something • And the same is true for player 2 • Deletion of dominated strategies wouldn’t lead anywhere here… • Would it be rational for player 1 to chose “M”?**Another simple game (1)**Player 2 c r l • What is the NE for this game? • What’s tricky in this game? • Do BR have to be unique? • Are players happy about playing the NE? U Player 1 M D**NE vs. Dominance (1)**• We’ve seen how to find NE on a normal form game • We’ve seen how NE relates to the idea of BR • We have a NE when the BR coincide • What is the relation between NE and the notion of dominance?**NE vs. Dominance (2)**Player 2 • What is this game? • Are there any dominated strategies? • What is the NE for this game? beta alpha alpha Player 1 beta**NE vs. Dominance (3)**• Claim: no strictly dominated strategies could ever be played in NE • Why? A strictly dominated strategy is never a best response to anything • What about weakly dominated strategies?**NE vs. Dominance (4)**Player 2 • Are there any dominated strategies? • What is the NE for this game? r l l Player 1 r**NE vs. Dominance (5)**• First observation: the game has 2 NE! • Informally we’ve seen that a NE can be: • Everyone plays a BR • None has any strict incentive to deviate • What’s annoying here? What is the prediction game theory leads us to? • Is that reasonable?**The Investment Game (1)**• The players: you • The strategies: each of you chose between investing nothing in a class project ($0) or invest ($10) • Payoffs: • If you don’t invest your payoff is $0 • If you invest you’re going to make a net profit of $5 (gross profit = $15; investment $10)This however requires more than 90% of the class to invest. Otherwise, you loose $10 • As usual no communication please!!**The Investment Game (2)**• What did you do? • Who invested? • Who did not invest? • What is the NE in this game?**The Investment Game (3)**• There are 2 NE in this game • All invest • None invest • Let’s check: • If everyone invests, none would have regrets, and indeed the BR would be to invest • If nobody invests, then the BR would be to not invest