Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Log in
Learn more about individual access
Request company access
13th International Engine Congress 2026 | 24 + 25 February 2026

Meeting Place for the Powertrain and Sustainable Fuels Community

Take part as a speaker in the 13th International Engine Congress 2026, the Meeting Place for the Powertrain, and Sustainable Fuels Community for the exchange of experience. Submit a subject proposal online about our main subject areas: Passenger car engine technology, Commercial vehicle engine technology and Sustainable Fuels & Energy!
EXTENDED SEARCH
Log in
Top
Social Choice and Welfare
Published in:

09-07-2024 | Original Paper

Partitionable choice functions and stability

Authors: Umut Dur, Thayer Morrill, William Phan

Published in: Social Choice and Welfare | Issue 2/2024

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider the two-sided many-to-one matching problem and introduce a class of preferences reflecting natural forms of complementarities. For example, academic departments hire seniors and then supporting juniors, teams recruit different roles and specialties, starting with the critical ones, and firms hire workers at various levels, starting with the executives. The key feature is that a firm can partition workers into types and prioritize certain types before others. Despite this partitionability requirement of choice functions being weaker than substitutes—an essential condition concerning the existence of a stable assignment—we show that it still guarantees the existence of a stable assignment and is further a maximal domain for such.
previous article Generalized welfare lower bounds and strategyproofness in sequencing problems
next article Probabilistic models of profiles for voting by evaluation

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now
Appendix
Available only for authorised users
Footnotes
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.
 
Literature
Abdulkadiroğlu A, Sönmez T (2003) School choice: a mechanism design approach. Am Econ Rev 93:729–747CrossRef
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
Metadata
Title
Partitionable choice functions and stability
Authors
Umut Dur
Thayer Morrill
William Phan
Publication date
09-07-2024
Publisher
Springer Berlin Heidelberg
Published in
Social Choice and Welfare / Issue 2/2024
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-024-01534-1

Other articles of this Issue 2/2024

Preference heterogeneity over the aspects of individual well-being: towards the construction of an applied well-being index

  • Open Access
  • 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

Probabilistic models of profiles for voting by evaluation

  • Original Paper

Padding and pruning: gerrymandering under turnout heterogeneity

  • Original Paper

Population Lorenz-monotonic allocation schemes for TU-games

  • Open Access
  • Original Paper

Premium Partner

    Image Credits