Introduction to Game Theory (Part 1)
Check out this game theory basics post for an introduction to Two-player Sequential games — Dominant Strategies, Nash Equilibrium, and Cooperation vs. Defection.
By Devin Soni, Computer Science Student
Game theory generally refers to the study of mathematical models that describe the behavior of logical decision-makers. It is widely used in many fields such as economics, political science, politics, and computer science, and can be used to model many real-world scenarios. Generally, a game refers to a situation involving a set of players who each have a set of possible choices, in which the outcome for any individual player depends partially on the choices made by other players.
One of the main types of games in game theory is the simultaneous game, in which both players make their moves simultaneously (or if they do not, the later player is unaware of the earlier player’s action, making it effectivelysimultaneous). Sequential games are often represented in normal form, which, for a game with 2 players and N possible moves for each player, consists of an N x N matrix where each entry is a 2-tuple containing the payoff for each respective player.
To illustrate this, consider the below example. This is a type of sequential game called the Prisoner’s Dilemma, in which each prisoner has the option to either betray the other prisoner for a reduced punishment (Confess), or cover up for the other prisoner and hope the other prisoner does the same (Lie). In each cell of the matrix, the first element of the tuple represents the payoff for Prisoner 1, and the second element represents the payoff for Prisoner 2. One reads this payoff matrix by first identifying the choice (Confess or Lie) that each player will make, and then locating the matrix entry that corresponds to that row and column. For example, if Prisoner 1 chooses Confess and Prisoner 2 chooses Lie, you would read the matrix entry in the 1st row and 2nd column, giving Prisoner 1 a payoff of 0 and Prisoner 2 a payoff of -10.
In a simultaneous game, each player must make decisions based on what he assumes the other player will do. Remember that in game theory, we assume that players are rational decision-makers who want to maximize their payoff. One method of predicting the game’s outcome is by identifying dominant strategies for each player. A dominant strategy is one that is the best for a given player regardless of the choice of the other player — so regardless of what Prisoner 2 does, a dominant strategy for Prisoner 1 is the optimal strategy for Prisoner 1.
In the Prisoner’s Dilemma game, we can observe that the dominant strategy for both players is to Confess. First, note that this payoff matrix is symmetric, so each player has the same payoff for each choice. This means that when identifying dominant strategies, we only need to consider one player’s dominant strategy, as it will also be a dominant strategy for the other player. Now, to find Prisoner 1’s (and Prisoner 2’s) dominant strategy, we need to find Prisoner 1’s best-choice move for each of Prisoner 2’s possible choices. If Prisoner 2 chooses to Confess, Prisoner 1 gets a payoff of -8 by Confessing and a payoff of -10 by Lying, so he will choose to Confess. If Prisoner 2 chooses to Lie, Prisoner 1 gets a payoff of 0 by Confessing and a payoff of -1 by Lying, so he will again choose to Confess. Therefore, Prisoner 1 has a dominant strategy that is to always Confess, since regardless of Prisoner 2’s choice, Confessing is Prisoner 1’s best option. This same analysis applies to Prisoner 2’s dominant strategy. Therefore, in the Prisoner’s Dilemma game, both Prisoners will ultimately choose to Confess.
The (Confess, Confess) option is therefore a Nash Equilibrium. A Nash Equilibrium is a set of choices in which no player has anything to gain by changing only their own choice. Since we have identified that Confess is the dominant strategy for both Prisoners, we already know that neither player has anything to gain by switching. Therefore, since each player is playing his dominant strategy, that set of choices is a Nash Equilibrium.
The Prisoner’s Dilemma game is an example of situation in which two rational decision-makers will choose not to cooperate (defect) with each other despite the fact that cooperation (both choosing Lie) would result in a better payoff for both Prisoners ((-8, -8) vs. (-1, -1)). In such an uncooperative game, by choosing their own individual dominant strategy, the two prisoners fail to make the choice that is actually optimal. The individual’s rational strategy conflicts with the societal, or global, optimal strategy. In general, simultaneous games such as the Prisoner’s Dilemma provide us with formalized methods to study conflict and cooperation. This specific scenario that results in a lack of cooperation shows up in several fields such as politics, economics, and biology. These examples illustrate that while the “best” option in many real world situations may be to cooperate, rational players, thinking as individuals, will choose not to cooperate with each other since they cannot trust the other player to cooperate.
You can also follow me on Twitter!
Original. Reposted with permission.
- Introduction to Markov Chains
- Supervised vs. Unsupervised Learning
- Introduction to k-Nearest Neighbors