IDEAS home Printed from https://ideas.repec.org/a/eee/mateco/v46y2010i5p937-949.html
   My bibliography  Save this article

The Blocking Lemma for a many-to-one matching model

Author

Listed:
  • Martínez, Ruth
  • Massó, Jordi
  • Neme, Alejandro
  • Oviedo, Jorge

Abstract

The Blocking Lemma identifies a particular blocking pair for each non-stable and individually rational matching that is preferred by some agents of one side of the market to their optimal stable matching. Its interest lies in the fact that it has been an instrumental result to prove key results on matching. For instance, the fact that in the college admissions problem the workers-optimal stable mechanism is group strategy-proof for the workers and the strong stability theorem in the marriage model follow directly from the Blocking Lemma. However, it is known that the Blocking Lemma and its consequences do not hold in the general many-to-one matching model in which firms have substitutable preference relations. We show that the Blocking Lemma holds for the many-to-one matching model in which firms' preference relations are, in addition to substitutable, quota q-separable. We also show that the Blocking Lemma holds on a subset of substitutable preference profiles if and only if the workers-optimal stable mechanism is group strategy-proof for the workers on this subset of profiles.

Suggested Citation

  • Martínez, Ruth & Massó, Jordi & Neme, Alejandro & Oviedo, Jorge, 2010. "The Blocking Lemma for a many-to-one matching model," Journal of Mathematical Economics, Elsevier, vol. 46(5), pages 937-949, September.
    • Handle: RePEc:eee:mateco:v:46:y:2010:i:5:p:937-949
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0304-4068(10)00085-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Lars Ehlers & Bettina Klaus, 2003. "Coalitional strategy-proof and resource-monotonic solutions for multiple assignment problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 21(2), pages 265-280, October.
    2. Gabrielle Demange & David Gale & Marilda Sotomayor, 1987. "A Further Note on the Stable Matching Problem," Post-Print halshs-00670980, HAL.
    3. Dutta, Bhaskar & Masso, Jordi, 1997. "Stability of Matchings When Individuals Have Preferences over Colleagues," Journal of Economic Theory, Elsevier, vol. 75(2), pages 464-475, August.
    4. Ruth Martínez & Jordi Massó & Alejdanro Neme & Jorge Oviedo, 2004. "On group strategy-proof mechanisms for a many-to-one matching model," International Journal of Game Theory, Springer;Game Theory Society, vol. 33(1), pages 115-128, January.
    5. Barbera, Salvador & Sonnenschein, Hugo & Zhou, Lin, 1991. "Voting by Committees," Econometrica, Econometric Society, vol. 59(3), pages 595-609, May.
    6. Tayfun Sönmez, 1994. "Strategy-proofness in many-to-one matching problems," Review of Economic Design, Springer;Society for Economic Design, vol. 1(1), pages 365-380, December.
    7. Barbera, Salvador & Sonnenschein, Hugo & Zhou, Lin, 1991. "Voting by Committees," Econometrica, Econometric Society, vol. 59(3), pages 595-609, May.
    8. Roth, Alvin E, 1984. "Stability and Polarization of Interests in Job Matching," Econometrica, Econometric Society, vol. 52(1), pages 47-57, January.
    9. Roth, Alvin E., 1985. "The college admissions problem is not equivalent to the marriage problem," Journal of Economic Theory, Elsevier, vol. 36(2), pages 277-288, August.
    10. 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.
    11. Ahmet Alkan, 2001. "original papers : On preferences over subsets and the lattice structure of stable matchings," Review of Economic Design, Springer;Society for Economic Design, vol. 6(1), pages 99-111.
    12. Charles Blair, 1988. "The Lattice Structure of the Set of Stable Matchings with Multiple Partners," Mathematics of Operations Research, INFORMS, vol. 13(4), pages 619-628, November.
    13. Roth, Alvin E & Xing, Xiaolin, 1994. "Jumping the Gun: Imperfections and Institutions Related to the Timing of Market Transactions," American Economic Review, American Economic Association, vol. 84(4), pages 992-1044, September.
    14. Martinez, Ruth & Masso, Jordi & Neme, Alejandro & Oviedo, Jorge, 2000. "Single Agents and the Set of Many-to-One Stable Matchings," Journal of Economic Theory, Elsevier, vol. 91(1), pages 91-105, March.
    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. Jiao, Zhenhua & Tian, Guoqiang & Chen, Songqing & Yang, Fei, 2016. "The blocking lemma and group incentive compatibility for matching with contracts," Mathematical Social Sciences, Elsevier, vol. 82(C), pages 65-71.
    2. José Alcalde & Antonio Romero-Medina, 2017. "Fair student placement," Theory and Decision, Springer, vol. 83(2), pages 293-307, August.
    3. Fisher, James C.D., 2020. "Existence of stable allocations in matching markets with infinite contracts: A topological approach," Journal of Mathematical Economics, Elsevier, vol. 91(C), pages 136-140.
    4. Hatfield, John William & Kojima, Fuhito, 2009. "Group incentive compatibility for matching with contracts," Games and Economic Behavior, Elsevier, vol. 67(2), pages 745-749, November.
    5. 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.
    6. Kitahara, Minoru & Okumura, Yasunori, 2019. "On the number of employed in the matching model," Journal of Mathematical Economics, Elsevier, vol. 83(C), pages 63-69.

    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. 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.
    2. Jiao, Zhenhua & Tian, Guoqiang & Chen, Songqing & Yang, Fei, 2016. "The blocking lemma and group incentive compatibility for matching with contracts," Mathematical Social Sciences, Elsevier, vol. 82(C), pages 65-71.
    3. , & ,, 2006. "A theory of stability in many-to-many matching markets," Theoretical Economics, Econometric Society, vol. 1(2), pages 233-273, June.
    4. Ruth Martínez & Jordi Massó & Alejdanro Neme & Jorge Oviedo, 2004. "On group strategy-proof mechanisms for a many-to-one matching model," International Journal of Game Theory, Springer;Game Theory Society, vol. 33(1), pages 115-128, January.
    5. 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.
    6. 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.
    7. Barbera, S. & Bossert, W. & Pattanaik, P.K., 2001. "Ranking Sets of Objects," Cahiers de recherche 2001-02, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    8. John William Hatfield & Paul R. Milgrom, 2005. "Matching with Contracts," American Economic Review, American Economic Association, vol. 95(4), pages 913-935, September.
    9. 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.
    10. Hideo Konishi & M. Utku Ünver, 2003. "Credible Group Stability in Multi-Partner Matching Problems," Working Papers 2003.115, Fondazione Eni Enrico Mattei.
    11. Kadam, Sangram V. & Kotowski, Maciej H., 2018. "Time horizons, lattice structures, and welfare in multi-period matching markets," Games and Economic Behavior, Elsevier, vol. 112(C), pages 1-20.
    12. 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.
    13. Cantala, David, 2004. "Restabilizing matching markets at senior level," Games and Economic Behavior, Elsevier, vol. 48(1), pages 1-17, July.
    14. Ayşe Yazıcı, 2017. "Probabilistic stable rules and Nash equilibrium in two-sided matching problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(1), pages 103-124, March.
    15. Yuichiro Kamada & Fuhito Kojima, 2020. "Accommodating various policy goals in matching with constraints," The Japanese Economic Review, Springer, vol. 71(1), pages 101-133, January.
    16. Hatfield, John William & Kojima, Fuhito, 2010. "Substitutes and stability for matching with contracts," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1704-1723, September.
    17. 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.
    18. Bonifacio, Agustín G. & Guiñazú, Nadia & Juarez, Noelia & Neme, Pablo & Oviedo, Jorge, 2022. "The lattice of worker-quasi-stable matchings," Games and Economic Behavior, Elsevier, vol. 135(C), pages 188-200.
    19. Mauleon, Ana & Roehl, Nils & Vannetelbosch, Vincent, 2018. "Constitutions and groups," Games and Economic Behavior, Elsevier, vol. 107(C), pages 135-152.

    More about this item

    Keywords

    Matching Stability Blocking Lemma;

    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:mateco:v:46:y:2010:i:5:p:937-949. 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/jmateco .

    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.