An Overview of Recent Developments in Combinatorial Auctions

In a combinatorial auction, there are m items for sale to n bidders, each with a valuation function over sets of items (that is, fully describing a bidder's valuation function requires 2^m numbers). The designer's goal is to allocate the items in a way that optimizes the total welfare: the sum over all bidders of their value for the set they receive.

In this talk, I'll provide a brief overview of seminal results for this problem, and a deeper overview of several recent results. This talk will focus on the communication complexity of resolving this problem -- the amount of communication necessary among the bidders to find an (approximately) optimal allocation.

I'll highlight one recent result in further detail, which settles the communication complexity of achieving any approximation guarantee using a maximal-in-range mechanism. This result is joint work with Frederick Qiu.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.