Friday, Sep 24, 2010
3:30 pm, MC 5158

Tutte Seminar Series
Combinatorics & Optimization
Fall 2010


Vijay Vazirani
Georgia Institute of Technology

The Invisible Hand of the Market: Algorithmic Ratification and the Digital Economy

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 latter question can clearly benefit from the powerful tools of modern complexity theory and algorithms, and was taken up in the earnest within theoretical computer science a decade ago. In this talk, we will provide a summary of key developments. We will also describe a fascinating new direction, for the theory of algorithms, that has emerged from this work.
A compelling new issue is extending this deep understanding of markets to the digital economy -- because of some fundamental reasons, the methodology outlined above does not carry over to the digital realm. We will outline recent progress on this issue.

      Based in part on: http://www.cc.gatech.edu/~vazirani/NBalg.pdf and http://arxiv.org/abs/1007.4586