Prior-Free Multi-Unit Auctions with Ordered Bidders
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Prior-free auctions are robust auctions that assume no distribution over bidders valuations and provide worst-case input-by-input approximation guarantees. In contrast to previous work on this topic, we pursue good prior-free auctions with non-identical bidders. Prior-free auctions can approximate meaningful benchmarks for non-identical bidders only when sufficient qualitative information about the bidder asymmetry is publicly known. We consider digital goods auctions where there is a total ordering of the bidders that is known to the seller, where earlier bidders are in some sense thought to have higher valuations. We use the framework of Hartline and Roughgarden STOC 08 to define an appropriate revenue benchmark the maximum revenue that can be obtained from a bid vector using prices that are nonincreasing in the bidder ordering and bounded above by the second-highest bid. This monotone-price benchmark is always as large as the well-known fixed-price benchmark F2, so designing prior-free auctions with good approximation guarantees is only harder. By design, an auction that approximates the monotone-price benchmark satisfies a very strong guarantee it is, in particular, simultaneously near-optimal for essentially every Bayesian environment in which bidders valuation distributions have nonincreasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next. Even when there is no distribution over bidders valuations, such an auction still provides a quantifiable input-by-input performance guarantee. In this paper, we design a simple O1-competitive prior-free auction for digital goods with ordered bidders. We also extend the monotone-price benchmark and our O1-competitive prior-free auction to multi-unit settings with limited supply.
- Economics and Cost Analysis
- Operations Research