Online ascending auctions for gradually expiring items

We consider dynamic auction mechanisms for the allocation of multiple items. Items are identical, but have different expiration times, and each item must be allocated before it expires. Buyers are of dynamic nature, and arrive and depart over time. Our goal is to design mechanisms that maximize the social welfare. We begin by showing that dominant-strategy incentive-compatibility cannot be used in this case, since any such auction cannot obtain any constant fraction of the optimal social welfare. We then design two auctions that perform well under a wide class of “semi-myopic” strategies. For every combination of such strategies, the auction is associated with a different algorithm (or allocation rule), and so we have a family of “semi-myopic” algorithms. We show that any algorithm in this family obtains at least 1/3 of the optimal social welfare. We also provide some game-theoretic justification for acting in a semi-myopic way. We suggest a new notion of “Set-Nash” equilibrium, where we cannot pinpoint a single best-response strategy, but rather only a set to which best-response strategies belong. We show that our auctions have a Set-Nash equilibrium which is all semi-myopic.