Two axiomatic approaches to the probabilistic serial mechanism

Ün e , M. U ku; Kes en, Onu ; Ku ino, Mo imi su; Hashimo o, Tadashi; Hi a a, Daisuke A icle — Published Ve sion Two axioma ic app oaches o he p obabilis ic se ial mechanism Theo e ical Economics P o ided in Coope a ion wi h: The Econome ic Socie y Sugges ed Ci a ion: Ün e , M. U ku; Kes en, Onu ; Ku ino, Mo imi su; Hashimo o, Tadashi; Hi a a, Daisuke (2014) : Two axioma ic app oaches o he p obabilis ic se ial mechanism, Theo e ical Economics, ISSN 1555-7561, The Econome ic Socie y, New Ha en, CT, Vol. 9, Iss. 1, pp. 253-277, h ps://doi.o g/10.3982/TE1010 This Ve sion is a ailable a : h ps://hdl.handle.ne /10419/150220 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/3.0/ Theo e ical Economics 9 (2014), 253–277 1555-7561/20140253 Two axioma ic app oaches o he p obabilis ic se ial mechanism Tadashi Hashimo o Toulouse School o Economics (IDEI) Daisuke Hi a a Depa men o Economics, Ha a d Uni e si y Onu Kes en Teppe Business School, Ca negie Mellon Uni e si y Mo imi su Ku ino Wissenscha szen um Be lin ü Sozial o schung M. U ku Ün e Depa men o Economics, Bos on College This pape s udies he p oblem o assigning a se o indi isible objec s o a se o agen s when mone a y ans e s a e no allowed and agen s e eal only o dinal p e e ences, bu andom assignmen s a e possible. We o e wo cha ac e iza ions o he p obabilis ic se ial mechanism, which assigns lo e ies o e objec s. We show ha i is he only mechanism ha sa is ies non-was e ulness and o dinal ai ness, and he only mechanism ha sa is ies sd-e iciency,sd-en y- eeness,and weak in a iance o weak unca ion obus ness (whe e “sd” s ands o i s -o de s ochas ic dominance). Keywo ds. Random assignmen , p obabilis ic se ial, o dinal ai ness, sd-e i- ciency, sd-en y- eeness, weak in a iance, weak unca ion obus ness. JEL classi ica ion. C71, C78, D71, D78. Tadashi Hashimo o: [email p o ec ed] Daisuke Hi a a: [email p o ec ed] Onu Kes en: [email p o ec ed] Mo imi su Ku ino: [email p o ec ed] M. U ku Ün e : [email p o ec ed] We would like o hank Ch is ian Bas eck, Anqi Fu, Fuhi o Kojima, Mike Os o sky, Al Ro h, Michael Schwa z, Jay Se hu aman, and pa icipan s a he 2011 Asian Mee ing o he Econome ic Socie y, CORE, he Duke “Ro h–So omayo : 20 Yea s A e ” Con e ence, Kyo o, Maas ich , Osaka, and S an o d, Tokyo, Tsukuba, 6 h Pan Paci ic Con e ence on Game Theo y a Tokyo Tech, and Uni e si é Lib e de B uxelles o commen s. Ku ino acknowledges inancial suppo om he Max Planck Ins i u e o Economics and Maas ich Uni e si y when he was a ilia ed he e. Ün e acknowledges he esea ch suppo o Mic oso Resea ch Lab, New England. The cu en pape supe sedes wo p e ious wo king pape s, Kes en e al. (2011) and Hashimo o and Hi a a (2011), in cha ac e izing he p obabilis ic se ial mechanism. We hank he edi o , an associa e edi o , and e e ees o hei cons uc i e commen s. Copy igh ©2014 Tadashi Hashimo o, Daisuke Hi a a, Onu Kes en, Mo imi su Ku ino, and M. U ku Ün e . Licensed unde he C ea i e Commons A ibu ion-NonComme cial License 3.0. A ailable a h p://econ heo y.o g. DOI: 10.3982/TE1010 254 Hashimo o, Hi a a, Kes en, Ku ino, and Ün e Theo e ical Economics 9 (2014) 1. In oduc ion A wide ange o eal-li e esou ce alloca ion p oblems—s uden placemen in public schools, o gan ansplan a ion h ough li e o deceased dono s, on-campus housing alloca ion, and cou se alloca ion a business schools—in ol es he assignmen o indi- isible objec s wi hou he use o mone a y ans e s. Mos o hese ma ke s ely on o dinal mechanisms, whe e pa icipan s e eal only hei p e e ence ankings o e gi en choices o he cen al au ho i y a he han hei ca dinal p e e ences. Ensu ing ai ness o a de e minis ic alloca ion can en ail signi - ican ine iciencies.1The e o e, i has become commonplace o use andom mecha- nisms, which allow he alloca ion o di isible p obabili ies, o achie e ai ness ex an e.2 In spi e o his use o andomiza ion, mos such ma ke s ely on o dinal mecha- nisms: pa icipan s e eal only hei p e e ences o e objec s, a he han hei p e - e ences o e andom alloca ions o objec s. Howe e , om an agen ’s o dinal anking io e he se Ao objec s (assumed s ic ), one can de ine i s -o de s ochas ic domi- nance ( .o.s.d.), which is a pa ial o de ≥io e he se o andom alloca ions (p obabili y measu es on A). These pa ial o de s can be used o e alua e andom mechanisms. Us- ing he p e ix “sd-” o indica e .o.s.d., we say ha a andom assignmen Pis sd-e icien i i is Pa e o e icien wi h espec o he .o.s.d. o de ings. We say ha i is sd-en y- ee i Pi≥iPj o all i,j. Then we can make compa isons: •Sd-e iciency is s onge han ex pos e iciency, hough no as s ong as ex an e e iciency would be i one had access o he comple e on-Neumann–Mo gens e n ( NM) u ili ies. •Sd-en y- eeness is weake han ex pos en y- eeness, hough no as weak as ex an e en y- eeness would be wi h he NM u ili ies. A common mechanism used in p ac ice is he andom se ial dic a o ship (RSD). Agen s a e andomly o de ed (wi h a uni o m dis ibu ion o e pe mu a ions) and hen, in he ealized o de , agen s successi ely pick hei a o i e objec s om hose a ailable. How- e e , in spi e o he appa en equal ea men o agen s, he esul ing andom assign- men may no be sd-en y- ee; nei he need i be sd-e icien . In a seminal pape , Bogomolnaia and Moulin (2001) (BM he ea e ) p oposed he p obabilis ic se ial mechanism (PS), which is sd-e icien and sd-en y- ee. The ou - come o PS is de ined by he simul aneous ea ing algo i hm (SEA): Conside each objec as a con inuum o p obabili y sha es. Agen s simul aneously “ea away” om hei a- o i e objec s a he same speed; once an agen ’s a o i e objec is gone, he u ns o his nex a o i e objec , and so on. The amoun o an objec ea en away by an agen 1See, o example, Kes en and Yazıcı (2012). 2Fo example, he assignmen mechanisms used in he con ex o s uden placemen ope a e h ough a collec ion o s ic p io i y o de s o schools o e s uden s. In p ac ice, de e mining hese o de s o en in ol es andomiza ion (Abdulkadi o˘ glu and Sönmez 2003b,E dil and E gin 2008,Pa hak and Se hu aman 2011,Kes en and Ün e 2013). Simila ly, in he exchange o li e-dono kidneys among kidney pa ien s o ansplan a ion, he egali a ian app oach equi es he design o a andom mechanism (Ro h e al. 2005). Theo e ical Economics 9 (2014) P obabilis ic se ial mechanism 255 h oughou he p ocess is in e p e ed as he p obabili y wi h which he is assigned his objec by PS.3 The pu pose o his pape is o p o ide wo axioma iza ions o PS. Ou i s axioma- iza ion is buil a ound a new p ope y, o dinal ai ness. Fix a andom assignmen and o any agen iand each a∈A,le Fi(a) be he p obabili y ha iob ains ao an objec be e han a; his is called i’s su plus a a. The andom assignmen is o dinally ai i o all i,jand a∈Asuch ha job ains awi h a posi i e p obabili y, i’s su plus a ais as la ge as j’s su plus a a. Though ela ed in spi i , o dinal ai ness and sd-en y- eeness a e qui e di e en , as we illus a e wi h his example. Suppose he e a e wo agen s, i=12, and wo objec s, A={a b}.Agen 1p e e s a o b;agen 2p e e s b o a. Suppose we gi e each objec o each agen wi h an equal p obabili y. Agen 1does no wish he had agen 2’s andom alloca ion, ye he migh en y he ac ha agen 2always ge s an objec ha she likes a leas as much as a, whe eas his happens o agen 1only hal o he ime. The alloca ion is no o dinally ai . In his example, he andom assignmen is no sd-e icien . The only sd-e icien al- loca ion gi es a o agen 1 o su e and b o agen 2 o su e, bu hen o dinal ai ness ob ains. This sugges s a link be ween o dinal ai ness and bo h sd-e iciency and sd- en y- eeness. In ac , we show ha o dinal ai ness implies bo h o hese p ope ies in he BM se ing in which he o al supply o objec s exac ly equals he numbe o agen s. Fu he mo e, i p o ides a ull cha ac e iza ion o PS in he same se ing. (This is he i s ede ini ion o an algo i hmic ma ching mechanism, ha we a e awa e o , h ough a single igh p ope y.) In he mo e gene al se ing when he o al supply o objec s ex- ceeds he numbe o agen s, i cha ac e izes PS in combina ion wi h a mild assump ion called non-was e ulness (Theo em 1). We ob ain a second cha ac e iza ion o PS using sd-e iciency and sd-en y- eeness. These a e implied by PS, bu do no ully cha ac e ize i . Ou Theo em 2 and Co olla y 2 show ha a comple e cha ac e iza ion is ob ained by adding ei he weak in a iance o weak unca ion obus ness; hese axioms impose in a iance o he assignmen o ce - ain pe u ba ions o he o dinal p e e ences. 1.1 Rela ed li e a u e The e a e e y ew pape s ha discuss he andom assignmen p oblem p io o he new millennium. The ea lies accoun o he p oblem is due o Hylland and Zeckhause (1979), who p opose a pseudo-ma ke mechanism ha elies on ca dinal p e e ences o agen s. Much la e , Zhou (1990) p o es an impo an impossibili y esul o he ca - dinal domain: The e exis s no s a egy-p oo , Pa e o-e icien , and symme ic mecha- nism. A simila nega i e esul is ob ained by Chambe s (2004) in he o dinal domain: 3Howe e , RSD is sd-s a egy-p oo , unlike PS, which is sd-s a egy-p oo only in a weak sense. Ne e - heless, Kojima and Manea (2010) show ha in la ge bu ini e p oblems whe e each objec has a su icien ly la ge supply, PS egains sd-s a egy-p oo ness. In ela ed wo k, Che and Kojima (2010) show ha in he limi o disc e e economies wi h ini e objec ypes, PS con e ges o RSD. 256 Hashimo o, Hi a a, Kes en, Ku ino, and Ün e Theo e ical Economics 9 (2014) all ex pos consis en , symme ic, and s a egy-p oo mechanisms should coincide wi h uni o mly andom assignmen o objec s. Following he seminal wo k o BM ha in oduced PS, he li e a u e on he andom assignmen p oblem has g own apidly. Con a y o he ea ly li e a u e, he new s and o li e a u e o en es ic s a en ion o he case when agen s’ p e e ences a e o dinal.4 The PS was ini ially p oposed by C ès and Moulin (2001) o asimplemodelwhe e agen s ha e he same ankings o e objec s. A cha ac e iza ion o his special con ex is gi en by Bogomolnaia and Moulin (2002). Kojima and Manea (2010) show ha PS eco e s s a egy-p oo ness when he ma ke size becomes su icien ly la ge. Manea (2009) shows ha o dinal ine iciency o RSD p e ails e en o la ge assignmen p ob- lems. Ka a and Se hu aman (2006) ex end PS o he domain o weak p e e ences. Yılmaz (2009,2010) adap s i o en i onmen s whe e he e may be ini ial p ope y igh s o e some o he objec s. A hanassoglou and Se hu aman (2011) u he ex end his model and he mechanism o he case wi h p obabilis ic endowmen s. Kojima (2009) o e s a gene aliza ion o PS o mul iple assignmen p oblems. Abdulkadi o˘ glu and Sönmez (1998) show ha RSD is equi alen o a co e mecha- nism ha uni o mly andomly selec s an ini ial assignmen o objec s and hen u ilizes Gale’s celeb a ed op ading cycles (Shapley and Sca 1974)p ocedu e. Sönmez and Ün e (2005), Pa hak and Se hu aman (2011), and Ca oll (2013) ex end his esul o di - e en andom ma ching domains. Kes en (2009) shows a simila connec ion be ween PS and he op ading cycles p ocedu e: PS is equi alen o a pa icula op ading cycles mechanism ha ini ially endows each agen wi h an equal sha e o each objec . He also p o ides a “ eplica ed” RSD mechanism ha becomes equi alen o PS in he limi . Budish e al. (2013) cha ac e ize he cons ain s on a andom assignmen ha can also be sa is ied by each o he de e minis ic assignmen s in he suppo o a lo e y ha induces i . The compelling no ion o sd-e iciency is also he ocus o o he ela ed pape s. Abdulkadi o˘ glu and Sönmez (2003a) o e a cha ac e iza ion o o dinally e icien an- dom assignmen s. McLennan (2002) p o es an in e es ing esul on he ela ionship be- ween sd-e iciency and ex an e e iciency. Manea (2008) p o ides a cons uc i e p oo o his esul . The axioma ic cha ac e iza ion o PS o un es ic ed p e e ence domains began wi h h ee independen s udies: Hashimo o and Hi a a (2011) (he ea e , HH), Heo (2013), and Kes en e al. (2011) (he ea e , KKÜ).5KKÜ is he pape ha o iginally p esen s Theo em 1 o his pape , and is he i s pape ha cha ac e izes PS in he gene al case using sd-e iciency and sd-en y- eeness. HH cha ac e ize he mechanism wi h hese axioms in he en i onmen whe e he null objec always exis s. They also p o ide an axioma iza ion based on he Rawlsian p inciple. Heo (2013)conside san en i onmen whe e agen s may demand mul iple uni s and shows ha he gene alized 4Th ee common jus i ica ions o he o dinal app oach a e as ollows: Fi s , since agen s a e bound- edly a ional, ca dinal p e e ences a e di icul o elici . Second, o dinal mechanisms a e ela i ely simple and mo e p ac ical han ca dinal mechanisms. Thi d, eal-li e ma ching ma ke s unc ion mos ly h ough elici a ion o o dinal p e e ences. 5The i s e sions o he pape s by Heo and KKÜ we e ci cula ed in 2010. Theo e ical Economics 9 (2014) P obabilis ic se ial mechanism 257 PS mechanism is cha ac e ized by sd-e iciency, he p opo ional di ision lowe bound, and se e al auxilia y axioms. In a mo e ecen wo k, Bogomolnaia and Heo (2012) (he ea e , BH) eplace he in- a iance axioms in KKÜ and HH wi h a weake condi ion called bounded in a iance and o e new, sho e p oo s in a uni ying amewo k o he KKÜ and HH esul s. This p oo echnique was based on he obse a ions o Heo (2013) ega ding PS and p obabilis ic assignmen s in gene al. Ou cha ac e iza ions in his pape using sd-e iciency and sd- en y- eeness (Theo em 2 and Co olla y 2), which build on KKÜ and HH, a e s onge han all h ee p e ious esul s men ioned (HH Theo em 1, KKÜ Theo em 2, and BH The- o em 2), as weak in a iance is implied by bo h uppe in a iance o KKÜ and bounded in a iance o BH, in he gene al case when a null objec does no necessa ily exis ; and weak unca ion obus ness, when a null objec exis s, is implied by bo h unca ion obus ness o HH and bounded in a iance o BH.6,7,8 Mos no ably, whe eas all he p e iously conside ed in a iance condi ions men- ioned abo e equi e ha whene e he p e e ences o an agen change wi h e e ence o a ixed objec in a speci ic way, all agen s’ p obabili y sha es o he pa icula objec emain he same, weak in a iance makes a much less demanding equi emen : only he pa icula agen ’s p obabili y sha e o he pa icula objec should emain he same.9 Al e na i ely, Liu and Pycia (2011) look a la ge ma ke s in which all ypes o agen s a e ep esen ed. They show ha in his case, he e is a unique mechanism ha is sd- e icien and sd-en y- ee, and ha in he limi o la ge ma ke s, uni o mly andom e - sions o many known de e minis ic mechanisms such as se ial dic a o ships, hie a chi- cal exchange ules (Pápai 2000), and ading cycles mechanisms (Pycia and Ün e 2011) coincide wi h his unique mechanism. 2. Model Ou objec o s udy is a disc e e esou ce alloca ion p oblem (c . Hylland and Zeckhause 1979,Shapley and Sca 1974). Le Nbe he ini e se {1n}o agen s o whom objec s a e alloca ed. In BM, he e a e exac ly ndis inc objec s o be alloca ed, one pe agen . We gene alize his sligh ly: each agen s ill ecei es one objec , bu he pool o objec s o be dis ibu ed can include duplica es, ha is, objec s ha a e equi alen o all he agen s. We le Adeno e he se o ypes o objec s and, o a∈A,le qadeno e he quo a o supply o objec a. The e may be a su plus o objec s: a∈Aqa≥|N|. 6We hank an anonymous e e ee o sugges ing ha we weaken HH’s de ini ion o unca ion obus - ness o he cu en de ini ion (De ini ion 3). Upon showing ha his new de ini ion is s ong enough o cha ac e ize PS, we obse ed ha he p oo also ex ends o he gene al case whe e he null objec may no exis . This mo i a ed us o ob ain ou second cha ac e iza ion esul using he cu en de ini ion o weak in a iance (De ini ion 2), which is he coun e pa o De ini ion 3 in en i onmen s wi hou he null objec . 7Also, ou p oo immedia ely implies ha we can weaken sd-e iciency in Theo em 2 and Co olla y 2 as in HH and BH. 8A mo e ecen pape by Heo and Yılmaz (2012) ex ends he esul s o BH o he case wi h weak p e e - ences o Ka a and Se hu aman’s (2006) ex ended p obabilis ic se ial co espondence. 9This axiom was p e iously in oduced by Heo (2013) as one o he auxilia y axioms. She e e ed o i as “limi ed in a iance.” 258 Hashimo o, Hi a a, Kes en, Ku ino, and Ün e Theo e ical Economics 9 (2014) An assignmen speci ies an objec o each agen such ha o each a∈A, henum- be o agen s ecei ing objec adoes no exceed qa.Le A e e o he se o possible assignmen s. We assume objec s can be alloca ed andomly. A lo e y is a p obabili y dis ibu ion o e assignmen s. Each agen i∈Nca es only abou his own andom al- loca ion, ha is, he esul ing p obabili y dis ibu ion Pi=[pia]a∈Ao e A,whe epia is he p obabili y wi h which he ecei es objec a. We e e o he ma ix P=[Pi]i∈No andom alloca ions, whe e each ow Piis he andom alloca ion o an agen and each column Paalloca es p obabili y sha es o an objec a o he agen s, as a andom assign- men ;i has hep ope y ha i∈Npia ≤qa o each a∈Aand a∈Apia =1 o i∈N. Le R e e o he se o possible andom assignmen s. Each lo e y induces such a an- dom assignmen and each such andom assignmen is induced by some lo e y (c . on Neumann 1953).10 The e o e, we can ocus ou a en ion on andom assignmen s as he ou come o a mechanism. We equi e ha a mechanism elici s only each agen i’s o dinal p e e ence ela ion io e objec s. This p e e ence o de ing is assumed o be s ic . Al hough we implici ly allow o some indi e ence by le ing he e be duplica es o each objec , any indi e ence mus be sha ed by all agen s. Le Pbe he se o such s ic p e e ences. We some imes ep esen iby he o de ed lis o objec s; e.g., i=(bca) o i=(bca) means ha bicia(he e assuming ha A={ab c}). Al hough agen s’ p e e ences o e andom alloca ions a e unspeci ied, we can con- s uc a pa ial o de ha can be used o compa e andom alloca ions based on ( i s - o de ) s ochas ic dominance. Gi en a∈Aand i∈P o agen i,le U(ia) = {b∈A|bia}be he uppe con ou se o objec aa i. Gi en a andom alloca ion Pi,le F(iaPi)=b∈U(ia) pib be he p obabili y ha iis assigned an objec a leas as good as aunde Pi; we simply e e o i as i’s su plus a aunde Pi.Fo agen i,gi en ∈PNand PR ∈R,Pis ochas ically domina es Ria ii F(iaPi)≥F(iaRi) o all a∈A. In addi ion, Ps ochas ically domina es Ra i Pis ochas ically domina es Ri a i o all i∈N. Th oughou he pape , whene e i is no ambiguous, we supp ess N,A,andq,and deno e an alloca ion p oblem by a p e e ence p o ile. Fo mally, a mechanism is a sys- ema ic way o ind a andom assignmen o a gi en p oblem, ha is, i is an alloca ion ule φ:PN→R. Ou model is gene al enough o con ain a ious in e es ing special cases: (i) Unaccep able objec s: The e is a speci ic objec e e ed o as he null objec and assigned a quo a o a leas |N|. By in e p e a ion, agen s who a e assigned he null objec a e iewed as aking hei ou side op ions o , using he ma ching ja - gon, hey emain unassigned. The objec s anked below he null objec a e called unaccep able. This case models assignmen unde olun a y pa icipa ion.11 10This classical esul is also commonly c edi ed o Ga e Bi kho and e e ed o as he Bi kho – on Neumann Theo em. 11In his se ing, he s anda d indi idual a ionali y equi emen , i.e., ha no agen be assigned an unac- cep able objec wi h some posi i e p obabili y, is implied by ei he e iciency p ope y o be subsequen ly in oduced; namely, by ei he non-was e ulness o sd-e iciency. Theo e ical Economics 9 (2014) P obabilis ic se ial mechanism 259 (ii) Pe ec supply wi h uni quo as: Each objec has a quo a o 1and he e a e exac ly |N|objec s. This is he o iginal se ing o BM.12 Th ee p ope ies o andom assignmen s a e essen ial in ou cha ac e iza ions. A an- dom assignmen is sd-e icien i i is no s ochas ically domina ed by ano he andom assignmen .13 Nex is a much weake e iciency p ope y. A andom assignmen is non-was e ul i he su plus o no agen a any objec can be aised h ough he use o an unassigned p obabili y sha e o some objec . Fo mally, gi en ∈PN,P∈Ris non-was e ul a i o all i∈Nand all a∈Asuch ha pia >0,weha ej∈Npjb =qb o all b∈Awi h bia. Ou i s ai ness p ope y is a undamen al p inciple in mechanism design heo y o iginally p oposed by Foley (1967). A andom assignmen is sd-en y- ee i each agen , ega dless o his NM u ili ies, p e e s his andom alloca ion o ha o any o he agen . Fo mally, gi en ∈PN,P∈Ris sd-en y- ee a i o all i∈N,Pis ochas ically domi- na es Pj o all j∈Na i. A mechanism is said o sa is y a p ope y i i s ou come, o any p oblem, sa is ies ha p ope y. 3. Two new axioms Ou second ai ness p ope y, which is essen ial o ou i s cha ac e iza ion, is a na - u al and in ui i e axiom o he andom assignmen se ing. A andom assignmen is o dinally ai i whene e an agen is assigned some objec wi h posi i e p obabili y, his su plus a his objec is no g ea e han ha o any o he agen a he same objec . I ollows ha whene e an agen is assigned some objec xwi h ze o p obabili y, he mus be assigned a be e objec ( o him) wi h a p obabili y no less han any agen who is assigned objec xwi h posi i e p obabili y. De ini ion 1. Gi en ∈PN,P∈Ris o dinally ai a i o all a∈Aand all i j ∈N wi h pia >0,weha eF(iaPi)≤F(jaPj). One in e p e a ion o he p oblem we a e s udying he e is o en i le each agen o an equal p obabili y sha e o each objec ini ially. Unde such an in e p e a ion, o dinal ai ness makes i possible o agen s o e icien ly edis ibu e hei ini ial sha es among hemsel es so ha e e y agen can enjoy a highe objec -speci ic su plus, p o ided ha his su plus does no exceed ha o ano he agen . In his sense, o dinal ai ness can be iewed as an analogue o he cu en se up o Va ian’s ai ness no ion, which encom- passes Pa e o e iciency and en y- eeness in exchange economies wi h pe ec ly di is- ible goods (c . Va ian 1974,1975,1976). Rema kably, o dinal ai ness implies bo h sd- e iciency and sd-en y- eeness, and i is implied by hese wo p ope ies in conjunc ion 12In his se ing, one o ou p ope ies—non-was e ulness— o be subsequen ly in oduced, is sa is ied acuously. 13Equi alen ly, unde any al e na i e andom assignmen , he su plus o some agen a some objec is less han ha unde he o iginal assignmen . 260 Hashimo o, Hi a a, Kes en, Ku ino, and Ün e Theo e ical Economics 9 (2014) wi h a weak echnical p ope y when he o al supply o objec s is equal o he numbe o agen s. We nex in oduce an auxilia y obus ness axiom—weak in a iance— ha is essen- ial o ou second cha ac e iza ion. Gi en −i, he axiom equi es ha he p obabili y o agen ige ing objec adepends only on i’s p e e ence anking down o a. When he null objec is a ailable, we can in e p e weak in a iance as obus ness agains unca ions, which a e p ac ically impo an manipula ions. We o malize his in e p e a ion in Sec- ion 6.Le i|Bbe he es ic ion o i∈P o B⊆A; ha is,i|Bis a p e e ence ela ion o e Bsuch ha o all a b ∈B,ai|Bb⇔aib. De ini ion 2. A mechanism φis weakly in a ian i o all ∈ PN,i∈N,a∈A, and  i∈P,φia()=φia( i−i)whene e U( ia) =U(ia) and  i|U( ia) = i|U( ia).14 Mos mechanisms s udied in he li e a u e a e weakly in a ian . Examples include PS, he agen -p oposing de e ed accep ance mechanism, he Bos on mechanism, and hie a chical exchange ules (Pápai 2000), which include se ial dic a o ship and he op ading cycles mechanism as special cases.15 The RSD is also weakly in a ian since i is a con ex combina ion o weakly in a ian mechanisms. 4. P obabilis ic se ial mechanism BM in oduced he p obabilis ic se ial mechanism (PS), he ou come o which can be compu ed ia he ollowing simul aneous ea ing algo i hm (SEA): Gi en a p oblem , hink o each objec aas an in ini ely di isible good wi h supply qa ha agen s ea in he ime in e al [01]. S ep 1. Each agen ea s away om his a o i e objec a he same uni speed. P oceed o he nex s ep when an objec is comple ely exhaus ed.    S ep s( o s∈{2S}). Each agen ea s away om his emaining a o i e objec a he same speed. P oceed o he nex s ep when an objec is comple ely exhaus ed. The p ocedu e e mina es a e S≤|N|s eps when each agen has ea en exac ly 1 o al uni o objec s (i.e., a ime 1). The andom alloca ion o an agen iby PS is hen gi en by he amoun o each objec he has ea en un il he algo i hm e mina es. Le PS()∈Rdeno e he ou come o PS o p oblem . 5. Fi s cha ac e iza ion o p obabilis ic se ial In ou i s esul , we es ablish ha o each p oblem he e is a unique o dinally ai and non-was e ul andom assignmen and ha his andom assignmen is he ou come o 14This p ope y is weake han bo h he uppe in a iance condi ion o KKÜ and he bounded in a iance condi ion o BH. 15The “objec -p oposing” de e ed accep ance mechanism, howe e , iola es weak in a iance. This is because agen s may bene i om unca ion (see, e.g., Example 2 o Ro h and Ro hblum 1999), which is no possible unde a weakly in a ian mechanism. Theo e ical Economics 9 (2014) P obabilis ic se ial mechanism 267 P oo . To begin, no e ha o any N⊆Ns(b ),i b is unde supplied o some i∈ Ns(b ) Na =(∗ N −1 −N), heni issoalsoa  =(∗ N∪{i} −1 −(N∪{i})).Thisis simply because φand PS a e bo h weakly in a ian ,and, hus,PS ib ()=PSib () and φib ()=φib (). (Recall ha he ankings o  −1 i= iand ∗ icoincide down o b =a∗ i.) Nex , we show ha o any N⊆Ns(b ),i b is unde supplied o some i∈N a =( N −1 −N), hen i is unde supplied o all j∈Ns(b )a . By he de ini- ion o  i= i= ∗ i, he eexis sa∈Asuch ha U( ia) =As−1∪{b }.Le jbe an a bi a y membe o Ns(b ).Fi s ,asU( jb )⊆U( ia),F( jb φj()) ≤ F( iaφj()).Second,bysd-en y- eeness,F( iaφj()) ≤F( iaφi()).Thi d, by he assump ion ha b is unde supplied o i,F( iaφi()) < F( iaPSi()) = F( ib PSi()) =τ(b ), whe e he i s equali y ollows om Claim 1(i ) and he second equali y ollows om (2). Combining hese h ee inequali ies, we ob ain F( jb φj()) < τ(b ). The e o e, i b is unde supplied o i∈Ns(b )a  −1,wecanexpandN om N=∅ o N=Ns(b )by epea edly applying he abo e wo a gumen s so ha b is unde - supplied o any j∈Ns(b )a  =(∗ Ns(b ) −1 −Ns(b )). This comple es he p oo o he claim.  Claim 3. Fo all ∈{0|B|−1},τ (b1)≤···≤τ (b +1)and τ (b +1)≤τ (bu) o all u∈{ +2|B|}. P oo . We a gue by induc ion on .Fo =0,asb1=asand 0=,weha eτ0(b1)≤ τ0(bu) o all uby he de ini ion o as.Fix ∈{1|B|}. Assume he claim is ue o −1as ou induc i e assump ion. By he de ini ion o  , SEA unde  wo ks in exac ly he same way as unde  −1un il ime τ∗=τ −1(b ). In pa icula , o all b∈B ,τ −1(b) =τ (b) ≤τ∗.Also,b +1is no exhaus ed be o e ime τ∗unde  −1 (and hence unde  ), o o he wise he claim does no hold o −1, con a y o he induc i e assump ion. The e o e, τ (b1)≤ ··· ≤ τ (b +1). I emains o show ha τ (b +1)≤τ (bu) o all u∈{ +2|B|}. Suppose, o hecon a y, ha τ (bu)< τ (b +1) o some u> +1. Wi hou loss o gene ali y, suppose bu∈a g minb∈B B τ (b). Then i ollows om he desc ip ion o SEA ha buis ea en away only by he agen s in Ns(bu)unde  .Hence,τ (bu)=τmax(bu),whe eτmax(·)is gi en by (3). Howe e , τ (b +1)≤τmax(b +1)≤τmax(bu), whe e he second inequali y ollows by he cons uc- ion o he sequence b1b|B|. Thisin u nimpliesτ (b +1)≤τ (bu),whichisa con adic ion.  Claim 4. Fo all ∈{1|B|} and i∈M ,F( ib PSi( )) =τ (b ). P oo .Le ∈{1|B|}.Fixj∈Ns(b ).Equa ion(2)impliesF( jb PSj( )) = τ (b ).Fixu< and i∈Ns(bu). In SEA unde  ,byClaim 3 o all ∈{u },ob- jec b is no ully exhaus ed be o e b −1. Thus, by he cons uc ion o  i,oncebuis ully exhaus ed, agen iwill u n o objec bu+1since objec s in As−1 U( ibu)ha e al eady been exhaus ed. Then he will u n o bu+2, and hen o b in SEA unde  . 268 Hashimo o, Hi a a, Kes en, Ku ino, and Ün e Theo e ical Economics 9 (2014) Thus, a ime τ (b ),ihas jus inished consuming an objec b wi h ≤ such ha τ (b )=τ (b )and, hence, i b = b ,icanno consumeanyo heobjec sb +1b . Thus, F( ib PSi( )) =τ (b ). Claim 5. Fo all ∈{1|B|} and i j ∈M ,i P∈Ris sd-en y- ee a  , hen a∈As−1∪B pia =a∈As−1∪B pja. P oo .Le i j ∈M . Thus, we ha e a∗ ia∗ j∈B . Hence, by he cons uc ion o  , he e exis aiaj∈Asuch ha U( iai)=U( jaj)=As−1∪B .Thus, a∈As−1∪B pia = F( iaiPi)=F( jajPi)≤F( jajPj)=a∈As−1∪B pja, whe e he inequali y ol- lows om sd-en y- eeness. Swi ching iand j, we ob ain he opposi e inequali y. Thus, we ha e he desi ed equali y.  Claim 6. Fo all ∈{1T},whe eTis de ined as in (4), i∈M b∈B −1φib( )≤ i∈M b∈B −1PSib( ). P oo . We conside wo cases. Fi s , suppose ha τ (b −1)<1.In hiscase,by Claim 3 and he cons uc ion o  , all objec s in B −1a e exhaus ed by he agen s in M −1in SEA unde  .Tha is, i∈M −1PSib( )=i∈M PSib( )=qb o all b∈B −1, and he desi ed inequali y immedia ely ollows om easibili y. Second, suppose ha τ (b −1)=1.In hiscase,F( ib −1PSi( )) =1 o all i∈M .By Claim 1, his implies b∈B −1PSib( )=1−a∈As−1φia( ) o all i∈M . The e o e, i i∈M b∈B −1φib( )>i∈M b∈B −1PSib( ), he e mus exis j∈M −1such ha a∈Aφja( )>1, which is a con adic ion.  Claim 7. Fo all ∈{1T},whe eTis de ined as in (4), i b is unde supplied o all agen s in Ns(b )a  , hena∈As−1∪B φia( )<τ  (b ) o all i∈M . P oo . We conside wo cases. Fi s , suppose ha φkb ( )>0 o some k∈M −1 and ix a bi a y j∈Ns(b ).Then,bysd-e iciency,φjb( )=0 o all b∈B −1 because b kb and b  jbby cons uc ion o  . Since b is unde supplied o ja  ,a∈As−1∪B φja( )=F( jb φj( )) < τ (b ).Then,byClaim 5, a∈As−1∪B φia( )<τ  (b ) o all i∈M . Second, suppose ha φkb ( )=0 o all k∈M −1. This implies i∈M φib ( )< i∈M PSib ( ),becauseb is unde supplied o all agen s in Ns(b ). Also, ecall ha by Claim 1,φia( )=PSia( ) o all i∈M and a∈As−1. These a gumen s oge he wi h Claim 6 and (2)imply  i∈M  b∈As−1∪B φib( )<  i∈M  b∈As−1∪B PSib( )=|M |τ (b ) Then Claim 5 implies ha o all i∈M ,  b∈As−1∪B φib( )=|M |−1 k∈M  b∈As−1∪B φkb( )<τ  (b )  Theo e ical Economics 9 (2014) P obabilis ic se ial mechanism 269 Claim 8. Suppose ha asis unde supplied o some agen in Ns(as)a . Then, o each ∈{1T},b is unde supplied o all agen s in Ns(b )a  ,whe eTis de ined as in (4). P oo . We a gue by induc ion on .Fo =1, i is immedia e om Claim 2. We assume ha b is unde supplied o all agen s in Ns(b )a  ,whe e <T.ByClaim 2, we need o show ha b +1is unde supplied o some agen in Ns(b +1)a  .Le P=φ( )and P=PS( ). We conside h ee cases, whe e Cases 1 and 2 a e no mu ually exclusi e. Case 1.Fo somei∈M ,a∈As−1∪B +1pia <τ  (b +1). Then, o all j∈Ns(b +1), by sd-en y- eeness and U( jb +1)⊆U( ib +1),weha eF( jb +1Pj)≤ F( ib +1Pj)≤F( ib +1Pi)≤a∈As−1∪B +1pia <τ  (b +1).Thus,b +1is unde sup- plied o ja  . Case 2.Weha eτ (b +1)=1. Since <T, he eexis si∈M +1such ha F( ib +1Pi)<1=τ (b +1).I i∈M , hen his case educes o Case 1. O he wise i∈Ns(b +1), owhomb +1is unde supplied a  . Case 3.Weha eτ (b +1)<1and o all i∈M ,a∈As−1∪B +1pia ≥τ (b +1).Then, since b is unde supplied o all agen s in Ns(b )a  , i ollows om Claim 7 ha o all i∈M ,a∈As−1∪B pia <τ  (b ). Thus, by ou assump ion, o all i∈M  pib +1= a∈As−1∪B +1 pia − a∈As−1∪B pia >τ  (b +1)−τ (b )=p ib +1 (5) whe e he las equali y ollows om he ac ha by Claim 3,inSEAagen i∈M u ns o ea ing b +1a ime τ (b )un il τ (b +1). Since τ (b +1)<1,b +1is ully consumed a  in SEA, i.e., i∈Np ib +1=qb +1.Also, since τ (b +1)≤τ (bu) o all u> +1by Claim 3,anyagen i∈N M +1does no ea b +1in SEA, i.e., p ib +1=0.Thus,  i∈M +1 p ib +1=qb +1(6) The e o e, i ollows om (5)and(6) ha i∈Ns(b +1)pib +1≤qb +1−i∈M pib +1< qb +1−i∈M p ib +1=i∈M +1p ib +1−i∈M p ib +1=i∈Ns(b +1)p ib +1. Thus, o some i∈Ns(b +1),weha epib +1<p  ib +1.Tha is,b +1is unde supplied o ia  . Finally, we a e eady o de i e a con adic ion i (1) does no hold. Fo no a ional simplici y, le P=φ(T)and P=PS(T) De ine B∗={b∈B BT|∃i∈Ns(b) and a∈U(T ib)s. . pia >0} and N∗= b∈B∗ Ns(b) 270 Hashimo o, Hi a a, Kes en, Ku ino, and Ün e Theo e ical Economics 9 (2014) Suppose (1) does no hold. Then he e exis s some k∈Nsuch ha φkas()<PSkas(). As PSkas()>0,k∈Ns(as), i.e., asis unde supplied o ka .Ou objec i eis oshow ha i∈N∗a∈Apia >|N∗|, which is a con adic ion because i∈N∗a∈Apia ≤|N∗| by he de ini ion o a andom assignmen . S ep 1.Weshow o alli∈MT,a∈As−1∪BTpia <a∈As−1∪BTp ia =τT(bT) and, hus, a∈BTpia <a∈BTp ia.Fixi∈MT.Fi s ,byClaim 1(iii) and (i ), a∈As−1∪BTp ia =F(T ibTP i).Second,Claim 4 implies F(T ibTP i)=τT(bT). Thi d, as asis unde supplied o agen k∈Ns(as)a ,Claim 8 implies ha bTis unde - supplied o all agen s in Ns(bT), which in u n implies by Claim 7 ha a∈As−1∪BTpia < τT(bT). These h ee s a emen s imply a∈As−1∪BTpia <a∈As−1∪BTp ia. Finally, Claim 1(iii) implies a∈BTpia <a∈BTp ia. S ep 2.Weshowpia =0 o all i∈N (MT∪N∗)and a∈U(T ia∗ i). Suppose i∈N MTand a∈U(T ia∗ i).Theni pia >0,weha ea∗ i∈B∗and, hus, i∈N∗.The e- o e, pia mus be 0 i i/∈N∗. S ep 3. We show ha he e exis i∗∈N∗and b∈BTsuch ha pi∗b >0. Fi s no e ha i∈Npib =qb o all b∈BT, since Pis non-was e ul,and o alli∈MT, heobjec s in As−1∪BTa e anked highes unde T iand a∈As−1∪BTpia <a∈As−1∪BTp ia ≤1 by S ep 1. The e exis i∗∈N MTand b∈BTsuch ha pi∗b >0, o o he wise S ep 1 implies a∈BTqa=i∈MTa∈BTpia <i∈MTa∈BTp ia ≤a∈BTqa,whichisacon- adic ion. Obse e ha b∈U(T i∗a∗ i∗).Thus,i∗∈N∗by S ep 2. S ep 4.Weshow(i)T<|B|, (ii) o all i∈MT+1,F(T ibT+1Pi)=1,and (iii) bT+1∈B∗. S ep 3 implies N∗= ∅. This in u n implies T<|B|,becauseN MT=∅ when T=|B|. The e o e, o all i∈MT+1,F(T ibT+1Pi)=1by he de ini ion o T.In pa icula , F(T ibT+1Pi)=1 o all i∈Ns(bT+1), which implies bT+1∈B∗. S ep 5. We show ha o all a∈B∗,i∈N∗pia =qa.Fixa∈B∗. Obse e ha o all i∈N (MT∪N∗),a∈U(T ia∗ i)and, he e o e, pia =0by S ep 2. Mo eo e , o all i∈MT,a∈U(T ibT+1)by S ep 4(iii) and he cons uc ion o T i,and, he e o e,by S ep 4(ii), pia =0.Thus,i∈N∗pia =i∈Npia . Al e na i ely, he e exis s some i∈N∗ wi h a=a∗ iand some b∈U(T ia) such ha pib >0by he de ini ion o B∗and N∗. Hence, j∈N∗pja =j∈Npja =qa, whe e he second equali y ollows om he non- was e ulness o P. S ep 6.Weshow o allu>T,τT(bu)=1: qbT+1≥ i∈MT+1 pibT+1 = i∈MT (1−F(T ibTPi)) + i∈Ns(bT+1)1− a∈As−1 p ia by S ep 4(ii) and Claim 1(iii) ≥ i∈MT1− a∈As−1∪BT pia+ i∈Ns(bT+1)1− a∈As−1 p ia since U(T ibT)⊆As−1∪BT Theo e ical Economics 9 (2014) P obabilis ic se ial mechanism 271 > i∈MT1− a∈As−1∪BT p ia+ i∈Ns(bT+1)1− a∈As−1 p iaby S ep 1 ≥ i∈MT+1 p ibT+1 No agen i∈N MT+1e e ea s bT+1in SEA unde T,asa∗ i∈B BT+1is no exhaus ed be o e bT+1by Claim 3.Thus,qbT+1>i∈Np ibT+1, i.e., bT+1is no ully exhaus ed in SEA. Hence, τT(bT+1)=1.AgainbyClaim 3, o all u>T,τT(bu)=1. S ep 7. We inally show i∈N∗a∈Apia >|N∗|.Fi s , a∈Apia ≥a∈B∗pia + a∈As−1pia o all i∈N∗, and he inequali y is s ic i i=i∗by S ep 3. Thus i∈N∗a∈Apia >i∈N∗a∈B∗pia +i∈N∗a∈As−1pia . The i s summa ion on he igh -hand side equals a∈B∗qaby S ep 5 and he second summa ion equals i∈N∗a∈As−1p ia by Claim 1(iii). The e o e,  i∈N∗ a∈A pia > a∈B∗ qa+ i∈N∗ a∈As−1 p ia ≥ i∈N∗ F(T ia∗ iP i) = i∈N∗ τT(a∗ i)by (2) =|N∗|by a∗ i∈B BT o all i∈N∗and S ep 6 This comple es he p oo .  We inally conside a special case o ou model ha assumes he exis ence o he null objec (i.e., an objec ha is always abundan in supply) and p o ide an in e es ing co olla y o Theo em 2 o his case. The null objec ep esen s an agen ’s ou side op ion ha depends on he speci ic con ex , i.e., he op ion o no being assigned a eal objec om A. This special case o he model could be o impo an p ac ical ele ance since i gi es ise o some na u al p e e ence mis ep esen a ions ha may a ise in p ac ice. Fo example, in many eal-wo ld assignmen p ocedu es, au ho i ies o en cap he numbe o objec s ha agen s can include in hei p e e ence lis s.20 E en wi hou caps, i could be un ealis ic and imp ac ical o expec agen s o e alua e and lis all o hei accep able objec s, especially when he assignmen p oblem in ol es a la ge numbe o objec s.21 Gi en ha agen s may need o sho en hei p e e ence lis s, unca ed lis s 20Fo ins ance, eshmen a he Uni e si y o Pennsyl ania may lis up o eigh choices in hei campus-housing applica ions (h p://www.business-se ices.upenn.edu/housing/asse s/pd /b ochu es/ eshman.pd ; e ie ed on No embe 15, 2010). See Hae inge and Klijn (2009), Calsamiglia e al. (2010), and Pa hak and Sönmez (2013) o mo e examples and implica ions o caps. 21In he con ex o school choice, mo e han 500 p og ams pa icipa e in he New Yo k Ci y high school ma ch (Abdulkadi o˘ glu e al. 2005). I is possible ha hund eds o p og ams a e accep able o some s uden s, bu i is highly unlikely ha hey lis all o hei accep able schools. In ac , Bos on Public Schools encou age amilies o lis a leas i e school choices (“mo e is be e ”) when egis e ing 272 Hashimo o, Hi a a, Kes en, Ku ino, and Ün e Theo e ical Economics 9 (2014) would be among he mos na u al and likely p e e ence epo s o obse e in p ac ice. The esul ing assignmen is po en ially ola ile, depending on whe he agen s unca e hei lis s o no , which would be un a o able o au ho i ies and po en ially un a o able o agen s as well. Hence, obus ness agains unca ions is a desi able p ope y o a mechanism. This p ope y is implied by weak in a iance. As i u ns ou , o indi idually a ional mechanisms, he con e se is also ue. We in oduce o mally hese nex . Le us deno e he null objec by ∅. A p e e ence ela ion  iis called a unca ion o ii U( i∅)⊆U(i∅)and i|U( i∅)=  i|U( i∅)(Ro h and Ro hblum 1999). Tha is, unca ion  iis ob ained om iby sh inking he lis o accep able objec s while p ese ing he ela i e ankings o hose objec s ha emain accep able. The ollowing axiom asks ha he p obabili y wi h which an agen i ecei es an ( eal) objec as ays he same whene e his p e e ences a e unca ed, p o ided ha a emains accep able a e he unca ion. De ini ion 3. A mechanism φis weakly unca ion obus i o all ∈PN,i∈N,and a∈A,φia()=φia( i−i)whene e a i∅and  iis a unca ion o i.22 De ini ion 4. A mechanism φis indi idually a ional i o all ∈PN,i∈N,anda∈A, φia()=0whene e ∅ia. By de ini ion, i  iis a unca ion o iand a i∅, hen he ankings o he wo p e e ences coincide down o a. The e o e, weak in a iance immedia ely implies weak unca ion obus ness. The con e se s a emen is also ue o indi idually a ional mechanisms.23 P oposi ion 1. Suppose ha he null objec exis s. A mechanism is weakly unca ion obus i i is weakly in a ian . The con e se is ue i he mechanism is indi idually a ional. P oo . To see he i s pa , no e ha i  iis a unca ion o iand a i∅, hen U( ia)=U(ia)and  i|U( ia) = i|U( ia). To show he second pa , suppose ha a (h p://www.bos onpublicschools.o g/node/169). Also, San F ancisco Uni ied School Dis ic wa ns in bold ace ha “[p]a en s who do no lis up o 7 choices un a highe isk o ge ing assigned o a school hey did no eques ” (h p://po al.s usd.edu/ empla e/de aul .c m?page=policy.placemen .p ocess). This sugges s ha some amilies may no lis he maximum numbe o choices e en when ha numbe is small. E en hough some o hem migh ac ually ha e a smalle numbe o accep able schools han he maxi- mum, s ill o he s migh sho en hei p e e ence lis s owing o a hos o o he easons including a ious cos s in ol ed in he applica ion p ocess. All he web pages we e e ie ed on No embe 15, 2010. 22In he con ex o de e minis ic assignmen s, Ehle s and Klaus (2009) p opose an axiom called unca- ion in a iance. I equi es all agen s’ assignmen s o emain he same as a esul o agen i’s unca ion, as long as he objec ha agen iob ains be o e he unca ion emains accep able. T unca ion in a iance would appea s onge han weak unca ion obus ness: The o me imposes he in a iance es ic ion o all objec s, whe eas he la e only o a pa icula one. They a e, in ac , incompa able, because he o me es ic s he class o unca ions bu he la e does no . 23The ollowing is an example o a mechanism ha is weakly unca ion obus bu no weakly in a ian . Fo any ∈PN,le φ()=Pi he e exis wo dis inc i j ∈Nsuch ha i= jand ∅ia o all a∈A, and le φ()=Po he wise, whe e Pand Pa e wo a bi a y bu dis inc andom assignmen s. Theo e ical Economics 9 (2014) P obabilis ic se ial mechanism 273 mechanism φsa is ies indi idual a ionali y and weak unca ion obus ness.Fixa∈A, i∈N,and∈PN.Le  ibe an a bi a y p e e ence such ha U(ia)=U( ia) and i|U(ia) =  i|U(ia).I ∅ia(and hus ∅ ia), hen φia()=φia( i−i)=0by indi idual a ionali y.I ai∅(and hus a i∅), le  ibe a unca ion o isuch ha U( i∅)=U(ia)∪{∅}.Then iis also a unca ion o  iand, hus, φia(i−i)= φia( i−i)=φia( i−i)by weak unca ion obus ness.I a=∅, heniis a unca- ion o  iand, hus, φib()=φib( i−i) o each bi∅.Hence,byindi idual a io- nali y,φi∅(i−i)=1−bi∅φib()=1−bi∅φib( i−i)=φi∅( i−i). I ollows om P oposi ion 1 ha weak unca ion obus ness can eplace weak in- a iance in Theo em 2 i he null objec is p esen . Co olla y 2. Suppose ha he null objec exis s. A mechanism is sd-e icien , sd-en y- ee, and weakly unca ion obus i and only i i is PS.24 7. Concluding ema ks Finally, we es ablish he logical independence o he axioms in Theo ems 1and 2.We s a wi h Theo em 1. An o dinally ai bu was e ul mechanism is he ollowing. When he o al quo a o objec s exceeds he numbe o agen s,25 conside he ollowing s a - egy: Fix q a≤qa o all a∈Asuch ha a∈Aq a=|N|. The PS mechanism ha assigns objec s acco ding o he a i icial quo a ec o (q a)a∈Ais o dinally ai bu was e ul. Al- e na i ely, a simple (de e minis ic) se ial dic a o ship is a non-was e ul bu o dinally un ai mechanism. The independence o he axioms in Theo em 2 can be shown as ollows. The PS mechanism wi h an a i icial quo a ec o de ined abo e is sd-en y- ee and weakly in- a ian bu sd-ine icien . A se ial dic a o ship is an sd-e icien and weakly in a ian mechanism ha induces sd-en y. The mechanism in Example 2 is sd-e icien and sd- en y- ee, bu no weakly in a ian . Example 2. Suppose N={123},A={ab c},andqa=qb=qc=1. De ine p e e ence p o ile ∗=((abc) (abc) (bca)). Le mechanism φbe such ha φ(∗)= abc 11 2 1 3 1 6 21 2 1 3 1 6 301 3 2 3 24As in HH’s Theo em 2, by sligh ly modi ying he p oo , we can weaken sd-en y- eeness o he condi- ion ai∅φia()≥ai∅φja() o all ∈PNand i j ∈N. 25I he o al quo a o objec s is equal o he numbe o agen s, we ha e an assignmen p oblem wi h pe ec supply. Thus, non-was e ulness holds acuously. 274 Hashimo o, Hi a a, Kes en, Ku ino, and Ün e Theo e ical Economics 9 (2014) and o all = ∗,φ()=PS().Thenφ()is sd-e icien and sd-en y- ee o all . No e ha 26 PS3b((abc)(abc)(bca)   = ∗ )=PS3b((abc)(abc)   = ∗ −3 (bac))=2 3 Howe e , he abo e de ini ion o φ iola es weak in a iance because φ3b((abc)(abc) (bca)   = ∗ )=1 3= 2 3=φ3b((abc)(abc)   = ∗ −3 (bac)) ♦ One may wonde whe he sd-e iciency can be weakened o non-was e ulness in Theo em 2. The answe is nega i e: Suppose ha he o al quo a o objec s is equal o he numbe o agen s. Then he uni o m mechanism, which assigns φia()=qa/|N| o all i∈N,a∈A,and∈PN, is non-was e ul, sd-en y- ee, and weakly in a ian , bu sd-ine icien . We can cons uc a coun e example in a simila spi i e en i he null objec exis s. Re e ences Abdulkadi o˘ glu, A ila, Pa ag A. Pa hak, and Al in E. Ro h (2005), “The New Yo k Ci y high school ma ch.” Ame ican Economic Re iew Pape s and P oceedings, 95, 364–367. [271] Abdulkadi o˘ glu, A ila and Tay un Sönmez (1998), “Random se ial dic a o ship and he co e om andom endowmen s in house alloca ion p oblems.” Econome ica, 66, 689–701. [256] Abdulkadi o˘ glu, A ila and Tay un Sönmez (2003a), “O dinal e iciency and domina ed se s o assignmen s.” Jou nal o Economic Theo y, 112, 157–172. [256] Abdulkadi o˘ glu, A ila and Tay un Sönmez (2003b), “School choice: A mechanism design app oach.” Ame ican Economic Re iew, 93, 729–747. [254] A hanassoglou, S e gios and Jay Se hu aman (2011), “House alloca ion wi h ac ional endowmen s.” In e na ional Jou nal o Game Theo y, 40, 481–513. [256] Bogomolnaia, Anna and Eun Jeong Heo (2012), “P obabilis ic assignmen o objec s: Cha ac e izing he se ial ule.” Jou nal o Economic Theo y, 147, 2072–2082. [257] Bogomolnaia, Anna and He é Moulin (2001), “A new solu ion o he andom assign- men p oblem.” Jou nal o Economic Theo y, 100, 295–328. [254] Bogomolnaia, Anna and He é Moulin (2002), “A simple andom assignmen p oblem wi h a unique solu ion.” Economic Theo y, 19, 623–635. [256] Budish, E ic, Yeon-Koo Che, Fuhi o Kojima, and Paul Milg om (2013), “Designing an- dom alloca ion mechanisms: Theo y and applica ions.” Ame ican Economic Re iew, 103, 585–623. [256] 26See Example 1, whe e i explains how he PS ou come o hese p oblems a e ound. Theo e ical Economics 9 (2014) P obabilis ic se ial mechanism 275 Calsamiglia, Ca e ina, Guillaume Hae inge , and Flip Klijn (2010), “Cons ained school choice: An expe imen al s udy.” Ame ican Economic Re iew, 100, 1860–1874. [271] Ca oll, Gab iel (2013), “A gene al equi alence heo em o alloca ion o indi isible ob- jec s.” Unpublished pape . [256] Chambe s, Ch is ophe P. (2004), “Consis ency in he p obabilis ic assignmen model.” Jou nal o Ma hema ical Economics, 40, 953–962. [255] Che, Yeon-Koo and Fuhi o Kojima (2010), “Asymp o ic equi alence o p obabilis ic se ial and andom p io i y mechanisms.” Econome ica, 78, 1625–1672. [255] C ès, He e and He é Moulin (2001), “Scheduling wi h op ing ou : Imp o ing upon andom p io i y.” Ope a ions Resea ch, 49, 565–577. [256] Ehle s, La s and Be ina Klaus (2009), “Alloca ion ia de e ed-accep ance unde espon- si e p io i ies.” Unpublished pape . [272] E dil, Ay ek and Haluk E gin (2008), “Wha ’s he ma e wi h ie-b eaking? Imp o ing e iciency in school choice.” Ame ican Economic Re iew, 98, 669–689. [254] Foley, Duncan K. (1967), “Resou ce alloca ion and he public sec o .” Yale Economic Es- says, 7, 45–98. [259] Hae inge , Guillaume and Flip Klijn (2009), “Cons ained school choice.” Jou nal o Eco- nomic Theo y, 144, 1921–1947. [271] Hashimo o, Tadashi and Daisuke Hi a a (2011), “Cha ac e iza ions o he p obabilis ic se ial mechanism.” Unpublished pape . [253,256] Heo, Eun Jeong (2013), “P obabilis ic assignmen p oblem wi h mul i-uni demands: A gene aliza ion o he se ial ule and a cha ac e iza ion.” Unpublished pape . [256,257] Heo, Eun Jeong and Özgü Yılmaz (2012), “A cha ac e iza ion o he ex ended se ial co - espondence.” Unpublished pape . [257] Hylland, Aanund and Richa d Zeckhause (1979), “The e icien alloca ion o indi iduals o posi ions.” Jou nal o Poli ical Economy, 87, 293–314. [255,257] Ka a, Akshay-Kuma and Jay Se hu aman (2006), “A solu ion o he andom assignmen p oblem on he ull p e e ence domain.” Jou nal o Economic Theo y, 131, 231–250. [256, 257] Kes en, Onu (2009), “Why do popula mechanisms lack e iciency in andom en i on- men s?” Jou nal o Economic Theo y, 144, 2209–2226. [256] Kes en, Onu , Mo imi su Ku ino, and M. U ku Ün e (2011), “Fai and e icien assign- men ia he p obabilis ic se ial mechanism.” Unpublished pape . [253,256] Kes en, Onu and M. U ku Ün e (2013), “A heo y o school-choice lo e ies.” Unpub- lished pape . [254] Kes en, Onu and Ay¸se Yazıcı (2012), “The Pa e o-dominan s a egy-p oo and ai ule o p oblems wi h indi isible goods.” Economic Theo y, 50, 463–488. [254] 276 Hashimo o, Hi a a, Kes en, Ku ino, and Ün e Theo e ical Economics 9 (2014) Kojima, Fuhi o (2009), “Random assignmen o mul iple indi isible objec s.” Ma hema - ical Social Sciences, 57, 134–142. [256] Kojima, Fuhi o and Mihai Manea (2010), “Incen i es in he p obabilis ic se ial mecha- nism.” Jou nal o Economic Theo y, 145, 106–123. [255,256] Liu, Quingmin and Ma ek Pycia (2011), “O dinal e iciency, ai ness, and incen i es in la ge mul i-uni -demand assignmen s.” Unpublished pape . [257] Manea, Mihai (2008), “A cons uc i e p oo o he o dinal e iciency wel a e heo em.” Jou nal o Economic Theo y, 141, 276–281. [256] Manea, Mihai (2009), “Asymp o ic o dinal ine iciency o andom se ial dic a o ship.” Theo e ical Economics, 4, 165–197. [256] McLennan, And ew (2002), “O dinal e iciency and he polyhed al sepa a ing hype - plane heo em.” Jou nal o Economic Theo y, 105, 435–449. [256] Pápai, Szil ia (2000), “S a egyp oo assignmen by hie a chical exchange.” Econome - ica, 68, 1403–1433. [257,260] Pa hak, Pa ag A. and Jay Se hu aman (2011), “Lo e ies in s uden assignmen : An equi - alence esul .” Theo e ical Economics,6,1–17.[254,256] Pa hak, Pa ag A. and Tay un Sönmez (2013), “School admissions e o m in Chicago and England: Compa ing mechanisms by hei ulne abili y o manipula ion.” Ame ican Economic Re iew, 103, 80–106. [271] Pycia, Ma ek and M. U ku Ün e (2011), “Incen i e compa ible alloca ion and exchange o disc e e esou ces.” Unpublished pape . [257] Ro h, Al in E. and U iel Ro hblum (1999), “T unca ion s a egies in ma ching ma ke s— In sea ch o ad ice o pa icipan s.” Econome ica, 67, 21–43. [260,272] Ro h, Al in E., Tay un Sönmez, and M. U ku Ün e (2005), “Pai wise kidney exchange.” Jou nal o Economic Theo y, 125, 151–188. [254] Shapley, Lloyd S. and He be E. Sca (1974), “On co es and indi isibili y.” Jou nal o Ma hema ical Economics, 1, 23–37. [256,257] Sönmez, Tay un and M. U ku Ün e (2005), “House alloca ion wi h exis ing enan s: An equi alence.” Games and Economic Beha io , 52, 153–185. [256] Va ian, Hal R. (1974), “Equi y, en y, and e iciency.” Jou nal o Economic Theo y,9, 63–91. [259] Va ian, Hal R. (1975), “Dis ibu i e jus ice, wel a e economics, and he heo y o ai - ness.” Philosophy and Public A ai s, 4, 223–247. [259] Va ian, Hal R. (1976), “Two p oblems in he heo y o ai ness.” Jou nal o Public Eco- nomics, 5, 249–260. [259] on Neumann, John (1953), “A ce ain ze o-sum wo-pe son game equi alen o he op- imal assignmen p oblem.” In Con ibu ions o he Theo y o Games, Vol. 2 (Ha old W.