Robust and Simple Market Design
- Inbal Talgam Cohen - CS-Lecture
- Monday, 23.1.2017, 10:30
- Room 601 Taub Bld.
Algorithms and the Internet are revolutionizing "markets" - the mechanisms through which resources are allocated among players under optimization criteria. While resource allocation is a long-standing theme in the study of classic algorithms like matching and routing, the need to interact with self-interested players, and the uncertain inputs they provide, break traditional algorithms and raise fundamental new challenges. Applications include the allocation of cloud computing resources, real-time auctions for online advertising, wireless spectrum auctions, and matching platforms for ridesharing. In this talk, I will present some of my work on tackling the challenges of computational market design, by considering a problem crucial for the modern digital economy: the design of mechanisms for the maximization of revenue. Most existing designs hinge on "getting the price right" - offering resources at prices low enough to encourage a sale, but high enough to garner non-trivial revenue. I will show a new solution based on a "robust and simple" approach, which contrary to existing designs requires no a-priori information about buyers' willingness to pay. Our method performs provably well even in complex markets with multiple resources for sale, which have posed a major open problem for three decades. I will conclude my talk with a surprising connection between economic equilibria in markets and computational complexity: the latter gives an explanation as to the puzzling rare existence of the former. Short Bio: ========== Inbal Talgam-Cohen is a Marie Curie postdoctoral researcher at HUJI and a visiting postdoctoral researcher at TAU. She holds a PhD from Stanford (2015) supervised by Tim Roughgarden, an MSc from Weizmann and a BSc from TAU in computer science, as well as a law LLB. Her research is in algorithmic game theory, including computational and data aspects of market design and applications to Internet economics. Her awards include Best Doctoral Dissertation Award of ACM SIGecom, the Stanford Interdisciplinary Graduate Fellowship, and the Best Student Paper Award at EC'15.