TY - GEN
T1 - Prompt mechanisms for online auctions
AU - Cole, Richard
AU - Dobzinski, Shahar
AU - Fleischer, Lisa
PY - 2008
Y1 - 2008
N2 - We study the following online problem: at each time unit, one of m identical items is offered for sale. Bidders arrive and depart dynamically, and each bidder is interested in winning one item between his arrival and departure. Our goal is to design truthful mechanisms that maximize the welfare, the sum of the utilities of winning bidders. We first consider this problem under the assumption that the private information for each bidder is his value for getting an item. In this model constant-competitive mechanisms are known, but we observe that these mechanisms suffer from the following disadvantage: a bidder might learn his payment only when he departs. We argue that these mechanism are essentially unusable, because they impose several seemingly undesirable requirements on any implementation of the mechanisms. To crystalize these issues, we define the notions of prompt and tardy mechanisms. We present two prompt mechanisms, one deterministic and the other randomized, that guarantee a constant competitive ratio. We show that our deterministic mechanism is optimal for this setting. We then study a model in which both the value and the departure time are private information. While in the deterministic setting only a trivial competitive ratio can be guaranteed, we use randomization to obtain a prompt truthful -competitive mechanism. We then show that no truthful randomized mechanism can achieve a ratio better than in this model.
AB - We study the following online problem: at each time unit, one of m identical items is offered for sale. Bidders arrive and depart dynamically, and each bidder is interested in winning one item between his arrival and departure. Our goal is to design truthful mechanisms that maximize the welfare, the sum of the utilities of winning bidders. We first consider this problem under the assumption that the private information for each bidder is his value for getting an item. In this model constant-competitive mechanisms are known, but we observe that these mechanisms suffer from the following disadvantage: a bidder might learn his payment only when he departs. We argue that these mechanism are essentially unusable, because they impose several seemingly undesirable requirements on any implementation of the mechanisms. To crystalize these issues, we define the notions of prompt and tardy mechanisms. We present two prompt mechanisms, one deterministic and the other randomized, that guarantee a constant competitive ratio. We show that our deterministic mechanism is optimal for this setting. We then study a model in which both the value and the departure time are private information. While in the deterministic setting only a trivial competitive ratio can be guaranteed, we use randomization to obtain a prompt truthful -competitive mechanism. We then show that no truthful randomized mechanism can achieve a ratio better than in this model.
UR - http://www.scopus.com/inward/record.url?scp=44449104166&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=44449104166&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-79309-0_16
DO - 10.1007/978-3-540-79309-0_16
M3 - Conference contribution
AN - SCOPUS:44449104166
SN - 3540793089
SN - 9783540793083
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 170
EP - 181
BT - Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings
T2 - 1st International Symposium on Algorithmic Game Theory, SAGT 2008
Y2 - 30 April 2008 through 2 May 2008
ER -