Inbal Talgam Cohen - CS-Lecture
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
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.
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.