孔芳- 匹配市场中的多臂赌博机算法.pdf

1、1Bandit Learning in Matching MarketsFang KongSouthern University of Science and TechnologyJoint work with Shuai LiMatching markets Talent cultivation(school admissions,student internships)Task allocation(crowdsourcing assignments,domestic services)Resource distribution(housing allocation,organ donat

2、ion allocation)2https:/;https:/ market has two sides%3!#$%Both sides have preferences over the other side4!#$Worker sideBased on payment or prior familiarity of the task:#!$:!#$:#!$:!#$:!#$!#$%Both sides have preferences over the other side5!#$:!#$%:!$#%:#!%$:$%!#Employer sideBased on the skill leve

3、ls of workersA case study:Medical interns Roth 1984 Hospital side Internship has relatively low cost Student side Closely engage with clinical medicine through internships Historical practice Medical schools first publish students grade ranking Then hospitals start signing internship agreements with

4、 students How to match?6Medical interns(cont.)Bad case Student!Receives offer from but knows he is on the waiting list of!Wishes to wait for!If!is forced to accept and then!sends an invitation?Hospital Rejected by!at the last moment Students on the waiting list have already accepted other offers Imp

5、ortant to guarantee stability!7!Participants have no incentive to abandon their current partner,i.e.,no blocking pair such that they both preferred to be matched with each other than their current partnerStable matchingAlvin E.Roth and Lloyd S.Shapley jointly won the Nobel Prize in 2012 for their co

6、ntributions to stable matching theory.!#!#!#!#!#!#8Blocking pair May be more than one stable matching!#!#9!=!,!,&,&=!,!,&,&!#!#!#!#!#!#!#!#!#!#!Each agent on A-side is matched with the most preferred partner among all stable matchings!=!,!,#,#A-side optimal stable matching1!#!#1The existence is prov