CS Talk
Matt Weinberg, Princeton University
Host: Yang Cai
Title: (a biased selection of) Recent Developments in Combinatorial Auctions
Abstract:
In a combinatorial auction there are m items, and each of n players has a valuation functionv_i which maps sets of items to non-negative reals. A designer wishes to partition the items into S_1,…,S_n to maximize the welfare (sum_iv_i(S_i) ), perhaps assuming that allv_i lie in some class V (such as submodular, subadditive, etc.).
Within Algorithmic Game Theory, this problem serves as a lens through which to examine the interplay between computation and incentives. For example: is it the case that whenever a poly-time/poly-communication algorithm for honest players can achieve an approximation guarantee of c when all valuations lie in V, a poly-time/poly-communication truthful mechanism for strategic players can achieve an approximation guarantee of c when all valuations lie in V as well?
In this talk, I’ll give a brief history, then survey three recent results on this topic which:
- provide the first separation between achievable guarantees of poly-communication algorithms and poly-communication truthful mechanisms for any V (joint works with Mark Braverman and Jieming Mao, and with Sepehr Assadi, Hrishikesh Khandeparkar, and Raghuvansh Saxena).
- resolve the communication complexity of combinatorial auctions for two subadditive players (joint work with Tomer Ezra, Michal Feldman, Eric Neyman, and Inbal Talgam-Cohen).
- revisit existing separations between poly-time algorithms and poly-time truthful mechanisms via a solution concept we call “Implementation in Advised Strategies” (joint work with Linda Cai and Clayton Thomas).
Bio:
Matt Weinberg is an assistant professor of computer science at Princeton University. Before that, he was also a postdoc at Princeton CS, and a research fellow at the Simons Institute (Algorithmic Game Theory in 2015, and Algorithms and Uncertainty in 2016). He received his PhD from MIT in 2014 with Costis Daskalakis.