IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v72y2011i1p1-11.html
   My bibliography  Save this article

Derandomization of auctions

Author

Listed:
  • Aggarwal, Gagan
  • Fiat, Amos
  • Goldberg, Andrew V.
  • Hartline, Jason D.
  • Immorlica, Nicole
  • Sudan, Madhu

Abstract

We study the role of randomization in seller optimal (i.e., profit maximization) auctions. Bayesian optimal auctions (e.g., Myerson, 1981) assume that the valuations of the agents are random draws from a distribution and prior-free optimal auctions either are randomized (e.g., Goldberg et al., 2006) or assume the valuations are randomized (e.g., Segal, 2003). Is randomization fundamental to profit maximization in auctions? Our main result is a general approach to derandomize single-item multi-unit unit-demand auctions while approximately preserving their performance (i.e., revenue). Our general technique is constructive but not computationally tractable. We complement the general result with the explicit and computationally-simple derandomization of a particular auction. Our results are obtained through analogy to hat puzzles that are interesting in their own right.

Suggested Citation

  • Aggarwal, Gagan & Fiat, Amos & Goldberg, Andrew V. & Hartline, Jason D. & Immorlica, Nicole & Sudan, Madhu, 2011. "Derandomization of auctions," Games and Economic Behavior, Elsevier, vol. 72(1), pages 1-11, May.
    • Handle: RePEc:eee:gamebe:v:72:y:2011:i:1:p:1-11
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899-8256(10)00128-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ilya Segal, 2003. "Optimal Pricing Mechanisms with Unknown Demand," American Economic Review, American Economic Association, vol. 93(3), pages 509-529, June.
    2. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    3. HervÊ Moulin, 1999. "Incremental cost sharing: Characterization by coalition strategy-proofness," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 16(2), pages 279-320.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Iftah Gamzu & Danny Segev, 2017. "A Sublogarithmic Approximation for Tollbooth Pricing on Trees," Mathematics of Operations Research, INFORMS, vol. 42(2), pages 377-388, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.
    2. Kim-Sau Chung & J.C. Ely, 2007. "Foundations of Dominant-Strategy Mechanisms," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 74(2), pages 447-476.
    3. Baliga Sandeep & Vohra Rakesh, 2003. "Market Research and Market Design," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 3(1), pages 1-27, August.
    4. Yash Kanoria & Hamid Nazerzadeh, 2020. "Dynamic Reserve Prices for Repeated Auctions: Learning from Bids," Papers 2002.07331, arXiv.org.
    5. Dirk Bergemann & Karl Schlag, 2012. "Robust Monopoly Pricing," World Scientific Book Chapters, in: Robust Mechanism Design The Role of Private Information and Higher Order Beliefs, chapter 13, pages 417-441, World Scientific Publishing Co. Pte. Ltd..
    6. Jarman, Felix & Meisner, Vincent, 2017. "Ex-post optimal knapsack procurement," Journal of Economic Theory, Elsevier, vol. 171(C), pages 35-63.
    7. Vinicius Carrasco & Vitor Farinha Luz & Paulo Monteiro & Humberto Moreira, 2015. "Robust Selling Mechanisms," Textos para discussão 641, Department of Economics PUC-Rio (Brazil).
    8. Mariann Ollár & Antonio Penta, 2021. "A Network Solution to Robust Implementation: The Case of Identical but Unknown Distributions," Working Papers 1248, Barcelona School of Economics.
    9. Ruben Juarez & Rajnish Kumar, 2013. "Implementing efficient graphs in connection networks," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 54(2), pages 359-403, October.
    10. James Bergin & Lin Zhou, 2006. "Monotonic Assignment Rules and Common Pricing," Mathematics of Operations Research, INFORMS, vol. 31(1), pages 133-146, February.
    11. Li, Yunan, 2017. "Approximation in mechanism design with interdependent values," Games and Economic Behavior, Elsevier, vol. 103(C), pages 225-253.
    12. Shuchi Chawla & Jason D. Hartline & Denis Nekipelov, 2016. "A/B Testing of Auctions," Papers 1606.00908, arXiv.org.
    13. Haitian Xie, 2020. "Finite-Sample Average Bid Auction," Papers 2008.10217, arXiv.org, revised Feb 2022.
    14. Moshe Babaioff & Kira Goldner & Yannai A. Gonczarowski, 2019. "Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets," Papers 1903.06696, arXiv.org, revised Dec 2019.
    15. Emmanuelle Auriol & Robert Gary-Bobo, 2007. "On Robust Constitution Design," Theory and Decision, Springer, vol. 62(3), pages 241-279, May.
    16. Dhangwatnotai, Peerapong & Roughgarden, Tim & Yan, Qiqi, 2015. "Revenue maximization with a single sample," Games and Economic Behavior, Elsevier, vol. 91(C), pages 318-333.
    17. Georgiou, Konstantinos & Swamy, Chaitanya, 2019. "Black-box reductions for cost-sharing mechanism design," Games and Economic Behavior, Elsevier, vol. 113(C), pages 17-37.
    18. Devanur, Nikhil R. & Hartline, Jason D. & Yan, Qiqi, 2015. "Envy freedom and prior-free mechanism design," Journal of Economic Theory, Elsevier, vol. 156(C), pages 103-143.
    19. Kazuhiko Hashimoto & Kohei Shiozawa, 2018. "Strategy-Proofness and Efficiency of Probabilistic Mechanisms for Excludable Public Good," Working Papers e118, Tokyo Center for Economic Research.
    20. Thierry Marchant & Debasis Mishra, 2015. "Mechanism design with two alternatives in quasi-linear environments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(2), pages 433-455, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:72:y:2011:i:1:p:1-11. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.