Tutte seminar - Vijay Vazirani

Friday, September 24, 2010 3:30 pm - 4:30 pm EDT (GMT -04:00)

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

Speaker: Vijay Vazirani
Affiliation: Georgia Institue of Technology
Room: Mathematics & Computer Building (MC) 5158


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 sciencea 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: The Notion of a Rational Convex Program, and an Algorithm for the Arrow-Debreu Nash Bargaining Game (PDF) and Equilibrium Pricing of Semantically Substitutable Digital Goods.