算法-稳定匹配StableMatchingppt课件

1,SaluteLloydShapley,LloydStowellShapley(June2,1923March12,2016）,1980,NobelMemorialPrizeinEconomicSciences(2012),StableMatching,3,MatchingResidentstoHospitals,Goal.Givenasetofpreferencesamonghospitalsandmedicalschoolstudents,designaself-reinforcingadmissionsprocess.Unstablepair:applicantxandhospitalyareunstableif:xprefersytoitsassignedhospital.yprefersxtooneofitsadmittedstudents.Stableassignment.Assignmentwithnounstablepairs.Naturalanddesirablecondition.Individualself-interestwillpreventanyapplicant/hospitaldealfrombeingmade.,4,StableMatchingProblem,Goal.Givennmenandnwomen,findasuitablematching.Participantsratemembersofoppositesex.Eachmanlistswomeninorderofpreferencefrombesttoworst.Eachwomanlistsmeninorderofpreferencefrombesttoworst.,Zeus,Amy,Clare,Bertha,Yancey,Bertha,Clare,Amy,Xavier,Amy,Clare,Bertha,1st,2nd,3rd,MensPreferenceProfile,favorite,leastfavorite,Clare,Xavier,Zeus,Yancey,Bertha,Xavier,Zeus,Yancey,Amy,Yancey,Zeus,Xavier,1st,2nd,3rd,WomensPreferenceProfile,favorite,leastfavorite,5,StableMatchingProblem,Perfectmatching:everyoneismatchedmonogamously.Eachmangetsexactlyonewoman.Eachwomangetsexactlyoneman.Stability:noincentiveforsomepairofparticipantstoundermineassignmentbyjointaction.InmatchingM,anunmatchedpairm-wisunstableifmanmandwomanwprefereachothertocurrentpartners.Unstablepairm-wcouldeachimprovebyeloping.Stablematching:perfectmatchingwithnounstablepairs.Stablematchingproblem.Giventhepreferencelistsofnmenandnwomen,findastablematchingifoneexists.,6,StableMatchingProblem,Q.IsassignmentX-C,Y-B,Z-Astable?,Zeus,Amy,Clare,Bertha,Yancey,Bertha,Clare,Amy,Xavier,Amy,Clare,Bertha,1st,2nd,3rd,MensPreferenceProfile,Clare,Xavier,Zeus,Yancey,Bertha,Xavier,Zeus,Yancey,Amy,Yancey,Zeus,Xavier,1st,2nd,3rd,WomensPreferenceProfile,favorite,leastfavorite,favorite,leastfavorite,7,StableMatchingProblem,Q.IsassignmentX-C,Y-B,Z-Astable?A.No.BerthaandXavierwillhookup.,Zeus,Amy,Clare,Bertha,Yancey,Bertha,Clare,Amy,Xavier,Amy,Clare,Bertha,Clare,Xavier,Zeus,Yancey,Bertha,Xavier,Zeus,Yancey,Amy,Yancey,Zeus,Xavier,1st,2nd,3rd,1st,2nd,3rd,favorite,leastfavorite,favorite,leastfavorite,MensPreferenceProfile,WomensPreferenceProfile,8,StableMatchingProblem,Q.IsassignmentX-A,Y-B,Z-Cstable?A.Yes.,Zeus,Amy,Clare,Bertha,Yancey,Bertha,Clare,Amy,Xavier,Amy,Clare,Bertha,Clare,Xavier,Zeus,Yancey,Bertha,Xavier,Zeus,Yancey,Amy,Yancey,Zeus,Xavier,1st,2nd,3rd,1st,2nd,3rd,favorite,leastfavorite,favorite,leastfavorite,MensPreferenceProfile,WomensPreferenceProfile,9,StableRoommateProblem,Q.Dostablematchingsalwaysexist?A.Notobvious.Stableroommateproblem.2npeople;eachpersonranksothersfrom1to2n-1.Assignroommatepairssothatnounstablepairs.Observation.Stablematchingsdonotalwaysexistforstableroommateproblem.,B,Bob,Chris,Adam,C,A,B,D,D,Doofus,A,B,C,D,C,A,1st,2nd,3rd,A-B,C-DB-CunstableA-C,B-DA-BunstableA-D,B-CA-Cunstable,10,Propose-and-rejectalgorithm.Gale-Shapley1962Intuitivemethodthatguaranteestofindastablematching.,Propose-And-RejectAlgorithm,Initializeeachpersontobefree.while(somemanisfreeandhasntproposedtoeverywoman)Choosesuchamanmw=1stwomanonmslisttowhommhasnotyetproposedif(wisfree)assignmandwtobeengagedelseif(wprefersmtoherfiancm)assignmandwtobeengaged,andmtobefreeelsewrejectsm,11,ProofofCorrectness:Termination,Observation1.Menproposetowomenindecreasingorderofpreference.Observation2.Onceawomanismatched,sheneverbecomesunmatched;sheonlytradesup.Claim.Algorithmterminatesafteratmostn2iterationsofwhileloop.Pf.Eachtimethroughthewhileloopamanproposestoanewwoman.Thereareonlyn2possibleproposals.,n(n-1)+1proposalsrequired,12,ProofofCorrectness:Perfection,Claim.Allmenandwomengetmatched.Pf.(bycontradiction)Suppose,forsakeofcontradiction,thatZeusisnotmatcheduponterminationofalgorithm.Thensomewoman,sayAmy,isnotmatchedupontermination.ByObservation2,Amywasneverproposedto.But,Zeusproposestoeveryone,sinceheendsupunmatched.,13,Claim.Nounstablepairs.Pf.(bycontradiction)SupposeA-Zisanunstablepair:eachpreferseachothertopartnerinGale-ShapleymatchingS*.Case1:ZneverproposedtoA.ZprefershisGSpartnertoA.A-Zisstable.Case2:ZproposedtoA.ArejectedZ(rightawayorlater)AprefersherGSpartnertoZ.A-Zisstable.IneithercaseA-Zisstable,acontradiction.,ProofofCorrectness:Stability,Bertha-Zeus,Amy-Yancey,S*,.,menproposeindecreasingorderofpreference,womenonlytradeup,14,Summary,Stablematchingproblem.Givennmenandnwomen,andtheirpreferences,findastablematchingifoneexists.Gale-Shapleyalgorithm.Guaranteestofindastablematchingforanyprobleminstance.Q.HowtoimplementGSalgorithmefficiently?Q.Iftherearemultiplestablematchings,whichonedoesGSfind?,15,EfficientImplementation,Efficientimplementation.WedescribeO(n2)timeimplementation.Representingmenandwomen.Assumemenarenamed1,n.Assumewomenarenamed1,n.Engagements.Maintainalistoffreemen,e.g.,inaqueue.Maintaintwoarrayswifem,andhusbandw.setentryto0ifunmatchedifmmatchedtowthenwifem=wandhusbandw=mMenproposing.Foreachman,maintainalistofwomen,orderedbypreference.Maintainanarraycountmthatcountsthenumberofproposalsmadebymanm.,16,EfficientImplementation,Womenrejecting/accepting.Doeswomanwprefermanmtomanm?Foreachwoman,createinverseofpreferencelistofmen.ConstanttimeaccessforeachqueryafterO(n)preprocessing.,fori=1toninverseprefi=i,Amyprefersman3to6sinceinverse3inverse6,2,7,17,UnderstandingtheSolution,Q.Foragivenprobleminstance,theremaybeseveralstablematchings.DoallexecutionsofGale-Shapleyyieldthesamestablematching?Ifso,whichone?Aninstancewithtwostablematchings.A-X,B-Y,C-Z.A-Y,B-X,C-Z.,Zeus,Yancey,Xavier,A,B,A,1st,B,A,B,2nd,C,C,C,3rd,Clare,Bertha,Amy,X,X,Y,1st,Y,Y,X,2nd,Z,Z,Z,3rd,18,UnderstandingtheSolution,Q.Foragivenprobleminstance,theremaybeseveralstablematchings.DoallexecutionsofGale-Shapleyyieldthesamestablematching?Ifso,whichone?Def.Manmisavalidpartnerofwomanwifthereexistssomestablematchinginwhichtheyarematched.Man-optimalassignment.Eachmanreceivesbestvalidpartner.Claim.Allexecutions