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.
@cite_19: We study multi-unit auctions for perishable goods, in a setting where the supply arrives online. This is motivated by its application in advertisement auctions on the internet. We give a 1 4 -competitive algorithm for computing the optimal single price auction assuming that all the agents report their bids truthfully. We use that algorithm to develop a truthful auction with a constant competitive ratio compared to the optimum offline single-price auction.
@cite_16: 
@cite_6: In this paper we consider online auction mechanisms for the allocation of M items that are identical to each other except for the fact that they have different expiration times, and each item must be allocated before it expires. Players arrive at different times, and wish to buy one item before their deadline. The main difficulty is that players act "selfishly" and may mis-report their values, deadlines, or arrival times. We begin by showing that the usual notion of truthfulness (where players follow a single dominant strategy) cannot be used in this case, since any (deterministic) truthful auction cannot obtain better than an M-approximation of the social welfare. Therefore, instead of designing auctions in which players should follow a single strategy, we design two auctions that perform well under a wide class of selfish, "semi-myopic", strategies. For every combination of such strategies, the auction is associated with a different algorithm, and so we have a family of "semi-myopic" algorithms. We show that any algorithm in this family obtains a 3-approximation, and by this conclude that our auctions will perform well under any choice of such semi-myopic behaviors. We next turn to provide a game-theoretic justification for acting in such a semi-myopic way. We suggest a new notion of "Set-Nash" equilibrium, where we cannot pin-point a single best-response strategy, but rather only a set of possible best-response strategies. We show that our auctions have a Set-Nash equilibrium which is all semi-myopic, hence guarantees a 3-approximation. We believe that this notion is of independent interest.
The works most related to ours are Mahdian and Saberi @cite_19 , Cole, Dobzinski, and Fleischer @cite_16 and Lavi and Nisan @cite_6 . Mahdian and Saberi @cite_19 is the only other work that we are aware of to study mechanisms in which the supply is unknown and arrives online. They study the sale of multiple types of goods to bidders who desire only a single item, and wish to design mechanisms to maximize revenue. They consider only the adversarial supply setting, and allow extracting all payments when the entire supply has been exhausted . In this model, they give a truthful mechanism that is constant competitive with respect to the optimal auction that is restricted to selling all items at a single price, and show a lower bound of @math . Their mechanism is randomized, and is based on random-sampling techniques to achieve truthfulness.