ABSTRACT: The Internet has revolutionized markets; perhaps the most impressive of these in terms of size, impact and novelty of mechanisms is Google’s Adwords market.  Google’s initial mechanism for this market did not effectively serve small advertisers, who form the fat tail of the budget distribution, thereby losing a significant fraction of potential revenue. Building on the theory of online matching algorithms, we gave an optimal algorithm for the Adwords market and a formal framework that has proved useful in thinking about budgeted auctions more generally. These ideas have been widely adopted by Google and other search engine companies. The rapidly growing cloud computing market, which is projected to eclipse even the Adwords market, provides another opportunity for novel algorithms and practical impact.  I will describe a first attempt in this direction: an equilibrium-based market model for pricing and allocating resources, and a polynomial time algorithm for computing them without relying on the proverbial “invisible hand of the market”. Note: This talk is meant for a general audience. BIO: Vijay Vazirani received his BS at MIT and his Ph.D. from the University of California at Berkeley.  He has made seminal contributions to the theory of algorithms, in particular to the classical maximum matching problem, approximation algorithms, and complexity theory. Over the last decade and a half, he has contributed widely to an algorithmic study of economics and game theory. Vazirani is author of a definitive book on Approximation Algorithms, published in 2001, and translated into Japanese, Polish, French and Chinese.  He was McKay Fellow at U. C. Berkeley in Spring 2002, and Distinguished SISL Visitor at Caltech during 2011-12. He is a Guggenheim Fellow and an ACM Fellow.

Hosted by Professor Rafail Ostrovsky

REFRESHMENTS at 3:45 pm, SPEAKER at 4:15 pm