Center for Global Studies

View Full Calendar

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

Event Type
Seminar/Symposium
Sponsor
Illinois Computer Science
Location
2405 Siebel Center for Computer Science
Virtual
wifi event
Date
Sep 25, 2023   10:00 am  
Speaker
Matt Weinberg (Princeton)
Contact
Candice Steidinger
E-Mail
steidin2@illinois.edu
Views
48
Originating Calendar
Computer Science Speakers Calendar

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

Abstract:

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