Complexity of markets
Computation in economic mechanisms
2021-02-19 — 2026-09-06
In Which the Socialist Calculation Debate Is Invoked, PPAD-hardness Is Assigned to Nash Equilibria, Scarf’s Three-Good Cycles Are Documented, and \(N(l-1)\) Messages Are Traded to Satisfy the Competitive Mechanism.
What is the “computational power of a market”? We can operationalize this by examining the computational complexity of the work that markets do. What is the computational complexity of the work that markets do? This was a live question in the so-called socialist calculation debate.. Cosma Shalizi is fun on this: 1. See also his notebook on Planned Economies.
1 Algorithmic results
Nash equilibrium and Walrasian equilibrium are both proved to exist by fixed point — Arrow and Debreu lean on Debreu’s social equilibrium theorem, which generalizes Nash’s own use of Kakutani — and PPAD is the class built to capture that situation: a search problem whose answer is guaranteed to exist by an argument that declines to say where it is. So Nash being PPAD-hard (C. Daskalakis, Goldberg, and Papadimitriou 2009) and market equilibrium being PPAD-hard are one fact about one difficulty. It is not hardness in the NP sense, either: the trouble is not that the answer might be missing, but that it is certainly there but may be nonetheless out of reach.
That said, a market-clearing price is not a Nash equilibrium, and these problems are not structurally identical, although my friendly local LLM tells me that there is a construction by Codenotti et al. (2008) that builds Leontief exchange economies whose equilibria stand in one-to-one correspondence with the Nash equilibria of a bimatrix game.
It seems a lot of the complexity is conditioned by the form of the utility (Ye 2008). Linear utilities are solvable in polynomial time (Jain 2007), and Cobb–Douglas likewise. Leontief … depends. It is tractable in simple special cases like Fisher markets, but PPAD-hard in exchange economies (Codenotti et al. 2008)1. Generally for any interesting class of utility functions, the complexity is high, e.g. even when utilities are additively separable and piecewise-linear computing an Arrow–Debreu equilibrium is PPAD-complete (Chen et al. 2009).
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.
2 Convergence
Even if an equilibrium exists, does tâtonnement converge upon it? Scarf (1960) exhibited three-good exchange economies in which tâtonnement cycles forever instead of settling. Those economies have to violate gross substitutes in order to manage it: Arrow, Block, and Hurwicz (1959) had already proved tâtonnement globally stable under that condition, so Scarf is showing what the condition was holding back. Saari and Simon (1978) asked what it would take to rule that out, and found that any price-adjustment rule guaranteed to converge must consume essentially the whole Jacobian of excess demand, i.e. not just some summary statistic, but some kind of panoptic oversight of the entire derivative structure. Naïve guarantees on the invisible hand need the information that the price system was supposed to save us from gathering.
3 Messaging complexity
The complementary literature runs the other way and is friendlier to markets. The quantity being measured here is the message space: how many real numbers have to pass between agents before the process can name an efficient allocation. Each agent knows only their own preferences and endowment, nobody sees the whole economy, and the question is how much has to be said out loud. Mount and Reiter (1974) set that measure up. For an exchange economy with \(n\) agents and \(l\) goods, the competitive mechanism needs a message space of dimension \(n(l-1)\) — a normalized price vector plus everyone’s net trades, and nothing further. That is the minimum over all informationally decentralized mechanisms realizing efficient allocations, and Jordan (1982) showed the competitive mechanism is essentially the only one attaining it.
\(n(l-1)\) is linear in the number of agents: double the population and we double the talking. That, rather than any claim about optimality of outcomes, is what markets have going for them computationally. The catch is the domain, which wants convexity, divisibility, and the regularity conditions that travel with them.
4 Substitutes and complements
Gross substitutes: raising the price of one good never makes a buyer want less of some other good. The same condition sits behind three results already mentioned. Arrow, Block, and Hurwicz (1959) introduced it and proved tâtonnement globally stable under it, which is the result Scarf’s economies had to escape in order to cycle. Leontief utilities, \(u=\min_i(x_i/w_i)\), are perfect complements and violate it about as thoroughly as anything can, which is why the Leontief exchange economies above are where the PPAD-hardness sits. Linear utilities satisfy it, and are the case that solves in polynomial time. So convergence and computational complexity are tracking one property from two directions. For divisible goods the counterpart condition is convexity, which is what the message-space result assumes; gross substitutes is its stand-in once goods come in whole units.
Kelso and Crawford (1982) carried the condition into matching, which is why it is often attributed to them, and proved two things under it, in a labour market where firms have preferences over whole sets of workers. A competitive equilibrium in ordinary linear prices exists — one salary per worker, the same figure quoted to everyone. And an ascending salary-adjustment process, firms bidding and salaries rising on contested workers, reaches a core allocation in finite time. So on this side of the condition prices exist, and a mechanical procedure anyone could actually run will find them.
Complements break both halves. When two workers are worth more together than apart — the crane is useless without an operator — a linear anonymous price vector supporting an efficient allocation may not exist at all. Bikhchandani and Ostroy (2002) characterize what has to replace it: prices on bundles rather than goods, so \(2^l\) numbers instead of \(l\), and personalized, so one such schedule per buyer rather than one public list. Both properties that kept the message space small in the previous section are gone. The price of a thing stops being a well-defined object, no list can be posted, and the \(n(l-1)\) bound gives way to something exponential and private.
5 Designing the mechanism instead
If the market cannot be relied on to do the computing, the alternative is to compute the market. Conitzer and Sandholm (2002) found automated mechanism design NP-hard, and with an awkward shape: searching over rules means evaluating candidates, and evaluating a candidate means solving the game it induces.
I work through the bargaining-side version of all this in Hyperscaling Coase.
6 References
Footnotes
A Fisher market has buyers with fixed budgets of money; an exchange economy gives them goods instead↩︎