CS Talk - Matt Weinberg, Princeton University

Event time: 
Wednesday, January 29, 2020 - 4:15pm
Location: 
AKW 200 See map
51 Prospect Street
New Haven, CT 06511
Event description: 

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.