TY - GEN
T1 - Online Resource Allocation with Matching Constraints
AU - Dickerson, John P.
AU - Sankararaman, Karthik Abinav
AU - Sarpatwar, Kanthi Kiran
AU - Srinivasan, Aravind
AU - Wu, Kun Lung
AU - Xu, Pan
N1 - Publisher Copyright:
© 2019 International Foundation for Autonomous Agents and Multiagent Systems. All rights reserved.
PY - 2019
Y1 - 2019
N2 - Matching markets with historical data are abundant in many applications, e.g., matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, arid jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually first-order moments) of the arriving agents (e.g., candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi-Budgeted Online Assignment with Known Adversarial Distributions. In this model, we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type arrives. Assigning this job to a server i yields a profit wij while consuming ae [0,1] quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LP-based approaches. We also propose several heuristics adapted from our algorithms and compare them to other LP-agnostic algorithms using both synthetic as well as real-time cloud scheduling and public safety datasets. Experimental results show that our proposed algorithms are effective and significantly out-perform the baselines. Moreover, we show empirically the trade-off between fairness and efficiency of our algorithms which does well even on fairness metrics without explicitly optimizing for it.
AB - Matching markets with historical data are abundant in many applications, e.g., matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, arid jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually first-order moments) of the arriving agents (e.g., candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi-Budgeted Online Assignment with Known Adversarial Distributions. In this model, we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type arrives. Assigning this job to a server i yields a profit wij while consuming ae [0,1] quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LP-based approaches. We also propose several heuristics adapted from our algorithms and compare them to other LP-agnostic algorithms using both synthetic as well as real-time cloud scheduling and public safety datasets. Experimental results show that our proposed algorithms are effective and significantly out-perform the baselines. Moreover, we show empirically the trade-off between fairness and efficiency of our algorithms which does well even on fairness metrics without explicitly optimizing for it.
KW - Fairness
KW - Online matching
KW - Online scheduling
KW - Randomized algorithms
UR - http://www.scopus.com/inward/record.url?scp=85076894743&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076894743&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85076894743
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 1681
EP - 1689
BT - 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019
Y2 - 13 May 2019 through 17 May 2019
ER -