Mathematics · Algorithms · Incentives
Essential Background These topics support Nash equilibrium, mechanism design, auctions, social choice, routing games, Price of Anarchy, multi-agent systems, and learning.
DM
Discrete Mathematics Sets · functions · relations · logic
Game-theoretic models use sets of players, actions, outcomes, relations, and mappings.
Technical significance
Comfort with discrete mathematical notation makes strategic models easier to read and manipulate.
Sets Functions Logic
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 logical conditions such as “for every player” and “there exists a deviation.” AGT connections: strategy profiles, utilities, feasible allocations, social choice functions.
More ↓
PR
Probability Random variables · distributions · expectation
Mixed strategies, Bayesian games, randomized mechanisms, and learning all depend on probability.
Technical significance
Expected utility is one of the most frequently used calculations in game theory.
Probability Expectation Distributions
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.
More ↓
CA
Basic Calculus Derivatives · maxima · minima
Continuous strategy spaces and optimization-based models often require basic calculus.
Technical significance
Best responses and welfare optima may be found by analyzing derivatives and convexity.
Derivatives Optimization Continuous Games
You should 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.
More ↓
LA
Linear Algebra Vectors · matrices · linear systems
Finite games are commonly represented by payoff matrices, while equilibrium computation uses vector and matrix notation.
Technical significance
Linear algebra provides a compact representation of strategies, payoffs, and optimization constraints.
Matrices Vectors Linear Systems
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, Markov and learning models.
More ↓
AL
Algorithms Design · correctness · efficiency
Algorithmic game theory studies not only strategic outcomes but also whether those outcomes can be computed efficiently.
Technical significance
Algorithm design is essential for matching, auctions, routing, equilibrium computation, and market mechanisms.
Algorithms Efficiency Correctness
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.
More ↓
BO
Big-O & Complexity Asymptotic analysis · tractability
Computational difficulty is one of the features that distinguishes algorithmic game theory from classical game theory.
Technical significance
You should be able to distinguish efficient algorithms from combinatorial explosion.
Big-O P vs NP Complexity
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.
More ↓
GR
Graphs & Networks Vertices · edges · paths · flows
Routing games, network formation, matching, and multi-agent interaction rely heavily on graphs.
Technical significance
Many strategic environments are naturally represented as networks.
Graphs Paths Networks
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.
More ↓
OP
Optimization Basics Objective · constraints · feasible region
Mechanisms and equilibria are often compared with a centralized optimum.
Technical significance
Optimization provides the benchmark for welfare, cost, revenue, and efficient allocation.
Optimization Constraints Welfare
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.
More ↓
PF
Programming Fundamentals Variables · loops · functions · data structures
Simulation and computational experiments require practical programming ability.
Technical significance
Small implementations make equilibrium, bidding, learning, and routing dynamics easier to test.
Programming Simulation Implementation
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.
More ↓
PY
Python Basics Python · NumPy-style reasoning · scripts
Python is convenient for matrix games, experiments, Nashpy, optimization, and learning simulations.
Technical significance
A small amount of Python is enough for most computational demonstrations.
Python Nashpy Experiments
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.
More ↓
EU
Expected Utility Utilities · lotteries · expectation
Strategic decisions under randomization are evaluated through expected utility.
Technical significance
This concept underlies mixed strategies, auctions with uncertainty, and Bayesian games.
Utility Expected Value Mixed Strategies
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.
More ↓
PT
Proof Techniques Direct proof · contradiction · counterexample
Many game-theoretic results are claims about every possible deviation, mechanism, or equilibrium.
Technical significance
Basic proof skills are necessary to justify equilibrium and incentive properties.
Proofs Counterexamples Reasoning
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.
More ↓
EC
Basic Economics Vocabulary Utility · welfare · incentives · efficiency
Algorithmic game theory borrows a compact set of economic concepts used throughout auctions and mechanism design.
Technical significance
Understanding the vocabulary prevents confusion between individual utility and global objectives.
Utility Welfare Efficiency
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.
More ↓
SR
Strategic Reasoning Best response · dominance · deviation
Students should be comfortable asking what each player would do given the actions of others.
Technical significance
Best-response reasoning is the core local test behind Nash equilibrium.
Best Response Dominance Deviation
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.
More ↓
CB
Combinatorics Counting · permutations · combinations
Finite games and allocation problems can have very large strategy and outcome spaces.
Technical significance
Counting helps explain why brute-force search becomes computationally expensive.
Counting Permutations Combinations
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.
More ↓
ST
Basic Statistics Samples · averages · variance
Learning and repeated-game experiments produce noisy empirical data.
Technical significance
Basic statistical reasoning helps interpret simulation results without overreading random variation.
Mean Variance Sampling
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.
More ↓
No prerequisite matches your search or filter.