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

Monotone comparative statics for submodular functions, with an application to aggregated deferred acceptance

Author

Listed:
  • Alfred Galichon
  • Yu-Wei Hsieh
  • Maxime Sylvestre

Abstract

We propose monotone comparative statics results for maximizers of submodular functions, as opposed to maximizers of supermodular functions as in the classical theory put forth by Veinott, Topkis, Milgrom, and Shannon among others. We introduce matrons, a natural structure that is dual to sublattices that generalizes existing structures such as matroids and polymatroids in combinatorial optimization and M-sets in discrete convex analysis. Our monotone comparative statics result is based on a natural order on matrons, which is dual in some sense to Veinott's strong set order on sublattices. As an application, we propose a deferred acceptance algorithm that operates in the case of divisible goods, and we study its convergence properties.

Suggested Citation

  • Alfred Galichon & Yu-Wei Hsieh & Maxime Sylvestre, 2023. "Monotone comparative statics for submodular functions, with an application to aggregated deferred acceptance," Papers 2304.12171, arXiv.org.
    • Handle: RePEc:arx:papers:2304.12171
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. John K.-H. Quah & Bruno Strulovici, 2009. "Comparative Statics, Informativeness, and the Interval Dominance Order," Econometrica, Econometric Society, vol. 77(6), pages 1949-1992, November.
    2. Alkan, Ahmet & Gale, David, 2003. "Stable schedule matching under revealed preference," Journal of Economic Theory, Elsevier, vol. 112(2), pages 289-306, October.
    3. Federico Echenique, 2002. "Comparative Statics by Adaptive Dynamics and the Correspondence Principle," Econometrica, Econometric Society, vol. 70(2), pages 833-844, March.
    4. Paes Leme, Renato, 2017. "Gross substitutability: An algorithmic survey," Games and Economic Behavior, Elsevier, vol. 106(C), pages 294-316.
    5. Odran Bonnet & Alfred Galichon & Yu-Wei Hsieh & Keith O’Hara & Matt Shum, 2022. "Yogurts Choose Consumers? Estimation of Random-Utility Models via Two-Sided Matching [Unobserved Product Differentiation in Discrete-Choice Models: Estimating Price Elasticities and Welfare Effects," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 89(6), pages 3085-3114.
    6. Milgrom, Paul & Shannon, Chris, 1994. "Monotone Comparative Statics," Econometrica, Econometric Society, vol. 62(1), pages 157-180, January.
    7. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    8. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    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. Kazuo Murota, 2016. "Discrete convex analysis: A tool for economics and game theory," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 1(1), pages 151-273, December.
    2. Natalia Lazzati, 2013. "Comparison of equilibrium actions and payoffs across players in games of strategic complements," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 54(3), pages 777-788, November.
    3. Hector Chade & Lones Smith, 2006. "Simultaneous Search," Econometrica, Econometric Society, vol. 74(5), pages 1293-1307, September.
    4. Saurabh Amin & Patrick Jaillet & Haripriya Pulyassary & Manxi Wu, 2023. "Market Design for Dynamic Pricing and Pooling in Capacitated Networks," Papers 2307.03994, arXiv.org, revised Nov 2023.
    5. Roy, Sunanda & Sabarwal, Tarun, 2012. "Characterizing stability properties in games with strategic substitutes," Games and Economic Behavior, Elsevier, vol. 75(1), pages 337-353.
    6. repec:kan:wpaper:201412 is not listed on IDEAS
    7. Finn Christensen, 2019. "Comparative statics and heterogeneity," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 67(3), pages 665-702, April.
    8. Ozan Candogan & Markos Epitropou & Rakesh V. Vohra, 2021. "Competitive Equilibrium and Trading Networks: A Network Flow Approach," Operations Research, INFORMS, vol. 69(1), pages 114-147, January.
    9. Satoru Fujishige & Akihisa Tamura, 2007. "A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis," Mathematics of Operations Research, INFORMS, vol. 32(1), pages 136-155, February.
    10. John William Hatfield & Paul R. Milgrom, 2005. "Matching with Contracts," American Economic Review, American Economic Association, vol. 95(4), pages 913-935, September.
    11. Amir, Rabah & De Castro, Luciano, 2017. "Nash equilibrium in games with quasi-monotonic best-responses," Journal of Economic Theory, Elsevier, vol. 172(C), pages 220-246.
    12. Anne-Christine Barthel & Tarun Sabarwal, 2018. "Directional monotone comparative statics," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 66(3), pages 557-591, October.
    13. Andrew J. Monaco & Tarun Sabarwal, 2016. "Games with strategic complements and substitutes," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 62(1), pages 65-91, June.
    14. Bar Light, 2021. "Stochastic Comparative Statics in Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 797-810, May.
    15. repec:kan:wpaper:201502 is not listed on IDEAS
    16. Roy, Souvik & Kumar, Ujjwal, 2021. "Local incentive compatibility in non-convex type-spaces," MPRA Paper 110872, University Library of Munich, Germany.
    17. Eric Balkanski & Renato Paes Leme, 2020. "On the Construction of Substitutes," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 272-291, February.
    18. John W. Hatfield & Paul Milgrom, 2005. "Auctions, Matching and the Law of Aggregate Demand," Levine's Bibliography 122247000000000780, UCLA Department of Economics.
    19. Yokote, Koji, 2023. "A critical comparison between the gross substitutes and complements conditions," Economics Letters, Elsevier, vol. 226(C).
    20. Charlene Cosandier & Filomena Garcia & Malgorzata Knauff, 2018. "Price competition with differentiated goods and incomplete product awareness," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 66(3), pages 681-705, October.
    21. Andrew Monaco & Tarun Sabarwal, 2012. "Monotone Comparative Statics in Games with both Strategic Complements and Strategic Substitutes," WORKING PAPERS SERIES IN THEORETICAL AND APPLIED ECONOMICS 201236, University of Kansas, Department of Economics, revised Aug 2012.
    22. Bar Light, 2019. "Stochastic Comparative Statics in Markov Decision Processes," Papers 1904.05481, arXiv.org, revised Jan 2020.

    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:2304.12171. 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.