Prerequisites for Algorithmic Game Theory
Algorithmic game theory combines strategic reasoning with algorithms, probability, optimization, complexity, networks, and computational experiments.
The strongest preparation is a combination of discrete mathematics, probability, algorithms, graph theory, basic optimization, and practical programming.
Essential Background
These topics support Nash equilibrium, mechanism design, auctions, social choice, routing games, Price of Anarchy, multi-agent systems, and learning.
Discrete Mathematics
Game-theoretic models use sets of players, actions, outcomes, relations, and mappings.
Be comfortable with sets, Cartesian products, functions, relations, quantifiers, implication, and basic proof notation.
- Read strategy spaces such as S₁ × S₂ × ··· × Sₙ.
- Interpret utility functions uᵢ(s).
- Work with finite sets and indexed families.
- Understand statements such as “for every player” and “there exists a deviation.”
AGT connections: Strategy profiles, utilities, feasible allocations, social choice functions.
Probability
Mixed strategies, Bayesian games, randomized mechanisms, and learning all depend on probability.
Know basic probability rules, conditional probability, independence, random variables, and expected value.
- Compute E[X] for finite distributions.
- Interpret a mixed strategy as a probability distribution over actions.
- Use conditional probabilities in Bayesian reasoning.
- Distinguish independent from correlated random choices.
AGT connections: Mixed Nash equilibrium, Bayesian games, randomized algorithms, expected welfare.
Basic Calculus
Continuous strategy spaces and optimization-based models often require basic calculus.
Be able to differentiate elementary functions and locate stationary points.
- Interpret first-order optimality conditions.
- Distinguish local and global optima.
- Understand monotonicity and basic convexity intuition.
AGT connections: Continuous games, congestion functions, utility maximization, auction optimization.
Linear Algebra
Finite games are commonly represented by payoff matrices, while equilibrium computation uses vector and matrix notation.
Be comfortable with matrix indexing, vector operations, dot products, and systems of linear equations.
- Read bimatrix games.
- Represent mixed strategies as probability vectors.
- Compute expected payoff with matrix-vector products.
AGT connections: Zero-sum games, support enumeration, linear programming, learning models.
Algorithms
Algorithmic game theory studies not only strategic outcomes but also whether those outcomes can be computed efficiently.
Be familiar with greedy algorithms, dynamic programming, graph traversal, sorting, and basic algorithm design.
- Trace an algorithm step by step.
- State what input and output an algorithm computes.
- Reason about correctness and runtime.
AGT connections: Gale–Shapley, auctions, shortest paths, equilibrium algorithms, allocation mechanisms.
Big-O & Complexity
Computational difficulty is one of the features that distinguishes algorithmic game theory from classical game theory.
Know common growth rates such as O(1), O(log n), O(n), O(n log n), O(n²), and exponential time.
- Understand polynomial-time computation.
- Know the basic meaning of P and NP.
- Recognize reductions as a tool for showing hardness.
AGT connections: Equilibrium complexity, combinatorial auctions, optimization, PPAD intuition.
Graphs & Networks
Routing games, network formation, matching, and multi-agent interaction rely heavily on graphs.
Know adjacency lists/matrices, paths, cycles, connectedness, shortest paths, and basic flow intuition.
- Understand weighted edges.
- Read directed and undirected graphs.
- Recognize congestion as load placed on shared edges.
AGT connections: Selfish routing, congestion games, matching, network design, social networks.
Optimization Basics
Mechanisms and equilibria are often compared with a centralized optimum.
Be able to identify decision variables, an objective function, and constraints.
- Distinguish maximization from minimization.
- Understand feasible versus infeasible solutions.
- Read a simple linear program.
AGT connections: Social welfare, allocation, zero-sum games, routing optimum, auction revenue.
Programming Fundamentals
Simulation and computational experiments require practical programming ability.
Be comfortable with variables, loops, functions, arrays/lists, dictionaries/maps, and simple classes.
- Implement payoff calculations.
- Enumerate strategy profiles.
- Simulate repeated interaction.
- Collect and compare numerical results.
AGT connections: Game simulators, auction experiments, learning dynamics, equilibrium search.
Python Basics
Python is convenient for matrix games, experiments, Nashpy, optimization, and learning simulations.
Know lists, tuples, dictionaries, functions, loops, comprehensions, and basic module use.
- Represent payoff matrices with nested lists or arrays.
- Generate random strategies.
- Plot or summarize repeated-game outcomes where needed.
AGT connections: Nashpy, simulations, bandits, reinforcement learning, market experiments.
Expected Utility
Strategic decisions under randomization are evaluated through expected utility.
For outcomes x with probabilities p(x), compute expected utility as Σ p(x)u(x).
- Do not confuse expected payoff with the most likely payoff.
- Understand indifference conditions used to solve mixed equilibria.
AGT connections: Mixed Nash equilibrium, Bayesian mechanisms, lotteries, randomized strategies.
Proof Techniques
Many game-theoretic results are claims about every possible deviation, mechanism, or equilibrium.
Be comfortable with direct proofs, contradiction, proof by cases, and counterexamples.
- Prove that no unilateral deviation improves payoff.
- Show a mechanism is or is not truthful.
- Construct a counterexample to a claimed property.
AGT connections: Equilibrium proofs, truthfulness, fairness, impossibility results.
Basic Economics Vocabulary
Algorithmic game theory borrows a compact set of economic concepts used throughout auctions and mechanism design.
Know the meanings of valuation, cost, utility, social welfare, revenue, efficiency, and incentive.
- Utility describes an individual agent's objective.
- Social welfare aggregates outcomes across agents.
- Revenue is generally different from welfare.
AGT connections: Auctions, market design, mechanism objectives, Price of Anarchy.
Strategic Reasoning
Students should be comfortable asking what each player would do given the actions of others.
Given a payoff table, identify each player's best response to the other players' choices.
- Recognize strictly and weakly dominated strategies.
- Check whether a profile is stable under unilateral deviations.
- Separate individual incentives from collective outcomes.
AGT connections: Nash equilibrium, dominant strategies, Prisoner's Dilemma, auctions.
Combinatorics
Finite games and allocation problems can have very large strategy and outcome spaces.
Know factorials, combinations, permutations, and basic product-rule counting.
- Count pure strategy profiles.
- Estimate the number of allocations or matchings.
- Recognize exponential growth in combinatorial spaces.
AGT connections: Combinatorial auctions, voting, matching, equilibrium enumeration.
Basic Statistics
Learning and repeated-game experiments produce noisy empirical data.
Know sample means, variance intuition, distributions, and why finite samples fluctuate.
- Average repeated-game rewards.
- Compare empirical frequencies with theoretical probabilities.
- Recognize randomness in bandit and reinforcement-learning experiments.
AGT connections: Learning, adaptation, simulations, online platforms.