7 min read
On this page

Game Theory Foundations

Game Representations

Normal (Strategic) Form

A simultaneous-move game defined by the tuple (N, S, u) where:

  • N = {1, ..., n}: set of players
  • S = S_1 x ... x S_n: strategy space (each S_i is player i's strategy set)
  • u = (u_1, ..., u_n): utility functions, u_i: S -> R

For two-player games, represented as a bimatrix (A, B) where A_{ij} is player 1's payoff and B_{ij} is player 2's payoff when player 1 plays row i and player 2 plays column j.

Extensive Form

Sequential games represented as game trees:

  • Nodes: Decision points for players or chance
  • Information sets: Group nodes where a player cannot distinguish between them (models imperfect information)
  • Actions: Available moves at each information set
  • Terminal nodes: Outcomes with associated payoff vectors

Perfect information: Every information set is a singleton (chess, Go). Imperfect information: Some information sets contain multiple nodes (poker).

Subgame: A subtree starting at a node that is a singleton information set, containing all successors and complete information sets. Subgame perfect equilibrium (SPE): NE in every subgame; found by backward induction in perfect information games.

Nash Equilibrium

Definition

A strategy profile s* = (s_1, ..., s_n) is a Nash equilibrium if no player can unilaterally improve their payoff:

u_i(s_i, s{-i}) >= u_i(s_i, s*{-i}) for all s_i in S_i, for all i

No player has an incentive to deviate, given others' strategies are fixed.

Existence (Nash's Theorem)

Every finite game (finite players, finite strategy sets) has at least one Nash equilibrium, possibly in mixed strategies. The proof uses Brouwer's (or Kakutani's) fixed point theorem on the best-response correspondence.

Pure vs. Mixed Strategies

Pure strategy: A deterministic choice from S_i.

Mixed strategy: A probability distribution sigma_i over S_i. Player i's expected utility under mixed strategy profile sigma:

u_i(sigma) = sum_{s in S} (product_j sigma_j(s_j)) * u_i(s)

The support of a mixed strategy is the set of pure strategies played with positive probability. In a mixed NE, every pure strategy in the support must yield the same expected payoff (indifference principle).

Dominant Strategies

  • Strictly dominant: s_i is strictly dominant if u_i(s_i, s_{-i}) > u_i(s'i, s{-i}) for all s'i != s_i and all s{-i}
  • Weakly dominant: >= for all, > for at least one
  • Iterated elimination of strictly dominated strategies (IESDS): Iteratively remove strategies that are strictly dominated; order of elimination does not matter; the result is unique. Dominance solvable games reduce to a single strategy profile.

Prisoner's Dilemma: Each player has a strictly dominant strategy (Defect), yet mutual cooperation Pareto-dominates the NE. Illustrates the tension between individual rationality and collective welfare.

Computing Nash Equilibria

Two-Player Zero-Sum Games

Equivalent to linear programming (minimax theorem, von Neumann 1928). Player 1 maximizes min_j (sum_i x_i A_{ij}); dual is player 2's problem. Solvable in polynomial time.

Two-Player General Games

Lemke-Howson Algorithm: Pivoting algorithm on the labeled polytope formed by the best-response conditions. Follows a path of complementary solutions to find a NE.

  • Input: Bimatrix game (A, B) with m x n strategies
  • Operates on polytopes P = {x: x >= 0, B^T x <= 1} and Q = {y: y >= 0, A y <= 1}
  • Follows complementary pivot steps analogous to simplex method
  • Guaranteed to terminate at a NE (by Lemke's complementary pivoting)
  • Exponential worst case (Savani-von Stengel, 2006)

Support Enumeration: For each pair of support sizes (k, l), solve the resulting linear system from the indifference conditions. Exponential in the support size.

Homotopy methods: Govindan-Wilson; polynomial systems with path-following.

PPAD-Completeness

PPAD (Polynomial Parity Argument on Directed graphs): Complexity class for problems where existence is guaranteed by a parity argument on directed graphs (every directed graph with an unbalanced node has another unbalanced node).

Theorem (Daskalakis-Goldberg-Papadimitriou, 2009; Chen-Deng, 2006): Computing a Nash equilibrium of a two-player game is PPAD-complete. This holds even for:

  • Bimatrix games with 0/1 payoffs
  • Games with 3 or more players (reduced to 2-player case)

Implications: No polynomial-time algorithm exists unless PPAD = FP. Finding NE is computationally hard even though existence is guaranteed. This is unlike NP-completeness: the solution always exists, but finding it is hard.

Approximate NE: An epsilon-approximate NE allows each player's payoff to be within epsilon of best response. The complexity of finding epsilon-NE for small epsilon remains PPAD-hard (Rubinstein, 2016 for inverse polynomial epsilon).

Correlated Equilibrium

A probability distribution p over strategy profiles S such that for each player i and each strategy s_i in the support:

sum_{s_{-i}} p(s_i, s_{-i}) * u_i(s_i, s_{-i}) >= sum_{s_{-i}} p(s_i, s_{-i}) * u_i(s'i, s{-i}) for all s'_i

A mediator draws a strategy profile from p and privately recommends each player their component. No player benefits from deviating from the recommendation.

Key properties:

  • Every NE is a CE (product distributions are a special case)
  • The set of CE is a convex polytope (defined by linear constraints)
  • Can be computed in polynomial time via linear programming
  • Can achieve higher social welfare than any NE (e.g., traffic light in Chicken game)
  • Regret minimization: No-regret learning dynamics converge to the set of coarse correlated equilibria; no-swap-regret converges to CE

Zero-Sum Games and Minimax

In zero-sum games: u_1(s) + u_2(s) = 0 for all strategy profiles s.

Minimax Theorem (von Neumann): In finite two-player zero-sum games:

max_{sigma_1} min_{sigma_2} u_1(sigma_1, sigma_2) = min_{sigma_2} max_{sigma_1} u_1(sigma_1, sigma_2) = v

The value v is the game value. Minimax strategies are NE strategies. The NE is interchangeable (any combination of NE strategies of each player forms a NE) and has a unique payoff.

Practical significance: LP solvable in polynomial time. Foundation for game-solving in AI (chess, Go, poker). Regret-minimization algorithms (counterfactual regret minimization) converge to minimax strategies in zero-sum games.

Bayesian Games (Games of Incomplete Information)

Players have private information (types) drawn from known prior distributions.

Formal Definition

  • Type space: Theta_i for each player; types drawn from common prior p(theta)
  • Strategy: Maps types to actions, s_i: Theta_i -> A_i
  • Bayesian Nash equilibrium (BNE): Strategy profile where each player maximizes expected utility given their type and beliefs about others' types:

E_{theta_{-i} | theta_i} [u_i(s_i(theta_i), s_{-i}(theta_{-i}), theta_i)] >= E_{theta_{-i} | theta_i} [u_i(a_i, s_{-i}(theta_{-i}), theta_i)]

for all types theta_i and alternative actions a_i.

Harsanyi transformation: Converts incomplete information game to an imperfect information game by introducing Nature as a player who selects types. This is foundational for auction theory and mechanism design.

Repeated Games

Finite Repetition

Finitely repeated games with a unique stage-game NE have a unique SPE: play the stage NE in every period (backward induction). With multiple stage NE, cooperation can be sustained via punishment strategies.

Infinite Repetition

With discount factor delta in (0,1), players maximize sum_{t=0}^{infinity} delta^t u_i(a^t).

Folk Theorem: Any feasible and individually rational payoff vector can be sustained as a Nash equilibrium of the infinitely repeated game for sufficiently high delta. The "individually rational" payoff for player i is the minimax value: v_i = min_{s_{-i}} max_{s_i} u_i(s_i, s_{-i}).

Subgame perfect folk theorem (Fudenberg-Maskin): The same result holds for SPE when the dimension of the feasible payoff set equals n (the number of players). Requires more sophisticated punishment strategies (e.g., mutual punishment phases with gradual return to cooperation).

Trigger strategies: Grim trigger (defect forever after any defection) sustains cooperation when delta >= (temptation - cooperation)/(temptation - punishment). Tit-for-tat and other forgiving strategies can sustain cooperation more robustly.

Applications

  • Collusion in oligopoly (Bertrand/Cournot repeated games)
  • Cooperation in the iterated Prisoner's Dilemma
  • Reputation effects in finitely repeated games with incomplete information (Kreps-Milgrom-Roberts-Wilson)

Key Connections to Computer Science

Game theory intersects with algorithms and complexity theory in fundamental ways. The computational hardness of equilibrium concepts (PPAD-completeness of Nash) motivates the study of alternative solution concepts (CE, approximate NE). Algorithmic mechanism design asks how to design games with desirable equilibria that are also computationally tractable. Online learning and no-regret algorithms provide decentralized dynamics converging to equilibrium. These connections define the field of algorithmic game theory.