IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2609.20032.html

A polyhedral characterization of worker-quasi-stable matchings

Author

Listed:
  • Nadia Gui~naz'u
  • Noelia Juarez
  • Paola Manasero
  • Pablo Neme
  • Jorge Oviedo

Abstract

We provide the first polyhedral characterization of worker-quasi-stable matchings in the classical one-to-one matching model. By modifying the classical stability constraints, we introduce a convex polytope and prove that it is integral. Consequently, its extreme points coincide exactly with the incidence vectors of worker-quasi-stable matchings, demonstrating that worker-quasi-stability preserves the geometric tractability of standard stability.

Suggested Citation

  • Nadia Gui~naz'u & Noelia Juarez & Paola Manasero & Pablo Neme & Jorge Oviedo, 2026. "A polyhedral characterization of worker-quasi-stable matchings," Papers 2609.20032, arXiv.org, revised Oct 2026.
  • Handle: RePEc:arx:papers:2609.20032
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Yi-You Yang, 2025. "On the existence of stable matchings with contracts," Theory and Decision, Springer, vol. 98(3), pages 367-372, May.
    2. Sotomayor, Marilda, 1996. "A Non-constructive Elementary Proof of the Existence of Stable Marriages," Games and Economic Behavior, Elsevier, vol. 13(1), pages 135-137, March.
    3. Nadia Guiñazú & Noelia Juarez & Pablo Neme & Jorge Oviedo, 2025. "Quasi-stability notions in two-sided matching models," International Journal of Game Theory, Springer;Game Theory Society, vol. 54(2), pages 1-23, December.
    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. V. I. Danilov, 2025. "On the existence of stable contract systems," Papers 2505.12721, arXiv.org.
    2. Yi-You Yang, 2026. "Doctor-Optimal Stability in Unitary Many-to-Many Markets," Papers 2607.10756, arXiv.org.
    3. Dimitrov, Dinko & Lazarova, Emiliya A., 2008. "Coalitional Matchings," Coalition Theory Network Working Papers 37523, Fondazione Eni Enrico Mattei (FEEM).
    4. Vladimir Danilov, 2025. "A short way to the stability," Papers 2511.16104, arXiv.org.
    5. 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.
    6. Marilda Sotomayor, 2016. "On Simple Outcomes and Cores," Working Papers, Department of Economics 2016_05, University of São Paulo (FEA-USP).
    7. Alcalde, Jose & Revilla, Pablo, 2004. "Researching with whom? Stability and manipulation," Journal of Mathematical Economics, Elsevier, vol. 40(8), pages 869-887, December.
    8. David Pérez-Castrillo & Marilda Sotomayor, 2023. "Constrained-optimal tradewise-stable outcomes in the one-sided assignment game: a solution concept weaker than the core," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(3), pages 963-994, October.
    9. Wu, Qingyun & Roth, Alvin E., 2018. "The lattice of envy-free matchings," Games and Economic Behavior, Elsevier, vol. 109(C), pages 201-211.
    10. R. Pablo Arribillaga & Beatriz Millan & Eliana Pepa Risma, 2025. "Obvious Manipulations, Stability, and Efficiency in Matching Markets with No, Unitary, and Multiple Contracts: Three Different Results," Working Papers 363, Red Nacional de Investigadores en Economía (RedNIE).
    11. 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.
    12. Jaramillo, Paula & Kayı, Çaǧatay & Klijn, Flip, 2013. "Equilibria under deferred acceptance: Dropping strategies, filled positions, and welfare," Games and Economic Behavior, Elsevier, vol. 82(C), pages 693-701.
    13. Dimitrov, Dinko & Lazarova, Emiliya, 2011. "Two-sided coalitional matchings," Mathematical Social Sciences, Elsevier, vol. 62(1), pages 46-54, July.
    14. Sotomayor, Marilda, 2007. "Core structure and comparative statics in a hybrid matching market," Games and Economic Behavior, Elsevier, vol. 60(2), pages 357-380, August.
    15. , & , J. & ,, 2011. "Von Neumann-Morgenstern farsightedly stable sets in two-sided matching," Theoretical Economics, Econometric Society, vol. 6(3), September.
    16. Cantala, David, 2004. "Restabilizing matching markets at senior level," Games and Economic Behavior, Elsevier, vol. 48(1), pages 1-17, July.
    17. Jacob Schwartz & Kyungchul Song, 2021. "The Law of Large Numbers for Large Stable Matchings," Papers 2101.00399, arXiv.org, revised Mar 2024.
    18. Sotomayor, Marilda, 1999. "Three remarks on the many-to-many stable matching problem," Mathematical Social Sciences, Elsevier, vol. 38(1), pages 55-70, July.
    19. Beatriz Millán & Eliana Pepa Risma, 2018. "Random path to stability in a decentralized market with contracts," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 51(1), pages 79-103, June.
    20. Hakan İnal, 2015. "Core of coalition formation games and fixed-point methods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 45(4), pages 745-763, December.

    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:2609.20032. 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: https://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.