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. 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.
    2. 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..
    3. 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.
    4. Jarman, Felix & Meisner, Vincent, 2017. "Ex-post optimal knapsack procurement," Journal of Economic Theory, Elsevier, vol. 171(C), pages 35-63.
    5. Li, Yunan, 2017. "Approximation in mechanism design with interdependent values," Games and Economic Behavior, Elsevier, vol. 103(C), pages 225-253.
    6. 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.
    7. Shuchi Chawla & Jason D. Hartline & Denis Nekipelov, 2016. "A/B Testing of Auctions," Papers 1606.00908, arXiv.org.
    8. Haitian Xie, 2020. "Finite-Sample Average Bid Auction," Papers 2008.10217, arXiv.org, revised Feb 2022.
    9. 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.
    10. Emmanuelle Auriol & Robert Gary-Bobo, 2007. "On Robust Constitution Design," Theory and Decision, Springer, vol. 62(3), pages 241-279, May.
    11. Georgiou, Konstantinos & Swamy, Chaitanya, 2019. "Black-box reductions for cost-sharing mechanism design," Games and Economic Behavior, Elsevier, vol. 113(C), pages 17-37.
    12. 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.
    13. Wang, Dazhong & Xu, Xinyi, 2022. "Optimal equity auction with interdependent valuations," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    14. Yash Kanoria & Hamid Nazerzadeh, 2021. "Incentive-Compatible Learning of Reserve Prices for Repeated Auctions," Operations Research, INFORMS, vol. 69(2), pages 509-524, March.
    15. Loertscher, Simon & Marx, Leslie M., 2020. "Asymptotically optimal prior-free clock auctions," Journal of Economic Theory, Elsevier, vol. 187(C).
    16. Xinyu Hua, 2007. "Strategic ex ante contracts: rent extraction and opportunity costs," RAND Journal of Economics, RAND Corporation, vol. 38(3), pages 786-803, September.
    17. Tim Roughgarden & Inbal Talgam-Cohen & Qiqi Yan, 2019. "Robust Auctions for Revenue via Enhanced Competition," Operations Research, INFORMS, vol. 68(4), pages 1074-1094, July.
    18. Blumrosen, Liad & Feldman, Michal, 2013. "Mechanism design with a restricted action space," Games and Economic Behavior, Elsevier, vol. 82(C), pages 424-443.
    19. Loertscher, Simon & Marx, Leslie M., 2023. "Asymptotically optimal prior-free asset market mechanisms," Games and Economic Behavior, Elsevier, vol. 137(C), pages 68-90.
    20. Pham, Hien & Yamashita, Takuro, 2024. "Auction design with heterogeneous priors," Games and Economic Behavior, Elsevier, vol. 145(C), pages 413-425.

    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.