Big Data

Simple and Nearly Optimal Multi-Item Auctions

Date Added: Oct 2012
Format: PDF

The authors provide a Polynomial Time Approximation Scheme (PTAS) for the Bayesian optimal multiitem multi-bidder auction problem under two conditions. First, bidders are independent, have additive valuations and are from the same population. Second, every bidder's value distributions of items are independent but not necessarily identical Monotone Hazard Rate (MHR) distributions. For non-i.i.d. bidders, they also provide PTAS when the number of bidders is small. Prior to their paper, even for a single bidder, only constant factor approximations are known. Another appealing feature of their mechanism is the simple allocation rule. Indeed, the mechanism they use is either the second-price auction with reserve price on every item individually, or VCG allocation with a few outlying items that requires additional treatments.