Algorithmic game theory

Algorithmic game theory is the intersection of game theory and computational complexity theory, studying how the computational difficulty of finding equilibria, optimal strategies, and mechanism outcomes reshapes strategic behavior. The field's founding question is simple: if computing a Nash Equilibrium is PPAD-complete — meaning no efficient general algorithm is known — then in what sense can real agents be said to play Nash equilibria? The answer is that they cannot, not literally. They use heuristics, learning rules, and social imitation that may approximate equilibrium behavior under favorable conditions but that are fundamentally different from equilibrium analysis. Algorithmic game theory inverts the classical perspective: instead of assuming rationality and deriving behavior, it assumes computational constraints and asks what behavior emerges. This has produced surprising results, including mechanisms in which social welfare is maximized precisely because the equilibrium is computationally hard to find, forcing agents into simple heuristics that align incentives. The field belongs to the same research program as bounded rationality and mechanism design, but with a sharper focus on complexity-theoretic impossibility results.