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

Limited Farsightedness in Priority-Based Matching

Author

Listed:
  • Ata Atay
  • Ana Mauleon
  • Vincent Vannetelbosch

Abstract

We consider priority-based matching problems with limited farsightedness. We show that, once agents are sufficiently farsighted, the matching obtained from the Top Trading Cycles (TTC) algorithm becomes stable: a singleton set consisting of the TTC matching is a horizon-$k$ vNM stable set if the degree of farsightedness is greater than three times the number of agents in the largest cycle of the TTC. On the contrary, the matching obtained from the Deferred Acceptance (DA) algorithm may not belong to any horizon-$k$ vNM stable set for $k$ large enough.

Suggested Citation

  • Ata Atay & Ana Mauleon & Vincent Vannetelbosch, 2022. "Limited Farsightedness in Priority-Based Matching," Papers 2212.07427, arXiv.org.
    • Handle: RePEc:arx:papers:2212.07427
    as

    Download full text from publisher

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

    Other versions of this item:

    References listed on IDEAS

    as
    1. Dogan, Battal & Ehlers, Lars, 2021. "Minimally unstable Pareto improvements over deferred acceptance," Theoretical Economics, Econometric Society, vol. 16(4), November.
    2. Battal Doğan & Lars Ehlers, 2022. "Robust Minimal Instability of the Top Trading Cycles Mechanism," American Economic Journal: Microeconomics, American Economic Association, vol. 14(4), pages 556-582, November.
    3. Herings, P. Jean-Jacques & Mauleon, Ana & Vannetelbosch, Vincent, 2020. "Matching with myopic and farsighted players," Journal of Economic Theory, Elsevier, vol. 190(C).
    4. Yeon-Koo Che & Olivier Tercieux, 2019. "Efficiency and Stability in Large Matching Markets," Journal of Political Economy, University of Chicago Press, vol. 127(5), pages 2301-2342.
    5. Ehlers, Lars, 2014. "Top trading with fixed tie-breaking in markets with indivisible goods," Journal of Economic Theory, Elsevier, vol. 151(C), pages 64-87.
    6. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2022. "School Choice with Farsighted Students," LIDAM Discussion Papers CORE 2022025, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Jean-Jacques HERINGS & Ana MAULEON & Vincent VANNETELBOSCH, 2017. "Stable sets in matching problems with coalitional sovereignty path dominance," LIDAM Reprints CORE 2861, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Rustamdjan Hakimov & Onur Kesten, 2018. "The Equitable Top Trading Cycles Mechanism For School Choice," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 59(4), pages 2219-2258, November.
    9. Atila Abdulkadiroğlu & Yeon-Koo Che & Parag A. Pathak & Alvin E. Roth & Olivier Tercieux, 2020. "Efficiency, Justified Envy, and Incentives in Priority-Based Matching," American Economic Review: Insights, American Economic Association, vol. 2(4), pages 425-442, December.
    10. Chenghong Luo & Ana Mauleon & Vincent Vannetelbosch, 2021. "Network formation with myopic and farsighted players," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(4), pages 1283-1317, June.
    11. Martin Bichler & Alexander Hammerl & Thayer Morrill & Stefan Waldherr, 2021. "How to Assign Scarce Resources Without Money: Designing Information Systems that are Efficient, Truthful, and (Pretty) Fair," Information Systems Research, INFORMS, vol. 32(2), pages 335-355, June.
    12. , & , J. & ,, 2011. "Von Neumann-Morgenstern farsightedly stable sets in two-sided matching," Theoretical Economics, Econometric Society, vol. 6(3), September.
    13. Daniel Granot & Greys Sov{s}i'{c}, 2005. "Formation of Alliances in Internet-Based Supply Exchanges," Management Science, INFORMS, vol. 51(1), pages 92-105, January.
    14. Klaus, Bettina & Klijn, Flip & Walzl, Markus, 2010. "Farsighted house allocation," Journal of Mathematical Economics, Elsevier, vol. 46(5), pages 817-824, September.
    15. Debraj Ray & Rajiv Vohra, 2015. "The Farsighted Stable Set," Econometrica, Econometric Society, vol. 83(3), pages 977-1011, May.
    16. Lars Ehlers, 2008. "Truncation Strategies in Matching Markets," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 327-335, May.
    17. Dutta, Bhaskar & Vohra, Rajiv, 2017. "Rational expectations and farsighted stability," Theoretical Economics, Econometric Society, vol. 12(3), September.
    18. Ehlers, Lars, 2007. "Von Neumann-Morgenstern stable sets in matching problems," Journal of Economic Theory, Elsevier, vol. 134(1), pages 537-547, May.
    19. Kirchsteiger, Georg & Mantovani, Marco & Mauleon, Ana & Vannetelbosch, Vincent, 2016. "Limited farsightedness in network formation," Journal of Economic Behavior & Organization, Elsevier, vol. 128(C), pages 97-120.
    20. Debraj Ray & Rajiv Vohra, 2019. "Maximality in the Farsighted Stable Set," Econometrica, Econometric Society, vol. 87(5), pages 1763-1779, September.
    21. Kesten, Onur, 2006. "On two competing mechanisms for priority-based allocation problems," Journal of Economic Theory, Elsevier, vol. 127(1), pages 155-171, March.
    22. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    23. P. Jean-Jacques Herings & Ana Mauleon & Vincent Vannetelbosch, 2019. "Stability of networks under horizon-K farsightedness," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 68(1), pages 177-201, July.
    24. Kawasaki, Ryo, 2010. "Farsighted stability of the competitive allocations in an exchange economy with indivisible goods," Mathematical Social Sciences, Elsevier, vol. 59(1), pages 46-52, January.
    25. Mahesh Nagarajan & Greys Soši'{c}, 2007. "Stable Farsighted Coalitions in Competitive Markets," Management Science, INFORMS, vol. 53(1), pages 29-45, January.
    26. Rajiv D. Banker & Robert J. Kauffman, 2004. "50th Anniversary Article: The Evolution of Research on Information Systems: A Fiftieth-Year Survey of the Literature in Management Science," Management Science, INFORMS, vol. 50(3), pages 281-298, March.
    27. Onur Kesten, 2010. "School Choice with Consent," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 125(3), pages 1297-1348.
    28. Jean-Jacques Herings, P. & Mauleon, Ana & Vannetelbosch, Vincent, 2017. "Stable sets in matching problems with coalitional sovereignty and path dominance," Journal of Mathematical Economics, Elsevier, vol. 71(C), pages 14-19.
    29. Thayer Morrill, 2015. "Two simple variations of top trading cycles," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 60(1), pages 123-140, September.
    30. Ma, Jinpeng, 1994. "Strategy-Proofness and the Strict Core in a Market with Indivisibilities," International Journal of Game Theory, Springer;Game Theory Society, vol. 23(1), pages 75-83.
    31. Alvin E. Roth, 1982. "The Economics of Matching: Stability and Incentives," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 617-628, November.
    32. Philip J. Reny, 2022. "Efficient Matching in the School Choice Problem," American Economic Review, American Economic Association, vol. 112(6), pages 2025-2043, June.
    33. Roth, Alvin E. & Postlewaite, Andrew, 1977. "Weak versus strong domination in a market with indivisible goods," Journal of Mathematical Economics, Elsevier, vol. 4(2), pages 131-137, August.
    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. Ata Atay & Sylvain Funck & Ana Mauleon & Vincent Vannetelbosch, 2023. "Matching markets with farsighted couples," UB School of Economics Working Papers 2023/445, University of 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. Afacan, Mustafa Oğuz & Hu, Gaoji & Li, Jiangtao, 2024. "Housing markets since Shapley and Scarf," Journal of Mathematical Economics, Elsevier, vol. 111(C).
    2. Mauleon, Ana & Sempere-Monerris, Jose J. & Vannetelbosch, Vincent, 2023. "R&D network formation with myopic and farsighted firms," Journal of Economic Behavior & Organization, Elsevier, vol. 208(C), pages 203-229.
    3. Pierre Callataÿ & Ana Mauleon & Vincent Vannetelbosch, 2024. "Minimal farsighted instability," International Journal of Game Theory, Springer;Game Theory Society, vol. 53(2), pages 493-523, June.
    4. Pierre de Callataÿ & Ana Mauleon & Vincent Vannetelbosch, 2023. "Myopic-farsighted absorbing networks," Theory and Decision, Springer, vol. 94(3), pages 405-422, April.
    5. de Callatay, Pierre & Mauleon, Ana & Vannetelbosch, Vincent, 2021. "Minimally Farsighted Unstable Networks," LIDAM Discussion Papers CORE 2021012, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Herings, P. Jean-Jacques & Mauleon, Ana & Vannetelbosch, Vincent, 2020. "Matching with myopic and farsighted players," Journal of Economic Theory, Elsevier, vol. 190(C).
    7. Luo, Chenghong & Mauleon, Ana & Vannetelbosch, Vincent, 2024. "Destabilizing segregation in friendship networks with farsighted agents," Journal of Economic Behavior & Organization, Elsevier, vol. 221(C), pages 1-16.
    8. Estelle Cantillon & Li Chen & Juan Sebastian Pereyra Barreiro, 2022. "Respecting priorities versus respecting preferences in school choice: When is there a trade-off ?," Working Papers ECARES 2022-39, ULB -- Universite Libre de Bruxelles.
    9. Kesten, Onur & Kurino, Morimitsu, 2019. "Strategy-proof improvements upon deferred acceptance: A maximal domain for possibility," Games and Economic Behavior, Elsevier, vol. 117(C), pages 120-143.
    10. Abdulkadiroglu, Atila & Andersson, Tommy, 2022. "School Choice," Working Papers 2022:4, Lund University, Department of Economics.
    11. Luo, Chenghong & Mauleon, Ana & Vannetelbosch, Vincent, 2022. "Friendship networks with farsighted agents," LIDAM Discussion Papers CORE 2022021, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. Rodríguez-Álvarez, Carmelo & Romero-Medina, Antonio, 2024. "School choice with transferable student characteristics," Games and Economic Behavior, Elsevier, vol. 143(C), pages 103-124.
    13. Chenghong Luo & Ana Mauleon & Vincent Vannetelbosch, 2021. "Network formation with myopic and farsighted players," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(4), pages 1283-1317, June.
    14. P. Jean-Jacques Herings & Ana Mauleon & Vincent Vannetelbosch, 2023. "Social Rationalizability with Mediation," Dynamic Games and Applications, Springer, vol. 13(2), pages 440-461, June.
    15. Kimya, Mert, 2021. "Coalition Formation Under Dominance Invariance," Working Papers 202106, University of Sydney, School of Economics.
    16. Morrill, Thayer & Roth, Alvin E., 2024. "Top trading cycles," Journal of Mathematical Economics, Elsevier, vol. 112(C).
    17. Pierre de Callataÿ & Ana Mauleon & Vincent Vannetelbosch, 2024. "Local farsightedness in network formation," International Journal of Economic Theory, The International Society for Economic Theory, vol. 20(2), pages 199-226, June.
    18. Kimya, Mert, 2021. "Coalition Formation Under Dominance Invariance," Working Papers 2021-06, University of Sydney, School of Economics.
    19. Mert Kimya, 2023. "Coalition Formation Under Dominance Invariance," Dynamic Games and Applications, Springer, vol. 13(2), pages 480-496, June.
    20. Bloch, Francis & van den Nouweland, Anne, 2020. "Farsighted stability with heterogeneous expectations," Games and Economic Behavior, Elsevier, vol. 121(C), pages 32-54.

    More about this item

    JEL classification:

    • C70 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - General
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D47 - Microeconomics - - Market Structure, Pricing, and Design - - - Market Design
    • D61 - Microeconomics - - Welfare Economics - - - Allocative Efficiency; Cost-Benefit Analysis

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