IDEAS home Printed from https://ideas.repec.org/a/eee/jetheo/v156y2015icp103-143.html
   My bibliography  Save this article

Envy freedom and prior-free mechanism design

Author

Listed:
  • Devanur, Nikhil R.
  • Hartline, Jason D.
  • Yan, Qiqi

Abstract

We consider the provision of an abstract service to single-dimensional agents. Our model includes position auctions, single-minded combinatorial auctions, and constrained matching markets. When the agents' values are drawn independently from a distribution, the Bayesian optimal mechanism is given by Myerson [1] as a virtual-surplus optimizer. We develop a framework for prior-free mechanism design and analysis. A good mechanism in our framework approximates the optimal mechanism for the distribution if there is a distribution; moreover, when there is no distribution this mechanism still provably performs well.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:jetheo:v:156:y:2015:i:c:p:103-143
    DOI: 10.1016/j.jet.2014.08.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0022053114001094
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jet.2014.08.001?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. Bulow, Jeremy & Klemperer, Paul, 1996. "Auctions versus Negotiations," American Economic Review, American Economic Association, vol. 86(1), pages 180-194, March.
    2. Ilya Segal, 2003. "Optimal Pricing Mechanisms with Unknown Demand," American Economic Review, American Economic Association, vol. 93(3), pages 509-529, June.
    3. Bulow, Jeremy & Roberts, John, 1989. "The Simple Economics of Optimal Auctions," Journal of Political Economy, University of Chicago Press, vol. 97(5), pages 1060-1090, October.
    4. 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.
    5. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    6. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    7. Benjamin Edelman & Michael Ostrovsky & Michael Schwarz, 2007. "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords," American Economic Review, American Economic Association, vol. 97(1), pages 242-259, March.
    8. Jason D. Hartline, 2012. "Approximation in Mechanism Design," American Economic Review, American Economic Association, vol. 102(3), pages 330-336, May.
    9. 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.
    10. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    11. Laffont, Jean-Jacques & Robert, Jacques, 1996. "Optimal auction with financially constrained buyers," Economics Letters, Elsevier, vol. 52(2), pages 181-186, August.
    12. Matthew Jackson & Ilan Kremer, 2007. "Envy-freeness and implementation in large economies," Review of Economic Design, Springer;Society for Economic Design, vol. 11(3), pages 185-198, November.
    13. Varian, Hal R., 2007. "Position auctions," International Journal of Industrial Organization, Elsevier, vol. 25(6), pages 1163-1178, December.
    14. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    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. Sambuddha Ghosh & Yan Long & Manipushpak Mitra, 2021. "Prior-free online mechanisms for queueing with arrivals," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 72(2), pages 671-700, September.
    2. Alaei, Saeed & Hartline, Jason & Niazadeh, Rad & Pountourakis, Emmanouil & Yuan, Yang, 2019. "Optimal auctions vs. anonymous pricing," Games and Economic Behavior, Elsevier, vol. 118(C), pages 494-510.
    3. Obara, Takuya & 小原, 拓也 & Tsugawa, Shuichi & Managi, Shunsuke, 2019. "Envy-free Pricing for Impure Public Good," CCES Discussion Paper Series 69, Center for Research on Contemporary Economic Systems, Graduate School of Economics, Hitotsubashi University.
    4. Blume, Lawrence & Easley, David & Kleinberg, Jon & Kleinberg, Robert & Tardos, Éva, 2015. "Introduction to computer science and economic theory," Journal of Economic Theory, Elsevier, vol. 156(C), pages 1-13.
    5. Loertscher, Simon & Marx, Leslie M., 2020. "Asymptotically optimal prior-free clock auctions," Journal of Economic Theory, Elsevier, vol. 187(C).
    6. Mark Braverman & Jon Schneider & S. Matthew Weinberg, 2021. "Prior-free Dynamic Mechanism Design With Limited Liability," Papers 2103.01868, 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. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.
    3. Sebastián D. Bauer, 2023. "Buyers’ welfare maximizing auction design," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(2), pages 555-567, June.
    4. Yi Zhu & Kenneth C. Wilbur, 2011. "Hybrid Advertising Auctions," Marketing Science, INFORMS, vol. 30(2), pages 249-273, 03-04.
    5. Loertscher, Simon & Marx, Leslie M., 2020. "Asymptotically optimal prior-free clock auctions," Journal of Economic Theory, Elsevier, vol. 187(C).
    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. 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.
    8. Jehiel, Philippe & Meyer-ter-Vehn, Moritz & Moldovanu, Benny, 2007. "Mixed bundling auctions," Journal of Economic Theory, Elsevier, vol. 134(1), pages 494-512, May.
    9. Michael Ostrovsky & Michael Schwarz, 2023. "Reserve Prices in Internet Advertising Auctions: A Field Experiment," Journal of Political Economy, University of Chicago Press, vol. 131(12), pages 3352-3376.
    10. Committee, Nobel Prize, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    11. Yu Ning & Su Xiu Xu & George Q. Huang & Xudong Lin, 2021. "Optimal digital product auctions with unlimited supply and rebidding behavior," Annals of Operations Research, Springer, vol. 307(1), pages 399-416, December.
    12. Ronald M. Harstad & Aleksandar Saša Pekeč, 2008. "Relevance to Practice and Auction Theory: A Memorial Essay for Michael Rothkopf," Interfaces, INFORMS, vol. 38(5), pages 367-380, October.
    13. Seiji Takanashi & Takehiro Kawasaki & Taiki Todo & Makoto Yokoo, 2019. "Efficiency in Truthful Auctions via a Social Network," Papers 1904.12422, arXiv.org.
    14. Shuchi Chawla & Jason D. Hartline & Denis Nekipelov, 2016. "A/B Testing of Auctions," Papers 1606.00908, arXiv.org.
    15. Dhangwatnotai, Peerapong & Roughgarden, Tim & Yan, Qiqi, 2015. "Revenue maximization with a single sample," Games and Economic Behavior, Elsevier, vol. 91(C), pages 318-333.
    16. Yukun Cheng & Xiaotie Deng & Dominik Scheder, 2022. "Recent studies of agent incentives in internet resource allocation and pricing," Annals of Operations Research, Springer, vol. 314(1), pages 49-76, July.
    17. Kenneth C. Wilbur & Linli Xu & David Kempe, 2013. "Correcting Audience Externalities in Television Advertising," Marketing Science, INFORMS, vol. 32(6), pages 892-912, November.
    18. Chaithanya Bandi & Dimitris Bertsimas, 2014. "Optimal Design for Multi-Item Auctions: A Robust Optimization Approach," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1012-1038, November.
    19. Guo, Mingyu & Conitzer, Vincent, 2009. "Worst-case optimal redistribution of VCG payments in multi-unit auctions," Games and Economic Behavior, Elsevier, vol. 67(1), pages 69-98, September.
    20. 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.

    More about this item

    Keywords

    Envy freedom; Incentive compatibility; Myerson; Prior-free; Mechanism design;
    All these keywords.

    JEL classification:

    • C7 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory

    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:jetheo:v:156:y:2015:i:c:p:103-143. 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/622869 .

    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.