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

Approximation in mechanism design with interdependent values

Author

Listed:
  • Li, Yunan

Abstract

This paper studies the revenue maximization problem in environments wherein buyers have interdependent values and correlated types. We show that (1) when the system of feasible sets is a matroid and buyer valuations satisfy a single-crossing condition, the generalized Vickrey–Clarke–Groves mechanisms with lazy reserves (VCG-L) are ex-post incentive compatible and ex-post individually rational; (2) if, in addition, the valuation distribution satisfies a generalized monotone hazard rate condition, the VCG-L mechanism with conditional monopoly reserves is approximately optimal. Then we construct an ascending auction that implements the truth-telling equilibrium of a VCG-L mechanism in ex-post equilibrium. Finally, we discuss the connection between the VCG-L mechanisms and greedy algorithms studied in Lehmann et al. (2002) and deferred-acceptance auctions studied in Milgrom and Segal (2014), and the impact of competition by proving a Bulow and Klemperer (1996) type result.

Suggested Citation

  • Li, Yunan, 2017. "Approximation in mechanism design with interdependent values," Games and Economic Behavior, Elsevier, vol. 103(C), pages 225-253.
  • Handle: RePEc:eee:gamebe:v:103:y:2017:i:c:p:225-253
    DOI: 10.1016/j.geb.2016.01.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825616000099
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.geb.2016.01.006?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. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    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. , & ,, 2015. "Implementation with interdependent valuations," Theoretical Economics, Econometric Society, vol. 10(3), September.
    5. Jehiel, Philippe & Moldovanu, Benny, 2001. "Efficient Design with Interdependent Valuations," Econometrica, Econometric Society, vol. 69(5), pages 1237-1259, September.
    6. Peter Cramton & John McMillan & Paul Milgrom & Bradley Miller & Bridger Mitchell & Daniel Vincent & Robert Wilson, 1998. "Simultaneous Ascending Auctions with Package Bidding," Papers of Peter Cramton 98cra2, University of Maryland, Department of Economics - Peter Cramton.
    7. Krishna, Vijay, 2009. "Auction Theory," Elsevier Monographs, Elsevier, edition 2, number 9780123745071.
    8. Ausubel Lawrence M & Milgrom Paul R, 2002. "Ascending Auctions with Package Bidding," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 1(1), pages 1-44, August.
    9. Cramton, Peter, 1998. "Ascending auctions," European Economic Review, Elsevier, vol. 42(3-5), pages 745-756, May.
    10. Lawrence Ausubel, 2000. "A Generalized Vickrey Auction," Econometric Society World Congress 2000 Contributed Papers 1257, Econometric Society.
    11. Paul Klemperer, 2004. "Auctions: Theory and Practice," Online economics textbooks, SUNY-Oswego, Department of Economics, number auction1, March.
    12. Hendricks, Kenneth & Porter, Robert H, 1988. "An Empirical Study of an Auction with Asymmetric Information," American Economic Review, American Economic Association, vol. 78(5), pages 865-883, December.
    13. Milgrom,Paul, 2004. "Putting Auction Theory to Work," Cambridge Books, Cambridge University Press, number 9780521536721, October.
    14. Demange, Gabrielle & Gale, David & Sotomayor, Marilda, 1986. "Multi-Item Auctions," Journal of Political Economy, University of Chicago Press, vol. 94(4), pages 863-872, August.
    15. Motty Perry & Philip J. Reny, 2002. "An Efficient Auction," Econometrica, Econometric Society, vol. 70(3), pages 1199-1212, May.
    16. Kenneth Hendricks & Joris Pinkse & Robert H. Porter, 2003. "Empirical Implications of Equilibrium Bidding in First-Price, Symmetric, Common Value Auctions," Review of Economic Studies, Oxford University Press, vol. 70(1), pages 115-145.
    17. Milgrom, Paul R & Weber, Robert J, 1982. "A Theory of Auctions and Competitive Bidding," Econometrica, Econometric Society, vol. 50(5), pages 1089-1122, September.
    18. Motty Perry & Philip J. Reny, 2005. "An Efficient Multi-Unit Ascending Auction," Review of Economic Studies, Oxford University Press, vol. 72(2), pages 567-592.
    19. Neeman, Zvika, 2003. "The effectiveness of English auctions," Games and Economic Behavior, Elsevier, vol. 43(2), pages 214-238, May.
    20. Paul Klemperer, 2004. "Auctions: Theory and Practice," Online economics textbooks, SUNY-Oswego, Department of Economics, number auction1.
    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. Mariann Ollár & Antonio Penta, 2019. "Implementation via transfers with identical but unknown distributions," Economics Working Papers 1676, Department of Economics and Business, Universitat Pompeu Fabra.
    2. Mariann Ollár & Antonio Penta, 2021. "A Network Solution to Robust Implementation: The Case of Identical but Unknown Distributions," Working Papers 1248, Barcelona School of Economics.

    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. Satoru Fujishige & Zaifu Yang, 2020. "A Universal Dynamic Auction for Unimodular Demand Types: An Efficient Auction Design for Various Kinds of Indivisible Commodities," Discussion Papers 20/08, Department of Economics, University of York.
    2. Kaplan, Todd R. & Zamir, Shmuel, 2015. "Advances in Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    3. A. Talman & Zaifu Yang, 2015. "An efficient multi-item dynamic auction with budget constrained bidders," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(3), pages 769-784, August.
    4. Ning Sun & Zaifu Yang, 2014. "An Efficient and Incentive Compatible Dynamic Auction for Multiple Complements," Journal of Political Economy, University of Chicago Press, vol. 122(2), pages 422-466.
    5. Eric Maskin, 2004. "The Unity of Auction Theory: Paul Milgrom's Masterclass," Economics Working Papers 0044, Institute for Advanced Study, School of Social Science.
    6. Satoru Fujishige & Zaifu Yang, 2017. "On a spontaneous decentralized market process," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 2(1), pages 1-37, December.
    7. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    8. Philippe Jehiel & Benny Moldovanu, 2005. "Allocative and Informational Externalities in Auctions and Related Mechanisms," Levine's Bibliography 784828000000000490, UCLA Department of Economics.
    9. Committee, Nobel Prize, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    10. Onur A. Koska & Ilke Onur & Frank Stähler, 2018. "The scope of auctions in the presence of downstream interactions and information externalities," Journal of Economics, Springer, vol. 125(2), pages 107-136, October.
    11. Ning Sun & Zaifu Yang, 2008. "A Double-Track Auction for Substitutes and Complements," KIER Working Papers 656, Kyoto University, Institute of Economic Research.
    12. Lorentziadis, Panos L., 2016. "Optimal bidding in auctions from a game theory perspective," European Journal of Operational Research, Elsevier, vol. 248(2), pages 347-371.
    13. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press, vol. 33(4), pages 541-571.
    14. Gerard van der Laan & Zaifu Yang, 2016. "An ascending multi-item auction with financially constrained bidders," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 1(1), pages 109-149, December.
    15. Li, Zhen & Kuo, Ching-Chung, 2011. "Revenue-maximizing Dutch auctions with discrete bid levels," European Journal of Operational Research, Elsevier, vol. 215(3), pages 721-729, December.
    16. Emiel Maasland & Sander Onderstal, 2006. "Going, Going, Gone! A Swift Tour of Auction Theory and its Applications," De Economist, Springer, vol. 154(2), pages 197-249, June.
    17. Sweeting, Andrew & Bhattacharya, Vivek, 2015. "Selective entry and auction design," International Journal of Industrial Organization, Elsevier, vol. 43(C), pages 189-207.
    18. Akiyoshi Shioura & Zaifu Yang, 2013. "Equilibrium, Auction, Multiple Substitutes and Complements," Discussion Papers 13/17, Department of Economics, University of York.
    19. 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.
    20. Condorelli, Daniele, 2013. "Market and non-market mechanisms for the optimal allocation of scarce resources," Games and Economic Behavior, Elsevier, vol. 82(C), pages 582-591.

    More about this item

    Keywords

    Mechanism design; Approximation; Interdependent values; Revenue maximization;
    All these keywords.

    JEL classification:

    • D44 - Microeconomics - - Market Structure, Pricing, and Design - - - Auctions
    • D82 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Asymmetric and Private Information; Mechanism Design

    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:103:y:2017:i:c:p:225-253. 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.