Bounding the Competition Complexity for Additive Buyers over Two Independent Items

Abstract

Designing a multi-item auction that obtains optimal revenue is exceedingly difficult, and such auctions are often practically infeasible. However, it is possible to achieve optimal revenue by running a simple auction (i.e. running a separate second-price auction for each item) with additional bidders. The competition complexity of an auction is the number of additional bidders necessary such that selling the items separately (to additional bidders) achieves greater expected revenue than the optimal mechanism (without additional bidders). Prior work has shown that the competition complexity of \(n\) buyers with additive values over two independent items is \(\Omega(\log n)\) and \(O(\sqrt{n})\). The goal of this project is to provide a tighter bound on the competition complexity of two-item auctions with additive buyers and values drawn i.i.d. from the equal revenue curve.