Computer Science/Discrete Mathematics Seminar II

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 $v_i$ from subsets of M to real numbers. The goal is to partition the items into $S_1,\ldots$, $S_n$ maximizing $\sum_i v_i(S_i)$.

I'll cover 2x2 variants of this problem:

• Computational model (brief overview and statements of results): n parties each separately hold one of the $v_i$, 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 $v_i$ 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 $p_i$ to agent i, if desired. Party i will behave in whatever way they believe maximizes $v_i(S_i) - p_i$. 

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.