ThreesomeRoommatesProblems
Chien-ChungHuang
DartmouthCollegevillars@cs.dartmouth.edu
Abstract.WeinvestigateKnuth’seleventhopenquestiononstablematchings.Inthestablefamilyproblem,setsofwomen,men,anddogsaregiven,allofwhomstatetheirpreferencesamongtheothertwogroups.Thegoalistoorganizethemintofamilyunits,sothatnothreeofthemhaveincentivetodeserttheirassignedfamilymemberstojoininanewfamily.Asimilarproblem,calledthethreesomeroommatesproblem,assumesthatagroupofpersons,eachwiththeirpreferencesamongthecombinationsoftwoothers,aretobepartitionedintotriples.Similarly,thegoalistomakesurethatnothreepersonswanttobreakupwiththeirassignedroommates.
NgandHirschbergwerethefirsttoinvestigatethesetwoproblems.Intheirfor-mulation,eachparticipantprovidesastrictly-orderedlistofallcombinations.Theyprovedthatunderthisscheme,bothproblemsareNP-complete.Theirpa-perreviewerspointedoutthattheirreductionexploitsinconsistentpreferencelistsandtheywonderwhetherthesetwoproblemsremainNP-completeifpreferencesarerequiredtobeconsistent.Weanswerintheaffirmative.
Inordertogivethesetwoproblemsabroaderoutlook,wealsoconsiderthepos-sibilitythatparticipantscanexpressindifference,ontheconditionthatthepref-erenceconsistencyhastobemaintained.Asanexample,weproposeaschemeinwhichallparticipantssubmittwo(orjustoneintheroommatescase)listsrankingtheothertwogroupsseparately.Theorderofthecombinationsisdecidedbythesumoftheirordinalnumbers.Combinationsaretiedwhenthesumsareequal.Byintroducingindifference,ahierarchyofstabilitiescanbedefined.WeprovethatallstabilitydefinitionsleadtoNP-completenessforexistenceofastablematch-ing.
1ProblemDefinition
Knuthproposedtwelveopenquestionsonthestablematchingproblem[9].Theeleventhquestionaskswhetherthewell-studiedstablemarriageproblem[3]canbegeneralizedtothecaseofthreeparties,women,men,anddogs.Inthispaper,wecallthisproblemthestablefamilyproblemandrefergenericallytoallparticipantsinthisproblemas“players.”Roughlyspeaking,givensetsofwomen,men,anddogs,allofwhomstatetheirpreferencesamongtheothertwogroups,thegoalistoorganizethemintofamilyunitssothatthereisnoblockingtriple:threeplayerseachpreferringoneanothertotheirassignedfamilymembers.Aprobleminasimilarvein,whichwecallthethree-someroommatesproblem,assumesthat3nstudentsaretobeassignedtothedormitorybedroomsinsomecollege.Theystatetheirpreferencesofthecombinationsoftwoother
persons.Thegoalistopartitionthemintosetsofsize3.Suchapartition(matching)issaidtobestableifnothreepersonseachprefertheotherstotheirassignedroommates.
AsKnuthdoesnotspecifyanyprecisedefinitionof“preference”and“blockingtriples,”onecanconceiveanumberofwaystodefinethetwoproblems.Onepossi-bleformulationisthateachplayersubmitsastrictly-orderedpreferencelist,rankingallpossiblecombinationsthatshe/he/itcangetinamatching.Wecallsuchaschemestrictly-ordered-complete-list(SOCL)scheme.Inthissetting,NgandHirschberg[10]provedthatbothproblemsareNP-complete.
Attheendoftheirpaper,NgandHirschbergmentionedthattheirreviewerspointedouttheirreductionallowspreferencetobeinconsistent.Forexample,manmmightrank(w1,d1)higherthan(w2,d1),buthealsoranks(w2,d2)higherthan(w1,d2).Inotherwords,hedoesnotconsistentlypreferwomanw1overwomanw2(northeotherwayaround).Independently,Subramanian[11]gaveanalternativeNP-completenessproofforstablefamily,buthisreductionalsousesinconsistentlists.
ThereviewersofNgandHirschbergwonderedwhetherthesetwoproblemsremainNP-completeifinconsistencyisdisallowed.Toanswerthisopenquestionandtomo-tivatesomevariantsproblemswewilldefine,weintroducethenotionofpreferenceposetsandsimplelists.Instablefamily,assumingthateachplayerhastwosimplelistsinwhichtwodifferenttypesofplayersarerankedseparately,apreferenceposetisaproductposetofthetwosimplelists.Insuchaposet,thecombination(w1,d1)pre-cedesanothercombination(w2,d2)onlyifw1ranksatleastashighasw2andd1atleastashighasd2inthesimplelists.Ifneithercombinationprecedestheother,theyareincomparable.Similarly,inthreesomeroommates,thepreferenceposetistheprod-uctposetoftheonesimplelistwithitself.Bythisnotion,thequestionraisedbythereviewersofNgandHirschbergcanberephrasedasfollows.UndertheSOCLscheme,ifeveryplayerhastosubmitapreferencelistwhichisalinearextensionofher/his/itspreferenceposet,arethestablefamilyandthethreesomeroommatesstillNP-complete?Weanswerintheaffirmative.
Inanattempttogivethesetwoproblemsabroaderoutlook,wethenallowplayerstoexpressindifferencebygivingfullpreferencelistscontainingties.Inparticular,tocapturethespiritofmaintainingconsistencyinthepreferences,westipulatethatthefulllistmustbearelaxedlinearextensionofapreferenceposet:strictprecedenceorderintheposethastobeobservedintherelaxedlinearextension;onlyincomparableelementsintheposetcanbetied.
Weproposethefollowingschemetomaketheaboveconceptconcrete.Supposethataplayersubmitstwosimplelists(orjustoneintheroommatescase).Wecreateafulllist,rankingthecombinationsbasedonthesumsoftheirordinalnumbers.Forexample,formanm,thecombinationofhisrank-2womanandrank-5dogisasgoodasthatofhisrank-4womanandrank-3dog;whilebothofthemareinferiortothecombinationofhistop-rankedwomanandhistop-rankeddog.Wecallsuchaschemeprecedence-by-ordinal-number(PON)scheme.ThePONschemeproducesfullpreferencelistswhicharerelaxedlinearextensionsofpreferenceposets.Also,onecanenvisageanevenmoreflexiblescheme.Forexample,insteadofgiving“ranks,”theplayerscanprovide“rat-ings”ofotherplayers.Theorderofthecombinationscanbedecidedbythesumoftheratings;twocombinationsaretiedonlywhenthesumsoftheirratingsareequivalent.
Settingtheoreticalconcernsasideforamoment,theaboveschemesareprobablymorepracticablewhennislarge,becauseaplayeronlyhastoprovidelistsofΘ(n)length,whileundertheSOCLscheme,theyhavetogivestrictlyorderedlistsofsizeΘ(n2).
Byallowingindifference,wecandefine4differenttypesofblockingtriplesand,basedonthem,buildupahierarchyofstabilities.(ThishierarchyissimilartothatconstructedbyIrvinginthecontextof2-partystablematchings[7].)
–WeakStableMatching:ablockingtripleisoneinwhichallthreeplayersoftheblockingtriplestrictlyprefertheothertwomembersinthetripleovertheirassignedfamilymembers(roommates).
–StrongStableMatching:ablockingtripleisoneinwhichatleasttwoplayersoftheblockingtriplestrictlyprefertheothertwoplayersinthetripletotheirassignedfamilymembers(roommates),whiletheremainingplayercanbeindifferentoralsostrictlyprefertheothertwoplayersinthetriple.
–SuperStableMatching:ablockingtripleisoneinwhichatleastoneplayeroftheblockingtriplestrictlypreferstheothertwoplayersinthetripletoher/his/itsassignedfamilymembers(roommates),whiletheremainingplayerscanbeindif-ferentoralsostrictlyprefertheothertwoplayersinthetriple.
–UltraStableMatching:ablockingtripleisoneinwhichallthreeplayersinthetripleareatleastindifferenttotheothers.
Notethatiftiesarenotallowedinthefullpreferencelists,i.e.,theSOCLscheme,thenblockingtriplescanonlybeofdegree3.Thustherecanbeonlyonetypeofsta-bility.Forpresentationalreason,inthiscase,werefertothestabilityundertheSOCLschemeastheweakstability.
OurResultsandPaperRoadmapWewillproveinthepaperthat,iffullprefer-encelistsare(relaxed)linearextensionsofpreferenceposets,theproblemofdecidingwhetherweak/strong/super/ultrastablematchingsexistisNP-completeinboththesta-blefamilyproblemandthethreesomeroommatesproblem.OurreductiontechniquesareinspiredbyNgandHirschberg’s,althoughtheconsistencyrequirementinthepref-erencesmakesourconstructionmoreinvolved.Inpresentingourresult,insteadofdi-rectlyansweringtheopenquestionposedbyNgandHirschberg’sreviewersbystudyingweak-stability,wemakeadetourtofirststudystrong/super/ultrastability.Introducingthemfirsthelpsustoexplainourintuitionbehindthemorecomplexreductionfortheformerproblem.
Asiswell-known,thestablemarriageandthestableroommatesproblemscanbesolvedinO(n2)time,bytheGale-Shapleyalgorithm[3]andbytheIrvingalgo-rithm[6],respectively.Unfortunately,ourresults,alongwithNgandHirschbergandSubramanian’s,indicatethatattemptstoefficientlysolvethestablematchingproblemingeneralizedcasesofthree(ormore)partiesareunlikelytobefruitful.Thisisnotsurprising,asintheoreticalcomputerscience,thefinelinebetweenPandNPisoftendrawnbetweenthenumberstwoandthree.
Weorganizethepaperasfollows.InSection2,wepresentnecessarynotation;Sec-tion3provestheNP-completenessofstrong/super/ultrastablematchingsinthestablefamilyproblemunderthePONscheme;Section4presentsareductiontotransform
astablefamilyproblemtoathreesomeroommateproblem,thusestablishingtheNP-completenessofstrong/super/ultrastablematchingsinthelatter;Section5considerstheSOCLschemeandprovestheNP-completenessof(weak)stablematchings,therebyansweringtheopenquestionposedbytheanonymousreviewersofNgandHirschberg.Section6concludesanddiscussesrelatedissues.Duetospaceconstraint,weomitsomeproofs.See[5]forfulldetails.
2Preliminaries
WeuseM,W,Dtoindicatethesetsofmen,women,anddogsinstablefamily;thestudentsinthreesomeroommatesaredenotedasR.Instablefamily,Lg(p)denotesthesimplelistofplayerpontheplayersoftypeg∈{M,W,D}.ForexampleLW(m)isthesimplelistofmanmamongwomenW.Inthreesomeroommates,wesimplywriteL(m),wherem∈R,droppingthesubscript.
Ingeneral,weusethenotation≻todenotetheprecedenceorder(ineitherposetsorinlinearlists).Forexample,supposingthatpirankshigherthanpjinthelistl,wewritepi≻lpj.InaposetQ,twoelementsqi,qjeitheroneprecedestheother,whichwewriteqi≻Qqjorqj≻Qqi,ortheyareincomparable,whichisexpressedasqi||Qqj.Thenotation≻isalsousedtoexpressexplicitlytheorderofplayersinsimplelists.Forexample,wewriteL(p)=q≻r≻···toshowthatplayerpprefersplayerqtoplayerr.Notealsothatthenotation···denotestheremainingplayersinarbitraryorder.Weusethenotationrp(q)toindicatetherankofqonplayerp’ssimplelist.
Wesayablockingtripleisofdegreei,ifiplayersstrictlypreferthetriplewhiletheremaining3−iplayersareindifferent.Unlessstatedotherwise,inthearticle,whenwesaysometriple“blocks,”itisalwaysablockingtripleofdegree3.
Apreferenceposetconstructedfromlistsl1andl2iswrittenasl1×l2.Tobeprecise,givenlistsl1andl2andtheposetl1×l2,supposingthat{pi,pj},{pi′,pj′}∈l1×l2,then{pi,pj}≻l1×l2{pi′,pj′}onlyif(1)pi≻l1pi′,pj=pj′,or(2)pj≻l2pj′,pi=pi′,or(3)pi≻l1pi′,pj≻l2pj′.Thenotationπ(X)meansanarbitrarypermutationofelementsinthesetX.Eπ(l1×l2)isanarbitrarylinearextensionofthepreferenceposetl1×l2.
3ReducingThree-dimensionalMatchingtoStableFamily
Inthissection,wefocusontheNP-completenessofstrongstablematchingunderthePONscheme.Similarresultsholdforsuperstableandultrastablematchingsbyastraightforwardargumentandwillbediscussedattheendofthissection.
Ourreductionisfromthethree-dimensionalmatchingproblem,oneofthe21NP-completeproblemsinKarp’sseminalpaper[8].TheprobleminstanceisgivenintheformΥ=(M,W,D,T),whereT⊆M×W×D.ThegoalistodecidewhetheraperfectmatchingM⊆Texists.ThisproblemremainsNP-completeevenifeveryplayerinM∪W∪Dappearsexactly2or3timesinthetriplesofT[4].
Wefirstexplaintheintuitionbehindourreduction.Supposingthatmanmiap-pearsinthreetriples(mi,wia,dia),(mi,wib,dib),(mi,wic,dic)inT,wecreatethreedopplegangers,mi1,mi2,mi3inthederivedstablefamilyprobleminstanceΥ′.We
gggg
alsocreatefourgarbagecollectors,wi1,di1,wi2,di2.Eachdopplegangermijputsa
woman-dogpair,withwhommanmisharesatriple,andthegarbagecollectorsontopofhistwosimplelists.Thegoalofourdesignisthatinastablematching,exactlyonedopplegangerwillbematchedtoawoman-dogpairwithwhommisharesatripleinT,whiletheothertwodopplegangerswillbematchedtogarbagecollectors.InthecasethatthereareonlytwotriplesinTcontainingmanmi,weartificiallymakeacopyofoneofthetriples,makingthetotalnumberoftriplesthree,andtreathimasdescribedabove.
Now,wewillrefertothesetofdopplegangersasM1,M2,M3,thesetofgarbage
gggg
collectorsasW1,W2,D1,D2andtheoriginalsetofrealwomenandrealdogsasW,D.
gggg
Collectively,werefertothemasX=M1∪M2∪M3∪W1∪W2∪W∪D1∪D2∪D.
Torealizeourplan,weintroducetwogadgets.Thefirstisthreesetsof“dummy
########
players”:m#1,w1,d1,m2,w2,d2,m3,w3,d3.Theirpreferencesaresuchthattheymustbematchedtooneanotherinastablematching.Tobeprecise,forj∈{1,2,3},
###
–LW(m#j)=wj≻···,LD(mj)=dj≻···
###
–LM(wj)=m#j≻···,LD(wj)=dj≻···###–LM(d#j)=mj≻···,LW(dj)=wj≻···
Theseninedummyplayersareusedto“pad”thepreferencelistsofotherplayers.Theirpurposewillbeclearshortly.
Anothergadgetweneedisasetof“guardplayers”foreachdopplegangerinM1∪M2∪M3.Theywillmakesurethatinastablematching,adopplegangermijwillonlygetawoman-dogpairwithwhommisharesatripleinTorthosegarbagecollectors.Asanexample,considerthedopplegangermi1.Hehassixassociatedguardplayers,1♭1♭1♭2♭2♭2m♭i1,wi1,di1,mi1,wi1,di1andtheirpreferencesaresummarizedbelow:
gg###♭1♭2–LW(mi1)=wi2≻wi1≻wia≻wi1≻wi1≻w1≻w2≻w3≻···,
g###♭2♭1
LD(mi1)=dgi2≻di1≻dia≻di1≻di1≻d1≻d2≻d3≻···
1♭1♭1♭1
–LW(m♭i1)=wi1≻···,LD(mi1)=di1≻···
2♭2♭2♭2
LW(m♭i1)=wi1≻···,LD(mi1)=di1≻···
#♭1♭1♭1♭1
–LM(wi1)=mi1≻mi1≻···,LD(wi1)=di1≻d1≻···
#♭2♭2♭2♭2
LM(wi1)=mi1≻mi1≻···,LD(wi1)=di1≻d1≻···
#1♭1♭1♭1
–LM(d♭i1)=mi1≻mi1≻···,LW(di1)=wi1≻w1≻···
#2♭2♭2♭2
LM(d♭i1)=mi1≻mi1≻···,LW(di1)=wi1≻w1≻···
Thefollowingcaseanalysisprovesthat,inastablematchingM′,mi1willgetonly
gggg
playersfromtheset{wi1,wi2,wia,di1,di2,dia}.
♭1♭1–Supposethatmi1getstwoplayersrankingbelowwi1anddi1respectively.Itcanbe
♭1♭1
observedthatforbothwi1,di1,thebestmanismi1.Therefore,theywouldprefermi1andsodoeshethem,inducingablockingtripletoM′,acontradiction.
gg
–Supposethatmi1getsawomanw∈{wia,wi1,wi2}andadogdrankingbelow
###1
d♭i1.Inthiscase,wecanbesurethatdcannotbed1ord2ord3,sincetheirpreferencesguaranteethattheywillonlybematchedtootherdummyplayers.So,
♭1♭1♭1♭1
rmi1(w)+rmi1(d)≥10,whilermi1(wi1)+rmi1(di1)=9,causing(mi1,wi1,di1)
tobecomeablockingtriple.Thisexampleexplainswhyweneedtopadthesimplelistsofmi1withdummyplayers.
g
Thecasethatmi1getsadogd∈{dia,dgi1,di2}andawomanwrankinglowerthangg♭2wi1followsanalogousarguments;(mi1,wi2,di2)willbecomeablockingtriple.
♭1♭2♭1♭2
–Supposethatmi1getsonlyoneoftheplayersfromtheset{wi1,wi1,di1,di1}.
♭1φφ♭1
Withoutlossofgenerality,weassumethat(mi1,wi1,d),d=di1,ispartofthe
#♭1φ
matching.Forwomanwi1,dogdcannotbethedummyplayerd1.Therefore,
1♭1♭1
rw♭1(mi1)+rw♭1(dφ)≥4>3=rw♭1(m♭♭1(di1).Similarlyfordi1,i1)+rwii1i1i11
♭1♭1
rd♭1(mi1)+rd♭1(wi1)=3,whichisbetterthanwhatevercombinationitcanget.i1i1
1♭1♭1′
Therefore,wehavethat(m♭i1,wi1,di1)constitutesablockingtripletoM.This
♭1♭1♭2♭2
exampleshowswhyweneedtopadthepreferenceofwi1,di1(andalsowi1,di1)withdummyplayers.
♭1♭1♭1♭2♭2♭1
–Supposethatmi1getswi1anddi1.Notethatwi1≻wi1anddi1≻di1.There-♭2♭2♭1fore,mi1isindifferenttothecombinationsofwi1anddi1,sincermi1(wi1)+
1♭2♭2♭2♭2
rmi1(d♭i1)=9=rmi1(wi1)+rmi1(di1).Additionally,wi1,di1strictlyprefer
♭2♭2′
mi1.Hence(mi1,wi1,di1)constitutesablockingtripleofdegree2toM.Thisexplainswhyweneedtwosetsofguardplayerstoguaranteethatthedopplegangerwill“behave”inastablematching.
♭2♭2
Thecasethatmi1getswi1anddi1followsanalogousarguments.Theothertwodopplegangersmi2,mi3alsohavesixassociatedguardplayersforeach;they,alongwiththeirassociatedguardplayers,havesimilarpreferencestoguar-anteethatmi2andmi3willonlygetgarbagecollectorsorthewoman-dogpairswithwhommisharestriples.Theonlydifferenceinthelistsisthatmi2andmi3replacewia,diawithwib,dib,andwithwic,dic,respectively,intheirsimplelists.Forasum-maryofthesimplelistsofmembersinthesetX,seeTable1.Itshouldbenoted
gggg
thatwi1,di1(andalsowi2,di2)rankthethreedopplegangersinreverseorder.Thistrickguaranteesthatthedopplegangerswillnotformblockingtripleswiththegarbagecollectors,defeatingourpurpose.Forexample,suppose(mi1,wia,dia)ispartofthe
gg
matching,wewanttoavoid(mi1,wi1,di1)tobecomingablockingtriple.Itcanbeggeasilyverifiedthatifwi1anddi1arematchedtomi2ormi3,suchablockingtriplewillnotbeformed.
Finally,garbagecollectorsalsousedummyplayerstopadtheirsimplelists,toavoidtheawkwardsituationthatsomedopplegangerismatchedtoarealwomanandagarbagecollectordog(orarealdogandagarbagecollectorwoman).Howthisarrange-mentworkswillbeclearintheproofbelow.
Lemma1.SupposeastablematchingM′existsinthederivedstablefamilyprobleminstanceΥ′.ThefollowingfactsholdinM′:
–FactA:Thethreesetsofdummyplayersarematchedtooneanother.
–FactB:Foreachdopplegangermij∈M1∪M2∪M3,theranksofhisfamilymembersinM′areatleastashighas3inhissimplelists.
–FactC:Thesixassociatedguardplayersofeachdopplegangermij∈M1∪M2∪M3arematchedtooneanother.
ggg
Table1.ThesimplelistsofallplayersinthesetX=M1∪M2∪M3∪W1∪W2∪W∪D1∪g
D2∪D.Weassumethatthereexistthreetriples(mi,wia,dia),(mi,wib,dib),(mi,wic,dic)inT.
Playermi1∈M1
g###♭2♭1
LD(mi1)=dgi2≻di1≻dia≻di1≻di1≻d1≻d2≻d3≻···
gg###♭1♭2
LW(mi2)=wi2≻wi1≻wib≻wi2≻wi2≻w1≻w2≻w3≻···
mi3∈M1
g###♭2♭1LD(mi3)=dgi2≻di1≻dic≻di3≻di3≻d1≻d2≻d3≻···
g
LM(wi1)=mi1≻mi2≻mi3≻···
g
dgi1∈D1
g###
LW(dgi1)=wi1≻w1≻w2≻w3≻···
g
LM(wi2)=mi1≻mi2≻mi3≻···
g
dgi2∈D2
g###
LW(dgi2)=wi2≻w1≻w2≻w3≻···LM(w)=···
d∈D
LW(d)=···
Proof.FactAfollowsdirectlyfromconstruction.FactBistrueaswehavearguedinthecaseanalysisbefore.FactCistruebecauseiftheguardplayersarenotmatchedto
♭1♭1♭2♭2
oneanother,theywillblockM′,unlesswij,dijorwij,dijarematchedtomijinM′,butthisisimpossiblebecauseofFactB.⊓⊔Lemma2.SupposeastablematchingM′existsinthederivedstablefamilyproblem
gggg
instanceΥ′.Considerthegarbagecollectorswi1,di1,wi2,di2createdformanmi∈ggggM.Wemusthavethatwi1,di1belongtothesametriplet1andthatwi2,di2belongtothesametriplet2inM′.Moreover,int1andt2,themanplayermustbeoneofthedopplegangersmi1,mi2andmi3.
Proof.Wewillprovethislemmabyprogressivelyestablishingthefollowingfacts.
gg′
FactD:wi2anddi2mustbelongtothesametriplet2inM.
gg′Proof:Foracontradiction,supposethatwi2anddi2areindifferenttriplesinM.gggWeclaimthat(mi1,wi2,di2)formsablockingtriple.Itisobviousthatmi1andwi2
gφφ
prefersuchatriple.Nowletthemanandwomanpartnersofdgi2bemandw=wi2;g
(mi1)+rdg(withenbyFactAinLemma1,rdg(w)≥5.Wehavethatrdg
2)=4 (wφ).Sodg6≤rdg(mφ)+rdg i2willalsoprefermi1andwi2,formingablockingi2i2 triplewiththemtoM′.Thisproofalsoshowswhyweneedtopadthepreferencesofthegarbagecollectors. gg′ FactE:wi1anddi1mustbelongtothesametriplet1inM. gφ1φ2φ2gProof:Foracontradiction,supposethat(mφ1,wi1,d)and(m,w,di1)aretriplesinM′.Thereexistsatleastonedopplegangerin{mi1,mi2,mi3}preferringthe ggg combinationofwi1anddi1(sinceatmostonedopplegangercanbematchedtowi2 ganddgi2).Letsuchadopplegangerbemij.ThenbyFactAinLemma1,rwi1(mij)+ ggg(d)≤4<6≤rg(mφ1)+rg(dφ2);andsimilarly,rg(m)+rg(w)≤rwiijddwwi1i11i1i1i1i1 ggφ2′φ2 (w),implyingthat(mij,wi1,di1)blocksM.(m)+rdg4<6≤rdg i1i1gg′ FactF:wi2anddi2mustbematchedtooneofthedopplegangersofmiinM,andggsoarewi1anddi1.gg Proof:Ifwi2anddi2arenotmatchedtoadopplegangerofmi,thenanydopple-gangermijwillpreferthecombinationofthemoverhisfamilymembers,causing gggg′ (mij,wi2,di2)toblockM.Asimilarargumentappliestothecaseofwi1anddi1,givingthelemma.⊓⊔ Bytheprevioustwolemmas,wehaveestablishedthecorrectnessofthereductionononeside. Lemma3.(Sufficiency)IfthereexistsastablematchingM′inthederivedstablefamilyprobleminstanceΥ′,thereexistsaperfectmatchingMintheoriginalthree-dimensionalmatchinginstanceΥ. Toshowthenecessity,weneedtoproveonemorelemma. Lemma4.InamatchingM′inthederivedstablefamilyprobleminstanceΥ′,sup-posethatdummyplayersarematchedtooneanother.Supposefurtherthatthegarbagecollectorsofmiarematchedtotwoofthedopplegangersofmi,whiletheremainingdopplegangermijismatchedtoarealwomanandarealdogwithwhommisharesatripleinTintheoriginalthree-dimensionalmatchinginstanceΥ.Thenthereisnoblockingtripleinwhichthedopplegangersmi1,mi2,andmi3areinvolved. gggg′ Proof.Weassumethat(mi1,wi2,di2),(mi2,wi1,di1),(mi3,wic,dic)∈M.Othercasesfollowanalogousarguments.Weclaimthattheredoesnotexistablockingtripleof ggφ1φ2φ3gφ4g theform(mij,wi1,d),(mij,wi2,d),(mij,w,di1),and(mij,w,di2)whereggφ2φ3φ4dφ1=dg=dg=wi=wii1,di2,w1,andw2.Weonlyarguethefirstcase.Since g###φ1φ1g(d)+rg(m).Therefore,g(d)≥5>3=rwid∈{d1,d2,d3},wehaverwii2wi1i111 gφ1wi1hasnoincentivetojointhecombinationofmijandd. Nowweonlyneedtoconsiderthethreeremainingpotentialblockingtriples: gggggg (mi2,wi2,di2),(mi3,wi2,di2),(mi3,wi1,di1).ItcanbeeasilyverifiedthattheydognotblockM′becausetheordersofthethreedopplegangersinthesimplelistsofwi1 ggg ⊓⊔anddi1(andalsowi2anddi2)arereversed. Lemma5.(Necessity)SupposethatthereisaperfectmatchingMintheoriginalthree-dimensionalmatchinginstanceΥ.TherealsoexistsastablematchingM′inthederived stablefamilyprobleminstanceΥ′. Proof.WebuildastablematchingM′inΥ′asfollows.Letthedummyplayers ## {m#j,wj,dj},1≤j≤3,bematchedtooneanother.Givenanydopplegangermij, 1♭1♭1♭2♭2♭2 lethisguardplayers{m♭ij,wij,dij},{mij,wij,dij}bematchedtooneanotheraswell.Furthermore,supposethat(mi,wix,dix)∈M.Letthedopplegangerwholistswixanddixabovehisguardplayersbematchedtowixanddix,whiletheothertwodopplegangersbematchedtothegarbagecollectors.Bythisconstruction,itcanbeseenthatnoneoftheguardplayersanddummyplayerswillbepartofablockingtriple.This,combinedwithLemma4,completestheproof.⊓⊔Supposethatinthegiventhree-dimensionalmatchinginstanceΥ,|M|=|W|=|D|=n.TheninthederivedinstanceΥ′,weuseinall3ndopplegangers,18nguardplayers,4ngarbagecollectors,2nrealwomenandrealdogs,and9dummyplayers.Theirpreferences(intheformofsimplelists)canbegeneratedinO(n2)time.There-fore,thisisapolynomial-timereduction.Also,givenanymatching,wedefinitelycancheckitsstabilityinO(n3)time.CombiningthetwofactswithLemma3andLemma5,wecanconclude: Theorem1.ItisNP-completetodecidewhetherstrongstablematchingsexistunderthePONscheme.Therefore,thequestionofdecidingexistenceofstrongstablematchingisalsoNP-completewhenthefullpreferencelistsareconsistent,i.e.,whentheyarerelaxedlinearextensionsofpreferenceposets. SuperStabilityandUltraStabilityItcanbeobservedthatthroughouttheproof,allargumentsinvolvingblockingtriplesusethoseofdegree3.Theonlyexceptionistheoccasionthatwearguethatadopplegangercannotbematchedtohisguardplayersin ♭1♭1 astablematching.Torecall,supposingthat(mij,wij,dij)ispartofamatching,then ♭2♭2 (mij,wij,dij)isablockingtripleofdegree2.(Orifthelatterispartofthematch-ing,theformerisablockingtripleofdegree2).Therefore,ourreductiononlyusesblockingtriplesofdegree2or3;botharestillblockingtripleswithregardtosuperstabilityandultrastability.Moreover,whenwearguethestrong-stabilityofmatchingsinthereduction,weneverallowblockingtriplesofdegree0ordegree1toexist.There-fore,essentially,ourreductionhasalsoestablishedtheNP-completenessofsuperstablematchingsandultrastablematchings. 4ThreesomeRoommateswithRelaxedLinearExtensionsofPreferencePosets Inthissection,weexhibitareductionofstablefamilytothreesomeroommates,therebyestablishingtheNP-completenessofstrong/super/ultrastablematchingsinthelatterproblem.InsteadofthePONscheme,weusethemoregeneralschemeinwhichanyrelaxedlinearextensionofpreferenceposetsisallowed.Wechoosetousethisschemebecausetheinvolvedreductiontechniquehasadifferentflavor.Nonetheless,wedohaveanotherreductionforthePONscheme.See[5]fordetails. LetaninstanceofstablefamilyproblembeΥ=(M,W,D,Ψ),whereΨrepresentsthepreferencesoftheplayersinM∪W∪D.Wecreateaninstanceofthreesome roommatesΥ′=(R′,Ψ′)bycopyingallplayersinM∪W∪DintoR′.RegardingthepreferencesinΨ′,wefirstbuildupthesimplelistsofallplayers.–Supposem∈M,L(m)=LW(m)≻LD(m)≻π(M−{m}).–Supposew∈W,L(w)=LD(w)≻LM(w)≻π(W−{w}).–Supposed∈D,L(d)=LM(d)≻LW(d)≻π(D−{d}). Inwords,amanlistsallwomenandthenalldogs,basedrespectivelyontheirorigi-nalorderinhissimplelistsinΨ.Hethenattachesotherfellowmeninarbitraryordertotheendofhislist.Womenanddogshaveanalogousarrangementsintheirsimplelists. Havingconstructedthesimplelists,westillneedtobuildconsistentrelaxedlinearextensions.Wewillexploitthefollowinglemma,whoseproofcanbefoundinthefullversion[5]. Lemma6.Letlbeastrictly-orderedlist.Supposekthatlisdecomposedintononemptycontiguoussublists(l1,l2,···,lk)suchthat(1)i=1li=l,(2)ife≻lif,thene≻lf,and(3)ife∈li,f∈lj,i –Considerm∈MandassumethatW=LW(m),D=LD(m),N=π(M−{m}).Hisrelaxedlinearextensionis:Eπ(W×W)≻X≻Eπ(W×N)≻Eπ(D×D)≻Eπ(D×N)≻Eπ(N×N),whereXistheoriginalrelaxedlinearextensionofmanm’spreferenceposetgiveninΨ. –Considerw∈WandassumethatD=LD(w),N=LM(w),W=π(W−{w}).Herrelaxedlinearextensionis:Eπ(D×D)≻Y≻Eπ(D×W)≻Eπ(N×N)≻Eπ(N×W)≻Eπ(W×W),whereYistheoriginalrelaxedlinearextensionofwomanw’spreferenceposetgiveninΨ. –Considerd∈DandassumethatN=LM(d),W=LW(d),D=π(D−{d}).Itsrelaxedlinearextensionis:Eπ(N×N)≻Z≻Eπ(N×D)≻Eπ(W×W)≻Eπ(W×D)≻Eπ(D×D),whereZistheoriginalrelaxedlinearextensionofdogd’spreferenceposetgiveninΨ. ToprovethatthereductionfromΥtoΥ′isvalid,wewillrelyheavilyonthefol-lowingtechnicallemma. Lemma7.InthederivedinstanceΥ′,ifastablematchingM′exists,everytripleinM′mustcontainaman,awoman,andadog.Moreover,supposethatinamatchingM′′inΥ′inwhicheachplayergetstwoothertypesofplayersasroommates,thenablockingtriplecannotcontaintwo(orthree)playersofthesametype.Proof.Forthefirstpart,wearguecasebycase. 1.If{m,wi,wj}∈M′,thereexistsanothermanm′whocangetneitherawoman-womancombinationnorawoman-dogcombination.Byconstruction,m′wouldpreferanywoman-dogcombinationtohisassignedroommatesinM′.Similarly,thereexistsadogd′whogetsanotherfellowdoginM′.Suchadogwouldpreferaman-womancombinationtoitsassignedroommatesinM′.Finally,womanwiandwjwouldpreferadog-mancombination.Therefore,both{m′,wi,d′}and{m′,wj,d′}blockM′,acontradiction. 2.If{m,mi,mj}∈M′,thenthereexistsawomanwwhogetsafellowwomaninM′andadogdwhogetsafellowdoginM′.Thus,womanwwouldpreferadog-mancombinationanddogdwouldpreferaman-womancombination.Therefore,{m,w,d},{mi,w,d},{mj,w,d}blockM′,acontradiction.3.Allothercasescanbearguedsimilarly. Forthesecondpart,supposethatmatchingM′′hasthestatedproperty.Givenanymanm,byourconstruction,ifthereisablockingtriplecontainingmandinwhichtherearetwoplayersofthesametype,theonlypossibilityofablockingtripleis{m,wi,wj}.However,neitherwinorwjwouldprefersuchatriple,becauseinourconstruction,forawoman,adog-mancombinationisbetterthanaman-womancombination.Theotherpotentialblockingtriplesnotinvolvingmenfollowanalogousarguments,thusgivingusthelemma.⊓⊔ ItisstraightforwardtouseLemma7toproveourreductionisavalidone.Theorem2.Decidingwhetherstrong/super/ultrastablematchingsexistinthethree-someroommatesproblemisNP-completewhenfullpreferencelistsareconsistent,i.e.,whentheyarerelaxedlinearextensionofpreferenceposets. 5WeakStabilityundertheSOCLScheme Duetospaceconstraint,wecanonlystateourresultsandleavethedetailstothefullversion[5]. Theorem3.ItisNP-completetodecidewhetherweakstablematchingsexistundertheSOCLscheme,forboththestablefamilyandthethreesomeroommatesproblems.Hence,itisalsoNP-completetodecidewhetheraweakstablematchingexistswhenconsistentpreferencesareallowedtocontainties:i.e.thefullpreferencesarerelaxedlinearextensionsofpreferenceposets. 6ConclusionandRelatedProblems Inthispaper,weanswertheopenquestionofwhetherthestablefamilyandthethree-someroommatesproblemsareNP-completeifallplayershavetoprovideconsistentpreferencelists.Weintroduceaschemeinwhichplayerscanexpressindifferenceonthepreconditionthattheirpreferenceshavetobeconsistent.Underthisscheme,avari-etyofstabilitiesaredefinedandweprovethatallleadtoNP-completeproblems. Sincewehaveprovedthatthegeneralcasesofstablefamilyandthreesomeroom-matesareNP-complete,anaturalquestiontoaskiswhethertherearespecialcasesthat allowpolynomialtimesolutions.Actually,examplesofthetwoproblemsthatcanbesolvedefficientlydoexist. Considerthefollowingscheme.Everyplayersubmitstwosimplelists.Amaneval-uatescombinationsfirstbythewomanhegets,thenbythedog;awomanfirstbythemanshegets,thenbythedog;adogfirstbythemanitgets,thenbythewoman.(Notetheasymmetry).ItisnothardtoseethatwecanapplytheGale-Shapleyalgorithmtwicetogetaweakstablematching:lettingthemenproposetowomenandthenproposetodogs.Womenanddogsmakethedecisionofacceptanceorrejectionbasedontheirsimplelistsofmen[2].Mergingthetwomatchingswillgiveastablematchinginthestablefamilyproblem. However,evenalittletwistcanmaketheaboveschemehardtosolve.Supposeamandecidesfirstbasedonthewomanhegetsandthenthedog;awomanfirstbasedonthedogshegetsandthenontheman;adogdecidesfirstbasedonthemanitgetsthenonthewoman.TheGale-Shapleyalgorithmnolongerworks[1]. Interestingly,theaboveschemeisreminiscentofanotheropenproblemallegedlyoriginatedbyKnuth.Supposethatamanhasonlyasimplelistforwomen;awomanhasonlyasimplelistfordogs;adoghasonlyasimplelistformen.Thisproblemiscalledcircularstablematching.Itscomplexityisstillunknown. Acknowledgements IthankmyadviserPeterWinklerformanyhelpfulsuggestions.Iamalsoindebtedtotheanonymousreviewersfortheirdetailedcomments. References 1.E.Boros,V.Gurvich,S.Jaslar,andD.Krasner.Stablematchingsinthree-sidedsystemswithcyclicpreferences.DiscreteMathematics,289(1-3):1–10,2004. 2.V.I.Danilov.Existenceofstablematchingsinsomethree-sidedsystems.MathematicalSocialScience,46(2):145–148,2003. 3.D.GaleandL.Shapley.Collegeadmissionsandthestabilityofmarriage.AmericanMathe-maticalMonthly,69(1):9–15,1962. 4.M.GareyandD.Johnson.ComputersandIntractablility.Freeman,1979. 5.C.-C.Huang.Two’scompany,three’sacrowd:Stablefamilyandthreesomeroommatesproblems.TechnicalReportTR2007-598,ComputerScienceDepartment,DartmouthCol-lege,2007. 6.R.Irving.Anefficientalgorithmforthestableroom-matesproblem.JournalofAlgorithms,6:577–595,1985. 7.R.Irving.Stablemarriageandindifference.DiscreteAppliedMathematics,48:261–272,1994. 8.R.Karp.Reducibilityamongcombinatorialproblems.InComplexityofComputerCompu-tations,pages85–103,1972. 9.D.Knuth.Mariagesstablesetleursrelationsavecd’autreprobl`emescombinatoires.LesPressesdel’universit´edeMontr´eal,1976. 10.C.NgandD.Hirschberg.Three-dimensionalstablematchingproblems.SIAMJournalon DiscreteMathematics,4(2):245–252,1991. 11.A.Subramanian.Anewapproachtostablematchingproblems.SIAMJournalonComputing, 23(4):671–700,1994. 因篇幅问题不能全部显示，请点此查看更多更全内容