Lavi, Ron and Nisan, Noam (2005) Online Ascending Auctions for Gradually Expiring Items. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, pp. 1146-1155. ISBN 978-0-89871-585-9 http://resolver.caltech.edu/CaltechAUTHORS:20100930-123758119
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20100930-123758119
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.
|Item Type:||Book Section|
|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.|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Tony Diaz|
|Deposited On:||11 Nov 2010 23:43|
|Last Modified:||26 Dec 2012 12:29|
Repository Staff Only: item control page