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

Revenue maximization with a single sample

Author

Listed:
  • Dhangwatnotai, Peerapong
  • Roughgarden, Tim
  • Yan, Qiqi

Abstract

This paper pursues auctions that are prior-independent. The goal is to design an auction such that, whatever the underlying valuation distribution, its expected revenue is almost as large as that of an optimal auction tailored for that distribution. We propose the prior-independent Single Sample mechanism, which is essentially the Vickrey–Clarke–Groves (VCG) mechanism, supplemented with reserve prices chosen at random from participants' bids. We prove that under reasonably general assumptions, this mechanism simultaneously approximates all Bayesian-optimal mechanisms for all valuation distributions. Conceptually, our analysis shows that even a single sample from a distribution — some bidder's valuation — is sufficient information to obtain near-optimal expected revenue.

Suggested Citation

  • Dhangwatnotai, Peerapong & Roughgarden, Tim & Yan, Qiqi, 2015. "Revenue maximization with a single sample," Games and Economic Behavior, Elsevier, vol. 91(C), pages 318-333.
    • Handle: RePEc:eee:gamebe:v:91:y:2015:i:c:p:318-333
    DOI: 10.1016/j.geb.2014.03.011
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825614000645
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2014.03.011?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. 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.
    2. Bulow, Jeremy & Klemperer, Paul, 1996. "Auctions versus Negotiations," American Economic Review, American Economic Association, vol. 86(1), pages 180-194, March.
    3. Ilya Segal, 2003. "Optimal Pricing Mechanisms with Unknown Demand," American Economic Review, American Economic Association, vol. 93(3), pages 509-529, June.
    4. Dirk Bergemann & Stephen Morris, 2012. "Robust Mechanism Design," World Scientific Book Chapters, in: Robust Mechanism Design The Role of Private Information and Higher Order Beliefs, chapter 2, pages 49-96, World Scientific Publishing Co. Pte. Ltd..
    5. Krishna, Vijay, 2009. "Auction Theory," Elsevier Monographs, Elsevier, edition 2, number 9780123745071.
    6. Neeman, Zvika, 2003. "The effectiveness of English auctions," Games and Economic Behavior, Elsevier, vol. 43(2), pages 214-238, May.
    7. Bernard Caillaud & Jacques Robert, 2005. "Implementation of the revenue-maximizing auction by an ignorant seller," Review of Economic Design, Springer;Society for Economic Design, vol. 9(2), pages 127-143, April.
    8. Goldberg, Andrew V. & Hartline, Jason D. & Karlin, Anna R. & Saks, Michael & Wright, Andrew, 2006. "Competitive auctions," Games and Economic Behavior, Elsevier, vol. 55(2), pages 242-269, May.
    9. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    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. Bikhchandani, Sushil & Mishra, Debasis, 2022. "Selling two identical objects," Journal of Economic Theory, Elsevier, vol. 200(C).
    2. Dirk Bergemann & Francisco Castro & Gabriel Weintraub, 2019. "Uniform Pricing Versus Third-Degree Price Discrimination," Cowles Foundation Discussion Papers 2213r, Cowles Foundation for Research in Economics, Yale University, revised Feb 2020.
    3. Yash Kanoria & Hamid Nazerzadeh, 2021. "Incentive-Compatible Learning of Reserve Prices for Repeated Auctions," Operations Research, INFORMS, vol. 69(2), pages 509-524, March.
    4. Mahsa Derakhshan & Negin Golrezaei & Renato Paes Leme, 2022. "Linear Program-Based Approximation for Personalized Reserve Prices," Management Science, INFORMS, vol. 68(3), pages 1849-1864, March.
    5. 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.
    6. Çağıl Koçyiğit & Garud Iyengar & Daniel Kuhn & Wolfram Wiesemann, 2020. "Distributionally Robust Mechanism Design," Management Science, INFORMS, vol. 66(1), pages 159-189, January.
    7. Jerry Anunrojwong & Santiago R. Balseiro & Omar Besbes, 2022. "On the Robustness of Second-Price Auctions in Prior-Independent Mechanism Design," Papers 2204.10478, arXiv.org, revised Jan 2024.
    8. Bergemann, Dirk & Castro, Francisco & Weintraub, Gabriel, 2022. "Third-degree price discrimination versus uniform pricing," Games and Economic Behavior, Elsevier, vol. 131(C), pages 275-291.
    9. Moshe Babaioff & Michal Feldman & Yannai A. Gonczarowski & Brendan Lucier & Inbal Talgam-Cohen, 2020. "Escaping Cannibalization? Correlation-Robust Pricing for a Unit-Demand Buyer," Papers 2003.05913, arXiv.org, revised Aug 2020.
    10. Han, Jun & Weber, Thomas A., 2023. "Price discrimination with robust beliefs," European Journal of Operational Research, Elsevier, vol. 306(2), pages 795-809.
    11. Loertscher, Simon & Marx, Leslie M., 2020. "Asymptotically optimal prior-free clock auctions," Journal of Economic Theory, Elsevier, vol. 187(C).
    12. Babichenko, Yakov & Talgam-Cohen, Inbal & Xu, Haifeng & Zabarnyi, Konstantin, 2022. "Regret-minimizing Bayesian persuasion," Games and Economic Behavior, Elsevier, vol. 136(C), pages 226-248.
    13. Hemant K. Bhargava & Gergely Csapó & Rudolf Müller, 2020. "On Optimal Auctions for Mixing Exclusive and Shared Matching in Platforms," Management Science, INFORMS, vol. 66(6), pages 2653-2676, June.
    14. Shixin Wang, 2023. "The Power of Simple Menus in Robust Selling Mechanisms," Papers 2310.17392, arXiv.org.
    15. Amine Allouah & Omar Besbes, 2020. "Prior-Independent Optimal Auctions," Management Science, INFORMS, vol. 66(10), pages 4417-4432, October.
    16. Jerry Anunrojwong & Santiago R. Balseiro & Omar Besbes, 2023. "Robust Auction Design with Support Information," Papers 2305.09065, arXiv.org, revised Aug 2023.
    17. Jin Xi & Haitian Xie, 2021. "Strength in Numbers: Robust Mechanisms for Public Goods with Many Agents," Papers 2101.02423, arXiv.org, revised May 2023.
    18. Haitian Xie, 2020. "Finite-Sample Average Bid Auction," Papers 2008.10217, arXiv.org, revised Feb 2022.
    19. You Zu & Krishnamurthy Iyer & Haifeng Xu, 2021. "Learning to Persuade on the Fly: Robustness Against Ignorance," Papers 2102.10156, arXiv.org.

    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. Tim Roughgarden & Inbal Talgam-Cohen, 2018. "Approximately Optimal Mechanism Design," Papers 1812.11896, arXiv.org, revised Aug 2020.
    2. Li, Yunan, 2017. "Approximation in mechanism design with interdependent values," Games and Economic Behavior, Elsevier, vol. 103(C), pages 225-253.
    3. 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.
    4. Kim-Sau Chung & J.C. Ely, 2007. "Foundations of Dominant-Strategy Mechanisms," Review of Economic Studies, Oxford University Press, vol. 74(2), pages 447-476.
    5. Shuchi Chawla & Jason D. Hartline & Denis Nekipelov, 2016. "A/B Testing of Auctions," Papers 1606.00908, arXiv.org.
    6. Hashimoto, Tadashi, 2018. "The generalized random priority mechanism with budgets," Journal of Economic Theory, Elsevier, vol. 177(C), pages 708-733.
    7. Wang, Dazhong & Xu, Xinyi, 2022. "Optimal equity auction with interdependent valuations," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    8. Loertscher, Simon & Marx, Leslie M., 2020. "Asymptotically optimal prior-free clock auctions," Journal of Economic Theory, Elsevier, vol. 187(C).
    9. 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.
    10. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.
    11. Jin Xi & Haitian Xie, 2021. "Strength in Numbers: Robust Mechanisms for Public Goods with Many Agents," Papers 2101.02423, arXiv.org, revised May 2023.
    12. Schmitz, Patrick W., 2003. "On second-price auctions and imperfect competition," Journal of Mathematical Economics, Elsevier, vol. 39(8), pages 901-909, November.
    13. Jehiel, Philippe & Lamy, Laurent, 2014. "On discrimination in procurement auctions," CEPR Discussion Papers 9790, C.E.P.R. Discussion Papers.
    14. Simon Loertscher & Andras Niedermayer, 2012. "Fee-Setting Mechanisms: On Optimal Pricing by Intermediaries and Indirect Taxation," Department of Economics - Working Papers Series 1162, The University of Melbourne.
    15. Ronald M. Harstad, 2007. "Does a Seller Really Want Another Bidder?," Working Papers 0711, Department of Economics, University of Missouri.
    16. Stephanie Rosenkranz & Patrick W. Schmitz, 2007. "Reserve Prices in Auctions as Reference Points," Economic Journal, Royal Economic Society, vol. 117(520), pages 637-653, April.
    17. Jason Shachat & Lijia Tan, 2015. "An Experimental Investigation of Auctions and Bargaining in Procurement," Management Science, INFORMS, vol. 61(5), pages 1036-1051, May.
    18. Kirkegaard, René & Overgaard, Per Baltzer, 2008. "Pre-auction offers in asymmetric first-price and second-price auctions," Games and Economic Behavior, Elsevier, vol. 63(1), pages 145-165, May.
    19. 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..
    20. Sushil Bikhchandani & Shurojit Chatterjee & Arunava Sen, 2004. "Incentive Compatibility in Multi-unit Auctions," Levine's Bibliography 122247000000000750, UCLA Department of Economics.

    More about this item

    Keywords

    Auctions; Approximation; Revenue-maximization; Prior-independence;
    All these keywords.

    JEL classification:

    • D44 - Microeconomics - - Market Structure, Pricing, and Design - - - Auctions

    Statistics

    Access and download statistics

    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:91:y:2015:i:c:p:318-333. 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.