Adaptive Dynamic Bipartite Graph Matching A Reinforcement Learning Approach Yansheng Wang 1, Yongxin Tong1, Cheng Long2, Pan Xu3, Ke Xu1, Weifeng Lv 1 1 Beihang University 2 Nanyang Technological University 3 University of Maryland, College Park ERSIT 南洋埋工大學 4 NANYANO 9 TECHNOLOGICA UNIVERSIT RYLA
Adaptive Dynamic Bipartite Graph Matching: A Reinforcement Learning Approach Yansheng Wang 1 , Yongxin Tong 1 , Cheng Long 2 , Pan Xu 3 , Ke Xu 1 , Weifeng Lv 1 1 Beihang University 2 Nanyang Technological University 3 University of Maryland, College Park
Outline e background and motivation ● Problem statement ° Our so| utions ● EXperiments Conclusion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusion 2
Outline o Background and Motivation ● Problem statement ° Our so| utions ● EXperiments Conclusion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusion 3
Background Bipartite graph matching 3 Solved by the Hungarian method 4 in polynomial time 6 Harold w, Kuhn Traditional applications Assignment problem, vehicle scheduling problem, etc. Perform well in offline scenarios
⚫ Bipartite graph matching ⚫ Traditional applications ⚫ Assignment problem, vehicle scheduling problem, etc. ⚫ Perform well in offline scenarios Background 4 3 1 2 4 5 6 2 3 4 1 2 Solved by the Hungarian method in polynomial time Harold W. Kuhn
Background Emergence of online scenarios Transportation Medical Economic Taxi-hailing, Mutual blood donation, Two-sided market, Ride sharing, Kidney exchange,… Crowdsourcing, 回 UNOS amazon THOO!! UBER ANSWERS UNITED NETWORK FOR ORGAN SHARING mechanical turk Online matching is more and more important
⚫ Emergence of online scenarios Background 5 Transportation Medical Economic Taxi-hailing, Ride sharing, … Mutual blood donation, Kidney exchange, … Two-sided market, Crowdsourcing, … Online matching is more and more important
Existing Research Problem model: online bipartite matching Objective: Nodes arrive and maximize the leave dynamically sum of weights 3 Match as soon as the node arrives 4 (instantaneous constraint) 5 Solution: online algorithms under instantaneous constraint Y. Tong et al, On line mobile microtask allocation in spatial crowdsourcing In ICDE 2016
⚫ Problem model: online bipartite matching ⚫ Solution: online algorithms under instantaneous constraint Existing Research 6 3 1 2 4 5 6 Nodes arrive and leave dynamically 2 3 4 1 2 Objective: maximize the sum of weights Match as soon as the node arrives (instantaneous constraint) Y. Tong et al, Online mobile microtask allocation in spatial crowdsourcing. In ICDE 2016
Motivation Instantaneous constraint is too strong sometimes Waiting for response Accuracy: 70%)( Accuracy: 95% 加点小费②000 Passengers can wait for a short time drivers nearby have before being served received your order 17:00 17:30 Requseters are willing 02:54 to wait for more I have a task of labeling 500 reliable workers pictures If nodes can wait(match in a batch manner) More information can be gathered Likely to meet better candidates in the future I LKazemiet al, Geocrowd: enablingquery answering with spatial crowdsourcing In GIS 2012
⚫ Instantaneous constraint is too strong sometimes ⚫ If nodes can wait (match in a batch manner) ⚫ More information can be gathered ⚫ Likely to meet better candidates in the future Motivation 7 Waiting for response 2 drivers nearby have received your order Passengers can wait for a short time before being served Requseters are willing to wait for more reliable workers 17:00 17:30 I have a task of labeling 500 pictures Accuracy:70% Accuracy:95% L. Kazemi et al. Geocrowd: enabling query answering with spatial crowdsourcing. In GIS 2012
Limitation of existing work 8 Strong assumptions: instantaneous constraint Batch manner: fixed batch and lacking in global theoretical guarantee Y Tong et al, Online mobile microtask allocation in spatial crowdsourcing In ICDE 2016 Y. Tong et al, Flexible dynamic task assignment in real-time spatial data In VLDB 2017. P Cheng et al, An experimentalevaluation of task assignment in spatial crowdsourcing. In VLDB 2018 L. Kazemiet al Geocrowd: enabling query answering with spatial crowdsourcing In GIS 2012 L. Kazemiet al Geo TruCrowd: trustworthy query answering with spatial crowdsourcing In GIS 2013
Limitation of existing work 8 ⚫ Strong assumptions: instantaneous constraint ⚫ Batch manner: fixed batch and lacking in global theoretical guarantee Y. Tong et al, Online mobile microtask allocation in spatial crowdsourcing. In ICDE 2016. Y. Tong et al, Flexible dynamic task assignment in real-time spatial data. In VLDB 2017. L. Kazemi et al. Geocrowd: enabling query answering with spatial crowdsourcing. In GIS 2012. L. Kazemi et al. GeoTruCrowd: trustworthy query answering with spatial crowdsourcing. In GIS 2013. P. Cheng et al, An experimental evaluation of task assignment in spatial crowdsourcing. In VLDB 2018
Contribution Devise a novel adaptive batch-based framework Analyze the global theoretical guarantee Propose an effective and efficient reinforcement learning based solution
Contribution 9 ⚫ Devise a novel adaptive batch-based framework ⚫ Analyze the global theoretical guarantee ⚫ Propose an effective and efficient reinforcement learning based solution
Outline e background and motivation ● Problem statement ° Our so| utions ● EXperiments Conclusion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusion 10