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. Neeman, Zvika, 2003. "The effectiveness of English auctions," Games and Economic Behavior, Elsevier, vol. 43(2), pages 214-238, May.
    6. 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.
    7. Krishna, Vijay, 2009. "Auction Theory," Elsevier Monographs, Elsevier, edition 2, number 9780123745071.
    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. Duarte Gonc{c}alves & Bruno A. Furtado, 2024. "Statistical Mechanism Design: Robust Pricing, Estimation, and Inference," Papers 2405.17178, arXiv.org.
    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. 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.
    5. 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.
    6. 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.
    7. Ç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.
    8. 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 Dec 2024.
    9. 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.
    10. Çağıl Koçyiğit & Daniel Kuhn & Napat Rujeerapaiboon, 2024. "Regret Minimization and Separation in Multi-Bidder, Multi-Item Auctions," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1543-1561, December.
    11. 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.
    12. Han, Jun & Weber, Thomas A., 2023. "Price discrimination with robust beliefs," European Journal of Operational Research, Elsevier, vol. 306(2), pages 795-809.
    13. Andrew Komo & Scott Duke Kominers & Tim Roughgarden, 2024. "Shill-Proof Auctions," Papers 2404.00475, arXiv.org, revised Nov 2024.
    14. Loertscher, Simon & Marx, Leslie M., 2020. "Asymptotically optimal prior-free clock auctions," Journal of Economic Theory, Elsevier, vol. 187(C).
    15. 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.
    16. 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.
    17. Shixin Wang, 2023. "The Power of Simple Menus in Robust Selling Mechanisms," Papers 2310.17392, arXiv.org, revised Sep 2024.
    18. Amine Allouah & Omar Besbes, 2020. "Prior-Independent Optimal Auctions," Management Science, INFORMS, vol. 66(10), pages 4417-4432, October.
    19. Jerry Anunrojwong & Santiago R. Balseiro & Omar Besbes, 2023. "Robust Auction Design with Support Information," Papers 2305.09065, arXiv.org, revised Jan 2025.
    20. Jin Xi & Haitian Xie, 2021. "Strength in Numbers: Robust Mechanisms for Public Goods with Many Agents," Papers 2101.02423, arXiv.org, revised May 2023.
    21. Haitian Xie, 2020. "Finite-Sample Average Bid Auction," Papers 2008.10217, arXiv.org, revised Feb 2022.
    22. You Zu & Krishnamurthy Iyer & Haifeng Xu, 2021. "Learning to Persuade on the Fly: Robustness Against Ignorance," Papers 2102.10156, arXiv.org, revised May 2024.

    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. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.
    5. 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.
    6. Jin Xi & Haitian Xie, 2021. "Strength in Numbers: Robust Mechanisms for Public Goods with Many Agents," Papers 2101.02423, arXiv.org, revised May 2023.
    7. Shuchi Chawla & Jason D. Hartline & Denis Nekipelov, 2016. "A/B Testing of Auctions," Papers 1606.00908, arXiv.org.
    8. Hashimoto, Tadashi, 2018. "The generalized random priority mechanism with budgets," Journal of Economic Theory, Elsevier, vol. 177(C), pages 708-733.
    9. Wang, Dazhong & Xu, Xinyi, 2022. "Optimal equity auction with interdependent valuations," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    10. Loertscher, Simon & Marx, Leslie M., 2020. "Asymptotically optimal prior-free clock auctions," Journal of Economic Theory, Elsevier, vol. 187(C).
    11. 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.
    12. Wei He & Jiangtao Li & Weijie Zhong, 2024. "Rank-Guaranteed Auctions," Papers 2408.12001, arXiv.org.
    13. Schmitz, Patrick W., 2003. "On second-price auctions and imperfect competition," Journal of Mathematical Economics, Elsevier, vol. 39(8), pages 901-909, November.
    14. Fu, Hu & Haghpanah, Nima & Hartline, Jason & Kleinberg, Robert, 2021. "Full surplus extraction from samples," Journal of Economic Theory, Elsevier, vol. 193(C).
    15. Jehiel, Philippe & Lamy, Laurent, 2014. "On discrimination in procurement auctions," CEPR Discussion Papers 9790, C.E.P.R. Discussion Papers.
    16. 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.
    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. Ronald M. Harstad, 2007. "Does a Seller Really Want Another Bidder?," Working Papers 0711, Department of Economics, University of Missouri.
    19. Jeremy Bulow & Paul Klemperer, 2007. "When are Auctions Best?," Economics Papers 2007-W03, Economics Group, Nuffield College, University of Oxford.
    20. Philippe Jehiel & Laurent Lamy, 2020. "On the Benefits of Set-Asides," Journal of the European Economic Association, European Economic Association, vol. 18(4), pages 1655-1696.

    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.