A decomposition from a many-to-one matching market with path-independent choice functions to a one-to-one matching market

• Pablo Neme ^[1] ; Jorge Oviedo ^[1]
  1. [1] Instituto de Matematica Aplicada San Luis, UNSL-CONICET, San Luis, San Luis, Argentina
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 34, Nº. 2, 2026, págs. 225-244
• Idioma: inglés
• DOI: 10.1007/s11750-025-00709-y
• Enlaces
  • Texto completo
• Resumen

  • For a many-to-one market where firms are endowed with path-independent choice functions, based on the Aizerman–Malishevski decomposition, we define an associated one-to-one market. Given that the usual notion of stability for a one-to-one market does not fit well for this associated one-to-one market, we introduce a new notion of stability.

    This notion allows us to establish an isomorphism between the set of stable matchings in the many-to-one market and the matchings in an associated one-to-one market that meet this new stability criterion. Furthermore, we present an adaptation of the wellknown deferred acceptance algorithm to compute a matching that satisfies this new notion of stability for the associated one-to-one market. Finally, as a byproduct of our isomorphism, we prove an adapted version of the so-called Rural Hospital Theorem.

• Referencias bibliográficas
  • Aizerman M, Malishevski A (1981) General theory of best variants choice: some aspects. IEEE Trans Autom Control 26:1030–1040
  • Alkan A (2002) A class of multipartner matching markets with a strong lattice structure. Econ Theor 19:737–746
  • Birkhoff G (1967) Lattice theory. American Mathematical Society, Providence
  • Blair C (1988) The lattice structure of the set of stable matchings with multiple partners. Math Oper Res 13:619–628
  • Chambers CP, Yenmez MB (2017) Choice and matching. Am Econ J Microecon 9:126–147
  • Gale D, Shapley L (1962) College admissions and the stability of marriage. Am Math Mon 69:9–15
  • Hatfield JW, Milgrom PR (2005) Matching with contracts. Am Econ Rev 95:913–935
  • Martínez R, Massó J, Neme A, Oviedo J (2000) Single agents and the set of many-to-one stable matchings. J Econ Theory 91:91–105
  • Martínez R, Massó J, Neme A, Oviedo J (2008) On the invariance of the set of stable matchings with respect to substitutable preference profiles....
  • McVitie DG, Wilson LB (1971) Three procedures for the stable marriage problem. Commun ACM 14:491–492
  • Moulin H (1985) Choice functions over a finite set: a summary. Soc Choice Welf 2:147–160
  • Roth A (1984) The evolution of the labor market for medical interns and residents: a case study in game theory. J Polit Econ 92:991
  • Roth A (1985) The college admissions problem is not equivalent to the marriage problem. J Econ Theory 36:277–288
  • Roth A, Sotomayor M (1989) The college admissions problem revisited. Econometrica 57:559–570