IDEAS home Printed from https://ideas.repec.org/a/eee/matsoc/v66y2013i1p91-94.html
   My bibliography  Save this article

Testing substitutability of weak preferences

Author

Listed:
  • Aziz, Haris
  • Brill, Markus
  • Harrenstein, Paul

Abstract

In various models of matching markets, substitutable preferences constitute the largest domain for which stable matchings are guaranteed to exist. Recently, Hatfield et al. (2012) have proposed an efficient algorithm to test substitutability of strict preferences. In this note we show how the algorithm by Hatfield et al. can be adapted in such a way that it can test substitutability of weak preferences as well. When restricted to the domain of strict preferences, our algorithm is faster than Hatfield et al.’s original algorithm by a linear factor.

Suggested Citation

  • Aziz, Haris & Brill, Markus & Harrenstein, Paul, 2013. "Testing substitutability of weak preferences," Mathematical Social Sciences, Elsevier, vol. 66(1), pages 91-94.
    • Handle: RePEc:eee:matsoc:v:66:y:2013:i:1:p:91-94
    DOI: 10.1016/j.mathsocsci.2013.01.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0165489613000152
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.mathsocsci.2013.01.007?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. Hatfield, John William & Immorlica, Nicole & Kominers, Scott Duke, 2012. "Testing substitutability," Games and Economic Behavior, Elsevier, vol. 75(2), pages 639-645.
    2. Orhan Aygün & Tayfun Sönmez, 2012. "The Importance of Irrelevance of Rejected Contracts in Matching under Weakened Substitutes Conditions," Boston College Working Papers in Economics 805, Boston College Department of Economics.
    3. Roth, Alvin E, 1984. "Stability and Polarization of Interests in Job Matching," Econometrica, Econometric Society, vol. 52(1), pages 47-57, January.
    4. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.
    5. Ballester, Coralio, 2004. "NP-completeness in hedonic games," Games and Economic Behavior, Elsevier, vol. 49(1), pages 1-30, October.
    6. Sotomayor, Marilda, 1999. "Three remarks on the many-to-many stable matching problem," Mathematical Social Sciences, Elsevier, vol. 38(1), pages 55-70, July.
    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. Orhan Aygün & Tayfun Sönmez, 2012. "Matching with Contracts: The Critical Role of Irrelevance of Rejected Contracts," Boston College Working Papers in Economics 804, Boston College Department of Economics.
    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. Cosmina Croitoru & Kurt Mehlhorn, 2018. "On testing substitutability," Papers 1805.07642, arXiv.org.

    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. Hatfield, John William & Kominers, Scott Duke, 2017. "Contract design and stability in many-to-many matching," Games and Economic Behavior, Elsevier, vol. 101(C), pages 78-97.
    2. John William Hatfield & Scott Duke Kominers, 2012. "Matching in Networks with Bilateral Contracts," American Economic Journal: Microeconomics, American Economic Association, vol. 4(1), pages 176-208, February.
    3. Paula Jaramillo & Çaǧatay Kayı & Flip Klijn, 2014. "On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(4), pages 793-811, April.
    4. Klijn, Flip & Yazıcı, Ayşe, 2014. "A many-to-many ‘rural hospital theorem’," Journal of Mathematical Economics, Elsevier, vol. 54(C), pages 63-73.
    5. Mauleon, Ana & Roehl, Nils & Vannetelbosch, Vincent, 2018. "Constitutions and groups," Games and Economic Behavior, Elsevier, vol. 107(C), pages 135-152.
    6. Kong, Qianqian & Peters, Hans, 2023. "Power indices for networks, with applications to matching markets," European Journal of Operational Research, Elsevier, vol. 306(1), pages 448-456.
    7. Danilov, V., 2021. "Stable systems of schedule contracts," Journal of the New Economic Association, New Economic Association, vol. 51(3), pages 12-29.
    8. Committee, Nobel Prize, 2012. "Alvin E. Roth and Lloyd S. Shapley: Stable allocations and the practice of market design," Nobel Prize in Economics documents 2012-1, Nobel Prize Committee.
    9. Hirata, Daisuke & Kasuya, Yusuke, 2017. "On stable and strategy-proof rules in matching markets with contracts," Journal of Economic Theory, Elsevier, vol. 168(C), pages 27-43.
    10. Tayfun Sönmez, 2013. "Bidding for Army Career Specialties: Improving the ROTC Branching Mechanism," Journal of Political Economy, University of Chicago Press, vol. 121(1), pages 186-219.
    11. Hideo Konishi & M. Utku Ünver, 2003. "Credible Group Stability in Multi-Partner Matching Problems," Working Papers 2003.115, Fondazione Eni Enrico Mattei.
    12. Erdil, Aytek & Kumano, Taro, 2019. "Efficiency and stability under substitutable priorities with ties," Journal of Economic Theory, Elsevier, vol. 184(C).
    13. Klaus, Bettina & Walzl, Markus, 2009. "Stable many-to-many matchings with contracts," Journal of Mathematical Economics, Elsevier, vol. 45(7-8), pages 422-434, July.
    14. Tayfun Sönmez & Tobias B. Switzer, 2013. "Matching With (Branch‐of‐Choice) Contracts at the United States Military Academy," Econometrica, Econometric Society, vol. 81(2), pages 451-488, March.
    15. , & ,, 2006. "A theory of stability in many-to-many matching markets," Theoretical Economics, Econometric Society, vol. 1(2), pages 233-273, June.
    16. Pérez-Castrillo, David & Sotomayor, Marilda, 2019. "Comparative statics in the multiple-partners assignment game," Games and Economic Behavior, Elsevier, vol. 114(C), pages 177-192.
    17. Konishi, Hideo & Unver, M. Utku, 2006. "Credible group stability in many-to-many matching problems," Journal of Economic Theory, Elsevier, vol. 129(1), pages 57-80, July.
    18. Jiao, Zhenhua & Tian, Guoqiang, 2017. "The Blocking Lemma and strategy-proofness in many-to-many matchings," Games and Economic Behavior, Elsevier, vol. 102(C), pages 44-55.
    19. Daniel Lehmann, 2019. "Revealed Preferences for Matching with Contracts," Papers 1908.08823, arXiv.org, revised Mar 2020.
    20. Ehlers, Lars & Hafalir, Isa E. & Yenmez, M. Bumin & Yildirim, Muhammed A., 2014. "School choice with controlled choice constraints: Hard bounds versus soft bounds," Journal of Economic Theory, Elsevier, vol. 153(C), pages 648-683.

    More about this item

    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:matsoc:v:66:y:2013:i:1:p:91-94. 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/505565 .

    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.