Source-linked AI summary
Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources
John P Dickerson, Karthik A Sankararaman, Aravind Srinivasan, Pan Xu
TL;DR
The paper addresses online matching where service providers are reusable after serving users, unlike disposable-resource models, and where user arrivals vary over time. It introduces OM-RR-KAD and an LP-based online approach, with experiments reporting that LP-based algorithms outperform simpler baselines.
Problem
Online matching often assumes disposable resources, although service providers in many settings are reusable and user arrival distributions can change over time.
Source: §1 · p. 1Method
The paper introduces OM-RR-KAD, modeling reusable resources with occupation times, and presents an LP-based online algorithm.
Source: §1 · p. 2, §1.1 · p. 2Results
LP-based algorithms outperform uniform free-neighbor choice, and with distributional assumptions they also outperform greedy; their ratios against the LP optimum are 0.5 to 0.7.
Source: §5.3 · p. 7Takeaways & Limitations
The model captures ride-sharing assignment and reusable resources in settings where agents enter and leave the system multiple times.
Source: §6 · p. 7The experiments assume every car starts and ends trips at the same location and that occupation-time distributions are identically and independently distributed across matches.
Source: §5 · p. 5
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction motivates online matching with reusable resources and changing arrival distributions through applications including ride-sharing and organ allocation. It proposes OM-RR-KAD, gives theoretical guarantees, and reports data-driven and heuristic results.
1 Introduction
- The introduction frames reusable providers and time-varying user arrivals as features of resource-allocation and scheduling settings, including ride-sharing and organ allocation.In the organ-allocation example, patients reappear after donor organs last up to 15 years, while donors arrive over time.Source: §1 · pp. 1–2
- OM-RR-KAD models offline resources that return after a known-distribution occupation time, while online arrival distributions may vary across rounds.The paper identifies taxi dispatch and ride-sharing as settings where occupation time can depend on rider type and time.Source: §1 · pp. 1–2
1.1 Our Contributions
- An LP-guided online algorithm achieves a competitive ratio of 1/2 − ε for any ε > 0 under benchmark LP (1).The LP upper-bounds the expected offline optimum.Source: §1.1 · p. 2
- No non-adaptive algorithm based on benchmark LP (1) can achieve a competitive ratio better than 1/2 + o(1), even when occupation times are constant.Source: §1.1 · p. 2
- A data-driven analysis on an openly available dataset supports the model's applicability to taxi hailing and sharing, and the paper also reports useful heuristics.The authors suggest combining theoretically grounded algorithms with heuristics to improve ratios in practice.Source: §1.1 · p. 2
1.2 Other Related Work
- The related-work discussion recasts the model as stochastic online scheduling, where its objective is expected completed-job profit rather than minimizing total or maximum completion time.Source: §1.2 · p. 3
2 Main Model
The model assigns arriving online vertices immediately to neighboring offline resources, which become unavailable for a random, known-distribution occupation time and later return. Its benchmark LP upper-bounds the offline optimum.
2 Main Model
- Each arriving vertex is immediately and irrevocably rejected or assigned to one neighboring offline resource; the goal is to maximize expected total assignment weight.The model assumes |V| ≫ |U| and T ≫ 1.Source: §2 · p. 3
- After assignment e = (u, v), resource u is unavailable for C_e rounds and then rejoins; C_e is an integer-valued random variable with known distribution.The occupation time can range from 0 to T.Source: §2 · p. 3
- LP (1) upper-bounds the expected offline optimum by limiting assignments to an arriving vertex by its arrival probability and resource use by its availability.The resource-availability constraint accounts for earlier assignments that still occupy the resource and assignments made in the current round.Source: §2 · p. 3
3 Simulation-based Algorithm
ADAP estimates how likely an assignment is to be safe, then attenuates its sampling probability to match the LP-guided target. The method extends to time-sensitive occupation times while retaining a 1/2 − ε competitive ratio against a modified valid benchmark.
3 Simulation-based Algorithm
- ADAP simulates its strategy up to arrival time t to estimate the probability β_e,t that assignment e is safe, then samples safe assignments at an attenuated rate.When e is safe, the sampling probability is chosen using γ and β_e,t so that e is sampled unconditionally with probability γx*_e,t.Source: §3 · p. 3
- An algorithm is valid when γ ≤ β_e,t, ensuring that its safe-assignment sampling can realize the target probability.For the analysis, the authors assume exact β_e,t values; sampling error can be folded into a (1 − ε) factor in the competitive ratio using Chernoff bounds.Source: §3 · p. 3
- The authors state that Theorem 1 follows directly from Lemmas 1 and 2.The supplied passages identify the theorem’s derivation but do not state its full guarantee.Source: §3 · p. 3
Extension from Ce to Ce,t
- For time-sensitive occupation times, the modified LP remains a valid benchmark and ADAP achieves a competitive ratio of 1/2 − ε for any ε > 0.The extension replaces constraint (3) with constraint (5); the remaining algorithm is unchanged.Source: §3 · p. 4
4 Hardness Result
The hardness analysis studies a uniform, unit-weight complete bipartite instance with reusable resources and bounds the optimal value of a program capturing non-adaptive performance. Its bound approaches one half when K grows while remaining o(n).
4 Hardness Result
- The instance has K resources, n² online vertices, n rounds, uniform arrival probability 1/n², occupation time K, and unit edge weights.Each resource is unavailable for K rounds after an assignment, and the benchmark LP reduces to program (10).Source: §4 · p. 4
- The benchmark LP has an optimal solution x*_e,t = 1/(n²K) for every edge and time, with objective value n.The non-adaptive algorithm is parameterized by a fixed allocation probability α_u,v for each resource–vertex pair.Source: §4 · p. 4
- For a given resource u, NADAP’s expected matches are expressed as the sum of β_uγ_u,t over rounds, where γ_u,t is its probability of being available.The availability probabilities obey recursive inequalities with γ_u,1 = 1.Source: §4 · p. 4
- When K = o(n), the optimal value of program (10) is at most 1/(2 − 1/K + o(1)).The stated bound implies an asymptotic ceiling approaching one half as K grows while remaining o(n).Source: §4 · p. 5
- The authors note that the known-distribution disposable-resource hardness of 0.823 also applies because their reusable-resource setting generalizes that problem.This is a separate unconditional hardness observation from the program-based bound.Source: §4 · p. 5
5 Experiments
On NYC taxi data, the experiments compare LP-based algorithms and heuristics across arrival and occupation-time assumptions. The LP-based approaches outperform uniform choice, and their performance is robust to the tested occupation-time distributions.
5 Experiments
- The experiments use 2013 NYC yellow-cab trip records and assume cars return to fixed docking locations with identically distributed occupation times, testing normal and power-law distributions.Distribution parameters and docking positions are learned from training data.Source: §5 · p. 5, §5.1 · p. 5
5.2 Justifying The Two Important Model Assumptions
- Request arrivals rise markedly in the middle of the day, supporting time-varying KAD arrival distributions over identical distributions across time.The paper reports that the LP and corresponding algorithm can exploit these arrival-rate differences; Figures 1 and 2 are cited as experimental confirmation.Source: §5.2 · pp. 5–6
- Most recorded occupation times are around 2–3 time steps, with a long tail; two randomly selected cars have roughly coinciding distributions.The authors suggest these distributions can be learned from historical data and used to guide future matches.Source: §5.2 · p. 6, Figure 5 · p. 6, Figure 6 · p. 6
5.3 Results
- ALG-LP and ALG-SC-LP achieve competitive ratios of 0.5–0.7 against the benchmark LP, outperform uniform choice, and, with distributional assumptions, outperform greedy.The authors attribute the ratios partly to high arrival rates occurring in only a few time steps; they report negligible performance differences between normal and power-law occupation-time assumptions.Source: Figure 2 · p. 6, Figure 3 · p. 6, §5.3 · p. 7
6 Conclusion and Future Directions
The conclusion presents reusable offline resources as a way to model ride-sharing assignment and other settings where agents repeatedly enter and leave a system. It identifies batch arrivals, Markovian driver starting positions, and integration with applied optimization or reinforcement learning as future directions.
6 Conclusion and Future Directions
- The model captures ride-sharing assignment through reusable offline resources and points to batch arrivals, Markovian driver starting positions, and applied stochastic optimization or reinforcement learning as future directions.The paper names crowdsourcing markets and organ allocation as other settings involving reusable resources.Source: §6 · p. 7
7 Supplementary Materials
The supplementary proofs establish intermediate bounds used in the analysis, including a bound on the objective of program (10) under K=o(n).
7.1 Proof of Lemma 2
- The Lemma 2 proof proceeds inductively, assuming earlier safe-assignment probabilities are at least 1/2 and the adaptive algorithm is valid, then invokes benchmark-LP constraints.The supplied proof passages show the induction setup and its use of LP constraints, but not the complete derivation.Source: §7.1 · p. 9
7.2 Proof of Lemma 3
- The Lemma 3 proof uses disjoint safe and matched events across each time window to support its probability bound.The supplied passage states the disjointness property for a resource that is safe at time t or matched in the preceding window.Source: §7.2 · p. 9
7.3 Proof of Lemma 4
- Under K=o(n), the Lemma 4 analysis bounds the maximization value by 1/(2−1/K)+o(1), attained when all β_u equal 1/K.The proof upper-bounds H_u and the objective of program (10), then uses concavity under the constraint that the β_u sum to one.Source: §7.3 · p. 9