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

On the complexity of dynamic mechanism design

Author

Listed:
  • Papadimitriou, Christos
  • Pierrakos, George
  • Psomas, Alexandros
  • Rubinstein, Aviad

Abstract

We introduce a simple dynamic mechanism design problem in which the designer offers two items in two consecutive stages to a single buyer. The buyer's joint distribution of valuations for the two items is known, and the buyer knows the valuation for the current item, but not for the one in the future. The designer seeks to maximize expected revenue, and the mechanism must be deterministic, truthful, and ex-post individually rational. We show that finding the optimum deterministic mechanism in this situation — arguably one of the simplest meaningful dynamic mechanism design problems imaginable — is NP-hard. We also prove several positive results, including a polynomial-time linear programming-based algorithm for the revenue optimal randomized mechanism (even for many buyers and many stages). We prove strong separations in revenue between non-adaptive, adaptive, and randomized mechanisms, even when the valuations in the two stages are independent.

Suggested Citation

  • Papadimitriou, Christos & Pierrakos, George & Psomas, Alexandros & Rubinstein, Aviad, 2022. "On the complexity of dynamic mechanism design," Games and Economic Behavior, Elsevier, vol. 134(C), pages 399-427.
    • Handle: RePEc:eee:gamebe:v:134:y:2022:i:c:p:399-427
    DOI: 10.1016/j.geb.2022.01.024
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825622000306
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2022.01.024?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. Pascal Courty & Li Hao, 2000. "Sequential Screening," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 67(4), pages 697-717.
    2. Stephen E. Spear & Sanjay Srivastava, 1987. "On Repeated Moral Hazard with Discounting," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 54(4), pages 599-617.
    3. Baron, David P. & Besanko, David, 1984. "Regulation and information in a continuing relationship," Information Economics and Policy, Elsevier, vol. 1(3), pages 267-302.
    4. Krähmer, Daniel & Strausz, Roland, 2016. "Optimality of sequential screening with multiple units and ex post participation constraints," Economics Letters, Elsevier, vol. 142(C), pages 64-68.
    5. Dirk Bergemann & Juuso V‰lim‰ki, 2010. "The Dynamic Pivot Mechanism," Econometrica, Econometric Society, vol. 78(2), pages 771-789, March.
    6. Alessandro Pavan & Ilya Segal & Juuso Toikka, 2008. "Dynamic Mechanism Design: Incentive Compatibility, Profit Maximization and Information Disclosure," Carlo Alberto Notebooks 84, Collegio Carlo Alberto.
    7. Vahab Mirrokni & Renato Paes Leme & Pingzhong Tang & Song Zuo, 2020. "Non‐Clairvoyant Dynamic Mechanism Design," Econometrica, Econometric Society, vol. 88(5), pages 1939-1963, September.
    8. Takuo Sugaya & Alexander Wolitzky, 2021. "The Revelation Principle in Multistage Games [Information Feedback in a Dynamic Tournament]," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 88(3), pages 1503-1540.
    9. Fernandes, Ana & Phelan, Christopher, 2000. "A Recursive Formulation for Repeated Agency with History Dependence," Journal of Economic Theory, Elsevier, vol. 91(2), pages 223-247, April.
    10. Thomas, Jonathan & Worrall, Tim, 1990. "Income fluctuation and asymmetric information: An example of a repeated principal-agent problem," Journal of Economic Theory, Elsevier, vol. 51(2), pages 367-390, August.
    11. Dirk Bergemann & Juuso Välimäki, 2019. "Dynamic Mechanism Design: An Introduction," Journal of Economic Literature, American Economic Association, vol. 57(2), pages 235-274, June.
    12. Daniel Krähmer & Roland Strausz, 2011. "Optimal Procurement Contracts with Pre-Project Planning," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 78(3), pages 1015-1041.
    13. Alessandro Pavan & Ilya Segal & Juuso Toikka, 2010. "Infinite-Horizon Mechanism Design," Discussion Papers 1503, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    14. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    15. Alessandro Pavan & Ilya Segal & Juuso Toikka, 2014. "Dynamic Mechanism Design: A Myersonian Approach," Econometrica, Econometric Society, vol. 82(2), pages 601-653, March.
    16. Myerson, Roger B, 1986. "Multistage Games with Communication," Econometrica, Econometric Society, vol. 54(2), pages 323-358, March.
    17. Alessandro Pavan & Ilya Segal & Juuso Toikka, 2010. "Infinite-Horizon Mechanism Design: the Independent-Shock Approach," Discussion Papers 1492, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    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. Boaz Zik, 2023. "Efficient sequential screening with informational externalities," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 75(2), pages 567-590, February.
    2. Arve, Malin & Zwart, Gijsbert, 2023. "Optimal procurement and investment in new technologies under uncertainty," Journal of Economic Dynamics and Control, Elsevier, vol. 147(C).
    3. Golosov, M. & Tsyvinski, A. & Werquin, N., 2016. "Recursive Contracts and Endogenously Incomplete Markets," Handbook of Macroeconomics, in: J. B. Taylor & Harald Uhlig (ed.), Handbook of Macroeconomics, edition 1, volume 2, chapter 0, pages 725-841, Elsevier.
    4. Liu, Bin & Liu, Dongri & Lu, Jingfeng, 2020. "Shifting supports in Esö and Szentes (2007)," Economics Letters, Elsevier, vol. 193(C).
    5. Krähmer, Daniel & Strausz, Roland, 2017. "Sequential versus static screening: An equivalence result," Games and Economic Behavior, Elsevier, vol. 106(C), pages 317-328.
    6. Vahab Mirrokni & Renato Paes Leme & Pingzhong Tang & Song Zuo, 2020. "Non‐Clairvoyant Dynamic Mechanism Design," Econometrica, Econometric Society, vol. 88(5), pages 1939-1963, September.
    7. Bergemann, Dirk & Pavan, Alessandro, 2015. "Introduction to Symposium on Dynamic Contracts and Mechanism Design," Journal of Economic Theory, Elsevier, vol. 159(PB), pages 679-701.
    8. von Wangenheim, Jonas, 2017. "Consumer-Optimal Information Design," Rationality and Competition Discussion Paper Series 53, CRC TRR 190 Rationality and Competition.
    9. Tao Zhang & Quanyan Zhu, 2019. "On Incentive Compatibility in Dynamic Mechanism Design With Exit Option in a Markovian Environment," Papers 1909.13720, arXiv.org, revised May 2021.
    10. Rohit Lamba & Ilia Krasikov, 2017. "A Theory of Dynamic Contracting with Financial Constraints," 2017 Meeting Papers 1544, Society for Economic Dynamics.
    11. Tao Zhang & Quanyan Zhu, 2022. "On Incentive Compatibility in Dynamic Mechanism Design With Exit Option in a Markovian Environment," Dynamic Games and Applications, Springer, vol. 12(2), pages 701-745, June.
    12. Chifeng Dai, 2021. "Optimal sequential contract with a risk‐averse supplier," Canadian Journal of Economics/Revue canadienne d'économique, John Wiley & Sons, vol. 54(1), pages 92-125, February.
    13. Ying-Ju Chen, 2011. "Optimal Selling Scheme for Heterogeneous Consumers with Uncertain Valuations," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 695-720, November.
    14. Emil Temnyalov, 2019. "Points mechanisms and rewards programs," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 28(3), pages 436-457, June.
    15. Krähmer, Daniel & Strausz, Roland, 2015. "Ex post information rents in sequential screening," Games and Economic Behavior, Elsevier, vol. 90(C), pages 257-273.
    16. Rohit Lamba, 2022. "Efficiency with(out) intermediation in repeated bilateral trade," Papers 2202.04201, arXiv.org.
    17. Alireza Fallah & Michael I. Jordan & Annie Ulichney, 2024. "Fair Allocation in Dynamic Mechanism Design," Papers 2406.00147, arXiv.org, revised Oct 2024.
    18. Sham M. Kakade & Ilan Lobel & Hamid Nazerzadeh, 2013. "Optimal Dynamic Mechanism Design and the Virtual-Pivot Mechanism," Operations Research, INFORMS, vol. 61(4), pages 837-854, August.
    19. Akan, Mustafa & Ata, Barış & Dana, James D., 2015. "Revenue management by sequential screening," Journal of Economic Theory, Elsevier, vol. 159(PB), pages 728-774.
    20. Huiyi Guo & Wei He & Bin Liu, 2022. "Learning by Consuming: Optimal Pricing with Endogenous Information Provision," Papers 2209.01453, arXiv.org.

    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:134:y:2022:i:c:p:399-427. 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.