Complexity of markets
Computation in economic mechanisms
2021-02-19 — 2021-05-12
Wherein the computational limits of markets are examined, and the question of how market mechanisms are tasked with NP‑hard optimization problems like central planning is considered, with reductions to decision problems presented.
What is the computational power of a market? What is the computational complexity of the work that markets do? Socialist calculation debate. Computational complexity and command-and-control economics.
Classic: Cosma Shalizi: In Soviet Union, Optimization Problem Solves You. See also his notebook on Planned Economies.
1 Algorithmic results
The same fixed-point machinery that makes Nash equilibria PPAD-hard (C. Daskalakis, Goldberg, and Papadimitriou 2009) applies to general-equilibrium economics. Finding an Arrow–Debreu competitive market equilibrium has its own algorithmic literature (Ye 2008), with tractable special cases (Leontief, linear, Cobb–Douglas utilities) and intractable ones. Axtell (2005) is the place to look for the worry that real markets cannot plausibly be computing the equilibria classical theory hands them — the market-as-distributed-computer view has hard limits.