Computer Science/Discrete Mathematics Seminar II

Topic: Overview and Recent Results in Combinatorial Auctions
Speaker: Matt Weinberg
Affiliation: Princeton University
Date: February 7, 2023

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.

Institute for Advanced Study Transcript on Youtube

Overview and Recent Results in Combinatorial Auctions - Matt Weinberg