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.

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.

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).

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.

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.

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?

Связанные уроки

• prob-04-bayes