CSCI 1440/2440 Introduction to Game Theory - Homework 1: Nash equilibrium
Homework 1: Introduction to Game Theory CSCI 1440/2440
2022-01-27
Due Date: Tuesday, February 1, 2022. 11:59 PM.
We encourage you to work in groups of size two. Each group need only submit one solution. Your submission must be typeset using LATEX. Please submit via Gradescope with you and your partner’s Banner ID’s and which course you are taking.
For 1000-level credit, you need only solve the first two problems. For 2000-level credit, you should solve all three problems.
Extra Credit: We think the third problem is really fun and inter- esting. So if you are in the 1000-level class and have the time and inclination, please go ahead and solve it for extra credit.
1 Rock-Paper-Scissors
Lisa’s Brain: Poor predictable Bart; always takes rock. Bart’s Brain: Good ol’ rock. Nothin’ beats that! Bart: Rock! Lisa: Paper. Bart: D’oh! -The Simpsons, Season 4, Episode 19: The Front
In the game rock-paper-scissors, two players simultaneously se- lect one of three possible actions: rock, paper, or scissors. You might recall from your childhood, or The Simpsons, that rock beats scissors, scissors beats paper, and paper beats rock. The outcomes are expressed as a payoff matrix in Figure 1.
Rock Paper Scissors
Rock 0, 0 1, -1 -1, 1
Paper -1, 1 0, 0 1, -1
Scissors 1, -1 -1, 1 0, 0
Figure 1: The payoff matrix describing the payoffs in rock-paper-scissors. If the row player selects Rock, and the column player selects Scissors, then the row player receives payoff 1, and the column player receives payoff -1.
1. Explain why no Nash equilibria exist when players use pure strategies.
2. Find all symmetric Nash equilibria that involve mixed strategies. Give an intuitive explanation for your solution.
2 Stag Hunt
Jean-Jacques Rousseau describes a social dilemma that can arise on a stag hunt. Hunters have tracked a stag, and are lying in wait.
Hours go by without the stag reappearing. In the meantime, a hare appears. A single hunter can kill and eat a hare. Eating a hare brings mild satisfaction, but not as much satisfaction as sharing a stag with friends. Thus, each hunter faces a dilemma: should he continue to wait for the stag, thereby cooperating with the others, or should he defect by killing and eating the hare himself?
In the two-player version of the stag hunt, Alice and Bob are hunters planning a joint expedition. Each must decide independently whether to hunt the stag or the hare. Neither can kill the stag alone, but both prefer to hunt the stag if the other does. Alternatively, either can kill the hare alone. If one hunts the stag and the other the hare, the one who hunts the stag goes home hungry, while the other enjoys the hare. The payoff matrix is shown in Figure 2.
Stag Hare
Stag 4, 4 0, 3
Hare 3, 0 3, 3
- Draw the best response correspondences for each player on the same graph. Your solution can be hand drawn, but please insert a picture of your drawing into your latex file.
- Label all Nash equilibria that involve pure strategies.
- Label all Nash equilibria that involve mixed strategies.
- What are the expected payoffs at each of these Nash equilibria?
- Comment on the two pure-strategy Nash equilibria in this game. What are the pros and cons of each?
3 The Bystander Effect
Amy’s husband Justin tells a story of how, as a Ph.D. student at CMU, he single-handedly saved the city of Pittsburgh. He was walk- ing along a sidewalk, and he smelled smoke. So he walked to the back of a nearby driveway, where through the rear basement window, he spotted orange flames. He found a public fire alarm box (there was life before cell phones), and called the fire department. When the firefighters arrived, they thought it was a prank, until he led themto the fire, at which point they immediately swung into action: axes, hoses, etc. As you can see from this story, there was a cost to call- ing the fire department. Justin was probably late to get to wherever he was going; he had to deal with the wrath of the fire department when they thought it was a prank; etc. On the other hand, he now has a story to tell, about how he saved the city of Pittsburgh.
Let’s turn this story into a game. Justin’s best friend duringtheir first year at CMU was Michael Littman, now a world-class reinforcement-learning researcher here at Brown who also dabbles in game theory. Suppose both Justin and Michael were walking down the street, in opposite directions, without seeing or communicating with one another, when they both smelled smoke. They could choose to investigate, which would incur some cost, but could also save the city; or they could choose to walk on, hoping the other would incur the cost, and they would reap the benefits for free.
Here’s one way to formalize this scenario. The actions are call the fire department, or don’t call. And the payoffs are:
- 1 to any free-rider who does not call, if the city is saved
- 1 − ε to anyone who calls (let’s assume the cost of calling is ε, for some 0 < ε < 1)
- 0 if nobody calls, and the city burns to the ground
Finally, let’s add a few more players—more potential bystanders— beyond only Justin and Michael, all of whom are walking down the sidewalk, and acting independently of the others.
- Describe the pure-strategy Nash equilibria in this game.
- Find the unique symmetric mixed-strategy Nash equilibrium of this game with 3 players. N.B. At the symmetric equilibrium, all players call and don’t call with equal probabilities.
- Find the symmetric Nash equilibrium of this game with n players.
- At this equilibrium, how does the probability that nobody calls and the city burns to the ground vary with the number of by- standers? Does it increase, decrease, or remain constant?
- In the limit, as n → ∞, what is the probability that no one calls?
