naeporuE cimonocE weiveR 72 )5891( .69-57 dnalloH-htroN COMMON AND CONFLICTING INTERESTS IN TWO-SIDED MATCHING MARKETS nivlA E. *HTOR Uniorrsity fo .hgrubsttiP ,hgrubsttiP AP ,06251 ASU sihT repap sweiver dna sezisehtnys emos fo tahw si won nwonk tuoba tahw I lliw llac dedis-owt gnihctam mmrkets. A rebmun fo hcus ,sledom hcihw esira yllarutan ni eht yduts fo niatrec robal ,stekram evah neeb nwohs ot evah gnisirprus snoitacilpmi tuoba eht nommoc dna gnitcilfnoc stseretni fo eht ,stnega dna tuoba eht sevitnecni yeht .ecaf .1 noitcudortnI ehT esoprup of siht paper si ot weiver dna ezisehtnys emos of what si won nwonk tuoba what I lliw llac two-sided matching markets. A rebmun of hcus ,sledom hcihw esira yllarutan ni the yduts of niatrec robal ,stekram evah neeb nwohs ot evah gnisirprus snoitacilpmi tuoba the nommoc dna -tcilfnoc gni stseretni of the ,stnega dna tuoba the sevitnecni yeht face. elihW ti si ton tey nwonk ylesicerp hcihw serutaef of these sledom tnuocca for each of the seitreporp yeht share, rieht ’ssendedis-owt‘ dna the ’gnihctam‘ tnemeriuqer ylraelc yalp a lartnec .elor ehT phrase ’dedis-owt‘ refers ot the fact that stnega ni hcus stekram gnoleb ot eno of two tniojsid sets - e.g. smrif or workers - that are deificeps ni .ecnavda sihT stsartnoc for elpmaxe htiw ytidommoc stekram ni hcihw the tekram ecirp senimreted whether na tnega si a reyub or a .relles ehT mret ’gnihctam‘ refers ot the laretalib erutan of egnahcxe ni these - e.g., fi I ma deyolpme yb the ytisrevinU of ,hgrubsttiP neht the ytisrevinU of hgrubsttiP syolpme .em sihT stsartnoc htiw ytidommoc stekram ni hcihw I yam emusnoc emos of ruoy laitini tnemwodne neve hguoht uoy emusnoc enon of .enim yM nwo tseretni ni hcus stekram was tsrif desuora yb the tekram ni hcihw gnitaudarg lacidem stneduts seek level-yrtne snoitisop spihsnretni( dna )seicnediser ni naciremA .slatipsoh tahT tekram si deretsinimda yb snaem of a lartnec ,esuohgniraelc ot hcihw stneduts timbus a gniredro-knar of the *I evah detiforp morf noitasrevnoc dna ecnednopserroc no siht cipot htiw selrahC ,rialB ohw sah derahs htiw em emos fo sih krow ni .ssergorp sihT krow sah neeb detroppus yb stnarg morf eht lanoitaN ecneicS noitadnuoF dna eht eciffO fo lavaN ,hcraeseR dna yb spihswolleF morf eht nhoJ nomiS miehnegguG lairomeM noitadnuoF dna eht derflA .P naolS .noitadnuoF 03.3$/58/12924100 0 ,5891 reiveslE ecneicS srehsilbuP .V.B )dnalloH-htroN( E.E.R. D 61 A.E. Roth, Two-sided matching markets slatipsoh ot hcihw yeht evah ,deilppa dna slatipsoh timbus a gniredro-knar of the stneduts who evah deilppa ot .meht ehT esuohgniraelc neht sesu siht noitamrofni ot ecudorp a gnihctam of stneduts dna ,slatipsoh yb snaem of na mhtirogla adopted yb the tnaveler lacidem snoitaicossa ni 1951. nI the lacidem erutaretil gnibircsed siht ,erudecorp dna detubirtsid each raey ot gnitapicitrap stneduts dna ,slatipsoh ti si demialc that the mhtirogla works ni hcus a yaw that on tnapicitrap ,.e.i( on tneduts or )latipsoh nac do retteb naht ot timbus a gniredro-knar gnidnopserroc ot sih true .secnereferp nI the esruoc of gnitagitsevni siht mialc [Roth (1982a)], dna gnidnif ti ot eb eslaf (see meroehT 5.1 of siht paper), ti emaceb tnerappa that the ,mhtirogla dna the yrotsih of the tekram erofeb dna after the noitpoda of siht mhtirogla ni 1951, htob cast thgil no emos lausunu seitreporp of siht tekram that etaler ot sti dedis-owt gnihctam .erutcurts ,oslA ynam of the seussi that arose as lacitcarp smelborp ni the esruoc of gnizinagro siht tekram rehtie detapicitna yb a rebmun of sraey the noissucsid of detaler srettam ni the erutaretil of scimonoce dna emag ’,yroeht or esle deriuqer levon citeroeht-emag sisylana [see htoR .])b4891( ehT nalp of siht paper lliw eb as .swollof nI order ot ecalp these stluser ni a cificeps ,txetnoc noitces 2 lliw ylfeirb ebircsed the yrotsih dna noitarepo of the robal tekram for lacidem snretni dna .stnediser noitceS 3 lliw ecudortni a dedis-owt gnihctam ledom of siht ,tekram hcihw lliw eb the yramirp ledom deredisnoc here. A( ediw yteirav of detaler sledom evah yltnecer neeb nwohs ot evah ralimis ,seitreporp dna these other sledom lliw eb referred ot ).yllamrofni A set of stable semoctuo lliw eb ,denifed ylesolc detaler ot the core of the ,tekram dna ti lliw eb deugra that siht dnik of ytilibats si the etairporppa muirbiliuqe tpecnoc for siht dnik of ’.tekram noitceS 4 lliw redisnoc emos of the erom gnikirts seitreporp of the set of elbats ,semoctuo as llew as emos of the gniylrednu larutcurts seitreporp that yam yllautneve edivorp yrotcafsitas laciteroeht snoitanalpxe for these ,anemonehp hcihw are llits ylroop .dootsrednu noitceS 5 lliw redisnoc the evitnecni seitreporp of serudecorp dengised ot ecudorp elbats .semoctuo rehtegoT htiw each of these stluser lliw eb a feirb noitpircsed of the detaler sledom ni hcihw ralimis stluser osla ,dloh dna those ni hcihw yeht liaf ot ,dloh ni order ot ebircsed what si yltneserp nwonk dna( how hcum erom si )nwonknu tuoba the gniylrednu sesuac dna the ytilareneg of these .stluser noitceS 6 lliw redisnoc nepo snoitseuq dna snoisnetxe detseggus yb these ,stluser htob of a laciteroeht ,erutan dna of na laciripme ,erutan gninrecnoc lanoitutitsni dna larudecorp serutaef of .stekram roF‘ ,elpmaxe na mhtirogla tnelaviuqe ot eht eno detpoda ni 1591 saw yltnednepedni desoporp a edaced retal yb elaG dna yelpahS .)2691( daetsnI‘ fo muirbiliuqe‘ ’tpecnoc I dluohs spahrep yas noitulos‘ ’tpecnoc ot etonnoc taht eht noissucsid fo ytilibats lliw eb ni eht krowemarf fo evitarepooc emag .yroeht saereh* eht noissucsid fo sevitnecni lliw eb ni eht krowemarf fo evitarepooc-non emag .yroeht A.E. Roth, Two-sided mutching markets 77 2. ehT robal tekram for naciremA lacidem 3snretni slatipsoH tsrif nageb gnireffo detaudarg-ylwen lacidem stneduts pihsnretni snoitisop dnuora the raey 1900. Not litnu 1945 were the tnaveler lacidem snoitaicossa elba ot etutitsni a elgnis tekram for these snoitisop yb -hsilbatse gni mrofinu dates at hcihw hcus snoitisop dluoc eb offered yb ,slatipsoh dna accepted yb 4.stneduts ecnO siht was ,dehsilpmocca ,revewoh htob stneduts dna slatipsoh were deyamsid yb the citoahc snoitidnoc that depoleved neewteb the emit offers of spihsnretni were tsrif ,edam dna the emit yb hcihw stneduts were deriuqer ot accept or tcejer .meht ehT noitautis that depoleved si debircsed as swollof ni htoR :)b4891( ,yllacisaB‘ the melborp was that a tneduts who was offered na pihsnretni at, ,yas sih driht eciohc ,latipsoh dna who was demrofni he was na etanretla .e.i( no a gnitiaw )tsil at sih dnoces ,eciohc dluow eb denilcni ot tiaw as gnol as elbissop erofeb gnitpecca the noitisop he had been offered, ni the hope of yllautneve gnieb offered a elbareferp .noitisop stnedutS who were derusserp otni gnitpecca offers erofeb rieht etanretla sutats was devloser were yppahnu fi yeht were yletamitlu offered a elbareferp ,noitisop dna slatipsoh whose setadidnac detiaw litnu the tsal etunim ot tcejer meht were yppahnu fi rieht preferred etanretla -nac setadid had ni the emitnaem ydaerla accepted .snoitisop slatipsoH were reippahnu llits nehw a etadidnac who had detacidni ecnatpecca -bus yltneuqes deliaf ot litluf sih tnemtimmoc after gniviecer a elbareferp offer. nI esnopser ot erusserp gnitanigiro ylfeihc morf the ,slatipsoh a seires of llams larudecorp stnemtsujda were edam ni the sraey .15-5491 ehT erutan of these ,stnemtsujda debircsed ,txen sekam raelc how these smelborp were deviecrep yb the seitrap .devlovni roF 1945, ti was devloser that slatipsoh dluohs wolla stneduts net syad after na offer had neeb edam ot redisnoc whether ot accept or tcejer .ti roF 1946, ti was devloser that there dluohs eb a mrofinu tnemtnioppa date yluJ( 1) no hcihw offers dluohs eb ..derednet ,. dna that ecnatpecca or noitcejer dluohs ton eb deriuqer erofeb yluJ 8. yB 1949, [the noitaicossA of naciremA lacideM ]segelloC proposed that stnemtnioppa dluohs eb edam yb margelet at lO:21 MA no( rebmevoN 15), htiw stnacilppa ton gnieb deriuqer ot accept or tcejer meht litnu 00:21 nooN the emas .yad nevE siht ruoh-evlewt gnitiaw doirep was detcejer yb the naciremA latipsoH noitaicossA as too :gnol the tnioj secnerefeR‘ dna rehtruf sliated nac eb dnuof ni htoR ,)b4891( morf hcihw eht lairetam ni siht noitces si .nward ehT4 reilrae seitluciffid deretnuocne ni siht tekram lliw ton nrecnoc su ,ereh tub ees htoR )b4891( rof a noitpircsed fo eht ’srenosirp ammelid melborp taht derefretni htiw eht gnittes fo mrofinu tnemtnioppa setad roirp ot .5491 87 A.E. Roth, Two-sided matching markets noituloser yllanif agreed nopu deniatnoc the phrase on“ deificeps gnitiaw doirep after lO:21 MA si ”,yrotagilbo dna yllacificeps deton that -elet smarg dluoc eb delif ni ecnavda for yreviled ylesicerp at lO:21 .MA nI 1950, the noituloser niaga dedulcni a ruoh-evlewt doirep for -redisnoc ,noita htiw the cificeps noitcnujni that slatipsoH“ ro/dna stneduts llahs ton wollof smargelet of offers of tnemtnioppa htiw enohpelet ”sllac litnu after the ruoh-evlewt grace .doirep [. . the noitcnujni tsniaga enohpelet sllac was ,yaw-owt ni order ot mets a doolf of sllac htob morf slatipsoh gnikees ot erusserp stneduts otni na etaidemmi ,noisiced dna morf stneduts gnikees ot trevnoc rieht etanretla sutats otni a mrif offer.]’ tI was yllautneve dezingocer that these smelborp dluoc ton eb devlos yb gnisserpmoc the tsal stage of the gnihctam process otni a shorter dna shorter emit ,doirep dna ti was agreed ot daetsni yrt a dezilartnec gnihctam ,mhtirogla ot eb desu no a yratnulov .sisab stnedutS dna slatipsoh dluow eunitnoc ot egnahcxe noitamrofni aiv snoitacilppa dna sweivretni as ,erofeb tub neht htob stneduts dna slatipsoh dluow timbus sgniredro-knar of rieht laitnetop ’,stnemngissa dna the mhtirogla dluow eb desu ot tseggus a gnihctam of stneduts ot ,slatipsoh who dluow ,neht ti was hoped, dnif on snosaer ton ot ngis tnemyolpme stcartnoc htiw rieht detseggus .stnemngissa ehT tsrif mhtirogla ot eb proposed was denodnaba after a raey esuaceb ti was devresbo ot evig stneduts the evitnecni ot timbus a gniredro-knar tnereffid morf rieht eurt .secnereferp ehT mhtirogla that was proposed ni sti ecalp was desu for the tsrif emit ni 1951, dna sniamer ni esu ot siht .yad sihT( ,mhtirogla hcihw si debircsed ni xidneppa 1, lliw eb dellac the PMIN ,mhtirogla where PMIN sdnats for lanoitaN nretnI gnihctaM ,margorP hcihw si the eman rednu hcihw the mhtirogla was yllaitini ).deretsinimda Note that siht metsys of gnignarra sehctam was deviecnoc dna -nemelpmi ted as a voluntary erudecorp - stneduts dna slatipsoh were free ot yrt ot egnarra rieht nwo sehctam edistuo of the ,metsys dna there was on snaem of gnicrofne ecnailpmoc no those who did 6.etapicitrap sihT sekam ti lla the erom elbakramer that, ni the tsrif sraey of ,noitarepo revo 950/, of elbigile stneduts dna slatipsoh detapicitrap ni the ,metsys dna these hgih rates of noitapicitrap deunitnoc litnu the ylrae 1970’s. ecniS( ,neht gnisaercni srebmun of ,stneduts ylralucitrap those gnoma the gniworg rebmun of lacidem stneduts who are deirram ot other lacidem ,stneduts evah nugeb ot seek ot gnidrageRS eht melborp fo gnitalumrof a ,gniredro-knar eton taht eht etelpmoc -boj noitpircsed dereffo yb a latipsoh margorp ni a nevig raey saw yliramotsuc deificeps ni .ecnavda suhT eht ,seitilibisnopser ,yralas .cte detaicossa htiw a nevig ,pihsnretni elihw yeht thgim eb detsujda morf raey ot raey ni esnopser ot a s’latipsoh ecneirepxe ni eht suoiverp s’raey ,tekram erew ton a tcejbus fo noitaitogen htiw laudividni boj .setadidnac ehT6 ecneirepxe roirp ot 0591 ylpma detartsnomed taht on tnuoma fo larom noisaus saw evitceffe ta gnitneverp stnapicitrap morf gnitca ni tahw yeht deviecrep sa rieht nwo tseb .stseretni A.E. Roth, Two-sided matching markets 79 egnarra rieht nwo ,sehctam tuohtiw gniog hguorht the dezilartnec ).esuohgniraelc nI the redniamer of siht paper, a ledom lliw eb deiduts that setanimulli a rebmun of elbakramer serutaef of siht .tekram Of ,esruoc how gnitseretni hcus a ledom yletamitlu si lliw dneped ton ylerem no sti lacitamehtam ,seitreporp tub no how llew ti snialpxe the elbavresbo serutaef of stekram ekil the eno debircsed ,evoba dna no how daerpsediw dna tnatropmi hcus stekram are ni the .ymonoce nI ,ralucitrap htiw respect ot the lacirotsih tnempoleved of the tekram for naciremA lacidem ,snretni a lufsseccus ledom dluohs eb elba ot nialpxe the citoahc snoitidnoc roirp ot 1951, the hgih degree of ylredro noitapicitrap after 1951, dna the erutan of the segnahc ni the tekram that detubirtnoc ot a enilced of these hgih rates ni the 1970’s. 3. A ledom of eht nretni-latipsoh tekram ehT stnega ni the nretni-latipsoh tekram tsisnoc of two tniojsid sets H = dna =S .,ls{ . , },s. ’slatipsoh‘( dna 7.)’stneduts‘ Each latipsoh ih (b..,~“j has a quota qi hcihw si the rebmun of stneduts for hcihw ti has .secalp Each tneduts s has a etelpmoc ecnereferp gniredro P(s) revo the set H u {u), dna each latipsoh h has a etelpmoc ecnereferp gniredro P(h) revo the set S u ,}u{ where u setoned the ytilibissop of gniniamer *.dehctamnu tahT ,si each tnega nac erapmoc the ytilibarised of each of sih or her laitnetop ,stnemngissa hcihw are the stnega morf the etisoppo set dna the ytilibissop of gniniamer .dehctamnu nA s’tnega secnereferp are dellac strict fi the tnega si ton -ni tnereffid neewteb yna two tcnitsid laitnetop .stnemngissa tI lliw yfilpmis the noitisopxe ni siht paper ot ylno redisnoc the case ni hcihw lla stnega evah tcirts ,secnereferp dna siht lliw htrofecneh eb ’.demussa Let ,h)s(Pjh etoned that tneduts s prefers latipsoh jh ot latipsoh h,, dna tel ,h)s.(Rjh etoned that he rehtie prefers jh ot h, or esle si .tnereffidni (Note that he nac ylno eb tnereffidni fi =j k, ecnis lla secnereferp are ).tcirts ralimiS noitaton lliw eb desu for the secnereferp of the ,slatipsoh dna P=(P(h,),.. ., P(h,), P(sl), . . , P(s,)) lliw etoned the rotcev of ecnereferp sgniredro of each tnega for stnega no the other edis of the .tekram ,yllamroF‘ hcae h ni H dluohs eb dellac a latipsoh‘ ,’margorp ecnis hcae latipsoh sedivid sti elbaliava spihsnretni otni etarapes ?margorp gnitsisnoc fo lacitnedi ,snoitisop dna eseht >margorp era deretsinimda .yletarapes slatipsoH‘ hcihv~ etah emoh fo rieht <noltiop .dehctamnu dna stneduts ohw era dehctamnu yb eht NIMP .mhtirogla evah eht ytinutroppo OI retne a dezilartneced lekram-retfa‘ taht lliw ton eb dezylana .ereh tu%! ees htoR )c,b8491( rof a tnemtaert fo tcirts-non .secnereferp ,ylsuoiruC elihw ti si tnatropmi rof emos fo eht stluser ni noitces 4 taht secnereferp eb ,tcirts ralimis stluser era nwonk ot dloh rof sledom taht wolla ,stnemyapedis ni hcihw secnereferp yllaitnesse tonnac eb .tcirts emoS selpmaxe fo hcus sledom era esoht fo ylepahS dna kibuhS .)2791( drofwarC dna reonK ,)1891( dna egnameD dna elaG .)4891( esehT sledom esira ,yllarutan nehw yralas si delledom sa a suounitnoc ,elbairav ni robal stekram ni hcihw yralas si ,elbaitogen rof .elpmaxe 80 A.E. Roth, Two-sided matching markets nA outcome ofthe tekram si denifed yb ecnednopserroca x:H u S-+ H u S u {u) hcus that (x(s)( = 1 for lla s ni ,S 1)+1(x( =qi for lla ih ni H, ,dna for yna h ni H dna s ni ,S h=)s(x fi dna ylno fi s si na tnemele of x(h). tahT ,si na emoctuo sngissa a tesbus of the stneduts ot a tesbus of the ,secalp dna sevael the rest of the stneduts dna secalp .dehctamnu fI( a latipsoh h htiw atouq q si dengissa emos rebmun k <q of stneduts at na emoctuo x, neht q-k stnemele of x(h) are lauqe ot ).u No tneduts si dengissa ot erom naht eno ,ecalp dna on latipsoh si dengissa erom naht sti atouq of .stneduts ’stnedutS secnereferp revo semoctuo dnopserroc ylesicerp ot rieht -erp secneref revo ,slatipsoh so that tneduts s prefers emoctuo x ot emoctuo y fi dna ylno fi he prefers latipsoh x(s) ot latipsoh .)y(x ehT secnereferp of slatipsoh revo semoctuo are ylirassecen detaler ot rieht secnereferp revo stneduts ni a erom xelpmoc ,yaw ecnis a latipsoh h htiw atouq q> 1 seviecer tnereffid sets of stneduts dna seicnacav at tnereffid .semoctuo ,yllacificepS tel P’ (h) etoned the ecnereferp noitaler of latipsoh h revo lla stnemngissa x(h) that ti dluoc eviecer at emos emoctuo x. A latipsoh h’s secnereferp P#(h) lliw eb dellac responsive ot sti secnereferp P(h) revo laudividni stnemngissa fi y(h)P#(h)x(h) revenehw y(h) si deniatbo morf x(h) yb gnicalper emos tneduts is (or )u ni x(h) htiw a preferred tneduts oS who si ton ni x(h); ,.e.i revenehw y(h)=x(h) u [s~)\{cT) for CJ ni x(h) dna sk ton ni x(h) hcus that s,P(h)a. tahT ,si a latipsoh h has evisnopser secnereferp revo stnemngissa ,fi for yna two stnemngissa that reffid ni ylno eno ,tneduts ti prefers the tnemngissa gniniatnoc the erom preferred .tneduts roF ,elpmaxe fi x(h) sngissa latipsoh 11 htiw a atouq of qh = 2 sti 3rd dna 4th eciohc ,stneduts dna )11(y sngissa ti sti dn2 dna 4th eciohc ,stneduts neht latipsoh h prefers )h(y ot x(h) fi sti secnereferp are .evisnopser slatipsoH lliw htrofecneh eb demussa ot evah secnereferp revo sets of stneduts that are evisnopser as llew as .tcirts Note that ynam tnereffid evisnopser ecnereferp sgniredro P#(h) tsixe for yna ecnereferp P(h), ,ecnis for ,elpmaxe ssenevisnopser does ton yficeps whether a latipsoh htiw a atouq of 2 prefers ot eb dengissa sti ts1 dna 4th eciohc stneduts daetsni of sti dn2 dna 3rd eciohc .stneduts ,revewoH the ecnereferp gniredro P(h) revo laudividni stneduts nac eb devired morf P#(h) yb gniredisnoc a latipsoh s‘~11 secnereferp revo stnemngissa x(/z,) gniniatnoc on erom naht a elgnis tneduts dna( qi - 1 seipoc of .)u ecniS[ P(h) si yletelpmoc denimreted yb P#(h), ti nac eb thguoht of as a yrammus of the lluf ].secnereferp ehT secnereferp of the slatipsoh revo tnereffid semoctuo x dna y nac won eb deificeps as gnidnopserroc ylesicerp ot rieht secnereferp revo rieht nwo stnemngissa at x dna ;y ,.e.i a latipsoh hi prefers x ot y fi dna ylno fi x(h,)P#(h,)y(h,). etoneD yb P’ the rotcev of secnereferp P# =(P#(h,),...,P#(h,), P(sl),. . , P(s,)), hcihw scnited the secnereferp of the stnega revo lla elbisaef .semoctuo A.E. Roth, Two-sided matchina markets 81 nA emoctuo x si individually rational fi for yreve tneduts s, ,u)s(R)s(x dna fi for yreve latipsoh h dna CJ ni x(h), .u)h(Ro nA emoctuo x si unstable fi ti si ton yllaudividni lanoitar or fi there tsixe a latipsoh h dna a tneduts s who are ton dehctam at x[.x(s)#h] dna who each prefer eno rehtona ot eno of rieht ;stnemngissa ,.e.i hcus that hP(s)x(s) dna sP(h)o for emos c ni x(h). nA emoctuo x that si ton elbatsnu lliw eb dellac stable, dna the set of elbats semoctuo htiw respect ot yna rotcev P of ecnereferp sgniredro lliw eb detoned S(P).’ O nA tnatropmi laiceps case of siht nretni-latipsoh ,!edom hcihw has deviecer the tsom noitnetta ni the citeroeht-emag ,erutaretil si the cirtemmys tekram that stluser nehw lla satouq are lauqe ot ;1 ni siht case the ledom si dellac the egairram‘ ’melborp dna( the two sets of stnega are referred ot as ’nem‘ dna .)’nemow‘ nI siht ,erutaretil the noitautis where eno set of stnega has satouq that yam eb greater naht 1 si referred ot as the egelloc‘ snoissimda ,’melborp dna ti emaceb yramotsuc ot yficeps egelloc snoissimda smelborp ylno pu ot the tniop of gniyficeps the ’segelloc secnereferp revo laudividni ,stneduts tuohtiw gniredisnoc secnereferp revo ”.semoctuo roF a gnol emit ti tnew decitonnu that siht level of noitpircsed deliaf ot yficeps the egelloc snoissimda melborp as a denifed-llew ,emag neve hguoht the egairram melborp si yltcefrep llew denifed ni siht ”.rennam roF siht ,nosaer lla smeroeht devorp for the egairram melborp were thguoht ot yrrac revo yllautriv degnahcnu ot the egelloc snoissimda .melborp sihT snrut tuo ton ot eb the :esac elihw ynam seitreporp of the egairram melborp do yrrac revo ot the case where secnereferp are evisnopser dna satouq no eno edis of the tekram deen ton lauqe 1, other tnatropmi seitreporp do 31.ton nI siht paper, smeroehT 4.2d dna 5.3 etartsulli siht .tniop ehT set of elbats semoctuo si ylesolc detaler ot the core of the emag that sesira morf the nretni-latipsoh tekram nehw the selur are that yna tneduts dna latipsoh yam ngis na tnemyolpme tcartnoc fi yeht htob agree. tI si devorp ni xidneppa 2 that the set of elbats semoctuo slauqe the core denifed yb weak .noitanimod nI( the laiceps case of the egairram ,melborp siht sedicnioc htiw the core denifed yb gnorts ).noitanimod desaB‘“ no eht noitiniled sa nevig ,ereh dna ni weiv fo eht tcaf taht slatipsoh evah secnereferp denifed rebo stes fo stneduts dna ,seicnacav ti thgim mees retteb ot llac hcus semoctuo prrirw~isc ,elbats dna ot osla redisnoc emos mrof fo puorg ,ytilibats esohw tnemetats dluow evlovni spuorg fo slatipsoh dna stneduts taht thgim eb regral naht ,sriap dna ’slatipsoh secnereferp P# rehtar naht P. nI xidneppa 2 ti si nwohs taht eseht owt snoitinifed era tnelaviuqe nehw secnereferp era .evisnopser ,.e.I“ P saw ,deificeps tub ton PG. nehW“ lla satouq lauqe ,1 ’P = P. sihT“ noitacificeps-sim dna sti secneuqesnoc saw tsrif deton ni htoR ,)e4891( hcihw osla sniatnoc emos erom deliated secnerefer ot suoenorre stnemetats ni eht .erutaretil roF a elpmis ledom htiw ,stnemyapedis drofhcoR )4891( sevresbo rehtruf tnatropmi secnereffid neewteb eht esac fo eno-ot-eno gnihctam dna eht esac fo eno-ot-ynam gnihctam ni hcihw smrif kees ot llif ,elpitlum suoenegoreteh snoitisop htiw spuorg fo suoenegoreteh .srekrow 82 A.E. Roth, Two-sided matching markets Before gnissucsid the seitreporp of elbats semoctuo ni siht ,tekram tel su tsrif redisnoc yhw siht noitinifed of ytilibats thgim eb na etairporppa muirbiliuqe noiton for stekram of siht ,dnik dna how ti thgim eb desu ot ,nialpxe for ,elpmaxe the yrotsih of the ralucitrap tekram deniltuo ni the suoiverp .noitces nI htoR ,)b4891( siht was approached ni the gniwollof 41:yaw redisnoC‘ won a set of boj offers morf slatipsoh ot )elbatpecca( stneduts ,hcihw fi the stneduts each accept the tseb of the offers yeht evah deviecer gnidulcni( the ytilibissop of gniniamer ,)dehctamnu dluow tluser ni na elbatsnu emoctuo x. ehT fact that x si elbatsnu snaem that there si a latipsoh ih dna a tneduts js who dluow htob prefer ot x rehtona emoctuo at hcihw js was deyolpme yb hi. So these two stnega evah na evitnecni ot yrt ot etacol each other, dna we thgim expect ot ssentiw the dnik of etunim-tsal liomrut devresbo ni the nretni tekram roirp ot 1951. gnikooL at the other edis of the ,nioc we thgim expect that yna yratnulov metsys of gnizinagro the tekram dluow ecneirepxe ralimis liomrut fi ti decudorp elbatsnu .semoctuo ecniS the PMIN si a yratnulov metsys that has deniatniam a hgih degree of ylredro -icitrap noitap for ynam ,sraey ti si elbanosaer ot erutcejnoc that ti secudorp elbats ,semoctuo .e.i semoctuo ni the core of the ’.tekram sihT erutcejnoc snrut tuo ot eb correct, as lliw eb dessucsid ,woleb dna so siht noitalumrof of ytilibats snrut tuo ot evah a elbanosaer tnuoma of yrotanalpxe power for the roivaheb of the nretni-latipsoh tekram -mi yletaidem erofeb dna after the noitpoda of the PMIN .mhtirogla eW lliw osla see that the emas laciteroeht tcurtsnoc nac eb desu ot nialpxe the gnisaerced rates of noitapicitrap as deirram selpuoc started ot ekam pu a elbaeciton noitcarf of the lacidem tneduts ,noitalupop ecnis the erudecorp desu ot hctam deirram selpuoc decudorp elbatsnu .semoctuo suhT the yrotanalpxe power of siht noiton of ytilibats si ton detimil ot eno edosipe ni the yrotsih of siht .tekram nI the txen noitces we lliw see that ti lliw osla etanimulli yhw siht gnisaerced rate of noitapicitrap si ylekil ot evorp tluciffid ot .evloser 4. elbatS semoctuo ehT stluser stated yllamrof as smeroeht ni siht noitces lla ylppa ot the nretni-latipsoh ledom of the suoiverp ,noitces ni hcihw secnereferp are tcirts dna .evisnopser ehT tsrif of these si na ecnetsixe ,meroeht hcihw osla speaks ot the noitseuq of yhw the PMIN mhtirogla was so lufsseccus ni the robal tekram for .snretni A41 tneduts s si acceptable ot h fi sP(h)u; ,.e.i fi eht latipsoh sreferp gniyolpme s ot gnivael a noitisop .tnacav A.E. Roth, Two-sided matching markets 83 4.1. Existence fo stable outcomes Theorem 4.1. roF any vector P fo preferences, the set )P(S fo stable outcomes si non-empty. ,eromrehtruF fi students and slatipsoh submit rank-order stsil ,P then the PMIN algorithm produces an outcome ni .)P(S ehT tsrif lamrof ecnetsixe tluser of siht dnik ot appear ni the erutaretil si eud ot elaG dna yelpahS (1962), who were ton aware of the PMIN ,mhtirogla tub proposed na tnelaviuqe 51.mhtirogla A rebmun of srohtua evah ylevitcurtsnoc devorp the ecnetsixe of elbats semoctuo ni erom lareneg dedis-owt gnihctam ,stekram yb gnipoleved detaler .smhtirogla Crawford dna reonK (1981) dehsilpmocca siht for a tekram ni hcihw workers’ seiralas dna boj snoitpircsed are denimreted ,ylsuonegodne dna osleK dna Crawford (1982) dezilareneg siht ot a case ni hcihw the rebmun of workers deyolpme yb a nevig mrif si osla denimreted ,ylsuonegodne daetsni of gnieb denimreted yb a atouq that si tnednepedni of hcihw workers are 6i.deyolpme ehT nommoc serutaef of these smhtirogla are llew derutpac ni a noitalumrof eud ot rialB .)b,a4891( tI si worth gniton that these smhtirogla evah ecin lanoitatupmoc seitreporp [see eitiVcM dna nosliW (1971), htunK (1976), senoJ (1983)]. elaG dna yelpahS osla showed that the ecnetsixe of elbats semoctuo sdneped no the dedis-owt erutcurts of the ,tekram yb gnivresbo that ni the dedis-eno golana of the egairram ,melborp hcihw yeht dellac the etammoor‘ ,’melborp the set of elbats semoctuo yam eb ”.ytpme ,revewoH a tnecer paper yb iizniuQ (1984) stneserp a evitcurtsnoc-non proof that stseggus snoitcennoc neewteb the ecnetsixe of elbats semoctuo ni these dedis-owt ,stekram dna ecnetsixe stluser for niatrec dedis-eno stekram htiw etercsid ?sdoog eW nrut won morf snoitseuq of ecnetsixe ot na noitanimaxe of the erutcurts of the set of elbats .semoctuo ehT51 sfoorp fo smeroehT 1.4 dna a2.4 ni htoR )b4891( yllaitnesse dedeecorp yb -tartsnomed gni siht .ecnelaviuqe ‘% eht ledom fo osleK dna ,drofwarC emos lanoitidda snoitpmussa tuoba ’smrif secnereferp era deriuqer ot erussa eht ecnetsixe fo elbats .semoctuo yehT osla dnif ti tneinevnoc ot ledom yralas sa a etercsid ,elbairav ,.g.e sa nehw yralas nac eb deificeps ylno pu ot eht tseraen .ynnep A ylesolc detaler ledom dna mhtirogla si derolpxe ni htoR .)a4891( ehT“ etammoor melborp si denifed yb a elgnis tes N fo ,sreyalp hcae fo mohw sah secnereferp revo lla eht rehto .sreyalp ehT tes fo elbisaef semoctuo si eht tes fo lla snoitititrap fo eht sreyalp otni ,sriap dna na emoctuo si elbatsnu ni esac ereht era owt sreyalp ton dehctam ot rehtongeno hcae fo mohw sreferp eht rehto ot eht reyalp eh si dehctam .htiw esehTa‘ .stekram hcihw era deiduts vb velpahS dna fracS ,)4791f htoR dna etiaweltsoP )7791( dna htoR ,)b2891( kcal neve eht laretalib ’gnihctam‘ ytreporp ’fo eht rehto stekram deredisnoc ,ereh ,revewoH hcae redart ni eseht stekram sah na laitini tnemwodne fo a elgnis tinu fo na elbidividni ,ytidommoc os ereht si a esnes ni hcihw hcae redart si ’deifitnedi‘ htiw sih .ytidommoc okenaK dna sredooW )2891( yduts eht noitseuq fo woh eht ecnetsixe fo elbats semoctuo si detaler ot ,ssendedis-owt yb gniredisnoc tahw rehto snoitcirtser no hcihw snoitilaoc nac ylevitcudorp mrof lliw osla dleiy a ytpme-non eroc rof yreve citsiretcarahc .noitcnuf E.E.R. E 48 .E.A ,htoR dedis-owT gnihctam stekram 4.2. Conflict and coincidence of interest Perhaps the tsom gnikirts erutaef of these dedis-owt gnihctam stekram si the yaw the tnerappa snrettap of nommoc dna gnitcilfnoc tseretni gnoma dna neewteb the stnega no tnereffid sedis of the tekram are desrever nehw we enifnoc ruo noitnetta ot the set of elbats .semoctuo nehW we kool at the eritne set of elbisaef semoctuo elbatsnu( as llew as ,)elbats ti si larutan ot kniht of stneduts as gnitepmoc htiw eno rehtona for elbarised secalp ni ,slatipsoh elihw slatipsoh etepmoc htiw eno rehtona for elbarised .stneduts suhT elihw stnega no etisoppo sedis of the tekram evah a nommoc tseretni ni gnignarra sehctam htiw eno ,rehtona stnega no the emas edis of the tekram evah stseretni that tcilfnoc at tsael ot emos degree.19 ehT gniwollof two stluser show how yllacitamard the noitautis segnahc nehw we kool at the nommoc dna gnitcilfnoc stseretni of the stnega no the set of elbats .semoctuo roF a nevig ecnereferp eliforp P, a tneduts s dna a latipsoh h lliw eb dellac achievable for eno rehtona fi there si emos elbats emoctuo at hcihw s si deyolpme yb h ,.e.i[ fi there si na emoctuo x ni S(P) hcus that x(s) = h]. roF each hi, tel ir eb the mumixam rebmun of stneduts deyolpme at yna elbats emoctuo iv( 5 qi). Theorem 4.2a. In the set S(P) of stable outcomes, there is a Hospital-optimal stable outcome x* with the property that every hospital is assigned its ri most- preferred achievable students, and a Student-optimal stable outcome y* with the property that every student is assigned his most-preferred achievable hospital. (The NIMP algorithm selects the H-optimal stable outcome.) Theorem 4.2b. At the H-optimal stable outcome x*, each student is matched with his least-preferred achievable hospital, while at the S-optimal stable outcome y*, each hospital is matched with its ri least preferred achievable students. ecniS ’slatipsoh secnereferp are ,evisnopser siht seilpmi that lla slatipsoh agree that x* si the tsom elbareferp elbats emoctuo dna *y the tsael ,elbareferp elihw stneduts lla agree that *y si the tseb dna x* the worst.” ,suhT yrartnoc ot the erutcip detniap evoba of stneduts gnitepmoc htiw eno rehtona for the tseb slatipsoh dna slatipsoh for the tseb ,stneduts nehw we sihT“ tcilfnoc si tsetaerg eht erom stnega no eht emas edis fo eht tekram evah nommoc secnereferp revo stnega no eht rehto .edis nA emertxe elpmaxe si nehw lla stneduts evah eht emas eciohc-tsrif ,latipsoh dna lla slatipsoh evah eht emas eciohc-tsrif .tneduts nI siht esac lla stneduts era gnitepmoc rof eht emas ,noitisop dna lla slatipsoh rof eht emas .tneduts esuaceB“ fo eht noitinifed fo ir desu ,ereh eseht stluser era a elttil tnereffid morf eht ralimis stluser devorp ni htoR ,)b4891( tub ni weiv fo meroehT a3.4 yeht era .tnelaviuqe ehT tseilrae stluser fo siht mrof rof eht egairram melborp ni( hcihw lla ir = )1 era dnuof ni elaG dna yelpahS )2691( dna htunK ,)6791( ,ylevitcepser elihw ralimis stluser rof a tnemyapedis ledom era dnuof ni yelpahS dna kibuhS .)2791(