Computer Science Speaker Series Master Calendar

View Full Calendar

Matt Weinberg "A (biased selection of) recent developments in combinatorial auctions"

Event Type
Illinois Computer Science
2405 Siebel Center for Computer Science
wifi event
Sep 25, 2023   10:00 am  
Matt Weinberg (Princeton)
Candice Steidinger
Originating Calendar
Computer Science Speakers Calendar

We look forward to seeing you in person in 2405 Siebel Center or online


In a combinatorial auction there are m items, and each of n players has a valuation function v_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_i v_i(S_i) ), perhaps assuming that all v_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 a few recent results on this topic which:

 - resolve the communication complexity of achieving an (m/k)-approximation for all monotone valuations via a maximal-in-range mechanism at 2^{\Theta (k)}. This improves on both the previous-best protocol of [Holzman, Kfir-Dahav, Monderer, Tennenholtz 04] and previous-best lower bound of [Daniely, Schapira, Shahaf 15] (joint work with Frederick Qiu).

 - provide the first separation between achievable guarantees of poly-communication algorithms and poly-communication truthful mechanisms for any V

Based on joint works with Mark Braverman and Jieming Mao; and with Sepehr Assadi, Hrishikesh Khandeparkar, and Raghuvansh Saxena.

link for robots only