(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 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 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).

– revisit existing separations between poly-time algorithms and poly-time truthful mechanisms via a new solution concept “Implementation in Advised Strategies” (joint work with Linda Cai and Clayton Thomas).

– resolve the communication complexity of combinatorial auctions for two subadditive players (joint work with Tomer Ezra, Michal Feldman, Eric Neyman, and Inbal Talgam-Cohen, time-permitting).