Online Ascending Auctions for Gradually Expiring Items

Опубликовано 6 сентября 2016, 5:15

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.