Moshe Babaioff, Liad Blumrosen, and Aaron Roth
We study the problem of selling identical items to $n$ unit-demand bidders in a setting in which the total supply of items is unknown to the mechanism. Items arrive dynamically, and the seller must make the allocation and payment decisions online with the goal of maximizing social welfare. We consider two models of unknown supply: the adversarial supply model, in which the mechanism must produce a welfare guarantee for any arbitrary supply, and the stochastic supply model, in which supply is drawn from a distribution known to the mechanism, and the mechanism need only provide a welfare guarantee in expectation.
Our main result is a separation between these two models. We show that all truthful mechanisms, even randomized, achieve a diminishing fraction of the optimal social welfare (namely, no better than a $\Omega(\log\log n)$ approximation) in the adversarial setting. In sharp contrast, in the stochastic model, under a standard monotone hazard-rate condition, we present a truthful mechanism that achieves a constant approximation. We show without any condition on the supply distribution, no mechanism can achieve a constant fraction approximation. We also characterize a natural subclass of truthful mechanisms in our setting, the set of online-envy-free mechanisms. All of the mechanisms we present fall into this class, and we prove almost optimal lower bounds for such mechanisms. Since auctions with unknown supply are regularly run in many online-advertising settings, our main results emphasize the importance of considering distributional information in the design of auctions in such environments.
In ACM Conference on Electronic Commerce (EC'10)
Publisher Association for Computing Machinery, Inc.
Copyright © 2007 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or email@example.com. The definitive version of this paper can be found at ACM’s Digital Library --http://www.acm.org/dl/.