Can Complexity Theory Ratify the Invisible Hand of the Market?

*It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard for their own interest. Each participant in a competitive economy is led by an invisible hand to promote an end which was no part of his intention.*
Adam Smith, 1776

With his treatise, *The Wealth of Nations*, 1776, Adam Smith initiated the field of economics, and his famous quote provided this field with its central guiding principle. The pioneering work of Walras (1874) gave a mathematical formulation for this statement, using his notion of market equilibrium, and opened up the possibility of a formal ratification.

Mathematical ratification came with the celebrated Arrow-Debreu Theorem (1954), which established existence of equilibrium in a very general model of the economy; however, an efficient mechanism for finding an equilibrium has remained elusive.

The question of algorithmic ratification was taken up in the earnest within theoretical computer science a decade ago, and attention soon gravitated on markets under piecewise-linear, concave utility functions. As it turned out, the recent resolution of this open problem did not yield the hoped-for mechanism; however, it did mark the end of the road for the current approach. It is now time to step back and plan a fresh attack, using the powerful tools of modern complexity theory and algorithms.

After providing a summary of key developments through the ages and a gist of the recent results, we will discuss some ways of moving forward.

(Based in part on recent work with Mihalis Yannakakis.)