Allocation Problems in Ride-sharing Platforms: Online Matching with Offline Reusable Resources

John P. DIckerson, Karthik A. Sankararaman, Aravind Srinivasan, Pan Xu

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

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 article, 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 non-adaptive algorithm that achieves an online competitive ratio of ½- μ for any given constant μ > 0. We also show that no adaptive algorithm can achieve a ratio of ½ + 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.

Original languageEnglish (US)
Article number13
JournalACM Transactions on Economics and Computation
Volume9
Issue number3
DOIs
StatePublished - Sep 2021

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Statistics and Probability
  • Economics and Econometrics
  • Marketing
  • Computational Mathematics

Keywords

  • Online-matching
  • matching markets
  • randomized algorithms
  • rideshare

Fingerprint

Dive into the research topics of 'Allocation Problems in Ride-sharing Platforms: Online Matching with Offline Reusable Resources'. Together they form a unique fingerprint.

Cite this