Pricing and Optimization in Shared Vehicle Systems:
An Approximation Framework
Siddhartha Banerjee

∗

Daniel Freund

†

Thodoris Lykouris

‡

Abstract

arXiv:1608.06819v3 [cs.GT] 16 May 2017

Optimizing shared vehicle systems (bike-sharing/car-sharing/ride-sharing) is more challenging compared to traditional resource allocation settings due to the presence of 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/control policies is computationally difficult
since the resulting optimization problems are high-dimensional and non-convex.
To this end, we develop a general approximation framework for designing pricing policies
in shared vehicle systems, based on a novel convex relaxation which we term elevated flow
relaxation. Our approach provides the first efficient algorithms with rigorous approximation
guarantees for a wide range of objective functions (throughput, revenue, welfare). For any
shared vehicle system with n stations and m vehicles, our framework provides a pricing policy
with an approximation ratio of 1 + (n − 1)/m. This guarantee is particularly meaningful
when m/n, the average number of vehicles per station is large, as is often the case in practice.
Further, the simplicity of our approach allows us to extend it to more complex settings:
rebalancing empty vehicles, redirecting riders to nearby vehicles, multi-objective settings (such
as Ramsey pricing), incorporating travel-times, etc. Our approach yields efficient algorithms
with the same approximation guarantees for all these problems, and in the process, obtains
as special cases several existing heuristics and asymptotic guarantees.

∗

Cornell University, sbanerjee@cornell.edu. Work supported by ARL grant W911NF-17-1-0094.
Cornell University, df365@cornell.edu. Work supported under NSF grants CCF-1526067, CMMI-1537394
and CCF-1522054.
‡
Cornell University, teddlyk@cs.cornell.edu. Work supported under NSF grant CCF-1563714, ONR grant
N00014-08-1-0031, and a Google faculty research award.
†

1

Introduction

Shared vehicle systems, such as those for bike-sharing (e.g., Citi Bike in NYC, Vélib in Paris),
car-sharing (e.g., car2go, Zipcar) and ride-sharing (e.g., Uber, Lyft), are fast becoming essential
components of the urban transit infrastructure. In such systems, customers have access to a
collection of personal transportation vehicles, which can be engaged anytime (subject to vehicle
availability) and between a large number of source-destination locations. In bike- and car-sharing,
the vehicles are operated by the customers themselves, while in ride-sharing they are operated
by independent drivers.
All vehicle sharing systems experience inefficiencies due to limited supply (vehicles) and asymmetric demand across time and space. These inefficiencies, however, can often be greatly reduced
by rebalancing the demand and/or supply. Pricing has traditionally been the main tool to
balance demand and supply in limited resource settings: for instance, in limited-item auctions
or hotel reservations. Ride-sharing platforms have long utilized dynamic pricing, and today,
many bike- and car-sharing platforms are also experimenting with point-to-point prices and other
location-based incentive schemes [Kat16]. Shared vehicle platforms also enable other means of
rebalancing demand and supply, such as repositioning empty-vehicles, or redirecting customers
to nearby stations (cf. Section 1.2). Moreover, different platforms use these tools towards
achieving different objectives – examples include revenue/welfare/throughput maximization,
multi-objective settings, etc. Our work develops a unifying queueing-theoretic framework for
designing such rebalancing policies, under a variety of controls and constraints, with performance
guarantees for a large class of objectives.
While rebalancing in shared vehicle systems is necessitated by spatial demand heterogeneity, it is
more challenging compared to other limited-resource settings due to the presence of spatial supply
dependencies. This is an extreme type of a network externality where, whenever a customer
engages a vehicle, this not only decreases the instantaneous availability at the source location,
but also affects the future availability at all other locations in the system. Moreover, the high
frequency of events (passenger arrivals/rides) tends to drive such systems into operating under a
dynamic equilibrium state (or steady-state). The performance of any pricing/control policy is
thus determined by this equilibrium which is induced by the controls, demand, and supply; in a
nutshell, this is the key difficulty in designing policies for such systems.
Both spatial demand heterogeneity and supply dependencies are captured by closed queueingnetwork models [Ser99, Kel11], which are widely used in the literature on shared vehicle systems [Geo12, ZP16, WJ14]. These models use a Markov chain to track the number of vehicles
across locations. Each location experiences a stream of arriving customers, who engage available
vehicles and take them to their desired destination. Increasing the price for a ride between a
pair of stations decreases the number of customers willing to take that ride, which over time
affects the distribution of vehicles across all stations. Even though demand rates and price
elasticities can be estimated using historical data, enabling the calibration of accurate closed
queueing-network models, the problem of designing good pricing/control policies under such a
model has a non-convex structure due to the equilibrium constraints. Consequently, previous work
has focused only on a narrow set of objectives (typically, some form of weighted throughput) and
is largely based on heuristics or simulation/numerical techniques, with few provable guarantees
(cf. Section 1.2 for a discussion). Therefore, algorithms for other objectives (e.g. revenue and
welfare) as well as more complex constrained settings, have yet to be addressed.
A class of constrained problems of particular interest are multi-objective settings, where the goal
is to optimize some objective subject to a lower bound on another. A canonical example is
the so-called Ramsey pricing problem [Ram27]: designing a pricing policy to maximize system
revenue subject to a lower bound on the system welfare. For many shared vehicle systems this is

1

the most relevant objective, since they are operated by private companies in close partnership
with city governments. For instance, the Citi Bike system in New York City is run by Motivate,
a private company, under service-level agreements with the NYC Department of Transportation.
The complementary problem (maximizing welfare subject to revenue constraints) is of interest
when such systems are managed by non-profit organizations (e.g., Pronto in Seattle); such
multi-objective paradigms are also under consideration in other market-design settings such as
the FCC spectrum auction [MS14].
Our work leverages techniques from convex optimization and approximation algorithms to provide
a unified framework for designing efficient algorithms for pricing (and other rebalancing controls)
in closed queueing networks. We obtain performance guarantees for a large class of optimization
problems (including multi-objective settings); significantly, our guarantees are near-optimal in
the parameter regime of real systems. Moreover, given the widespread use of closed queueing
models for a variety of other applications, 1 we anticipate that our framework can prove useful in
these areas as well.

1.1

Outline of our Contributions

We model a shared vehicle system as a continuous-time Markov chain that tracks the number
of vehicles (units) at each station (node), and use this framework to study a variety of pricing
and control problems. We use pricing as a primary example to illustrate our methodology and
present extensions to other controls in Section 5.
A brief description of our model is as follows (cf. Section 2 for details). Each station in the system
observes a Poisson arrival of customers. Arriving customers draw a value and a destination from
some known distribution. Upon arrival at a station, the customer is quoted a price and one of
three scenarios occurs: i) the customer is not willing to pay the price, i.e. the price exceeds
her value, and she leaves the system, ii) the customer is willing to pay the price but no unit is
available at the node; therefore she again leaves the system, or iii) the customer is willing to pay
the price, and a vehicle is available. A ride occurs only in the final case with the vehicle moving
to the customer’s destination. The state of the continuous-time Markov chain at the origin and
the destination is then instantaneously updated. This describes the basic dynamics under which
we aim to maximize the long-run average performance, measured by the throughput, the social
welfare, or the revenue obtained in steady-state. Unfortunately, this problem is non-convex even
in very basic settings (cf. Section 2.4), thereby posing technical hurdles for optimization.
In Section 3, we propose a simple pricing policy, based on optimizing over a novel convex
relaxation, which we term elevated flow relaxation. Our relaxation separately tackles nonconvexities appearing in both the objective and the constraints. For the objective, we identify a
concave pointwise upper bound which we call elevated objective. For the constraints, we derive a
natural convex relaxation on the rates at which customers are served. As the elevated objective is
bounded below by the original objective, optimal solutions in the elevated optimization problem
are bounded below in value by optimal solutions in the original optimization problem.
In Section 4, we present our main result, namely that the above policy gives an approximation
ratio of 1 + (n − 1)/m for the objectives we consider. Although, our policy is state independent,
i.e. the prices do not differ based on the configuration of units across nodes, the guarantee
holds with respect to the optimal state-dependent policy. The idea of the proof is based on the
following three steps:
1

In addition to transportation settings, [Ser99] and [Kel11] list applications of closed queueing networks in
computing and communications, healthcare, industrial applications, etc.

2

1. First, we notice that, for any state-dependent policy in the m-unit system (and therefore
also for the optimal), there exists a feasible solution in our relaxation that upper bounds
its value. Hence, the elevated value of our policy upper bounds the original objective of
the optimal state-dependent policy in the m-unit system.
2. Next, we observe that the elevated objective of our policy is equal to the original objective
in a hypothetical infinite-supply setting. For this part, we exploit a structural property of
our solution, under which we prove that in the infinite-supply setting the elevated objective
collapses to the original objective.
3. Last, we show that the performance of any policy in the m-unit setting approximates its
performance in the infinite-supply setting within a factor of 1 + (n − 1)/m. The proof
applies a combinatorial construction of a biregular graph that relates the state spaces of
the m- and (m − 1)-unit systems.
In Section 5, we demonstrate the versatility of our results. In particular, we show that the above
framework, comprising of a policy derived via an appropriate elevated flow relaxation, and the
three-step process to prove its guarantees, can be extended and applied to other settings.
• In Section 5.1 we introduce two other rebalancing controls previously studied in the literature,
and obtain 1+(n−1)/m approximation guarantees for the respective optimization problems.
In the first, units can move to a new location after ending a trip; in the second, customers
can be matched to units at neighboring nodes. In both cases, we recover and strengthen
the previous results.
• In Section 5.2 we use our techniques to optimize in multiobjective settings where the goal
is to maximize one objective subject to a lower bound on another. In this context we
obtain a (γ, γ) bicriteria approximation guarantee with γ = (1 + n−1
m ). This is motivated
by paradigms like Ramsey pricing as we discussed above.
• In Section 5.3 we show that similar approximation guarantees continue to hold when rides
do not occur instantaneously but instead require some delay (travel time).
• In Section 5.4, we consider a special case of the basic pricing problem where the customers’
value distributions depend only on their source node and the platform is limited to point
prices, that are based only on the origin of a trip, but not on the destination. The latter
assumption is motivated by contemporary schemes like surge pricing. We show that in this
case the optimization problem then collapses to a one-dimensional concave maximization,
allowing us to incorporate additional constraints.
Our results not only recover and unify all existing results in this area, but also provide rigorous
approximation guarantees for a wide range of objective functions in all of the above settings.
While our guarantees depend on the size of the system, they are close to 1 for realistic system
parameters. For instance, for the parameters (m = 10000, n = 600) of New York City’s Citi Bike
system, we obtain an approximation ratio of 1.06.

1.2

Related work

There is a large literature on characterizing open and closed queueing-network models, building
on seminal work of Jackson [Jac63], Gordon and Newell [GN67], and Baskett et al. [BCMP75];
the books by Kelly [Kel11] and Serfozo [Ser99] provide an excellent summary. Optimal resource
allocation in open queueing networks also has a long history, going back to the work of Whittle
[Whi85]. However, there is much less work for closed networks, in part due to the presence of
a normalization constant for which there is no closed-form (though it is computable in O(nm)
time via iterative techniques [Buz73, RL80]). Most existing work on optimizing closed queueing
3

networks use heuristics, with limited or no guarantees. In contrast, our work focuses on obtaining
algorithms with provable guarantees for a wide range of problems.
Three popular approaches for closed queueing-network optimization in the literature are: (i)
using open queueing-network approximations, (ii) heuristically imposing a ‘fairness’ property,
which we refer to as the demand circulation constraint (cf. Section 3.3), and (iii) characterizing
the fluid limits of closed queueing networks, and obtaining solutions that are optimal in these
scaling regimes. We now briefly describe each approach.
The first approach was formalized by Whitt [Whi84], via the fixed-population-mean (FPM)
method, where exogenous arrival rates are chosen to ensure the mean population is m. It has
since been used in many applications; for example, Brooks et al. [BKM13] use it to derive
policies for matching debris-removal vehicles to routes following natural disasters. Performance
guarantees however are available only in restricted settings.
Another line of work is based on heuristics that enforce the demand circulation property (variously
referred to as the demand rebalancing/fairness/bottleneck property). In transportation settings,
George et al. used these to optimize weighted throughput [Geo12], Zhang et al. to minimize
rebalancing costs [ZP16]. Most works typically only provide asymptotic guarantees [GXS12].
More recently, Ozkan and Ward [OW16] and Braverman et al. [BDLY16] characterized appropriate fluid (or large-market) limits for closed queueing networks, and used it to study the operations
of ride-sharing systems. In contrast to our work, which focuses on optimizing a given finite-m
system, these works consider a regime where m and the arrival rates of passengers together scale
to ∞, and characterize the optimal policy in the limit. Within this limit, the former studied
the assignment of customers to nearby drivers, whereas the latter considered directing drivers at
the end of each trip to under-served locations. Our extensions to settings beyond pricing (cf.
Section 5.1) are inspired by these works; in particular, we show that similar scaling results can be
derived within our framework. Moreover, our work provides guarantees for the resulting policies
in the finite case (i.e., before taking the limit), and also against a much more general class of
state-dependent policies.
The closest work to ours is that of Waserhole and Jost [WJ14], who provide a pricing policy
for maximizing throughput in closed queueing networks, with the same approximation ratio we
obtain. They do this via a different argument wherein they observe that, under the demand
circulation property, the Markov chain is doubly stochastic, and hence has a uniform distribution
(this was also noted earlier by Whitt [Whi84]). A simple counting argument then implies that
the probability of a station having a vehicle is m/(m + n − 1). Moreover, since the maximum
throughput under any policy is bounded by the maximum demand circulation, the maximum
throughput under demand circulation is within a m/(m + n − 1) factor of the optimum. This
argument is finely tuned to this particular setting (maximizing throughput via pricing with no
delays). In contrast, our approach can accommodate several objectives and rebalancing controls
as well as delays.
Finally, we note that there is a parallel line of work which tackles settings with dynamic arrivals
and pricing, using techniques from approximate dynamic programming [Ade07, LR10, HMW09].
These typically can deal only with small systems, as their dimensionality scales rapidly with the
number of stations; moreover, many of the techniques have no provable guarantees.

2

Preliminaries

In this section, we first formally define our model of shared vehicle systems and formulate the
optimal pricing problem. To capture the complex network externalities of the system, we define

4

a probabilistic model of customer arrivals, which we analyze in steady state. Subsequently, we
introduce known results from the queuing literature that provide the technical background upon
which our analysis relies. Finally, we present an example that shows that even in the restricted
sets of pricing policies, that are independent of the configuration of vehicles across the system,
the optimization problems we consider are non-convex.

2.1

Basic setting

We consider a system with m units (corresponding to vehicles) and n nodes (corresponding to
stations). Customers traveling between nodes i and j arrive at node i according to a Poisson
process of rate φij . Each customer traveling from i to j has a value drawn independently from a
distribution Fij (·). We assume that Fij has a density and that all values are positive with some
probability, i.e. Fij (0) < 1. Upon arrival at i, a customer is quoted a price pij , and engages a
unit if her value exceeds this price, i.e. with probability 1 − Fij (pij ), and at least one unit is
available at node i; else she leaves the system.
As is common with pricing, the related optimization problems are often more easily framed in
terms of the inverse demand (or quantile) function associated with the user as qij = 1 − Fij (pij ).
For ease of presentation we assume that the density of Fij is positive everywhere in its domain,
implying that there is a 1-1 mapping between prices and quantiles. As Fij is therefore invertible,
we can write pij = Fij−1 (1 − qij ). This allows us to abuse notation throughout the paper by using
prices and quantiles interchangeably.
A continuous-time Markov chain tracks the number of units across nodes. At time t ≥ 0, the state
of the Markov chain X(t) = (X1 (t), . . . , Xn (t)) contains the number of units Xi (t) present
at each
P
n
node i. The state space of the system is denoted by Sn,m = {(x1, x2 , . . . , xn ) ∈ N0 | i xi = m}. 2
Note that the state-space is finite; moreover, |Sn,m | = m+n−1
= Ω(mn ). Since our focus is on
n−1
the long-run average performance, i.e. system performance under the steady state of the Markov
chain, we henceforth suppress the dependence on t for ease of notation.
For ease of presentation, we assume that rides between nodes occur without delay. In the context
of our model, this translates into an instantaneous state transition from X to X − ei + ej when a
customer engages a unit to travel from i to j (where ei denotes the ith canonical unit vector).
We relax this assumption in Section 5.3.

2.2

Pricing Policies and Objectives

We consider pricing policies that select point-to-point prices pij as a function of the overall
state X. Formally, given arrival rates and demand elasticities {φij , Fij (·)}, we want to design
a pricing policy p(·) = {pij (·)}, where each pij : Sn,m → R ∪ {±∞} maps the state to a price
for a ride between i and j. Equivalently, we want to select quantiles q(·) = {qij } where each
qij : Sn,m → [0, 1]. For a fixed pricing policy p with corresponding quantiles q, the effective
demand stream from i to j (i.e. customers traveling from node i to j with value exceeding pij )
thus follows a state-dependent Poisson process with rate φij qij (X). 3 State-dependent prices also
allow us to capture unavailability by defining qij (x) = 0 if xi = 0 (i.e. a customer with origin i is
always turned away if there are no units at that station; recall we defined Fij (∞) = 1). Thus, a
pricing policy p, along with arrival rates and demand elasticities {φij , Fij (·)}, determines the
transitions of the Markov chain. Note that this is a finite-state Markov chain, and furthermore,
2

We use X(t), Xi (t) to indicate random variables, and x, xi to denote specific elements of the state space.
This follows from the notion of probabilistic thinning of a Poisson process – the rate of customers wanting
to travel from i to j is a Poisson process of rate φij , and each customer is independently willing to pay pij with
probability qij = 1 − Fij (pij ).
3

5

is irreducible under weak assumptions on the prices and the demand (cf. Appendix
A); hence, it
P
has a unique steady-state distribution π(·) with π(x) ≥ 0 ∀ x ∈ Sn,m and x∈Sn,m π(x) = 1.
Our goal is to design a pricing policy p to maximize the steady-state performance under various
objectives. In particular, we consider objective functions that decompose into per-ride reward
functions Iij : R → R, which correspond to the reward obtained from a customer engaging a ride
between stations i and j at price p. The per-ride rewards corresponding to the three canonical
objective functions are:
• Throughput: the total rate of rides in the system; for this, we set IijT (p) = 1.
• Social welfare: the per-ride contribution to welfare is given by IijW (p) = EV ∼Fij [V |V ≥ p].
• Revenue: to find the system’s revenue rate, we can set IijR (p) = p.
We abuse notation to define Iij (q) , Iij (Fij−1 (1 − q)) as a function of the quantile instead of the
price. We also define the reward curves Rij (q) := q · Iij (q) (analogous to the notion of revenue
curves; cf. [Har14]). Our results require the technical condition that Rij (q) are concave in q,
which implies that Iij (q) are non-increasing in q (equivalently Iij (p) are non-decreasing in p). We
note that this assumption holds for throughput and welfare under all considered distributions, and
revenue for regular distributions. For completeness, we prove these observations in Appendix B.
For a given objective, our aim is to select a pricing policy p, equivalently quantiles q, that
maximizes the steady-state rate of reward accumulation, given by
X

X

X
X


Objm (q) =
π(x)·
φij ·qij (x)·Iij qij (x) =
π(x)·
φij ·Rij qij (x) . (1)
x∈Sn,m

i,j

x∈Sn,m

i,j

Intuitively, Equation (1) captures that at any node i, customers destined for j arrive via a Poisson
process with rate φij , and find the system in state x ∈ Sn,m with probability π(x). They are
then quoted a price pij (x) (corresponding to quantile qij (x)), and engage a ride with probability
qij (x). The resulting ride then contributes in expectation Iij (qij (x)) to the objective function.
Recall that unavailability of units is captured by our assumption that qij (x) = 0 whenever xi = 0.

2.3

State-Independent Pricing and Closed Queueing Models

The Markov chain described in Section 2.1 has the structure of a closed queueing network 4 (cf.
[Ser99, Kel11]), a well-studied class of models in applied probability. Our analysis crucially relies
on some classical results from the queuing theory literature, which we review in this section. Our
presentation here closely resembles that of Serfozo [Ser99]. One particular class of pricing policies
is that of state-independent policies, wherein we set point-to-point prices {pij } which do not
react to the state of the system. As a consequence, the rate of units departing from any node i at
any time t when Xi (t) > 0 is a constant, independent of the state of the network. The resulting
model is a special case of a closed queueing model proposed by Gordon and Newell [GN67].
Definition 1. A Gordon-Newell network is a continuous-time Markov chain on states x ∈ Sn,m ,
in which for any state x and any i, j ∈ [n], the chain transitions from x to x − ei + ej at a
rate λij µi 1{xi (t)>0} , where µi > P
0 is referred to as the service rate at node i, and λij ≥ 0 as the
routing probabilities satisfying j λij = 1.
In other words, if units are present at a node i in state x, then departures from that node occur
according to a Poisson distribution with rate µi > 0; conditioning on a departure, the destination
j is chosen according to state-independent routing probabilities λij .
4

Here closed refers to the fact that the number of units remains constant; in open networks, units may arrive
and depart from the system.

6

The Markovian dynamics resulting from state-independent pricing policies fulfill the conditions of
Gordon-Newell networks: fixing a price pij (with corresponding qij ) results in a Poisson process
with rate φij qij of arriving customers willing to pay price pij . These customers engage a unit
only if one is available, else leave the system. Thus, given
P quantiles q, the time to a departure
from node i is distributed exponentially with rate µi = j φij qij when Xi > 0 and with rate 0
otherwise. Further, conditioned on an arriving customer having value at least
P equal to the quoted
price, the probability that the customer’s destination is j, is λij = φij qij / k φik qik , independent
of system state.
One advantage of considering state-independent policies (and drawing connections with GordonNewell networks) is that the resulting steady-state distribution {πp,m (x)}x∈Sn,m can be expressed
in product form, as established by the Gordon-Newell theorem.
Theorem (Gordon-Newell Theorem [GN67]). Consider an m-unit n-node Gordon-Newell network with transition rates µi and routing probabilities λij . Let {wi }i∈[n] denote the invariant
distribution associated with the routing probability matrix {λij }i,j∈[n] , and define the traffic
P
intensity at node i as ri = wi / j φij . Then the stationary distribution is given by:
π(x) =

n
1 Y
(rj )xj ,
Gm

(2)

j=1

where the Gordon-Newell normalization constant is given by Gm =

P

x∈Sn,m

Qn

j=1 (rj )

xj

.

We now show how the Gordon-Newell theorem can be used to simplify the objective function
in Equation (1). Recall that for an m-unit system with state-independent policyP
p (with
corresponding quantiles q), we obtain
a
Gordon-Newell
network
with
service
rate
j φij qij
P
and routing probabilities φij qij / k φik qik at node i. Let {π(x)}x∈Sn,m be the corresponding
steady-state distribution. Since q is no longer a function
P of the system state, we can no longer
set qi = 0 when Xi = 0. Instead, we define Ai,m (q) = x∈Sn,m π(x)1{xi >0} as the steady-state
availability of units at node i (i.e. the probability in steady-state that at least one unit is present
at node i), and fij,m (q) = Ai,m (q) · φij qij to be the steady-state rate of units moving from node
i to j. Then, from Equation (2), one can derive (see e.g. Proposition 1.33 and Equation 1.31 in
[Ser99])
Ai,m (q) = (Gm−1 (q)/Gm (q)) · ri (q).
(3)
Notice that ri (q) denotes the traffic intensity as defined above. Now, the objective in Equation
(1) can be written as


X
X
X
Objm (q) =
Ai,m (q) · 
φij qij · Iij (qij ) =
fij,m (q)Iij (q).
(4)
i

j

i

For ease of notation, we omit the explicit dependence on m when clear from context.
The infinite-unit limit: The stationary distribution described above (for state-independent
pricing policies) holds for any finite m; moreover, it can also be used to obtain the limiting
distribution when the number of units tends to infinity. This infinite-unit limit is described in
detail in Section 3.7 in [Ser99] (and we provide more details in Appendix C). For the purposes of
our results, we rely on one particular fact, which we state in the proposition below. Recall first
that given p = {pij }, the quantities wi (p) and ri (p) are independent of m.
Proposition 2. Given a policy with quantiles q, in the infinite-unit limit, the steady-state
availability of each node i is given by ri (q)/ maxj rj (q); in particular, there exists at least one
node i with Ai (q) = 1.

7

C

C


1

1+
2

B
1

C




B
1

1


B

1

1

1

A

A

A

I

II

III

Figure 1: Example for non-concavity of throughput for finite units (m = 1, n = 3)
The existence of a node with availability 1 essentially captures the fact that in an infinite-unit
system, at least one node must have an infinite number of units. For a formal proof of this result,
cf. Section 3.7 in [Ser99].

2.4

Non-concavity of objective under state-independent pricing

Directly optimizing the finite-unit system is non-trivial as the objective function is not concave
in prices (or quantiles); we now demonstrate this in a simple network (m = 1 and n = 3), using
throughput as the objective. Our example is presented in Figure 1. The network comprises of
three nodes (A, B, C); the labels on the edges show the effective demand rate φij (q) with which
people wanting to move from node i to node j arrive for the corresponding pricing policies p
(and corresponding quantiles q). In particular, the first figure corresponds to setting all prices to
0 (quantiles to 1), while in the second and third figures, we increase the price between B and C
to set quantile qBC = (1 + )/2 in figure II, and qBC =  in figure III. Note that the demand in
network II is the average of the demands in networks I and III. To prove that this is non-concave
with respect to the demand rates we now demonstrate that the throughput in network II is
less than half of the sum of its value in networks I and III. To compute the throughput in
each network, note that the expected waiting time at a node is inversely proportional to the
total effective demand at each node. Furthermore, the unit makes exactly two rides between
consecutive visits to node B. Thus, the expected throughput is twice the expected rate of return
to node B. 5 The expected return-time to B in the three networks can be computed as 6
 
1 1
1 1
1 + 2
1
Network I : 1 · + · 1 + · =
=Ω
2 2
2 
2



 
1
2
1+ 1
5 + 1
1
Network II : 1 ·
1+ + 3 +  · 1 + 3 +  ·  =  · (3 + ) = Ω 
1+ 2




1
1

1
3
Network III : 1 ·
+
·1+
· =
= O(1).
1+
1+
1+

1+
Thus, the throughput in I and II is O(), whereas it is constant in III, so the throughput is
non-concave in the demand-rates (quantiles).
5
To see this, note that if the unit starts from node B, then the expected time for the first 2k rides (for any
positive integer k) is k times the expected return time to node B.
6
Notice that the total expected waiting time can be computed as the sum of the expected waiting time at B,
the probability of waiting at A times the expected waiting time at A (1), plus the probability of waiting at C
times the expected waiting time at C ().

8

3

Pricing via the Elevated Flow Relaxation

In this section, we present our algorithm for the pricing problem. Section 2.4 demonstrates that
the state-independent pricing problem is non-convex; moreover, this non-convexity appears in
both the objective and the constraints. We circumvent this via a novel convex relaxation, based
on two separate interventions, that alleviates the technical hurdles. Surprisingly, the resulting
pricing policy has strong performance guarantees even with respect to state-dependent policies,
as we prove in Section 4.

3.1

Elevated Objective Function

Recall from Equation (4) that our objective can be written as
X
Objm (q) =
(fij,m (q) · Iij (qij )).
i,j

Let qbij = fij,m (q)/φij = Ai,m (q) · qij ; note that qbij ≤ qij , and moreover, unlike the quantiles qij
which are in one-to-one correspondence to prices, there is no straightforward way to derive qbij
from prices. Since we assume that the per-ride rewards Iij (·) are non-increasing on the quantile
space, we have Iij (qij ) ≤ Iij (b
qij ). We now define the elevated objective function as
X
X
d q) =
Obj(b
φij qbij Iij (b
qij ) =
φij Rij (b
qij ).
(5)
i,j

i,j

The elevated objective has two useful properties: i) for all m and q, the elevated objective upper
d
bounds the true objective function, i.e. Obj(q)
≥ Objm (q), and ii) it is a concave function of qb
(since we focus on objectives corresponding to concave reward curves Rij (·)).

3.2

The Flow Polytope

We now turn our attention to the constraints of our pricing problem. As we discussed above, each
pricing policy (with corresponding quantiles q) realizes steady-state flows (steady-state rates of
units) fij,m (q) = Ai,m (q)φij qij . As before, we define the change of variables qbij = fij,m (q)/φij .
Note that while it is not the case that all flows obeying natural flow constraints can be realized
as steady-state flows {fij,m (q)} under some policy q, all realized flows do have to obey flow
conservation and capacity constraints. This motivates the following relaxation {b
qij } of the set of
possible steady-state flows under any policy q and for any number of units m.
A natural capacity constraint arises since prices only decrease demand; the steady-state flow of
units between a pair of nodes is thus bounded above by the rate of customers wanting to travel
between the nodes. We refer to this constraint as demand bounding. Formally, for every pair
(i, j), we have fij,m (q) ≤ φij and hence
qbij ∈ [0, 1].
Next, any steady-state flow must obey a natural flow conservation constraint, wherein the rate
of incoming units at each node must equal the rate of outgoing
units. We
P
P refer to this constraint
as supply circulation. Formally, at any node i, we have k fki,m (q) = j fij,m (q), and hence
X

φki qbki =

X
j

k

9

φij qbij .

Note that the above two constraints hold for every finite m and every q; 7 moreover, it is also
true for the infinite-unit limit (cf. Appendix C). We refer to the set of flows defined by the above
(linear) constraints as the flow polytope.

3.3

Pricing via the Elevated Flow Relaxation

Combining the elevated objective and the flow polytope, we obtain the elevated flow relaxation
program (cf. Algorithm 1). Note that this is a convex optimization problem since the objective
function is concave while the polytope is linear; hence it can be efficiently maximized.
Algorithm 1 The Elevated Flow Relaxation Program
Require: arrival rates φij , value distributions Fij , reward curves Rij .
1: Find {qij } that solves the following relaxation:
P
Maximize
φ R (b
q )
P
P(i,j) ij ij ij
φ
q
b
=
φ
q
b
∀i
k ki ki
j ij ij
qbij ∈ [0, 1]
∀ i, j.
2:

Output state-independent prices pij = Fij−1 (1 − qij ).

Note that the prices (quantiles) returned by Algorithm 1 impose the flow conservation not only
on the units (supply) but also on the customers (demand); we henceforth refer to this property
as demand circulation.

4

Main approximation guarantee

In this section, we prove the main approximation guarantee of the paper, which bounds the
performance of Algorithm 1 with respect to the optimal state-dependent pricing policy. This is
formalized in the following theorem
Theorem 3. Consider any objective function Objm for the m-unit system with concave reward
e be the pricing policy returned by Algorithm 1 and Optm be the value of the
curves Rij (·). Let p
objective function for the optimal state-dependent pricing policy in the m-unit system. Then
Objm (e
p) ≥

m
Optm .
m+n−1

(6)

Proof. The proof is based on the following three lemmas. First (Lemma 4), we show that the
objective of the optimal state-independent policy is upper bounded by the elevated objective
e returned by the Elevated Flow relaxation (Algorithm 1). Next (Lemma 5), we
of the policy p
e is equal to its objective in the infinite-unit system. Finally
show that the elevated objective of p
e ), the objective in the
(Lemma 6), we show that for any pricing policy (and so in particular for p
m
m-unit system is within a factor of m+n−1 of the objective in the infinite-unit system.
Lemma 4. For objectives with concave reward curves Rij (·), the value of the objective function
of the optimal state-dependent policy is upper bounded by the value of the elevated objective
e returned by Algorithm 1
function of the pricing policy p
d p) ≥ Optm .
Obj(e
7

Indeed, if it did not hold and the rate of incoming units to node i was larger than the rate of outgoing units
then after letting the system run in steady-state for long enough, the number of units in i would be larger than m.

10

e returned by
Lemma 5. The value of the elevated objective function of the pricing policy p
Algorithm 1 is equal to the value of its objective function in the infinite-unit system
d p).
Obj∞ (e
p) = Obj(e
Lemma 6. For any state-independent pricing policy p, the value of the objective of the policy p
in the m-unit system is at least m/(m + n − 1) times the value of the objective of the same policy
in the infinite-unit system.
Objm (p) ≥

m
Obj∞ (p).
m+n−1

In the remainder of this section, we prove these three lemmas.

4.1

From finite-unit state-dependent to the elevated flow relaxation

Lemma 7 (Lemma 4 restated). For objectives with concave reward curves Rij (·), the value of
the objective function of the optimal state-dependent policy is upper bounded by the value of the
e returned by Algorithm 1
elevated objective function of the pricing policy p
d p) ≥ Optm .
Obj(e
Proof. Our proof applies Jensen’s inequality to show that Optm is bounded above by the elevated
b that form a feasible solution of the elevated flow relaxation
objective value of some quantiles q
e maximizes this mathematical program, the lemma follows.
program. Since the pricing policy p
Let q? (X) denote the quantiles of the optimal state dependent policy and π ? (X) denote the
steady-state distribution it induces. Then Optm can be written as
X
X

?
π ? (X)
φij Rij qij
(X) .
i,j

X∈Sn,m

b via
We define q
qbij =

X

?
π ? (X)qij
(X).

X∈Sn,m

Since the price-setting reward curve is concave, Jensen’s inequality implies that
X
Optm ≤
φij Rij (b
qij ).
i,j
? (X) = 0 when X = 0. Therefore demand circulation and
Also, note that, by definition qij
i
demand bounding constraints of the elevated flow relaxation program are satisfied as convex
combinations of the state-dependent supply circulation and demand bounding properties.

b is a feasible solution to the elevated flow relaxation program and the result follows.
Hence q

4.2

From the elevated flow relaxation to infinite-unit state-independent

Lemma 8 (Lemma 5 restated). The value of the elevated objective function of the pricing policy
e returned by Algorithm 1 is equal to the value of its objective function in the infinite-unit system
p
d p).
Obj∞ (e
p) = Obj(e
11

e satisfies the demand circulation property since it is a feasible solution
Proof. The pricing policy p
to the elevated flow relaxation program. By Lemmas 9 and Proposition 2, the availabilities at all
nodes is equal to 1. This means that (i) the value of the objective function in the infinite-unit
e is equal to its elevated value (since no term was increased), and (ii) the
limit for pricing policy p
flow of customers on each edge is equal to φij qeij .
Lemma 9. For any m (including ∞) if state-independent quantiles q satisfies the demand
circulation property then, at all nodes i, the availabilities Ai,m (q) are equal.
Proof. Consider i∗ ∈ arg max Ai,m (q). Then the demand circulation and supply circulation
properties imply
X
X
X
Ai∗ ,m (q)
φji∗ qji∗ = Ai∗ ,m (q)
φ i∗ j qi∗ j =
Aj,m (q)φji∗ qji∗
j

P

j

j

i∗ ,



and thus j Ai∗ ,m (q) − Aj,m (q) φji∗ qji∗ = 0. By choice of
each summand is nonnegative, so
for each j such that φji∗ > 0 we obtain Aj,m (q) = Ai∗ ,m (q). All availabilities being equal then
follows inductively using connectivity of the underlying graph.

4.3

From finite-unit to infinite-unit state-independent

Lemma 10 (Lemma 6 restated). For any state-independent pricing policy p, the value of the
objective of the policy p in the m-unit system is at least m/(m + n − 1) times the value of the
objective of the same policy in the infinite-unit system.
m
Objm (p) ≥
Obj∞ (p).
m+n−1
Proof. By Lemma 11, we have:
Gm−1 (p)
Objm (p)
= rmax (p) ·
.
Obj∞ (p)
Gm (p)
In order to uniformly bound the above expression, the essential ingredient is the construction of
a particular weighted biregular graph between the states in Sn,m−1 and the states in Sn,m . In
this graph, non-zero edges only exist between neighboring states, i.e. between states y ∈ Sn,m−1
and y + ei ∈ Sn,m ; further, the total weight of edges incident to any state in Sn,m is equal to 1,
and the total weight of edges incident to any state in Sn,m−1 is equal to m+n−1
. We construct
m
such a graph in Lemma 12.
Throughout this proof, we use s for a state in Sn,m−1 and t for one in Sn,m . The weight of the
edge (s, t) in the bipartite graph constructed in Lemma 12 is denoted by ωst .
P
Qn
sj
Objm (p)
Gm−1 (p)
s∈Sn,m−1
j=1 (rj (p))
= rmax (p) ·
= rmax (p) P
Qn
tj
Obj∞ (p)
Gm (p)
t∈Sn,m
j=1 (rj (p))
P
Qn
sj
s∈Sn,m−1
j=1 (rj (p))
P
Q
= rmax (p) · P
n
tj
ω
st
t∈Sn,m
s∈Sn,m−1
j=1 (rj (p))
P
Qn
sj
s∈Sn,m−1
j=1 (rj (p))
= rmax (p) · P
Qn
sj +(tj −sj )
(s,t)∈Sn,m−1 ×Sn,m ωst
j=1 (rj (p))
P
Qn
sj
s∈Sn,m−1
j=1 (rj (p))


≥P
P
Qn
sj
s∈Sn,m−1
t∈Sn,m ωst
j=1 (rj (p))
P
Qn
sj
m
s∈Sn,m−1
j=1 (rj (p))
= m+n−1  P
Qn
sj =
m+n−1
s∈Sn,m−1
j=1 (rj (p))
m
12

P
P
The third equality holds as s ωst = 1, while the second-to-last follows from t ωst = m+n−1
.
m
Crucially, ωst > 0 only holds for neighboring states s and t, which implies the inequality.
Lemma 11. For any state-independent pricing policy p, let Am (p) = maxi (Ai,m (p)) denote
the maximum steady-state availability across all nodes. Then the objective function of p in the
m-unit system is related to the infinite-limit objective as
Objm (p)
Gm−1 (p)
= rmax (p) ·
= Am (p).
Obj∞ (p)
Gm (p)
P
Proof. Let Bi (p) = j φij qij · Iij (qij ) denote the contribution of node i to the objective per
unit of time in which station i is available. By substituting Ai,m (p) = (Gm−1 (p)/Gm (p)) · ri (p),
Ai,∞ (p) = ri (p)/rmax (p), and Bi into the definition of the objectives in Equation 4, we obtain8
P
Ai,m (p)Bi (p)
Objm (p)
= Pi
=
Obj∞ (p)
A
i i,∞ (p)Bi (p)

Gm−1 (p)
Gm (p)
1
rmax (p)

·

P

·

P

i ri (p)Bi (p)

i ri (p)Bi (p)

= rmax (p) ·

Gm−1 (p)
= Am (p),
Gm (p)

where the last equality follows from the characterization of the availabilities in Equation (3).
Lemma 12. We call y ∈ Sn,m−1 a neighbor of y + ei ∈ Sn,m ∀i. There exists a weighted biregular
graph on Sn,m−1 ∪Sn,m such that i) an edge has non-zero weight only if it is connecting neighboring
states, ii) for any vertex corresponding to a state in Sn,m−1 the total weight of incident edges
is equal to m+n−1
, and iii) for any vertex corresponding to a state in Sn,m the total weight of
m
incident edges is equal to 1.
Proof. Our construction is shown in figure 2. Each state x ∈ Sn,m is adjacent to x − ei ∈ Sn,m−1
for
i with xi > 0. On these edges, the weight is xmi . Thus, the total weight incident to x is
P all
xi
y∈S
is adjacent to the states y + ei ∀i ∈ [n].
i m = 1. On the other hand, each state
P +1 n,m−1
The respective weight on these edges is i yim
= m−1+n
. Finally, there is only weight on edges
m
between neighboring states. This concludes the proof of the lemma.

(a) Graph between S2,3 , S2,2 and S2,1

(b) Construction for general n, m

Figure 2: Construction of biregular graph between states in Sn,m and Sn,m−1 , as described in
Lemma 12. Fig. 2(a) shows the construction for (S2,3 ,S2,2 ) and (S2,2 , S2,1 ). Fig. 2(b) shows the
general construction. Note that the sum of weights of incident edges for any node on the left (i.e.
any state in Sn,m ) is 1, while it is (m + n − 1)/m for nodes on the right (i.e. states in Sn,m−1 ).
To prove Theorem 3 it suffices to show that Lemma 6 holds when p is a demand circulation.
This has been known since the 1980s [Whi84] and has been used in similar settings [WJ14].
However, in the next section (cf. Sections 5.1, 5.4) we consider scenarios under which no demand
circulation is optimal/feasible. For these, the stronger statement of Lemma 6 is required.
8

Note that this argument requires OBJ∞ (p) > 0 which is the case for all policies/settings we consider.

13

5

Extensions

In this section, we relax some restrictions we previously imposed. All of the algorithms and
proofs for these extensions make use of our elevated flow relaxation framework of Section 3,
demonstrating its generality. First, in Section 5.1, we allow the designer to have additional
rebalancing controls beyond pricing by redirecting supply and demand. Second, in Section 5.2,
we consider multi-objective settings where the goal is to maximize some objective subject to a
constraint on another. Next, in Section 5.3, we relax our assumption that changes in the state
should be instantaneous by allowing travel-times for the trips. For each of these results, the
proof follows from the three steps of Section 4; coincidentally, in each case, two steps are easily
extended whereas one is more evolved. Further, the more evolved lemma is different for the three
settings, hinting that each of the lemmas captures some inherent structure of the problem. Last,
in Section 5.4, we consider constrained settings where prices can only depend on the source and
where the prices should come from a discrete set.

5.1

Beyond pricing

Pricing is just one of several control levers in shared vehicle systems for balancing supply and
demand; we now investigate two other levers, which we refer to as supply redirection and demand
redirection, and show how they fit into our approximation framework. In the former we make a
decision at the end of every trip on whether the unit remains at the destination of the trip or
moves elsewhere whilst incurring a cost. In the latter, we redirect passengers arriving at a node
to take units from nearby nodes. 9
Supply Redirection
We consider a state-dependent policy r(X) which, for each trip ending at a node i, chooses to
redirect the unit to some other node j (leading to state X − ei + ej ), else allows the unit to stay
at i. For a state-independent policy, let rij ∈ [0, 1] be the probability that an arriving unit at i is
redirected to j. We assume that each redirection from i to j has associated cost cij , and that
units arriving empty (redirected) are not redirected again.
With m units, a fixed pricing policy p (with corresponding quantiles q), and a fixed redirection
policy r, we observe a rate fij,m (q, r) of customers traveling from i to j, and a rate of redirected
vehicles zij,m (q, r) from i to j, i.e. trips with destination i which are redirected to j. For a
state-independent policy, since each unit arriving at i is redirected to j with probability rij , it
holds that
X
zij,m (q, r) = rij
fki,m (q, r).
k

Similarly to the correspondence between qij and fij,m , we observe a correspondence between
rij and zij,m , wherein the former are the controls and induce the latter in the objective via the
steady-state dynamics. As a result, the objective can be written as
X
Objm (q, r) =
fij,m (q, r)Iij (q) − cij zij,m (q, r).
i,j
9

In practice, this is achieved by pulling units from nearby nodes; for example in ridesharing services, the
platform can dispatch a driver from a nearby node. Mathematically, the two are equivalent.

14

In order to define the constraints of the elevated flow relaxation, we write (as in Section 3)
qbij = fij,m (q, r)/φij and zbij = zij,m (q, r). We can now write the following relaxed flow polytope:
X
X
X
X
(1) qbij ∈ [0, 1],
(2)
(φki qbki + zbki ) =
(φij qbij + zbij ),
(3)
zbik ≤
φji qbji ∀ i.
j

k

k

j

The first constraint is demand bounding, exactly as explained in Section 3. The second is a
variant of the supply circulation in Section 3 to incorporate redirected vehicles. Finally, the third
reflects that only units that are dropping off customers at a node, but not empty ones, can be
redirected. Note that these constraints hold for any state-dependent policy as any policy induces
such rates fij,m and zij,m .
d
Using the reward curves Rij (·) defined in Section 3, we obtain an upper bound Obj(q,
r) on
our desired objective via the Elevated Flow Relaxation with the above constraints; through
this, we obtain prices and redirection probabilities in Algorithm 2. Note that the redirection
probabilities rij returned by the algorithm correspond to the rate of redirected units zijPreturned
by the relaxation over the total incoming rate of (non-empty) units at node i, i.e.
k φkj qkj .
We now derive the equivalent of Theorem 3 to bound the performance of this algorithm.
Theorem 13. Consider any objective function Objm for the m-unit system with concave reward
e and e
curves Rij (·). Let p
r be the pricing and redirection policies returned by Algorithm 2, and
Optm be the objective of the optimal state-dependent policies in the m-unit system. Then
Objm (e
p, e
r) ≥

m
Optm .
m+n−1

Algorithm 2 The Elevated Flow Relaxation Program with Supply Redirection
Require: arrival rates φij , value distributions Fij , reward curves Rij , rerouting costs cij .
1: Find {qij , zij } that solves the the following relaxation:
P
(φ R (b
q ) − cij zbij )
Maximize
Pi,j ij ij ij
(φ
q
b
+
zbij )
∀i
(φ
q
b
+
z
b
)
=
k ki kiP ki
Pj ij ij
bik ≤
bji
∀i
kz
j φji q
qbij ∈ [0, 1]
∀i, j

P

2:

−1
Output
P state-independent prices pij = Fij (1 − qij ) and redirection probabilities rij =
zij / k φki qki

Proof. The proof closely resembles that of Theorem 3. As before, we show the inequality
d p, e
d p, e
through three intermediate steps: (i) Obj(e
r) ≥ Optm , (ii) Obj(e
r) = Obj∞ (e
p, e
r), and (iii)
m
Objm (e
p, e
r) ≥ m+n−1 Obj∞ (e
p, e
r). The proof of the first inequality is the same as in Lemma 4,
with the relaxation defined in Algorithm 1 replaced by the relaxation defined in Algorithm 2.
The second step relies on Lemma 14, which uses Lemma 9 to prove that in the infinite-unit
system all availabilities are 1. Based on this claim, similarly to the proof of Lemma 5, we observe
that the flow of customers on each edge is φij qeij . The definition of the redirection probabilities in
Algorithm 2 then immediately implies that zij,∞ (e
p, e
r) = zij , i.e. the flow of redirected units from
i to j is also equal to the value of zij in the solution of the relaxation. Finally, for the third step,
we apply the same proof as in Lemma 6 with just one small modification. In Lemma 6, Bi (p)
denotes the contribution of node i per unit of time in which a unit is present at i. Previously, this
just captured rides leaving node i. Now, we also charge Bi (p) for the cost incurred through the
possible
redirection of
P
P vehicles traveling from i to j that are redirected to k. Replacing Bi (p) by
j φij qij (Iij (qij ) −
k rjk pjk ) formalizes this charging argument – the remainder of the proof is
equivalent to that of the Lemma 6. This concludes the proof of the theorem.
15

e and e
r as returned by Algorithm 2, all availabilities are equal to one in the
Lemma 14. With p
infinite-unit system.
e the quantiles corresponding to p
e . We consider a closed queueing network
Proof. Denote by q
e and e
with the same transition probabilities between states as the one resulting from q
r. In our
hypothetical network, quantiles are all one, there is no redirection, and the demand circulation
property holds. Since the hypothetical network does not have redirection and satisfies the
demand circulation property, Lemma 9 implies that there the availabilities at all nodes are equal.
However, the two networks have the same transition probabilities so they also have the same
steady-state distribution. As a result, in the original network all availabilities are also equal and
thus, equal to 1 in the infinite-unit limit. We define the demand in the hypothetical network as
X
X
φ̄ij = φij qeij (1 −
rejk ) +
φik qeik rekj .
k

k

e
e
Observe that transitions occur at the same rate in this network as in the
P one with
P q and r. Since
quantiles are equal to 1, the demand circulation property says that j φ̄ij = k φ̄ki . To show
this property, notice first that the demand at node i is
!
X
X
X
X
XX
X
φ̄ij =
φij qeij −
φij qeij
rejk +
φik qeik rekj =
φij qeij .
j

j

j

j

k

j

k

On the other hand, due to the definition of φ̄ij (first equality), the definition of reij in Algorithm 2
(third equality), and the supply circulation constraint in Algorithm 2 (last equality), the demand
of customers traveling to i is
X
X
X
X
φ̄ki =
φki qeki −
φki qeki reij +
φkj qekj reji
k

=

k

j,k

X

X

φki qeki −

j

k

j,k

reij

X

X
 X

φki qeki +
reji
φkj qekj
j

k

k

X
X
 X

z
z
P ij
P ji
φki qeki +
φkj qekj
=
φki qeki −
eki
ekj
k φki q
k φkj q
j
j
k
k
k
X
X
X
=
φki qeki +
(zji − zij ) =
φij qeij .
X

X

k

j

j

Demand Redirection
For the control defined in this section, we assume that there exists a graph G = (V, E) on the set
of nodes with edges between nodes that are so close that a customer arriving at one node can be
served through a vehicle at an adjacent node. We consider a state-dependent policy µ(X) which,
for each customer arriving at node i willing to pay the price quoted, decides from which node in
{i} ∪ {j : (i, j) ∈ E}, the customer is served. With m units, fixed quantiles q(X), and a fixed
matching policy µ(X), we observe a rate fij,m (q, µ) of customers arriving at i that travel to j,
potentially after being matched to a unit at k, and a rate zik,m (q, µ) of customers that arrived
to travel from i but
P have been matched to a unit at k. We can write the objective in this setting
as Objm (q, µ) = i,j fij,m (q, µ)Iij (q). We again write qbij = fij,m (q, r)/φij and zbij = zij,m (q, r)
to define the following relaxed flow polytope:
X
X
X
X
(1) qbij ∈ [0, 1],
(2)
qbki φki + zbik =
qbij φij + zbji ∀ i,
(3)
zbki ≤
qbji φji ∀ i.
k

j

k

16

j

The first constraint is again demand bounding. The second is a variant of the supply circulation
to incorporate matchings to nearby nodes. In particular, the left hand side accounts for the total
number of units arriving at node i, which equals all users arriving at i together with all units
arriving due to matching from nearby nodes k. Similarly, the right hand side accounts for the
total number of units leaving i, which are the users leaving from i together with users from other
nodes j that use supply at i. Finally, the third ensures that customers are matched only to units
arriving at nearby nodes. Maximizing the elevated objectives over these constraints again yields
a m/(m + n − 1) approximation algorithm. We omit the proof, because of its similarity to the
one of Theorem 13.
Algorithm 3 The Elevated Flow Relaxation Program With Matching
Require: arrival rates φij , value distributions Fij , reward-curves Rij , edges E.
1: Find {qij , zij } that solves the the following relaxation:
Maximize
(φ
bki + zbik )
k ki q
P
bki
kz
qbij
zbij

P

2:

=
≤
∈
=

P
φ R (b
q )
Pi,j ij ij ij
(φ
q
b
+
zbji )
Pj ij ij
bji
j φji q
[0, 1]
0

∀i ∈ [n]
∀i ∈ [n]
∀i, j ∈ [n]
∀(i, j) 6∈ E

−1
Output
P state-independent prices pij = Fij (1 − qij ) and matching probabilities µij =
zij / k φik qik

Theorem 15. Solving for the elevated objective under the constraints defined above yields a
m/(m + n − 1) approximation algorithm for pricing and matching.
In Appendix D we show that the results obtained in this section continue to hold in settings, in
which matching and/or redirecting is allowed, but pricing is not. In such scenarios, the optimal
solution may not have the demand circulation property. Nevertheless, the same techniques yield
m/(m + n − 1) approximation algorithms.

5.2

Multi-objective optimization

We now discuss how to derive bicriterion approximations in multi-objective optimization settings,
in which one objective is maximized subject to a lower bound on another. For ease of presentation,
we restrict ourselves to pricing. Formally, the problem is as follows: we are given a m-unit system,
a requirement c ≥ 0, and objectives Φm (·) and Ψm (·); the goal is to maximize Φm (q) subject
to Ψm (q) ≥ c. We again assume that both
n objectives
o
n can
o be decomposed into per-ride rewards
Ψ
Φ
with associated concave reward curves Rij and Rij .
b q) = P φij RΦ (b
Similarly to Equation (5), we first elevate both objectives to obtain Φ(b
ij qij ) and
i,j
P
Ψ
b
Ψ(b
q) = i,j φij Rij (b
qij ). Since per-ride rewards are non-increasing on the quantiles, this can only
increase the values of the objectives. We then impose the supply circulation and demand bounding
constraints to create the flow polytope constraints. This mathematical program (Algorithm 4) is
the elevated flow relaxation for our multi-objective setting; we argue below that this is indeed a
relaxation. It can be efficiently optimized since the objective is concave while the polytope is
b is concave.
convex: the convex combination of any two feasible quantiles is feasible since Ψ(·)
Theorem 16. Let Φm and Ψm be objectives for the m-unit system with concave reward curves.
e returned by Algorithm 4 is a (γ, γ) bicriterion approximation for the multiThen the solution q
objective pricing problem where γ = m/(m + n − 1), i.e. Φm (q? ) ≥ γOptm and Ψm (q? ) ≥ γ · c.

17

Algorithm 4 The Elevated Flow Relaxation for the Multi-objective Pricing Problem
Φ and RΨ , requirement c.
Require: arrival rates φij , value distributions Fij , reward curves Rij
ij
1: Find {qij } that solves the following relaxation:
b q)
Maximize
Φ(b
P
P
bki =
bij
k φki q
j φij q
qbij ∈ [0, 1]
b q) ≥ c
Ψ(b
2:

∀i
∀ i, j.

Output state-independent prices pij = Fij−1 (1 − qij ).

Proof. Let q0 denote the optimal solution of an auxiliary program where we only elevate objective
b subject to Ψm (·) ≥ c as well as the demand circulation and demand
Φ, i.e. we maximize Φ(·)
bounding constraints. Moreover, let q? denote the optimal solution of the original (non-elevated)
program. Then, for the first guarantee, we have:
b q) ≥ γ Φ(q
b 0 ) ≥ γ Φ(q
b ? ) ≥ γΦ(q? ) = γOptm
Φm (e
q) ≥ γ Φ(e
The first inequality is a simple application of Theorem 3. The second inequality holds since
any solution of the auxiliary program is a feasible solution of the elevated flow relaxation. In
b m (·) is pointwise no less than the original objective
particular, since the elevated objective Ψ
Ψm (·), the corresponding constraint in the auxiliary program is tighter. The third inequality
holds as q0 is the optimal solution for the auxiliary program. The last inequality holds as the
b is pointwise no less than the original objective Φ(·).
elevated objective Φ(·)
Regarding the second guarantee, we have:
b q) ≥ γc
Ψm (e
q) ≥ γ Ψ(e
e is
The first inequality is again a simple application of Theorem 3 while the second holds since q
a feasible solution of the elevated flow relaxation and therefore satisfies its last constraint.
We note that the same approach yields multicriterion approximation algorithms for settings in
which more than one constraint of the form Ψm (·) ≥ c is given.

5.3

Incorporating travel-times between nodes

We now discuss how to remove the assumption that units move instantaneously by adding
travel-times between nodes. We state our result only for pricing; however, our arguments below
only depend on properties of the Markov chain, and hence can incorporate the other controls we
consider.
A standard way to model travel-times is to assume that each unit takes an i.i.d. random time to
travel from node i to j. Formally, we expand the network state to X = {Xi (t), Xij (t)}, where
node queues Xi (t) track the number of available units at node i, and link queues Xij (t) track
the number of units in transition between nodes i and j. When a customer engages a unit to
travel from i to j, the state changes to X − ei + eij (i.e., Xi → Xi − 1 and Xij → Xij + 1). The
unit remains in transit for an i.i.d. random time, distributed exponentially 10 with mean τij .
When the unit reaches its destination, the state changes to X − eij + ej . Finally, we assume that
10

This is primarily for ease of notation; our results extend if the travel time is distributed according to some
general Gij (·).

18

pricing policies and passenger-side dynamics remain the same as before; in particular, we assume
that the demand characteristics {φij , Fij } and reward-functions {Iij } are independent of the
actual transit times (dependence on average transit times τij can be embedded in the functions).
The system described above is a generalization of the Gordon-Newell network (Definition 1)
referred to as a BCMP network (introduced by [BCMP75]; cf. [Ser99], Section 3.3; also see
[ZP16] for the use of such a model for vehicle sharing). It is also a special case of a closed
migration process; our presentation here follows Kelly and Yudovina [KY14] (Chapter 2).
Definition 17. A closed migration process on states Sn2 ,m is a continuous-time Markov chain
in which transitions from state X to state X − ei + ej occur at rate
P λij µi (Xi ) when Xi > 0 and at
rate 0 otherwise. The λij again form routing probabilities with k λik = 1, λij ≥ 0 ∀i, j. Notice
that µi (Xi ) is a function of Xi only, whereas λij are independent of the state alltogether.
Given P
quantiles q, the above-described process is a closed migration process with
P λi,ij =
φij qij / k φik qik and λij,j = 1 for every i and j. Further, the service rate µi (Xi ) = k φik qik
when Xi > 0 for node queues and µij (Xij ) = Xij /τij for link queues. Intuitively, the latter
captures the idea that each of the Xij units has an exponential rate of 1/τij and therefore the
rate until the first is removed from the link queue is Xij /τij . The stationary distribution can
then be obtained as follows.
Theorem 18 (Theorem 2.4 in [KY14]). For a closed migration process as described in Definition
17, let {wi }i∈[n2 ] denote the invariant distribution associated with the routing probability matrix
{λij }i,j∈[n] . Then the equilibrium distribution for a closed migration process is
2

n
w xi
1 Y
Q xi i
,
π(x) =
Gm
y=1 φi (y)
i=1

where Gm =

P Qn2
x

i=1

x

w i
Qxi i
y=1 φi (y)

is a normalizing constant.

This implies for our setting, with w denoting again the invariant distribution of the routing
matrix11

πx,m (q) =

1 
Gm (q)

Y

i∈[n]

w (q)
P i
k φik qik

xi




Y (τij wij (q))xij

.
x
!
ij
2

(7)

i,j∈[n]

One consequence of the above characterization is that the resulting flows fij,m (q) continue to
satisfy demand bounding and supply circulation – consequently, the Elevated Flow Relaxation (cf.
Algorithm 1) continues to provide an upper bound. Moreover, adding link queues does not affect
the optimization problems we consider in the infinite-unit system; in particular, Lemma 5 also
continues to hold in this setting. Finally, from Lemma 11, we know that the ratio of objectives
between the infinite-unit system and the finite-unit system equals the maximum availability,
Objm (q)
among all nodes, in the finite-unit system, i.e. Obj
= maxi Ai,m (q). In order to obtain an
∞ (q)
approximation ratio, we now need to understand how maxi Ai,m (q) changes when link queues
are added.
Let M denote the random variable corresponding to the steady-state number of available

(i.e. not in transit) units across all nodes, and define Am (q|M ) , maxi∈[n] P 1{Xi >0} |M ,
Am (q) = maxi∈[n] Ai,m (q). Now we have the following
Lemma 19. Conditioned on M , the distribution of {Xi }i∈[n] in the network with travel-times is
identical to an n-node M -unit Gordon-Newell network with the same quantiles and arrival rates.
11

wiD

In comparison to the invariant distribution wI when rides occur instantaneously, wD with delays would be

D
= wiI /2 for node queues and wij
=

wD φ q
Pi ij ij
k φik qik

for link queues.

19

This follows directly from the product-form nature of the steady-state distribution in Equation (7).
Using this, we now obtain the following bound for the m-unit system availability.
Lemma
20. For any p
network with parameters {φij , Fij (·), τij } if m ≥ 100 and quantiles q satisfy
P
φ
τ
q
≤
m
−
2
m ln(m) then
ij ij ij ij

Am (q) ≥

3
1− √
m



!
√
m ln m
√
.
m ln m + n − 1

Note that the above converges to 1 as m → ∞.
Proof. First, for any given policy q, as before we have the realized flows fij,m (q) = qij φij Ai,m (q);
moreover, this is the expected rate of units entering link queue Xij . Let D = m − M be the
number of units which are in transit. Now, by Little’s law
P (cf. [Kel11] or [Ser99]), we have that
the expected number of units in link queues is given by i,j Ai,m (q)φij qij τij .
Note that the link queues {Xij } are stochastically dominated by independent M/M/∞ queues
with input rate φij qij and average transition time τij . This follows from a simple coupling
argument, where incoming customers follow an independent Poisson process of rate φij qij and
enter the link queue with a virtual unit, irrespective of whether the customer
engages a unit or
e = P oi(P φij qij τij ). Further,
not in the real system. Thus D is stochastically dominated by D
i,j
b
e m}.
since D is bounded above by m, D is also stochastically dominated by D = min{D,
Next, from Lemma 19, we know that conditioned on there being M available units in the steadystate system, the distribution of units in node queues is identical to that of an n-node M -unit
Gordon-Newell network; moreover, from Lemma 6, we have that for any n-node, m-unit GordonNewell network, Am (q|M ) ≥ M/(M + n − 1). Since M = m − D and (m − x)/(m + n − 1 − x)
is decreasing in x for x ≤ m, it follows that
"
#


b
m−D
m−D
.
(8)
≥E
Am (q) ≥ E
b
m+n−1−D
m+n−1−D






q
q
ln m
ln m
b
e
b
Further, by definition of D we observe that P D > m 1 −
=P D >m 1−
.
m
m
e (cf. from
We can now apply a standard Chernoff bound for the Poisson
D
p random variable
P
e
Lemma 35 in Appendix F), using the assumption that m − 2 m ln(m) ≥ ij φij τij qij = E[D].

20




q
ln m
b
In particular, we may bound P D > m 1 −
by
m
"
e >m 1−
P D

r

ln m
m

!#



√
−m ln m m − 3 m ln m

√
≤ exp
2(m − 2 m ln m)2




p
− ln m · 1 − 3 ln m/m

 
= exp 
p
p
2 1 − 4 ln m/m 1 − ln m/m



p
− ln m 1 − 3 ln m/m
 
≤ exp 
p
2 1 − 1.5 ln m/m



p
3 ln m/m
− ln m 
 
= exp
1− 
p
2
2 − 3 ln m/m


(9)

(10)

√
(Since ln m/m ≤ 1/e, and 4 · (1 − 1/ e) > 1.5)
!
1
3
3 ln m
= √ exp p
≤√
for m ≥ 100.
m
m
4 m/ ln m − 6
We can use the above to bound the availability in Inequality (8) as
!
√


m − (m − m ln m)
3
3
√
+ √ · 0.
Am (q) ≥ 1 − √
m
m
m − (m − m ln m) + n − 1
Simplifying, we obtain the result.
We are now ready to extend our pricing/control policies to the setting with transit delays. In
order to do so, we need to first extend the elevated flow relaxation by adding an extra constraint.
The main observation is that in an m-unit system with transit delays, there is an additional
conservation constraint induced by the fact that the number of units in the link queue can not
exceed m. As before, let fijm (q) = qbij φij denote the expected rate of units entering link queue
Xij ; then by Little’s law (cf.
P [Kel11] or [Ser99]), we have that the expected number of units
in link queues is given by i,j φij qbij τij , which, in an m-unit system, must be bounded by m.
To incorporate this, we need to addPan additional rate-limiting constraint to the elevated flow
relaxation wherein we ensure that i,j φij qbij τij ≤ m. This gives us the Rate-Limited Elevated
Flow Relaxation Program in Algorithm 5.
Algorithm 5 The Rate-Limited Elevated Flow Relaxation Program
Require: arrival rates φij , value distributions Fij , reward curves Rij , scaling parameter εm ,
travel-times τij .
1: Find {qij } that solves the following relaxation:
P
Maximize
φ R (b
q )
P
P(i,j) ij ij ij
φ qb =
bij
∀i
j φij q
P k ki ki
bij ≤ m
i,j φij τij q
qbij ∈ [0, 1]
∀ i, j.
2:
3:

Set qeij = qij · (1 − εm )
Output state-independent prices peij = Fij−1 (1 − qeij ).

21

Theorem 21. For any objective function Objm with concave reward curves
p Rij (·) in the m-unit
e be the output of Algorithm 5 with input εm := 2 ln m/m, Optm be the
system, let quantiles q
value of the objective function for the optimal state-dependent pricing policy, and m ≥ 100. Then
!
√
Objm (e
q)
m ln m
3
≥ (1 − εm ) √
−√
.
Optm
m ln m + n − 1
m ln m
Proof. The proof follows a similar roadmap as that of Theorem 3. In particular, we argue that
1. the rate-limited elevated flow relaxation provides an upper bound for any state-dependent
policy,
2. the rate-limited elevated flow relaxation solution is achieved by a state-independent policy
in the infinite-unit system, and
3. the ratio of the performance of any state-independent policy q in the infinite-unit and
m-unit system is equal to the maximum availability Am (q).
First, similar to Lemma 4, note that since the realized flows in the m unit system must obey the
conservation laws encoded by the rate-limited elevated flow relaxation,
hence Optm is bounded
P
by the solution to the rate-limited elevated flow relaxation (i,j) φij Rij (qij ). Moreover, since
per-ride rewards Iij (·) are non-increasing in q, therefore scaling the qij by (1 − εm ) results in an
elevated objective value that obeys
X
X
(1 − εm )
φij Rij (qij ) ≤
φij Rij (e
qij ),
(i,j)

(i,j)

P

and moreover, i,j φij qeij τij ≤ m · (1 − εm ). Now, using similar arguments as in Lemma 5, we
e
q) =
can
P show that using a state-independent policy q in the infinite-unit limit gives Obj∞ (e
e as derived from the m unit rate-limited elevated
qij ) (note that we use the same q
(i,j) φij Rij (e
flow relaxation in the infinite
unit
limit;
in
other
words, we scale the number of units to infinite,
P
but retain the constraint i,j φij τij qbij ≤ m for a fixed m). Next, from Lemma 11, we get that
Objm (e
q) = Am (e
q)Obj∞ (e
q). Finally, using Lemma 20, we get the desired bound
!
√
Objm (e
q)
m ln m
3
≥ (1 − εm ) √
.
−√
Optm
m
m ln m + n − 1

Note that for any fixed n, the theorem shows that the policy returned by the rate-limited elevated
flow relaxation is asymptotically optimal as m → ∞ for any demand rates and transit delays
{φij , τij }. In Appendix D we use this to recover and give a finite-m characterization for the
asymptotic results in [BDLY16, OW16].

5.4

Constrained point pricing

In this section, we focus on a special case of the vanilla pricing problem wherein the platform is
only allowed to set point prices, i.e. prices based on the origin node, and the value distributions of
all customers arriving at a node are identical (i.e. pij = pi , respectively qij = qi , and Fij (·) = Fi (·)
for all i, j). We provide a simple optimal pricing policy for the infinite-unit system, which involves
just one eigenvector computation (for throughput/social welfare) or a concave maximization over
a single variable (for revenue).
We then consider the additional constraint that prices are only allowed to come from a discrete
price set. Using our infinite-to-finite unit reduction, all our results are then translated back to
22

the finite unit setting. We emphasize that in the latter restricted settings, there may not be a
feasible solution satisfying demand circulation.
Unrestricted price set: We begin by providing the point pricing equivalent to Algorithm 1
and Theorem 3.
Algorithm 6 The Point Pricing Elevated Flow Relaxation Program
Require: arrival rates φij , value distributions Fi , reward curves Rij .
1: Find {qi } that solves the following point price relaxation:
P
Maximize
φ R (b
q)
P
P(i,j) ij ij i
bk =
bi
∀i
j φij q
k φki q
qbi ∈ [0, 1]
∀ i.
2:

Output state-independent prices pi = Fi−1 (1 − qi ).

Theorem 22. Consider any objective function Objm for the m-unit system with concave reward
e be the pricing policy returned by Algorithm 6, Optm be the value of the
curves Rij (·). Let p
objective function for the optimal state-dependent point pricing policy in the m-unit system. Then
Objm (e
p) ≥

m
Optm
m+n−1

(11)

Proof. The proof is again based on three steps that compare Objm (e
p) with Obj∞ (e
p), Obj∞ (e
p)
d
d
d
with Obj(e
p), and Obj(e
p) with Optm . The application of Jensen’s inequality to prove Obj(e
p) ≥
Optm is the same as in Lemma 4, with the polytope in Algorithm 1 replaced by the one in
e fulfilling the demand circulation
Algorithm 6. Lemma 5 applies since its proof only relies on p
d p). Finally, Lemma 6 implies
p) ≥ Obj(e
property, which it does (cf. Algorithm 6). Thus, Obj∞ (e
m
p), which concludes the proof of the theorem.
that Objm (e
p) ≥ m+n−1 Obj∞ (e
Notice that the optimization problem in Algorithm 6 has the demand circulation property as
a constraint; thus, with the resulting pricing policy, the availability is equal at every node (cf.
Lemma 9). Recall from Section 2.3 that the availability at each node in the infinite-unit system
depends on the traffic intensity at that particular node and the maximum traffic intensity among
all nodes. Further, the traffic intensity at each node
P i depends on (i) the ith coordinate of the
eigenvector
w(q) of the routing matrix {φijP(qi )/ k φik (qi )}i,j∈[n]2 , and (ii) the rate of arrivals
P
φ
at
i.
In particular, ri (q) = wi (q)/ j φij qij . In the setting
k ik
P of point prices
P however, w
is unaffected by the prices and ri (q) = rj (q)∀i, j implies that wi k φjk qj = wj k φik qi for all
i, j. Substituting in the optimization problem for every j
P
P
qj = wj k φik qi /wi k φjk ,
we find that the convex optimization problem can actually be written in just one variable. Further,
in the case of social welfare, and revenue, it is always the case that maxi qi = 1 for an optimal
solution in the infinite-unit system. Hence, in these cases only one eigenvector computation is
needed.
Discrete price set: We now show how the pricing policy from Algorithm 6 can be modified
when there is a discrete set of available prices for each node. We handle this case with an extra
loss in the objective that depends on how well the prices represent each part of the distribution. In
b by solving for the unconstrained case as in Algorithm 6
particular, we obtain the pricing policy p

23

to obtain prices p and then setting each pbi to be the lowest available price greater or equal to pi .
b.
We now prove the performance
guarantee for p
n
o
ki
1
Theorem 23. Let pi , . . . , pi
be the set of available prices for node i in increasing order,
n
o
b be defined as above.
qi1 , . . . , qiki be the corresponding quantiles (in decreasing order), and p, p
Suppose that for all i there exists an available price p`i such that qi` ≤ qi , and that there exists α
such that for all i and all s, α · qis ≥ qis+1 . Then,
αObjm (b
p) ≥

m
Optm ,
m+n−1

where Optm is the objective of the optimal state-dependent policy for discrete prices in the m-unit
system.
d
Proof. Since Obj(p)
is an upper bound on the unrestricted point pricing problem (cf. Theorem
d
22), it is also an upper bound on Optm . Lemma 5 implies that Obj(p)
= Obj∞ (p), since p
fulfills the demand circulation property (cf. Algorithm 6). Further, by Lemma 6, Objm (b
p) ≥
m
Obj
p
p
(b
).
Thus,
what
remains
is
to
bound
Obj
(b
)
with
respect
to
Obj
(p).
Since
∞
∞
∞
m+n−1
qbi ≤ qi for all i and the per-ride rewards Iij (·) are assumed to be non-decreasing in the quantiles,
we only need to bound the changes in the availabilities of the infinite-unit system for each i.
Since the wi are constant under point-pricing, the availabilities are only affected by prices in the
denominator, where the change is equal to qbi /qi . Thus, no traffic intensity changes by more than
a factor of α and the result follows.
The assumption that the value distributions at each node are identical may seem too restrictive.
Notice though that the same analysis also applies to the following setting: for each i, j there
exists a base price dij (e.g., based on geographic distance). This price is multiplied by the
(state-dependent) control pi , which is the same for all j. The behavioral assumption is now that
customers react the same way to the control, regardless of their destination.

6

Conclusions

We have studied pricing and optimization in shared vehicle systems for various objectives. Our
work parallels existing work through our use of a closed-queueing network model to capture
network externalities. It distinguishes itself, however, through the rigorous guarantees in finite
settings and the generality of controls/objectives considered. In that sense, it unifies and extends
several results from the literature. In particular, our main technical contribution (the elevated
flow relaxation), has the potential to apply to other settings. Given the widespread use of fluid
limits in the queuing theory literature, our framework may yield provable guarantees for finite
instances in these settings as well.
Further, it would be interesting to study how our framework can be extended to constrained
settings beyond multi-objective and discrete prices. For instance, in recent events, Uber was
exposed to bad publicity when turning off surge pricing for trips originating at JFK airport.
While the details of these events are not mathematical in nature, it demonstrates the significance
of studying settings where prices (in some locations) are bounded above. Additionally, our
pricing policies do not impose triangle inequality, potentially creating incentives for customers to
reach their destination via an extra stop. Addressing such strategic considerations opens up an
intriguing avenue for future research.
Finally, although our work suggests that state-independent prices have strong performance, this is
under the steady-state assumption with complete knowledge of the system parameters. Relaxing
either of these assumptions is a compelling extension of our work.
24

Acknowledgements
The authors would like to thank David Shmoys and Éva Tardos for their support and their
fruitful feedback throughout this work. The authors also thank Anton Braverman and Jim Dai
for many useful conversations.

References
[Ade07]

Daniel Adelman. Price-directed control of a closed logistics queueing network. Operations Research, 55(6):1022–1038, 2007.

[BCMP75] Forest Baskett, K Mani Chandy, Richard R Muntz, and Fernando G Palacios. Open,
closed, and mixed networks of queues with different classes of customers. Journal of
the ACM (JACM), 22(2):248–260, 1975.
[BDLY16] Anton Braverman, JG Dai, Xin Liu, and Lei Ying. Empty-car routing in ridesharing
systems. arXiv preprint arXiv:1609.07219, 2016.
[BKM13]

James D. Brooks, Koushik Kar, and David Mendonça. Dynamic allocation of entities
in closed queueing networks: An application to debris removal. In Proceedings of the
2013 IEEE International Conference on Technologies for Homeland Security, pages
504–510, 2013.

[Buz73]

Jeffrey P Buzen. Computational algorithms for closed queueing networks with
exponential servers. Communications of the ACM, 16(9):527–531, 1973.

[CY13]

Hong Chen and David D Yao. Fundamentals of queueing networks: Performance,
asymptotics, and optimization, volume 46. Springer Science & Business Media, 2013.

[Geo12]

David K George. Stochastic Modeling and Decentralized Control Policies for LargeScale Vehicle Sharing Systems via Closed Queueing Networks. PhD thesis, The Ohio
State University, 2012.

[GN67]

William J Gordon and Gordon F Newell. Closed queuing systems with exponential
servers. Operations research, 15(2):254–265, 1967.

[GXS12]

David K George, Cathy H Xia, and Mark S Squillante. Exact-order asymptotic
analysis for closed queueing networks. Journal of Applied Probability, pages 503–520,
2012.

[Har14]

Jason D Hartline. Mechanism Design and Approximation. 2014.

[HMW09] Robert C Hampshire, William A Massey, and Qiong Wang. Dynamic pricing to
control loss systems with quality of service targets. Probability in the Engineering
and Informational Sciences, 23(02):357–383, 2009.
[Jac63]

James R Jackson. Jobshop-like queueing systems. Management science, 10(1):131–142,
1963.

[Kat16]

Miranda Katz.
Help Citi Bike Rebalance Its Docks And You Can Ride
For Free. http://gothamist.com/2016/05/14/help_citi_bike_rebalance_its_
docks.php, 2016.

[Kel11]

Frank P Kelly. Reversibility and Stochastic Networks. Cambridge University Press,
2011.

25

[KY14]

Frank Kelly and Elena Yudovina. Stochastic networks, volume 2. Cambridge University Press, 2014.

[LR10]

Retsef Levi and Ana Radovanovic. Provably near-optimal lp-based policies for revenue
management in systems with reusable resources. Operations Research, 58(2):503–507,
2010.

[MS14]

Paul Milgrom and Ilya Segal. Deferred-acceptance auctions and radio spectrum
reallocation. In Proceedings of the fifteenth ACM conference on Economics and
computation, pages 185–186. ACM, 2014.

[OW16]

Erhun Ozkan and Amy R Ward. Dynamic matching for real-time ridesharing. 2016.

[Ram27]

Frank P Ramsey. A contribution to the theory of taxation. The Economic Journal,
37(145):47–61, 1927.

[RL80]

Martin Reiser and Stephen S Lavenberg. Mean-value analysis of closed multichain
queuing networks. Journal of the ACM (JACM), 27(2):313–322, 1980.

[Ser99]

Richard Serfozo. Introduction to stochastic networks, 1999.

[Whi84]

Ward Whitt. Open and closed models for networks of queues. AT&T Bell Laboratories
Technical Journal, 63(9):1911–1979, 1984.

[Whi85]

Peter Whittle. Scheduling and characterization problems for stochastic networks.
Journal of the Royal Statistical Society. Series B (Methodological), pages 407–428,
1985.

[WJ14]

Ariel Waserhole and Vincent Jost. Pricing in vehicle sharing systems: optimization
in queuing networks with product forms. EURO Journal on Transportation and
Logistics, pages 1–28, 2014.

[ZP16]

Rick Zhang and Marco Pavone. Control of robotic mobility-on-demand systems: a
queueing-theoretical perspective. The International Journal of Robotics Research,
35(1-3):186–203, 2016.

26

A

Irreducibility of the Priced System

We justify here our assumption from Section 2 that the infinite-unit solutions we obtain induce a
connected graph; to do so, we first need to assume that the graph created by edges (i, j) on which
φij > 0 is strongly connected. We then prove that given any solution to the infinite-unit pricing
problem, there exists a solution with arbitrarily close objective that also induces a connected
graph. Throughout this section we work with the flow fij,∞ (p) induced by the demands in the
infinite-unit system, but suppress all dependencies on ∞ in the notation.
Theorem 24. Let  > 0. For any non-decreasing objective and any pricing policy p that induces
a supply circulation fij on k components in the infinite-unit system, there exists a policy p0
inducing a supply circulation fij0 in the infinite-unit system such that the graph with edge-set
E = {(i, j) : fij0 > 0} is strongly connected and the objective with p0 is at least (1 − ) times that
of p.
Proof. To prove the theorem we repeatedly add flow to edges (i, j) with fij = 0, but also take
flow away from edges (ī, j̄) with fīj̄ > 0. To ensure that edges of the second kind do not have
their flow reduced by too much, we set



δ = × min min{fij : fij > 0}, min{φij : φij > 0} .
i,j
i,j
k
Whenever we decrease flow on an edge, this is done by an additive δ amount. Reducing flow at
most k times to obtain fij0 we guarantee that fij0 ≥ (1 − )fij holds.
As we assume our underlying graph with edge-set {(i, j) : φij > 0} to be strongly connected, it
must be the case that there exists a minimal sequence of components C1 , C2 , . . . , Cd = C1 , d > 2,
and nodes u` , v` ∈ C` such that λu` v`+1 > 0, but fu` v`+1 = 0. In particular, it being minimal
implies that no component other than the first appears repeatedly.
Since each u` , v` are in the same strongly connected component of the graph with edge-set E, we
know that for each ` there exists a simple path from u` to v` with positive flow on it. We change
flows as follows: for all pairs (u` , v`+1 ) we increase flow by δ and for each edge along the path
from u` to v` we decrease flow by δ. At all other edges the flow remains unchanged.
We need to first argue that the new circulation is feasible. Each node along a path within a
component has its in-flow and out-flow reduced by δ, whereas at the nodes ui , vi both the sum of
in-flows and the sum of out-flows has remained the same. At all other nodes, nothing is altered.
Thus, flow conservation continues to hold. By choice of δ none of the edge-capacities are violated.
Thus, the resulting flow is a circulation with at most k − 1 distinct components. Applying this
procedure k − 1 times, we obtain a single strongly connected component.
Finally, since Iij (·) are nondecreasing with price and decreasing flow is equivalent to increasing
prices, the choice of δ guarantees that the objective on paths from u` to v` has been reduced by
at most a factor of (1 − ). Since Iij (·) are non-negative, the additional flow on edges from u` to
v`+1 only increases the total objective. Thus, the pricing policy p0 that induces the circulation
fij0 has the desired properties.

B

Concave Reward Curves

In this section, we investigate conditions under which throughput, social welfare and revenue
satisfy the conditions of theorem 3. In particular, we first show that the respective reward curves
R(q) = qI(q) are concave. We then prove that the concave reward curves assumption implies the
non-increasing (quantiles) per-ride rewards assumption.
27

Lemma 25. Revenue (i) satisfies the assumptions of Theorem 3 under regular value distributions,
Throughput (ii) and Social Welfare (iii) satisfy the assumptions under any value distribution.
Proof. We drop the subscripts throughout this proof to simplify notation. We begin by considering
(i) revenue, for which the result holds due to the fact that the reward curve is concave if and only if
the distribution is regular (cf. Proposition 3.10 in [Har14]). For (ii) throughput, R(q) = q·I(q) = q
is a linear function of q for any value distribution and thus concave.
f (y)
Lastly, for (iii) social welfare, we use the so-called hazard rate h(y) = 1−F
(y) of a distribution
F with density f . Given F , denote by p(q) and q(p) a price as a function of its corresponding
quantile and vice-versa. Then, by the definition of hazard rate:
!
Z
p(q)

q(p) = exp −

h(y)dy

(12)

0

Taking logarithms and differentiating, we obtain:
−

1
dp(q)
= h(p(q))
q(p)
dq

(13)

Hence, as R(q(p)) = q(p) · I(q(p)) and f (p) = (1 − F (p))h(p) = q(p)h(p) we have
 Z v

Z ∞
Z ∞
R(q) =
vf (v)dv =
vh(v) exp −
h(y)dy dv
p(q)

The first derivative

dR(q)
dq

p(q)

0

of R(q) is equal to
Z

!

p(q)

−p(q)h(p(q)) exp −

h(y)dy
y=0

dp(q)
=
dq


 R
p(q)
p(q) exp − y=0 h(y)dy
q(p)

= p(q),

where the first equality comes from Equation (13), the second from (12).
The second derivative is then given by
d2 R(q)
dp(q)
1
1 − F (p(q))
=
=−
=−
< 0,
2
dq
dq
qh(p(q))
f (p(q))q(p)
which concludes the proof of the Lemma.
Lemma 26. If some objective satisfies the concave reward curves assumption, it also satisfies
the non-increasing (in quantiles) per-ride rewards assumption.
Proof. Suppose an objective has concave reward curves, but does not have non-increasing
(in quantiles) per-ride reards. Then there must exist i, j, q1 , q2 with 0 < q1 < q2 such that
Iij (q1 ) < Iij (q2 ). Let A = qq12 . Then
q1 Iij (q2 ) = A · q2 Iij (q2 ) = A · q2 Iij (q2 ) + (1 − A) · 0 · Iij (0)
≤ (A · q2 + (1 − A) · 0)I(A · q2 + (1 − A) · 0) = q1 Iij (q1 ),
where the inequality follows from Jensen’s inequality on since the rewards curve qIij (q) is a
concave function. As q1 > 0, it follows that Iij (q2 ) ≤ Iij (q1 ) and we therefore arrive at a
contradiction.

28

C

Infinite-unit Limit

In Section 2.1 we briefly introduced the infinite-unit limit of the Gordon-Newell network, i.e.,
the characterization of the limiting Markov chain wherein we keep all system parameters
(φij , Fij , etc.) constant, and scale m → ∞. We also mentioned that the primary result we
use from this characterization is that the steady-state availability of each node i is given by
Ai i, ∞(p) = ri (p)/ maxj rj (p), and that there exists at least one node i with Ai,∞ (p) = 1 (cf.
Proposition 2). We now describe this limit in a little more detail. Our presentation follows
closely that of [Ser99], Section 3.7, which we refer the reader to for more details.
Recall first that given p = {pij }, we can compute quantities wi (p) and ri (p), which are
independent of m. We define rmax = maxi ri (p) and rbi (p) = ri (p)/rmax . We also define
J = {i ∈ [n] | rbi (p) = 1} to be the set of bottleneck nodes in the network (note that J has at least
one element), and K = [n]\J be the remaining nodes. Then as m → ∞, the stationary distribution
of the m-unit system (as specified in Equation (2)) converges to a limiting distribution 12 as
m → ∞, with the following properties:
• The bottleneck nodes, i.e., nodes in set J with rbi (p) = 1, all have Ai (p) = 1.
• The bottleneck nodes feed the non-bottleneck nodes in set K, which together form an open
Jackson network, with each node behaving as a stable M/M/1 queue.
• For all i ∈ K, we have Ai (p) = rbi (p) < 1.
The above description has the following physical interpretation: in the infinite-unit limit, the
bottleneck nodes have an infinite queue of units, and hence always have availability 1. Moreover,
the rate of units traveling from one of these nodes i to a non-bottleneck node j is exactly φij (p).
Thus from the perspective of a non-bottleneck node j, it appears as if a steady-stream of units
(with total rate < φj (p)) arrive from (and depart to), an external node; the number of units in
node j therefore behaves according to the dynamics of a stable M/M/1 queue.
Lemma 27. The objective of the elevated flow relaxation for the policy returned by Algorithm 1
upper bounds the objective of any state-independent policy p in the infinite-unit system.
Proof. This follows if we show that the flows in the infinite-unit limit satisfy supply circulation
and demand bounding. The latter is clear from the dynamics of the system (the flow out of a
node can not exceed the rate of arriving customers). To see that the former follows from the
above listed properties, note that wi (p) is defined to be the leading left eigenvector of {λij (p)}i,j ,
where λij (p) = φij (p)/φi (p). From this we get for all i:
!
X φji (p)
X φik (p)
X
X
wj
= wi = wi
⇒
rj (p)φji (p) =
ri (p)φik (p)
φj (p)
φi (p)
j

j

k

k

P

P
Dividing both sides by rmax (p) we get that for all nodes i, we have j rbj (p)φji (p) = k rbi (p)φik (p).
However, as we noted above, Ai,∞ (p) = rbi (p), and hence fij∞ (p) = rbi (p)φij (p). Thus the fij∞ (p)
satisfy flow conservation.
Combining with Lemma 5, we get that the elevated flow relaxation solution is tight in the
infinite-unit limit.
Lemma 28. The objective of the elevated flow relaxation for the policy returned by Algorithm 1
is equal to the objective of the optimal state-independent policy in the infinite-unit system.
12

For the specific technical sense in which the steady-state distributions converge to the limit, cf. [Ser99]

29

D

Settings without Prices

In Section 5.1 we discussed how two control levers, redirection of supply and of demand, can be
combined with pricing to obtain the same guarantees we obtain for the pure pricing problem.
We now show that our technique extends to settings in which only redirection of supply/demand
is allowed, but pricing is not. Because demand cannot be modulated in these settings, one
may assume that Iij is constant for each i and j, because Iij is not a function of prices. Thus,
the elevated objective, defined analogously to Section 3, is always equal to the objective now.
Further, the interpretation of our results changes slightly.
Similarly to Algorithm 6, we introduce quantiles qi ; unlike Section 5.4 however, we cannot change
prices to modulate demand according to these quantiles. We adopt the same notation as in
Section 5.1, with the exception that we do not allow for pricing policies and thus everything is just
a function of r. The quantiles q now correspond to the induced availabilities, i.e., qi = Ai,m (r).
Observe that the resulting flows are within the following polytope (as in Sections 5.1 and 5.4):
X
X
X
X
(1) qbi ∈ [0, 1],
(2)
(φki qbk + zbki ) =
(φij qbi + zbij ),
(3)
zbik ≤
φji qbj ∀ i.
k

j

k

j

As in Section 5.1, these constraints stem from demand bounding, supply circulation, and the
limitation that only non-empty arriving vehicles may be rebalanced. Optimizing the elevated
objective over the polytope given by these constraints is a linear program and yields an upper
bound on the objective. Consider the redirection policy e
r obtained from the solution of the linear
program (cf. Algorithm 7). In the next Lemma, we bound the infinite unit performance of this
policy compared to the value of the elevated flow relaxation.
Algorithm 7 The Elevated Flow Relaxation Program for Redirection without Prices
Require: arrival rates φij , per-ride rewards Iij , rerouting costs cij .
1: Find {qi , zij } that solves the the following relaxation:
P
(φ qb I − cij zbij )
Maximize
P
Pi,j ij i ij
bk + zbki ) =
(φ qb + zbij )
∀i
k (φki q
Pj ij i
P
φ
q
b
∀i
z
b
≤
j ji j
k ik
qbi ∈ [0, 1]
∀i
2:

Output redirection probabilities rij = zij /

P

k

φki qki

b the quantiles solved for in the relaxation of Algorithm 7 and by e
r the
Lemma 29. Denote by q
d
redirection probabilities returned. Then Obj∞ (e
r) ≥ Obj(b
q, e
r).
Proof. Consider first Obj∞ (b
q, e
r), the objective obtained when implementing both the redirection
b that Algorithm 7 solves for. By the same argument as in Lemma 14,
policy e
r and the quantiles q
all availabilities are equal to 1 (and all traffic intensities are equal) in this system, and thus its
d q, e
objective matches Obj(b
r). In order for us to compare Obj∞ (b
q, e
r) with Obj∞ (e
r), consider a
node v ∈ arg maxj qbj . Increasing each quantile by a factor of 1/b
qv , we obtain quantiles q̄. Notice
that in the system with quantiles q̄, the traffic intensity at each node is changed by the same
factor, so the traffic intensities are still equal and the availabilities are still equal at every node.13
d q, e
Thus, Obj∞ (q̄, e
r) ≥ Obj(b
r). Thereafter, for each node j 6= v, we increase its quantile to 1.
Notice that each such change only decreases the traffic intensity at j, so the maximum traffic
intensity remains unchanged. The lemma follows because the decrease in the traffic intensity
13

In fact, for the relaxation in Algorithm 7, there exists at least one i such that qi = 1, so no quantile changes.
Allowing for delays and scaling demand with the number of units, this would not necessarily be the case.

30

(and thus availability) at each node j 6= v is exactly balanced by the increased rate of arrivals
at j. Formally, we have that fjk,∞ (q̄, e
r) remains unchanged when the jth coordinate of the
d q, e
quantiles is set to 1. Therefore, Obj∞ (e
r) = Obj∞ (q̄, e
r) ≥ Obj(b
r).
Now, using Lemma 29 in place of Lemma 14 in the proof of Theorem 13, we get the following.
m
Theorem 30. With e
r defined as above, Objm (e
r) ≥ m+n−1
Optm .

D.1

Delays without prices

Accommodating settings in which we are not allowed pricing, but do have delays, requires an
additional idea. This is because the argument in Section 5.3 explicitly relied on pricing to ensure
that (on average) not too many units are in transit simultaneously, thereby enabling a lower
bound on the maximum availability. Without prices to regulate demand, we can no longer control
the maximum availability. Instead, we use the following stochastic dominance characterization
for closed-queueing networks.
Lemma 31 (cf. Theorem 3.8 in Chen and Yao [CY13]). In a closed Jackson network, with
state-independent service rates, increasing the service rate functions, in a pointwise sense, at any
subset of nodes will increase throughput.
In our context, this is equivalent to saying that increasing quantiles at a subset of nodes only
increases throughput. In fact, one can show that throughput also increases locally, i.e., increasing
quantiles at one node (which we henceforth refer to as point quantiles) does not decrease the
rate of units on any edge.
e be a vector of point quantiles
Lemma 32. Let q = {qi } be a vector of point quantiles, and q
with qek ≥ qk ∀ k. Then for any pair (i, j), we have fij,m (q) ≤ fij,m (e
q), i.e. the rate of realized
trips from i to j does not decrease when point quantiles are increased.
e, we have
Proof. The proof relies on two observations. Note first for q and q
φ q
φ qe
P ij i = P ij i ∀ i, j,
ei
k φik qi
k φik q
P
and therefore, letting w(q0 ) denote the eigenvector of the routing matrix {φij (qi0 )/ k φik (qi0 )}i,j∈[n]2
q) = wi (q). Define Γm (q) , Gm (q)/Gm−1 (q). We now have that
(cf. Section 5.4), we obtain wi (e
the ratio of the rates fij,m (q)/fij,m (e
q) is equal to
Γm (q) Pwiφ(q)
qi
fij,m (q)
Ai,m (q)qi φij
Γm (q)ri (q)qi
Γm (q)
k ik qi
=
=
=
.
=
w
(e
q
)
i
fij,m (e
q)
Ai,m (e
q)e
qi φij
Γm (e
q)ri (e
q)e
qi
Γm (e
q)
Γm (e
q) P φik qei qei
k

Note that the
q) does not depend on i and j. Moreover, from Theorem
Pratio of fij,m (q)
P and fij,m (e
31 we have i,j fij,m (q) ≤ i,j fij,m (e
q). Combining the two, we get fij,m (q) ≤ fij,m (e
q).
This allows us to prove the guarantee of Theorem 21 for settings in which prices cannot be used
to provide a lower on the maximum availability within the system.
p
r denote the output of Algorithm 8 with εm := 2 ln m/m, Optm be the value
Theorem 33. Let e
of the objective function for the optimal state-dependent pricing policy, and m ≥ 100. Then
!
√
Objm (e
r)
m ln m
3
≥ (1 − εm ) √
−√
.
Optm
m ln m + n − 1
m ln m
Proof. The same proof as in Theorem 21 guarantees that using point prices as given by q(1 − m ),
where q comes from the solution of the relaxation in Algorithm 8 yields the required guarantee.
Lemma 32 then guarantees that increasing all quantiles to one yields a solution no worse.
31

Algorithm 8 The Rate-Limited Elevated Flow Relaxation Program for Redirection w/o Prices
Require: scaling paramter m , arrival rates φij , rewards Iij , rerouting costs cij , travel-times τij .
1: Find {qi , zij } that solves the the following relaxation:
Maximize
P
bij
i,j φij τij qi + z
P
(φ
q
+
z
b
k ki kP ki )
bik
kz
qbi
2:

P
≤
=
≤
∈

Output redirection probabilities rij = zij /

bi Iij
i,j (φij q

− cij zbij )

m
P
(φ qb + zbij )
Pj ij i
bj
j φji q
[0, 1]

P

k

∀i
∀i
∀i

φki qki

We remark that with m → ∞, the above theorem recovers the result of Braverman et al [BDLY16].
Finally, we note that Lemma 32 also yields an alternate proof of Lemma 6: given quantiles q
rk (q)
that do not induce a demand circulation, we consider a system with rates φeij = φij maxrik(q)
.
We observe that (i) the objectives with rates φeij and rates φij are the same in an infinite unit
system and (ii) that the system with rates φeij obeys the demand circulation property. Thus, the
counting argument of [Whi84] guarantees an objective within m/(m + n − 1) of the infinite unit
system in a system with rates φeij . However, by (i) the latter was equal to the upper bound on
Optm . Since Lemma 32 implies that the m-unit system with rates φij has objective no worse
than the m-unit system with rates φeij , the statement of the lemma follows.

E

Tightness Of Our Guarantees

In this section, we discuss an example of [WJ14], that proves that the guarantees we prove for our
algorithms are tight. Interestingly, this does not require the distinction between state-dependent
and state-independent policies, i.e. the objectives obtained through our algorithms can be as far
away from the optimal state-independent policy as from the optimal state-dependent polcy.
Proposition 34. ([WJ14]) For any number m of units and n of nodes, the objective of the
solution returned in Algorithm 1 and the optimal objective may be arbitrarily close to the
m
approximation guarantee m+n−1
.
Proof. Consider a system of n nodes {1, . . . , n} with demand only occurring from nodes i to i + 1
and from node n to node 1. In particular, suppose that for some k that is yet to be set, we have
φ12 = φ23 = . . . = φn−1 n = k, and φn1 = 1. Further, suppose we are maximizing throughput,
though the same construction works for revenue and social welfare. The policy returned by
Algorithm 1 sets quantiles q12 = q23 = . . . = qn−1 n = k1 and qn1 = 1. Given that the availability
m
of each node is then m+n−1
(cf. Lemma 6 with all inequalities holding tightly) and that there are
nm
n nodes from which a ride can occur (at rate 1), the throughput is m+n−1
. On the other hand,
for the solution that sets all quantiles to 1, the throughput converges to n as k → ∞. Intuitively,
this is because the expected time between an arrival at node n (triggering that unit to move
to node 1) and the expected return time of that unit to node n converges to 0. Thus, for each
arrival at node n, occurring at rate 1, the system observes m rides. The details of this argument
can be found in Proposition 3 of [WJ14].

32

F

Auxiliary lemma

We present a basic Chernoff tail bound for Poisson random variables, which we use in Section 5.3
Lemma 35. For X ∼ Poisson(λ), we have for any 0 ≤ x ≤ λ:

 2
x
x
1−
P[X > λ + x] ≤ exp −
2λ
λ
Proof. Using a standard Chernoff bound argument, we have for any θ ≥ 0:
h
i
θ
P[X > λ + x] = P[eθX > eθ(λ+x) ] ≤ e−θ(λ+x) E eθX = e−θ(λ+x) · eλ(e −1)
Now, optimizing over the choice of θ, we get
  


θ
P[X > λ + x] ≤ exp inf λ e − 1 − θ − xθ
θ

= exp(x − (x + λ) log(1 + x/λ)) (Setting θ = log(1 + x/λ))



 2

x
x2
x
x
≤ exp x − (x + λ)
−
= exp −
1−
λ 2λ2
2λ
λ

33

