Keynote Speakers
- Vijay Krishna, PennState, Pennsylvania, USA.
Title: Communication and Cooperation (joint with Yu Awaya)
Abstract:
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.
Bio:
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.
- Vijay Vazirani, University of California, Irvine, USA.
Title: Google's AdWords Market: How Theory Influenced Practice
Abstract:
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.
Bio:
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.
- Ariel Procaccia, Carnegie Mellon University, Pittsburg, USA.
- Tim Roughgarden, Stanford University, Stanford, USA.
Title: Extreme Democracy
Abstract:
Technological advances have changed every aspect of our lives in recent decades, yet, for the most part, the same systems of democratic decision making have been in place for centuries. I will argue that computer scientists can help rethink the practice of democracy, as well as its potential applications. I will focus on three emerging paradigms that go far beyond your run-of-the-mill election: (i) liquid democracy, an approach that allows voters to transitively delegate their votes; (ii) participatory budgeting, whereby residents collectively decide how to spend their local government's budget; and (iii) virtual democracy, which employs instant elections among machine learning models of real voters to address the grand AI challenge of ethical decision making.
Bio:
Ariel Procaccia is an Associate Professor in the Computer Science Department at Carnegie Mellon University. He usually works on problems at the interface of computer science and economics. His distinctions include the IJCAI Computers and Thought Award (2015), the Sloan Research Fellowship (2015), the NSF Faculty Early Career Development Award (2014), and the IFAAMAS Victor Lesser Distinguished Dissertation Award (2009); as well as half a dozen paper awards, including Best Paper (2016) and Best Student Paper (2014) at the ACM Conference on Economics and Computation (EC). He is co-editor of the Handbook of Computational Social Choice (Cambridge University Press, 2016).
Title: Data-Driven Optimal Auction Theory
Abstract:
The traditional economic approach to revenue-maximizing auction design posits a known prior distribution over what bidders are willing to pay, and then solves for the auction that maximizes the seller's expected revenue with respect to this distribution.But where does this distribution come from? One obvious answer is from data, in the form of previous bids by comparable bidders in auctions for comparable items. We survey recent work that develops theory to help reason about questions such as: (i) how much data is necessary and sufficient to identify a near-optimal auction? (ii) what is the optimal way to use data? (iii) are there fundamental trade-offs between auction complexity and auction optimality?
(Includes joint work with Richard Cole, Zhiyi Huang, Yishay Mansour, Jamie Morgenstern, and Josh Wang)