Prior-free auctions with ordered bidders
Authors:
Open Access
- 19 May 2012
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 427-434
Abstract
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 F (2), 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. Of course, even if 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 prior-free auction for digital goods with ordered bidders, the Random Price Restriction (RPR) auction. We prove that its expected revenue on every bid profile b is Ω(M (2)(b)/log* n), where M (2) denotes the monotone-price benchmark and log* n denotes the number of times that the log 2 operator can be applied to n before the result drops below a fixed constant. © 2012 ACMKeywords
This publication has 13 references indexed in Scilit:
- Crowdsourced Bayesian auctions2012
- Mechanism Design with Set-Theoretic Beliefs2011
- Envy, truth, and profit2011
- Prior-Independent Multi-parameter Mechanism DesignLecture Notes in Computer Science, 2011
- Averaging Techniques for Competitive Auctions2010
- On random sampling auctions for digital goods2009
- Reducing mechanism design to algorithm design via machine learningJournal of Computer and System Sciences, 2008
- Optimal mechanism design and money burning2008
- Competitive auctionsGames and Economic Behavior, 2006
- Envy-free auctions for digital goods2003