算法-稳定匹配StableMatching.ppt

《算法-稳定匹配StableMatching.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SaluteLloydShapleyLloydStowellShapley(June2,1923–March12,2016）11980NobelMemorialPrizeinEconomicSciences(2012)StableMatching3MatchingResidentstoHospitalsGoal.Givenasetofpreferencesamonghospitalsandmedicalschoolstudents,designaself-reinforcingadmissionsprocess.Unstablepair:applicantxandhos

2、pitalyareunstableif:xprefersytoitsassignedhospital.yprefersxtooneofitsadmittedstudents.Stableassignment.Assignmentwithnounstablepairs.Naturalanddesirablecondition.Individualself-interestwillpreventanyapplicant/hospitaldealfrombeingmade.4StableMatchingProblemGoal.Givennmenandnwomen,finda"

3、suitable"matching.Participantsratemembersofoppositesex.Eachmanlistswomeninorderofpreferencefrombesttoworst.Eachwomanlistsmeninorderofpreferencefrombesttoworst.ZeusAmyClareBerthaYanceyBerthaClareAmyXavierAmyClareBertha1st2nd3rdMen’sPreferenceProfilefavoriteleastfavoriteClareXavierZeusYanc

4、eyBerthaXavierZeusYanceyAmyYanceyZeusXavier1st2nd3rdWomen’sPreferenceProfilefavoriteleastfavorite5StableMatchingProblemPerfectmatching:everyoneismatchedmonogamously.Eachmangetsexactlyonewoman.Eachwomangetsexactlyoneman.Stability:noincentiveforsomepairofparticipantstoundermineassignmentby

5、jointaction.InmatchingM,anunmatchedpairm-wisunstableifmanmandwomanwprefereachothertocurrentpartners.Unstablepairm-wcouldeachimprovebyeloping.Stablematching:perfectmatchingwithnounstablepairs.Stablematchingproblem.Giventhepreferencelistsofnmenandnwomen,findastablematchingifoneexists.6Stab

6、leMatchingProblemQ.IsassignmentX-C,Y-B,Z-Astable?ZeusAmyClareBerthaYanceyBerthaClareAmyXavierAmyClareBertha1st2nd3rdMen’sPreferenceProfileClareXavierZeusYanceyBerthaXavierZeusYanceyAmyYanceyZeusXavier1st2nd3rdWomen’sPreferenceProfilefavoriteleastfavoritefavoriteleastfavorite7StableMatchi

7、ngProblemQ.IsassignmentX-C,Y-B,Z-Astable?A.No.BerthaandXavierwillhookup.ZeusAmyClareBerthaYanceyBerthaClareAmyXavierAmyClareBerthaClareXavierZeusYanceyBerthaXavierZeusYanceyAmyYanceyZeusXavier1st2nd3rd1st2nd3rdfavoriteleastfavoritefavoriteleastfavoriteMen’sPreferenceProfi