Computer Science – Computer Science and Game Theory
Scientific paper
2009-05-21
Computer Science
Computer Science and Game Theory
Scientific paper
We study the problem of selling identical goods to n unit-demand bidders in a setting in which the total supply of goods 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(loglog 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 that the monotone hazard rate condition is necessary, and 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.
Babaioff Moshe
Blumrosen Liad
Roth Aaron L.
No associations
LandOfFree
Auctions with Online Supply does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Auctions with Online Supply, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Auctions with Online Supply will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-444646