ride-sharing platform operators

Abstract: Traffic management has traditionally focused on toll-based and road pricing solutions. However, road pricing often raises concerns about accessibility and public dissatisfaction, leading to its prohibition in some places, such as Finland. This study optimises the dynamic allocation of incentives to drivers, encouraging them to reroute onto alternative (potentially longer) paths to achieve greater societal benefit, reduced total travel time (TTT) and total emissions in the transportation network, contributing to sustainable urban mobility. We employ a multi-agent reinforcement learning approach to dynamically assign incentives to drivers to reduce both TTT and emissions, with travel times estimated using traffic simulation software. We demonstrate that, with an unlimited budget and an objective of minimising travel time, the incentive scheme reduces TTT by 16%, compared to the dynamic User-Equilibrium (UE) with a budget equivalent to about 11% of the UE total time. When the goal is to minimise emissions, a 9% reduction in CO2 emissions is observed under an unlimited budget. We demonstrate a critical trade-off: minimising TTT leads to an increase in emissions, while prioritising emission reductions raises TTT. However, with the right combination of weights in the multi-objective function, both TTT and total emissions are improved beyond the baseline.

Abstract: In this work we initiate the study of competitive algorithms with arrival-time incentive compatibility for random-order online bipartite matching in settings where the users care only about receiving service (matched vs. unmatched) and not which offline resource serves them, while the platform's objective is to maximize total matching reward. This captures applications such as ride-sharing where the users primarily care about being matched to a ride while the platform internalizes the cost of dispatching a distant driver; dispatching homogeneous service requests to heterogeneous servers (cloud/edge routing); and assigning customer requests to a pool of providers with different flexibility (e.g., English-only vs. bilingual agents). Our main question is: \textit{Is constant-competitive matching possible for incentive-compatible, random-order edge-weighted matching on complete bipartite graphs?} Motivated by the LP-based treatment of incentive compatibility in the classical secretary problem by Buchbinder et al., we impose a constraint that the ex ante probability of selection is equalized across all arrival positions. We answer our main question in the affirmative and propose the first constant-competitive algorithm for incentive compatible edge-weighted random-order online matching on complete bipartite graphs. The competitive ratio of our algorithm is parameterized by the imbalance factor $k := n/m$ -- where $n$ and $m$ are the numbers of online and offline nodes, respectively, and $k$ is a positive integer. In particular, we obtain a competitive guarantee of the form $c_k - O(1/\sqrt{m})$ where $c_1 \approx 0.162$ and $c_k \to 0.02308\ldots$ as $k \to \infty$. We also present algorithms with strictly improved competitive ratio of $\approx 0.07 + O(1/m)$ for the binary-weighted case ($0$-$1$ rewards).

Abstract: On-demand delivery platforms pay riders through incentive activities whose tiers are set from recent completions of riders with a similar history. Operators request such plans for changing periods, rider populations, payment rules and budgets, often for holidays or bad weather, where randomized trials are scarce and take months to collect. We present a request-driven framework that composes four stages (conditional prediction, population reduction, trajectory integration and budget allocation) through seven replaceable modules that exchange conditional trajectory laws, whose award probabilities and award-marked moments give payment and uplift for any activity rule. A response-correction step reweights trajectories from abundant no-offer history to match the moments of a short pilot. We prove that, on a fixed plan menu and given the stage errors, the end-to-end value loss is bounded by the sum of four stage terms, and that for every stage there are instances on which omitting it leaves an error floor the others cannot remove. On 3,000 riders over 45 weekly origins, all 127 windows of a week are answered 11.04x faster with identical scenarios and at most 0.92% value lost by the allocation. On 24 new controlled response laws, the response correction with a one-week pilot lowers regret by 51.2% relative to a trial with the same nominal randomized rider-weeks, and a four-week pilot with exact summation comes within +0.007 of an 18-week trial. In registered studies where windows, populations, rules and binding budgets change from request to request, the framework's regret is below that of a trial with the same nominal rider-weeks and below dose interpolation of the same pilot data, and reusing its one-off preparation answers 60 requests 14.1x and 2.70x faster with identical answers. Against a nine-offer trial fitted with the framework's own dose curve, one-week regret is 0.055 lower.