IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v58y2010i4-part-2p1079-1089.html
   My bibliography  Save this article

Multidimensional Mechanism Design: Finite-Dimensional Approximations and Efficient Computation

Author

Listed:
  • Alexandre Belloni

    (Fuqua School of Business, Duke University, Durham, North Carolina 27708)

  • Giuseppe Lopomo

    (Fuqua School of Business, Duke University, Durham, North Carolina 27708)

  • Shouqiang Wang

    (Fuqua School of Business, Duke University, Durham, North Carolina 27708)

Abstract

Multidimensional mechanism design problems have proven difficult to solve by extending techniques from the one-dimensional case. This paper considers mechanism design problems with multidimensional types when the seller's cost function is not separable across buyers. By adapting results obtained by Border [Border, K. 1991. Implementation of reduced form auctions: A geometric approach. Econometrica 59 1175--1187], we transform the seller's problem into a representation that only involves “interim” variables and eliminates the dimensionality dependence on the number of buyers. We show that the associated infinite-dimensional optimization problem posed by the theoretical model can be approximated arbitrarily well by a sequence of finite-dimensional linear programming problems.We provide an efficient---i.e., terminating in polynomial time in the problem size---method to compute the separation oracle associated with the Border constraints and incentive compatibility constraints. This implies that our finite-dimensional approximation is solvable in polynomial time.Finally, we illustrate how the numerical solutions of the finite-dimensional approximations can provide insights into the nature of optimal solutions to the infinite-dimensional problem in particular cases.

Suggested Citation

  • Alexandre Belloni & Giuseppe Lopomo & Shouqiang Wang, 2010. "Multidimensional Mechanism Design: Finite-Dimensional Approximations and Efficient Computation," Operations Research, INFORMS, vol. 58(4-part-2), pages 1079-1089, August.
    • Handle: RePEc:inm:oropre:v:58:y:2010:i:4-part-2:p:1079-1089
    DOI: 10.1287/opre.1100.0824
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1100.0824
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1100.0824?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
    ---><---

    References listed on IDEAS

    as
    1. Sandro Brusco & Giuseppe Lopomo & Leslie M. Marx, 2011. "The Economics of Contingent Re-auctions," American Economic Journal: Microeconomics, American Economic Association, vol. 3(2), pages 165-193, May.
    2. Border, Kim C, 1991. "Implementation of Reduced Form Auctions: A Geometric Approach," Econometrica, Econometric Society, vol. 59(4), pages 1175-1187, July.
    3. Myerson, Roger B, 1979. "Incentive Compatibility and the Bargaining Problem," Econometrica, Econometric Society, vol. 47(1), pages 61-73, January.
    4. Manelli, Alejandro M. & Vincent, Daniel R., 2007. "Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly," Journal of Economic Theory, Elsevier, vol. 137(1), pages 153-185, November.
    5. Mussa, Michael & Rosen, Sherwin, 1978. "Monopoly and product quality," Journal of Economic Theory, Elsevier, vol. 18(2), pages 301-317, August.
    6. Armstrong, Mark, 1996. "Multiproduct Nonlinear Pricing," Econometrica, Econometric Society, vol. 64(1), pages 51-75, January.
    7. Jean-Charles Rochet & Philippe Chone, 1998. "Ironing, Sweeping, and Multidimensional Screening," Econometrica, Econometric Society, vol. 66(4), pages 783-826, July.
    8. Eric Maskin & John Riley, 1984. "Monopoly with Incomplete Information," RAND Journal of Economics, The RAND Corporation, vol. 15(2), pages 171-196, Summer.
    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. Braulio Calagua, 2023. "Reducing incentive constraints in bidimensional screening," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 8(1), pages 107-150, December.
    2. Sandro Brusco & Giuseppe Lopomo & Leslie M. Marx, 2011. "The Economics of Contingent Re-auctions," American Economic Journal: Microeconomics, American Economic Association, vol. 3(2), pages 165-193, May.
    3. Goeree, Jacob K. & Kushnir, Alexey, 2016. "Reduced form implementation for environments with value interdependencies," Games and Economic Behavior, Elsevier, vol. 99(C), pages 250-256.
    4. Alexey Kushnir & James Michelson, 2022. "Optimal Multi-Dimensional Auctions: Conjectures and Simulations," Papers 2207.01664, arXiv.org.
    5. Sameer Mehta & Milind Dawande & Ganesh Janakiraman & Vijay Mookerjee, 2022. "An Approximation Scheme for Data Monetization," Production and Operations Management, Production and Operations Management Society, vol. 31(6), pages 2412-2428, June.
    6. Wei Chen & Milind Dawande & Ganesh Janakiraman, 2018. "Optimal Procurement Auctions Under Multistage Supplier Qualification," Manufacturing & Service Operations Management, INFORMS, vol. 20(3), pages 566-582, July.
    7. Saeed Alaei & Hu Fu & Nima Haghpanah & Jason Hartline & Azarakhsh Malekian, 2019. "Efficient Computation of Optimal Auctions via Reduced Forms," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 1058-1086, August.
    8. Kenneth Judd & Garrett van Ryzin, 2010. "Preface to the Special Issue on Computational Economics," Operations Research, INFORMS, vol. 58(4-part-2), pages 1035-1036, August.

    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. Mark Armstrong, 2016. "Nonlinear Pricing," Annual Review of Economics, Annual Reviews, vol. 8(1), pages 583-614, October.
    2. Pascal Courty & Li Hao, 2000. "Sequential Screening," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 67(4), pages 697-717.
    3. Mierendorff, Konrad, 2016. "Optimal dynamic mechanism design with deadlines," Journal of Economic Theory, Elsevier, vol. 161(C), pages 190-222.
    4. Alexey Kushnir & James Michelson, 2022. "Optimal Multi-Dimensional Auctions: Conjectures and Simulations," Papers 2207.01664, arXiv.org.
    5. X. Ruiz del Portal, 2012. "Conditions for incentive compatibility in models with multidimensional allocation functions and one-dimensional types," Review of Economic Design, Springer;Society for Economic Design, vol. 16(4), pages 311-321, December.
    6. Sürücü, Oktay, 2016. "Welfare improving discrimination based on cognitive limitations," Research in Economics, Elsevier, vol. 70(4), pages 608-622.
    7. Bergemann, Dirk & Yeh, Edmund & Zhang, Jinkun, 2021. "Nonlinear pricing with finite information," Games and Economic Behavior, Elsevier, vol. 130(C), pages 62-84.
    8. Yossi Spiegel & Simon Wilkie, 2000. "Optimal Multiproduct Nonlinear Pricing with Correlated Consumer Types," Discussion Papers 1299, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    9. Kelvin Shuangjian Zhang, 2017. "Existence in Multidimensional Screening with General Nonlinear Preferences," Papers 1710.08549, arXiv.org, revised Dec 2018.
    10. Kelvin Shuangjian Zhang, 2019. "Existence in multidimensional screening with general nonlinear preferences," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 67(2), pages 463-485, March.
    11. Seung Han Yoo, 2018. "Membership Mechanisms," Discussion Paper Series 1804, Institute of Economic Research, Korea University.
    12. Robert J. McCann & Kelvin Shuangjian Zhang, 2023. "A duality and free boundary approach to adverse selection," Papers 2301.07660, arXiv.org, revised Nov 2023.
    13. Yao Luo & Isabelle Perrigne & Quang Vuong, 2018. "Structural Analysis of Nonlinear Pricing," Journal of Political Economy, University of Chicago Press, vol. 126(6), pages 2523-2568.
    14. Veiga, André, 2018. "A note on how to sell a network good," International Journal of Industrial Organization, Elsevier, vol. 59(C), pages 114-126.
    15. Bester, Helmut & Strausz, Roland, 2007. "Contracting with imperfect commitment and noisy communication," Journal of Economic Theory, Elsevier, vol. 136(1), pages 236-259, September.
    16. Chen, Bo & Ni, Debing, 2017. "Optimal bundle pricing under correlated valuations," International Journal of Industrial Organization, Elsevier, vol. 52(C), pages 248-281.
    17. Rochet, Jean-Charles & Carlier, Guillaume & Dupuis, Xavier & Thanassoulis, John, 2024. "A General Solution to the Quasi Linear Screening Problem," TSE Working Papers 24-1537, Toulouse School of Economics (TSE).
    18. Pavlov Gregory, 2011. "Optimal Mechanism for Selling Two Goods," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 11(1), pages 1-35, February.
    19. Wong, Kit Pong, 2024. "Optimal nonlinear pricing by a monopoly with smooth ambiguity preferences," International Review of Economics & Finance, Elsevier, vol. 89(PA), pages 594-604.
    20. Kimmo Berg & Harri Ehtamo, 2012. "Continuous learning methods in two-buyer pricing problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 75(3), pages 287-304, June.

    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:inm:oropre:v:58:y:2010:i:4-part-2:p:1079-1089. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.