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

arXiv: https://arxiv.org/abs/1711.08345 · HTML: https://mlsanity.com/paper/1711.08345/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2017.

## Built on by (most cited first, 14 of 14)

- [Dynamic fairness-aware recommendation through multi-agent social choice](https://mlsanity.com/paper/2303.00968/) (2023)
- [Learning-Augmented Online Bipartite Fractional Matching](https://mlsanity.com/paper/2505.19252/) (2025)
- [Matching Algorithms for Blood Donation](https://mlsanity.com/paper/2108.04862/) (2021)
- [Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual](https://mlsanity.com/paper/2201.06021/) (2022)
- [Near-Optimal Reviewer Splitting in Two-Phase Paper Reviewing and Conference Experiment Design](https://mlsanity.com/paper/2108.06371/) (2021)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [Combinatorial Blocking Bandits with Stochastic Delays](https://mlsanity.com/paper/2105.10625/) (2021)
- [A Survey of Machine Learning-Based Ride-Hailing Planning](https://mlsanity.com/paper/2303.14646/) (2023)
- [Online Task Assignment Problems with Reusable Resources](https://mlsanity.com/paper/2203.07605/) (2022)
- [Fully Dynamic Online Selection through Online Contention Resolution Schemes](https://mlsanity.com/paper/2301.03099/) (2023)
- [Design a Win-Win Strategy That Is Fair to Both Service Providers and Tasks When Rejection Is Not an Option](https://mlsanity.com/paper/2407.00032/) (2024)
- [SMaRT: Online Reusable Resource Assignment and an Application to Mediation in the Kenyan Judiciary](https://mlsanity.com/paper/2602.18431/) (2026)
- [JointMatch: A Unified Heterogeneous Graph Neural Solver for Large-Scale Ride-Sharing Matching](https://mlsanity.com/paper/2609.20200/) (2026)
- [Lag: A Mean-Field Optimal Policy for Online Assignment with Reusable Resources](https://mlsanity.com/paper/2610.19038/) (2026)

## Abstract (arXiv)

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 - eps for any given eps greater than 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.