TY - GEN
T1 - Allocation problems in ride-sharing platforms
T2 - 32nd AAAI Conference on Artificial Intelligence, AAAI 2018
AU - Dickerson, John P.
AU - Srinivasan, Aravind
AU - Sankararaman, Karthik A.
AU - Xu, Pan
N1 - Publisher Copyright:
Copyright © 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2018
Y1 - 2018
N2 - Bipartite matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this paper, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions (OM-RR-KAD), in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LP-based adaptive algorithm that achieves an online competitive ratio of 1 2 − for any given > 0. We also show that no non-adaptive algorithm can achieve a ratio of 1 2 + o(1) based on the same benchmark LP. Through a data-driven analysis on a massive openly-available dataset, we show our model is robust enough to capture the application of taxi dispatching services and ride-sharing systems. We also present heuristics that perform well in practice.
AB - Bipartite matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this paper, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions (OM-RR-KAD), in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LP-based adaptive algorithm that achieves an online competitive ratio of 1 2 − for any given > 0. We also show that no non-adaptive algorithm can achieve a ratio of 1 2 + o(1) based on the same benchmark LP. Through a data-driven analysis on a massive openly-available dataset, we show our model is robust enough to capture the application of taxi dispatching services and ride-sharing systems. We also present heuristics that perform well in practice.
UR - http://www.scopus.com/inward/record.url?scp=85047068578&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85047068578&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85047068578
T3 - 32nd AAAI Conference on Artificial Intelligence, AAAI 2018
SP - 1007
EP - 1014
BT - 32nd AAAI Conference on Artificial Intelligence, AAAI 2018
PB - AAAI press
Y2 - 2 February 2018 through 7 February 2018
ER -