Imamu a, Kenzo; Kawase, Yasushi
A icle
E icien and s a egy-p oo mechanism unde gene al
cons ain s
Theo e ical Economics
P o ided in Coope a ion wi h:
The Econome ic Socie y
Sugges ed Ci a ion: Imamu a, Kenzo; Kawase, Yasushi (2025) : E icien and s a egy-p oo
mechanism unde gene al cons ain s, Theo e ical Economics, ISSN 1555-7561, The Econome ic
Socie y, New Ha en, CT, Vol. 20, Iss. 2, pp. 481-509,
h ps://doi.o g/10.3982/TE6039
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/320291
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h ps://c ea i ecommons.o g/licenses/by-nc/4.0/
Theo e ical Economics 20 (2025), 481–509 1555-7561/20250481
E icien and s a egy-p oo mechanism unde gene al
cons ain s
Kenzo Imamu a
Depa men o Economics, Uni e si y o Tokyo
Yasushi Kawase
G adua e School o In o ma ion Science and Technology, Uni e si y o Tokyo
This s udy in es iga es e icien and s a egy-p oo mechanisms o alloca ing in-
di isible goods unde cons ain s. Fi s , we examine a se ing wi hou endow-
men s. In his se ing, we in oduce a class o cons ain s—o de ed accessibili y—
o which he se ial dic a o ship (SD) mechanism is Pa e o-e icien (PE), indi id-
ually a ional (IR), and g oup s a egy-p oo (GSP). Then we p o e ha accessi-
bili y is a necessa y condi ion o he exis ence o PE, IR, and GSP mechanisms.
Mo eo e , we show an example whe e he SD mechanism wi h a dynamically con-
s uc ed o de sa is ies PE, IR, and GSP i one school has an a bi a y accessible
cons ain and each o he o he schools has a capaci y cons ain . Second, we
examine a se ing wi h endowmen s. We ind ha he gene alized ma oid is a
necessa y and su icien condi ion on he cons ain s uc u e o he exis ence o
a mechanism ha is PE, IR, and s a egy-p oo . We also demons a e ha a op
ading cycles mechanism sa is ies PE, IR, and GSP unde any gene alized ma-
oid cons ain . Finally, we obse e ha any wo ou o he h ee p ope ies—PE,
IR, and GSP—can be achie ed unde gene al cons ain s.
Keywo ds. Ma ching wi h cons ain s, e icien ma ching, gene alized ma oid,
s a egy-p oo ness.
JEL classi ica ion. C78, D47, D71.
1. In oduc ion
Ou ocus is on he p oblem o alloca ing indi isible goods among agen s in he p es-
ence o cons ain s. Fo example, when assigning schools o s uden s, each school
should sa is y no only he usual capaci y cons ain s, bu also mee di e si y equi e-
men s, including ype-speci ic quo as (Abdulkadi o˘
glu and Sönmez (2003)) and p o-
po ionali y cons ain s (Nguyen and Voh a (2019)). Addi ionally, schools may ha e
Kenzo Imamu a: [email p o ec ed]
Yasushi Kawase: [email p o ec ed]
We a e g a e ul o Keisuke Bando, Toshiyuki Hi ai, Yuichi o Kamada, Fuhi o Kojima, William Phan, Tay un
Sönmez, M. Bumin Yenmez, and he semina pa icipan s a CIRM, EC’24, Hosei Uni e si y, and Kwan-
sei Uni e si y o hei help ul commen s. This wo k was pa ially suppo ed by JSPS KAKENHI G an s
JP20K19739, JP23K12443, and 21H04979, by JST ERATO G an JPMJER2301, by JST PRESTO G an JP-
MJPR2122, and by Value Exchange Enginee ing, a join esea ch p ojec be ween Me ca i, Inc. and he
RIISE.
©2025 The Au ho s. Licensed unde he C ea i e Commons A ibu ion-NonComme cial License 4.0.
A ailable a h ps://econ heo y.o g.h ps://doi.o g/10.3982/TE6039
482 Imamu a and Kawase Theo e ical Economics 20 (2025)
minimal quo as o de e mine he minimum numbe o s uden s equi ed o hei op-
e a ions. In he case o e ugee ese lemen (Delac é az, Komine s, and Tey elboym
(2023)), he cen al au ho i y mus conside ac o s such as he e ogeneous amily sizes
and o he equi emen s—such as job aining and language classes— esul ing in mul i-
dimensional knapsack cons ain s. In s uden –p ojec assignmen p oblems (Ab aham,
I ing, and Manlo e (2007)) in which an ins uc o can o e mul iple p ojec s, ce ain
subse s o p ojec s may sha e common quo as, as bo h p ojec s and ins uc o s ha e
capaci y cons ain s.
Ou goal is o cha ac e ize hose cons ain s ha admi he exis ence o alloca ion
mechanisms ha a e Pa e o-e icien (PE), indi idual a ional (IR), and s a egy-p oo
(SP) o he agen s. PE is a na u al e iciency equi emen and IR ensu es ha agen s
ha e incen i es o pa icipa e in he mechanism. SP is o en conside ed desi able be-
cause i elimina es he need o pa icipa ing agen s o engage in sophis ica ed eason-
ing; u h ul epo ing o p e e ences becomes a dominan s a egy. We also examine
g oup s a egy-p oo ness (GSP), which is a s onge equi emen han SP, as GSP mech-
anisms a e obus o manipula ion by g oups o agen s.1
We conside wo se ings. In he i s , agen s a e no endowed wi h any goods, as in
he case o school choice. In he second case, some agen s a e endowed wi h a good,
such as in he case wi h eache eassignmen (Combe, Te cieux, and Te ie (2022),
Combe, Du , Te cieux, Te ie , and Ün e (2022)). Re ugee ese lemen would i in o
ei he se ing (Delac é az, Komine s, and Tey elboym (2023)).
Be o e summa izing ou esul s, we will es ablish a con ex : agen s will be e e ed o
as s uden s, and objec s a e sea s wi hin schools. Cons ain s on how s uden s mus be
assigned o schools, beyond he ob ious equi emen ha no school exceeds i s capaci y,
will be e e ed o as easibili y cons ain s.
Fo he no-endowmen se ing, he e a e a a ie y o PE, IR, and GSP mechanisms
o alloca ing s uden s o schools ha sa is y a ious easibili y cons ain s. Fo example,
Delac é az, Komine s, and Tey elboym (2023) p oposed a modi ied e sion o a op ad-
ing cycle (TTC) mechanism o mul idimensional knapsack cons ain s. Kamada and
Kojima (2023) in oduced gene al uppe bound (he edi a y o downwa d-closed) con-
s ain s. This class also yields he exis ence o PE, IR, and GSP mechanisms. Howe e ,
he e is no PE, IR, and GSP mechanism o a bi a y cons ain s. Fo example, a desi ed
mechanism may no exis unde p opo ionali y cons ain s (see Example 3).
Ou esul delinea es he bounda y be ween wha is possible and wha is no . We
show ha he SD mechanism wi h a dynamically cons uc ed o de sa is ies PE, IR, and
GSP i one school has an accessible cons ain and each o he o he schools has a ca-
paci y cons ain (Theo em 2). Fu he mo e, we p o e ha accessibili y is a necessa y
condi ion (in a maximal domain sense) o gua an ee he exis ence o a mechanism ha
sa is ies PE, IR, and GSP (Theo em 3). Mo eo e , a PE, IR, and GSP mechanism exis s
when he easibili y cons ain s sa is y a p ope y called σ-accessibili y o some pe mu-
a ion σo he s uden s (Theo em 1).
1Ins ances o coo dina ed epo ing o manipula e school choice mechanisms ha e been documen ed
by Pa hak and Sönmez (2008).
Theo e ical Economics 20 (2025) E icien and s a egy-p oo mechanism 483
An example o a σ-accessible cons ain is when a school equi es ha he numbe
o mino i y s uden s ma ched o i mus be a leas hal he numbe o majo i y s uden s
ma ched o i . This cons ain is σ-accessible o a pe mu a ion σin which he mino i y
s uden s a e ahead o he majo i y s uden s. The σ-accessible cons ain s also a ise in
school choice in China (Huang (2021)). In China, each dis ic con ains mul iple schools,
and al hough s uden s can apply o schools in o he dis ic s, he go e nmen imposes
limi s on he p opo ion o c oss-dis ic s uden s in schools. No e ha hese cons ain s
a e accessible bu no downwa d-closed. In con as , e e y downwa d-closed cons ain
is σ-accessible o any σ, and e e y σ-accessible cons ain is accessible.
Now le us u n o he se ing wi h endowmen s. He e, IR equi es ha each s u-
den be assigned o a school ha is a leas as good as he endowmen . In gene al,
he e is no PE, IR, and SP mechanism unde a bi a y cons ain s. Delac é az, Komine s,
and Tey elboym (2023) p o ide an example wi h mul idimensional knapsack cons ain s
(see Example 4). This aises he ques ion o which cons ain s uc u e is essen ial o
he exis ence o PE, IR, and SP mechanisms. We show ha he easibili y cons ain s
being gene alized ma oid (g-ma oid) is bo h a “necessa y and su icien ” condi ion o
gua an ee exis ence.
To es ablish su iciency, we modi y he TTC wi h M-con ex se cons ain s (TTC-M)
mechanism in oduced by Suzuki, Tamu a, and Yokoo (2018)(Theo em4). Ou modi i-
ca ion o TTC-M no only handles he cons ain s co e ed by Suzuki, Tamu a, and Yokoo
(2018). bu also accommoda es a wide ange o mo e complex cons ain s, as de ailed
in Sec ion 1.1. To es ablish he necessi y o he g-ma oid condi ion, we p o ide an ex-
ample o a ma ke in which a single school has a cons ain ha is no a g-ma oid, and
o which no PE, IR, and SP mechanism exis s (Theo em 5).
1.1 Rela ed wo k
Ou s udy is closely ela ed o he pape s by Suzuki, Tamu a, and Yokoo (2018), Suzuki,
Tamu a, Yahi o, Yokoo, and Zhang (2023). These s udies explo ed se ings wi h endow-
men s and a gene alized TTC, whe e he dis ibu ional cons ain is ep esen ed by an
M-con ex se on he ec o o he numbe o s uden s assigned o each school. Suzuki,
Tamu a, and Yokoo (2018), Suzuki e al. (2023) p oposed he TTC-M mechanism and
p o ed ha i is PE, IR, and GSP. We make wo majo con ibu ions o he li e a u e.
Fi s , we iden i y ha a g-ma oid is a necessa y condi ion o he cons ain s uc-
u e o he exis ence o mechanisms ha sa is y he h ee desi able p ope ies. This
inding pa ially add esses he open ques ion posed by Suzuki e al. (2023). In addi ion,
g-ma oid is an impo an concep in he li e a u e on indi isible goods alloca ion p ob-
lems wi h mone a y ans e s. Kelso and C aw o d (1982) in oduced he g oss subs i-
u es condi ion and showed ha a compe i i e equilib ium exis s unde his condi ion.
The key ac is ha a demand co espondence de i ed om he g oss subs i u es con-
di ion o ms a g-ma oid o e e y p ice ec o (Gul and S acche i (1999), Fujishige and
Yang (2003), Nguyen and Voh a (2024)).
484 Imamu a and Kawase Theo e ical Economics 20 (2025)
Second, ou model gene alizes hei s because cons ain s a e imposed on he
ma ched s uden –school pai s. An example o such cons ain s can be ound in aca-
demic hi ing, whe e each s uden (o applican ) has mul iple labels based on hei ex-
pe ise, and each school (o uni e si y) p o ides an uppe and lowe quo a on each
label (Huang (2010), Fleine and Kamiyama (2016), Yokoi (2017)). Ano he example is a
model in which a s uden has mul iple ypes, bu is alloca ed as one o he ypes (Ku a a,
Hamada, Iwasaki, and Yokoo (2017)). This model includes impo an eal-li e applica-
ions, such as a i ma i e ac ion in India (Sönmez and Yenmez (2022)) and B azil (Aygün
and Bó (2021)).
Ano he di e ence om he model p oposed by Suzuki, Tamu a, and Yokoo (2018),
Suzuki e al. (2023) is ha ou model includes ou side op ions and allows o unma ched
agen s. The e o e, ou model is lexible enough o include house alloca ion wi h exis -
ing enan s (Abdulkadi o˘
glu and Sönmez (1999)) and kidney exchanges (Ro h, Sönmez,
and Ün e (2004)) as special cases. In addi ion, ou TTC gene alizes he “‘you eques
my house—I ge you u n” (YRMH-IGYT) mechanism (Abdulkadi o˘
glu and Sönmez
(1999)) and he op ading cycles and chains (TTCC) mechanism wi h he SP and PE
chain ule (Ro h, Sönmez, and Ün e (2004)).
Ha ali , Kojima, and Yenmez (2023) s udied he exis ence o a desi ed mechanism
ha weakly imp o es a dis ibu ional objec i e upon he ini ial ma ching. They showed
ha i he dis ibu ional objec i e sa is ies a no ion o disc e e conca i y, called pseudo
M-conca i y, hei gene alized TTC sa is ies (cons ained) PE, IR, and SP. I should be
no ed ha he se o ma chings ha weakly imp o es he dis ibu ional objec i e upon
he ini ial ma ching o ms a g-ma oid i he dis ibu ional objec i e sa is ies pseudo
M-conca i y.
Kamiyama (2013) explo ed he case whe e he ou side op ion is assumed o be wo s
o e e y s uden (e e y school is accep able o any s uden ). He showed ha a mecha-
nism, called he gene alized se ial dic a o ship wi h p ojec closu es (GSDPC), sa is ies
PE and SP o gene al cons ain s. The GSDPC sequen ially assigns each s uden o he
bes school o he ex en ha he emaining s uden s can be easibly assigned. I is no
di icul o see ha he GSDPC sa is ies GSP. Fu he mo e, in he se ing wi hou endow-
men s, any mechanism is IR; hence, he GSDPC sa is ies PE, IR, and GSP.
Imamu a and Kawase (2024) s udied PE unde a gene al cons ain and, in pa icu-
la , p o ided a me hod o checking whe he a gi en ma ching is Pa e o-e icien . They
iden i ied ha a ma oid is a necessa y and su icien condi ion o he cons ain o
cha ac e ize he se o PE ma chings by se ial dic a o ship (SD). They also in oduced
he cons ained se ial dic a o ship (CSD) o check PE unde gene al cons ain s. The
CSD is almos he same as he GSDPC; howe e , i also conside s IR. Hence, he CSD can
be iewed as a PE and IR mechanism, bu i is no SP.
The ield o ma ching unde cons ain s has g own apidly (Abdulkadi o˘
glu and Sön-
mez (2003), Bi ó, Fleine , I ing, and Manlo e (2010), Ha ali , Yenmez, and Yildi im
(2013), Ehle s, Ha ali , Yenmez, and Yildi im (2014), Kamada and Kojima (2015,2017),
Kawase and Iwasaki (2020)) wi h a p ima y ocus on s abili y o ai ness. Howe e , ou
s udy emphasizes he impo ance o PE. Se e al s udies examined PE mechanisms un-
de cons ain s (Roo and Ahn (2020), Yoko e (2022), Delac é az, Komine s, and Tey el-
boym (2023)). In pa icula , Delac é az, Komine s, and Tey elboym (2023)s udiedPE,
Theo e ical Economics 20 (2025) E icien and s a egy-p oo mechanism 485
IR, and SP mechanisms unde mul idimensional knapsack cons ain s. As p e iously
highligh ed, hey es ablished ha desi ed mechanisms do no exis when endowmen s
a e p esen and do exis when hey a e no . These indings can be de i ed om ou
esul s.
2. P elimina ies
2.1 Model
Ama ke isa uple(I,S,(i)i∈I,(Fs)s∈S,ω).I={1, 2, ,n}is a ini e se o s uden s,
and Sis a ini e se o schools. Each s uden ihas a s ic p e e ence io e S∪{∅},
whe e ∅means being unma ched (o an ou side op ion). We w i e xixi ei he xix
o x=xholds. Fsis he amily o subse s o s uden s ha school scan accep ; ω:I→
S∪{∅}is an endowmen unc ion, whe e ω(i)=sdeno es ha he endowmen o iis
s∈S∪{∅}. In a se ing wi hou endowmen s, we assume ha ω(i)=∅ o all i∈I.
Ama ching μis a subse o I×Ssuch ha each s uden iappea s a mos in one pai
o μ; ha is,|μ∩{(i,s):s∈S}|≤1 o alli∈I. Fo each i∈I,wew i eμ(i) o deno e he
school o which iis assigned a μ, ha is,μ(i)=si (i,s)∈μand μ(i)=∅i (i,s)/∈μ o
all s∈S.Simila ly, o each s∈S,wew i eμ(s) o deno e he se o s uden s assigned o s
a μ, ha is,μ(s)={i∈I:(i,s)∈μ}. A ma ching is called easible i μ(s)∈Fs o all s∈S.
Fo no a ional simplici y, we some imes add unma ched pai s (i,∅) o a ma ching, bu
we igno e such pai s.
Le μ0deno e he endowmen ma ching (o ini ial ma ching), ha is, μ0(i)=ω(i)
o all i∈I. We assume ha he endowmen ma ching is easible, ha is, μ0∈F.
2.2 Cons ain s
The agg ega ed cons ain is some imes ep esen ed by F={X⊆I×S:X(s)∈Fs(∀s∈
S)},whe eX(s)={i∈I:(i,s)∈X}.2Using his no a ion, a ma ching μis easible i and
only i μ∈F. In addi ion, we will also conside a dis ibu ional cons ain F⊆I×S ha
may no be exp essible h ough indi idual cons ain s (Fs)s∈S.
Le Ebe a g ound se . A amily o subse s F⊆2Eis a ma oid i i sa is ies he ol-
lowing h ee p ope ies: (i) ∅∈F; (ii) i X∈Fand X⊆X, henX∈F; (iii) i X,Y∈F
and |X|<|Y|, heny∈Y Xexis s such ha X∪{y}∈F. I indi idual cons ain Fs
is a ma oid o e e y s∈S, hen he agg ega ed cons ain Fis also a ma oid. Gi en a
ma oid F,anelemen B∈Fis called a base i Bis an inclusion-wise maximal subse
o Ein F. Acco ding o p ope y (iii), all he bases o a gi en ma oid ha e he same
ca dinali y. The collec ion o all he bases is called he ma oid base amily. The ma oid
base amily can be cha ac e ized as a nonemp y amily o subse s B⊆2E ha sa is ies
he ollowing p ope y: o any B,B∈Band b∈B B, he eexis sb∈B Bsuch ha
(B {b})∪{b}∈B.
Ma oid cons ain s include many eal-li e examples o cons ain s. Abdulkadi o˘
glu
and Sönmez (2003) o mally s udied ype-speci ic quo as o add ess s uden di e si y
2No e ha X∈Fmay no be a ma ching because some s uden s may appea mul iple imes.
486 Imamu a and Kawase Theo e ical Economics 20 (2025)
equi emen s wi hin schools. Kamada and Kojima (2015) s udied he egional maximum
quo as in he con ex o medical esidency ma ching in Japan. These cons ain s a e
special cases o a ma oid.
A nonemp y amily o subse s F⊆2Eis a g-ma oid i , o any X,Y∈Fand e∈
X Y,i holds ha
(i) X {e}and Y∪{e}∈Fo
(ii) he e is e∈Y Xsuch ha (X {e})∪{e}and (Y∪{e}) {e}a e in F.
Al e na i ely, a g-ma oid can be cha ac e ized by ano he p ope y (Mu o a and Sh-
iou a (1999), Ta dos (1985)): o any X,Y∈Fand e∈X Y,i holds ha
(i) X {e}∈Fo (X {e})∪{e}∈F o some e∈Y Xand
(ii) Y∪{e}∈Fo (Y∪{e}) {e}∈F o some e∈Y X.
Mo eo e , a g-ma oid can be ep esen ed by F={S⊆E:p(S)≤|X∩S|≤q(S)(
∀X⊆
E)},wi hapa amodula pai (p,q)(F ank (2011)). He e, a pai (p,q)is called pa amod-
ula i
(i) pis supe modula (i.e., p(X)+p(Y)≤p(X∪Y)+p(X∩Y) o all X,Y⊆E)
(ii) qis submodula (i.e., q(X)+q(Y)≥q(X∪Y)+q(X∩Y) o all X,Y⊆E)
(iii) p,qsa is y c oss-inequali y (i.e., p(X)−q(Y)≥p(X Y)−q(Y X) o all X,Y⊆
E).
A g-ma oid is also called an M-con ex amily because he co esponding se o 0–1
ec o sisanM-con ex se as a subse o ZE(Mu o a (2016)). The subsequen p oposi-
ion gi es use ul subclasses o g-ma oids. Re e o (Yokoi,2017, P oposi ion 17) o i s
p oo .
P oposi ion 1. Le L⊆2Ebe a lamina amily3and le L,uL∈Z≥0 o each L∈L.
Then a amily F={X⊆E:L≤|X∩L|≤uL(∀L∈L)}is a g-ma oid i F= ∅.
I is no di icul o see ha a g-ma oid is a class ha includes bo h a ma oid and
a ma oid base amily. Mo eo e , a nonemp y amily o subse s F⊆2Eis a g-ma oid i
and only i he e exis s a ma oid base amily B⊆2Ewi h E⊆Esuch ha F={B∩E:
B∈B}(Ta dos (1985)). Addi ionally, o a g-ma oid Fand ,u∈Z≥0, i s unca ion
Fu
={X∈F:≤|X|≤u}is also a g-ma oid i Fu
= ∅ (Ta dos (1985)). I indi idual
cons ain Fsis a g-ma oid o e e y s∈S, hen he agg ega ed dis ibu ional cons ain
is also a g-ma oid.
A amilyo subse sF⊆2Ebelongs o he class o gene al uppe bound (o indepen-
dence sys em) i X⊆Y∈Fimplies X∈F. A amily o subse s F⊆2Eis called acces-
sible i o any X∈F {∅}, he eexis se∈Xsuch ha X {e}∈F. By de ini ion, any
3A amilyL⊆2Eis called a lamina amily i , o any X,Y∈L,ei he X∩Y=∅,X⊆Y,o X⊇Y.
Theo e ical Economics 20 (2025) E icien and s a egy-p oo mechanism 487
Figu e 1. Classes o cons ain s we deal wi h in his s udy.
nonemp y accessible se sys em mus con ain he emp y se . Fo an o de σo E,a am-
ily o subse s F⊆2Eis called σ-accessible i o any X∈F {∅},weha eX {e}∈F o
e∈a g max{σ−1(e):e∈X}. By de ini ion, e e y gene al uppe bound is σ-accessible o
any σ, and e e y σ-accessible se sys em ( o some σ) is accessible. In addi ion, hese
classes a e dis inc , as {∅,{1},{1, 2}} is σ-accessible o σ=(1, 2), bu no gene al uppe
bound, and {∅,{1},{3},{1, 2},{2, 3},{1, 2, 3}} is accessible, bu no σ-accessible o any
σ.
Figu e 1illus a es he ela ionship among classes o cons ain s.
2.3 P ope ies
A ma ching μis said o Pa e o domina e μi μ(i)iμ(i) o all i∈Iand μ(i)iμ(i)
o some i∈I. A easible ma ching μis called Pa e o-e icien (PE) i he e is no easi-
ble ma ching μ ha Pa e o domina es μ. Addi ionally, a easible ma ching μis called
indi idually a ional (IR) i μ(i)iμ0(i) o all i∈I.
A mechanism ψis a map om a p e e ence p o ile o a easible ma ching. A mecha-
nism is PE and IR i i always p oduces a easible ma ching ha ul ills he condi ions o
PE and IR, espec i ely.
A mechanism ψis s a egy-p oo (SP) i o e e y p e e ence p o ile I, he eis
no i∈Iand he p e e ence
isuch ha ψ[
i,−i](i)iψ[I](i),whe eI=(j)j∈I
and −i=(j)j∈I {i}. In ui i ely, SP equi es ha no s uden can be assigned o a
s ic ly p e e ed school by mis epo ing he p e e ence. Simila ly, he mechanism ψ
is g oup s a egy-p oo (GSP) i , o e e y p e e ence p o ile I, he e is no I∈2I {∅}
and hei p e e ence p o ile Isuch ha ψ[
I,−I](i)iψ[I](i) o all i∈Iand
ψ[
I,−I](i)iψ[I](i) o some i∈I,whe e
I=(
j)j∈Iand −I=(j)j∈I I.In
o he wo ds, GSP equi es ha no g oup o s uden s can make each membe weakly
be e o and ha a leas one s uden in he g oup is s ic ly be e o by join ly mis e-
po ing he p e e ences. Clea ly, GSP is a s onge p ope y han SP.
A mechanism is nonbossy i no s uden can in luence he assignmen o o he s
wi hou changing he own assignmen by mis epo ing he p e e ence. Fo mally, o
e e y p e e ence p o ile I,i∈I, and p e e ence
i,ψ[I](i)=ψ[
i,−i](i)implies
ψ[I]=ψ[
i,−i].Pápai (2000) showed ha a mechanism is GSP unde uni capaci y
488 Imamu a and Kawase Theo e ical Economics 20 (2025)
cons ain i and only i i is SP and nonbossy. I is easy o e i y ha his equi alence
s ill holds unde any cons ain s in ou model.
2.4 Applica ions
In his sec ion, we examine some applica ions on ma ching unde cons ain s and show
ha ou esul s can be used o check he exis ence o a desi ed mechanism in each case.4
Reassignmen o eache s wi h dis ibu ional conce ns Combe e al. (2022), Combe, Te -
cieux, and Te ie (2022) s udied a eache eassignmen ma ke and ocused on imp o -
ing dis ibu ional wel a e o e he ini ial ma ching μ0. Each eache i∈Ihas a ype τ(i)
ha ep esen s he cha ac e is ics, such as expe ience. Each school shas a quo a qsand
a ype anking ▷so e he ypes :={τ(i):i∈I}∪{θ∅}. We assume ha τ(i)▷sθ∅ o all
i∈μ0(s)and s∈S. A ma ching μis s a us quo imp o ing i i is IR o each eache , and
Lo enz domina es he ini ial ma ching o each school s(i.e., τ(i)▷sθ∅ o all i∈μ(s)
and |{i∈μ(s):τ(i)⊵sθ}|≥|{i∈μ0(s):τ(i)⊵sθ}| o all ype θ∈). A ma ching is s a-
us quo imp o ing eache op imal (SI eache op imal) i i is s a us quo imp o ing and
no Pa e o domina ed o eache s by any o he s a us quo imp o ing ma ching. Combe
e al. (2022) p o ided a a ian o TTC, which is SI eache op imal and SP.
Thei exis ence esul can be de i ed om ou indings.5Fo each school s, de ine a
cons ain as a amily o subse s o s uden s ha Lo enz domina e he s uden s ma ched
o sin he ini ial ma ching. Then SI eache op imali y is equi alen o he conjunc ion
o IR and PE in a se ing wi h endowmen s. The key ac is ha he cons ain o each
school o ms a g-ma oid, enabling he applica ion o Theo em 4. Mo eo e , ou esul
can s eng hen hei esul om SP o GSP.
No e ha he cons ain o Lo enz domina ion o each school scan be ep esen ed
by a g-ma oid o he o m in P oposi ion 1by se ing L={Lθ:θ∈,θ⊵sθ∅}and
•Lθ∅={i∈I:θ∅▷sτ(i)},uθ∅=θ∅=0, and
•Lθ={i∈I:τ(i)⊵sθ},uθ=qs,θ=|{i∈μ0(s):τ(i)⊵sθ}| o each θ∈wi h θ▷sθ∅.
I is possible o cons uc a mo e gene al g-ma oid cons ain by using di e en alues
o he uppe and lowe bounds. Fo example, se ing uθ=|{i∈μ0(s):τ(i)⊵sθ}|+1 o
he mos expe ienced ype θwould p e en alloca ing oo many such eache s o one
school.
As seen abo e, ou necessa y and su icien condi ion enables us o app op ia ely
ex end a model while p ese ing he exis ence o he desi ed mechanism.
P opo ionali y ceiling cons ain The p opo ionali y ceiling cons ain a ises om
school choice in a Chinese dis ic . In his con ex , he go e nmen has imposed a
4Fo addi ional exis ing models no discussed in his pape , please e e o he wo king pape e sion o
de ails: h ps://pape s.ss n.com/sol3/pape s.c m?abs ac _id=4844451.
5The model s udied by Combe, Te cieux, and Te ie (2022) is a special case whe e unma ched eache s
and schools wi h acan sea s a e no allowed in he ini ial ma ching, and di e en s uden s canno ha e he
same ype. Thus, ou indings can also de i e he exis ence esul o Combe, Te cieux, and Te ie (2022).
Theo e ical Economics 20 (2025) E icien and s a egy-p oo mechanism 495
a model o alloca e indi isible goods wi h p io i ies. In his model, each school sis en-
dowed wi h a p io i y, which is ep esen ed by a choice unc ion o e se s o s uden s.
Le Chs:2
I→2Ibe he choice unc ion o s∈S,whe eCh
s(X)⊆X o all X⊆I.The
choice unc ion Chsinduces he easibili y cons ain Fs={X⊆I:Ch
s(X)=X}.The
condi ion Chs(X)=Xis called indi idual a ionali y o school s. A ma ching μis s a-
ble i i is indi idually a ional o bo h sides and he e exis s no (i,s)∈I×Ssuch ha
siμ(i)and i∈Chs(μ(s)∪{i}).
We in oduce condi ions ha impose es ic ions on he p io i ies. A choice unc ion
Ch sa is ies pa h-independence (Plo (1973)) i o any se s o s uden s Xand Y,we
ha e Ch(X∪Y)=Ch(Ch(X)∪Ch(Y)). Fu he mo e, a choice unc ion Ch sa is ies
unidi ec ional subs i u es and complemen s condi ions (Huang (2021), Du , Mo ill, and
Phan (2021)) i he e exis s an o de ed ype :I→Rsuch ha o any X⊆Iand i∈
Ch(X), he ollowing condi ions hold: (a) {i∈Ch(X) {i}: (i)= (i)}⊆{i∈Ch(X {i}):
(i)= (i)}and (b) {i∈Ch(X): (i)< (i)} {i}={i∈Ch(X {i}): (i)< (i)}.
When e e y choice unc ion sa is ies pa h-independence, a s able ma ching exis s
(Ro h (1984), Aygün and Sönmez (2013)). In ui i ely, a pa h-independen choice unc-
ion ules ou complemen a i ies, which a e associa ed wi h he nonexis ence o s able
ma chings. Howe e , Huang (2021) demons a ed ha a choice unc ion can accommo-
da e a speci ic ype o complemen a i y. When e e y choice unc ion sa is ies unidi ec-
ional subs i u es and complemen s condi ions o a common , a s able ma ching s ill
exis s. No e ha a pa h-independen choice unc ion Cinduces a gene al uppe bound
since C(X)=Ximplies C(Y)=Y o all Y⊆X.7Mo eo e , a choice unc ion ha sa -
is ies unidi ec ional subs i u es and complemen s induces a σ-accessible cons ain , as
discussed in a simila manne o he a gumen s p esen ed in Sec ion 2.4.8
An inaccessible cons ain is associa ed wi h s onge complemen a i ies. A choice
unc ion Ch wi h he ollowing complemen a i ies leads o an inaccessible cons ain :
he e exis s X⊆Iwi h Ch(X)= ∅ such ha o any i∈Ch(X),weha eCh
(Ch(X) {i})⊊
Ch(X) {i}.These Ch
(X)wi h such an Xis inaccessible in he easibili y cons ain
induced by Ch. This ype o complemen a i y is encoun e ed in choice unc ions unde
p opo ional cons ain s and lowe bounds, and is also obse ed in ma chings in ol ing
couples. The p esence o his complemen a i y is known o lead o he nonexis ence
o a s able ma ching (Nguyen and Voh a (2019), Bi ó e al. (2010), Ehle s e al. (2014),
F agiadakis, Iwasaki, T oyan, Ueda, and Yokoo (2016), F agiadakis and T oyan (2017)).
Impo an ly, his complemen a i y no only implies he absence o s able ma chings bu
also ules ou he exis ence o mechanisms ha sa is y he p ope ies o PE, IR, and GSP,
as equi ed by ou necessi y o accessibili y.
7I a pa h-independen choice unc ion induces a ma oid cons ain , i sa is ies he law o agg ega e
demand (Yokoi (2019)). Consequen ly, his class o choice unc ions gua an ees he exis ence o s able and
SP mechanisms (Ha ield and Milg om (2005)).
8Bando and Kawasaki (2021) in oduced a b oade class o choice unc ions and s udied dynamic ma ch-
ing. The cons ain s induced by he choice unc ions a e also σ-accessible.
496 Imamu a and Kawase Theo e ical Economics 20 (2025)
4. Se ing wi h endowmen s
In his sec ion, we es ablish ha a g-ma oid is a maximal domain o he exis ence o
PE, IR, and SP mechanisms in a se ing wi h endowmen s. To demons a e his, we i s
p o e ha a TTC mechanism sa is ies PE, IR, and GSP i he cons ain s a e g-ma oid.
Subsequen ly, we cons uc a ma ke ha pe mi s no PE, IR, and SP mechanisms o
each cons ain Fs∗ ha is no a g-ma oid.
4.1 Mo i a ing example
We begin wi h he ollowing example, a simpli ied e sion o one ound in Delac é az,
Komine s, and Tey elboym (2023), ha illus a es ha no mechanism can simul ane-
ously achie e PE, IR, and SP unde gene al cons ain s. Speci ically, Delac é az, Komin-
e s, and Tey elboym (2023) demons a ed ha no mechanism sa is ies PE, IR, and SP
unde mul idimensional knapsack cons ain s.9
Example 4. Suppose ha he e a e h ee s uden s, 1, 2, 3, and h ee schools, s1,s2,s3.
The p e e ence io each s uden iis gi en as
1=(s3s1s2∅),2=(s3s1s2∅),3=(s2s3∅s1).
Fo his p e e ence, s uden 1 p e e s school s3 he mos and leas p e e s he ou side
op ion ∅. The cons ain Fso each school sis gi en as
Fs1=∅,{1},{2},{3},Fs2=∅,{1},{2},{3},{1, 2},Fs3=∅,{1},{2},{3}.
He e, Fs1and Fs3a e (uni ) capaci y cons ain s, whe eas Fs2is no . Indeed, {1, 2},{3}∈
Fs2,bu {1, 3},{2, 3}/∈Fs2. Cons ain s such as Fs2appea as budge cons ain s (e.g.,
s uden 3 equi es mo e schola ship money). The endowmen s o s uden s 1 and 2 a e
s2, and he endowmen o s uden 3 is s3.
I is no di icul o see ha he e exis only wo PE and IR ma chings:
μ1=(1, s3),(2, s1),(3, s2)and μ2=(1, s1),(2, s3),(3, s2).
He e, i s uden 1 mis epo s he p e e ence as
1=(s3s2∅s1)whe eas he o he s u-
den s epo hei ue p e e ences, hen μ1is a unique PE and IR ma ching. Simila ly, i
s uden 2 mis epo s he p e e ence as
2=(s3s2∅s1)whe eas he o he s uden s epo
hei ue p e e ences, hen μ2is a unique PE and IR ma ching. Hence, in any PE and IR
mechanism, ei he s uden 1 o 2 can be be e o by mis epo ing his/he p e e ence,
depending on whe he he ou come o ue epo ing is μ1o μ2.
The example aises he ques ion o which cons ain s uc u e is c ucial o he exis-
ence o PE, IR, and SP mechanisms. We iden i y ha a gene alized ma oid (g-ma oid)
is a “necessa y and su icien ” condi ion o cons ain s o gua an ee exis ence.
9In he model wi h mul idimensional knapsack cons ain s, he e is a ini e se o se ice D. Each amily
i∈Ihas se ice needs νi=(νi
d)∈Z|D|
≥0. Each loca ion s∈Shas a se ice capaci y p o ile κs=(κs
d)∈Z|D|
≥0.
The cons ain o each school sis ep esen ed by Fs≡{I⊆I:i∈Iνi
d≤κs
d o all d∈D}.
Theo e ical Economics 20 (2025) E icien and s a egy-p oo mechanism 497
4.2 Mechanism o g-ma oid cons ain s
We p o ide a TTC mechanism ha sa is ies PE, IR, and GSP when he cons ain s a e
g-ma oid. We de i e his mechanism by u ilizing he TTC-M mechanism in oduced by
Suzuki, Tamu a, and Yokoo (2018), Suzuki e al. (2023). The TTC-M mechanism main-
ains PE, IR, and GSP o any dis ibu ional cons ain ha can be ep esen ed by an
M-con ex se on he ec o o he numbe o s uden s assigned o each school. Le
χe∈{0, 1}Ebe he e h uni ec o . A se o in ege ec o s V⊆ZE
≥0is an M-con ex se
i , o all , ∈Vand all e∈Ewi h e>
e, he eexis s ∈Ewi h <
such ha
−χe+χ ∈Vand +χe−χ ∈V(Mu o a (2003)).
No e ha he TTC-M mechanism canno be di ec ly applied o ou se ing. The p i-
ma y eason o his is ha in ou se ing, he cons ain s a e no imposed on he numbe
o s uden s assigned o each school, bu a he on he ma ched s uden –school pai s. In
addi ion, ou se ing allows s uden s o be unma ched, whe eas hei model does no .
To u ilize he TTC-M mechanism, we cons uc a i ual ma ke (I,˜
S,(˜
i)i∈I,˜
F,˜ω)
om he gi en ma ke (I,S,(i)i∈I,F,ω). The se o schools in he i ual ma ke is
de ined as he se o s uden –school pai s ˜
S:={(i,s):i∈I,s∈S∪{∅}}.Eachs uden
i∈Ihas a s ic p e e ence ˜
io e ˜
Ssuch ha o any (i1,s1),(i2,s2)∈˜
S,weha e
(i) (i1,s1)˜
i(i2,s2)⇐⇒ s1is2i i1=i2=i
(ii) (i1,s1)˜
i(i2,s2)i i1=iand i2= i.
The dis ibu ional cons ain ˜
F⊆Z˜
S
≥0is de ined as
˜
F:=ν∈{0, 1}˜
S:
(i,s)∈˜
S
ν(i,s)=|I|and (i,s)∈I×S:ν(i,s)=1∈F.
The endowmen unc ion sa is ies ˜ω(i)=(i,ω(i)) o each i∈I.Wewilldemons a e
ha ˜
Fis an M-con ex se i Fis a g-ma oid.
The TTC-M mechanism uns on he i ual ma ke as ollows. Le ▷be a com-
mon p io i y o de o e he s uden s I. Wi hou loss o gene ali y, we may assume
ha 1 ▷2▷···▷n. In each ound, e e y ( i ual) school (i,s)∈˜
Sselec s a s uden .
I (i,s)belongs o he endowmen ma ching, hen i selec s i.O he wise,
(i,s)selec s
he highes p io i y s uden among he s uden s i o which (i,s)can be added o he
cu en ma ching by emo ing (i,ω(i)) wi hou iola ing easibili y. This mechanism
gi es he selec ed s uden he igh o ob ain a sea . Each s uden selec s he igh o
ob ain he op applicable school sea . Subsequen ly, s uden s wi h such igh s can ade
sea s among hemsel es by cons uc ing ading cycles. Implemen he ade indica ed
by his cycle, and all he in ol ed s uden s a e emo ed om he ma ke . I any s uden s
emain, he p ocedu e con inues.
Fo cla i y, we p o ide an example o how ou TTC mechanism wo ks.
Example 5. Le I={1, 2, 3, 4, 5}and S={s1,s2}. Suppose ha s uden s 1 and 2 p e e
s2,s1,∅in his o de , and s uden s 3, 4, and 5 p e e s1,s2,∅in his o de . The cons ain s
498 Imamu a and Kawase Theo e ical Economics 20 (2025)
Algo i hm 3: Gene alized TTC.
inpu : ama ke (I,S,(i)i∈I,F,ω)
ou pu : a ma ching ˜μ
1Le μ(0)←{(i,ω(i)):i∈I},˜μ(0)←∅,andI(0)←I;
2 o k←1, 2, do
3i I(k−1)=∅ hen e u n ˜μ(k−1);
4 o each i∈I(k−1)do
5Le S(k)
i←{s∈S∪{∅}:(μ(k−1) {(i,ω(i))})∪˜μ(k−1)∪{(i,s)}∈F(∃i∈
I(k−1))};
6Le p(k)
ibe he mos p e e ed school in S(k)
i o i;
7ipoin s o (i,p(k)
i);
8 o each (i,s)∈{(i,p(k)
i):i∈I(k−1)}do
9i (i,s)∈μ(k−1) hen (i,s)poin s o i;
10 else
11 Le I(k)
(i,s)←{i∈I(k−1):(μ(k−1) {(i,ω(i))})∪˜μ(k−1)∪{(i,s)}∈F};
12 (i,s)poin s o he mos p io i ized (smalles index) s uden in I(k)
(i,s);
13 Iden i y a cycle (i1,(i1,p(k)
i1),i2,(i2,p(k)
i2),,i ,(i ,p(k)
i ));
14 μ(k)←μ(k−1) {(i1,ω(i1)),,(i ,ω(i ))};
15 ˜μ(k)←˜μ(k−1)∪{(i1,p(k)
i1),,(i ,p(k)
i )};
16 I(k)←I(k−1) {i1,,i };
Fis a g-ma oid ha is de ined as he agg ega ion o
Fs1=I⊆I:I∩{2, 3, 5}≤1and Fs2=I⊆I:1≤I≤2.
Le he endowmen s be (ω(1),ω(2),ω(3),ω(4),ω(5))=(s1,s1,s2,∅,∅), ha is, heen-
dowmen ma ching is μ(0)={(1, s1),(2, s1),(3, s2)}.
In ound 1 o Algo i hm 3, s uden 1 poin s o (1, s2),(1, s2)poin s o 1, s u-
den 2 poin s o (2, s2),(2, s2)poin s o 1, and so on (see Figu e 2a). No e ha
{(2, s1),(3, s2),(2, s2)}is in Fal hough i is no a ma ching. The cycle iden i ied a
line 13 is (1, (1, s2)). Hence, we ob ain μ(1)={(2, s1),(3, s2)},˜μ(1)={(1, s2)},and
I(1)={2, 3, 4, 5}.
In ound 2, he cycle iden i ied a line 13 is (2, (2, s2),3,(3, s1))(see Figu e 2b). Thus,
we ob ain μ(2)=∅,˜μ(2)={(1, s2),(2, s2),(3, s1)},andI(2)={4, 5}.
In ound 3, he e a e wo cycles (4, (4, s1)) and (5, (5, ∅)) (see Figu e 2c). No e ha
s uden 5 canno poin o s1, as s uden 3 was ma ched o s1in ound 2, and, he e-
o e, s1/∈S(3)
5. The ades indica ed by hese cycles a e implemen ed in ounds 3 and 4.
Consequen ly, we ob ain he ma ching ˜μ(4)={(1, s2),(2, s2),(3, s1),(4, s1)}.
Theo e ical Economics 20 (2025) E icien and s a egy-p oo mechanism 499
Figu e 2. Cycles ob ained by he TTC in Example 5. The blue and ed a ows ep esen he
ela ionship o which s uden s and i ual schools a e poin ing, espec i ely. Vi ual schools ha
ha e no been poin ed o by any s uden a e omi ed.
No e ha a ading cycle can be in e p e ed as an al e na ing cycle in he exchange
g aph o a g-ma oid in e sec ion. This co espondence can be es ablished by cons uc -
ing an ins ance o he g-ma oid in e sec ion p oblem whe e he common g ound se is
he se o s uden –school pai s ˜
S. One g-ma oid is he dis ibu ional cons ain ˜
F,and
he o he is a pa i ion ma oid M ha ensu es ha each s uden appea s a mos once.
In o he wo ds, X∈Mi |X∩{(i,s)∈˜
S:s∈S∪{∅}}|≤1 o alli∈I. Fo a easible ma ch-
ing μ, he exchange g aph is a di ec ed bipa i e g aph wi h bipa i ion μand ˜
S μ.A
pai (y,x)∈μ×(˜
S μ)is an a c i (μ {y})∪{x}∈˜
Fand (x,y)∈(˜
S μ)×μis an a c i
(μ {y})∪{x}∈M. To p ese e he easibili y o ma ching a e ading, i is su icien
o selec a cycle in he exchange g aph ha does no con ain sho cu s (Mu o a (1996)).
A s anda d me hod o selec ing such a cycle is o selec a sho es cycle. Howe e , such
a selec ion ule does no sa is y s a egy-p oo ness (Imamu a and Kawase (2024)). The
TTC-M mechanism ins ead selec s cycles wi hou sho cu s by u ilizing he p io i y o -
de .
Fo mally, ou TTC mechanism is desc ibed in Algo i hm 3. A he beginning o ound
k, he se o emaining s uden s is I(k−1), and each s uden i∈I(k−1)is ma ched wi h
μ(k−1)(i)=(i,ω(i)).Eachs uden i∈I I(k−1)exi s he ma ke ma ched wi h ˜μ(k−1)(i).
The se o schools o which s uden i∈I(k−1)has a chance o being ma ched wi h is
ep esen ed as S(k)
i. Then each s uden i∈I(k−1)poin s o (i,p(k)
i),whe ep(k)
iis he
mos p e e ed school in S(k)
i. Each i ual school (i,s)poin s o he mos p io i ized
s uden iwho (i,s)can add by emo ing (i,ω(i)).
We p o e he ollowing heo em.
Theo em 4. The gene alized TTC mechanism (Algo i hm 3) sa is ies PE, IR, and GSP i
he dis ibu ional cons ain s o m a g-ma oid. Addi ionally, Algo i hm 3can be imple-
men ed o un in ime O(|I|2·|S|)i we assume ha he easibili y o a ma ching can be
checked in a cons an ime.
P oo . Recall ha he TTC-M mechanism sa is ies PE, IR, and GSP when he dis i-
bu ional cons ain is ep esen ed by an M-con ex se on he ec o o he numbe o
s uden s assigned o each school (Suzuki e al. (2023)). The e o e, o demons a e ha
500 Imamu a and Kawase Theo e ical Economics 20 (2025)
Algo i hm 3sa is ies PE, IR, and GSP, i is su icien o p o e ha ˜
Fis an M-con ex se
i Fis a g-ma oid. Suppose ha Fis a g-ma oid. Then F={ν⊆˜
S:ν∩(I×S)∈F}is
also a g-ma oid by de ini ion. Fu he , ˜
Fcan be ob ained om Fby unca ing i wi h
ca dinali y |I|(i.e., ˜
F={ν∈F:|ν|=|I|}), and such a unca ion induces a ma oid base
amily (Ta dos (1985)). As he class o ma oid base amilies is a subclass o M-con ex
se s (Mu o a (2016)), Fis an M-con ex se .
Nex we discuss he compu a ional complexi y o Algo i hm 3. As a leas one s u-
den is ixed in each i e a ion, he numbe o i e a ions is a mos O(|I|).The un-
ning ime o each i e a ion is O(|I|·|S|). The e o e, he o al unning ime is a mos
O(|I|2·|S|).
4.3 Impossibili y o non-g-ma oid cons ain s
Nex we demons a e ha he g-ma oid s uc u e is necessa y o he exis ence o a
mechanism ha sa is ies PE, IR, and SP.
Theo em 5. Fix a se o s uden s I, a se o schools Swi h |S|≥3, and a school s∗wi h
he cons ain Fs∗. Suppose ha Fs∗is no a g-ma oid. Then he e mus exis a ma ke
(I,S,(Fs)s∈S,ω)wi h s∗∈Sand Fs={X⊆I:|X|≤1} o all s∈S {s∗}such ha no
mechanism simul aneously sa is ies PE, IR, and SP.
P oo .As
Fs∗is no a g-ma oid, he e exis subse s Xand Yin Fs∗and a s uden ein
X Y, such ha we ha e he al e na i es
(i) X {e}/∈Fs∗and (X {e})∪{e}/∈Fs∗ o any e∈Y X
(ii) Y∪{e}/∈Fs∗and (Y∪{e}) {e}/∈Fs∗ o any e∈Y X.
He e, we p o ide he p oo o he case in which (i) holds. We de e he p oo o he case
when (ii) holds o Appendix A, as i can be demons a ed in a simila manne .
Suppose ha he e exis X,Y∈Fs∗and e∈X Ysuch ha X {e}/∈Fs∗and (X
{e})∪{ }/∈Fs∗ o any ∈Y X.Le Z∈Fs∗be a se o s uden s such ha (X∩Y)⊆
Z⊆(X∪Y) {e}.Suchase Zmus exis because Ysa is ies he condi ion. Among all
se s Z ha sa is y his condi ion, we selec a se ha maximizes |X∩Z|.
We conside wo cases sepa a ely: (a) |X Z|=1and(b)|X Z|≥2.
Case (a): |X Z|=1 In his case, we ha e X∩Z=X {e}. In addi ion, we ha e |Z X|≥
2 because (X {e})∪J=Z∈Fs∗by se ing J=Z X. We selec wo s uden s x,y∈Z X
a bi a ily (see Figu e 3). We conside a ma ke in which he se o schools is S={s∗, ,u}
and F =Fu={I⊆I:|I|≤1}. Addi ionally, le he endowmen s be ω(e)= ,ω(i)=s∗
o each i∈Z,andω(i)=∅ o each i/∈Z∪{e}. The endowmen ma ching μ0 o his
ma ke is easible because μ0(s∗)=Z,|μ0( )|=1, and |μ0(u)|=0≤1.
Theo e ical Economics 20 (2025) E icien and s a egy-p oo mechanism 501
Figu e 3. Case (a).
Suppose ha he s uden s’ p e e ences a e gi en as
•
e=(s∗ ···)
•
x=( us∗···)
•
y=( us∗···)
•
i=(s∗···) o each i∈X {e}
•
i=(∅s∗···) o each i∈Z (X∪
{x,y})
•
i=(∅···) o each i/∈X∪Z.
Le μxbe he ma ching such ha xma ches o uand e e y o he s uden ma ches o
he mos a o i e school (o he ou side op ion). Simila ly, le μybe he ma ching such
ha yma ches o uand e e y o he s uden ma ches o he mos a o i e school. Then
μxand μya e easible since μx(s∗)=μy(s∗)=X. Fu he mo e, we can obse e ha only
μxand μya e PE and IR. By symme y, we can assume, wi hou loss o gene ali y, ha
a mechanism ou pu s μx. Suppose ha xmis epo s he p e e ence as
xs∗
x···.
Wi h his mis epo ing, he unique PE and IR ma ching is μy. Hence, any PE and IR
mechanism canno sa is y SP.
Case (b): |X Z|≥2Le ebe an a bi a y s uden in X (Z∪{e})(see Figu e 4). We
conside a ma ke in which he se o schools is S={s∗, ,u}and F =Fu={I⊆I:|I|≤
1}. In addi ion, le he endowmen s be ω(e)= ,ω(e)=u,ω(i)=s∗ o each i∈Z,and
ω(i)=∅ o each i∈I (Z∪{e,e}). The endowmen ma ching μ0 o his ma ke is
easible because μ0(s∗)=Zand |μ0( )|=|μ0(u)|=1.
Suppose ha s uden s’ p e e ences a e de ined as
•
e=(us∗ ···)
•
e=(s∗ u···)
•
i=(s∗···) o each i∈X∩Z
•
i=(∅s∗···) o each i∈Z X
Figu e 4. Case (b).
502 Imamu a and Kawase Theo e ical Economics 20 (2025)
•
i=(s∗∅···) o each i∈X (Z∪{e,e})
•
i=(∅···) o each i/∈X∪Z.
Le μbe he ma ching p oduced by a PE, IR, and SP mechanism. By IR, we ha e X∩Z⊆
μ(s∗)⊆X∪Z.I e/∈μ(s∗), henwemus ha eμ(s∗)⊆Zby he maximali y o |X∩Z|.
Hence, μ(e)= s∗implies μ(e)= s∗. Le us conside h ee subcases depending on μ(e).
Case (b1): μ(e)= .In hiscase,μ(e)= s∗and μ(e)=u. Thismeans ha μis no
PE because eand ecan be be e o by swapping hei alloca ed
schools, which is a con adic ion.
Case (b2): μ(e)=s∗. Suppose ha emis epo s s∗as being unaccep able (i.e., sub-
mi ing
e=(u ···)). Then emus be ma ched wi h uin any PE
and IR ma ching, which con adic s SP.
Case (b3): μ(e)=u.In hiscase,μ(e)= s∗and μ(e)= . Suppose ha emis epo s
ha as being unaccep able (i.e., submi ing
e=(s∗u···)).
Then emus be ma ched wi h s∗because he e exis s a unique
PE and IR ma ching {(i,s∗):i∈X}, which con adic s SP.
5. Discussion and conclusion
5.1 Rela ionship be ween he wo se ings
We discuss he ela ionship be ween he se ings, which can be summa ized as shown in
Table 2. Recall ha he endowmen s a e assumed o be easible in bo h se ings. In he
se ing wi h endowmen s, any easible ma ching in Fcan be se as he ini ial ma ching
μ0. In con as , in he se ing wi hou endowmen s, he ini ial ma ching μ0is es ic ed
o he emp y ma ching, bu i implies ha he emp y ma ching mus be easible in his
se ing. Thus, he necessa y o su icien condi ions o one se ing canno be simply
applied o he o he se ing.
To make his di e ence clea e , le us assume ha he emp y ma ching is easible in
he se ing wi h endowmen s as well. Then he necessa y and su icien condi ion o he
exis ence o a desi ed mechanism in his se ing becomes a ma oid. Since any ma oid
cons ain is σ-accessible o e e y σ, his is a su icien condi ion o he exis ence o a
desi ed mechanism in he se ing wi hou endowmen s.
Table 2. Rela ionship be ween se ings o he exis ence o a desi ed mechanism.
Se ing Assump ion Ini ial Endowmen Condi ion
Wi hou endowmen s ∅∈Fμ0=∅ (σ-)accessible
Wi h endowmen s F= ∅ μ0∈Fg-ma oid
Including bo h ∅∈Fμ0∈Fma oid
Theo e ical Economics 20 (2025) E icien and s a egy-p oo mechanism 503
5.2 Two ou o PE, IR, and GSP
In bo h se ings, wi h and wi hou endowmen s, any wo o he h ee p ope ies PE, IR,
and GSP can be achie ed unde gene al cons ain s. I is e iden ha he mechanism
ha always ou pu s he endowmen ma ching sa is ies bo h IR and GSP. To sa is y PE and
GSP, we can u ilize a gene alized SD mechanism ha sequen ially assigns each s uden
o he bes school in a p ede e mined o de , ensu ing ha he emaining s uden s can
be easibly assigned. To obse e ha he ou come μo he mechanism is PE, suppose, o
he con a y, ha he e exis s a easible ma ching μ ha is a Pa e o imp o emen o μ.
Le i∗be he i s s uden assigned o a school o he han μ(i∗)in he mechanism. Then
μ(i∗)i∗μ(i∗); howe e , his con adic s he beha io o he gene alized SD mecha-
nism. Addi ionally, he mechanism is GSP because i a s uden does no selec he p e-
e ed school in he u n, she will no ecei e ano he chance o do so. This mechanism
is equi alen o he GSDPC p oposed by Kamiyama (2013). PE and IR can be achie ed by
using he CSD mechanism (Imamu a and Kawase (2024)). The CSD mechanism sequen-
ially assigns each s uden o he bes school in a p ede e mined o de , while ensu ing
ha he emaining s uden s can be assigned o p oduce a easible IR ma ching. Clea ly,
his mechanism sa is ies IR. The p ope y o PE ollows om he ac ha a ma ching is
PE i i is PE unde he IR cons ain . No e ha he CSD mechanism is no SP because
each s uden is assigned o a school depending on he p e e ences o he la e s uden s.
5.3 Conclusion
This s udy in es iga ed he exis ence o e icien and s a egy-p oo mechanisms in in-
di isible goods alloca ion p oblems unde gene al cons ain s.
In he se ing wi hou endowmen s, we demons a ed ha he SD mechanism sa is-
ies PE, IR, and GSP i he cons ain s a e σ-accessible o a common σ.Wealsop o ed
ha accessibili y is a necessa y condi ion o ensu e he exis ence o PE, IR, and GSP
mechanisms. Iden i ying he mos gene al class o cons ain s unde which PE, IR, and
SP mechanisms exis emains open. In a se ing wi h endowmen s, we e ealed ha he
g-ma oid is a maximal domain unde which we can gua an ee he exis ence o a PE, IR,
and SP mechanism. The same s a emen holds ue e en i we eplace SP wi h GSP.
In a se ing wi hou endowmen s, we o mula e an in ege linea p og am (ILP) o
de e mine he exis ence o PE, IR, and SP mechanisms o a gi en ma ke . In he case
whe e I={1, 2, 3},S={s1,s2},Fs1={X⊆I:|X|= 2},andFs2={X⊆I:|X|≤1}, he
Gu obi sol e wi h he ILP e ealed ha no such mechanism exis s. The i educible in-
consis en subsys em ob ained o he ma ke con ains ela ionships among 43 p e e -
ences, making i challenging o disce n i s unde lying s uc u e. Whe he accessibili y is
necessa y o he exis ence o PE, IR, and SP mechanisms emains o u u e esea ch.
In a se ing wi h endowmen s, Delac é az, Komine s, and Tey elboym (2023)p e-
sen ed s onge nonexis ence esul s unde mul idimensional knapsack cons ain s. Fo
example, he desi ed mechanism does no exis e en when PE and IR a e eplaced by
he p ope y ha a mechanism Pa e o imp o es upon e e y Pa e o-ine icien endow-
men . We call his p ope y Pa e o-imp o ing (PI). Fo mally, a mechanism ϕis PI i , o
any p e e ence p o ile Ia which he endowmen ma ching μ0is Pa e o-ine icien ,
504 Imamu a and Kawase Theo e ical Economics 20 (2025)
ϕ[I](i)iμ0(i) o all i∈Iand ϕ[I](i)iμ0(i) o some i∈I. PI is a weake equi e-
men han he conjunc ion o PE and IR. Delac é az, Komine s, and Tey elboym (2023)
showed by example ha no PI and SP mechanism exis s unde mul idimensional knap-
sack cons ain s. In con as , a PI and SP mechanism exis s in Example 4.Thus,we
a e le wi h he ques ion, “Which class o cons ain s is necessa y and su icien o he
exis ence o PI and SP mechanisms?”
Finally, le us discuss he case in which he endowmen ma ching μ0is in easible.
In his case, no IR ma chings exis , especially when e e y s uden p e e s he own en-
dowmen he mos . The e o e, we ha e no op ion bu o abandon IR. Mo eo e , aban-
doning IR is a na u al choice when alloca ing cho es in a se ing wi hou endowmen s.
Ne e heless, e en wi hou IR, we can s ill a ain PE and GSP by employing he GSDPC
mechanism unde any cons ain s, as long as a leas one easible ma ching exis s.
Appendix A: Omi ed pa o he p oo o Theo em 5
He e, we p o ide he p oo o Theo em 5 o he case when (ii) holds.
Suppose ha he e exis X,Y∈Fs∗and e∈X Ysuch ha Y∪{e}/∈Fs∗and (Y∪
{e}) { }/∈Fs∗ o any ∈Y X.Le Z∈Fs∗be a se o s uden s such ha (X∩Y)∪{e}⊆
Z⊆X∪Y.Suchase Zmus exis because Xsa is ies he condi ion. Among all se s Z
ha sa is y his condi ion, we selec a se ha minimizes |X∩Z|.
We conside wo cases sepa a ely: (c) |X∩Z|=|X∩Y|+1and(d)|X∩Z|≥|X∩
Y|+2.
Case (c): |X∩Z|=|X∩Y|+1 In his case, we ha e X∩Z=(X∩Y)∪{e}. In addi ion,
we ha e |Y Z|≥2 because (Y∪{e}) J=Z∈Fs∗by se ing J=Y Z. We selec wo
s uden s x,y∈Y Za bi a ily (see Figu e 5). We conside a ma ke in which he se o
schools is S={s∗, ,u}and F =Fu={I⊆I:|I|≤1}. Addi ionally, le he endowmen s
be ω(e)= ,ω(i)=s∗ o each i∈Yand ω(i)=∅ o each i/∈Y∪{e}. The endowmen
ma ching μ0 o his ma ke is easible because μ0(s∗)=Y,|μ0( )|=1, and |μ0(u)|=0≤
1.
Suppose ha he s uden s’ p e e ences a e gi en as
•
e=(s∗ ···)
•
x=( us∗···)
•
y=( us∗···)
•
i=(s∗···) o each i∈Z {e}
•
i=(∅s∗···) o each i∈Y (Z∪
{x,y})
•
i=(∅···) o each i/∈Z∪Y.
Figu e 5. Case (c).
