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
Induced minor free graphs: isomorphism and clique-width
Belmonte R., Otachi Y., Schweitzer P.  Algorithmica 80(1): 29-47, 2018. Type: Article
Apr 2 2019
A modified artificial bee colony approach for the 0-1 knapsack problem
Cao J., Yin B., Lu X., Kang Y., Chen X.  Applied Intelligence 48(6): 1582-1595, 2018. Type: Article
Aug 22 2018
Symmetric masks for in-fill pixel interpolation on discrete p:q lattices
Ceko M., Guinard A., Svalbe I.  Journal of Mathematical Imaging and Vision 60(3): 304-312, 2018. Type: Article
Jun 20 2018

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
Terms of Use
| Privacy Policy