Robust Scale-Free Auctions
Abstract
We study prior-independent auction design when bidder values are independently and identically distributed and the seller knows only a scale-invariant shape restriction on their distribution, but neither the distribution nor the scale of values. We show that the maximin problem over a broad class of dominant-strategy incentive-compatible mechanisms reduces without loss to scale-free mechanisms. For any $n\ge 2$ monotone-hazard-rate bidders, the second-price auction without a reserve is maximin optimal over this class, including randomized mechanisms that may allocate to a lower bidder. We derive its exact guarantee for every $n$ and the sharp exponential rate at which its loss relative to the Bayesian optimum vanishes. Many familiar auctions are standard: they allocate only to a highest bidder, although incentive compatibility does not require this. For two regular bidders, we solve the standard problem exactly: its optimal mechanism mixes the second-price auction with a relative-markup auction and achieves a worst-case ratio of approximately $0.524413$. We construct a nonstandard mechanism that sometimes allocates to the lower bidder and achieves approximately $0.524829$, proving that standardness is strictly costly. The contrast is driven by tail restrictions: monotone hazard rate makes lower-rank allocation unhelpful, whereas regularity permits it to improve worst-case revenue.