IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2305.05590.html
   My bibliography  Save this paper

Description Complexity of Regular Distributions

Author

Listed:
  • Renato Paes Leme
  • Balasubramanian Sivan
  • Yifeng Teng
  • Pratik Worah

Abstract

Myerson's regularity condition of a distribution is a standard assumption in economics. In this paper, we study the complexity of describing a regular distribution within a small statistical distance. Our main result is that $\tilde{\Theta}{(\epsilon^{-0.5})}$ bits are necessary and sufficient to describe a regular distribution with support $[0,1]$ within $\epsilon$ Levy distance. We prove this by showing that we can learn the regular distribution approximately with $\tilde{O}(\epsilon^{-0.5})$ queries to the cumulative density function. As a corollary, we show that the pricing query complexity to learn the class of regular distribution with support $[0,1]$ within $\epsilon$ Levy distance is $\tilde{\Theta}{(\epsilon^{-2.5})}$. To learn the mixture of two regular distributions, $\tilde{\Theta}(\epsilon^{-3})$ pricing queries are required.

Suggested Citation

  • Renato Paes Leme & Balasubramanian Sivan & Yifeng Teng & Pratik Worah, 2023. "Description Complexity of Regular Distributions," Papers 2305.05590, arXiv.org.
  • Handle: RePEc:arx:papers:2305.05590
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2305.05590
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Bulow, Jeremy & Klemperer, Paul, 1996. "Auctions versus Negotiations," American Economic Review, American Economic Association, vol. 86(1), pages 180-194, March.
    2. Myerson, Roger B. & Satterthwaite, Mark A., 1983. "Efficient mechanisms for bilateral trading," Journal of Economic Theory, Elsevier, vol. 29(2), pages 265-281, April.
    3. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    4. Amine Allouah & Omar Besbes, 2020. "Prior-Independent Optimal Auctions," Management Science, INFORMS, vol. 66(10), pages 4417-4432, October.
    5. L. Elisa Celis & Gregory Lewis & Markus Mobius & Hamid Nazerzadeh, 2014. "Buy-It-Now or Take-a-Chance: Price Discrimination Through Randomized Auctions," Management Science, INFORMS, vol. 60(12), pages 2927-2948, December.
    Full references (including those not matched with items on IDEAS)

    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. Roberto Burguet & Martin K. Perry, 2009. "Preferred suppliers in auction markets," RAND Journal of Economics, RAND Corporation, vol. 40(2), pages 283-295, June.
    2. Jeong, Seungwon (Eugene) & Lee, Joosung, 2024. "The groupwise-pivotal referral auction: Core-selecting referral strategy-proof mechanism," Games and Economic Behavior, Elsevier, vol. 143(C), pages 191-203.
    3. 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.
    4. Loertscher, Simon & Marx, Leslie M., 2019. "Merger review with intermediate buyer power," International Journal of Industrial Organization, Elsevier, vol. 67(C).
    5. Simon Loertscher & Leslie M. Marx, 2021. "Coordinated Effects in Merger Review," Journal of Law and Economics, University of Chicago Press, vol. 64(4), pages 705-744.
    6. McAfee, R. Preston & Vincent, Daniel, 1997. "Sequentially Optimal Auctions," Games and Economic Behavior, Elsevier, vol. 18(2), pages 246-276, February.
    7. Bradley J Larsen, 2021. "The Efficiency of Real-World Bargaining: Evidence from Wholesale Used-Auto Auctions," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 88(2), pages 851-882.
    8. Yiding Feng & Yaonan Jin, 2024. "Beyond Regularity: Simple versus Optimal Mechanisms, Revisited," Papers 2411.03583, arXiv.org.
    9. Maslov, Alexander & Noiset, Luc & Schwartz, Jesse A., 2022. "A closer look at two conjectures about irregular marginal revenue," Economics Letters, Elsevier, vol. 218(C).
    10. Scott Fay & Robert Zeithammer, 2017. "Bidding for Bidders? How the Format for Soliciting Supplier Participation in NYOP Auctions Impacts Channel Profit," Management Science, INFORMS, vol. 63(12), pages 4324-4344, December.
    11. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    12. Stefano Galavotti, 2014. "Reducing Inefficiency in Public Good Provision Through Linking," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 16(3), pages 427-466, June.
    13. Jean-Michel Benkert, 2015. "Bilateral trade with loss-averse agents," ECON - Working Papers 188, Department of Economics - University of Zurich, revised Jul 2022.
    14. Kos, Nenad & Messner, Matthias, 2013. "Extremal incentive compatible transfers," Journal of Economic Theory, Elsevier, vol. 148(1), pages 134-164.
    15. Wei He & Jiangtao Li & Weijie Zhong, 2024. "Rank-Guaranteed Auctions," Papers 2408.12001, arXiv.org.
    16. Schmitz, Patrick W., 2003. "On second-price auctions and imperfect competition," Journal of Mathematical Economics, Elsevier, vol. 39(8), pages 901-909, November.
    17. Patrick W. Schmitz, 2006. "Information Gathering, Transaction Costs, and the Property Rights Approach," American Economic Review, American Economic Association, vol. 96(1), pages 422-434, March.
    18. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.
    19. Schmitz, Patrick W., 2002. "On Monopolistic Licensing Strategies under Asymmetric Information," Journal of Economic Theory, Elsevier, vol. 106(1), pages 177-189, September.
    20. Yuen Leng Chow & Isa E. Hafalir & Abdullah Yavas, 2015. "Auction versus Negotiated Sale: Evidence from Real Estate Sales," Real Estate Economics, American Real Estate and Urban Economics Association, vol. 43(2), pages 432-470, June.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:arx:papers:2305.05590. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.