Source-linked AI summary
Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework
Siddhartha Banerjee, Daniel Freund, Thodoris Lykouris
TL;DR
Shared vehicle systems face spatial and temporal supply externalities and high-frequency events, making steady-state control optimization computationally difficult. This paper develops a rigorous convex-relaxation-based approximation framework spanning multiple controls, objectives, and constraints, with parameterized guarantees that recover existing results and are near-optimal in realistic regimes.
Problem
Spatial and temporal supply externalities, together with high-frequency events, make shared vehicle systems more challenging to optimize than traditional limited-supply settings.
Method
The paper develops a rigorous approximation framework using steady-state Markovian models and convex optimization techniques across pricing, matching, rebalancing, objectives, and system constraints.
Results
The framework provides parameterized performance guarantees that improve with vehicle count, recover existing approximate-optimality and asymptotic-optimality results, and are near-optimal in realistic regimes.
Takeaways & Limitations
The framework unifies existing results and supports approximation algorithms for combinations of controls, with guarantees close to 1 for realistic system parameters.
Takeaways & Limitations
The pricing formulation assumes a continuous positive demand density on a contiguous domain and permits prices high enough to make an arbitrarily small or zero customer fraction willing to pay.
Abstract
from arXiv · showhide
Optimizing shared vehicle systems (bike/scooter/car/ride-sharing) is more challenging compared to traditional resource allocation settings due to the presence of \emph{complex network externalities} -- changes in the demand/supply at any location affect future supply throughout the system within short timescales. These externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze such systems. However, using such models to design pricing and other control policies is computationally difficult since the resulting optimization problems are high-dimensional and non-convex. To this end, we develop a \emph{rigorous approximation framework} for shared vehicle systems, providing a unified approach for a wide range of controls (pricing, matching, rebalancing), objective functions (throughput, revenue, welfare), and system constraints (travel-times, welfare benchmarks, posted-price constraints). Our approach is based on the analysis of natural convex relaxations, and obtains as special cases existing approximate-optimal policies for limited settings, asymptotic-optimality results, and heuristic policies. The resulting guarantees are non-asymptotic and parametric, and provide operational insights into the design of real-world systems. In particular, for any shared vehicle system with $n$ stations and $m$ vehicles, our framework obtains an approximation ratio of $1+(n-1)/m$, which is particularly meaningful when $m/n$, the average number of vehicles per station, is large, as is often the case in practice.
1 Introduction
Shared vehicle systems require steady-state control because local decisions create network-wide supply effects. The paper develops a unified approximation framework with non-asymptotic guarantees across controls, objectives, and constraints.
- Motivation: Spatial and temporal supply externalities and high-frequency events make shared vehicle control an infinite-horizon equilibrium problem.A ride changes availability at its origin and future availability elsewhere, so performance depends on the induced dynamic equilibrium.
- Framework scope: The framework covers pricing, matching, and rebalancing across throughput, revenue, and welfare objectives with travel-time and operational constraints.Its scope includes welfare benchmarks, posted-price constraints, limited empty-car movement, and travel times.
- Guarantees: Travel-time guarantees transition from an O(1/m) gap to an O(1/√m) gap in heavy-traffic regimes, providing finite-system results.The paper presents these as the first and only finite-system results with travel times.
- Applications and implications: The approach recovers large-market optimality and existing approximation results while extending to repositioning, neighboring-node matching, and origin-only pricing.For Citi Bike parameters m = 10000 and n = 600, the reported approximation ratio is 1.06.
2 Preliminaries
The paper models shared vehicle systems as finite-state continuous-time Markov chains and optimizes steady-state rewards through pricing policies. It highlights non-concavity caused by vehicle availability and network interactions, motivating specialized approximations.
- Basic Setting: Customers arrive according to Poisson processes, accept quoted prices according to origin-destination value distributions, and can ride only when a vehicle is available.Acceptance probability is represented by the demand quantile qij = 1 − Fij(pij).
- Basic Setting: A finite-state continuous-time Markov chain tracks vehicle counts across n stations, with rides producing state transitions between station configurations.The state space contains all nonnegative vehicle allocations summing to m.
- Pricing Policies: Pricing policies may depend on the full vehicle configuration, creating potentially state-dependent prices and a steady-state optimization problem over Markov-chain behavior.The policy assigns prices or equivalent quantiles to each system state, with a stationary distribution satisfying balance equations.
- Objectives: The framework considers throughput, social welfare, and revenue through per-ride reward functions and quantile-based reward curves.Throughput uses unit reward, welfare uses passenger value, and revenue uses the quoted price.
- State-Independent Pricing: State-independent pricing fixes each origin-destination price, yielding a closed queueing network whose node departure rates are constant whenever vehicles are present.The resulting model is a special case of a Gordon-Newell network.
- Non-Concavity: Finite-unit throughput can be non-concave in prices or quantiles, as shown by a three-node example in which changing the B-to-C quantile produces sharply different throughput levels.The example contrasts small throughput near all-one quantiles with large throughput when qBC is small.
A B C
The paper connects shared vehicle dynamics to closed migration and queueing-network models, then analyzes finite- and infinite-unit stationary behavior. In the infinite-unit limit, node availability is determined by relative routing quantities.
- Queueing-Network Model: Shared vehicle systems are represented as BCMP networks and special cases of closed migration processes with fixed vehicle populations.The closed migration process is a continuous-time Markov chain whose transition rates depend on routing probabilities and node service rates.
- Stationary Distribution: Under pricing-induced routing, node and link service rates describe vehicle departures and travel-time queues, producing a product-form stationary distribution.For link queues, the departure rate is proportional to the number of vehicles in transit divided by mean travel time.
- Travel Times: With travel delays, vehicles alternate between node queues and link queues, changing the invariant availability weights relative to instantaneous rides.The delay model assigns distinct stationary mass contributions to node and link queues.
- Infinite-Unit Limit: As m →∞, the finite-unit stationary distribution converges to a limiting distribution containing a node with availability 1.This property supports a combinatorial route from infinite-unit behavior to finite-unit guarantees.
- Infinite-Unit Limit: In the infinite-unit limit, the steady-state availability of node i equals ri(q) divided by the maximum rj(q) across nodes.The quantities ri(q) and wi(q) do not depend on the number of vehicles.
3 Our Approximation Framework
The approximation framework combines an elevated objective with flow-conservation constraints to form a convex relaxation, then pulls its solution back to finite systems. For pricing, it guarantees a factor 1 + (n−1)/m relative to optimal state-dependent pricing.
- Framework Scope: The framework begins with pricing without travel times, then extends the same analysis to travel times, other controls, and constrained pricing settings.It also covers throughput, revenue, welfare, matching, and rebalancing objectives or controls.
- Motivation: State-dependent pricing is difficult because it can require exponentially many prices, while even state-independent pricing is non-convex in its quantiles.The framework addresses both hurdles by restricting policy search and introducing a convex relaxation.
- Elevated Objective: The elevated objective upper-bounds the true objective while remaining concave in the quantiles, because it ignores availability-induced demand thinning.Its concavity relies on concave reward curves.
- Flow Polytope: The flow polytope reinstates network externalities through linear demand-bounding and supply-circulation constraints on steady-state flows and effective quantiles.These constraints encode necessary realizability conditions and flow conservation.
- Relaxation Algorithm: For throughput, combining the elevated objective with the flow polytope yields a linear elevated flow relaxation whose solution produces state-independent prices.The algorithm solves for quantiles and converts them to prices using the inverse demand function.
- Approximation Guarantee: 1 + (n−1)/m is the approximation factor obtained for pricing with concave reward curves relative to the optimal state-dependent policy.The pullback argument uses a finite-system maximum availability lower bound of m/(m+n−1).
4 Incorporating Travel Times Between Nodes
With travel times, in-transit vehicles create an additional conservation constraint and make approximation guarantees depend on demand loading. The framework extends the elevated flow relaxation and characterizes when convergence is O(1/m) versus O(1/√m), including limits on faster rates.
- Availability analysis: Conditioned on M available units, node inventories follow an n-node M-unit Gordon-Newell network.This identity supports bounding availability in the finite system with travel times.
- Rate-limited relaxation: Travel times add a rate-limiting constraint because the number of units in transit cannot exceed m.The constraint is incorporated into the elevated flow relaxation used for pricing.
- Asymptotic guarantee: For fixed n, the rate-limited relaxation policy is asymptotically optimal as m →∞ for arbitrary demand rates and transit delays.This applies to the stated finite-system pricing framework and its delay parameters.
- Tightness: When the rate-limiting constraint is tight and demand grows with m, O(1/m) convergence cannot be achieved even by an optimal policy.The paper identifies this as a fundamental limitation rather than merely an algorithmic shortcoming.
5 Applications of our Framework
The framework extends elevated flow relaxations beyond basic pricing to supply and demand redirection, discrete-price and multi-objective settings, and repositioning constraints. These extensions yield finite approximation guarantees, including bicriterion guarantees and performance factors depending on the number of vehicles and stations.
- 5.1 Rebalancing Controls Beyond Pricing: Supply redirection lets platforms choose whether arriving units remain at destinations or move elsewhere, potentially incurring redirection costs.The framework derives pricing and redirection policies from an elevated flow relaxation.
- 5.1 Rebalancing Controls Beyond Pricing: The elevated flow relaxation enforces demand bounding, supply circulation, and the restriction that only customer drop-offs—not empty units—can be redirected.These constraints apply to rates induced by any state-dependent policy.
- 5.1 Rebalancing Controls Beyond Pricing: m/(m+n−1) approximates optimal state-dependent performance for supply redirection and repositioning without pricing.The supply-redirection guarantee compares Algorithm 3 with optimal state-dependent pricing and redirection, while the repositioning-only result covers settings where pricing is unavailable.
- 5.1 Rebalancing Controls Beyond Pricing: Demand redirection extends supply circulation to account for units and users entering or leaving through nearby-node matching.The corresponding constraints ensure that customers are matched only to units arriving at nearby nodes.
- 5.3 Pricing in Multi-Objective Settings: The framework supports multi-objective pricing by elevating both objectives and optimizing a concave objective over a convex feasible polytope.For objectives Φm and Ψm, the resulting solution is a (γ, γ) bicriterion approximation with γ = m/(m+n−1).
- 5 Applications of our Framework: The same approach extends to multiple welfare-style constraints and limits on repositioning while preserving finite performance guarantees.With repositioning constraints, the objective remains within a factor of 1+(n−1)/(m+n−1), and constraints satisfied in the infinite-unit system are also satisfied in the finite-unit system.
6 Conclusions
The paper unifies pricing and optimization across shared-vehicle objectives, controls, and constraints with finite guarantees, while identifying conservation-law-based policies and extensions beyond the current model.
- The framework unifies pricing and optimization across objectives, controls, and system constraints, including travel-times and unbalanced networks.It provides rigorous finite-system guarantees across these settings.
- Expected flow conservation and Little’s law yield near-optimal policies in regimes of interest.
- The elevated flow relaxation couples a fluid model with a product-form distribution and may apply beyond shared-vehicle systems.Such applications depend on understanding the associated partition function.
- Bounded prices remain a challenging extension because they complicate deriving a flow relaxation coupled appropriately with the stochastic system.
- The pricing policies do not impose triangle inequality, potentially incentivizing customers to use an extra stop.Addressing these strategic considerations is identified as future research.
- State-independent prices have strong performance only under steady state and complete knowledge of system parameters.Relaxing either assumption is left as an extension.
A Irreducibility of the Priced System
The appendix shows that pricing can be perturbed to make the positive-flow graph strongly connected while preserving balanced demand and retaining throughput arbitrarily close to the original.
- The proof begins by assuming the underlying positive-demand graph is strongly connected and uses balanced demand without loss of generality.
- Any infinite-unit pricing solution can be approximated by one whose positive-flow graph is strongly connected.The resulting throughput is at least (1 − ε) times the original.
- The construction repeatedly increases demand on zero-flow positive-demand edges and decreases demand on positive-flow edges.
- After at most k flow reductions, each retained flow satisfies fij(q′) ≥ (1 − ε)fij(q), preserving total throughput within factor 1 − ε.
- Demand is shifted along paths between components while preserving flow conservation and respecting edge capacities.
B Concave Reward Curves
The appendix establishes when reward curves are concave and shows that concavity implies non-increasing per-ride rewards, covering revenue, throughput, and social welfare under stated distributional conditions.
- Revenue satisfies the theorem’s assumptions under regular value distributions, while throughput and social welfare satisfy them under any value distribution.
- Throughput satisfies concavity for any value distribution because its reward curve R(q) = q is linear.
- Revenue has a concave reward curve exactly when the value distribution is regular.
- The proof for social welfare uses the distribution’s hazard rate and the price–quantile relationship.
- If qI(q) is concave, then I(q) is non-increasing in the quantile.Thus concave reward curves imply non-increasing per-ride rewards.
C Appendix on Point Pricing
The point-pricing appendix develops an elevated flow relaxation for origin-based prices, extends it to discrete price sets, and provides approximation guarantees relative to optimal state-dependent point pricing.
- Point pricing restricts prices to depend only on the origin node, with identical customer value distributions across destinations at each origin.This models the surge-multiplier setting described for Uber and Lyft.
- Discrete-price guarantees incur extra loss depending on how well available prices represent each part of the distribution.
- The results extend immediately to rate-limiting constraints, even when balanced demand is infeasible under restricted prices.
- Algorithm 6 solves the unrestricted point-price relaxation and outputs state-independent prices from the resulting quantiles.
- Under point pricing, the optimization can reduce to one variable, and throughput or social welfare requires only one eigenvector computation.
- Discrete prices are obtained by rounding each preliminary quantile down to the largest available feasible quantile.
- The discrete-price policy applies to concave reward curves and is compared with the optimal state-dependent point-pricing policy.
D Settings Without Prices
The framework extends beyond pricing to settings where supply or demand redirection is available without pricing. It uses quantile-like variables to represent service fractions in the infinite-unit limit.
- Supply and demand redirection can be combined with pricing while retaining the guarantees established for pure pricing.
- Without pricing, quantile-like variables capture the fraction of customers served in the infinite-unit limit.
D.1 Quantiles Without Prices
Without pricing, the framework models availability-based service through quantiles and optimizes an elevated objective over a linear-program relaxation. The resulting policy admits a finite-system guarantee relative to the optimal state-dependent policy.
- D.1 Quantiles Without Prices: Availability-based quantiles represent the induced infinite-unit availabilities rather than destination-specific admission controls.Pricing is unavailable, so the quantiles arise through system availabilities.
- D.1 Quantiles Without Prices: The elevated objective is optimized over a polytope whose constraints encode demand bounding, supply circulation, and restricted rebalancing.Because availability-based admission cannot distinguish destinations, the formulation uses station-level quantiles.
- D.1 Quantiles Without Prices: The relaxation is formulated as a linear program using arrival rates, per-ride rewards, and rerouting costs.
- D.1 Quantiles Without Prices: Obj∞(er) is at least d Obj(eq,er) for the quantiles and redirection probabilities returned by Algorithm 8.
- D.1 Quantiles Without Prices: The finite-system guarantee for demand redirection without pricing compares the constructed objective with the optimal state-dependent policy.The displayed theorem statement supplies the comparison factor, but its numerator and denominator are fragmented in the passage.
- D.1 Quantiles Without Prices: The finite-system comparison is based on the infinite-unit limit rather than a balanced-demand property.
D.2 Delays Without Prices
Removing pricing while retaining travel delays requires a different argument because pricing previously regulated the number of units in transit. The framework uses stochastic dominance and rate-limited relaxations to recover guarantees.
- D.2 Delays Without Prices: Without prices, demand cannot regulate maximum availability, so the travel-delay analysis uses a stochastic-dominance characterization of closed queueing networks.
- D.2 Delays Without Prices: Increasing point quantiles does not decrease the realized-trip rate on any origin-destination edge.
- D.2 Delays Without Prices: The quantile monotonicity result supports guarantees for systems where prices cannot provide a lower bound on maximum availability.
- D.2 Delays Without Prices: Theorem 34 gives a finite-system guarantee for any objective when ε_m := 2 ln m/m and m ≥100.
- D.2 Delays Without Prices: Algorithm 9 introduces a rate-limited elevated-flow relaxation for redirection without prices and with travel times.Its inputs include a scaling parameter, arrival rates, rewards, rerouting costs, and travel times.
- D.2 Delays Without Prices: As m →∞, the theorem recovers and strengthens an earlier result through a finite guarantee and a convergence rate.For some regimes, the same reasoning yields a linear convergence rate to the elevated-flow objective.
E Auxiliary Lemma
The auxiliary result provides a Chernoff tail bound for Poisson random variables, which is used in the travel-time analysis.
- E Auxiliary Lemma: For X ∼ Poisson(λ), the auxiliary lemma provides a Chernoff bound for the lower tail with 0 ≤ x ≤ λ.
- E Auxiliary Lemma: The bound is derived by applying the standard Chernoff argument and setting θ = log(1 + x/λ).
F Alternate Proof of Lemma 14
The section gives an alternate stochastic-coupling proof of Lemma 14. The argument translates an existing inequality into this setting, normalizes it, and applies Lemma 12 to obtain the result.
- A stochastic coupling argument provides an alternate proof of Lemma 14.The argument adapts an inequality from Zahorjan et al. to the paper’s context.
- The translated inequality supplies the key bound used in the proof.
- Normalizing the resulting expression leads to the form needed for the final implication.
- Lemma 12 then implies the result.