GAME THEORY
October 11, 2008
Jack Brennen
Game Theory: “the modern mathematical approach to interest conflict.” (Luce and Raiffa, 1957.)
The discipline of Game Theory is fairly new; it traces its roots to the 1928 paper by John von Neumann, “Zur Theorie der Gesellschaftsspiele” (On the Theory of Parlor Games).
Three recommended books on Game Theory:
Ranked from least rigorous math to most…
Game Theory: A Nontechnical Introduction, Morton D. Davis, 1970.
Games and Decisions: Introduction and Critical Survey, R. Duncan Luce and Howard Raiffa, 1957.
Theory of Games and Economic Behavior, John von Neumann and Oskar Morgenstern, 1944.
Does anyone really use game theory for anything serious? Apparently so. The Nobel Prize in Economics has been awarded to game theorists 3 times in the last 15 years, with a total of 8 game theorists being recognized. The most famous by far is the American mathematician John Nash, whose story was told in the book and movie, “A Beautiful Mind.”
A SIMPLE GAME
To illustrate the mechanics of Game Theory, let’s analyze a simple game which is known worldwide, the game of Rock, Paper, Scissors (also called “Roshambo”).
In this game, two players simultaneously choose and reveal their chosen “strategy” between the three choices – Rock, Paper, Scissors.
In this game, Rock defeats Scissors, Scissors defeats Paper, and Paper defeats Rock. The loser pays the winner one unit.
Payoff matrix:
P2 – Rock / P2 – Scissors / P2 – PaperP1 – Rock / (0, 0) / (1, -1) / (-1, 1)
P1 – Scissors / (-1, 1) / (0, 0) / (1, -1)
P1 – Paper / (1, -1) / (-1, 1) / (0, 0)
Discussion points:
-Is this game zero-sum?
-Is this game fair?
-Is this game balanced?
-Is there any strategy which guarantees a win for either player?
-Is there any strategy which guarantees to break even?
-If my opponent knows my strategy, can he exploit that knowledge?
Pure vs. Mixed Strategies
A pure strategy is one where you choose your strategy deterministically without deviation using only “common knowledge”.
Examples of pure strategies in Rock, Paper, Scissors:
-Always play Rock
-Always play the same strategy that your opponent played on the last round.
-Always play the strategy that would have defeated your opponent on the last round
-Play Paper before noon, play Scissors after noon.
A mixed strategy is one where you choose your strategy “randomly” using knowledge which is not common. The “randomness” may come from rolling a die, flipping a coin, consulting a table of random numbers, or some other source.
Examples of mixed strategies in Rock, Paper, Scissors:
-Play Rock 1/3 of the time, Paper 1/3 of the time, Scissors 1/3 of the time
-Play Rock 3/4 of the time, Paper 1/8 of the time, Scissors 1/8 of the time
-Repeat your last strategy 1/2 of the time, repeat your opponent’s last strategy 1/2 of the time
In Game Theory, we generally assume that our opponent knows our strategy. Does this argue for or against a pure strategy?
Nash Equilibrium
A Nash Equilibrium is a set of strategies (one pure or mixed strategy for each player) with the property that no player has any incentive to unilaterally change his own strategy. In other words, each player can say, “if everyone else’s strategy is set in stone, then I’m doing the best I can.”
-Does a Nash Equilibrium exist among pure strategies for Rock, Paper, Scissors?
-Does a Nash Equilibrium exist among mixed strategies for Rock, Paper, Scissors?
A Non Zero-Sum Game
Assume a variant called Rock, Paper, where both players choose simultaneously to play either Rock or Paper. If both choose Rock, they each receive $10 from a rich benefactor; if they both choose Paper, they each receive $1, and if one plays Paper and one plays Rock, neither receives anything.
Payoff matrix:
P2 – Rock / P2 – PaperP1 – Rock / (10, 10) / (0, 0)
P1 – Paper / (0, 0) / (1, 1)
Discussion points:
-How many Nash Equilibria are there in this game?
-Is there any strategy which guarantees a win for either player?
-If my opponent knows my strategy, can he exploit that knowledge?
-Would a “rational” player ever choose to play Paper? Why or why not?
Pareto Optimality
A set of strategies is called “Pareto Optimal” if any other set of strategies which improves one player’s expected outcome necessarily diminishes some other player’s expected outcome. If one or more players can change their strategy and end up with everybody’s expected outcome either better or unchanged, then the set is not Pareto optimal.
Discussion points:
-Describe the Pareto Optimal strategy sets in Rock, Paper, Scissors?
-Describe the Pareto Optimal strategy sets in the Rock, Paper variant above.
-Will “rational” players always attempt to find a Pareto optimal situation.
Prisoner’s Dilemma
Two criminals are caught for the same crime. The prosecutors offer each prisoner a deal… Snitch on the other guy, and you’ll get a lighter sentence than if you don’t. If both snitch, they each get 7 years in prison. If one snitches on the other, he gets 3 months and the other guy gets 10 years. If neither snitches, they each do 1 year in prison.
Payoff matrix:
P2 – Snitch / P2 – Keep QuietP1 – Snitch / (-7, -7) / (-0.25, -10)
P1 – Keep Quiet / (-10, -0.25) / (-1, -1)
Discussion points:
-How many Nash Equilibria are there in this game?
-How many Pareto optimal strategy sets are there in this game?
-Would a “rational” criminal ever fail to snitch?
-What do we mean when we say that keeping quiet is “dominated” by snitching?
Example Games For In-Class Analysis
The first set of games all have to do with Player A and Player B each choosing an integer from 1 to 10. They simultaneously reveal their choices, and then they determine the payoff by some set of rules. In the rules, we assume that A and B refer to the numbers chosen by the two players.
For each, we will do an analysis of fairness, strategy, equilibrium, domination, optimality, cooperation, and competition.
Game 1: If A+B is composite, both players receive a payoff of A+B.
Game 2: If A+B is prime, both players receive a payoff of A+B.
Game 3: If A+B is square, both players receive a payoff of A+B.
Game 4: If A+B is prime, player A receives A, player B receives B.
Game 5: If A+B is square, player A receives A, player B receives B.
Game 6: The player who picks the highest number receives a payoff equal to his number and the other player receives nothing. If both players pick the same number, each receives a negative payoff equal to 5 times that number.
Game 7: “Nash bargaining game”… If A+B <= 10, player A receives A, player B receives B. Otherwise, neither player receives any payoff.