Prof. Vijay Vazirani 

“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. We will provide an in-depth overview of the fascinating theory that has emerged around this question over the last decade.

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 as well.

----------------------------------------------------------------------------------

Speaker's bio:

Vijay Vazirani got his Bachelor's degree in Computer Science from MIT in 1979 and his Ph.D. from the University of California at Berkeley in 1983. His research has spanned a broad range of themes within the design of efficient algorithms - combinatorial optimization, approximation algorithms, randomized algorithms, parallel algorithms, and most recently algorithmic issues in game theory and mathematical economics. He has also worked in complexity theory, cryptography and information theory. In 2001 he published what is widely regarded as the definitive book on Approximation Algorithms. This book has been translated into Japanese, Polish, French and Chinese. In 2007, he co-edited a comprehensive volume on Algorithmic Game Theory. During 2011-12 he is visiting Stanford University and Caltech under a Guggenheim Fellowship.