A Brief Introduction to Game Theory
Game Theory is a field shared by math and economics that aims to describe strategies and outcomes of games. A game is simply a set of possible decisions and their outcomes. While Game Theory is immediately applicable to certain board games (Tic-Tac-Toe and Chess among others), its usefulness goes far beyond into areas such as public policy and business strategy.
A pure game is one that is turn-based, deterministic, moves sequentially, and has perfect information. Pure games range from the extremely simple (Matching Pennies) to the very challenging (Go). Notably, they do not include games of chance which rules out much of what people think of as games (for example: Monopoly). While there are ways to deal with more complex games, it is more prudent to first study the simplest cases: 2-player pure games.
Consider the game of Matching Pennies where there are two players, each with a coin:
Player 1 selects heads or tails.
Then Player 2 selects heads or tails.
If the sides match, Player 2 wins.
If they do not, Player 1 wins.
Whoever does not win, loses.
Some pseudocode to describe the game would be as follows:
[code language=”javascript”]
s1 = getChoiceFromP1();
s2 = getChoiceFromP2();
if (s1 == s2) {
p2 wins
} else {
p1 wins
}
[/code]
The first game theoretic way to view a game is a decision tree called the “Extended Form.”
The following image is the extended form of Matching Pennies:
The Extended Form of Matching Pennies
Some notes about the above image: “H” refers to a player choosing heads as their strategy and “T” refers to a player choosing tails. Each outcome (at the bottom of the “pyramid”) is denoted as a pair. Each pair has Player 1’s outcome as the first number and Player 2’s outcome as the second number. For instance, if both players choose heads, then Player 2 will get 1 point and Player 1 will get zero. This aligns with the pseudocode written above.
It will be useful to view the same game as a combination of strategies and outcomes in what is defined as the “Normal Form.” This is the second and last Game Theory diagram we will discuss. The normal form of Matching Pennies is shown below:
The Normal Form of Matching Pennies
For this game, both the normal form and the extended form are visually simple but for larger games (for example: Chess) both diagrams will become too large and complex to humanly understand. However, the normal form allows us to view the outcomes of simultaneous and repeated games more easily which is crucial for determining Nash Equilibria.
A Nash Equilibrium is a combination of strategies where knowing a player’s strategy in advance would not cause the other player to change strategies. In Matching Pennies, no Nash Equilibria exist (because each player’s optimal strategy depends on knowing what the other player will do).
A famous example of a game with a Nash Equilibrium is The Prisoner’s Dilemma as pictured here:
The Normal Form of a version of the Prisoner’s Dilemma
The Prisoner’s Dilemma is usually told as follows:
Two criminals have been brought in with moderate evidence. If one of them confesses, he stands to spend far less time in prison. If both confess however, each will spend far more time than if neither had. The strategies are named for their relation to the other player, not to authority. So, in the above image, “C” stands for “Cooperate” and “D” stands for “Defect.” Each player seeks to maximize their own point value, so more points means more time spent on the outside.
The Nash Equilibrium in the Prisoner’s Dilemma is noteworthy because it is not the optimum for either player. Both players would get more points by cooperating but because of the way incentives are set up, they can each count on the other defecting, and will therefore defect themselves. However, when the game is repeated over many iterations, more interesting strategies come into play.
The Prisoner’s Dilemma’s incentive structure mirrors real world societal problems like the Tragedy of the Commons. In both cases, we have a suboptimal outcome due to incentives that skew towards non-cooperation. The Prisoner’s Dilemma allows for a very simple mathematical model in which to sandbox solutions. When the game is repeated, the strategies (and therefore outcome) of a given round can depend on the actions taken in previous round(s). Some longer term strategies (there’s no way to avoid overloading this word so we’ll use “action” for the single time period “strategy”) include: Tit-for-Tat, Grudging, Always Cooperate, Always Defect. Always Cooperate and Always Defect are fairly self-explanatory: every turn the agent takes the same action: Cooperate or Defect respectively. Tit-for-Tat uses the last action the other agent used. Grudging is when an agent always cooperates until its opponent defects.
The justification for the repeated games is that this is often how dilemmas work in real life. Two criminals may be working together consistently. Renewable pools of resources are slowly rundown but can also be repopulated with some effort. As far as the Tragedy of the Commons goes, it is possible to add all sorts of ornaments to modify people’s behavior. For example, vouchers and limits can be added to prevent people from overusing their share. Offenders can be prevented from further access. People could be charged nominal fees that go to increasing the health of the shared resource. All of these modifications would modify the outcomes of strategies in the underlying game. This is part of the reason for the significance of The Prisoner’s Dilemma: it provides a simple case (2 players, 2 options per player) where it is difficult to hand-wave away the core problem (mismatched incentives).
Game Theory is a useful field to have at least a basic understanding of. Its applications vary from games to business to psychology to sociology and anthropology. Although the field is fairly stagnant today, there’s a lot more that didn’t make it into this post. For further reading, consider looking into finding Nash Equilibria via Dominated Strategies, Evolutionarily Stable Strategies, and signaling (how games relate to markets with imperfect information).
