| Resumo: | <p>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.</p>
<p>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 secondhighest 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. Even when there is no distribution over bidders’ valuations,
such an auction still provides a quantifiable input-by-input performance guarantee.</p>
<p>In this paper, we design a simple O(1)-competitive prior-free auction for digital goods with
ordered bidders. We also extend the monotone-price benchmark and our O(1)-competitive
prior-free auction to multi-unit settings with limited supply.</p>
|
|---|