Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Derandomization of auctions
Aggarwal G., Fiat A., Goldberg A., Hartline J., Immorlica N., Sudan M.  Theory of computing (Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, Baltimore, MD, May 22-24, 2005)619-625.2005.Type:Proceedings
Date Reviewed: Jul 31 2006

In a single-round, sealed-bid auction, every bidder, independently, submits a single bid without seeing the bids of others. One talks about unlimited supply, unit-demand auctions when an infinite number of items is for sale, and every consumer desires at most one unit. An auction is truthful when each bidder has his own strategy to bid, and bid his utility value, regardless of the actions of the other bidders. The aim in general is to design an auction such that it yields a revenue within a constant factor of optimal fixed pricing.

Given a set of bids, the outcome of an auction is the subset of bids that are satisfied and a corresponding set of sale prices such that for each winning bid bi, the associated sale price is at most bi. A deterministic auction mechanism maps sets of bids to an outcome, while a randomized auction mechanism maps sets of bids to probability distributions on auction outcomes.

A result from Goldberg et al. [1] shows that the simplest truthful auction that is approximately optimal in the worst case is a randomized auction. In this paper, the authors show the existence of deterministic auctions that are approximately optimal in the worst case. They also show that such an auction is necessarily asymmetric, that is, the outcome can depend on the order of the input bids. This result answers a question that was left open in Goldberg et al. [1].

Reviewer:  Jan De Beule Review #: CR133121 (0707-0698)
1) Goldberg, A.; Hartline, J.; Wright, A. Competitive auctions and digital goods. In Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, ), SIAM, Philadelphia, PA, 2001, 735–744.
Bookmark and Share
  Featured Reviewer  
Discrete Mathematics (G.2 )
Would you recommend this review?
Other reviews under "Discrete Mathematics": Date
 Discrete mathematics and its applications
Rosen K., McGraw-Hill Higher Education, Columbus, OH, 2002.  928, Type: Book (9780072424348)
May 7 2003
Algorithms on strings
Crochemore M., Hancart C., Lecroq T., Cambridge University Press, New York, NY, 2007.  392, Type: Book (9780521848992)
Apr 8 2008
Algorithms in algebraic geometry (IMA Volumes in Mathematics and its Applications)
Dickenstein A., Schreyer F., Sommese A., Springer, 2007. Type: Book
Jul 30 2008

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy