Videos

Workshop: Mathematics and Computer Science of Market and Mechanism Design: "An Overview of Recent Developments in Combinatorial Auctions"

Presenter
September 14, 2023
Keywords:
  • market design
  • mechanism design
  • auctions
  • matching
  • approximation
  • equilibrium analysis
  • algorithmic game theory
  • complexity
  • economic theory
  • discrete optimization
  • graph theory
  • mathematical programming
Abstract
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.