Overview and Recent Results in Combinatorial Auctions

In this talk, I'll first give a broad overview of the history of combinatorial auctions within TCS, and then discuss some recent results.

Combinatorial auctions center around the following problem: There is a set M of m items, and N of n bidders. Each bidder i has a valuation function vi from subsets of M to real numbers. The goal is to partition the items into S1,…, Sn maximizing ∑ivi(Si).

I'll cover 2x2 variants of this problem:

Computational model (brief overview and statements of results): n parties each separately hold one of the vi, and they must use poly(n,m) runtime/queries/etc. to find as good an approximation as possible.

vs. Communication model (main focus): n parties each separately hold one of the vi and they must use poly(n,m) communication to find as good an approximation as possible.

Algorithm Design version (one main focus): all parties honestly participate in whatever protocol is proposed.

Mechanism Design version (also a main focus): The designer is allowed to charge price pi to agent i, if desired. Party i will behave in whatever way they believe maximizes vi(Si)−pi.

A sample of results I'll aim to discuss (at varying levels of detail):

Tight bounds on achievable approximation guarantees for algorithms.

The Vickrey-Clarke-Groves auction: a black-box reduction from exact mechanism design to exact algorithm design.

Maximal-in-range auctions: tight bounds on the approximation guarantees achievable by "VCG-like" ideas.

Separations between approximation guarantees achievable by algorithms vs. mechanisms.

No prior background in game theory or combinatorial auctions will be assumed.