Efficient and strategy-proof mechanism under general constraints

Imamura, Kenzo; Kawase, Yasushi Article Efficient and strategy-proof mechanism under general constraints Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Imamura, Kenzo; Kawase, Yasushi (2025) : Efficient and strategy-proof mechanism under general constraints, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 20, Iss. 2, pp. 481-509, https://doi.org/10.3982/TE6039 This Version is available at: https://hdl.handle.net/10419/320291 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Theoretical Economics 20 (2025), 481–509 1555-7561/20250481 Efficient and strategy-proof mechanism under general constraints Kenzo Imamura Department of Economics, University of Tokyo Yasushi Kawase Graduate School of Information Science and Technology, University of Tokyo This study investigates efficient and strategy-proof mechanisms for allocating indivisible goods under constraints. First, we examine a setting without endowments. In this setting, we introduce a class of constraints—ordered accessibility— for which the serial dictatorship (SD) mechanism is Pareto-efficient (PE), individually rational (IR), and group strategy-proof (GSP). Then we prove that accessibility is a necessary condition for the existence of PE, IR, and GSP mechanisms. Moreover, we show an example where the SD mechanism with a dynamically constructed order satisfies PE, IR, and GSP if one school has an arbitrary accessible constraint and each of the other schools has a capacity constraint. Second, we examine a setting with endowments. We find that the generalized matroid is a necessary and sufficient condition on the constraint structure for the existence of a mechanism that is PE, IR, and strategy-proof. We also demonstrate that a top trading cycles mechanism satisfies PE, IR, and GSP under any generalized matroid constraint. Finally, we observe that any two out of the three properties—PE, IR, and GSP—can be achieved under general constraints. Keywords. Matching with constraints, efficient matching, generalized matroid, strategy-proofness. JEL classification. C78, D47, D71. 1. Introduction Our focus is on the problem of allocating indivisible goods among agents in the presence of constraints. For example, when assigning schools to students, each school should satisfy not only the usual capacity constraints, but also meet diversity requirements, including type-specific quotas (Abdulkadiro˘ glu and Sönmez (2003)) and proportionality constraints (Nguyen and Vohra (2019)). Additionally, schools may have Kenzo Imamura: [email protected] Yasushi Kawase: [email protected] We are grateful to Keisuke Bando, Toshiyuki Hirai, Yuichiro Kamada, Fuhito Kojima, William Phan, Tayfun Sönmez, M. Bumin Yenmez, and the seminar participants at CIRM, EC’24, Hosei University, and Kwansei University for their helpful comments. This work was partially supported by JSPS KAKENHI Grants JP20K19739, JP23K12443, and 21H04979, by JST ERATO Grant JPMJER2301, by JST PRESTO Grant JPMJPR2122, and by Value Exchange Engineering, a joint research project between Mercari, Inc. and the RIISE. ©2025 The Authors. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE6039 482 Imamura and Kawase Theoretical Economics 20 (2025) minimal quotas to determine the minimum number of students required for their operations. In the case of refugee resettlement (Delacrétaz, Kominers, and Teytelboym (2023)), the central authority must consider factors such as heterogeneous family sizes and other requirements—such as job training and language classes—resulting in multidimensional knapsack constraints. In student–project assignment problems (Abraham, Irving, and Manlove (2007)) in which an instructor can offer multiple projects, certain subsets of projects may share common quotas, as both projects and instructors have capacity constraints. Our goal is to characterize those constraints that admit the existence of allocation mechanisms that are Pareto-efficient (PE), individual rational (IR), and strategy-proof (SP) for the agents. PE is a natural efficiency requirement and IR ensures that agents have incentives to participate in the mechanism. SP is often considered desirable because it eliminates the need for participating agents to engage in sophisticated reasoning; truthful reporting of preferences becomes a dominant strategy. We also examine group strategy-proofness (GSP), which is a stronger requirement than SP, as GSP mechanisms are robust to manipulation by groups of agents.1 We consider two settings. In the first, agents are not endowed with any goods, as in the case of school choice. In the second case, some agents are endowed with a good, such as in the case with teacher reassignment (Combe, Tercieux, and Terrier (2022), Combe, Dur, Tercieux, Terrier, and Ünver (2022)). Refugee resettlement would fit into either setting (Delacrétaz, Kominers, and Teytelboym (2023)). Before summarizing our results, we will establish a context: agents will be referred to as students, and objects are seats within schools. Constraints on how students must be assigned to schools, beyond the obvious requirement that no school exceeds its capacity, will be referred to as feasibility constraints. For the no-endowment setting, there are a variety of PE, IR, and GSP mechanisms for allocating students to schools that satisfy various feasibility constraints. For example, Delacrétaz, Kominers, and Teytelboym (2023) proposed a modified version of a top trading cycle (TTC) mechanism for multidimensional knapsack constraints. Kamada and Kojima (2023) introduced general upper bound (hereditary or downward-closed) constraints. This class also yields the existence of PE, IR, and GSP mechanisms. However, there is no PE, IR, and GSP mechanism for arbitrary constraints. For example, a desired mechanism may not exist under proportionality constraints (see Example 3). Our result delineates the boundary between what is possible and what is not. We show that the SD mechanism with a dynamically constructed order satisfies PE, IR, and GSP if one school has an accessible constraint and each of the other schools has a capacity constraint (Theorem 2). Furthermore, we prove that accessibility is a necessary condition (in a maximal domain sense) to guarantee the existence of a mechanism that satisfies PE, IR, and GSP (Theorem 3). Moreover, a PE, IR, and GSP mechanism exists when the feasibility constraints satisfy a property called σ-accessibility for some permutation σof the students (Theorem 1). 1Instances of coordinated reporting to manipulate school choice mechanisms have been documented by Pathak and Sönmez (2008). Theoretical Economics 20 (2025) Efficient and strategy-proof mechanism 483 An example of a σ-accessible constraint is when a school requires that the number of minority students matched to it must be at least half the number of majority students matched to it. This constraint is σ-accessible for a permutation σin which the minority students are ahead of the majority students. The σ-accessible constraints also arise in school choice in China (Huang (2021)). In China, each district contains multiple schools, and although students can apply to schools in other districts, the government imposes limits on the proportion of cross-district students in schools. Note that these constraints are accessible but not downward-closed. In contrast, every downward-closed constraint is σ-accessible for any σ, and every σ-accessible constraint is accessible. Now let us turn to the setting with endowments. Here, IR requires that each student be assigned to a school that is at least as good as her endowment. In general, there is no PE, IR, and SP mechanism under arbitrary constraints. Delacrétaz, Kominers, and Teytelboym (2023) provide an example with multidimensional knapsack constraints (see Example 4). This raises the question of which constraint structure is essential for the existence of PE, IR, and SP mechanisms. We show that the feasibility constraints being generalized matroid (g-matroid) is both a “necessary and sufficient” condition to guarantee existence. To establish sufficiency, we modify the TTC with M-convex set constraints (TTC-M) mechanism introduced by Suzuki, Tamura, and Yokoo (2018)(Theorem4). Our modification of TTC-M not only handles the constraints covered by Suzuki, Tamura, and Yokoo (2018). but also accommodates a wider range of more complex constraints, as detailed in Section 1.1. To establish the necessity of the g-matroid condition, we provide an example of a market in which a single school has a constraint that is not a g-matroid, and for which no PE, IR, and SP mechanism exists (Theorem 5). 1.1 Related work Our study is closely related to the papers by Suzuki, Tamura, and Yokoo (2018), Suzuki, Tamura, Yahiro, Yokoo, and Zhang (2023). These studies explored settings with endowments and a generalized TTC, where the distributional constraint is represented by an M-convex set on the vector of the number of students assigned to each school. Suzuki, Tamura, and Yokoo (2018), Suzuki et al. (2023) proposed the TTC-M mechanism and proved that it is PE, IR, and GSP. We make two major contributions to the literature. First, we identify that a g-matroid is a necessary condition of the constraint structure for the existence of mechanisms that satisfy the three desirable properties. This finding partially addresses the open question posed by Suzuki et al. (2023). In addition, g-matroid is an important concept in the literature on indivisible goods allocation problems with monetary transfers. Kelso and Crawford (1982) introduced the gross substitutes condition and showed that a competitive equilibrium exists under this condition. The key fact is that a demand correspondence derived from the gross substitutes condition forms a g-matroid for every price vector (Gul and Stacchetti (1999), Fujishige and Yang (2003), Nguyen and Vohra (2024)). 484 Imamura and Kawase Theoretical Economics 20 (2025) Second, our model generalizes theirs because constraints are imposed on the matched student–school pairs. An example of such constraints can be found in academic hiring, where each student (or applicant) has multiple labels based on their expertise, and each school (or university) provides an upper and lower quota on each label (Huang (2010), Fleiner and Kamiyama (2016), Yokoi (2017)). Another example is a model in which a student has multiple types, but is allocated as one of her types (Kurata, Hamada, Iwasaki, and Yokoo (2017)). This model includes important real-life applications, such as affirmative action in India (Sönmez and Yenmez (2022)) and Brazil (Aygün and Bó (2021)). Another difference from the model proposed by Suzuki, Tamura, and Yokoo (2018), Suzuki et al. (2023) is that our model includes outside options and allows for unmatched agents. Therefore, our model is flexible enough to include house allocation with existing tenants (Abdulkadiro˘ glu and Sönmez (1999)) and kidney exchanges (Roth, Sönmez, and Ünver (2004)) as special cases. In addition, our TTC generalizes the “‘you request my house—I get your turn” (YRMH-IGYT) mechanism (Abdulkadiro˘ glu and Sönmez (1999)) and the top trading cycles and chains (TTCC) mechanism with the SP and PE chain rule (Roth, Sönmez, and Ünver (2004)). Hafalir, Kojima, and Yenmez (2023) studied the existence of a desired mechanism that weakly improves a distributional objective upon the initial matching. They showed that if the distributional objective satisfies a notion of discrete concavity, called pseudo M-concavity, their generalized TTC satisfies (constrained) PE, IR, and SP. It should be noted that the set of matchings that weakly improves the distributional objective upon the initial matching forms a g-matroid if the distributional objective satisfies pseudo M-concavity. Kamiyama (2013) explored the case where the outside option is assumed to be worst for every student (every school is acceptable to any student). He showed that a mechanism, called the generalized serial dictatorship with project closures (GSDPC), satisfies PE and SP for general constraints. The GSDPC sequentially assigns each student to her best school to the extent that the remaining students can be feasibly assigned. It is not difficult to see that the GSDPC satisfies GSP. Furthermore, in the setting without endowments, any mechanism is IR; hence, the GSDPC satisfies PE, IR, and GSP. Imamura and Kawase (2024) studied PE under a general constraint and, in particular, provided a method for checking whether a given matching is Pareto-efficient. They identified that a matroid is a necessary and sufficient condition for the constraint to characterize the set of PE matchings by serial dictatorship (SD). They also introduced the constrained serial dictatorship (CSD) to check PE under general constraints. The CSD is almost the same as the GSDPC; however, it also considers IR. Hence, the CSD can be viewed as a PE and IR mechanism, but it is not SP. The field of matching under constraints has grown rapidly (Abdulkadiro˘ glu and Sönmez (2003), Biró, Fleiner, Irving, and Manlove (2010), Hafalir, Yenmez, and Yildirim (2013), Ehlers, Hafalir, Yenmez, and Yildirim (2014), Kamada and Kojima (2015,2017), Kawase and Iwasaki (2020)) with a primary focus on stability or fairness. However, our study emphasizes the importance of PE. Several studies examined PE mechanisms under constraints (Root and Ahn (2020), Yokote (2022), Delacrétaz, Kominers, and Teytelboym (2023)). In particular, Delacrétaz, Kominers, and Teytelboym (2023)studiedPE, Theoretical Economics 20 (2025) Efficient and strategy-proof mechanism 485 IR, and SP mechanisms under multidimensional knapsack constraints. As previously highlighted, they established that desired mechanisms do not exist when endowments are present and do exist when they are not. These findings can be derived from our results. 2. Preliminaries 2.1 Model Amarketisatuple(I,S,(i)i∈I,(Fs)s∈S,ω).I={1, 2, ,n}is a finite set of students, and Sis a finite set of schools. Each student ihas a strict preference iover S∪{∅}, where ∅means being unmatched (or an outside option). We write xixif either xix or x=xholds. Fsis the family of subsets of students that school scan accept; ω:I→ S∪{∅}is an endowment function, where ω(i)=sdenotes that the endowment of iis s∈S∪{∅}. In a setting without endowments, we assume that ω(i)=∅for all i∈I. Amatching μis a subset of I×Ssuch that each student iappears at most in one pair of μ;thatis,|μ∩{(i,s):s∈S}|≤1foralli∈I. For each i∈I,wewriteμ(i)to denote the school to which iis assigned at μ,thatis,μ(i)=sif (i,s)∈μand μ(i)=∅if (i,s)/∈μfor all s∈S.Similarly, for each s∈S,wewriteμ(s)to denote the set of students assigned to s at μ,thatis,μ(s)={i∈I:(i,s)∈μ}. A matching is called feasible if μ(s)∈Fsfor all s∈S. For notational simplicity, we sometimes add unmatched pairs (i,∅)to a matching, but we ignore such pairs. Let μ0denote the endowment matching (or initial matching), that is, μ0(i)=ω(i) for all i∈I. We assume that the endowment matching is feasible, that is, μ0∈F. 2.2 Constraints The aggregated constraint is sometimes represented by F={X⊆I×S:X(s)∈Fs(∀s∈ S)},whereX(s)={i∈I:(i,s)∈X}.2Using this notation, a matching μis feasible if and only if μ∈F. In addition, we will also consider a distributional constraint F⊆I×Sthat may not be expressible through individual constraints (Fs)s∈S. Let Ebe a ground set. A family of subsets F⊆2Eis a matroid if it satisfies the following three properties: (i) ∅∈F; (ii) if X∈Fand X⊆X,thenX∈F; (iii) if X,Y∈F and |X|<|Y|,theny∈Y\Xexists such that X∪{y}∈F. If individual constraint Fs is a matroid for every s∈S, then the aggregated constraint Fis also a matroid. Given a matroid F,anelementB∈Fis called a base if Bis an inclusion-wise maximal subset of Ein F. According to property (iii), all the bases of a given matroid have the same cardinality. The collection of all the bases is called the matroid base family. The matroid base family can be characterized as a nonempty family of subsets B⊆2Ethat satisfies the following property: for any B,B∈Band b∈B\B,thereexistsb∈B\Bsuch that (B\{b})∪{b}∈B. Matroid constraints include many real-life examples of constraints. Abdulkadiro˘ glu and Sönmez (2003) formally studied type-specific quotas to address student diversity 2Note that X∈Fmay not be a matching because some students may appear multiple times. 486 Imamura and Kawase Theoretical Economics 20 (2025) requirements within schools. Kamada and Kojima (2015) studied the regional maximum quotas in the context of medical residency matching in Japan. These constraints are special cases of a matroid. A nonempty family of subsets F⊆2Eis a g-matroid if, for any X,Y∈Fand e∈ X\Y,itholdsthat (i) X\{e}and Y∪{e}∈For (ii) there is e∈Y\Xsuch that (X\{e})∪{e}and (Y∪{e})\{e}are in F. Alternatively, a g-matroid can be characterized by another property (Murota and Shioura (1999), Tardos (1985)): for any X,Y∈Fand e∈X\Y,itholdsthat (i) X\{e}∈For (X\{e})∪{e}∈Ffor some e∈Y\Xand (ii) Y∪{e}∈For (Y∪{e})\{e}∈Ffor some e∈Y\X. Moreover, a g-matroid can be represented by F={S⊆E:p(S)≤|X∩S|≤q(S)( ∀X⊆ E)},withaparamodular pair (p,q)(Frank (2011)). Here, a pair (p,q)is called paramodular if (i) pis supermodular (i.e., p(X)+p(Y)≤p(X∪Y)+p(X∩Y)for all X,Y⊆E) (ii) qis submodular (i.e., q(X)+q(Y)≥q(X∪Y)+q(X∩Y)for all X,Y⊆E) (iii) p,qsatisfy cross-inequality (i.e., p(X)−q(Y)≥p(X\Y)−q(Y\X)for all X,Y⊆ E). A g-matroid is also called an M-convex family because the corresponding set of 0–1 vectorsisanM-convex set as a subset of ZE(Murota (2016)). The subsequent proposition gives useful subclasses of g-matroids. Refer to (Yokoi,2017, Proposition 17) for its proof. Proposition 1. Let L⊆2Ebe a laminar family3and let L,uL∈Z≥0for each L∈L. Then a family F={X⊆E:L≤|X∩L|≤uL(∀L∈L)}is a g-matroid if F= ∅. It is not difficult to see that a g-matroid is a class that includes both a matroid and a matroid base family. Moreover, a nonempty family of subsets F⊆2Eis a g-matroid if and only if there exists a matroid base family B⊆2Ewith E⊆Esuch that F={B∩E: B∈B}(Tardos (1985)). Additionally, for a g-matroid Fand ,u∈Z≥0, its truncation Fu ={X∈F:≤|X|≤u}is also a g-matroid if Fu = ∅ (Tardos (1985)). If individual constraint Fsis a g-matroid for every s∈S, then the aggregated distributional constraint is also a g-matroid. AfamilyofsubsetsF⊆2Ebelongs to the class of general upper bound (or independence system) if X⊆Y∈Fimplies X∈F. A family of subsets F⊆2Eis called accessible if for any X∈F\{∅},thereexistse∈Xsuch that X\{e}∈F. By definition, any 3AfamilyL⊆2Eis called a laminar family if, for any X,Y∈L,eitherX∩Y=∅,X⊆Y,orX⊇Y. Theoretical Economics 20 (2025) Efficient and strategy-proof mechanism 487 Figure 1. Classes of constraints we deal with in this study. nonempty accessible set system must contain the empty set. For an order σof E,afamily of subsets F⊆2Eis called σ-accessible if for any X∈F\{∅},wehaveX\{e}∈Ffor e∈arg max{σ−1(e):e∈X}. By definition, every general upper bound is σ-accessible for any σ, and every σ-accessible set system (for some σ) is accessible. In addition, these classes are distinct, as {∅,{1},{1, 2}} is σ-accessible for σ=(1, 2), but not general upper bound, and {∅,{1},{3},{1, 2},{2, 3},{1, 2, 3}} is accessible, but not σ-accessible for any σ. Figure 1illustrates the relationship among classes of constraints. 2.3 Properties A matching μis said to Pareto dominate μif μ(i)iμ(i)for all i∈Iand μ(i)iμ(i) for some i∈I. A feasible matching μis called Pareto-efficient (PE) if there is no feasible matching μthat Pareto dominates μ. Additionally, a feasible matching μis called individually rational (IR) if μ(i)iμ0(i)for all i∈I. A mechanism ψis a map from a preference profile to a feasible matching. A mechanism is PE and IR if it always produces a feasible matching that fulfills the conditions of PE and IR, respectively. A mechanism ψis strategy-proof (SP) if for every preference profile I,thereis no i∈Iand her preference  isuch that ψ[ i,−i](i)iψ[I](i),whereI=(j)j∈I and −i=(j)j∈I\{i}. Intuitively, SP requires that no student can be assigned to a strictly preferred school by misreporting her preference. Similarly, the mechanism ψ is group strategy-proof (GSP) if, for every preference profile I, there is no I∈2I\{∅} and their preference profile Isuch that ψ[ I,−I](i)iψ[I](i)for all i∈Iand ψ[ I,−I](i)iψ[I](i)for some i∈I,where I=( j)j∈Iand −I=(j)j∈I\I.In other words, GSP requires that no group of students can make each member weakly better off and that at least one student in the group is strictly better off by jointly misreporting her preferences. Clearly, GSP is a stronger property than SP. A mechanism is nonbossy if no student can influence the assignment of others without changing her own assignment by misreporting her preference. Formally, for every preference profile I,i∈I, and preference  i,ψ[I](i)=ψ[ i,−i](i)implies ψ[I]=ψ[ i,−i].Pápai (2000) showed that a mechanism is GSP under unit capacity 488 Imamura and Kawase Theoretical Economics 20 (2025) constraint if and only if it is SP and nonbossy. It is easy to verify that this equivalence still holds under any constraints in our model. 2.4 Applications In this section, we examine some applications on matching under constraints and show that our results can be used to check the existence of a desired mechanism in each case.4 Reassignment of teachers with distributional concerns Combe et al. (2022), Combe, Tercieux, and Terrier (2022) studied a teacher reassignment market and focused on improving distributional welfare over the initial matching μ0. Each teacher i∈Ihas a type τ(i) that represents her characteristics, such as experience. Each school shas a quota qsand a type ranking ▷sover the types :={τ(i):i∈I}∪{θ∅}. We assume that τ(i)▷sθ∅for all i∈μ0(s)and s∈S. A matching μis status quo improving if it is IR for each teacher, and Lorenz dominates the initial matching for each school s(i.e., τ(i)▷sθ∅for all i∈μ(s) and |{i∈μ(s):τ(i)⊵sθ}|≥|{i∈μ0(s):τ(i)⊵sθ}|for all type θ∈). A matching is status quo improving teacher optimal (SI teacher optimal) if it is status quo improving and not Pareto dominated for teachers by any other status quo improving matching. Combe et al. (2022) provided a variant of TTC, which is SI teacher optimal and SP. Their existence result can be derived from our findings.5For each school s, define a constraint as a family of subsets of students that Lorenz dominate the students matched to sin the initial matching. Then SI teacher optimality is equivalent to the conjunction of IR and PE in a setting with endowments. The key fact is that the constraint for each school forms a g-matroid, enabling the application of Theorem 4. Moreover, our result can strengthen their result from SP to GSP. Note that the constraint of Lorenz domination for each school scan be represented by a g-matroid of the form in Proposition 1by setting L={Lθ:θ∈,θ⊵sθ∅}and •Lθ∅={i∈I:θ∅▷sτ(i)},uθ∅=θ∅=0, and •Lθ={i∈I:τ(i)⊵sθ},uθ=qs,θ=|{i∈μ0(s):τ(i)⊵sθ}|for each θ∈with θ▷sθ∅. It is possible to construct a more general g-matroid constraint by using different values for the upper and lower bounds. For example, setting uθ=|{i∈μ0(s):τ(i)⊵sθ}|+1for the most experienced type θwould prevent allocating too many such teachers to one school. As seen above, our necessary and sufficient condition enables us to appropriately extend a model while preserving the existence of the desired mechanism. Proportionality ceiling constraint The proportionality ceiling constraint arises from school choice in a Chinese district. In this context, the government has imposed a 4For additional existing models not discussed in this paper, please refer to the working paper version for details: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4844451. 5The model studied by Combe, Tercieux, and Terrier (2022) is a special case where unmatched teachers and schools with vacant seats are not allowed in the initial matching, and different students cannot have the same type. Thus, our findings can also derive the existence result of Combe, Tercieux, and Terrier (2022). Theoretical Economics 20 (2025) Efficient and strategy-proof mechanism 495 a model to allocate indivisible goods with priorities. In this model, each school sis endowed with a priority, which is represented by a choice function over sets of students. Let Chs:2 I→2Ibe the choice function of s∈S,whereCh s(X)⊆Xfor all X⊆I.The choice function Chsinduces the feasibility constraint Fs={X⊆I:Ch s(X)=X}.The condition Chs(X)=Xis called individual rationality of school s. A matching μis stable if it is individually rational for both sides and there exists no (i,s)∈I×Ssuch that siμ(i)and i∈Chs(μ(s)∪{i}). We introduce conditions that impose restrictions on the priorities. A choice function Ch satisfies path-independence (Plott (1973)) if for any sets of students Xand Y,we have Ch(X∪Y)=Ch(Ch(X)∪Ch(Y)). Furthermore, a choice function Ch satisfies unidirectional substitutes and complements conditions (Huang (2021), Dur, Morrill, and Phan (2021)) if there exists an ordered type t:I→Rsuch that for any X⊆Iand i∈ Ch(X), the following conditions hold: (a) {i∈Ch(X)\{i}:t(i)=t(i)}⊆{i∈Ch(X\{i}): t(i)=t(i)}and (b) {i∈Ch(X):t(i)<t(i)}\{i}={i∈Ch(X\{i}):t(i)<t(i)}. When every choice function satisfies path-independence, a stable matching exists (Roth (1984), Aygün and Sönmez (2013)). Intuitively, a path-independent choice function rules out complementarities, which are associated with the nonexistence of stable matchings. However, Huang (2021) demonstrated that a choice function can accommodate a specific type of complementarity. When every choice function satisfies unidirectional substitutes and complements conditions for a common t, a stable matching still exists. Note that a path-independent choice function Cinduces a general upper bound since C(X)=Ximplies C(Y)=Yfor all Y⊆X.7Moreover, a choice function that satisfies unidirectional substitutes and complements induces a σ-accessible constraint, as discussed in a similar manner to the arguments presented in Section 2.4.8 An inaccessible constraint is associated with stronger complementarities. A choice function Ch with the following complementarities leads to an inaccessible constraint: there exists X⊆Iwith Ch(X)= ∅ such that for any i∈Ch(X),wehaveCh (Ch(X)\{i})⊊ Ch(X)\{i}.ThesetCh (X)with such an Xis inaccessible in the feasibility constraint induced by Ch. This type of complementarity is encountered in choice functions under proportional constraints and lower bounds, and is also observed in matchings involving couples. The presence of this complementarity is known to lead to the nonexistence of a stable matching (Nguyen and Vohra (2019), Biró et al. (2010), Ehlers et al. (2014), Fragiadakis, Iwasaki, Troyan, Ueda, and Yokoo (2016), Fragiadakis and Troyan (2017)). Importantly, this complementarity not only implies the absence of stable matchings but also rules out the existence of mechanisms that satisfy the properties of PE, IR, and GSP, as required by our necessity of accessibility. 7If a path-independent choice function induces a matroid constraint, it satisfies the law of aggregate demand (Yokoi (2019)). Consequently, this class of choice functions guarantees the existence of stable and SP mechanisms (Hatfield and Milgrom (2005)). 8Bando and Kawasaki (2021) introduced a broader class of choice functions and studied dynamic matching. The constraints induced by the choice functions are also σ-accessible. 496 Imamura and Kawase Theoretical Economics 20 (2025) 4. Setting with endowments In this section, we establish that a g-matroid is a maximal domain for the existence of PE, IR, and SP mechanisms in a setting with endowments. To demonstrate this, we first prove that a TTC mechanism satisfies PE, IR, and GSP if the constraints are g-matroid. Subsequently, we construct a market that permits no PE, IR, and SP mechanisms for each constraint Fs∗that is not a g-matroid. 4.1 Motivating example We begin with the following example, a simplified version of one found in Delacrétaz, Kominers, and Teytelboym (2023), that illustrates that no mechanism can simultaneously achieve PE, IR, and SP under general constraints. Specifically, Delacrétaz, Kominers, and Teytelboym (2023) demonstrated that no mechanism satisfies PE, IR, and SP under multidimensional knapsack constraints.9 Example 4. Suppose that there are three students, 1, 2, 3, and three schools, s1,s2,s3. The preference iof each student iis given as 1=(s3s1s2∅),2=(s3s1s2∅),3=(s2s3∅s1). For this preference, student 1 prefers school s3the most and least prefers the outside option ∅. The constraint Fsof each school sis given as Fs1=∅,{1},{2},{3},Fs2=∅,{1},{2},{3},{1, 2},Fs3=∅,{1},{2},{3}. Here, Fs1and Fs3are (unit) capacity constraints, whereas Fs2is not. Indeed, {1, 2},{3}∈ Fs2,but{1, 3},{2, 3}/∈Fs2. Constraints such as Fs2appear as budget constraints (e.g., student 3 requires more scholarship money). The endowments of students 1 and 2 are s2, and the endowment of student 3 is s3. It is not difficult to see that there exist only two PE and IR matchings: μ1=(1, s3),(2, s1),(3, s2)and μ2=(1, s1),(2, s3),(3, s2). Here, if student 1 misreports her preference as  1=(s3s2∅s1)whereas the other students report their true preferences, then μ1is a unique PE and IR matching. Similarly, if student 2 misreports her preference as  2=(s3s2∅s1)whereas the other students report their true preferences, then μ2is a unique PE and IR matching. Hence, in any PE and IR mechanism, either student 1 or 2 can be better off by misreporting his/her preference, depending on whether the outcome for true reporting is μ1or μ2. The example raises the question of which constraint structure is crucial for the existence of PE, IR, and SP mechanisms. We identify that a generalized matroid (g-matroid) is a “necessary and sufficient” condition of constraints to guarantee existence. 9In the model with multidimensional knapsack constraints, there is a finite set of service D. Each family i∈Ihas service needs νi=(νi d)∈Z|D| ≥0. Each location s∈Shas a service capacity profile κs=(κs d)∈Z|D| ≥0. The constraint of each school sis represented by Fs≡{I⊆I:i∈Iνi d≤κs dfor all d∈D}. Theoretical Economics 20 (2025) Efficient and strategy-proof mechanism 497 4.2 Mechanism for g-matroid constraints We provide a TTC mechanism that satisfies PE, IR, and GSP when the constraints are g-matroid. We derive this mechanism by utilizing the TTC-M mechanism introduced by Suzuki, Tamura, and Yokoo (2018), Suzuki et al. (2023). The TTC-M mechanism maintains PE, IR, and GSP for any distributional constraint that can be represented by an M-convex set on the vector of the number of students assigned to each school. Let χe∈{0, 1}Ebe the eth unit vector. A set of integer vectors V⊆ZE ≥0is an M-convex set if, for all v,v∈Vand all e∈Ewith ve>v  e,thereexistsf∈Ewith vf<v  fsuch that v−χe+χf∈Vand v+χe−χf∈V(Murota (2003)). Note that the TTC-M mechanism cannot be directly applied to our setting. The primary reason for this is that in our setting, the constraints are not imposed on the number of students assigned to each school, but rather on the matched student–school pairs. In addition, our setting allows students to be unmatched, whereas their model does not. To utilize the TTC-M mechanism, we construct a virtual market (I,˜ S,(˜ i)i∈I,˜ F,˜ω) from the given market (I,S,(i)i∈I,F,ω). The set of schools in the virtual market is defined as the set of student–school pairs ˜ S:={(i,s):i∈I,s∈S∪{∅}}.Eachstudent i∈Ihas a strict preference ˜ iover ˜ Ssuch that for any (i1,s1),(i2,s2)∈˜ S,wehave (i) (i1,s1)˜ i(i2,s2)⇐⇒ s1is2if i1=i2=i (ii) (i1,s1)˜ i(i2,s2)if i1=iand i2= i. The distributional constraint ˜ F⊆Z˜ S ≥0is defined as ˜ F:=ν∈{0, 1}˜ S: (i,s)∈˜ S ν(i,s)=|I|and (i,s)∈I×S:ν(i,s)=1∈F. The endowment function satisfies ˜ω(i)=(i,ω(i)) for each i∈I.Wewilldemonstrate that ˜ Fis an M-convex set if Fis a g-matroid. The TTC-M mechanism runs on the virtual market as follows. Let ▷be a common priority order over the students I. Without loss of generality, we may assume that 1 ▷2▷···▷n. In each round, every (virtual) school (i,s)∈˜ Sselects a student. If (i,s)belongs to the endowment matching, then it selects i.Otherwise, (i,s)selects the highest priority student among the students ifor which (i,s)can be added to the current matching by removing (i,ω(i)) without violating feasibility. This mechanism gives the selected student the right to obtain a seat. Each student selects the right to obtain her top applicable school seat. Subsequently, students with such rights can trade seats among themselves by constructing trading cycles. Implement the trade indicated by this cycle, and all the involved students are removed from the market. If any students remain, the procedure continues. For clarity, we provide an example of how our TTC mechanism works. Example 5. Let I={1, 2, 3, 4, 5}and S={s1,s2}. Suppose that students 1 and 2 prefer s2,s1,∅in this order, and students 3, 4, and 5 prefer s1,s2,∅in this order. The constraints 498 Imamura and Kawase Theoretical Economics 20 (2025) Algorithm 3: Generalized TTC. input : amarket(I,S,(i)i∈I,F,ω) output: a matching ˜μ 1Let μ(0)←{(i,ω(i)):i∈I},˜μ(0)←∅,andI(0)←I; 2for k←1, 2,  do 3if I(k−1)=∅then return ˜μ(k−1); 4foreach i∈I(k−1)do 5Let S(k) i←{s∈S∪{∅}:(μ(k−1)\{(i,ω(i))})∪˜μ(k−1)∪{(i,s)}∈F(∃i∈ I(k−1))}; 6Let p(k) ibe the most preferred school in S(k) ifor i; 7ipoints to (i,p(k) i); 8foreach (i,s)∈{(i,p(k) i):i∈I(k−1)}do 9if (i,s)∈μ(k−1)then (i,s)points to i; 10 else 11 Let I(k) (i,s)←{i∈I(k−1):(μ(k−1)\{(i,ω(i))})∪˜μ(k−1)∪{(i,s)}∈F}; 12 (i,s)points to the most prioritized (smallest index) student in I(k) (i,s); 13 Identify a cycle (i1,(i1,p(k) i1),i2,(i2,p(k) i2),,ir,(ir,p(k) ir)); 14 μ(k)←μ(k−1)\{(i1,ω(i1)),,(ir,ω(ir))}; 15 ˜μ(k)←˜μ(k−1)∪{(i1,p(k) i1),,(ir,p(k) ir)}; 16 I(k)←I(k−1)\{i1,,ir}; Fis a g-matroid that is defined as the aggregation of Fs1=I⊆I:I∩{2, 3, 5}≤1and Fs2=I⊆I:1≤I≤2. Let the endowments be (ω(1),ω(2),ω(3),ω(4),ω(5))=(s1,s1,s2,∅,∅),thatis,theendowment matching is μ(0)={(1, s1),(2, s1),(3, s2)}. In round 1 of Algorithm 3, student 1 points to (1, s2),(1, s2)points to 1, student 2 points to (2, s2),(2, s2)points to 1, and so on (see Figure 2a). Note that {(2, s1),(3, s2),(2, s2)}is in Falthough it is not a matching. The cycle identified at line 13 is (1, (1, s2)). Hence, we obtain μ(1)={(2, s1),(3, s2)},˜μ(1)={(1, s2)},and I(1)={2, 3, 4, 5}. In round 2, the cycle identified at line 13 is (2, (2, s2),3,(3, s1))(see Figure 2b). Thus, we obtain μ(2)=∅,˜μ(2)={(1, s2),(2, s2),(3, s1)},andI(2)={4, 5}. In round 3, there are two cycles (4, (4, s1)) and (5, (5, ∅)) (see Figure 2c). Note that student 5 cannot point to s1, as student 3 was matched to s1in round 2, and, therefore, s1/∈S(3) 5. The trades indicated by these cycles are implemented in rounds 3 and 4. Consequently, we obtain the matching ˜μ(4)={(1, s2),(2, s2),(3, s1),(4, s1)}. Theoretical Economics 20 (2025) Efficient and strategy-proof mechanism 499 Figure 2. Cycles obtained by the TTC in Example 5. The blue and red arrows represent the relationship to which students and virtual schools are pointing, respectively. Virtual schools that have not been pointed to by any student are omitted. Note that a trading cycle can be interpreted as an alternating cycle in the exchange graph of a g-matroid intersection. This correspondence can be established by constructing an instance of the g-matroid intersection problem where the common ground set is the set of student–school pairs ˜ S. One g-matroid is the distributional constraint ˜ F,and the other is a partition matroid Mthat ensures that each student appears at most once. In other words, X∈Mif |X∩{(i,s)∈˜ S:s∈S∪{∅}}|≤1foralli∈I. For a feasible matching μ, the exchange graph is a directed bipartite graph with bipartition μand ˜ S\μ.A pair (y,x)∈μ×(˜ S\μ)is an arc if (μ\{y})∪{x}∈˜ Fand (x,y)∈(˜ S\μ)×μis an arc if (μ\{y})∪{x}∈M. To preserve the feasibility of matching after trading, it is sufficient to select a cycle in the exchange graph that does not contain shortcuts (Murota (1996)). A standard method for selecting such a cycle is to select a shortest cycle. However, such a selection rule does not satisfy strategy-proofness (Imamura and Kawase (2024)). The TTC-M mechanism instead selects cycles without shortcuts by utilizing the priority order. Formally, our TTC mechanism is described in Algorithm 3. At the beginning of round k, the set of remaining students is I(k−1), and each student i∈I(k−1)is matched with μ(k−1)(i)=(i,ω(i)).Eachstudenti∈I\I(k−1)exits the market matched with ˜μ(k−1)(i). The set of schools to which student i∈I(k−1)has a chance of being matched with is represented as S(k) i. Then each student i∈I(k−1)points to (i,p(k) i),wherep(k) iis the most preferred school in S(k) i. Each virtual school (i,s)points to the most prioritized student iwho (i,s)can add by removing (i,ω(i)). We prove the following theorem. Theorem 4. The generalized TTC mechanism (Algorithm 3) satisfies PE, IR, and GSP if the distributional constraints form a g-matroid. Additionally, Algorithm 3can be implemented to run in time O(|I|2·|S|)if we assume that the feasibility of a matching can be checked in a constant time. Proof. Recall that the TTC-M mechanism satisfies PE, IR, and GSP when the distributional constraint is represented by an M-convex set on the vector of the number of students assigned to each school (Suzuki et al. (2023)). Therefore, to demonstrate that 500 Imamura and Kawase Theoretical Economics 20 (2025) Algorithm 3satisfies PE, IR, and GSP, it is sufficient to prove that ˜ Fis an M-convex set if Fis a g-matroid. Suppose that Fis a g-matroid. Then F={ν⊆˜ S:ν∩(I×S)∈F}is also a g-matroid by definition. Further, ˜ Fcan be obtained from Fby truncating it with cardinality |I|(i.e., ˜ F={ν∈F:|ν|=|I|}), and such a truncation induces a matroid base family (Tardos (1985)). As the class of matroid base families is a subclass of M-convex sets (Murota (2016)), Fis an M-convex set. Next we discuss the computational complexity of Algorithm 3. As at least one student is fixed in each iteration, the number of iterations is at most O(|I|).Therunning time of each iteration is O(|I|·|S|). Therefore, the total running time is at most O(|I|2·|S|). 4.3 Impossibility for non-g-matroid constraints Next we demonstrate that the g-matroid structure is necessary for the existence of a mechanism that satisfies PE, IR, and SP. Theorem 5. Fix a set of students I, a set of schools Swith |S|≥3, and a school s∗with the constraint Fs∗. Suppose that Fs∗is not a g-matroid. Then there must exist a market (I,S,(Fs)s∈S,ω)with s∗∈Sand Fs={X⊆I:|X|≤1}for all s∈S\{s∗}such that no mechanism simultaneously satisfies PE, IR, and SP. Proof.As Fs∗is not a g-matroid, there exist subsets Xand Yin Fs∗and a student ein X\Y, such that we have the alternatives (i) X\{e}/∈Fs∗and (X\{e})∪{e}/∈Fs∗for any e∈Y\X (ii) Y∪{e}/∈Fs∗and (Y∪{e})\{e}/∈Fs∗for any e∈Y\X. Here, we provide the proof for the case in which (i) holds. We defer the proof for the case when (ii) holds to Appendix A, as it can be demonstrated in a similar manner. Suppose that there exist X,Y∈Fs∗and e∈X\Ysuch that X\{e}/∈Fs∗and (X\ {e})∪{f}/∈Fs∗for any f∈Y\X.LetZ∈Fs∗be a set of students such that (X∩Y)⊆ Z⊆(X∪Y)\{e}.SuchasetZmust exist because Ysatisfies the condition. Among all sets Zthat satisfy this condition, we select a set that maximizes |X∩Z|. We consider two cases separately: (a) |X\Z|=1and(b)|X\Z|≥2. Case (a): |X\Z|=1 In this case, we have X∩Z=X\{e}. In addition, we have |Z\X|≥ 2 because (X\{e})∪J=Z∈Fs∗by setting J=Z\X. We select two students x,y∈Z\X arbitrarily (see Figure 3). We consider a market in which the set of schools is S={s∗,t,u} and Ft=Fu={I⊆I:|I|≤1}. Additionally, let the endowments be ω(e)=t,ω(i)=s∗ for each i∈Z,andω(i)=∅for each i/∈Z∪{e}. The endowment matching μ0for this market is feasible because μ0(s∗)=Z,|μ0(t)|=1, and |μ0(u)|=0≤1. Theoretical Economics 20 (2025) Efficient and strategy-proof mechanism 501 Figure 3. Case (a). Suppose that the students’ preferences are given as • e=(s∗t···) • x=(tus∗···) • y=(tus∗···) • i=(s∗···)for each i∈X\{e} • i=(∅s∗···)for each i∈Z\(X∪ {x,y}) • i=(∅···)for each i/∈X∪Z. Let μxbe the matching such that xmatches to uand every other student matches to her most favorite school (or her outside option). Similarly, let μybe the matching such that ymatches to uand every other student matches to her most favorite school. Then μxand μyare feasible since μx(s∗)=μy(s∗)=X. Furthermore, we can observe that only μxand μyare PE and IR. By symmetry, we can assume, without loss of generality, that a mechanism outputs μx. Suppose that xmisreports her preference as t xs∗ x···. With this misreporting, the unique PE and IR matching is μy. Hence, any PE and IR mechanism cannot satisfy SP. Case (b): |X\Z|≥2Letebe an arbitrary student in X\(Z∪{e})(see Figure 4). We consider a market in which the set of schools is S={s∗,t,u}and Ft=Fu={I⊆I:|I|≤ 1}. In addition, let the endowments be ω(e)=t,ω(e)=u,ω(i)=s∗for each i∈Z,and ω(i)=∅for each i∈I\(Z∪{e,e}). The endowment matching μ0for this market is feasible because μ0(s∗)=Zand |μ0(t)|=|μ0(u)|=1. Suppose that students’ preferences are defined as • e=(us∗t···) • e=(s∗tu···) • i=(s∗···)for each i∈X∩Z • i=(∅s∗···)for each i∈Z\X Figure 4. Case (b). 502 Imamura and Kawase Theoretical Economics 20 (2025) • i=(s∗∅···)for each i∈X\(Z∪{e,e}) • i=(∅···)for each i/∈X∪Z. Let μbe the matching produced by a PE, IR, and SP mechanism. By IR, we have X∩Z⊆ μ(s∗)⊆X∪Z.Ife/∈μ(s∗),thenwemusthaveμ(s∗)⊆Zby the maximality of |X∩Z|. Hence, μ(e)= s∗implies μ(e)= s∗. Let us consider three subcases depending on μ(e). Case (b1): μ(e)=t.Inthiscase,μ(e)= s∗and μ(e)=u. Thismeansthatμis not PE because eand ecan be better off by swapping their allocated schools, which is a contradiction. Case (b2): μ(e)=s∗. Suppose that emisreports s∗as being unacceptable (i.e., submitting  e=(ut ···)). Then emust be matched with uin any PE and IR matching, which contradicts SP. Case (b3): μ(e)=u.Inthiscase,μ(e)= s∗and μ(e)=t. Suppose that emisreports that tas being unacceptable (i.e., submitting  e=(s∗u···)). Then emust be matched with s∗because there exists a unique PE and IR matching {(i,s∗):i∈X}, which contradicts SP. 5. Discussion and conclusion 5.1 Relationship between the two settings We discuss the relationship between the settings, which can be summarized as shown in Table 2. Recall that the endowments are assumed to be feasible in both settings. In the setting with endowments, any feasible matching in Fcan be set as the initial matching μ0. In contrast, in the setting without endowments, the initial matching μ0is restricted to the empty matching, but it implies that the empty matching must be feasible in this setting. Thus, the necessary or sufficient conditions of one setting cannot be simply applied to the other setting. To make this difference clearer, let us assume that the empty matching is feasible in the setting with endowments as well. Then the necessary and sufficient condition for the existence of a desired mechanism in this setting becomes a matroid. Since any matroid constraint is σ-accessible for every σ, this is a sufficient condition for the existence of a desired mechanism in the setting without endowments. Table 2. Relationship between settings for the existence of a desired mechanism. Setting Assumption Initial Endowment Condition Without endowments ∅∈Fμ0=∅ (σ-)accessible With endowments F= ∅ μ0∈Fg-matroid Including both ∅∈Fμ0∈Fmatroid Theoretical Economics 20 (2025) Efficient and strategy-proof mechanism 503 5.2 Two out of PE, IR, and GSP In both settings, with and without endowments, any two of the three properties PE, IR, and GSP can be achieved under general constraints. It is evident that the mechanism that always outputs the endowment matching satisfies both IR and GSP. To satisfy PE and GSP, we can utilize a generalized SD mechanism that sequentially assigns each student to her best school in a predetermined order, ensuring that the remaining students can be feasibly assigned. To observe that the outcome μof the mechanism is PE, suppose, to the contrary, that there exists a feasible matching μthat is a Pareto improvement of μ. Let i∗be the first student assigned to a school other than μ(i∗)in the mechanism. Then μ(i∗)i∗μ(i∗); however, this contradicts the behavior of the generalized SD mechanism. Additionally, the mechanism is GSP because if a student does not select her preferred school in her turn, she will not receive another chance to do so. This mechanism is equivalent to the GSDPC proposed by Kamiyama (2013). PE and IR can be achieved by using the CSD mechanism (Imamura and Kawase (2024)). The CSD mechanism sequentially assigns each student to her best school in a predetermined order, while ensuring that the remaining students can be assigned to produce a feasible IR matching. Clearly, this mechanism satisfies IR. The property of PE follows from the fact that a matching is PE if it is PE under the IR constraint. Note that the CSD mechanism is not SP because each student is assigned to a school depending on the preferences of the later students. 5.3 Conclusion This study investigated the existence of efficient and strategy-proof mechanisms in indivisible goods allocation problems under general constraints. In the setting without endowments, we demonstrated that the SD mechanism satisfies PE, IR, and GSP if the constraints are σ-accessible for a common σ.Wealsoproved that accessibility is a necessary condition to ensure the existence of PE, IR, and GSP mechanisms. Identifying the most general class of constraints under which PE, IR, and SP mechanisms exist remains open. In a setting with endowments, we revealed that the g-matroid is a maximal domain under which we can guarantee the existence of a PE, IR, and SP mechanism. The same statement holds true even if we replace SP with GSP. In a setting without endowments, we formulate an integer linear program (ILP) to determine the existence of PE, IR, and SP mechanisms for a given market. In the case where I={1, 2, 3},S={s1,s2},Fs1={X⊆I:|X|= 2},andFs2={X⊆I:|X|≤1},the Gurobi solver with the ILP revealed that no such mechanism exists. The irreducible inconsistent subsystem obtained for the market contains relationships among 43 preferences, making it challenging to discern its underlying structure. Whether accessibility is necessary for the existence of PE, IR, and SP mechanisms remains for future research. In a setting with endowments, Delacrétaz, Kominers, and Teytelboym (2023)presented stronger nonexistence results under multidimensional knapsack constraints. For example, the desired mechanism does not exist even when PE and IR are replaced by the property that a mechanism Pareto improves upon every Pareto-inefficient endowment. We call this property Pareto-improving (PI). Formally, a mechanism ϕis PI if, for any preference profile Iat which the endowment matching μ0is Pareto-inefficient, 504 Imamura and Kawase Theoretical Economics 20 (2025) ϕ[I](i)iμ0(i)for all i∈Iand ϕ[I](i)iμ0(i)for some i∈I. PI is a weaker requirement than the conjunction of PE and IR. Delacrétaz, Kominers, and Teytelboym (2023) showed by example that no PI and SP mechanism exists under multidimensional knapsack constraints. In contrast, a PI and SP mechanism exists in Example 4.Thus,we are left with the question, “Which class of constraints is necessary and sufficient for the existence of PI and SP mechanisms?” Finally, let us discuss the case in which the endowment matching μ0is infeasible. In this case, no IR matchings exist, especially when every student prefers her own endowment the most. Therefore, we have no option but to abandon IR. Moreover, abandoning IR is a natural choice when allocating chores in a setting without endowments. Nevertheless, even without IR, we can still attain PE and GSP by employing the GSDPC mechanism under any constraints, as long as at least one feasible matching exists. Appendix A: Omitted part of the proof of Theorem 5 Here, we provide the proof of Theorem 5for the case when (ii) holds. Suppose that there exist X,Y∈Fs∗and e∈X\Ysuch that Y∪{e}/∈Fs∗and (Y∪ {e})\{f}/∈Fs∗for any f∈Y\X.LetZ∈Fs∗be a set of students such that (X∩Y)∪{e}⊆ Z⊆X∪Y.SuchasetZmust exist because Xsatisfies the condition. Among all sets Z that satisfy this condition, we select a set that minimizes |X∩Z|. We consider two cases separately: (c) |X∩Z|=|X∩Y|+1and(d)|X∩Z|≥|X∩ Y|+2. Case (c): |X∩Z|=|X∩Y|+1 In this case, we have X∩Z=(X∩Y)∪{e}. In addition, we have |Y\Z|≥2 because (Y∪{e})\J=Z∈Fs∗by setting J=Y\Z. We select two students x,y∈Y\Zarbitrarily (see Figure 5). We consider a market in which the set of schools is S={s∗,t,u}and Ft=Fu={I⊆I:|I|≤1}. Additionally, let the endowments be ω(e)=t,ω(i)=s∗for each i∈Yand ω(i)=∅for each i/∈Y∪{e}. The endowment matching μ0for this market is feasible because μ0(s∗)=Y,|μ0(t)|=1, and |μ0(u)|=0≤ 1. Suppose that the students’ preferences are given as • e=(s∗t···) • x=(tus∗···) • y=(tus∗···) • i=(s∗···)for each i∈Z\{e} • i=(∅s∗···)for each i∈Y\(Z∪ {x,y}) • i=(∅···)for each i/∈Z∪Y. Figure 5. Case (c).