Keynote Speakers

Title: Communication and Cooperation (joint with Yu Awaya)


We study the role of communication in sustaining cooperation in repeated interactions. Specifically, we identify conditions under which, without communication the prospects for cooperation are limited because of poor monitoring---all equilibrium are bounded away from the efficient frontier. We show, however, that with cheap-talk communication, nearly efficient cooperation can be sustained as an equilibrium. In this sense communication is necessary for cooperation.


Vijay Krishna is a Professor of Economics at Penn State University. He has worked in a variety of areas of economic and game theory: auctions and mechanism design, bargaining, communication, learning, repeated games and voting.He is the author of Auction Theory, a standard reference on the subject.

Title: Google's AdWords Market: How Theory Influenced Practice


I will talk about an optimal online algorithm for Internet Ad markets, such as Google's AdWords market. Although this result was obtained over a decade ago when the algorithmic and economic/game-theoretic issues of this marketplace were just being understood, its impact is becoming clear only in recent years. Our result addresses a central algorithmic issue underlying this marketplace: how to match query keywords to advertisers so as to maximize Google's revenue.

I will give an overview of the novel LP-based techniques that led to this result and the simple heuristic, of bid scaling, that is suggested by our algorithm.

I will also present a formal framework for thinking about budgeted auctions more generally. These ideas have been widely adopted by Google and other search engine companies.

Purely theoretical work, from the 1990s, on the online bipartite matching problem greatly benefitted our work. The latter problem, while mathematically clean and elegant, appears to have no applications. On the other hand, the multi-billion dollar online ad industry has become the key source of revenues for several Internet companies. For algorithms designers, this a very happy story of practical impact from rich theory.


Dr. Vazirani is distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine. He is a leading researcher in algorithm design, and more generally, in the theory of computing. Throughout his research career, he has demonstrated a consistent ability to obtain novel algorithmic ideas, frequently of substantial mathematical depth, which while solving the problem at hand, also lay the groundwork for future contributions by others. Dr. Vazirani's research career spans over twenty five years. During the first ten years, he made seminal contributions to the classical maximum matching problem which has historically played a central role in the development of the theory of algorithms. He discovered, jointly with other researchers, the fastest known sequential and parallel algorithms for his problem. Over the next ten years, Vazirani focused on approximation algorithms for NP-hard problems and had much influence on this area through work on several of its fundamental problems. In 2001, he published a book on this topic. He is currently working in algorithmic game theory, in particular on algorithms for computing market equilibria.