EUVIMEDEUVIMED entdecken
Crossref

Allocation Problems in Ride-sharing Platforms

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

ACM Transactions on Economics and Computation · 30.09.2021 · 9 (3) · 1-17

DOI: 10.1145/3456756 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, online erschienen am 21.06.2021. Verfasst von John P. Dickerson und 3 weiteren Autor:innen. Die Arbeit wurde bisher 46-mal zitiert (Crossref) und nennt 59 Literaturangaben. Gefördert von: NSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • NSF

Zitieren

APA

Dickerson, J. P., Sankararaman, K. A., Srinivasan, A., & Xu, P. (2021). Allocation Problems in Ride-sharing Platforms. ACM Transactions on Economics and Computation, 9(3), 1-17. https://doi.org/10.1145/3456756

Vancouver

Dickerson JP, Sankararaman KA, Srinivasan A, Xu P. Allocation Problems in Ride-sharing Platforms. ACM Transactions on Economics and Computation. 2021;9(3):1-17. doi:10.1145/3456756

BibTeX
@article{Dickerson2021,
  author = {Dickerson, John P. and Sankararaman, Karthik A. and Srinivasan, Aravind and Xu, Pan},
  title = {Allocation Problems in Ride-sharing Platforms},
  journal = {ACM Transactions on Economics and Computation},
  year = {2021},
  volume = {9},
  number = {3},
  pages = {1--17},
  doi = {10.1145/3456756}
}
Kostenlos starten →