Game Theory
Introduction to Game Theory
Why do countries arm up even though peace would be better for everyone? Why do firms cut prices to zero? Why does a goalkeeper dive randomly? Behind these different questions lies a single mathematics - game theory: the science of how rational agents make decisions when the outcome depends on others' actions.
- **Auctions:** Google sells ads through a Vickrey second-price auction - a design based on game theory (Nobel 2020, Milgrom and Wilson)
- **Biology:** Animal survival strategies (hawk vs. dove) are modeled by evolutionary game theory - ESS (evolutionarily stable strategies)
- **AI:** Algorithms for poker (Libratus, Pluribus) and Go (AlphaGo) are based on finding Nash equilibria and minimax
Players and Rationality
Two companies decide whether to cut prices. Two states choose: arm or disarm. Two drivers head toward each other and decide whether to swerve or not. All these situations are **games** in the mathematical sense: participants make decisions that affect the outcome for everyone.
A formal model of strategic interaction. Defined by three elements: 1. a set of players N = {1, 2, ..., n} 2. a set of strategies Sᵢ for each player 3. a payoff function uᵢ: S₁ × S₂ × ... × Sₙ → R for each player.
A **player** is a decision-maker. It can be a person, a firm, a state, a biological species, or an algorithm. The key assumption of classical game theory: players are **rational** - each maximizes their payoff, knowing that the others do the same.
Rationality is a strong assumption. Behavioral economics (Kahneman, Tversky) showed that people systematically deviate from rationality. But rationality is a useful starting point: first understand how ideal agents 'should' behave, then study the deviations.
Games can have **complete information** (everyone knows the rules and all payoffs) or **incomplete information** (someone doesn't know others' payoffs). Chess has complete information (all pieces are visible), poker has incomplete information (opponent's cards are hidden). We'll start with complete information.
What does 'rationality' mean for a player in game theory?
Pure and Mixed Strategies
A **strategy** is a complete plan of action for a player covering all possible situations. In simple games a strategy is a single action (Cooperate or Defect). In complex games it is a decision tree: 'if the opponent does X, I do Y; if Z - I do W'.
A definite choice of action. The player knows exactly what they will do. The set of pure strategies Sᵢ is a finite (or infinite) collection of options.
A probability distribution over pure strategies. The player randomizes their choice: plays strategy A with probability p and strategy B with probability (1-p).
Why randomize? Consider a goalkeeper facing a penalty kick. If they always dive left - the kicker will learn this and shoot right. The optimal strategy is to dive randomly with certain probabilities, to remain unpredictable.
Rock-Paper-Scissors is a game with no 'best' pure strategy (each one loses to one of the other two). The only optimal strategy is mixed: play each option with probability 1/3. Any deviation from uniformity can be exploited.
A strategy profile is a combination of all players' strategies: s = (s₁, s₂, ..., sₙ). The notation s₋ᵢ means 'the strategies of all players except i'. This notation is key for defining Nash equilibrium.
When does a rational player choose a mixed strategy?
Payoff Function
The **payoff function** uᵢ(s₁, s₂, ..., sₙ) is a number reflecting the 'happiness' of player i under a given strategy profile. The higher it is, the better for the player. It can be profit, pleasure, years of freedom, or any other measure of 'utility'.
Important: payoffs represent **ordinal utility** (order matters more than absolute values). If u(A) = 10 and u(B) = 5, this only means 'A is better than B for the player', not 'A is exactly twice as good'. For mixed strategies, **cardinal utility** is needed - expected payoff: E[u] = Σ p(s) · u(s).
Games are classified by their payoff type: **antagonistic** (zero-sum) - one player's gain equals the other's loss (chess, poker); **cooperative** - the total can grow (trade); **mixed** - both conflict and cooperation (prisoner's dilemma).
| Game type | u₁ + u₂ | Example |
|---|---|---|
| Zero-sum | = 0 always | Chess, poker, penalty kicks |
| Positive-sum | > 0 possible | Trade, alliances |
| Negative-sum | < 0 possible | War, arms race |
| Variable-sum | Depends on outcome | Prisoner's dilemma |
What does a zero-sum (antagonistic) game mean?
Normal Form and the Prisoner's Dilemma
The **normal form** (strategic form) is the simplest way to write down a game: a matrix where rows are player 1's strategies, columns are player 2's strategies, and the cells contain pairs of payoffs (u₁, u₂).
The **Prisoner's Dilemma** is the most famous game in game theory. Two suspects are arrested. Each can stay silent (Cooperate) or betray their accomplice (Defect). The paradox: the rational choice of each (to betray) leads to the worst outcome for both (-2, -2), even though mutual silence (-1, -1) would be better.
The logic of each prisoner: 'If the other stays silent, it's better for me to betray (0 > -1). If the other betrays, it's also better for me to betray (-2 > -3). Whatever the other does, it's better for me to betray.' Both reach this conclusion - and both betray.
Origin of the Prisoner's Dilemma
The game was formalized by Merrill Flood and Melvin Dresher in 1950 at RAND Corporation. Albert Tucker invented the prisoner story and gave the game its name. Since then, the prisoner's dilemma has become the canonical example of the conflict between individual rationality and the collective good.
The prisoner's dilemma appears everywhere: arms races (each country arms up, even though mutual disarmament would be better), pollution (each firm pollutes, even though a clean environment is better for all), doping in sports (everyone dopes, even though clean sport is better).
The normal form is a convenient notation, but it doesn't show the order of moves. For sequential games (chess, negotiations) the **extensive form** is used - a decision tree. We'll study that later; for now we focus on simultaneous games in normal form.
Game theory is about board games and video games
Game theory is a branch of mathematics about the strategic interaction of rational agents. It is applied in economics, political science, biology, computer science, military affairs, and auction design.
The word 'game' here is a formal term for any situation where the outcome depends on the decisions of multiple participants. Nobel Prizes in game theory were awarded to economists (Nash, Schelling, Aumann), not board game designers.
Why do both rational players betray in the prisoner's dilemma, even though mutual cooperation would be better?
Key ideas
- **Game** = (players, strategies, payoffs) - a formal model of strategic interaction
- **Pure strategy** - a definite choice; **mixed strategy** - randomization for unpredictability
- **Normal form** - a payoff matrix for simultaneous games
- **Prisoner's dilemma** shows: individual rationality can lead to a collectively worse outcome
Related topics
Introduction to game theory opens the way to fundamental results:
- Nash Equilibrium — The central concept - a strategy profile from which no one benefits by deviating
- Dominance and Iterated Elimination — A systematic method for simplifying games by removing 'bad' strategies
Вопросы для размышления
- The prisoner's dilemma shows a conflict between individual and collective rationality. What real-life situations exist with this structure in everyday life?
- If we assume players are NOT rational (they make mistakes, are driven by emotions) - how does that change the analysis of the game?
- Why does a goalkeeper on a penalty kick not always dive in the same direction, even if statistics show the kicker more often shoots to the left?