Skip to main content
Erweiterte Suche
Anmelden
nach oben
Social Choice and Welfare
Erschienen in:

09.07.2024 | Original Paper

Partitionable choice functions and stability

verfasst von: Umut Dur, Thayer Morrill, William Phan

Erschienen in: Social Choice and Welfare | Ausgabe 2/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Dieser Artikel stellt einen neuartigen Ansatz zur Lösung des beidseitigen Many-to-One-Matching-Problems durch die Einführung von "partitionierbaren Choice-Funktionen" vor. Diese Funktionen ermöglichen die Unterteilung komplexer Matching-Probleme in einfachere, sequenzielle Probleme, wodurch stabile Zuweisungen auch bei Komplementaritäten gewährleistet sind. Die praktische Anwendung dieses Konzepts veranschaulichen die Autoren am Beispiel der Präferenzen des medizinischen Arbeitsmarktes, wo Krankenhäuser Ärzte und Krankenschwestern mit spezifischen Interdependenzen einstellen. Der vorgeschlagene Sequential Deferred Acceptance (SDA) -Mechanismus erweist sich als effektiv, wenn es darum geht, stabile und strategiesichere Übereinstimmungen zu erzielen, selbst in Szenarien mit reinen Ergänzungen. Der Aufsatz diskutiert auch die maximalen Domänenergebnisse und bietet eine Erweiterung auf Umgebungen mit strengen Verhältnisanforderungen, was ihn zu einem wertvollen Beitrag auf dem Gebiet der Matching-Theorie und -Ökonomie macht.
KI-Generiert

Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.

Vorheriger Artikel Generalized welfare lower bounds and strategyproofness in sequencing problems
Nächster Artikel Probabilistic models of profiles for voting by evaluation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
This example is reminiscent of Danilov (2003); however, in our environment, hospitals have preferences over arbitrary subsets of all types of agents, whereas he considers matchings that are tuples consisting of only one agent of every type.
 
2
Implicitly, we consider the hospitals’ choice functions collectively instead of individually, and our theoretical exercise is to identify a property of a profile of choice functions that is sufficient to guarantee the existence of a stable assignment. We may view the substitutes domain as a rectangular domain for profiles of choice functions, and the partitionable domain, a non-rectangular (\(\pi \) must be consistent across agents) superset of the substitutes domain.
 
3
A similar exercise is performed with single-peaked preferences: Can the set of alternatives be ordered so that each agent’s preference is single-peaked (with respect to this order)?
 
4
When all agents have the same type, i.e., the partition is trivial, the SDA is equivalent to DA.
 
5
Some variants of substitutability in the matching with contracts literature, such as bilateral substitutability, are equivalent to substitutability when there is only a single contract available for each potential match.
 
6
We need a consistency property, called irrelevance of rejected alternatives, in addition to substitutability to guarantee the existence of stable outcomes (Fleiner 2003; Aygün and Sönmez 2013). Throughout our analysis, we assume the choice functions of each agent on the multi-unit demand side satisfy this consistency property.
 
7
In a transferable utility setting, using insights from tropical geometry, Baldwin and Klemperer (2019) show that competitive equilibria can exist for a far more general class of utility functions than gross substitutes.
 
8
Rostek and Yoder (2020) conduct a similar exercise but with complementary preferences. Their domain and the substitutes domain are unrelated (i.e., have empty intersection), while our partitionability condition includes the latter as a special case.
 
9
Che et al. (2019) considers a large market matching model, and shows that approximately stable matchings exist without the substitutes condition.
 
10
Hatfield et al. (2019) show that in the matching with contracts framework, the cumulative offer process is the unique strategy-proof and stable mechanism when three conditions on multi-unit demand side choice function are satisfied—observable substitutes, observable size monotonicity, and non-manipulability via contractual terms. Moreover, if the choice function of a firm does not satisfy any of these three conditions, then there exist instances in which all other firms have unit demand choice functions such that strategy-proof and stable mechanisms fail to exist. In our setting, matching without contracts, observable substitutes, and observable size monotonicity correspond to substitutes and size monotonicity, respectively. Hence, our discussions on Hatfield and Kojima (2008) also hold here.
 
11
Notice that we do not restrict the number of staff, either doctor or nurse, assigned to a hospital. Instead, each hospital determines its capacity through the choice function.
 
12
That is, it is not blocked by any hospital \(h\in H\) and subset of staff \(\bar{M}\subset M\) such that each staff in \(\bar{M}\) belongs to a group.
 
13
Both Hatfield and Milgrom (2005) and Hatfield and Kojima (2008) consider the matching with contracts framework. The two-sided matching problem is a special case where there is a unique contract term for each medical staff and hospital pair. In our setting, substitutability and irrelevance of rejected alternatives together are sufficient conditions to guarantee the existence of stable matching (Fleiner 2003).
 
14
Substitutability, as well as weaker conditions, i.e., bilateral and unilateral substitutes (Hatfield and Kojima 2010), have been shown to be sufficient conditions in the matching with contracts model. Since, in our setting, each hospital-staff pair have only one possible contract, such conditions are all the same.
 
15
Notice that hospital h’s choice function fails to be substitutable even if it accepts a doctor alone.
 
16
This is reminiscent of the history independence assumption in Kotowski (2019) in the context of a dynamic matching when agents are repeatedly assigned each period. Their property requires that matchings in previous periods do not affect preferences today. Our downstream independence is the opposite—matchings in previous/upstream groups can affect selections in the current group, but later/downstream groups cannot affect previous selections.
 
17
Note that by downstream independence, \(\mu _{g-1}(h)\) is a subset of the chosen staff from \(\mu _{g-1}(h)\cup A_1(h).\)
 
18
Our result in this section still holds if the number of nurses needed to support a doctor differs across doctors.
 
19
For completeness, we provide the proof of Theorem 2 in the Appendix.
 
20
A similar problem occurs if we attempt to reverse the order of SDA with Placeholders and assign nurses first by permuting the roles of the two groups.
 
Literatur
Abdulkadiroğlu A, Sönmez T (2003) School choice: a mechanism design approach. Am Econ Rev 93:729–747CrossRef
Alva S (2018) WARP and combinatorial choice. J Econ Theory 173:320–333CrossRef
Aygün O, Sönmez T (2013) Matching with contracts: comment. Am Econ Rev 103:2050–2051CrossRef
Baldwin E, Klemperer P (2019) Understanding preferences:“demand types’’, and the existence of equilibrium with indivisibilities. Econometrica 87:867–932CrossRef
Balinski M, Sönmez T (1999) A tale of two mechanisms: student placement. J Econ Theory 84:73–94CrossRef
Bando K, Kawasaki R (2021) Stability and substitutability in dynamic matching markets. Working Paper
Che Y-K, Kim J, Kojima F (2019) Stable matching in large economies. Econometrica 87:65–110CrossRef
Combe J, Tercieux O, Terrier C (2018) The design of teacher assignment: theory and evidence. Working Paper
Correa J, Epstein R, Escobar J, Rios I, Bahamondes B, Bonet C, Epstein N, Aramayo N, Castillo M, Cristi A, Epstein B (2019) School choice in Chile. In: Proceedings of the 2019 ACM Conference on Economics and Computation. EC ’19. Association for Computing Machinery, New York, pp 325-343
Danilov VI (2003) Existence of stable matchings in some three-sided systems. Math Soc Sci 46:145–148CrossRef
Delacrétaz D, Kominers SD, Teytelboym A et al (2019) Matching mechanisms for refugee resettlement. Working Paper
Dur U, Morrill T, Phan W (2021) Allocating medical resources during a pandemic. Working Paper
Dur U, Morrill T, Phan W (2022) Family ties: school assignment with siblings. Theor Econ 17:89–120CrossRef
Fleiner T (2003) A fixed-point approach to stable matchings and some applications. Math Oper Res 28:103–126CrossRef
Gale D, Shapley L (1962) College admissions and the stability of marriage. Am Math Mon 69:9–15CrossRef
Hatfield JW, Kojima F (2008) Matching with contracts: comment. Am Econ Rev 98:1189–1194CrossRef
Hatfield JW, Kojima F (2010) Substitutes and stability for matching with contracts. J Econ Theory 145:1704–1723CrossRef
Hatfield JW, Milgrom P (2005) Matching with contracts. Am Econ Rev 95:913–935CrossRef
Hatfield JW, Kominers SD, Westkamp A (2019) Stability, strategy-proofness, and cumulative offer mechanisms. Rev Econ Studies 88(3):1457–1502CrossRef
Huang C (2021) Unidirectional substitutes and complements. Working Paper
Kamada Y, Kojima F (2015) Efficient matching under distributional constraints: theory and applications. Am Econ Rev 105:67–99CrossRef
Kamada Y, Kojima F (2017) Stability concepts in matching under distributional constraints. J Econ Theory 168:107–142CrossRef
Kelso AS, Crawford VP (1982) Job matching, coalition formation, and gross substitutes. Econometrica 50:1483–1504CrossRef
Kotowski MH (2019) A perfectly robust approach to multiperiod matching problems
Ostrovsky M (2008) Stability in supply chain networks. Am Econ Rev 98:897–923CrossRef
Pathak PA, Sönmez T, Ünver MU, Yenmez MB (2020) Fair allocation of vaccines, ventilators and antiviral treatments: leaving no ethical value behind in health care rationing. Working Paper
Rostek M, Yoder N (2020) Matching with complementary contracts. Econometrica 88:1793–1827CrossRef
Roth A (1982) The economics of matching: stability and incentives. Math Oper Res 617–628
Roth AE (1984) The evolution of the labor market for medical interns and residents: a case study in game theory. J Polit Econ 92:991–1016CrossRef
Roth A (1991) A natural experiment in the organization of entry-level labor markets: regional markets for new physicians and surgeons in the United Kingdom. Am Econ Rev 81:415–440
Roth A, Sotomayor M (1992) Two-sided matching: a study in game-theoretic modeling and analysis. Cambridge University Press, Cambridge
Sönmez T, Yenmez MB (2022) Affirmative action in India via vertical, horizontal, and overlapping reservations. Econometrica 90:1143–1176CrossRef
Sun N, Yang Z (2006) Equilibria and indivisibilities: gross substitutes and complements. Econometrica 74:1385–1402CrossRef
Metadaten
Titel
Partitionable choice functions and stability
verfasst von
Umut Dur
Thayer Morrill
William Phan
Publikationsdatum
09.07.2024
Verlag
Springer Berlin Heidelberg
Erschienen in
Social Choice and Welfare / Ausgabe 2/2024
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-024-01534-1

Weitere Artikel der Ausgabe 2/2024

Probabilistic models of profiles for voting by evaluation

  • Original Paper

Generalized welfare lower bounds and strategyproofness in sequencing problems

  • Original Paper

Sequential school choice with public and private schools

  • Original Paper

Patent package structures and sharing rules for royalty revenue

  • Original Paper

On the optimality of policy choices in the face of biased beliefs, retrospective voting and the down-up problem

  • Open Access
  • Original Paper

Padding and pruning: gerrymandering under turnout heterogeneity

  • Original Paper

Premium Partner

    Bildnachweise