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 ACM.

Prior-free auctions with ordered bidders / Leonardi, Stefano; Tim, Roughgarden. - (2012), pp. 427-433. (Intervento presentato al convegno 44th Annual ACM Symposium on Theory of Computing, STOC '12 tenutosi a New York, New York, USA nel 19 May 2012 through 22 May 2012) [10.1145/2213977.2214018].

Prior-free auctions with ordered bidders

LEONARDI, Stefano;
2012

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 ACM.
2012
44th Annual ACM Symposium on Theory of Computing, STOC '12
algorithmic mechanism design; auction theory
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Prior-free auctions with ordered bidders / Leonardi, Stefano; Tim, Roughgarden. - (2012), pp. 427-433. (Intervento presentato al convegno 44th Annual ACM Symposium on Theory of Computing, STOC '12 tenutosi a New York, New York, USA nel 19 May 2012 through 22 May 2012) [10.1145/2213977.2214018].
File allegati a questo prodotto
File Dimensione Formato  
VE_2012_11573-480693.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 843.78 kB
Formato Adobe PDF
843.78 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/480693
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 3
social impact