On-Trip Matching and Pricing for Shared Rides

arXiv:2604.17552 · math.OC · Submitted 2026-04-19 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: I'm Ada.

Emmy: And I'm Emmy, here with Kolya.

Ada: We're looking at the paper: "On-Trip Matching and Pricing for Shared Rides".

Emmy: Here's the gist of the paper. Shared rides have seen limited success outside of dense urban areas—the sparse outskirts of greater metropolitan areas remain underserved <ref:2604.17552#pg2> The authors developed a dynamic, stochastic matching model that incorporates both pre-trip and on-trip matching decisions, finding that on-trip matching is critical in sparser outskirts where demand is spatially dispersed <ref:2604.17552#pg4> They also found that the addition of on-trip matching increases profitability and efficiency for the platform and lowers prices for riders, particularly in sparse outskirts <ref:2604.17552#pg4>.

Ada: Modeling Framework The paper introduces a dynamic, stochastic matching model where the platform makes both pre-trip and on-trip matching decisions The model is formulated as an average-reward, discrete-time Markov Decision Process (MDP) <ref:2604.17552#pg10>.

Emmy: The state of the system at time t is denoted by st = (st,i,u)(i,u) ∈ C ∈ S <ref:2604.17552#pg10>.

Ada: The platform implements a static pricing policy and a state-dependent matching policy.

Title and authors: Ada: So this paper is titled "On-Trip Matching and Pricing for Shared Rides", which sounds pretty technical, but it's really about how you match riders dynamically while also setting prices.

Emmy: It focuses on the idea that shared rides aren't working well outside of big cities right now.

Ada: Exactly. The authors point out that the outskirts of greater metropolitan areas are still underserved because current matching models only look at what happens before a ride starts, pre-trip matching, and they miss something important.

Emmy: They introduce a model where the platform makes decisions both before a trip starts and while you're actually on the ride.

Ada: That's the core idea of this paper, looking at how that dynamic on-trip matching affects things like profit and efficiency.

Emmy: It really tries to connect those two decisions with pricing as well, which is a big step in how these platforms operate.

The paper's summary: Ada: So the main summary is that they developed a dynamic, stochastic matching model that takes into account both pre-trip and on-trip matching decisions.

Emmy: They found that while pre-trip matching is useful when demand is concentrated, on-trip matching becomes critical in those sparser outskirts where demand is spread out over time.

Ada: That means for those remote areas, the ability to match someone after you're already started a ride matters more than just finding the best match before you leave.

Emmy: And they showed that adding this on-trip matching actually increases the platform's profitability and efficiency while simultaneously lowering prices for riders.

Ada: That’s a win-win situation for both sides, especially in those sparse outskirts.

Kolya: What I'm hearing is that the model suggests on-trip matching isn't just nice to have; it’s what unlocks better performance when demand isn't clustered together.

Ada: Right, Kolya. They found that the addition of on-trip matching substantially improves profit across all instances compared to only doing pre-trip matching.

Emmy: And they linked this directly to pricing, showing that low prices can encourage more riders and also help with the matching decisions themselves.

Kolya: So it’s not just about finding a good ride; it’s about managing the flow of demand over time when you don't have a lot of options available.

Ada: That captures the essence, Kolya. They found that in sparse regions with dispersed demand, medium-to-high heterogeneity on-trip matches become more common than they would be otherwise.

The paper's improvements: Emmy: Now, the authors suggest some ways to improve this framework. First, they propose implementing a state-dependent matching policy based on solving a non-bipartite matching problem at each time step t.

Ada: That means instead of one fixed strategy, the AI system can decide whether to match immediately with an existing solo rider or wait for a potentially better match later.

Emmy: And they also suggest using a generalized cost function to determine the best match, favoring a connection if the value for you is greater than some threshold derived from your price.

Ada: I see that as making the matching decision more reactive to what's happening right now, rather than just planning ahead.

Emmy: And they also suggest optimizing pricing using a method called minorization-maximization, where the AI iteratively constructs surrogate functions to maximize revenue while keeping flow constraints in mind.

Ada: That sounds like a sophisticated way for the system to adjust prices as demand changes during the trip, not just setting one price at the start.

Kolya: From a probabilistic view, this suggests we need bounds on these costs and revenues, and they use fluid relaxation of the MDP model to get an upper bound on long-run average profit.

Ada: So they’re trying to prove that this complex dynamic matching system is better than the simpler pre-trip only version by showing it can be modeled with a fluid relaxation, which gives them that upper bound on profit.

Kolya: But I wonder about the constants in those bounds; are they tight enough for real-world application, especially when dealing with those sparse outskirts where demand is tricky?

Emmy: That's a fair question, Kolya. They acknowledge that modeling the value of waiting for a match over the whole trip duration is challenging because you have to track riders through time.

Conclusion: Ada: So to wrap up, this paper on "On-Trip Matching and Pricing for Shared Rides" shows that successful operation in areas with dispersed demand requires both pre-trip and on-trip matching strategies working together.

Emmy: The main point is that the combination of these two types of matching, when tied into a pricing policy, creates a beneficial outcome for both the platform's profit and the rider's access to service.

Ada: It expands shared rides access substantially in those historically underserved outskirts where median household incomes are lower.

Kolya: I just want to say that the results show that this combined matching policy improves profit substantially across all instances compared with pre-trip matching alone.

Emmy: And Kolya, from a probability standpoint, it suggests that we can model these dynamic decisions rigorously using MDPs and fluid relaxations to get solid performance metrics.

Ada: Exactly. The implication is that platforms should stop focusing only on dense downtown areas and start modeling this new paradigm where on-trip matching is essential for capturing demand in those less concentrated zones.

Emmy: It’s about making the system work better where the traditional model fails, specifically by incorporating that dynamic on-trip element and linking it to pricing.

University of Washington · Tsinghua University · Sauder School of Business, University of British Columbia · University of California, Berkeley

math.OC

Submitted: 2026-04-19

Updated: 2026-10-29

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 88/100

The gist: Shared rides have seen limited success outside of dense urban areas—the sparse outskirts of greater metropolitan areas remain underserved <ref:2604.17552#pg2> The authors developed a dynamic,

Key concepts

Dynamic Stochastic Matching Model: This is a mathematical framework that predicts how shared rides should be matched over time. It considers both decisions made before a trip starts (pre-trip) and during the ride itself (on-trip), making the matching process flexible based on changing conditions.
On-Trip Matching: This strategy involves matching a new rider with an existing solo rider while they are already in transit. It is particularly effective when demand is spread out geographically, as it allows for better utilization of rides in less dense areas compared to just pre-trip matching.
Bilevel Optimization: This mathematical technique is used to solve the complex problem of setting optimal prices and matching rules simultaneously. It involves an inner optimization (cost minimization) nested within an outer optimization (profit maximization), leading to a balanced solution.
Spatially Dispersed Demand: This refers to situations where ride requests are not concentrated in one area but are spread out across a larger geographic region, such as the outskirts of a city. The paper finds that on-trip matching is most beneficial in these dispersed areas.

Terminology

Markov Decision Process — 4× in this paper
Bilevel Optimization — 3× in this paper · explained in 3 episodes
Clustering — 2× in this paper · explained in 2 episodes
Markov Decision Process (MDP) — 2× in this paper · explained in 16 episodes
Objective Function — 2× in this paper · explained in 3 episodes
Benchmark — 1× in this paper · explained in 2 episodes
Core — 1× in this paper · explained in 2 episodes
Curse of Dimensionality — 1× in this paper · explained in 6 episodes
Hypergraph — 1× in this paper · explained in 2 episodes
K-means Clustering — 1× in this paper · explained in 3 episodes
Sparsity — 1× in this paper · explained in 5 episodes

Summary

Shared rides have seen limited success outside of dense urban areas—the sparse outskirts of greater metropolitan areas remain underserved <ref:2604.17552#pg2> The authors developed a dynamic, stochastic matching model that incorporates both pre-trip and on-trip matching decisions, finding that on-trip matching is critical in sparser outskirts where demand is spatially dispersed <ref:2604.17552#pg4> They also found that the addition of on-trip matching increases profitability and efficiency for the platform and lowers prices for riders, particularly in sparse outskirts <ref:2604.17552#pg4>.

Modeling Framework

The paper introduces a dynamic, stochastic matching model where the platform makes both pre-trip and on-trip matching decisions The model is formulated as an average-reward, discrete-time Markov Decision Process (MDP) <ref:2604.17552#pg10>. The state of the system at time t is denoted by st = (st,i,u)(i,u) ∈ C ∈ S <ref:2604.17552#pg10>. The platform implements a static pricing policy and a state-dependent matching policy.

Matching Dynamics and Compatibility

The model defines the set of states C as C:= (i, u)i∈[N],u∈[li−1], where u denotes the number of time periods elapsed since departure. A new rider of type i is matched with an on-trip solo rider (j, u) if they are compatible, defined by two conditions: the Trip Length Condition and the Backtracking Condition. The Trip Length Condition requires lu i,j < li + lj − u, and the Backtracking Condition requires (j, u) should not be on any shortest path from Oi (exclusive) to Dj.

Pricing Optimization via Fluid Relaxation

The optimal pricing and matching problem is formulated as a bilevel optimization where the objective is g:= max λ∈[0,1] X i∈[N] Λ iλi p i(λ i) − C(λ). The inner-level cost minimization problem C(λ) is formulated as a bilevel optimization involving flow variables x and y. A fluid relaxation of this MDP model provides an upper bound on the optimal long-run average profit of the MDP model.

Computational Evidence in Chicago

The authors evaluate their combined matching policy and pricing policies using large-scale simulations on Chicago ridesharing data. They show that adding on-trip matching improves profits and efficiency for the platform and lowers prices for riders, with gains especially pronounced in the outskirts of the city. The results demonstrate that combined matching improves profit substantially across all instances compared with pre-trip matching.

Key Findings on Matching Policy Trade-offs

The paper highlights contrasting behaviors between pre-trip and on-trip matching. Pre-trip matching is primarily about matching value, seeking “ideal” matches with identical origin-destination pairs, hence it is favorable when demand is concentrated. In contrast, on-trip matching is favorable when demand is heterogeneous and spatially dispersed. The results show that in the sparse region where demand is spatially dispersed, medium-to-high-heterogeneity on-trip matches become more common.

Equity and Accessibility Implications

The addition of on-trip matching enables higher profits and efficiency for the platform, allowing it to lower prices for riders or redistribute gains in the form of lower waiting times in the pre-trip phase. The greatest benefits are seen in the sparse outskirts zones, expanding access to shared rides to areas that have historically been underserved. The effect of expanded shared rides access in these sparse zones is substantial, as they correspond to the lowest median household incomes and levels of transit accessibility.

Conclusion

Successful operation of shared rides in large metropolitan areas, where a substantial portion of the demand can be spatially dispersed, requires both pre-trip and on-trip matching. The paper emphasizes the importance of modeling this new matching paradigm. The combination of higher profit and lower prices makes the combined pre-trip and on-trip matching policy a win-win for platform and riders alike.

Improvements for AI systems

Dynamic On-Trip Matching Policy Implementation: The AI system can implement a state-dependent matching policy phi i s 7→ C ∪0 based on solving a non-bipartite matching problem at each time step t, choosing between immediately matching with an existing solo rider or dispatching a solo ride.
Pricing Optimization via Minorization-Maximization: The system can optimize the pricing policy lambda by iteratively constructing surrogate functions Q to maximize revenue subject to flow balance and ratio constraints using the Minorization-Maximization algorithm.
Adaptive Matching based on Trip State: The system can determine matching decisions using a generalized cost function c l u i, j − ξ u i (lambda) − ξ v j (lambda) to find the minimum cost match, favoring a match if γi(lambda) ≥ κi(lambda).
Context-Aware Zone Allocation: The AI can deploy different matching strategies based on geographic zone density, preferring pre-trip matching in dense downtown areas and on-trip matching in sparse outskirts to manage the tradeoff between matching opportunity and value.
Price-Driven Access Expansion: By combining pricing and matching, the system can lower prices for riders, which increases throughput and improves accessibility, specifically expanding shared rides access to historically underserved outskirts zones.

Sources

On the Linear Programming Model for Dynamic Stochastic Matching and Its Application to Pricing