Can the Theory of Algorithms Ratify the 'Invisible Hand of the Market'?

Опубликовано 17 августа 2016, 21:29

ΓÇ£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.)