Uppsala University Department of Information Technology

Technical Report 2009-001

A New Analysis of Revenue in the Combinatorial and Simultaneous Auction

Arne Andersson and Jim Wilenius

January 2009

Abstract:

We prove that in many cases, a first-price sealed-bid combinatorial auction gives higher expected revenue than a sealed-bid simultaneous auction. This is the first theoretical evidence that combinatorial auctions indeed generate higher revenue, which has been a common belief for decades.

We use a model with many bidders and items, where bidders are of two types: (i) single-bidders interested in only one item and (ii) synergy-bidders, each interested in one random combination of items. We provide an upper bound on the expected revenue for simultaneous auctions and a lower bound on combinatorial auctions. Our bounds are parameterized on the number of bidders and items, combination size, and synergy.

We derive an asymptotic result, proving that as the number of bidders approach infinity, expected revenue of the combinatorial auction will be higher than that of the simultaneous auction. We also provide concrete examples where the combinatorial auction is revenue-superior.

Note: Updated May 2009.

Available as PDF (177 kB, no cover)

Download BibTeX entry.



Uppsala Universitet