Taming the Communication and Computation Complexity of Combinatorial Auctions: The FUEL Bid Language

Martin Bichler, Paul Milgrom, Gregor Schwarz

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Combinatorial auctions have found widespread application for allocating multiple items in the presence of complex bidder preferences. The enumerative exclusive OR (XOR) bid language is the de facto standard bid language for spectrum auctions and other applications, despite the difficulties, in larger auctions, of enumerating all the relevant packages or solving the resulting NP-hard winner determination problem. We introduce the flexible use and efficient licensing (FUEL) bid language, which was proposed for radio spectrum auctions to ease both communications and computations compared with XOR-based auctions. We model the resulting allocation problem as an integer program, discuss computational complexity, and conduct an extensive set of computational experiments, showing that the winner determination problem of the FUEL bid language can be solved reliably for large realistic-sized problem instances in less than half an hour on average. In contrast, auctions with an XOR bid language quickly become intractable even for much smaller problem sizes. We compare a sealed-bid FUEL auction to a sealed-bid auction with an XOR bid language and to a simultaneous clock auction. The sealed-bid auction with an XOR bid language incurs significant welfare losses because of the missing bids problem and computational hardness, the simultaneous clock auction leads to a substantially lower efficiency than FUEL because of the exposure problem.

Original languageEnglish
Pages (from-to)2217-2238
Number of pages22
JournalManagement Science
Volume69
Issue number4
DOIs
StatePublished - Apr 2023

Keywords

  • bid languages
  • market design
  • spectrum auction

Fingerprint

Dive into the research topics of 'Taming the Communication and Computation Complexity of Combinatorial Auctions: The FUEL Bid Language'. Together they form a unique fingerprint.

Cite this