Online Ascending Auctions for Gradually Expiring Items
- Creators
- Lavi, Ron
- Nisan, Noam
Abstract
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.
Additional Information
© 2004 Society for Industrial and Applied Mathematics. We wish to warmly thank Yair Bartal and Ahuva Mu'alem for their help in the early stages of this work. We also thank Moshe Babaioff, Liad Blumrosen, Rica Gonen, Daniel Lehmann, and Motty Perry for many helpful discussions and comments.Attached Files
Published - Lavi2005p11452Proceedings_Of_The_Sixteenth_Annual_Acm-Siam_Symposium_On_Discrete_Algorithms.pdf
Files
Name | Size | Download all |
---|---|---|
md5:be0a48b61b82a52289e0ef8d8dab285a
|
822.3 kB | Preview Download |
Additional details
- Eprint ID
- 20236
- Resolver ID
- CaltechAUTHORS:20100930-123758119
- Created
-
2010-11-11Created from EPrint's datestamp field
- Updated
-
2019-10-03Created from EPrint's last_modified field