  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.
