欢迎来到天天文库
浏览记录
ID:61784673
大小:340.00 KB
页数:22页
时间:2021-03-20
《算法-稳定匹配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
此文档下载收益归作者所有