Local and Global Consis ency P ope ies o S uden Placemen ∗
Be ina Klaus†Flip Klijn‡
Ma ch 2011
Abs ac
In he con ex o esou ce alloca ion on he basis o p io i ies, E gin (2002) iden i ies a
necessa y and su icien condi ion on he p io i y s uc u e such ha he s uden -op imal
s able mechanism sa is ies a consis ency p inciple. E gin (2002) o mula es consis ency as a
local p ope y based on a ixed popula ion o agen s and ixed esou ces – we e e o his
condi ion as local consis ency and o his condi ion on he p io i y s uc u e as local acyclici y.
We iden i y a ela ed bu s onge necessa y and su icien condi ion (uni acyclici y) on he
p io i y s uc u e such ha he s uden -op imal s able mechanism sa is ies a mo e s anda d
global consis ency p ope y.
Nex , we p o ide necessa y and su icien condi ions o he s uden -op imal s able mech-
anism o sa is y con e se consis ency p inciples. We iden i y a necessa y and su icien con-
di ion (local shi - eeness) on he p io i y s uc u e such ha he s uden -op imal s able
mechanism sa is ies local con e se consis ency. In e es ingly, local acyclici y implies local
shi - eeness and hence he s uden -op imal s able mechanism mo e equen ly sa is ies local
con e se consis ency han local consis ency. Finally, in o de o he s uden -op imal s able
mechanism o be globally con e sely consis en , one again has o impose uni acyclici y on
he p io i y s uc u e. Hence, uni acyclici y is a necessa y and su icien condi ion on he
p io i y s uc u e o he s uden -op imal s able mechanism o sa is y global consis ency o
global con e se consis ency.
JEL classi ica ion: D63, C78.
Keywo ds: acyclici y, consis ency, con e se consis ency, s uden placemen .
1 In oduc ion
A s uden placemen p oblem is de e mined by a se o s uden s, a se o posi ion ypes, he
numbe o a ailable posi ions – he quo a – o each ype, and he s uden s’ s ic p e e ences o e
posi ion ypes (e.g., a posi ion ype could ep esen he admission o a college o uni e si y) and
emaining unassigned. A s uden placemen mechanism assigns o any gi en s uden placemen
∗Be ina Klaus g a e ully acknowledges inancial suppo om he Ne he lands O ganisa ion o Scien i ic
Resea ch (NWO) unde g an VIDI-452-06-013. Flip Klijn g a e ully acknowledges suppo om Plan Nacional
I+D+I (ECO2008-04784), Gene ali a de Ca alunya (SGR2009-01142), he Ba celona GSE Resea ch Ne wo k
and he Consolide -Ingenio 2010 (CSD2006-00016) p og am. A i s d a o his pape was w i en while Flip
Klijn was isi ing Ha a d Business School. He g a e ully acknowledges a esea ch ellowship om HBS.
†Facul y o Business and Economics, Uni e si y o Lausanne, In e ne 538, CH-1015 Lausanne, Swi ze land;
e-mail: be [email protected]
‡Co esponding au ho : Ins i u e o Economic Analysis (CSIC), Campus UAB, 08193 Bella e a (Ba celona),
Spain; e-mail: [email protected]
1
p oblem an alloca ion o he posi ion ypes o he s uden s such ha e e y s uden ecei es a
mos one posi ion and quo as a e binding. In con as o so-called house alloca ion p oblems,
whe e an assignmen is made on he basis o s uden s’ p e e ences o e posi ion ypes alone,1we
assume ha in a s uden placemen p oblem addi ional in o ma ion is a ailable.2Fo ins ance,
college admissions o unde g adua e s uden s a e o en based on ankings ob ained om one o
se e al en ance exams. Then, s uden s who achie ed highe es sco es in he en ance exam
o a ce ain college ha e highe p io i y o admission a ha college han s uden s wi h lowe
es sco es. We will model his si ua ion using s ic p io i y ankings o indi iduals o each
posi ion ype (possibly using ie-b eaking). We call he collec ion o s ic p io i y ankings a
p io i y s uc u e.
A placemen mechanism iola es he p io i y o s uden i o posi ion xi he e exis p e e -
ences unde which s uden ien ies s uden jwho ob ains xe en hough ihas a highe p io i y
o x han j. A placemen mechanism is ai i i ne e iola es he p io i y o any s uden . E -
gin (2002) ocuses on he so-called s uden -op imal s able mechanism (in oduced by Gale and
Shapley, 1962) since i is ai and Pa e o supe io o any o he ai placemen mechanism. E -
gin (2002, Theo em 1) p o ides a necessa y and su icien “acyclici y” condi ion on he p io i y
s uc u e o he s uden -op imal s able mechanism o sa is y se e al appealing p ope ies. In
pa icula , he conside s a no ion o consis ency. Howe e , E gin (2002) o mula es consis ency
as a local p ope y based on a ixed popula ion o agen s and ixed esou ces – we e e o his
condi ion as local consis ency and o his condi ion on he p io i y s uc u e as local acyclici y.
E gin’s (2002) consis ency no ion is di e en om he s anda d consis ency no ion since
he se o s uden s and he quo as a e ixed in E gin’s (2002) model. We iden i y a ela ed
bu s onge necessa y and su icien condi ion (uni acyclici y) on he p io i y s uc u e such
ha he s uden -op imal s able mechanism sa is ies a mo e s anda d global consis ency p ope y
(Theo em 2).3
Nex , we a e in e es ed in a p ope y ha is closely ela ed o consis ency, namely con-
e se consis ency. Con e se consis ency e e s o an in e se o he educ ion ope a ion ha
consis ency uses. Thomson (2009, page 30) desc ibes con e se consis ency as a p ope y o “de-
cen alizabili y”: gi en some p oblem, i an alloca ion is chosen o each o i s associa ed educed
wo-agen p oblems, hen i should be chosen o he p oblem in ol ing he whole g oup. Con-
e se consis ency has some p ac ical appeal whene e small p oblems a e much easie o sol e
han la ge ones. Fo wo-sided ma ching p oblems, he wo-agen subg oup assump ion ha
con e se consis ency is based on is usually adjus ed o include somewha la ge g oups o agen s
(Thomson, 2009, page 209). Gi en he ma ching cha ac e o ou model (and he ac ha we
a e in e es ed in he p ope ies o a speci ic ma ching mechanism), wo pape s explo ing aspec s
o con e se consis ency o ma iage p oblems (one- o-one ma ching p oblems) a e Sasaki and
Toda (1992) and ¨
Ozkal-San e (2009). Sasaki and Toda (1992) show ha he co e co espon-
dence o ma iage ma ke s sa is ies con e se consis ency and ha his p ope y is pa o a co e
1Some imes i is also assumed ha exac ly one posi ion o each ype is a ailable. Some ecen a icles on
house alloca ion p oblems a e E gin (2000), Ehle s (2002), Ehle s e al. (2002), and Ehle s and Klaus (2003, 2006,
2007).
2See, o ins ance, Balinski and S¨onmez (1999), E gin (2002), and Kes en (2006).
3Fo ins ance, Thomson’s (2009, page 16) “Fundamen al De ini ion” o consis ency deals wi h a a iable
popula ion se up and imposes he consis ency equi emen on all subpopula ions as well.
2
cha ac e iza ion; we b ie ly discuss ¨
Ozkal-San e (2009) below. Fo an o e iew o he li e a u e
on con e se consis ency in o he con ex s we e e o Thomson (2004, 2009).
¨
Ozkal-San e (2009, Example 3.2) shows ha , depending on he p io i y s uc u e, he
s uden -op imal s able mechanism may no sa is y con e se consis ency. In iew o his neg-
a i e esul , he e a e (a leas ) wo ways o p oceed. The i s app oach is o expand he
s uden -op imal s able mechanism o ob ain a con e sely consis en (mul i- alued) co espon-
dence. A pa icula ly in e es ing co espondence is he minimal expansion ha is con e sely con-
sis en . ¨
Ozkal-San e ook his app oach and he main esul is he iden i ica ion o he minimal
con e sely consis en ex ension o he s uden -op imal s able mechanism (¨
Ozkal-San e , 2009,
Theo em 4.1). In iew o he p ac ical and heo e ical ele ance o he s uden -op imal s able
ma ching mechanism, a second app oach would consis o he iden i ica ion o condi ions unde
which i is con e sely consis en . Ou pape akes his app oach.
Simila ly o he p e ious discussion on consis ency, one can conside local con e se consis-
ency based on a ixed se o s uden s and a ixed quo a ec o , o allow o he gene al a iable
popula ion and esou ce con ex and conside (s anda d) global con e se consis ency. We i s
iden i y a necessa y and su icien condi ion (local shi - eeness) on he p io i y s uc u e such
ha he s uden -op imal s able mechanism sa is ies local con e se consis ency (Theo em 3). In-
e es ingly, local acyclici y implies local shi - eeness (Lemma 2) and hence he s uden -op imal
s able mechanism mo e equen ly sa is ies local con e se consis ency han local consis ency
(Co olla y 1). Fu he mo e, in si ua ions whe e a mos one posi ion pe posi ion ype is a ail-
able, bo h condi ions coincide (Lemma 3) and he s uden -op imal s able mechanism sa is ies
local con e se consis ency i and only i i sa is ies local consis ency (Co olla y 2).
Finally, in o de o he s uden -op imal s able mechanism o be globally con e sely consis-
en , one again has o impose uni acyclici y on he p io i y s uc u e (Theo em 4). Hence, he
s uden -op imal s able mechanism is globally con e sely consis en i and only i i is globally
consis en (Co olla y 3).
The pape is o ganized as ollows. In Sec ion 2 we in oduce he s uden placemen model
and he s uden -op imal s able mechanism. Sec ion 3 (4) con ains he local and global (con e se)
consis ency esul s men ioned abo e.
2 S uden Placemen
Le ¯
N={1,...,n}deno e a se o s uden s wi h n≥3. Le X={x1,...,xp}deno e a se o
( eal) posi ion ypes wi h |X| ≥ 3.4Fo each posi ion ype x∈X, a mos ¯qx∈Ncopies a e
a ailable wi h 1 ≤¯qx≤ | ¯
N|. Fu he mo e, while ¯qxdeno es he maximal numbe o posi ions o
ype x ha migh become a ailable, by qx∈ {0,1,...,¯qx}we deno e he numbe o posi ions, he
quo a,o posi ion ype x ha a e a ailable. A quo a ec o q≡(qx)x∈Xdeno es he quo a o all
posi ion ypes. No e ha we use he e m “posi ion x” when we e e o one o he qxposi ions
o posi ion ype x. Le 0 deno e he null posi ion, which does no belong o X; “ ecei ing he
null posi ion” means “no ecei ing any posi ion.” Since he null posi ion is eely a ailable, we
simply assume q0=∞.
4The cases |¯
N| ≤ 2 o |X| ≤ 2 a e i ial because hen he cen al p ope ies o he a icle (consis ency and
con e se consis ency) ha e no bi e. Fu he mo e, ou esul s emain unchanged o in ini e ¯
No X.
3
Each s uden i∈¯
Nis equipped wi h a s ic , ansi i e, and comple e p e e ence ela ion
Rio e X∪ {0}, i.e., Riis a linea o de o e X∪ {0}. Gi en x, y ∈X∪ {0},x Piymeans ha
s uden is ic ly p e e s x o y. I x Pi0, hen posi ion xis accep able o s uden i, o he wise i
is unaccep able (and 0 Pix). Le Rdeno e he se o s ic , ansi i e, and comple e p e e ence
ela ions o e X∪ {0}. Fo each N⊆¯
N,RNis he se o (p e e ence) p o iles R= (Ri)i∈N
such ha o all i∈N,Ri∈ R. Gi en N′⊆N⊆¯
Nand R∈ RN, le RN′deno e he p o ile
(Ri)i∈N′; i is he es ic ion o p o ile R o he se o s uden s N′.
Le x∈X. We call a linea o de ≻xo e ¯
Nap io i y o de ing o posi ion ype x. Gi en
i, j ∈¯
N,i6=j, s uden ihas a highe p io i y o posi ion x han s uden ji i≻xj. A p io i y
s uc u e is a p o ile ≻= (≻x)x∈Xspeci ying o each posi ion ype a p io i y o de ing.
A(s uden ) placemen p oblem (N, R, q) consis s o a ( ini e) se o s uden s N⊆¯
N, p e e -
ences R∈ RN, and a quo a ec o q= (qx)x∈Xsuch ha o all posi ions x∈X, 0 ≤qx≤¯qx.
We assume ha he null posi ion is a ailable in any placemen p oblem. Finally, we assume
ha a p io i y s uc u e ≻o e Xis ex e nally gi en (we do no include i in he desc ip ion o
a placemen p oblem because we assume i o be ixed).
Fo each placemen p oblem (N, R, q), each s uden i∈Nis o be alloca ed exac ly one
posi ion in X∪{0} aking quo as as uppe bounds. Fo mally, an alloca ion o (N, R, q) is a lis
α= (αi)i∈Nsuch ha o all i∈N,αi∈X∪ {0}, and o all x∈X,|{i∈N:αi=x}| ≤ qx.
Thus, an alloca ion is by de ini ion easible. No e ha no all a ailable posi ions need o be
assigned. Gi en i∈N, we call αi he allo men o s uden ia α.
Nex , we in oduce he no ion o a educed s uden placemen p oblem and o a educed
alloca ion. Conside a s uden placemen p oblem (N, R, q), an alloca ion α o i , and a subse
N′⊆No s uden s. Then, he educed placemen p oblem (N′, RN′, q(N′, α)) o s uden s N′
a alloca ion αis de ined as he placemen p oblem whe e he se o s uden s equals N′and he
only posi ion ypes ha a e a ailable o hem a e hose no alloca ed o s uden s in N N′a
α, i.e., o all x∈X,q(N′, α)x=qx− |{i∈N N′:αi=x}|. Le αN′deno e he alloca ion
(αi)i∈N′. I is he es ic ion o alloca ion α o he se o s uden s N′. No e ha αN′is an
alloca ion o (N′, RN′, q(N′, α)).
An alloca ion αis indi idually a ional o placemen p oblem (N, R, q) i o each i∈N,
allo men αiis accep able o s uden i.
An alloca ion αis non-was e ul o placemen p oblem (N, R, q) i he e a e no s uden i∈N
and posi ion x∈Xsuch ha x Piαiand |{j∈N:αj=x}| < qx.
An alloca ion α iola es he p io i y o s uden i∈N o placemen p oblem (N, R, q) i
he e exis s a posi ion xsuch ha s uden ihas a highe p io i y o x han one o he s uden s
assigned o i and s uden ip e e s o swi ch o posi ion x, i.e., he e exis x∈Xand j∈N {i}
such ha i≻xj,αj=x, and x Piαi.
A(s uden ) placemen mechanism is a unc ion ϕ ha assigns o each placemen p oblem
(N, R, q) an alloca ion ϕ(N, R, q).
A placemen mechanism ϕis indi idually a ional i o each placemen p oblem (N, R, q),
ϕ(N, R, q) is indi idually a ional o placemen p oblem (N, R, q).
4
A placemen mechanism ϕis non-was e ul i o each placemen p oblem (N, R, q), ϕ(N, R, q)
is non-was e ul o placemen p oblem (N, R, q).
A placemen mechanism ϕis ai (Balinski and S¨onmez, 1999) i o each placemen p oblem
(N, R, q), ϕ(N, R, q) does no iola e he p io i y o any s uden o placemen p oblem (N, R, q).
Gi en a placemen p oblem (N, R, q), we can associa e (N, R, q) wi h a college admissions
p oblem as ollows (Balinski and S¨onmez, 1999): he se o s uden s equals N, he se o posi-
ion ypes Xco esponds o he se o colleges, he quo a ec o qdesc ibes colleges’ quo as,
p e e ences Rco espond o s uden s’ p e e ences o e colleges, and he p io i y s uc u e ≻
is aken o ep esen colleges’ esponsi e p e e ences o e s uden s. Fu he mo e (Balinski and
S¨onmez, 1999, Lemma 2), an alloca ion αis indi idually a ional, non-was e ul, and ai o place-
men p oblem (N, R, q) i and only i he associa ed “ma ching” αis s able o he associa ed col-
lege admissions p oblem, i.e., αis indi idually a ional o (N, R, q) and he e exis s no s uden -
posi ion blocking pai (i, x)∈N×(X∪ {0}) such ha x Piαiand (s1) |{j∈N:αj=x}| < qx
o (s2) he e exis s k∈Nsuch ha αk=xand i≻xk.5
Fo each placemen p oblem (N, R, q), we deno e by ϕ≻(N, R, q) he s uden -op imal s able
alloca ion o placemen p oblem (N, R, q) ha is ob ained by using Gale and Shapley’s (1962)
s uden -p oposing de e ed-accep ance algo i hm:
•A he i s s ep o he s uden -p oposing de e ed-accep ance algo i hm, e e y s uden in
Napplies o he /his a o i e posi ion. Fo each posi ion x∈X∪ {0}, he qxapplican s
who ha e he highes p io i y o x(all applican s i he e a e ewe han qxo x= 0) a e
placed on he wai ing lis o posi ion x, and all o he s a e ejec ed. (I qx= 0, hen all
p oposing s uden s a e ejec ed.)
•A he - h s ep o he s uden -p oposing de e ed-accep ance algo i hm, hose applican s
who we e ejec ed a s ep −1 apply o hei nex bes posi ion. Fo each posi ion
x∈X∪ {0}, he qxapplican s among he new applican s and hose on he wai ing lis
who ha e he highes p io i y o posi ion xa e placed on he upda ed wai ing lis o
posi ion x, and all o he s a e ejec ed.
The s uden -op imal de e ed-accep ance algo i hm e mina es when e e y s uden is on a wai -
ing lis . No e ha he null objec has unlimi ed capaci y and e en ually any s uden is pu on
he wai ing lis o a eal posi ion x∈Xo he null objec . Once he algo i hm ends, posi ions
a e assigned o he s uden s on he espec i e posi ion wai ing lis s and he esul ing alloca ion
is he s uden -op imal s able alloca ion ϕ≻(N, R, q) o he placemen p oblem (N, R, q).
By ϕ≻we deno e he s uden -op imal s able mechanism ha assigns o each placemen
p oblem (N, R, q) he s uden -op imal s able alloca ion ϕ≻(N, R, q).
5The de ini ion o s abili y he e is less gene al han he one o college admissions p oblems because o s uden
placemen p oblems, posi ion ypes always “ ind all s uden s accep able.” Fo mo e de ails on he well-known
college admissions model and basic and well-known esul s o his model, we e e he in e es ed eade o Gale
and Shapley (1962) and Ro h and So omayo (1990).
5

3 Consis ency
3.1 Local Consis ency
E gin (2002) e e s o he s uden -op imal s able mechanism ϕ≻as he “bes ule” and analyzes
o which p io i y s uc u es ≻,ϕ≻sa is ies well-known and desi able p ope ies gi en a ixed se
o s uden s N⊆¯
Nand a ixed quo a ec o q. E gin (2002, Theo em 1) p o ides a necessa y and
su icien acyclici y condi ion (De ini ion 2 below) o he s uden -op imal s able mechanism o
sa is y ei he o Pa e o e iciency,6g oup-s a egy p oo ness,7and a (local!) consis ency p ope y
(E gin, 2002, p. 2494) ha we explain nex .
Loosely speaking, a placemen mechanism is consis en i , whene e some s uden s lea e
wi h hei allo men s, he placemen mechanism alloca es he emaining posi ions among he
s uden s who did no lea e in he same way as in he o iginal placemen p oblem. In o de o
in oduce consis ency o a placemen mechanism in a model whe e he se o agen s and esou ces
a e ixed a p io i, E gin (2002) only equi es a local consis ency check o all educed placemen
p oblems ha a e ob ained om an o iginal placemen p oblem (N, R, q) (Nand qbeing ixed).8
Fo mally, E gin (2002, p. 2493) only equi es ha ϕ≻is consis en on he domain o educed
placemen p oblems ha a e ob ained om a placemen p oblem (N, R, q) when a subse o
agen s N′⊆N ealloca es esou ces a e agen s in N N′ha e le wi h hei allo men s a
ϕ≻(N, R, q).
De ini ion 1. Local consis ency
Le N⊆¯
Nbe a se o s uden s and qa quo a ec o . A placemen mechanism ϕis locally
consis en o (N, q) i o each p o ile R∈ RNand each subse o s uden s N′⊆N: [ o all
i∈N′,ϕi(N′, RN′, q(N′, ϕ(N, R, q))) = ϕi(N, R, q)]. △
Nex , we in oduce E gin’s (2002, p. 2492) acyclici y condi ion o p io i y s uc u es. Again,
since he se o agen s Nand he quo a ec o qa e ixed, acyclici y has a “local cha ac e .”
De ini ion 2 (E gin, 2002).Local cycles and local acyclici y
Le N⊆¯
Nbe a se o s uden s and qa quo a ec o . Gi en a p io i y s uc u e ≻, a local cycle
o (N, q) is cons i u ed o o de ed and dis inc x, y ∈X(qx, qy6= 0) and i, j, k ∈Nsuch ha
he ollowing wo condi ions a e sa is ied:
cycle condi ion i≻xj≻xk≻yiand
c-sca ci y condi ion he e exis disjoin (and possibly emp y) se s Nx, Ny⊆N {i, j, k}such
ha Nx⊆ {l∈N:l≻xj},Ny⊆ {l∈N:l≻yi},|Nx|=qx−1, and |Ny|=qy−1.
A p io i y s uc u e ≻is locally acyclic o (N, q) i i has no local cycles o (N, q). △
I quo as a e all equal o 1, hen he cycle condi ion is su icien o es ablish he exis ence
o a local cycle. Fo o he quo as, he c-sca ci y condi ion limi s he de ini ion o a local cycle
6A placemen mechanism is Pa e o e icien i no assigned alloca ion can be (Pa e o) imp o ed such ha all
s uden s a e weakly be e o and some a e s ic ly be e o .
7A placemen mechanism is g oup-s a egy p oo i no g oup o s uden s, by join ly mis ep esen ing hei
p e e ences, can change hei allo men s such ha all membe s o he g oup a e weakly be e o and some a e
s ic ly be e o .
8Thomson and Zhou (1993) ake a simila “local consis ency” app oach in a model wi h a omless economies.
6
o cases whe e he e indeed exis s uden s’ p e e ences such ha s uden s i,j, and kcompe e
o posi ion ypes xand y(in he absence o his compe i ion, e.g., because he quo as do in
ac no limi he access o he s uden s o posi ions xand y, a local cycle will no lead o he
iola ion o Pa e o e iciency, g oup s a egy-p oo ness, o local consis ency – see E gin, 2002,
o u he discussion).
E gin (2002, Theo em 1, (iii)⇔(i ), p. 2494) cha ac e izes local consis ency o he s uden -
op imal s able mechanism by local acyclici y (E gin, 2002, uses he e ms consis ency and acyclic-
i y wi hou e e ing o hei local cha ac e ).
Theo em 1 (E gin, 2002).Local consis ency o he s uden -op imal s able mechanism
Le N⊆¯
Nbe a se o agen s, qa quo a ec o , and ≻a p io i y s uc u e. Then, ϕ≻is locally
consis en o (N, q)i and only i ≻is locally acyclic o (N, q).
3.2 Global Consis ency
In he li e a u e, consis ency is usually de ined o models wi h a a iable popula ion and a i-
able esou ces.9In o de o dis inguish his s anda d no ion o consis ency om E gin’s local
consis ency p ope y, we will e e o i as global consis ency.
In ou a iable popula ion and a iable esou ces ex ension o E gin’s (2002) model, a mech-
anism ϕis globally consis en i o any se o p esen agen s Nand o any se o a ailable
esou ces ( ep esen ed by a quo a ec o q), i is locally consis en .
De ini ion 3. Global consis ency
A placemen mechanism ϕis globally consis en i i is locally consis en o all (N, q) such ha
N⊆¯
Nand qis a quo a ec o . △
Using E gin’s (2002) esul (Theo em 1), we now iden i y a necessa y and su icien condi ion
o p io i y s uc u e ≻ o gua an ee ha ϕ≻is globally consis en .
De ini ion 4. Uni cycles and uni acyclici y
Gi en a p io i y s uc u e ≻, a uni cycle is cons i u ed o o de ed and dis inc x, y ∈Xand
i, j, k ∈¯
Nsuch ha he ollowing condi ion is sa is ied:
cycle condi ion i≻xj≻xk≻yi.
A p io i y s uc u e ≻is uni acyclic i i has no uni cycles. △
Theo em 2. Global consis ency o he s uden -op imal s able mechanism
Le ≻be a p io i y s uc u e. Then, ϕ≻is globally consis en i and only i ≻is uni acyclic.
P oo . Le ≻be a p io i y s uc u e. By de ini ion, ϕ≻is globally consis en i o all N⊆¯
Nand
all quo a ec o s q,ϕ≻is locally consis en o (N, q). By Theo em 1 (E gin, 2002, Theo em 1,
(iii)⇔(i )), his is equi alen o he p io i y s uc u e ≻being locally acyclic o all N⊆¯
Nand
o all quo a ec o s q. We comple e he p oo by showing ha ≻being locally acyclic o all
N⊆¯
Nand o all qis equi alen o ≻being uni acyclic.
9See E gin (2000) and Thomson (2004, 2009) o he indi isible-objec assignmen se ing and gene al alloca ion
p oblems, espec i ely.
7
I ≻is uni acyclic, hen he cycle condi ion in De ini ion 2 canno be sa is ied o any h ee
agen s i, j, k ∈N⊆¯
N. Hence, ≻is locally acyclic o all N⊆¯
Nand o all q.
Now assume ha ≻is no uni acyclic. Hence, he e exis dis inc x, y ∈Xand i, j, k ∈¯
N
such ha i≻xj≻xk≻yi. Le N={i, j, k}and qsuch ha qx= 1, qy= 1, and o all
z∈X {x, y},qz= 0. Then, we ha e cons uc ed a local cycle o (N, q).
4 Con e se Consis ency
We a e also in e es ed in a p ope y ha is closely ela ed o consis ency: con e se consis ency.
Con e se consis ency e e s o an in e se o he educ ion ope a ion ha consis ency uses.
Gi en some p oblem, i equi es ha i a mechanism o co espondence (pa ially) chooses
an alloca ion o each o i s associa ed educed wo-agen p oblems, hen he (whole) alloca ion
should be chosen o he p oblem in ol ing he whole g oup. Sasaki and Toda (1992) and ¨
Ozkal-
San e (2009) conside con e se consis ency o he closely ela ed class o ma iage p oblems
(one- o-one ma ching p oblems). Fu he mo e, Thomson (2004, 2009) p o ides an ex ensi e
su ey o consis ency and i s con e se o a ious economic models. Since we ocus on he
s uden -op imal s able mechanism, we in oduce con e se consis ency di ec ly o mechanisms
and no (as is he s anda d) o co espondences.
4.1 Local Con e se Consis ency
Simila ly as in Sec ion 3, we i s in oduce local con e se consis ency.
De ini ion 5. Local con e se consis ency
Le N⊆¯
Nbe a se o s uden s and qa quo a ec o . A placemen mechanism ϕis locally
con e sely consis en o (N, q) i o each p o ile R∈ RNand o each alloca ion α o place-
men p oblem (N, R, q): [i o all N′⊆Nwi h |N′|= 2, ϕ(N′, RN′, q(N′, α)) = αN′, hen
ϕ(N, R, q) = α]. △
The ollowing example demons a es ha a s uden -op imal s able mechanism migh iola e
local con e se consis ency (ou example is a simpli ica ion o ¨
Ozkal-San e ’s, 2009, Example 3.2).
Example 1. A p io i y s uc u e ≻such ha ϕ≻is no locally con e sely consis en
Le X={x, y, z},N={1,2,3}, and qx=qy=qz= 1. Conside he p io i y s uc u e ≻and
p e e ences R∈ RNas gi en in he ables below.
≻x≻y≻z
1 2 3
2 3 1
3 1 2
and
R1R2R3
z x y
x y z
Fo his placemen p oblem, ϕ≻(N, R, q) = (z, x, y). Le α= (x, y, z). One easily e i ies
ha o all N′⊆Nwi h |N′|= 2, ϕ≻(N′, RN′, q(N′, α)) = αN′. Howe e , ϕ≻(N, R, q)6=α.
The e o e, ϕ≻is no locally con e sely consis en o (N, q). (Inciden ally, no ice ha αis
he posi ion- ype-op imal s able ma ching o he associa ed ma iage p oblem.) Obse e ha
1≻x2≻y3≻z1, which u ns ou o be he “p oblema ic pa ” in p io i y s uc u e ≻ ha
causes ϕ≻ o iola e local con e se consis ency. ⋄
8
Gi en a ixed se o s uden s Nand a ixed quo a ec o q, we i s analyze which p io i y
s uc u es ≻gua an ee ha he s uden -op imal s able mechanism ϕ≻is locally con e sely
consis en o (N, q). In line wi h E gin’s (2002) esul , we show ha local acyclici y o he
p io i y s uc u e o (N, q) is su icien o ϕ≻ o be locally con e sely consis en o (N, q).
Howe e , i u ns ou ha he class o p io i y s uc u es ha induce ϕ≻ o be locally con e sely
consis en o (N, q) is s ic ly la ge han he class o locally acyclic p io i y s uc u es o (N, q).
We i s in oduce local shi - eeness o a p io i y s uc u e ≻ o (N, q). We hen p o e
ha local shi - eeness o (N, q) is a necessa y and su icien condi ion o he s uden -op imal
s able mechanism ϕ≻ o be locally con e sely consis en o (N, q) (Theo em 3).
De ini ion 6. Local shi s and local shi - eeness
Le N⊆¯
Nbe a se o s uden s and qa quo a ec o . Gi en a p io i y s uc u e ≻, a local shi
o (N, q) is cons i u ed o o de ed and dis inc x, y, z ∈X(qx, qy, qz6= 0) and i, j, k ∈Nsuch
ha he ollowing wo condi ions a e sa is ied:
shi condi ion i≻xj≻yk≻ziand
s-sca ci y condi ion he e exis disjoin (and possibly emp y) se s Nx, Ny, Nz⊆N {i, j, k}
such ha Nx⊆ {l∈N:l≻xj},Ny⊆ {l∈N:l≻yk},Nz⊆ {l∈N:l≻zi},|Nx|=qx−1,
|Ny|=qy−1, and |Nz|=qz−1.
A p io i y s uc u e ≻is locally shi - ee o (N, q) i i has no local shi s o (N, q). △
I quo as a e all equal o 1, hen he shi condi ion is su icien o es ablish he exis ence
o a local shi . Fo o he quo as, he s-sca ci y condi ion limi s he de ini ion o a local shi
o cases whe e he e indeed exis s uden s’ p e e ences such ha s uden s i,j, and kcompe e
o posi ion ypes x,y, and z(in he absence o his compe i ion, e.g., because he quo as do in
ac no limi he access o he s uden s o posi ions x,y, and z, a local shi will no cause he
s uden -op imal s able mechanism ϕ≻ o iola e local con e se consis ency).
No e ha Example 1 exhibi s a local “3-shi ” in he sense ha i in ol es 3 s uden s (and
3 posi ion ypes). We will use he ollowing concep o mo e gene al local shi s o p o e ou
main esul .
De ini ion 7. Local k-shi s
Le N⊆¯
Nbe a se o s uden s and qa quo a ec o . Gi en a p io i y s uc u e ≻, a local
k-shi o (N, q) is cons i u ed o o de ed and dis inc x1,...,xk∈X(qx1,...,qxk6= 0) and
i1,...,ik∈Nwi h k≥3 such ha he ollowing wo condi ions a e sa is ied:
k-shi condi ion i1≻x1i2≻x2i3≻x3· · · ≻xk−1ik≻xkik+1 := i1and
s-sca ci y condi ion he e exis disjoin (and possibly emp y) se s Nxl⊆N {i1,...,ik}(l=
1,...,k) such ha Nxl⊆ {j∈N:j≻xlil+1}and |Nxl|=qxl−1 (l= 1,...,k). △
We nex show ha o any pai (N, q), he p esence o a local k-shi o (N, q) implies he
p esence o a local shi o (N, q).
Lemma 1. Le N⊆¯
Nbe a se o s uden s and qa quo a ec o . I p io i y s uc u e ≻has a
local k-shi o (N, q), hen i has a local shi o (N, q).
9
acuously sa is ied). Hence, by Co olla y 2, ϕ≻is no locally con e sely consis en o (N, q).
So, ϕ≻is no globally con e sely consis en .
Pa II: Assume ϕ≻is no globally con e sely consis en . Then, o some se o agen s N⊆¯
N
and quo a ec o q,ϕ≻is no locally con e sely consis en o (N, q). By Theo em 3, he p io i y
s uc u e ≻has a local shi o (N, q). Le x, y, z ∈X(qx, qy, qz6= 0) and (wi hou loss o
gene ali y) 1,2,3∈Ncons i u e a local shi o (N, q). Le Nx, Ny,and Nzbe he co esponding
se s in he s-sca ci y condi ion. Conside ˜qwi h ˜qx=qx− |Nx|= 1, ˜qy=qy− |Ny|= 1,
˜qz=qz− |Nz|= 1, and ˜qx′= 0 (x′∈X {x, y, z}). Then, ˜qis a uni quo a ec o and
x, y, z ∈Xand 1,2,3∈Ncons i u e a local shi o (N, ˜q). By Lemma 2 (o Lemma 3), he e
is a local cycle o (N, ˜q). Hence, he p io i y s uc u e ≻has a uni cycle.
Co olla y 3. ϕ≻is globally con e sely consis en i and only i ϕ≻is globally consis en .
Re e ences
Balinski, M., and T. S¨onmez (1999): A Tale o Two Mechanisms: S uden Placemen , Jou nal
o Economic Theo y 84, 73–94.
Ehle s, L. (2002): Coali ional S a egy-P oo House Alloca ion, Jou nal o Economic The-
o y 105, 298–317.
Ehle s, L., and B. Klaus (2003): Resou ce-Mono onic House Alloca ion, In e na ional Jou nal
o Game Theo y 32, 545–560.
Ehle s, L., and B. Klaus (2006): E icien P io i y Rules, Games and Economic Beha -
io 55, 372–384.
Ehle s, L., and B. Klaus (2007): Consis en House Alloca ion, Economic Theo y 30, 561–574.
Ehle s, L., B. Klaus, and S. P´apai (2002): S a egy-P oo ness and Popula ion-Mono onici y
o House Alloca ion P oblems, Jou nal o Ma hema ical Economics 83, 329–339.
E gin, H. ˙
I. (2000): Consis ency in House Alloca ion P oblems, Jou nal o Ma hema ical Eco-
nomics 34, 77-97.
E gin, H. ˙
I. (2002): E icien Resou ce Alloca ion on he Basis o P io i ies, Econome -
ica 70, 2489–2497.
Gale, D., and L.S. Shapley (1962): College Admissions and he S abili y o Ma iage, The
Ame ican Ma hema ical Mon hly 69, 9–15.
Kes en, O. (2006): On Two Compe ing Mechanisms o P io i y-Based Alloca ion P oblems,
Jou nal o Economic Theo y 127, 155–171.
¨
Ozkal-San e , ˙
I (2009): Minimal Con e se Consis en Ex ension o he Men-Op imal Solu ion,
Mu a Se el Cen e o Ad anced Economic S udies Wo king Pape 1.
16

Ro h, A.E. (1982): The Economics o Ma ching: S abili y and Incen i es, Ma hema ics o
Ope a ions Resea ch 7, 617–628.
Ro h, A.E. (1984): The E olu ion o he Labo Ma ke o Medical In e ns and Residen s: a
Case S udy in Game Theo y, Jou nal o Poli ical Economy 92, 991–1016.
Ro h, A.E. (1985): The College Admissions P oblem is no Equi alen o he Ma iage P oblem,
Jou nal o Economic Theo y 36, 277–288.
Ro h, A.E., and M.A.O. So omayo (1990): Two-Sided Ma ching: A S udy in Game-Theo e ic
Modeling and Analysis. Econome ic Socie y Monog aph Se ies. New Yo k: Camb idge
Uni e si y P ess.
Sasaki, H., and M. Toda (1992): Consis ency and Cha ac e iza ion o he Co e o Two-Sided
Ma ching P oblems, Jou nal o Economic Theo y 56, 218–227.
Thomson, W. (2004): Consis ency and i s Con e se: an In oduc ion. Uni e si y o Roches e .
Mimeo.
Thomson, W. (2009): Consis en Alloca ion Rules (Ve sion: June 8, 2009). Uni e si y o
Roches e . Mimeo.
Thomson, W., and L. Zhou (1993): Consis en Solu ions in A omless Economies, Econome -
ica 61, 575–587.
17