Local and global consistency properties for student placement

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