Game Theory

Definitions

Prisoner's Dilemma

— the most famous example. Two suspects in different cells. Each can Remain Silent (S) or Betray (B). Payoffs are in years of imprisonment (negative: the fewer, the better):

"Chicken" Game

— two drivers speed toward each other. Swerve = lose face ("chicken"). Not swerving = risk of catastrophe.

Pure strategy

— a deterministic choice of one action. For example, "always play Rock."

Formulas

Most life tasks are solved individually: how much to study, how to allocate your budget, when to go to bed. But a whole class of decisions is fundamentally different—their outcome depends not only on your actions, but also on the actions of other people. A driver on the road, a company setting pr...

Game theory is a mathematical science of decision-making in situations of interdependence. The foundations were laid by John von Neumann and Oskar Morgenstern in the book "Theory of Games and Economic Behavior" (1944). John Nash in 1950 proposed the concept of equilibrium, and in 1994 he received...

Each player i chooses a strategy sᵢ ∈ Sᵢ, and their payoff uᵢ(s₁, s₂, ..., sₙ) depends on the strategies of all participants. Each player seeks to maximize their own payoff, knowing that others are doing the same.

By sum of payoffs: zero-sum games—one player's gain equals another's loss (chess, poker); nonzero-sum games—mutual gain or loss is possible (negotiations, trade).

Imagine that all players have already announced their strategies. When does no one have an incentive to unilaterally change their strategy? This state is called a Nash equilibrium. It is not necessarily the “best” outcome for everyone—it is stable, in the sense that each player has an incentive t...

Formally, a strategy profile s* = (s₁*, ..., sₙ*) is a Nash equilibrium if for each player i:

Here, s₋ᵢ* means the strategies of all other players except i. In other words: given fixed opponent strategies, sᵢ* is the best response for i.

Theorem: Any finite strategic game (finite number of players and strategies) has an equilibrium in mixed strategies.

Definitions

If IESDS leads to a single profile

— it is the unique Nash equilibrium. If it leads to several — IESDS has not solved the problem of equilibrium selection.

Before searching for a Nash equilibrium, it is useful to ask a simpler question: are there strategies that are never profitable to use? Such strategies are called dominated: no matter what the opponents do, another strategy is always better. A rational player will never choose a dominated strateg...

By repeating this procedure iteratively, we sometimes arrive at a single outcome — the equilibrium. This method requires not only rationality from each player, but also common knowledge of rationality: I know you are rational; you know that I know; and so on.

Strict domination: Strategy $s_i$ strictly dominates $s_i'$ if for all $s_{-i} \in S_{-i}$: $u_i(s_i, s_{-i}) > u_i(s_i', s_{-i})$. A strictly dominated strategy is never chosen by a rational player, regardless of beliefs about the opponents.

Weak domination: $u_i(s_i, s_{-i}) \geq u_i(s_i', s_{-i})$ for all $s_{-i}$, and for at least one $s_{-i}$ the inequality is strict. Weakly dominated strategies require more careful handling — elimination may depend on the order.

In real business and politics, decisions are made sequentially, and later players observe earlier moves. A company decides to enter a market, knowing that the incumbent firm may later initiate a price war. Parties make alternating proposals in negotiations. Countries impose sanctions in response ...

In such situations, Nash equilibrium permits "empty threats" — actions that are announced but would not rationally be carried out. The concept of subgame perfect equilibrium (SPNE) eliminates such threats.

A dynamic game is depicted by a tree: nodes are decision points, edges are actions, leaves are payoffs. Additionally, information sets (nodes among which the player cannot distinguish) describe incomplete information about the course of the game.

A subgame is a fragment of the tree starting at a single node (singleton information set) and including all its subtrees. A subgame must be "closed": information sets cannot be cut.

Formulas

In real games, information is often asymmetric: an insurance company does not know the health status of a client, an investor does not know the intentions of a manager, a buyer does not know the cost of goods. How do we analyze strategic interaction when players have private information?

Harsanyi (Nobel Prize 1994) proposed an elegant solution: introduce the notion of a type of a player—their private information—and model incomplete information as the random selection by nature of each player's type.

A type θᵢ of player i is his or her private characteristic (willingness to pay, production function, risk preferences). The type space is Θᵢ; nature "chooses" θ from the joint distribution μ(θ).

A Bayesian game in normal form: ⟨N, (Sᵢ), (Θᵢ), μ, (uᵢ)⟩. A strategy bᵢ: Θᵢ → Sᵢ is a rule of action for each possible type.

When two agents interact only once, the prisoner’s dilemma leads to mutual defection. But in real business relationships, companies meet over and over again—quarterly negotiations, repeat purchases, long-term contracts. In such conditions, the “shadow of the future”—the expectation of repeated in...

Repeated games are a model that formalizes this mechanism. They explain why honesty can be strategically profitable and how tacit collusion arises without explicit agreements.

Standard game G (stage game) is played in periods t = 1, 2, 3, ... Player i discounts the future with factor δᵢ ∈ (0, 1): the payoff in the next period is worth δ times less today. The total (normalized) payoff:

Normalization by (1−δ) makes Vᵢ comparable to the payoff in a single stage. When δ → 1: the player is patient, highly values the future. When δ → 0: “lives only for today,” the future does not matter.

Definitions

Core

— the set of allocations that cannot be "blocked" by any coalition: x ∈ Core(v) if and only if for all S ⊆ N: Σᵢ∈S xᵢ ≥ v(S).

Formulas

In cooperative game theory, the question is different: not "how do players interact strategically," but "how do they share the jointly created payoff." It is assumed that players can make binding agreements—the main question is which distribution is "fair" and "stable."

Examples: profit allocation in a joint venture; sharing costs for construction of joint infrastructure; allocation of power in a political coalition.

TU-game (with transferable utility) is defined by the pair (N, v): N = {1, ..., n}—the players; v: 2^N → ℝ—the characteristic function (v(S)—the maximum joint payoff of coalition S). Usually v(∅) = 0.

Superadditivity: v(S∪T) ≥ v(S) + v(T) when S∩T = ∅. This is the condition "it is beneficial to unite"—standard for most economic applications.

Formulas

The core is an attractive concept, but it has two drawbacks: it can be empty (no stable allocation exists) and non-unique (many stable allocations). The nucleolus and stable sets are alternative concepts, each with its own logic.

For an allocation x and coalition S, define the excess $e(S, x) = v(S) - \sum_{i \in S} x_i$. Positive excess: coalition S can "do better" for itself if it breaks off. Negative: the coalition "loses out" by breaking off.

The nucleolus is the allocation x that lexicographically minimizes the vector of excesses for all coalitions, ordered in descending order. First, we minimize the maximal excess; then, among allocations with the maximally "satisfied" ones fixed, we minimize the next one, and so on.

Schmeidler (1969): the nucleolus exists and is unique for any game. If the core is non-empty, the nucleolus lies within it.

On most markets, price balances supply and demand. But there are markets where monetary transfers are impossible or undesirable for ethical or legal reasons: allocating students to schools, residents to hospitals, donor organs to patients. Here, mechanisms are needed that provide a "fair" and "st...

Matching theory is a mathematical tool for such markets. Alvin Roth and Lloyd Shapley received the 2012 Nobel Prize for its development and practical application.

Given $n$ men $M = \{m_1, ..., m_n\}$ and $n$ women $W = \{w_1, ..., w_n\}$. Each man $m_i$ has a strict linear ordering of preferences over $W$; each woman $w_j$ over $M$.

Matching $\mu$: $M \to W \cup \{\varnothing\}$ — a mutually one-to-one mapping (each gets at most one partner).

Classical game theory analyzes existing rules: what is the equilibrium outcome? Mechanism design solves the reverse problem: which rules should be introduced so that rational behavior of players leads to the desired social outcome?

Analogy: classical game theory is physics (describes the world), mechanism design is engineering (designs the world). Leonid Hurwicz, Eric Maskin, and Roger Myerson won the 2007 Nobel Prize for foundational contributions.

Examples of mechanism design problems: how to sell government television frequencies for maximum revenue? How to organize trading on the electricity market to minimize costs? How to allocate healthcare resources "fairly" when patients have private information?

The key barrier is that agents have private information (type θᵢ), which the planner does not observe: willingness to pay, production function, risk attitude. Agents may lie about their type for personal gain.

Formulas

Auctions have existed for thousands of years: slaves in Babylon, fish in Japanese harbors, Treasury bonds, spectrum frequencies, internet advertising. Modern auction theory is precise mathematics about how participants place bids and how much revenue the seller earns.

The key question: with the same preferences among participants, do different auction formats yield the same or different revenue for the seller? The intuition “higher bids = more revenue” is not always correct — the auction format deeply affects strategies.

First-Price Sealed-Bid Auction (FPSB): Sealed bids; the highest bid wins, the winner pays their own bid. Strategy: no dominant strategy — one should "shade" the bid below their own valuation. The optimal shading depends on the number of participants and the distribution of valuations.

Second-Price Auction (Vickrey, 1961): Sealed bids; the highest bid wins, the winner pays the second-highest bid. Dominant strategy: bid your true value θᵢ! This is a DSIC mechanism. Why: when bidding above θᵢ — there’s a risk of winning and overpaying. When bidding below — there’s a risk of missi...

Mechanism design faces fundamental barriers. Even with the most clever rule design, there are things that cannot be implemented with strategically thinking agents. Impossibility theorems delineate what is fundamentally unattainable.

This is not just abstract mathematics: the Arrow and Gibbard–Satterthwaite theorems explain why an “ideal” voting system does not exist, and allow for conscious choice of which imperfections are permissible.

Context: n ≥ 2 voters, m ≥ 3 alternatives. A “rational” aggregation of individual preferences into a social choice is needed.

Four axioms: 1. Completeness and transitivity of the result. 2. Pareto Principle: if everyone prefers x over y → the social ordering prefers x over y. 3. IIA (Independence of Irrelevant Alternatives): social choice between x and y depends only on individual preferences x vs y, not on the position...

Classical game theory assumes fully rational players who know the equilibrium. Evolutionary game theory (EGT) offers an alternative foundation: instead of rationality—selection. Individuals with higher fitness (payoff) reproduce faster. Equilibrium emerges not from reasoning, but from evolutionar...

Maynard Smith and Price (1973) developed EGT to explain animal behavior. Later, the concepts were transferred to economics, sociology, computer science. The main question: which strategies “survive” in the population?

Definition: A strategy σ* is an ESS if, for a sufficiently small invasion of mutants with strategy σ ≠ σ*, the “resident” population σ* “displaces” the mutants:

ESS Conditions (sufficient): 1. u(σ*, σ*) > u(σ, σ*) for all σ ≠ σ* — strict Nash equilibrium, OR 2. u(σ*, σ*) = u(σ, σ*) AND u(σ*, σ) > u(σ, σ) — in case of a tie against residents, σ* is better against mutants

Theory states that in Nash equilibrium, no one benefits from deviating. But how do players end up at equilibrium? It is unlikely that everyone solves the system of equations in advance. The real process is adaptive learning: observing the past, correcting strategies, and gradually approaching equ...

Learning models disrupt the notion of instantly rational agents. Instead, there is an iterative process, which may or may not converge to equilibrium.

Rule: In each period t, player i: (1) observes the frequencies of past actions of opponents; (2) forms beliefs as empirical frequencies; (3) chooses the best response to these beliefs.

Formally: let $n_j^t(s)$ be the number of times $j$ played $s$ before $t$. Belief: $\pi_j^t(s) = n_j^t(s)/t$. Choice: $a_i^t = \arg\max_s u_i(s, \pi_{-i}^t)$.

All game theory concepts—Nash equilibrium, SPNE, ESS, mechanism design—were developed as abstract analytical tools. But their true value is revealed in applications: explaining real market behavior and shaping companies’ strategic decisions.

Cournot Model (competition by output): Firms simultaneously choose production volumes $q_1$, $q_2$. Equilibrium: $q^* = \frac{a-c}{3b}$ for two firms; price $P^* = \frac{a+2c}{3}$. For $n$ firms: $P \rightarrow c$ as $n \rightarrow \infty$ (convergence to a competitive market). Application: oil i...

Bertrand Model (competition by price): Firms choose price; buyers go to the cheaper one. For a homogeneous product, equilibrium: $P = c$ (competitive price!)—the “Bertrand Paradox.” Two firms are enough for a competitive market. Application: online airline ticket market, bank deposits, market for...

Stackelberg Competition: The leader firm first chooses $q_1$, the follower–observer chooses $q_2$ knowing $q_1$. SPNE: leader $q_1^* = \frac{a-c}{2b}$ (greater than Cournot!), follower $q_2^* = \frac{a-c}{4b}$. Leader advantage: the first move yields higher output and profit.