# Dynamic Pricing Provides Robust Equilibria in Stochastic Ride-Sharing
Networks

J. Massey Cashore Supported by an NSERC PGS D Fellowship Peter I. Frazier
Supported by AFOSR grant FA9550-19-1-0283 Éva Tardos Supported by AFOSR grant
FA9550-19-1-0183 and NSF grants CCF-1408673 and CCF-1563714

( Cornell University
)

###### Abstract

Ridesharing markets are complex: drivers are strategic, rider demand and
driver availability are stochastic, and complex city-scale phenomena like
weather induce large scale correlation across space and time. At the same
time, past work has focused on a subset of these challenges. We propose a
model of ridesharing networks with strategic drivers, spatiotemporal dynamics,
and stochasticity. Supporting both computational tractability and better
modeling flexibility than classical fluid limits, we use a two-level
stochastic model that allows correlated shocks caused by weather or large
public events.

Using this model, we propose a novel pricing mechanism: stochastic
spatiotemporal pricing (SSP). We show that the SSP mechanism is asymptotically
incentive-compatible and that all (approximate) equilibria of the resulting
game are asymptotically welfare-maximizing when the market is large enough.
The SSP mechanism iteratively recomputes prices based on realized demand and
supply, and in this sense prices dynamically. We show that this is critical:
while a static variant of the SSP mechanism (whose prices vary with the
market-level stochastic scenario but not individual rider and driver
decisions) has a sequence of asymptotically welfare-optimal approximate
equilibria, we demonstrate that it also has other equilibria producing
extremely low social welfare. Thus, we argue that dynamic pricing is important
for ensuring robustness in stochastic ride-sharing networks.

##  1 Introduction

Ridesharing markets are complex. Drivers are strategic (Cradeur, 2018; Lu et
al., 2018), rider and driver decisions are stochastic, stochastic city-scale
phenomenon like weather create correlation across space and time (Kamga et
al., 2013; Chou, 2002), and factors including irrationality (Sheldon, 2016;
Camerer, 1997), learning (Cook et al., 2018), and model error require robust
off-equilibrium performance.

At the same time, pricing methods for ridesharing published in the academic
literature are developed and analyzed considering only a portion of this
complexity. Work studying stochastic demand focuses on non-strategic drivers
(Braverman et al., 2019; Banerjee et al., 2017; Besbes et al., 2019; Yan et
al., 2020; Alonso-Mora et al., 2017; Ashlagi et al., 2018; Özkan and Ward,
2020) and/or ignores spatial aspects of ridesharing (Castillo et al., 2017;
Chen et al., 2019a; Garg and Nazerzadeh, 2020). Work focusing on strategic
drivers in more realistic spatial settings assume deterministic demand (Ma et
al., 2018), take a fluid limit in which demand becomes deterministic (Afeche
et al., 2018; Besbes et al., 2018; Bimpikis et al., 2016), or are descriptive
rather than normative (Lu et al., 2018).

Our paper studies strategic driver behaviour in a model unifying many of the
real-world complexities that were previously studied in isolation: stochastic
rider demand, stochastic driver availability, strategic driver decisions, and
network structure with spatial and temporal components. In a novel stochastic
large-market limit more appropriate for ridesharing applications than past
deterministic fluid limits (Afeche et al., 2018), we develop a computationally
tractable pricing and matching mechanism under which all approximate
equilibria are asymptotically welfare-optimal. We additionally show that
ensuring all approximate equilibria are good is non-trivial: we demonstrate
that persistent stochasticity in the large-market limit creates the need for a
“re-solving” step when defining our mechanism. Without this, we show that a
different mechanism that does not re-solve and that is more closely linked to
deterministic past work (Ma et al., 2018) has approximate equilibria that lose
substantial welfare even in the large-market limit.

We model stochastic supply and demand with a two-level hierarchical
distribution reminiscent of stochastic programming (Prékopa, 2013) that
simultaneously provides computational tractability and modeling flexibility.
The top level corresponds to city-level variation in demand and supply
patterns caused by weather, large public events, public transit outages and
other random phenomenon that affect many riders and drivers simultaneously.
These phenomena create random shocks that are correlated across many riders
and drivers. The lower level corresponds to fine-grained idiosyncratic
randomness that affects individual riders and drivers independently.

Idiosyncratic randomness is tackled with a key analytical tool: a large-market
setting in which the number of riders and drivers scale proportionally. This
is especially relevant for the key ridesharing markets, those in large cities,
where the number of riders and drivers is large. Through this approach, some
randomness vanishes (conditionally independent rider and driver variation),
supporting efficient computation of mechanisms based on this large-market
limit. At the same time, randomness encoded by the stochastic scenario tree
modeling city-level phenomena remains. This fact is an important difference
between the large-market limit that we study and other deterministic large-
market limits previously studied in ridesharing (Afeche et al., 2018), and
allows us to model important correlated city-wide shocks that pure fluid
limits do not.

Building on the power of this novel modeling approach, we develop a novel
pricing and matching algorithm for ridesharing markets, called the stochastic
spatiotemporal pricing (SSP) mechanism. This recomputes pricing and matching
decisions at each time period based on the observed scenario and driver
distribution by solving a multistage stochastic program arising in the large-
market limit. This can be solved as a convex program that remains tractable
for up to several thousand scenarios. Since the SSP responds to the stochastic
scenario and real-time driver locations, it is a form of dynamic pricing.

The SSP mechanism is incentive compatible and all equilibria are welfare-
maximizing when idiosyncratic randomness is absent. Further, all approximate
equilibria are approximately welfare-maximizing when demand is
idiosyncratically random and the market is large, in the sense that incentive
compatibility violations and welfare-suboptimality of any equilibria vanish in
this limit.

Indeed, this is critical in practice because such perturbations are
inevitable. We show that the repeated computations are essential for achieving
robust market performance in the presence of such perturbations. This insight
is derived from comparing the SSP mechanism to a static analog that uses
static prices derived from only a single computation, depending only on the
scenario. While this static mechanism has at least one approximate equilibrium
that is asymptotically welfare-optimal, namely, resulting from following the
platform’s suggestions, we observe, using a simple example, that its
performance is not robust: approximate equilibria of the static mechanism can
have extremely low social welfare while those of the SSP mechanism cannot.

The key distinction between the SSP and the static mechanism is that the first
responds to real-time conditions, while the second is only able to respond to
variation in the top-level stochastic scenario. Indeed, in the example in §5,
there is only one scenario and so the static mechanism (which can depend on
the scenario in general) corresponds to a fully deterministic pricing strategy
of the kind studied by (Ma et al., 2018). Thus, the fact that SSP (which uses
re-solving and thus changes prices dynamically based on market conditions) is
guaranteed to result in equilibria with high social welfare while the static
mechanism does not, argues that dynamic pricing is better able to provide
robust equilibria and adapt to market fluctuations. This is the first
analysis, of which we are aware, to argue that dynamic pricing is needed for
this purpose, and contributes to the larger literature on the purpose and
value of dynamic pricing in ridesharing (Castillo et al., 2017; Banerjee et
al., 2016; Lu et al., 2018; Cachon et al., 2017; Hall et al., 2015; Chen and
Sheldon, 2016).

In summary, the primary contributions of this paper are:

  * •

In §2 we provide a novel two-level stochastic model of ride-sharing, that
allows us to study a large-market limit retaining the persistent uncertainty
of the macroscopic stochasticity of our model. We refer to a model created by
taking this limit as the stochastic fluid model and to the original model as
the two-level model.

  * •

In §3 we show that the optimal driver allocation in the stochastic fluid model
can be computed by a tractable convex program. We will then use the dual
variables of this convex program for the suggested pricing method for
rideshare pricing, resulting in a practical dynamic pricing mechanism, SSP,
defined in §4.

  * •

In §4, we study SSP’s properties. First, in the stochastic fluid model, we
show (Theorem 2) that all equilibria resulting from the SSP mechanism are
welfare optimal and all approximate equilibria are approximately welfare
optimal.

  * •

Then, in the two-level model, we show (Theorem 3) that in this detailed and
realistic model, every approximate equilibrium resulting from the SSP
mechanism achieves approximately optimal welfare when the market is large
enough.

  * •

Finally, in §5 we show that dynamic pricing enabled by re-solving is a key
component in enabling our robustness result Theorem 3. We consider a variant
of the SSP that does not re-solve, ignoring current driver locations. We
demonstrate in a simple example how a risk premium leads to an equilibrium
with significantly suboptimal welfare in large finite markets, despite
existence of another equilibrium with optimal welfare in the stochastic fluid
model. This suggests that being fully dynamic (depending both on observed
supply/demand and city-level stochastic scenarios) may be important for
achieving good practical performance in rideshare pricing.

###  1.1 Related Work

The literature on ridesharing has recently considered drivers’ strategic
choice of location in (Ma et al., 2018; Afeche et al., 2018; Besbes et al.,
2018; Bimpikis et al., 2016; Lu et al., 2018).

Papers (Bimpikis et al., 2016; Afeche et al., 2018; Besbes et al., 2018) all
consider spatially heterogeneous driver-side pricing to incentivize driver
relocation, but unlike the current paper consider a deterministic continuum
approximation of the number of drivers in each node (or at points in a spatial
continuum in (Besbes et al., 2018)) and the flow of demand between nodes. In
contrast, we focus on atomic drivers and study the effects of demand
uncertainty.

(Lu et al., 2018) provides empirical evidence using data from Uber that surge
pricing causes drivers to relocate toward locations with higher surge. It
argues that the causal effect of surge has three components: a direct effect
on earnings per trip; a real-time signal that demand is higher than expected
at the surging location; and a slower signal about average location-specific
demand. In the current paper we focus on the first aspect. The second and
third aspects are absent from our model due to assumptions that the demand
distribution, other drivers’ strategies, and the platform’s mechanism are all
known.

The work within this ridesharing literature most closely related to the
current paper is (Ma et al., 2018). This paper studies driver-side pricing in
a multi-location multi-period model of a ridesharing market, and considers how
to set prices over space (and time) to ensure that strategic drivers make
welfare-optimal empty relocation decisions and accept all dispatches. Like the
current paper, these prices are based on solving an LP relaxation of the
optimal planning problem to integrality. Critically, and unlike the current
paper, (Ma et al., 2018) assumes that the platform (and drivers) have complete
information about future demand from riders. This assumption causes the
welfare-optimal actions to be incentivizable. We show that this result extends
to the fluid limit variant of our problem, despite the high-level uncertainty
in the model. However, stochasticity not encoded in a top-level scenario
(including the idiosyncratic low-level stochasticity in our model), can cause
the equilibria of such a mechanism without dynamic pricing to have extremely
low social welfare. Including a perfect representation of all stochasticity
into a scenario tree is practically impossible from a modeling perspective and
would lead to computational intractability. Thus, we see the model in (Ma et
al., 2018) as focusing on fully deterministic ridesharing markets, without
providing a robust way to generalize to realistic settings. In contrast, we
see our approach as a step toward the computational tractability, modeling
flexibility and robustness required in practice.

Within the sharing economy more broadly, (Chung et al., 2018) considers the
problem of designing incentives in the context of bike sharing rebalancing, in
which strategic agents trade off the cost (in terms of time and effort) of
moving a bike between stations against the location-specific platform-
controlled reward. The work in (Chung et al., 2018) pays special attention to
practical considerations, and they demonstrate that the intelligent design of
centrally controlled incentives can have meaningful real-world impact.

There is also work that considers drivers’ strategic behavior regarding which
trips to accept (Chen et al., 2019b; Chen and Hu, 2020; Garg and Nazerzadeh,
2020; Castro et al., 2020) without considering the spatial aspects of
ridesharing.

##  2 Model Description

Stochastic Network Structure. Drivers move across a set of locations
$\mathcal{L}\neq\emptyset$ in discrete time over $T$ periods.

Macroscopic randomness is modeled by a Markov chain $(A_{t}:t)$ with discrete
random variables $A_{t}$ that will make the behavior of riders and drivers
random, even in the large-market limit. We refer to $\omega_{t}=A_{1:t}$ as
the _scenario_ at time $t$ (including the history), where
$\omega_{0}=\emptyset$. $\Omega_{t}$ denotes the set of possible values for
$\omega_{t}$. We write $\omega_{t}\sim\mathbb{P}(\cdot\mid\omega_{t-1})$ to
indicate the conditional distribution of $\omega_{t}$. We use
$\Omega_{t}(\omega_{s})=\\{\omega_{t}\in\Omega_{t}:\omega_{t}^{1:s}=\omega_{s}\\}$
to denote the set of scenarios possible at time $t$ given $\omega_{s}$ at time
$s$, where $\omega_{t}^{1:s}$ truncates $\omega_{t}$ to its first $s$
elements. We refer to the set of all scenarios as the scenario tree. Each
scenario $w_{t}$ is a node in this tree, linked to all scienarios
$\Omega_{t+1}(\omega_{t})$.

We assume there is a fixed cost $c_{(\ell,d,\omega_{t})}$ to drive from a
location $\ell$ to a destination $d$ at time $t$ under the scenario
$\omega_{t}$.

Driver and Rider Entry. We consider a large-market limit where the volume of
drivers and riders scale with a _population-size parameter_ $k\in\mathbb{N}$.
The number of drivers entering the market at location $\ell$, time $t$, and
scenario $\omega_{t}$ under population size $k$ is a random variable
$M^{(k)}_{(\ell,\omega_{t})}$. The number of riders interested in traveling
from location $\ell$ to location $d$ is a random variable
$D^{(k)}_{(\ell,d,\omega_{t})}$. We sometimes omit the superscript $k$ and
write $M_{(\ell,\omega_{t})}$ or $D_{(\ell,d,\omega_{t})}$. A subset of the
possible riders in $D^{(k)}_{(\ell,d,\omega_{t})}$ will request a ride,
depending on the price set by the platform. We assume that these random
variables satisfy good concentration properties as $k$ grows large and have
expected values that scale linearly in $k$, as stated in Assumption 1.

######  Assumption 1.

Let $(X^{(k)})_{k=1}^{\infty}$ be the sequence of driver- or rider-entry
random variables $(M^{(k)}_{(\ell,\omega_{t})})_{k=1}^{\infty}$ or
$(D^{(k)}_{(\ell,d,\omega_{t})})_{k=1}^{\infty}$, for any location
$\ell,d,\omega_{t}$. We assume:

  1. 1.

The expected value of $X^{(k)}$ grows linearly in $k$, i.e.
$\mathbb{E}[X^{(k)}]=k\mathbb{E}[X^{(1)}]$ for all $k\geq 1$.

  2. 2.

There exists a sequence of error terms $(\epsilon_{k}:k\geq 1)$ and
probability terms $(q_{k}:k\geq 1)$, both converging to $0$ as $k\to\infty$,
such that:

$\mathbb{P}\left(\frac{1}{k}|X^{(k)}-\mathbb{E}[X^{(k)}]|\geq\epsilon_{k}\right)\leq
q_{k}.$ (1)

For example, if each $X^{(k)}$ follows a $\mathrm{Poisson}(\lambda k)$
distribution, then property 1 is immediate and property 2 follows from
concentration inequalities.

For simplicity we assume that drivers do not exit the market. We also assume
that it takes a single time period to driver from any origin location to
destination location. Both assumptions are without loss of generality: we can
add locations that model being on-trip or leaving the market.

Market State. Let $\mathcal{M}_{t}$ be the set of drivers who have entered the
marketplace by time $t$ and let $\ell_{i}\in\mathcal{L}$ be the current
location of driver $i$ (momentarily suppressing the dependence on $t$ in the
notation). Let $S_{\ell}$ denote $1/k$ times the number of drivers at position
$\ell$, that is the volume of active drivers who are positioned at $\ell$,
normalized by $k$.

Then, $\mathbf{S}_{t}=(S_{\ell}:\ell\in\mathcal{L})$ represents the supply
volume across all locations. We refer to $\mathbf{S}_{t}$ as the supply-
location vector. We define our state variable at the beginning of each time
period $t$ to be the tuple $(\omega_{t},\mathbf{S}_{t})$, meaning that the
platform pricing and matching decisions, as well as strategic driver decisions
about where to drive, depend only on the realized scenario $\omega_{t}$ and
the spatial distribution of drivers specified by $\mathbf{S}_{t}$. Section
shows that this is (essentially) without loss of generality, assuming that
drivers are expected utility maximizers.

The notation $\mathcal{S}=\mathbb{R}^{\mathcal{L}}_{+}$ indicates the set of
vectors indexed by locations $\mathcal{L}$ with nonnegative components. We
think of $\Omega_{t}\times\mathcal{S}$ as the state space at time $t$.

Pricing Policy and Rider Dispatch Requests. The platform sets prices at time
$t$ using function $P_{t}$. We write $P_{(\ell,d,\omega_{t})}(\mathbf{S}_{t})$
to mean the price for trips from $\ell$ to $d$ when
$(\omega_{t},\mathbf{S}_{t})$ is the market state. More simply, we write
$P_{(\ell,d)}$ when the pricing function and associated market state is clear.

Prices filter demand for a trip. For each pair of locations
$(\ell,d)\in\mathcal{L}^{2}$ and each scenario $\omega_{t}$, every rider who
is interested in a trip from $\ell$ to $d$ holds a private value $V$ for the
trip. We assume the private values $V_{j}$ for all
$j=1,2,\dots,D_{(\ell,d,\omega_{t})}$ riders are independent, identically
distributed random variables. Let $F_{(\ell,d,\omega_{t})}$ be the associated
cumulative distribution function. We assume $F_{(\ell,d,\omega_{t})}$
satisfies Assumption 2.

######  Assumption 2.

We assume:

  1. 1.

There exists an upper bound $V_{max}$ on the valuation $V$ such that
$F(V_{max})=1$.

  2. 2.

$F:[0,V_{max}]\to[0,1]$ is continuous and invertible, and the inverse is
Lipschitz continuous.

  3. 3.

The inverse function at $0$ satisfies $F^{-1}(0)=0$.

We assume that riders only request a dispatch if their value $V_{j}$ exceeds
the price $P_{(\ell,d)}$. Let $R_{(\ell,d,\omega_{t})}$ be a random variable
counting the number of riders who request a trip from $\ell$ to $d$ under the
price $P_{(\ell,d)}$. $R_{(\ell,d,\omega_{t})}$ follows a Binomial
distribution with $D_{(\ell,d,\omega_{t})}$ trials and
$1-F_{(\ell,d,\omega_{t})}(P_{(\ell,d)})$ success probability. We write
$R_{(\ell,d)}$ for the number of dispatch requests when the scenario
$\omega_{t}$ is clear.

Matching Process, Driver Strategies and Add-Passenger Disutility. After prices
filter demand and dispatch requests are realized for each route, the platform
operates a matching process that allocates dispatch requests to available
drivers. When allocated a dispatch, a driver may accept or decline. If the
driver accepts, they drive the passenger to the dispatch’s destination and
collect the associated payment. If the driver declines, they do not collect a
payment and may optionally drive to any destination they choose.

Drivers incur an idiosyncratic _add-passenger disutility_ , which models the
cost of adding a passenger to their car. In each period, every driver samples
their add-passenger disutility independently from a $\mathrm{Uniform}(0,C)$
distribution for some constant $C>0$. A driver’s decision about whether to
accept or reject a dispatch depends also on their add-passenger disutility.

We model driver decisions by assuming every driver at a location $\ell$
specifies a threshold $x_{(\ell,d)}\in[0,C]$ for each possible dispatch
destination $d\in\mathcal{L}$. These threshold may depend on the driver,
though we suppress this in the notation. When a driver is allocated a dispatch
towards location $d$, we assume they only accept the dispatch if their add-
passenger disutility value $X$ is smaller than $x_{(\ell,d)}$. Each driver’s
strategy also specifies a destination $e\in\mathcal{L}$, to which they will
drive empty if they do not accept a dispatch.

For each location $\ell$ and time $t$, let $\mathcal{M}_{\ell,t}$ be the set
of drivers at $\ell$ at time $t$. For each driver $i\in\mathcal{M}_{\ell,t}$,
we write $\bm{x}_{i}=(x^{i}_{(\ell,d)}:d\in\mathcal{L})$ to mean the vector of
disutility-acceptance thresholds selected by driver $i$, and
$e_{i}\in\mathcal{L}$ is the relocation destination selected by driver $i$.

We assume that dispatches can only be served by drivers positioned at the
dispatch’s origin. We also assume that each driver can be allocated at most
one dispatch, that is, drivers who decline a dispatch will not get allocated
an alternate dispatch in the same period.

We formalize the matching process as a function $\mathrm{MP}$ taking these
arguments:

  * •

A location $\ell\in\mathcal{L}$, and the market state
$(\omega_{t},\mathbf{S}_{t})$.

  * •

For each driver $i\in\mathcal{M}_{\ell,t}$, the disutility thresholds
$\bm{x}_{i}$ and the relocation destionation $e_{i}$.

  * •

For each driver $i\in\mathcal{M}_{\ell,t}$, the add-passenger disutility value
$X_{i}$.

  * •

For each destination $d$, the number of dispatch requests $R_{(\ell,d)}$.

  * •

An external source of randomness $U$ sampled independently and uniformly from
$[0,1]$.

The matching process produces a set of tuples
$\\{(i,b_{i}):i\in\mathcal{M}_{\ell,t}\\}$. Here,
$b_{i}\in\mathcal{L}\cup\\{\emptyset\\}$ is the destination of the dispatch
allocated to driver $i$ (where $b_{i}=\emptyset$ if driver $i$ was not
allocated a dispatch).

For each driver $i\in\mathcal{M}_{\ell,t}$, we use
$a_{i}^{t}=(\ell,d_{i},\delta_{i})$ to indicate their action at time $t$. The
driver’s starting location is $\ell$. The destination location $d_{i}$ depends
on the output of the matching process and the driver’s strategy
$(\bm{x}_{i},e_{i})$. If the add-passenger disutility $X_{i}$ is smaller than
the threshold $x_{(\ell,b_{i})}$, then the driver accepts the dispatch and
$d_{i}=b_{i}$ and $\delta_{i}=1$. If not, then the driver declines the
dispatch and instead drives towards $d_{i}=e_{i}$ with $\delta_{i}=0$.

We thus think of this entire matching process as taking the inputs to the
function $\mathrm{MP}$ specified above and producing the drivers’ actions
$(a_{i}^{t}:i\in\mathcal{M}_{\ell,t})$:

$(a_{i}^{t}:i\in\mathcal{M}_{\ell,t})\sim\mathrm{MP}(\ell,\\{(\bm{x}_{i},e_{i}):i\in\mathcal{M}_{\ell,t}\\},\\{R_{(\ell,d)}:d\in\mathcal{L}\\}).$

We assume the platform randomizes its selection of drivers (in particular,
preferential dispatch is not an available lever to align incentives). We also
assume the actions produced by the matching process are always feasible with
respect to demand, i.e. the number of drivers serving a dispatch from $\ell$
to $d$ never exceeds the number of dispatch requests $R_{(\ell,d)}$.

Strategy Profiles and Approximate Equilibria. We now define a strategy
profile. Let $\mathcal{M}$ be the set of indices for all drivers who could
potentially join the market. For each driver $i\in\mathcal{M}$, a strategy is
a sequence of functions $\pi_{i}=(\pi_{i}^{1},\pi_{i}^{2},\dots,\pi_{i}^{T})$
where each $\pi_{i}^{t}$ determines the driver’s action at time $t$. This
function
$\pi_{i}^{t}:\mathcal{L}\times\mathcal{S}_{t}\to\mathcal{X}\times\mathcal{L}$
takes as input a location $\ell$ and a time $t$ state
$(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}$, and produces a disutility
threshold vector $\bm{x}_{i}\in\mathcal{X}$ and a relocation destination
$e_{i}\in\mathcal{L}$.

We define a strategy profile as $\Pi=(\pi_{i}:i\in\mathcal{M})$. We model
strategic driver behaviour by assuming that drivers select strategies
resulting in an approximate equilibrium strategy profile $\Pi$, as defined
below. Fixing the strategy profile, (and also the pricing and matching
policies), the market dynamics are simply a stochastic process. Whether a
strategy profile $\Pi$ is an approximate equilibrium (with respect to a
pricing and matching policy) depends on this stochastic process.

Fix a strategy profile $\Pi$ and assume that pricing and matching policies are
fixed. Let $(a_{i}^{t}:t\in[T])$ be the sequence of actions taken by each
driver $i\in\mathcal{M}$. Set $a_{i}^{t}=\emptyset$ for any driver $i$ who
hasn’t entered the market by time period $t$; otherwise $a_{i}^{t}$ is
selected based on the matching process for time period $t$.

Let $R_{i}^{t}$ be the reward collected by driver $i$ in time period $t$.
$R_{i}^{t}$ is determined from the action $a_{i}^{t}$ based on the following
relationship:

$R_{i}^{t}=\begin{cases}P_{(\ell,d)}^{t}-X_{i}^{t}-c_{(\ell,d)}&\mbox{if
}a_{i}^{t}=(\ell,d,1),\\\ -c_{(\ell,d)}&\mbox{if }a_{i}^{t}=(\ell,d,0),\\\
0&\mbox{if }a_{i}^{t}=\emptyset,\end{cases}$ (2)

where $P_{(\ell,d)}^{t}$ is the price set by the SSP mechanism for a dispatch
from $\ell$ to $d$ in time period $t$, and $X_{i}^{t}$ is driver $i$’s add-
passenger disutility from time period $t$. The utility-to-go $U^{t}_{i}$ for
driver $i$ at time period $t$ is the sum of rewards they collect over all
future time periods,

$U_{i}^{t}=\sum_{\tau=t}^{T}R_{i}^{\tau}.$ (3)

$R_{i}^{t}$ and $U_{i}^{t}$ are both random variables.

Our definition of incentive compatibility for $\Pi$ will use of a driver’s
expected utility to go, conditioned on their dispatch destination and their
add-passenger disutility. Define
$\mathcal{U}_{i}^{t}(\ell,b,X,(\omega_{t},\mathbf{S}_{t});\Pi)$ to mean the
expected utility-to-go collected by driver $i$, conditioned on being located
at $\ell$, on being allocated a dispatch towards
$b\in\mathcal{L}\cup\\{\emptyset\\}$, on seeing add-passenger disutility
$X\in[0,C]$, on the market state $(\omega_{t},\mathbf{S}_{t})$, and the
strategy profile $\Pi$:

$\mathcal{U}_{i}^{t}(\ell,b,X,(\omega_{t},\mathbf{S}_{t});\Pi)=\mathbb{E}^{\Pi}\left[U_{i}^{t}\mid\ell_{i}^{t}=\ell,b_{i}^{t}=b,X_{i}^{t}=X,(\omega_{t},\mathbf{S}_{t})\right].$

When the location and the state do not need to be emphasized, we write
$\mathcal{U}_{i}^{t}(b,X;\Pi)$ for clarity.

Informally, a strategy profile $\Pi$ is an approximate equilibrium if (almost)
every driver has small incentive to deviate, regardless of the destination
they are dispatched towards (if any). We use the notation
$\Pi-\pi_{i}+\pi_{i}^{\prime}$ to represent that driver $i$ deviates from a
strategy $\pi_{i}$ to an alternate strategy $\pi_{i}^{\prime}$. The incentive-
to-deviate for a driver, given a particular time period and market state, is
defined as the maximum utility gain the driver can achieve by switching to an
alternate strategy. Recall we use the set $\mathcal{M}_{t}$ to index the
active drivers in the marketplace at time $t$. We use the notation
$\mathcal{M}_{t}(\epsilon;(\omega_{t},\mathbf{S}_{t}))$ to mean the set of
active drivers whose conditional incentive-to-deviate is at most $\epsilon$,
given the market state $(\omega_{t},\mathbf{S}_{t})$:

$\mathcal{M}_{t}(\epsilon;(\omega_{t},\mathbf{S}_{t}))=\left\\{i\in\mathcal{M}_{t}:\sup_{b\in\mathcal{L}\cup\\{\emptyset\\}}\sup_{X\in[0,C]}\sup_{\pi_{i}^{\prime}}\mathcal{U}_{i}^{t}(b,X;\Pi-\pi_{i}+\pi_{i}^{\prime})-\mathcal{U}_{i}^{t}(b,X;\Pi)\leq\epsilon\right\\}.$
(4)

$\mathcal{M}_{t}(\epsilon)$ implicitly depends on the market state
$(\omega_{t},\mathbf{S}_{t})$, but we omit this dependence in the notation for
clarity. The formal definition $\Pi$ must meet to be considered an approximate
equilibrium is stated below.

######  Definition 1.

Consider the two-level model with population size $k$. Hold the platform and
matching policies fixed and let $\Pi$ be a strategy-profile. For a constant
$\epsilon>0$, we say that $\Pi$ is an $(\epsilon,\delta)$-approximate
equilibrium if the number of drivers who have at least $\epsilon$-conditional
incentive to deviate from any market state is smaller than $\delta k$, i.e.,
if

$|\mathcal{M}_{t}\setminus\mathcal{M}_{t}(\epsilon;\omega_{t},\mathbf{S}_{t})|\leq\delta
k$

for every $t$ and every market state
$(\omega_{t},\mathbf{S}_{t})\in\Omega_{t}\times\mathcal{S}_{t}(\gamma_{t})$.

In the above definition, we use the notation $\mathcal{S}_{t}(\gamma_{t})$ to
mean the set of supply-location vectors $\mathbf{S}=(S_{\ell}\geq
0:\ell\in\mathcal{L})$ such that the total volume of drivers in the network is
smaller than $\gamma_{t}$, i.e. $\sum_{\ell}S_{\ell}\leq\gamma_{t}$. We pick
$\gamma_{t}$ to be a large constant so that
$\mathbf{S}_{t}\in\mathcal{S}_{t}(\gamma_{t})$ occurs with high-probability.
Note that the choice of $\gamma_{t}$ need only depend on the distributions
governing the number of drivers who enter the marketplace, which satisfy the
concentration assumptions described in Assumption 1. In particular, the total
volume of drivers in the marketplace at time $t$ is invariant to the strategy
that the drivers use (since we assume without loss of generality that drivers
never exit the marketplace).

The Stochastic Fluid Model The fluid model is our tractable approximation to
the main model we have been describing so far. We can think of the sources of
randomness in our main model as falling under two buckets: the stochastic
scenario tree governs _macroscopic_ randomness, and the remaining sources of
randomness (driver entry, rider entry and dispatch requests) form
_microscopic_ randomness. With this designation in mind, we refer to our main
model as the stochastic two-level model. The stochastic two-level model
retains the top-level macroscopic randomness, but it approximates the
microscopic randomness with deterministic dynamics.

The volume of riders and drivers who enter the market is deterministic in the
stochastic fluid model, conditional on the realized scenario. For a time
period $t$ and scenario $\omega_{t}$, let

$\bar{M}_{(\ell,\omega_{t})}=\mathbb{E}[M^{(1)}_{(\ell,\omega_{t})}]\ \ \
\mbox{ and }\ \ \
\bar{D}_{(\ell,d,\omega_{t})}=\mathbb{E}[D^{(1)}_{(\ell,d,\omega_{t})}]$

be the volume of drivers who join the market at location $\ell$, and the
volume of riders who enter the market interested in a dispatch from $\ell$ to
$d$, respectively. While these definitions are stated in terms of the expected
number of drivers and riders who join the market under a population-size
parameter $k$ equal to $1$, this is equivalent to taking the expected number
of drivers and riders who join under any population-size $k$ and dividing that
by $k$, under the first condition stated in Assumption 1. Also define

$\bar{r}_{(\ell,d,\omega_{t})}(P)=\bar{D}_{(\ell,d,\omega_{t})}\left(1-F_{(\ell,d,\omega_{t})}(P)\right)$

to be the fluid volume of riders who request a trip, as a function of the trip
price $P$.

Our formalization of a pricing policy is the same in the stochastic fluid
model as it was in the two-level model: a pricing policy is a sequence of
functions $(P_{1},P_{2},\dots,P_{T})$ where each $P_{t}$ is a function that
sees the market state $(\omega_{t},\mathbf{S}_{t})$ and produces a vector of
trip prices for each route $(P_{(\ell,d)}\geq 0:(\ell,d)\in\mathcal{L}^{2})$.

We model strategy profiles in the fluid model as a sequence of functions
$\Sigma=(\Sigma_{1},\dots,\Sigma_{T})$. In the stochastic fluid model we
assume all drivers at the same location use the same disutility threshold for
accepting or rejecting a dispatch decision. We also assume that driver
relocation decisions are determined by a collective relocation distribution
for all drivers at the same location. Each function $\Sigma_{t}$ takes as
input a time $t$ state $(\omega_{t},\mathbf{S}_{t})$ and produces a disutility
threshold vector $\bm{x}_{\ell}\in\mathcal{X}$ and a relocation distribution
$\mathbf{e}_{\ell}\in\Delta(\mathcal{L})$, for each location $\ell$.

In the stochastic fluid model, the matching process is defined as a function
$\bar{\mathrm{MP}}$ that takes as input a location $\ell$, a market state
$(\omega_{t},\mathbf{S}_{t})$, and a disutility threshold vector
$\bm{x}_{\ell}$, and produces a dispatch vector
$\bm{g}_{\ell}=(g_{(\ell,d)}:d\in\mathcal{L})$ specifying the volume of
drivers $g_{(\ell,d)}$ who serve a dispatch from $\ell$ to $d$. If the drivers
at $\ell$ use a disutility acceptance threshold $x=x_{(\ell,d)}$ for
destination $d$, and the matching process specifies $g=g_{(\ell,d)}$
dispatches towards $d$, we assume the fluid matching process has to allocated
dispatches towards $d$ to a pool of drivers with volume

$Z(g,x)=\begin{cases}g\frac{C}{x}&\mbox{if }x>0,\\\ 0&\mbox{else}.\end{cases}$
(5)

For the dispatch volumes to be feasible, each $g_{(\ell,d)}$ cannot exceed the
dispatch request volume $\bar{r}_{(\ell,d)}(P_{(\ell,d)})$, and the implied
pool sizes cannot exceed the available driver supply: at each location $\ell$,

$\sum_{d\in\mathcal{L}}Z(g_{(\ell,d)},x_{(\ell,d)})\leq S_{\ell}.$ (6)

The volume of relocation trips along each route is then determined by the
relocation distribution $\mathbf{e}_{\ell}$ and the remaining volume of
undispatched drivers at $\ell$. The volume of drivers who serve a relocation
trip from $\ell$ to $d$ is defined as

$h_{(\ell,d)}=e_{(\ell,d)}\left(S_{\ell}-\sum_{d\in\mathcal{L}}g_{(\ell,d)}\right).$

Because the relocation volumes are deterministic functions of the dispatch
volumes, we can think of the matching process as a deterministic function that
takes as input the market state $(\omega_{t},\mathbf{S}_{t})$, the disutility
thresholds $\bm{x}_{\ell}\in\mathcal{X}^{\mathcal{L}}$ and the relocation
distributions $\mathbf{e}_{\ell}\in\Delta(\mathcal{L})$ used at each location
$\ell$, and producing trip volumes
$(\bm{h},\bm{g})=\bar{\mathrm{MP}}(\omega_{t},\mathbf{S}_{t},(\bm{x}_{\ell},\mathbf{e}_{\ell}:\ell\in\mathcal{L}))$,
where $\bm{h}=(h_{(\ell,d)}:(\ell,d)\in\mathcal{L}^{2})$ specifies the volume
of relocation trips along each route, and
$\bm{g}=(g_{(\ell,d)}:(\ell,d)\in\mathcal{L}^{2})$ specifies the volume of
dispatch trips along each route.

We will frequently use the parameterization $\bm{f}=\bm{h}+\bm{g}$ to mean the
vector of total trip volumes across each route. In the stochastic fluid model,
note that the supply location vector for the next time period is a
deterministic function of the scenario in the next time period and the total
trip volumes in the current time period. If the time $t$ scenario is
$\omega_{t}$ and the time $t$ total trip volumes are given by $\bm{f}$, if the
time $t+1$ scenario is $\omega_{t+1}$ then let
$\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f})$ specify the the time $t+1$ supply
location vector, where

$(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}))_{\ell}=\bar{M}_{(\ell,\omega_{t+1})}+\sum_{o\in\mathcal{L}}f_{(o,\ell)}.$
(7)

Equilibrium Strategies in the Stochastic Fluid Model. In order to define what
it means for a fluid strategy profile $\Sigma=(\Sigma_{1},\dots,\Sigma_{T})$
to be an equilibrium strategy profile, we associated with $\Sigma$ a value
function for each location and a Q-value for each trip type. The value
function specifies the expected utility-to-go for a driver given their
location, and the Q-value specifies the expected utility-to-go for a driver
given their action.

Assume the pricing and matching policies are fixed. We define the Q-values and
the value function associated with $\Sigma$ recursively. For the base case,
let $\mathcal{V}_{T+1}(\cdot)$ always equal $0$. Let
$a=(\ell,d,\delta)\in\mathcal{L}^{2}\times\\{0,1\\}$ denote any action, let
$X\in[0,C]$ be any add-passenger disutility value, let $t\in[T]$ be any time
period, and let $(\omega_{t},\mathbf{S}_{t})\in\Omega_{t}\times\mathcal{S}$ be
any market state. Assume the value function for the next time period
$\mathcal{V}_{t+1}:\mathcal{L}\times\Omega_{t}\times\mathcal{S}\to\mathbb{R}_{+}$
has already been defined. Let $\bm{h},\bm{g}$ be the relocation-trip and
dispatch-trip volumes produced by the matching process and the time $t$
strategy $\Sigma_{t}$, and let $\bm{f}=\bm{h}+\bm{g}$ be the total-trip
volumes.

Define the Q-value for time $t$ as:

$\mathcal{Q}_{t}(a,X,\omega_{t},\mathbf{S}_{t})=\delta(P_{(\ell,d)}-X)-c_{(\ell,d)}+\mathbb{E}\left[\mathcal{V}_{t+1}(d,\omega_{t+1},\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}))\right],$

and define the value of location $\ell$ at time $t$ as:

$\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})=\frac{1}{S_{\ell}}\sum_{d\in\mathcal{L}}\left[h_{(\ell,d)}\mathcal{Q}_{t}(\ell,d,0)+g_{(\ell,d)}\mathcal{Q}_{t}\left(\ell,d,1,\frac{x_{(\ell,d)}}{2}\right)\right].$

In the above, we write

$\mathcal{Q}_{t}(\ell,d,0)=\mathcal{Q}_{t}((\ell,d,0),X,\omega_{t},\mathbf{S}_{t})$

to mean the expected utility-to-go of drivers who take a relocation trip from
$\ell$ to $d$, and we write

$\mathcal{Q}_{t}\left(\ell,d,1,\frac{x_{(\ell,d)}}{2}\right)=\mathcal{Q}_{t}\left((\ell,d,0),\frac{x_{(\ell,d)}}{2},\omega_{t},\mathbf{S}_{t}\right)$

to mean the expected utility-to-go of drivers who serve a dispatch from $\ell$
to $d$. Note that $\frac{x_{(\ell,d)}}{2}$ is the average pickup disutility
incurred by drivers who serve a dispatch from $\ell$ to $d$. In this
definition of $\mathcal{V}_{t}$, we are implicitly relying on the equality

$\mathcal{Q}_{t}\left(\ell,d,1,\frac{x_{(\ell,d)}}{2}\right)=\frac{1}{x_{(\ell,d)}}\int_{0}^{x_{(\ell,d)}}\bar{\mathcal{Q}}_{t}\left(\ell,d,1,x\right)dx.$

In order for a fluid strategy $\Sigma$ to be an equilibrium with respect to a
fixed pricing policy and matching process, we require that no driver can have
a profitable deviation from their specified action, from any market state. The
property that no driver can have a profitable deviation can be broken down
further into the following subproperties:

  * •

A driver who takes a relocation trip cannot have the ability to take a
relocation trip toward a different destination yielding higher utility.

  * •

A driver who accepts a dispatch cannot have the ability to take a relocation
trip yielding higher utility.

  * •

A driver who declines a dispatch cannot have been able to achieve higher
utility by accepting the dispatch.

We summarize these properties with the following equations:

$\displaystyle h_{(\ell,d)}>0$
$\displaystyle\implies\mathcal{Q}_{t}(\ell,d,0)=\max_{d^{\prime}\in\mathcal{L}}\mathcal{Q}_{t}(\ell,d^{\prime},0),$
$\displaystyle g_{(\ell,d)}>0$
$\displaystyle\implies\mathcal{Q}_{t}(\ell,d,1,X)\geq\max_{d^{\prime}\in\mathcal{L}}\mathcal{Q}_{t}(\ell,d^{\prime},0)\
\ \ \ \forall X\in[0,x_{(\ell,d)}],$ (8) $\displaystyle\bar{r}_{(\ell,d)}>0,\
x_{(\ell,d)}<C$
$\displaystyle\implies\mathcal{Q}_{t}(\ell,d,1,X)\leq\max_{d^{\prime}\in\mathcal{L}}\mathcal{Q}_{t}(\ell,d^{\prime},0)\
\ \ \ \forall X\in(x_{(\ell,d)},C].$

We also provide approximate incentive comptability conditions, which depend on
an error term $\epsilon>0$:

$\displaystyle h_{(\ell,d)}>\epsilon$
$\displaystyle\implies\mathcal{Q}_{t}(\ell,d,0)\geq\max_{d^{\prime}\in\mathcal{L}}\mathcal{Q}_{t}(\ell,d^{\prime},0)-\epsilon,$
$\displaystyle g_{(\ell,d)}>\epsilon$
$\displaystyle\implies\mathcal{Q}_{t}(\ell,d,1,X)\geq\max_{d^{\prime}\in\mathcal{L}}\mathcal{Q}_{t}(\ell,d^{\prime},0)-\epsilon\
\ \ \ \forall X\in[0,x_{(\ell,d)}],$ (9)
$\displaystyle\bar{r}_{(\ell,d)}>\epsilon,\ x_{(\ell,d)}<C-\epsilon$
$\displaystyle\implies\mathcal{Q}_{t}(\ell,d,1,X)\leq\max_{d^{\prime}\in\mathcal{L}}\mathcal{Q}_{t}(\ell,d^{\prime},0)+\epsilon\
\ \ \ \forall X\in(x_{(\ell,d)},C].$

######  Definition 2.

We say a fluid strategy profile $\Sigma$ is an exact equilibrium, with respect
to a fixed pricing and matching policy, if the incentive compatibility
conditions (8) are satisfied from every market state. $\Sigma$ is an
$\epsilon$-approximate equilibrium if the approximate incentive compatibility
conditions (9) are satisfied from any market state.

##  3 Optimal Centralized Solution for the Stochastic Fluid Model

In this section we construct an optimization problem to obtain the welfare-
optimal movement of drivers for the stochastic fluid model, ignoring strategic
aspects of the problem and assuming that all drivers can be routed by a
centralized planner. We refer to this problem as the fluid optimization
problem.

The fluid optimization problem resembles a maximum-value flow problem over a
“stochastic flow network” in which drivers move across locations and scenarios
$\omega_{1},\omega_{2},\dots,\omega_{T}$ unfold as time progresses.

The fluid optimization problem solves for the welfare-optimal trip
specification from any market state $(\omega_{t},\mathbf{S}_{t})$. Let
$\Phi_{\omega_{t}}:\mathcal{S}\to\mathbb{R}$ be a function such that
$\Phi_{\omega_{t}}(\mathbf{S}_{t})$ gives the optimal expected welfare that
can be achieved in the fluid model starting from the market state
$(\omega_{t},\mathbf{S}_{t})$ at time $t$.

We define $\Phi_{\omega_{t}}$ via backwards induction. For the base case, let
$\Phi_{\omega_{T+1}}(\cdot)=0$. Fix any time period $t$ and assume that
$\Phi_{\omega_{t+1}}$ has already been defined for all time $t+1$ scenarios
$\omega_{t+1}$. We define $\Phi_{\omega_{t}}(\mathbf{S}_{t})$ to be the value
of the optimization problem stated below in (10):

$\displaystyle\Phi_{\omega_{t}}(\mathbf{S})\equiv\ \ \ \
\;\;\;\sup_{\bm{f},\bm{g}}$ $\displaystyle\ \ \
\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})$ (10) subject to $\displaystyle
f_{(\ell,d)}\geq 0\ $ $\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (11)
$\displaystyle g_{(\ell,d)}\geq 0\ $
$\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (12) $\displaystyle
f_{(\ell,d)}\geq g_{(\ell,d)}\ $
$\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (13)
$\displaystyle\sum_{d\in\mathcal{L}}f_{(\ell,d)}=S_{\ell}$
$\displaystyle\forall\ell\in\mathcal{L}.$ (14)

The decision variables in (10) are the pair of vectors $(\bm{f},\bm{g})$,
where $\bm{f}=(f_{(\ell,d)}:(\ell,d)\in\mathcal{L}^{2})$ encodes the total
trip volumes along each route and
$\bm{g}=(g_{(\ell,d)}:(\ell,d)\in\mathcal{L}^{2})$ encodes the dispatch trip
volumes along each route. We use the notation

$F^{*}_{\omega_{t}}(\mathbf{S})=\\{(\bm{f},\bm{g})\mbox{ satisfying
(\ref{eq:f_nonneg_} -
\ref{eq:flow_conservation_})},\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\Phi_{\omega_{t}}(\mathbf{S})\\}$

to mean the set of optimal solutions with respect to
$(\omega_{t},\mathbf{S}_{t})$.

The objective function has two components:

$\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})+\mathcal{U}_{\omega_{t}}^{>t}(\bm{f}).$

The second component $\mathcal{U}_{\omega_{t}}^{>t}(\bm{f})$ gives the
expected total welfare achievable over all future time periods starting from
time $t+1$, as a function of the total trip volumes $\bm{f}$ taken in the
current time period. It is defined via

$\mathcal{U}^{>t}_{\omega_{t}}(\bm{f})=\mathbb{E}\left[\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}))\mid\omega_{t}\right].$
(15)

The expectation is taken over the scenario $\omega_{t+1}$ given the time $t$
scenario $\omega_{t}$. Recall that $\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f})$
is a deterministic function, specified in equation (7), that gives the time
$t+1$ supply location vector as a function of the total trip volumes $\bm{f}$.

The first component of the objective function,
$\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})$, gives the total welfare generated
by the trips $(\bm{f},\bm{g})$ in time period $t$.
$\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})$ is defined by the following
equation:

$\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})=\sum_{(\ell,d)\in\mathcal{L}^{2}}U_{(\ell,d,\omega_{t})}(g_{(\ell,d)})-\sum_{(\ell,d)\in\mathcal{L}^{2}}c_{(\ell,d,\omega_{t})}f_{(\ell,d)}-\sum_{\ell}A(\bm{g}^{T}\mathbf{1}_{\ell},\bm{f}^{T}\mathbf{1}_{\ell}),$
(16)

where $U_{(\ell,d,\omega_{t})}(g_{(\ell,d)})$ is the maximum utility generated
by serving $g_{(\ell,d)}$ dispatch trips,
$-c_{(\ell,d,\omega_{t})}f_{(\ell,d)}$ is the constant cost incurred by all
drivers who drive from $\ell$ to $d$, and
$A(\bm{g}^{T}\mathbf{1}_{\ell},\bm{f}^{T}\mathbf{1}_{\ell})$ is the add-
passenger disutility incurred by all drivers from $\ell$ who serve a dispatch.

In writing the add-passenger disutility cost function, we adopt the convention
that $\mathbf{1}_{\ell}$ is a vector indexed by routes
$(\ell,d)\in\mathcal{L}^{2}$ that takes the value $1$ on components where the
origin location is $\ell$ and $0$ otherwise. With this convention,
$\bm{g}^{T}\mathbf{1}_{\ell}$ specifies the total volume of drivers at $\ell$
who serve a dispatch, and $\bm{f}^{T}\mathbf{1}_{\ell}$ specifies the total
volume of drivers at $\ell$ in total.

The minimum disutility we can incur by serving $\bm{g}^{T}\mathbf{1}_{\ell}$
dispatches is to select drivers positioned at $\ell$ whose add-passenger
disutility falls in the bottom
$\frac{\bm{g}^{T}\mathbf{1}_{\ell}}{\bm{f}^{T}\mathbf{1}_{\ell}}$ quantile of
the disutility distribution. Recall that the add-passenger disutility follows
a $\mathrm{Uniform}(0,C)$ distribution in each time period. So the best
quantile results when drivers use the cutoff
$x_{(\ell,d)}=(1-\frac{\bm{g}^{T}\mathbf{1}_{\ell}}{\bm{f}^{T}\mathbf{1}_{\ell}})C$,
resulting in an idiosyncratic disutility cost function which is 0 when
$\bm{f}^{T}\mathbf{1}_{\ell}=0$, and otherwise can be expressed as:

$\displaystyle A(\bm{g}^{T}\mathbf{1}_{\ell},\bm{f}^{T}\mathbf{1}_{\ell})$
$\displaystyle=\bm{g}^{T}\mathbf{1}_{\ell}\left(\frac{C}{2}\frac{\bm{g}^{T}\mathbf{1}_{\ell}}{\bm{f}^{T}\mathbf{1}_{\ell}}\right)=\frac{C\left(\bm{g}^{T}\mathbf{1}_{\ell}\right)^{2}}{2\bm{f}^{T}\mathbf{1}_{\ell}}.$
(17)

To define the function $U_{(\ell,d,\omega_{t})}(g)$, which specifies the total
rider welfare generated as a function of the dispatch volume $g$, we first
derive the rider-side price maximizing welfare along that route. Recall that
$\bar{D}_{(\ell,d,\omega_{t})}$ riders arrive for a trip from $\ell$ to $d$
under the scenario $\omega_{t}$. For the sake of notational simplicity we
don’t explicitly include a constraint that the dispatch-volume $g_{(\ell,d)}$
cannot exceed rider demand $\bar{D}_{(\ell,d,\omega_{t})}$. instead, we
incorporate rider demand volume into the objective function. If the dispatch
volume is smaller than the total volume of riders, then the maximum utility is
generated when the price selects for the upper
$\frac{g_{(o,d,\omega_{t})}}{\bar{D}_{(o,d,\omega_{t})}}$ quantile of
potential riders to request a dispatch. If the dispatch volume is larger than
the volume of riders then the price should select for all available riders.
Thus, the welfare-optimal price as a function of the dispatch-volume $g$ can
be written as follows:

$P_{(\ell,d,\omega_{t})}(g)=\begin{cases}F_{(\ell,d,\omega_{t})}^{-1}\left(1-\frac{g}{\bar{D}_{(\ell,d,\omega_{t})}}\right)&\mbox{if
}g\leq\bar{D}_{(\ell,d,\omega_{t})},\\\ 0&\mbox{otherwise},\end{cases}$ (18)

where $F_{(o,d,\omega_{t})}$ is the distribution function for the rider value
distribution of riders from $\ell$ to $d$ under $\omega_{t}$. We are now ready
to specify the reward function $U_{(\ell,d,\omega_{t})}(g)$:

$U_{(\ell,d,\omega_{t})}(g)=\begin{cases}\min(g,\bar{D}_{(\ell,d,\omega_{t})})\mathbb{E}[V\mid
V\geq P_{(\ell,d,\omega_{t})}(g)]&\mbox{if }g\geq 0,\\\ V_{max}g&\mbox{if
}g<0,\end{cases}$ (19)

where $V$ is a rider willingness-to-pay random variable with distribution
function $F_{(\ell,d,\omega_{t})}$, and where $V_{max}$ is the smallest value
for which $F_{(\ell,d,\omega_{t})}(V_{max})=1$. The following Lemma
characterizes the derivative of each utility function
$U_{(o,d,\omega_{t})}(\cdot,\cdot)$:

######  Lemma 1.

Consider the reward function $U_{(\ell,d,\omega_{t})}$ associated with any
route $(\ell,d)\in\mathcal{L}^{2}$ and any scenario $\omega_{t}$. Assume the
rider-value distribution $F_{(\ell,d,\omega_{t})}$ satisfies Assumption 2.
Then $U_{(\ell,d,\omega_{t})}(g)$ is concave in $g$, is differentiable at
every $g\in\mathbb{R}$, and the derivative at each $g\in\mathbb{R}$ satisfies:

$\frac{d}{dg}U_{(\ell,d,\omega_{t})}(g)=\begin{cases}P_{(\ell,d,\omega_{t})}(g)&\mbox{if
}g\geq 0,\\\ V_{max}&\mbox{if }g<0.\end{cases}$

Moreover, the fluid optimization problem (10) has a concave objective function
for any market state.

We defer the proof of Lemma 1 to Appendix D.1. Next, we state a Lemma
characterizing the optimality conditions for the optimization problem (10). We
defer the proof of Lemma 2 to Appendix D.3.

######  Lemma 2.

Let $(\omega_{t},\mathbf{S}_{t})$ be any market state and let
$\bm{f},\bm{g}\in\mathbb{R}_{+}^{\mathcal{L}^{2}}$ be any feasible solution to
the fluid optimization problem (10) with respect to
$(\omega_{t},\mathbf{S}_{t})$. Then $(\bm{f},\bm{g})$ is an optimal solution
if and only if there exist dual variables
$\alpha_{(\ell,d)},\beta_{(\ell,d)},\gamma_{(\ell,d)}\geq 0$ for all
$(\ell,d)\in\mathcal{L}^{2}$, and $\eta_{\ell}\in\mathbb{R}$ for all
$\ell\in\mathcal{L}$, for which the following conditions are satisfied:

  1. 1.

Complementary Slackness:

$\forall(\ell,d)\in\mathcal{L}^{2},\ \ f_{(\ell,d)}\alpha_{(\ell,d)}=0,\ \ \
g_{(\ell,d)}\beta_{(\ell,d)}=0,\ \ \
(g_{(\ell,d)}-f_{(\ell,d)})\gamma_{(\ell,d)}=0.$

  2. 2.

Stationarity. For all $(\ell,d)\in\mathcal{L}^{2}$, if the volume of drivers
$S_{\ell}$ at $\ell$ is larger than $0$ then the following equations hold:

$\displaystyle
P_{(\ell,d)}(g_{(\ell,d)})-C\frac{\bm{g}^{T}\mathbf{1}_{\ell}}{\bm{f}^{T}\mathbf{1}_{\ell}}$
$\displaystyle=\gamma_{(\ell,d)}-\beta_{(\ell,d)}.$ (20) $\displaystyle-
c_{(\ell,d)}+\frac{C}{2}\left(\frac{\bm{g}^{T}\mathbf{1}_{\ell}}{\bm{f}^{T}\mathbf{1}_{\ell}}\right)^{2}$
$\displaystyle=\eta_{\ell}-\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}^{>t}_{\omega_{t}}(\bm{f})-\alpha_{(\ell,d)}-\gamma_{(\ell,d)}.$
(21)

In equation (21) above, $\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}^{>t}_{\omega_{t}}(\bm{f})$ is the partial derivative
of the future welfare function $\mathcal{U}^{>t}_{\omega_{t}}(\bm{f})$ (see
equation 15) with respect to the total trip volume along route $(\ell,d)$.
From the definition of the future welfare function, we have the following
equality:

$\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}^{>t}_{\omega_{t}}(\bm{f})=\mathbb{E}_{\omega_{t+1}}\left[\frac{\partial}{\partial
f_{(\ell,d)}}\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}))\mid\omega_{t}\right],$

where $\Phi_{\omega_{t+1}}(\cdot)$ is the optimal welfare achievable from
scenario $\omega_{t+1}$ as a function of the supply locations
$\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f})$.

The following Lemma characterizes the partial derivatives of
$\Phi_{\omega_{t}}(\mathbf{S})$ in terms of dual variables.

######  Lemma 3.

Fix a time-scenario $\omega_{t}$ and let $\mathbf{S}=(S_{\ell}\geq
0:\ell\in\mathcal{L})$ be any supply-location vector. Pick any location $\ell$
for which the volume of supply at $\ell$ is nonzero under $\mathbf{S}$, i.e.
$S_{\ell}>0$.

  1. 1.

For the state-dependent optimization problem with respect to $\mathbf{S}$ the
value of any optimal dual variable associated with the flow conservation
constraint for location $\ell$ is unique. That is there exists a number
$\eta_{\ell}^{*}$ such that $\eta_{\ell}=\eta_{\ell}^{*}$, where $\eta_{\ell}$
is the $\ell$th component of $\bm{\eta}$ for any optimal dual variables
$(\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta})\in D^{*}(\mathbf{S})$.

  2. 2.

The state dependent optimization function $\Phi_{\omega_{t}}(\cdot)$ is
differentiable with respect to $S_{\ell}$ at the supply location vector
$\mathbf{S}$. Moreover, the partial derivative is equal to the value of the
optimal dual variable for the flow conservation constraint at location $\ell$:

$\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S})=\eta_{\ell}^{*}.$

  3. 3.

The partial derivative $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S})$ is continuous at $\mathbf{S}$.

Lemma 3 concerns partial derivatives of the state-dependent optimization
function assuming the volume of drivers $S_{\ell}$ at location $\ell$ is
larger than $0$. Notice that, if the supply volume $S_{\ell}$ is strictly
smaller than $0$, then the feasible region for the state-dependent
optimization problem is empty and the optimal value is $-\infty$. Therefore,
the state-dependent optimization function $\Phi_{\omega_{t}}(\cdot)$ is only
finite for supply-location vectors which are nonnegative in every component.

It will be useful for us to extend our understanding of the partial derivative
$\frac{\partial}{\partial S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S})$ to supply-
location vectors which lie on the boundary of the domain, i.e. where
$S_{\ell}=0$. For supply-location vectors $\mathbf{S}$ where $S_{\ell}$ is $0$
we will take $\frac{\partial}{\partial S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S})$
to mean the sequence of derivatives of $\mathbf{S}+h\mathbf{1}_{\ell}$ as $h$
goes to $0$ from above:

$\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}^{+})=\lim_{h\downarrow
0}\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}+h\mathbf{1}_{\ell}),$

where $\mathbf{1}_{\ell}$ represents a vector indexed by locations
$\mathcal{L}$ with a $1$ in the $\ell$ component and $0$ everywhere else. In a
slight abuse of notation we will write

$\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S})=\begin{cases}\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S})&\mbox{if }S_{\ell}>0,\\\
\frac{\partial}{\partial S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}^{+})&\mbox{if
}S_{\ell}=0,\end{cases}$ (22)

for any supply-location vector $\mathbf{S}$ with nonnegative components. The
following Lemma states that the right derivative $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}^{+})$ is well-defined for points on the
boundary, and also that the partial derivative is continuous over all supply-
location vectors with nonnegative components.

######  Lemma 4.

Let $\mathbf{S}$ be a supply-location vector with nonnegative components and
assume $S_{\ell}=0$ for some location $\ell$. Then the right-derivative
$\frac{\partial}{\partial S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}^{+})$ is well-
defined at $\mathbf{S}$. Moreover, the partial derivative function
$\frac{\partial}{\partial S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S})$, defined in
(22), is continuous over the set
$\\{\mathbf{S}\in\mathbb{R}^{\mathcal{L}}:S_{\ell}\geq
0\forall\ell\in\mathcal{L}\\}$.

We defer the proof of Lemma 3 and Lemma 4 to Appendix D.

##  4 The Stochastic Spatiotemporal Pricing Mechanism

In this section we describe our main algorithmic contribution, which we refer
to as the stochastic spatiotemporal pricing (SSP) mechanism. The SSP mechanism
re-solves the fluid optimization problem based on the observed market state in
each time period and derives its prices and matching decisions from the
computed optimum.

The SSP pricing policy is the same algorithm in both the fluid model and the
two level model. It is formally defined below, in Definition 3.

######  Definition 3.

At each time period $t$, the SSP pricing policy observes the market state
$(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}$ and computes the price along
each route $(\ell,d)$ to be

$P_{(\ell,d)}=P_{(\ell,d,\omega_{t})}(g^{*}_{(\ell,d)})=F_{(\ell,d,\omega_{t})}^{-1}\left(1-\frac{g^{*}_{(\ell,d)}}{\bar{D}_{(\ell,d,\omega_{t})}}\right),$

where $(\bm{f}^{*},\bm{g}^{*})\in F^{*}_{\omega_{t}}(\mathbf{S}_{t})$ is an
optimal solution for the associated fluid optimization problem.

For brevity, we defer the exact definition of the SSP matching process to
Appendix E.1. For the arguments below, it is important to note only that the
matching process satisfies two properties: 1) it attempts to serve all
dispatches, and only fails to do so if too many drivers decline dispatches,
and 2) the only problem instances where the matching process results in
dispatch volume $g_{(\ell,d)}$ strictly smaller than the optimal dispatch
volume $g^{*}_{(\ell,d)}$ are those where drivers use a threshold
$x_{(\ell,d)}$ strictly smaller than the acceptance threshold implied by the
optimal solution.

###  4.1 Incentive Compatibility of the Fluid Optimal Solution

Our first result in this section shows that, under the SSP pricing mechanism,
the optimal trips and acceptance thresholds obtained from an optimal solution
to the fluid optimization problem form an equilibrium.

Let $\Sigma^{*}=(\Sigma_{1}^{*},\dots,\Sigma_{T}^{*})$ be the fluid strateegy
profile that maps market states $(\omega_{t},\mathbf{S}_{t})$ to thresohlds
$\bm{x}$ and relocation distributions which correspond to the same optimal
solution $(\bm{f}^{*},\bm{g}^{*})$ that the SSP mechanism uses to set prices.
That is, when $(\bm{x},\mathbf{e})=\Sigma_{t}^{*}(\omega_{t},\mathbf{S}_{t})$,
then, for every route $(\ell,d)\in\mathcal{L}^{2}$, we mean

$x_{(\ell,d)}=\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{S_{\ell}}C$

and

$e_{(\ell,d)}=\frac{f_{(\ell,d)}-g_{(\ell,d)}}{S_{\ell}-\bm{g}^{*T}\mathbf{1}_{\ell}}.$

We also define a variant of this strategy profile which follows the fluid
optimal solutions for the stochastic two-level model with population size $k$.
Let $\Pi^{(k)}$ be the strategy profile where drivers select their thresholds
and relocation destinations using the fluid optimal strategy $\Sigma^{*}$.
Specifically, at time $t$ with market state $(\omega_{t},\mathbf{S}_{t})$, a
driver $i$ positioned at location $\ell$ selects their action by first
computing $(\bm{x},\mathbf{e})=\Sigma_{t}^{*}(\omega_{t},\mathbf{S}_{t})$ The
driver uses acceptance thresholds
$\bm{x}_{i}=\bm{x}_{\ell}=(x_{(\ell,d)}:d\in\mathcal{L})$ as their threshold
vector. The drivers at each location $\ell$ collectively choose their
relocation destination so that the fraction of drivers choosing each
relocation destination is as close as possible to the fraction prescribed by
the fluid relocation distribution
$\mathbf{e}_{\ell}=(e_{(\ell,d)}:d\in\mathcal{L})$.

We start by proving a Lemma which characterizes the value function of the
strategy $\Sigma^{*}$.

######  Lemma 5.

Let $\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})$ be the value function
associated with the strategy profile $\Sigma^{*}$, for a location $\ell$ and
market state $(\omega_{t},\mathbf{S}_{t})$. When the SSP mechanism is used to
set prices in the stochastic fluid model, the value function satisfies

$\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})=\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{t}),$ (23)

where $\Phi_{\omega_{t}}(\mathbf{S}_{t})$ is the state-dependent optimal
welfare function.

###### Proof.

We prove (23) via backwards induction. Fix a time period $t$ and assume that
the value function at the next time period $t+1$ satisfies equation (23) for
any time $t+1$ market state.

Let $(\omega_{t},\mathbf{S}_{t})$ be any time $t$ market state, and let
$(\bm{f}^{*},\bm{g}^{*})\in F_{\omega_{t}}^{*}(\mathbf{S}_{t})$ be the optimal
fluid solution that the SSP mechanism uses to set prices, and that the
strategy profile $\Sigma^{*}$ uses to determine its actions.

Let $(\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta})$ be dual variables
certifying the optimality of $(\bm{f}^{*},\bm{g}^{*})$. In Lemma 3, we show
that the dual variables $\bm{\eta}$, which are associated with the flow-
conservation constraint for each location $\ell$, are equal to the partial
derivative of the state-dependent optimization function, i.e.
$\eta_{\ell}=\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{t})$. Therefore, to finish the proof of
equation (23), it suffices to show that
$\eta_{\ell}=\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})$. We proceed with
the following equations, which start from the definition of the value
function:

$\displaystyle\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})$
$\displaystyle=\frac{1}{S_{\ell}}\left[\sum_{d\in\mathcal{L}}(f^{*}_{(\ell,d)}-g^{*}_{(\ell,d)})\mathcal{Q}_{t}(\ell,d,0)+g^{*}_{(\ell,d)}\mathcal{Q}_{t}(\ell,d,1,\frac{x_{(\ell,d)}}{2})\right]$
$\displaystyle=\frac{1}{S_{\ell}}\left[\sum_{d\in\mathcal{L}}f^{*}_{(\ell,d)}\mathcal{Q}_{t}(\ell,d,0)+g^{*}_{(\ell,d)}\left(P_{(\ell,d)}-\frac{x_{(\ell,d)}}{2}\right)\right],$

where $\mathcal{Q}_{t}(\ell,d,0)$ is the Q value associated with a relocation
trip from $\ell$ to $d$, $\mathcal{Q}_{t}(\ell,d,1,\frac{x_{(\ell,d)}}{2})$ is
the Q value associated with a dispatch trip from $\ell$ to $d$, with respect
to the average pickup disutility $\frac{x_{(\ell,d)}}{2}$. Recall that the
disutility threshold $x_{(\ell,d)}$ used by the strategy profile $\Sigma^{*}$
is equal to
$x_{(\ell,d)}=C\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}$.
Therefore the following equation holds, continuing from our earlier algebra:

$\displaystyle\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})$
$\displaystyle=\frac{1}{S_{\ell}}\left[\sum_{d\in\mathcal{L}}f^{*}_{(\ell,d)}\mathcal{Q}_{t}(\ell,d,0)+g^{*}_{(\ell,d)}\frac{C}{2}\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}+g^{*}_{(\ell,d)}\left(P_{(\ell,d)}-C\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)\right].$

The stationarity optimality condition (20) states
$P_{(\ell,d)}-C\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}=\gamma_{(\ell,d)}-\beta_{(\ell,d)}$.
The complementary slackness conditions also state
$g^{*}_{(\ell,d)}(\gamma_{(\ell,d)}-\beta_{(\ell,d)})=f^{*}_{(\ell,d)}\gamma_{(\ell,d)}$,
as well as $f^{*}_{(\ell,d)}\alpha_{(\ell,d)}=0$. Therefore,

$\displaystyle\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})$
$\displaystyle=\frac{1}{S_{\ell}}\left[\sum_{d\in\mathcal{L}}f^{*}_{(\ell,d)}\mathcal{Q}_{t}(\ell,d,0)+g^{*}_{(\ell,d)}\frac{C}{2}\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}+g^{*}_{(\ell,d)}\left(\gamma_{(\ell,d)}-\beta_{(\ell,d)}\right)\right]$
$\displaystyle=\frac{1}{S_{\ell}}\left[\sum_{d\in\mathcal{L}}f^{*}_{(\ell,d)}(\mathcal{Q}_{t}(\ell,d,0)+\gamma_{(\ell,d)}+\alpha_{(\ell,d)})+g^{*}_{(\ell,d)}\frac{C}{2}\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right]$
$\displaystyle=\frac{1}{S_{\ell}}\left[\sum_{d\in\mathcal{L}}f^{*}_{(\ell,d)}(\mathcal{Q}_{t}(\ell,d,0)+\gamma_{(\ell,d)}+\alpha_{(\ell,d)})\right]+\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{S_{\ell}}\right)\frac{C}{2}\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}$
$\displaystyle=\frac{1}{S_{\ell}}\left[\sum_{d\in\mathcal{L}}f^{*}_{(\ell,d)}(\mathcal{Q}_{t}(\ell,d,0)+\gamma_{(\ell,d)}+\alpha_{(\ell,d)})\right]+\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}$
$\displaystyle=\frac{1}{S_{\ell}}\left[\sum_{d\in\mathcal{L}}f^{*}_{(\ell,d)}\left(\mathcal{Q}_{t}(\ell,d,0)+\gamma_{(\ell,d)}+\alpha_{(\ell,d)}+\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}\right)\right]$
(24)

The stationarity condition (21) states that, for any destination $d$

$-c_{(\ell,d)}+\frac{C}{2}\left(\frac{\bm{g}^{T}\mathbf{1}_{\ell}}{\bm{f}^{T}\mathbf{1}_{\ell}}\right)^{2}+\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}^{>t}_{\omega_{t}}(\bm{f}^{*})+\alpha_{(\ell,d)}+\gamma_{(\ell,d)}=\eta_{\ell}.$

Lemma 3 and our backwards induction assumption characterizes the partial
derivative as

$\displaystyle\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}^{>t}_{\omega_{t}}(\bm{f}^{*})$
$\displaystyle=\mathbb{E}_{\omega_{t+1}}\left[\frac{\partial}{\partial
f_{(\ell,d)}}\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{*}))\mid\omega_{t}\right]$
$\displaystyle=\mathbb{E}_{\omega_{t+1}}\left[\mathcal{V}_{t+1}(d,\omega_{t+1},\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{*}))\mid\omega_{t}\right].$

Therefore, the dual variable $\eta_{\ell}$ can be written as

$\eta_{\ell}=\mathcal{Q}_{t}(\ell,d,0)+\frac{C}{2}\left(\frac{\bm{g}^{T}\mathbf{1}_{\ell}}{\bm{f}^{T}\mathbf{1}_{\ell}}\right)^{2}+\alpha_{(\ell,d)}+\gamma_{(\ell,d)}.$

Plugging the above in to the expression (24), we obtain

$\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})=\frac{1}{S_{\ell}}\sum_{d\in\mathcal{L}}f^{*}_{(\ell,d)}\eta_{\ell}=\eta_{\ell},$

establishing our backwards induction hypothesis and finishing the proof of
equation (23).

∎

######  Lemma 6.

Let $\mathcal{Q}_{t}$ be the Q values associated with the strategy profile
$\Sigma^{*}$. Let $t$ be any time period and $(\omega_{t},\mathbf{S}_{t})$ be
any market state. Let $(\bm{f}^{*},\bm{g}^{*})\in
F_{\omega_{t}}^{*}(\mathbf{S}_{t})$ be the optimal fluid solution that the SSP
mechanism uses to set prices, and that the strategy profile $\Sigma^{*}$ uses
to determine its actions. Let $(\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta})$
be dual variables certifying the optimality of $(\bm{f}^{*},\bm{g}^{*})$. Let
$\ell\in\mathcal{L}$ be any location. When the SSP mechanism is used to set
prices, we have the following upper bound on the Q value of any relocation
trip originating from $\ell$:

$\eta_{\ell}-\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}\geq\max_{d}\mathcal{Q}_{t}(\ell,d,0).$
(25)

Moreover, if any drivers at $\ell$ take a relocation trip towards $d$, i.e. if
$f^{*}_{(\ell,d)}>g^{*}_{(\ell,d)}$, then

$\eta_{\ell}-\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}=\mathcal{Q}_{t}(\ell,d,0).$
(26)

Finally, if there are any drivers at $\ell$ who take a relocation trip, i.e.
if $\bm{g}^{*T}\mathbf{1}_{\ell}<\bm{f}^{*T}\mathbf{1}_{\ell}$, then for all
destinations $d$ where $g^{*}_{(\ell,d)}>0$ we have

$\mathcal{Q}_{t}(\ell,d,1,x_{(\ell,d)})=\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0)=\eta_{\ell}-\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}.$
(27)

###### Proof.

For any destination $d$, the stationarity condition (21) states that

$\eta_{\ell}=\mathcal{Q}_{t}(\ell,d,0)+\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}+\alpha_{(\ell,d)}+\gamma_{(\ell,d)}.$

Rearranging,

$\eta_{\ell}-\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}=\mathcal{Q}_{t}(\ell,d,0)+\alpha_{(\ell,d)}+\gamma_{(\ell,d)}.$

The upper bound (25) follows from the fact that $\alpha_{(\ell,d)}$ and
$\gamma_{(\ell,d)}$ are nonnegative.

To establish (26), consider any destination $d\in\mathcal{L}$ where
$f^{*}_{(\ell,d)}>g^{*}_{(\ell,d)}$. Then by the complementary slackness
conditions $f^{*}_{(\ell,d)}\alpha_{(\ell,d)}=0$ we know that
$\alpha_{(\ell,d)}=0$ must be satisfied, and by
$(g^{*}_{(\ell,d)}-f^{*}_{(\ell,d)})\gamma_{(\ell,d)}=0$ we know
$\gamma_{(\ell,d)}=0$ must be satisfied.

To establish (27), first observe the condition
$\bm{g}^{*T}\mathbf{1}_{\ell}<\bm{f}^{*T}\mathbf{1}_{\ell}$ guarantees the
existence of at least one destination $d$ where
$g^{*}_{(\ell,d)}<f^{*}_{(\ell,d)}$, so equation (26) guarantees
$\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0)=\eta_{\ell}-\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}$.
Next, consider any destination $d$ where $g^{*}_{(\ell,d)}>0$. The
stationarity condition (20) states

$P_{(\ell,d)}-x_{(\ell,d)}+\beta_{(\ell,d)}=\gamma_{(\ell,d)},$

and since $g^{*}_{(\ell,d)}>0$, complementary slackness provides us
$\beta_{(\ell,d)}=0$. Therefore, starting from the stationarity condition
(21), we obtain

$\eta_{\ell}=\mathcal{Q}_{t}(\ell,d,0)+\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}+P_{(\ell,d)}-x_{(\ell,d)}.$

Observing that
$\mathcal{Q}_{t}(\ell,d,0)+P_{(\ell,d)}-x_{(\ell,d)}=\mathcal{Q}_{t}(\ell,d,1,x_{(\ell,d)})$
establishes (27).

∎

We are now ready to state and prove our main theorem, which states that the
fluid optimal strategy profile $\Sigma^{*}$ is an equilibrium under the SSP
prices.

######  Theorem 1.

The following statements are true:

  1. 1.

When the SSP mechanism is used to set prices in the stochastic fluid model,
the strategy profile $\Sigma^{*}$ is an exact equilibrium.

  2. 2.

There exist nonnegative sequences $(\epsilon_{k}:k\geq 1)$ and
$(\delta_{k}:k\geq 1)$, both converging to $0$ as $k\to\infty$, such that when
the SSP mechanism is used to set prices in the stochastic two-level model with
population-size $k$, then $\Pi^{(k)}$ is an $(\epsilon_{k},\delta_{k})$
equilibrium.

###### Proof.

We present the proof of Theorem 1 part 1 below, and defer the proof of part 2
to Appendix A. Let $(\omega_{t},\mathbf{S}_{t})$ be any time $t$ market state,
and let $(\bm{f}^{*},\bm{g}^{*})\in F_{\omega_{t}}^{*}(\mathbf{S}_{t})$ be the
optimal fluid solution that the SSP mechanism uses to set prices, and that the
strategy profile $\Sigma^{*}$ uses to determine its actions. Let
$(\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta})$ be dual variables certifying
the optimality of $(\bm{f}^{*},\bm{g}^{*})$.

To show that $\Sigma^{*}$ is an equilibrium we have to show that no drivers
have an incentive to deviate.

First, we show that no driver has incentive to deviate from a relocation trip
to another relocation trip. Indeed, if there exists a destination $d$ where
drivers are taking a relocation trip, i.e. where
$f^{*}_{(\ell,d)}>g^{*}_{(\ell,d)}$, then Lemma 6 shows
$\mathcal{Q}_{t}(\ell,d,0)=\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0).$

Next, we show that no driver declines a dispatch that they would have
preferred to take. Let $\ell$ be the origin location and let $d$ be the
destination that the driver declines to take. If a driver declines a dispatch
then that means they are taking a relocation trip, so
$\bm{g}^{*T}\mathbf{1}_{\ell}<\bm{f}^{*T}\mathbf{1}_{\ell}$. Therefore, Lemma
6 states
$\mathcal{Q}_{t}(\ell,d,1,x_{(\ell,d)})=\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0)$.
Any driver who declines a dispatch towards $d$ has add-passenger disutility
$X$ larger than the threshold $x_{(\ell,d)}$, so the Q value
$\mathcal{Q}_{t}(\ell,d,1,X)$ is smaller than the optimal relocation-trip
utility that they do collect.

Finally, we show that no driver who accepts a dispatch would prefer to take a
relocation trip. This also follows from Lemma 6, which shows
$\mathcal{Q}_{t}(\ell,d,1,x_{(\ell,d)})\geq\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0)$
always holds. Any driver who accepts a dispatch trip from $\ell$ to $d$ has
add-passenger disutility $X$ smaller than the threshold $x_{(\ell,d)}$.
Therefore, the utility they collect $\mathcal{Q}_{t}(\ell,d,1,X)$ is larger
than the optimal relocation-trip utility that they could collect. ∎

###  4.2 Robustness of Equilibria Under the SSP Mechanism

Theorem 2, below, states our welfare-robustness theorem for the SSP mechanism
in the stochastic fluid model. Theorem 2’s proof is given in §4.3 with
additional details in Appendix B.

######  Theorem 2 (Welfare-robustness in the stochastic fluid model).

When the SSP mechanism is used to set prices in the stochastic fluid model,
every equilibrium strategy profile achieves optimal welfare, and every
$\epsilon$-equilibrium strategy achieves $\epsilon^{\prime}$-optimal welfare,
where $\epsilon^{\prime}$ goes to $0$ as $\epsilon$ goes to $0$.

Our welfare robustness theorem for the stochastic two-level model considers
approximate equilibria whose approximation error vanishes as the population
size grows large. We also restrict our attention to a subset of the state
space in which the total (normalized) volume of drivers in the network does
not exceed a constant. Let $\gamma>0$ be a constant, and for each time period
$t\in[T]$ define
$\mathcal{S}_{t}(\gamma)=\\{(\omega_{t},\mathbf{S}_{t})\in\Omega_{t}\times\mathcal{S}:\sum_{\ell}S_{\ell}\leq\gamma\\}$.
We assume that $\gamma$ is large enough so that the probability of the market
state belonging to $\mathcal{S}_{t}(\gamma)$ converges to $1$ as the
population size grows large, regardless of the strategy profile. This is
possible because there are only finitely many points at which drivers can
enter the network, and all the driver-entry random variables concentrate
around their mean as the population size grows, and these means grow linearly
in $k$ (see Assumption 1). Therefore, we can pick any $\gamma$ larger than the
maximum fluid driver volume over all scenarios.

Let $\alpha_{k}\geq 0$ be a sequence of error terms converging to $0$ as
$k\to\infty$, and for each $k\geq 1$ let $\mathcal{P}^{k}$ be the set of
$\alpha_{k}$-equilibrium strategy profiles for the two-level model with
population size $k$, over the state space $\mathcal{S}_{t}(\gamma)$.

For any strategy profile $\Pi$, let $W_{\omega_{t}}(\mathbf{S}_{t};\Pi,k)$
denote the normalized expected welfare achieved by $\Pi$ from the market state
$(\omega_{t},\mathbf{S}_{t})$ under the population size parameter $k$. A
formal definition of $W_{\omega_{t}}(\mathbf{S}_{t};\Pi,k)$ is given in
Appendix C.1.

Theorem 3, below, states our welfare-robustness theorem for the SSP mechanism
in the stochastic two-level model. We defer the proof of Theorem 3 to Appendix
C.

######  Theorem 3 (Approximate welfare-robustness in the stochastic two-level
model).

When the SSP mechanism is used to set prices in the stochastic two-level
model, every approximate equilibrium achieves approximately optimal welfare.

Specifically, there exists a sequence of error terms $\epsilon_{k}\geq 0$
converging to $0$ as $k\to\infty$ such that the following is true: for every
$k\geq 1$, every $\alpha_{k}$-approximate equilibrium $\Pi\in\mathcal{P}^{k}$,
and every market state $(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}(\gamma)$, we
have

$\Phi_{\omega_{t}}(\mathbf{S}_{t})-W_{\omega_{t}}(\mathbf{S}_{t};\Pi,k)\leq\epsilon_{k}.$

###  4.3 Proof of Theorem 2

We begin by proving the first part of Theorem 2, stating that equilibrium
fluid strategies achieve optimal welfare. Let $\Sigma$ be an equilibrium
strategy profile for the fluid model, meaning that the incentive compatibility
conditions (8) hold. Recall a fluid strategy profile is a sequence of
functions $\Sigma=(\Sigma_{1},\dots,\Sigma_{T})$ such that each $\Sigma_{t}$
maps market states $(\omega_{t},\mathbf{S}_{t})$ to a vector of disutility
thresholds and relocation distributions:
$(\bm{x},\mathbf{e})=\Sigma_{t}(\omega_{t},\mathbf{S}_{t})$. The matching
process takes as input the driver strategy $(\bm{x},\mathbf{e})$, the dispatch
volumes and the market state, and produces trip specifications
$(\bm{f},\bm{g})$.

For each $t$, let $\mathcal{V}_{t}$ and $\mathcal{Q}_{t}$ be the value
function and the Q-value function associated with $\Sigma$ at $t$.

We prove Theorem 2 by backward induction on $t$. Fix a period $t\leq T$ and
assume:

  1. 1.

$\Sigma$ achieves optimal welfare from every market state at time $t+1$.

  2. 2.

For any time $t+1$ state
$(\omega_{t+1},\mathbf{S}_{t+1})\in\mathcal{S}_{t+1}$, the value function for
any location $\ell$ satisfies:

$\mathcal{V}_{t+1}(\ell,\omega_{t+1},\mathbf{S}_{t+1})=\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1}).$ (28)

For the rest of this section we will write
$(\bm{g}^{\prime},\bm{f}^{\prime},\bm{x}^{\prime})$ to mean the trips and the
disutility thresholds used by the drivers in our arbitrary equilibrium, and we
will use $(\bm{g}^{*},\bm{f}^{*},\bm{x}^{*})$ to mean the optimal solution to
the fluid optimization problem and its associated disutility thresholds.

Where do the non-dispatched drivers go? We first show that the non-dispatched
drivers are incentivized to accept welfare-optimal trips, given any set of
dispatch trips. To show this we consider the optimization problem (29), which
depends on the vector $\bm{g}^{\prime}$ encoding the dispatch trips occurring
under our equilibrium and solves for the corresponding welfare-optimal trips
$\bm{f}$.

$\displaystyle\sup_{\bm{f}}$ $\displaystyle\ \ \
\sum_{(\ell,d)\in\mathcal{L}^{2}}-c_{(\ell,d)}f_{(\ell,d)}+\mathcal{U}_{\omega_{t}}^{>t}(\bm{f})$
(29) subject to $\displaystyle f_{(\ell,d)}\geq g^{\prime}_{(\ell,d)}\ $
$\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (30)
$\displaystyle\sum_{d\in\mathcal{L}}f_{(\ell,d)}=S_{\ell}\ $
$\displaystyle\forall\ell\in\mathcal{L}.$ (31)

where $\mathcal{U}_{\omega_{t}}^{>t}(\bm{f})$ is the future welfare function
(15). The following Lemma shows $\bm{f}^{\prime}$ is an optimal solution for
(29).

######  Lemma 7.

The total trip volumes $\bm{f}^{\prime}$ from our equilibrium is an optimal
solution for the relocation problem (29) with respect to the dispatch trips
$\bm{g}^{\prime}$. Moreover, dual variables certifying the optimality of
$\bm{f}^{\prime}$ are given by

$\lambda_{(\ell,d)}=\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0)-\mathcal{Q}_{t}(\ell,d,0),$
(32)

associated with the inequality constraint (30) for each $(\ell,d)$, and

$\eta_{\ell}=\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0)$ (33)

associated with the equality constraint (31) for each $\ell$.

###### Proof.

First, the complementary slackness conditions follow immediately from
incentive-compatibility properties. In particular, if a nonzero volume of
drivers take a relocation trip along $(\ell,d)$, i.e. if
$f^{\prime}_{(\ell,d)}-g^{\prime}_{(\ell,d)}>0$, then the incentive
compatibility conditions (8) state we must have

$\mathcal{Q}_{t}(\ell,d,0)=\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0),$

hence $(f^{\prime}_{(\ell,d)}-g^{\prime}_{(\ell,d)})\lambda_{(\ell,d)}=0$ is
satisfied for every route $(\ell,d)$.

It remains to check stationarity. We take the negative objective function to
convert (29) into a convex minimization problem, for compatibility with
standard definitions of the Lagrangian and associated optimality conditions.
The Lagrangian for this convex minimization problem is:

$L(\bm{f};\bm{\lambda},\bm{\eta})=c_{(\ell,d)}f_{(\ell,d)}-\mathcal{U}_{\omega_{t}}^{>t}(\bm{f})+\bm{\lambda}^{T}(\bm{g}^{\prime}-\bm{f})+\sum_{\ell}\eta_{\ell}\left(\sum_{d}f_{(\ell,d)}-S_{\ell}\right).$

The stationarity condition we must verify is that $0$ is the (sub-)gradient of
$L(\bm{f}^{\prime};\bm{\lambda},\bm{\eta})$. Our induction hypothesis (28)
yields

$\frac{\partial}{\partial
f^{\prime}_{(\ell,d)}}\mathcal{U}_{\omega_{t}}^{>t}(\bm{f}^{\prime})=\frac{\partial}{\partial
f^{\prime}_{(\ell,d)}}\mathbb{E}\left[\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{\prime}))\mid\omega_{t}\right]=\mathbb{E}\left[\frac{\partial}{\partial
f^{\prime}_{(\ell,d)}}\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{\prime}))\mid\omega_{t}\right].$

The derivative $\frac{\partial}{\partial
f^{\prime}_{(\ell,d)}}\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{\prime}))$
is the directional derivative of $\Phi_{\omega_{t+1}}$ evaluated at
$\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{\prime})$ as we increase the supply
at location $d$ (this is the effect on
$\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{\prime})$ of increasing the driver
flow $f^{\prime}_{(\ell,d)}$ from $\ell$ into $d$). By the induction
hypothesis, this directional derivative is
$\mathcal{V}_{t+1}(d;\omega_{t+1},\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{\prime}))$.

Thus,

$\frac{\partial}{\partial
f^{\prime}_{(\ell,d)}}\mathcal{U}_{\omega_{t}}^{>t}(\bm{f}^{\prime})=\mathbb{E}\left[\mathcal{V}_{t+1}(d;\omega_{t+1},\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{\prime}))\mid\omega_{t}\right]\\\
=\mathcal{Q}_{t}(\ell,d,0)+c_{(\ell,d)}.$

We evaluate the partial derivative of
$L(\bm{f}^{\prime};\bm{\lambda},\bm{\eta})$ at each coordinate
$f^{\prime}_{(\ell,d)}$:

$\displaystyle\frac{\partial}{\partial
f_{(\ell,d)}}L(\bm{f}^{\prime};\bm{\lambda},\bm{\eta})$
$\displaystyle=c_{(\ell,d)}-\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}_{\omega_{t}}^{>t}(\bm{f}^{\prime})-\lambda_{(\ell,d)}+\eta_{\ell}$
$\displaystyle=-\mathcal{Q}(\ell,d,0)-\lambda_{(\ell,d)}+\max_{d^{\prime}}\mathcal{Q}(\ell,d,0)$
$\displaystyle=0.$

Therefore $\bm{f}^{\prime}$ is an optimal solution for the problem (29). ∎

All equilibria serve all available dispatch demand. We proceed with the second
step of our proof, which is to show that all equilibria that arise under the
SSP prices must serve all available dispatch demand. Consider the optimum
solution $(\bm{g}^{*},\bm{f}^{*},\bm{x}^{*})$ and an arbitrary equilibrium
$(\bm{g}^{\prime},\bm{f}^{\prime},\bm{x}^{\prime})$ serves strictly fewer
dispatch trips than the corresponding optimum at some route. Recall that
$\bm{g}^{\prime}\leq\bm{g}^{*}$ on all routes, and that
$g^{\prime}_{(\ell,d)}<g^{*}_{(\ell,d)}$ on any route implies that
$x^{\prime}_{(\ell,d)}<x^{*}_{(\ell,d)}$. Based on our matching process of
drivers to passengers, it is no loss of generality to assume that drivers that
in the optimum should have accepted the passenger for a route $(\ell,d)$ were
offered this drive. To prove Theorem 2 we will use Lemma 7 on an auxiliary
networks that we construct next.

For all drivers that serve dispatches in the equilibrium, assume they start in
the next period at the destination of their current dispatch. For a location
$\ell$ where some route $(\ell,d)$ serves strictly fewer dispatch trips in
$\bm{g}^{\prime}$ then in $\bm{g}^{\prime*}$, if $\ell$ has $k$ routes
$(\ell,d)$ that had passengers to dispatch, we create $k$ copies of $\ell$,
each associated with one the the routes $(\ell,d)$, denoted by $\ell^{d}$. We
distribute the drivers from the equilibrium who started at location $\ell$
among the copies such that drivers who were offed dispatch $(\ell,d)$ will
start at location $\ell^{d}$, Note if there are unserved dispatches at
location $\ell$ than all drivers at $\ell$ were offered a dispatch. Each copy
$\ell^{d}$ is connected to the same set of nodes for the next period as $\ell$
with the same cost, but each has one additional possible route:
$(\ell^{d},d^{\prime})$ going to the same destination as the drive $d$, but
with a different cost. Suppose the price offered to the drivers was
$p_{\ell,d}$ and cutoff expected by our optimization is $x^{*}_{(\ell,d)}$,
and the cost of the drive is $c_{(\ell,d)}$ then this additional route will
have cost $c_{(\ell,d)}-p_{(\ell,d)}-x^{*}_{(\ell,d)}$.

First we construct the optimal solution
$(\bm{g}^{**},\bm{f}^{**},\bm{x}^{**})$ in this network, which is the same as
$(\bm{g}^{*},\bm{f}^{*},\bm{x}^{*})$ except drivers serving dispatches in the
equilibrium start only in the next period at the destination of their
dispatch, there are no dispatches available in period 1, so
$\bm{g}_{(\ell,d)}^{**}=0$ for the first period and $f^{**}$ includes all
additional dispatches that $\bm{f}^{*}$ would serve along the routes with the
new cost $c_{(\ell,d)}-p_{(\ell,d)}-x^{*}_{(\ell,d)}$, and $\bm{x}^{**}$ is
only for later periods of the problem. We call this the linearized problem
(where the first period values are linear). We first lemma this is an optimal
solution to the linearized program, with the same dual variables as the
original optimization problem.

######  Lemma 8.

The flow $(\bm{g}^{**},\bm{f}^{**},\bm{x}^{**})$ is an optimal solution to our
modified convex program, with optimal value $OPT^{**}$.

Second, for any route $(\ell,d)$ where not all dispatches are served, we can
replace $x^{*}_{(\ell,d)}$ with its equilibrium cutoff
$x^{\prime}_{(\ell,d)}$, this makes the cost lower, and hence the value of the
solution $(\bm{g}^{\prime\prime},\bm{f}^{\prime\prime},\bm{x}^{\prime\prime})$
is now strictly larger than $OPT^{\prime\prime}$.

######  Lemma 9.

The optimal solution to our modified convex program, using $x^{\prime}$ in
places of $x^{*}$ is strictly larger by at least
$\sum_{(\ell,d)}(g^{*}_{(\ell,d)}-g^{\prime}_{(\ell,d)})(x^{*}_{(\ell,d)}-x^{\prime}_{(\ell,d)})$
unless all dispatches are served.

Next consider the equilibrium solution
$(\bm{g}^{\prime},\bm{f}^{\prime},\bm{x}^{\prime})$ on the modified network.
To be precise, drivers who accepted dispatches again are starting in the next
period at the destination of the dispatch. All other drives either were not
offered dispatches or rejected their offer and choose an alternate drive
instead. We will call this
$(\bm{g}^{\prime\prime},\bm{f}^{\prime\prime},\bm{x}^{\prime\prime})$. The
resulting solution is an equilibrium of this network, and actually this is
true both with $x^{*}$ and with $x^{\prime}$ in our problem.

######  Lemma 10.

The flow $(\bm{g}^{\prime\prime},\bm{f}^{\prime\prime},\bm{x}^{\prime\prime})$
is an equilibrium on our modified network either with cost
$c_{(\ell,d)}-p_{(\ell,d)}-x^{*}_{(\ell,d)}$ or with costs
$c_{(\ell,d)}-p_{(\ell,d)}-x^{\prime}_{(\ell,d)}$ of the drives with modified
costs.

Now by Lemma 7 this equilibrium solution is optimal with both version of the
problem. Using $x^{*}$ to define cost we get the the equilibrium solution has
value $OPT^{**}$. However, using $x^{\prime}$ does not change the value of the
equilibrium, while the optimum increases by Lemma 9 unless all dispatches are
served.

All equilibria are welfare optimal. We now finish the backwards induction
proof. First, we claim that the thresholds $\bm{x}^{\prime}$ from our
arbitrary equilibrium have to equal the optimal thresholds $\bm{x}^{*}$
associated with the optimal solution $(\bm{f}^{*},\bm{g}^{*})$. This follows
from the fact we just established, that $\bm{g}^{\prime}=\bm{g}^{*}$. Consider
the case that all drivers at a location $\ell$ serve a dispatch. Then no
drivers can reject a dispatch, so it must be the case that
$x_{(\ell,d)}=x^{*}_{\ell}=C$ for all destinations $d$. Otherwise, consider
the case that some nonzero volume of drivers serve a relocation trip
originating from $\ell$. Then from Lemma 7, $\bm{f}^{\prime}$ and $\bm{f}^{*}$
are both optimal solutions for the problem (29). Let $\bm{\lambda}^{*}$ and
$\bm{\eta}^{*}$ be the dual variables (32) and (33) associated with the flow
$\bm{f}^{*}$. Let $d^{\prime}$ be the destination where
$f^{\prime}_{(\ell,d^{\prime})}>g^{\prime}_{(\ell,d^{\prime})}$. From the
equality $0=\frac{\partial}{\partial
f_{(\ell,d)}}L(\bm{f}^{\prime};\bm{\lambda}^{*},\bm{\eta}^{*})$ we conclude

$\max_{d}\mathcal{Q}_{t}(\ell,d,0)=\mathcal{Q}_{t}(\ell,d^{\prime},0)=\mathcal{Q}^{*}_{t}(\ell,d^{\prime},0)\leq\max_{d}\mathcal{Q}^{*}_{t}(\ell,d,0).$

Analogously, we can obtain the bound

$\max_{d}\mathcal{Q}^{*}_{t}(\ell,d,0)=\mathcal{Q}_{t}(\ell,d^{*},0)=\mathcal{Q}_{t}(\ell,d^{*},0)\leq\max_{d}\mathcal{Q}_{t}(\ell,d,0).$

Therefore the relocation utilities are the same under our arbitrary
equilibrium and the optimal solution. The incentive compatibility conditions
(8) give
$P_{(\ell,d)}-x_{(\ell,d)}=\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0),$
and we also have
$P_{(\ell,d)}-x^{*}_{\ell}=\max_{d^{\prime}}\mathcal{Q}^{*}_{t}(\ell,d^{\prime},0),$
therefore $x_{(\ell,d)}=x^{*}_{\ell}$ follows.

Therefore, the Q-values $\mathcal{Q}_{t}(\ell,d,0)$ and
$\mathcal{Q}_{t}(\ell,d,1,X)$ associated with our arbitrary equilibrium take
the same value as the Q-values $\mathcal{Q}^{*}_{t}(\ell,d,0)$ and
$\mathcal{Q}^{*}_{t}(\ell,d,1,X)$ associated with our optimal solution, which
implies the value function $\mathcal{V}_{t}(\ell;\omega_{t},\mathbf{S}_{t})$
is equal to the optimal value function
$\mathcal{V}^{*}_{t}(\ell;\omega_{t},\mathbf{S}_{t})$. But we know the optimal
value function is equal to $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{t})$, establishing the second and final
part of our backwards induction assumption.

We defer the proof of approximate welfare robustness in the fluid model to
Appendix B.

##  5 The Value of Re-Solving

The SSP mechanism changes prices based on drivers’ locations: in each period
$t$, the fluid optimization problem (10) used to set prices is re-solved using
drivers’ locations $\mathbf{S}_{t}$. Here we show that re-solving is
necessary, in the sense that Theorem 3’s robustness property vanishes without
it.

To show this, we consider a variant of the SSP mechanism, called the static
mechanism. This mechanism solves the optimization problem (10) once, for the
initial market state, and re-uses this solution to compute prices following
the same approach as the SSP mechanism. To define the static mechanism
formally, we first observe that solving (10) for the initial market state
defines an optimal anticipated sequence of supply location vectors
$\mathbf{S}_{\omega_{t}}^{*}$ and flows $\bm{f}_{\omega_{t}}^{*}$,
$\bm{g}_{\omega_{t}}^{*}$ indexed by time $t$ and scenario $\omega_{t}$. These
satisfy the forward recursion: $\bm{f}^{*}_{\omega_{0}}=0$;
$\mathbf{S}_{\omega_{t+1}}^{*}=\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{*}_{\omega_{t}})$
via (7) where $(\bm{f}^{*}_{\omega_{t}},\bm{g}^{*}_{\omega_{t}})\in
F^{*}_{\omega_{t}}(\mathbf{S}^{*}_{\omega_{t}})$ is an optimal solution to the
fluid optimization problem. Then, the price set by the static mechanism in
scenario $\omega_{t}$ on route $\ell,d$ is
$P_{(\ell,d,\omega_{t})}(g^{*}_{(\omega_{t},\ell,d)})$ as defined in
Definition 3, i.e., the price needed to have a flow $\bm{g}^{*}_{\omega_{t}}$
of riders requesting trips in the stochastic fluid model.

One can show that this static mechanism has a welfare-optimal equilibrium
under the stochastic fluid model: this is the strategy profile implied by the
solution to (10). Moreover, there exists a sequence of approximate equilibria
in the two-level model indexed by the population size $k$ that are
asymptotically welfare-optimal: those corresponding to this same strategy
profile.

Unfortunately, however, the static mechanism is not robust, in the sense that
poor equilibria (both exact and approximate) can exist, in contrast with the
SSP’s Theorem 3. Essentially, the issue is that prices do not react to
deviations between the actual supply location vector and the one anticipated
by solving (10).

We demonstrate this with a simple two-time-period one-location one-scenario
example. In the first period there are $k$ drivers who join the market in the
one location. Each driver can exit the market and collect utility $E$, or stay
for the second period and hope to serve a dispatch. In the second period there
are no new drivers who join, and the number of riders interested in taking a
trip (from the one location to itself) is
$D\sim\mathrm{Binomial}(k,\frac{1}{2})$. The distribution of the rider value
for taking a trip is $V\sim\mathrm{Uniform}(0,1)$, there is $c=0$ cost to a
driver for serving a dispatch, and no add-passenger disutility ($C=0$).

In the fluid model for this example, the welfare of having $S_{2}$ drivers
available to serve dispatches at the beginning of the second period ($t=2$) is

$\Phi_{2}(S_{2})=\begin{cases}\frac{1}{4}k&\mbox{if }S_{2}>k/2,\\\
S_{2}-\frac{S_{2}^{2}}{k}&\mbox{if }S_{2}\leq k/2.\end{cases}$

We can find the welfare-optimal $S_{2}$ by solving
$\frac{d}{dS_{2}}\Phi_{2}(S_{2})=E$. Setting $E=\frac{1}{2}$, welfare
optimality is obtained at $S_{2}=\frac{k}{4}$, so $\frac{3k}{4}$ drivers
should exit the market in the first period. The trip-price set by the platform
in this case is $P=\frac{1}{2}$, which correctly selects the $50$% of the
$\frac{k}{2}$ price-inquiring riders with the highest value $V$. In the fluid
setting, all drivers collect utility $\frac{1}{2}$ by following the welfare-
optimal solution, and no driver has incentive to deviate under the static
price $P=\frac{1}{2}$.

However, incentives break down if the static price $P=\frac{1}{2}$ is used in
the two-level model. From the perspective of a driver in the first period, and
relative to the fluid model, the utility of exiting at period $1$ remains
$\frac{1}{2}$, but the utility of staying is lower because receiving a
dispatch is not guaranteed. While the probability of dispatch goes to $1$ as
$k$ goes to $\infty$, and hence staying for the second period is approximately
incentive compatible for the $k/4$ drivers, the decision to exit the market
will always dominate the decision to stay in the market, for all drivers and
for all finite values of $k$, assuming the static price $P=\frac{1}{2}$ is
used. If many drivers leave that results in significant welfare loss.

SSP’s approach (using dynamic prices based on recomputing an optimal solution
in the second period) solves this problem. Adapting the price to the observed
amount of driver volume $S_{2}$ and computing the optimal solution with
respect to the expected rider volume interested in taking a trip produces a
trip-price $P=\frac{d}{dS_{2}}\Phi_{2}(S_{2})$, where $S_{2}$ is now the
observed volume of drivers that remain at the start of the second period. If
$S_{2}$ is lower than the value of $\frac{k}{2}$ anticipated in the fluid
solution, then $P$ will be larger than the anticipated price of $\frac{1}{2}$.
From the perspective of a driver in the first period, the utility of staying
in the market in the first period is
$\frac{d}{dS_{2}}\Phi_{2}(S_{2})\mathbb{P}^{k}(\mathrm{dispatch}\mid S_{2}),$
where $\mathbb{P}^{k}(\mathrm{dispatch}\mid S_{2})$ is the probability of
receiving a dispatch in the second period and also increases as $S_{2}$ falls.
Since a driver’s utility $\frac{d}{dS_{2}}\Phi_{2}(S_{2})$ is increasing as
$S_{2}$ decreases, it is no longer a dominant strategy, or even an equilibrium
of the game for all drivers to exit the market in the first period.

## References

  * (1)
  * Afeche et al. (2018) Philipp Afeche, Zhe Liu, and Costis Maglaras. 2018.  _Ride-hailing networks with strategic drivers: The impact of platform control capabilities on performance_.  Technical Report. Columbia Business School.  Available at SSRN 3120544.
  * Alonso-Mora et al. (2017) Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. 2017\.  On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment.  _Proceedings of the National Academy of Sciences_ 114, 3 (2017), 462–467.
  * Ashlagi et al. (2018) Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, and Chris Sholley. 2018\.  Maximum weight online matching with deadlines.  _arXiv preprint arXiv:1808.03526_ (2018).
  * Banerjee et al. (2017) Siddhartha Banerjee, Daniel Freund, and Thodoris Lykouris. 2017\.  Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework. In _Proceedings of the 2017 ACM Conference on Economics and Computation_ (Cambridge, Massachusetts, USA) _(EC ’17)_. Association for Computing Machinery, New York, NY, USA, 517\.  https://doi.org/10.1145/3033274.3085099
  * Banerjee et al. (2016) Siddhartha Banerjee, Ramesh Johari, and Carlos Riquelme. 2016\.  Dynamic pricing in ridesharing platforms.  _ACM SIGecom Exchanges_ 15, 1 (2016), 65–70.
  * Besbes et al. (2018) Omar Besbes, Francisco Castro, and Ilan Lobel. 2018\.  _Surge Pricing and Its Spatial Supply Response_.  Technical Report. Columbia Business School Research Paper No. 18-25.  Available at SSRN: https://ssrn.com/abstract=3124571.
  * Besbes et al. (2019) Omar Besbes, Francisco Castro, and Ilan Lobel. 2019\.  Spatial Capacity Planning. In _Proceedings of the 2019 ACM Conference on Economics and Computation_. 585–585.
  * Bimpikis et al. (2016) Kostas Bimpikis, Ozan Candogan, and Daniela Saban. 2016\.  _Spatial pricing in ride-sharing networks_.  Technical Report.  Available at SSRN: https://ssrn.com/abstract=2868080 or http://dx.doi.org/10.2139/ssrn.2868080.
  * Braverman et al. (2019) Anton Braverman, J. G. Dai, Xin Liu, and Lei Ying. 2019\.  Empty-Car Routing in Ridesharing Systems.  _Operations Research_ 67 (2019).  Issue 5. https://doi.org/10.1287/opre.2018.1822
  * Cachon et al. (2017) Gerard P Cachon, Kaitlin M Daniels, and Ruben Lobel. 2017\.  The role of surge pricing on a service platform with self-scheduling capacity.  _Manufacturing & Service Operations Management_ 19, 3 (2017), 368–384.
  * Camerer (1997) Colin F Camerer. 1997\.  Taxi drivers and beauty contests.  _Engineering and science_ 60, 1 (1997), 10–19.
  * Castillo et al. (2017) Juan Camilo Castillo, Dan Knoepfle, and Glen Weyl. 2017\.  Surge pricing solves the wild goose chase. In _Proceedings of the 2017 ACM Conference on Economics and Computation_. ACM, 241–242.
  * Castro et al. (2020) Francisco Castro, Peter Frazier, Hongyao Ma, Hamid Nazerzadeh, and Chiwei Yan. 2020.  Matching Queues, Flexibility and Incentives.  _arXiv preprint arXiv:2006.08863_ (2020).
  * Chen and Sheldon (2016) M Keith Chen and Michael Sheldon. 2016.  Dynamic Pricing in a Labor Market: Surge Pricing and Flexible Work on the Uber Platform.  _Ec_ 455, 10.1145 (2016), 2940716–2940798.
  * Chen and Hu (2020) Yiwei Chen and Ming Hu. 2020.  Pricing and matching with forward-looking buyers and sellers.  _Manufacturing & Service Operations Management_ 22, 4 (2020), 717–734.
  * Chen et al. (2019a) Yiwei Chen, Ming Hu, and Yun Zhou. 2019a.  _Pricing and Matching in the Sharing Economy_.  Chapter 8, 137–164.
  * Chen et al. (2019b) Yiwei Chen, Ming Hu, and Yun Zhou. 2019b.  Pricing and Matching in the Sharing Economy.  In _Sharing Economy_. Springer, 137–164.
  * Chou (2002) Yuan K Chou. 2002\.  Testing alternative models of labour supply: Evidence from taxi drivers in Singapore.  _The Singapore Economic Review_ 47, 01 (2002), 17–47.
  * Chung et al. (2018) Hangil Chung, Daniel Freund, and David B. Shmoys. 2018\.  Bike Angels: An Analysis of Citi Bike’s Incentive Program. In _Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies_ (Menlo Park and San Jose, CA, USA) _(COMPASS ’18)_. ACM, New York, NY, USA, Article 5, 9 pages.  https://doi.org/10.1145/3209811.3209866
  * Cook et al. (2018) Cody Cook, Rebecca Diamond, Jonathan Hall, John A List, and Paul Oyer. 2018.  _The gender earnings gap in the gig economy: Evidence from over a million rideshare drivers_.  Technical Report. National Bureau of Economic Research.
  * Cradeur (2018) Jay Cradeur. 2018\.  Rideshare Guy.  https://therideshareguy.com/how-i-make-1900-per-week-driving-for-uber-and-lyft-in-san-francisco/
  * Garg and Nazerzadeh (2020) Nikhil Garg and Hamid Nazerzadeh. 2020.  Driver Surge Pricing. In _Proceedings of the 21st ACM Conference on Economics and Computation_. 501–501.
  * Hall et al. (2015) Jonathan Hall, Cory Kendrick, and Chris Nosko. 2015\.  The effects of Uber’s surge pricing: A case study.  _The University of Chicago Booth School of Business_ (2015).
  * Kamga et al. (2013) Camille Kamga, M Anil Yazici, and Abhishek Singhal. 2013\.  Hailing in the rain: Temporal and weather-related variations in taxi ridership and taxi demand-supply equilibrium. In _Transportation Research Board 92nd Annual Meeting_.
  * Lewis (2006) Jonathan BorweinAdrian Lewis. 2006\.  _Convex Analysis and Nonlinear Optimization_.  Springer.
  * Lu et al. (2018) Alice Lu, Peter I Frazier, and Oren Kislev. 2018\.  Surge Pricing Moves Uber’s Driver-Partners. In _Proceedings of the 2018 ACM Conference on Economics and Computation_. 3–3.
  * Ma et al. (2018) Hangyaou Ma, Fei Fang, and David C. Parkes. 2018.  Spatio-Temporal Pricing for Ridesharing Systems.  (2018).  arXiv:1801.04015 [cs-gt]
  * Özkan and Ward (2020) Erhun Özkan and Amy R Ward. 2020.  Dynamic matching for real-time ride sharing.  _Stochastic Systems_ 10, 1 (2020), 29–70.
  * Prékopa (2013) András Prékopa. 2013\.  _Stochastic programming_. Vol. 324.  Springer Science & Business Media.
  * Sheldon (2016) Michael Sheldon. 2016\.  Income targeting and the ridesharing market.  _Unpublished manuscript. Available at: https://static1. squarespace. com/static/56500157e4b0cb706005352d_ 56 (2016), 1457131797556.
  * Yan et al. (2020) Chiwei Yan, Helin Zhu, Nikita Korolko, and Dawn Woodard. 2020\.  Dynamic pricing and matching in ride-hailing platforms.  _Naval Research Logistics (NRL)_ 67, 8 (2020), 705–724.

##  Appendix A Approximate Incentive-Compatibility of the Fluid Optimal
Solution in the Two-Level Model

In this section we prove part 2 of Theorem 1. We start by proving the
following Lemma, which shows that expected driver utilities in the two-level
model are approximately equal to driver utilities in the fluid model.

######  Lemma 11.

There exist nonnegative sequences $(\epsilon_{k}:k\geq 1)$ and
$(\beta_{k}:k\geq 1)$, both converging to $0$ as $k\to\infty$, such that when
the SSP mechanism is used to set prices in the stochastic two-level model with
population-size $k$, then for any market state
$(\omega_{t},\mathbf{S}_{t})\in\Omega_{t}\times\mathcal{S}_{t}$, and any
location $\ell$ with driver-volume larger than $\beta_{k}$, i.e.
$S_{\ell}\geq\beta_{k}$, we have the expected utility of drivers at $\ell$ is
at most $\epsilon_{k}$ away from the fluid utility for drivers at $\ell$, i.e.

$\left|\mathbb{E}[U_{i}^{t}\mid\ell_{i}^{t}=\ell]-\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{t})\right|\leq\epsilon_{k}.$

###### Proof.

Fix a time period $t$ and we assume via backwards induction that, at future
time periods $t+1$, drivers who are positioned at a location $\ell$ collect
expected utility that is approximately the same as the fluid counterpart. That
is, assume there exist sequences $(\epsilon^{t+1}_{k})$, $(\beta_{k}^{t+1})$
converging to $0$ as $k\to\infty$, such that for any time $t+1$ state
$(\omega_{t+1},\mathbf{S}_{t+1})\in\Omega_{t+1}\times\mathcal{S}_{t+1}(\gamma_{t+1})$
we have that the location-specific value function for the two-level model uner
$\Pi^{(k)}$ is within $\epsilon^{t+1}_{k}$ of the value function for the
corresponding two-level model, for any location $\ell$ where
$S_{\ell}\geq\beta_{k}^{t+1}$. That is,

$|\mathbb{E}[U_{i}^{t+1}\mid\ell_{i}^{t}=\ell]-\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1})|\leq\epsilon^{t+1}_{k}$ (34)

holds for every location $\ell$ where $S_{\ell}\geq\beta_{k}^{t+1}$, where $i$
is a driver positioned at location $\ell$, and $U_{i}^{t+1}$ is a random
variable specifying the utility collected by the driver starting from time
period $t+1$ onwards under the strategy profile $\Pi^{(k)}$.

Fix any state $(\omega_{t},\mathbf{S}_{t})$ and let
$(\bm{x},\mathbf{e})=\Sigma_{t}^{*}(\omega_{t},\mathbf{S}_{t})$ be the
disutility acceptance thresholds $\bm{x}=(\bm{x}_{\ell}:\ell\in\mathcal{L})$
and relocation destination distributions
$\mathbf{e}=(\mathbf{e}_{\ell}:\ell\in\mathcal{L})$ selected by the fluid
optimal strategy $\Sigma^{*}$. Let $(\bm{f}^{*},\bm{g}^{*})\in
F_{\omega_{t}}^{*}(\mathbf{S}_{t})$ be the optimal solution that the SSP
mechanism uses to set prices. Let $(\bar{\bm{f}}_{k},\bar{\bm{g}}_{k})$ be the
fluid outcomes associated with the market state $(\omega_{t},\mathbf{S}_{t})$
and strategy-profile $\Pi^{(k)}$ (7). Recall that, by definition, under the
strategy profile $\Pi^{(k)}$, every driver positioned at $\ell$ uses
$\bm{x}_{\ell}$ as their threshold vector, and the distribution of relocation
destinations selected by drivers at $\ell$ is equal to a rounded version of
$\mathbf{e}_{\ell}$. The fluid outcomes are deterministic functions of the
common disutility threshold vector $\bm{x}_{\ell}$ and the relocation
distribution used by drivers at $\ell$ (see equations (89-90), and Definition
5). Since the relocation distribution used by drivers at $\ell$ under
$\Pi^{(k)}$ is a rounded version of $\mathbf{e}_{\ell}$, and the rounding
error is on the order of $\frac{1}{k}$ for where $k$ is the population-size
parameter, it follows that $(\bar{\bm{f}}_{k},\bar{\bm{g}}_{k})$ converges
uniformly to $(\bm{f}^{*},\bm{g}^{*})$ over all states
$(\omega_{t},\mathbf{S}_{t})\in\Omega_{t}\times\mathcal{S}_{t}(\gamma_{t})$,
i.e.

$\sup_{(\omega_{t},\mathbf{S}_{t})\in\Omega_{t}\times\mathcal{S}_{t}(\gamma_{t})}\|\bar{\bm{f}}_{k}-\bm{f}^{*}\|+\|\bar{\bm{g}}_{k}-\bm{g}^{*}\|\to
0,\ \ \mbox{as}\ k\to\infty.$

Next, concentration properties for the matching process tell us that the
stochastic actions which occur under $\Pi^{(k)}$ converge to their
deterministic fluid counterparts. Specifically, let $(\bm{f}_{k},\bm{g}_{k})$
be (stochastic) vectors which encode the actions taken under $\Pi^{(k)}$ with
respect to a market state
$(\omega_{t},\mathbf{S}_{t})\in\Omega_{t}\times\mathcal{S}_{t}(\gamma_{t})$.
Lemma 28 states there exist nonnegative sequences $\alpha_{k}$ and $q_{k}$,
both converging to $0$ as $k\to\infty$, such that

$\sup_{(\omega_{t},\mathbf{S}_{t})\in\Omega_{t}\times\mathcal{S}_{t}(\gamma_{t})}\mathbb{P}\left(\|\bar{\bm{f}}_{k}-\bm{f}_{k}\|+\|\bar{\bm{g}}_{k}-\bm{g}_{k}\|\leq\alpha_{k}\right)\geq
1-q_{k}.$ (35)

holds for all $k$.

Define the sequence $(\beta_{k})_{k=1}^{\infty}$ by setting
$\beta_{k}=\sqrt{\alpha_{k}}$ for every $k\geq 1$. Since we know that
$\alpha_{k}\to 0$ as $k\to\infty$, it follows that $\beta_{k}\to 0$ as
$k\to\infty$, as required by our theorem statement.

Now consider a supply-location vector
$(\omega_{t},\mathbf{S}_{t})\in\Omega_{t}\times\mathcal{S}_{t}(\gamma_{t})$,
and consider a location $\ell$ with $S_{\ell}\geq\beta_{k}$. Consider the
expected utility collected by a driver $i$ positioned at $\ell$:

$\mathbb{E}[U_{i}^{t}\mid\ell_{i}^{t}=\ell]=\sum_{d\in\mathcal{L}\cup\\{\emptyset\\},\delta\in\\{0,1\\}}\mathbb{E}[U_{i}^{t}\mid
a_{i}^{t}=(\ell,d,\delta)]\mathbb{P}(a_{i}^{t}=(\ell,d,\delta)\mid\ell_{i}^{t}=\ell),$

where $a_{i}^{t}=(\ell,d,\delta,X)$ denote the action they take, where
$\delta\in\\{0,1\\}$ is an indicator specifying whether or not it is a
dispatch trip, and $X\in[0,C]$ is their sampled add-passenger disutility.
Under the backwards induction assumption (34), the driver $i$ has expected
utility at time $t$ given by

$\displaystyle\mathbb{E}[U_{i}^{t}\mid a_{i}^{t}=(\ell,d,\delta)]$
$\displaystyle=\delta(P_{(\ell,d)}-c_{(\ell,d)}-X)+\mathbb{E}[\frac{\partial}{\partial
S_{d}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1})\mid a_{i}^{t}]+\epsilon_{k}^{t+1}$
$\displaystyle=\delta(P_{(\ell,d)}-c_{(\ell,d)}-X)+\mathbb{E}[\frac{\partial}{\partial
S_{d}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1})]+\gamma_{k}+\epsilon_{k}^{t+1}$
$\displaystyle=\delta(P_{(\ell,d)}-c_{(\ell,d)}-X)+\mathbb{E}[\frac{\partial}{\partial
S_{d}}\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{*}))]+\psi_{k}+\gamma_{k}+\epsilon_{k}^{t+1}$

where $\epsilon_{k}^{t+1}$ is the error term bounding the difference between
the time $t+1$ expected utility of agent $i$ and the partial derivative of the
state-dependent optimization function, which exists by our backwards induction
assumption (34), assuming, for now, the destination $d$ has sufficiently many
drivers for the backwards induction assumption to hold. The backwards
induction assumption only holds if $S_{d}\geq\beta_{k}^{t+1}$, but
$\beta_{k}^{t+1}$ is vanishingly small as $k\to\infty$, so the proportion of
drivers who drive towards destinations satisfying this condition goes to one
as $k\to\infty$.

$\gamma_{k}$ is the error we pay for going from the distribution of the time
$t+1$ supply-locations $\mathbf{S}_{t+1}$ conditional on $a_{i}^{t}$ to the
unconditional distribution on $\mathbf{S}_{t+1}$. By Assumption 4 we know that
there exists a constant $\gamma_{k}$ that bounds the difference between the
conditional and unconditional distribution of $\mathbf{S}_{t+1}$ for all
initial states $(\omega_{t},\mathbf{S}_{t})$ and all strategy profiles, and
that $\gamma_{k}\to 0$ as the population size $k$ tends to $\infty$.

$\psi_{k}$ is an error term that bounds the difference between the expected
partial derivative of the state-dependent optimization function with respect
to the stochastic time $t+1$ supply-location vector $\mathbf{S}_{t+1}$, and
the fluid time $t+1$ supply-location vector
$\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{*})$, which is a deterministic
function of the time $t+1$ scenario $\omega_{t+1}$ and the fluid optimal trips
$\bm{f}^{*}$. We know there exists a constant $\psi_{k}$ that bounds this
difference, such that $\psi_{k}\to 0$ as $k\to\infty$, because of the uniform
convergence described in equation (35), as well as the fact that the partial
derivative function $\frac{\partial}{\partial
S_{d}}\Phi_{\omega_{t+1}}(\cdot)$ is bounded and continuous over a compact
domain.

Lemma 6 gives us the following expression for Q-values in the fluid model:

$\mathcal{Q}_{t}(\ell,d,1,x_{(\ell,d)})=\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{t})-\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}=\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0),$

so therefore we have

$\displaystyle\mathbb{E}[U_{i}^{t}\mid
a_{i}^{t}=(\ell,d,\delta)]=\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{t})-\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}+\delta(x_{(\ell,d)}-X)+\epsilon_{k},$

where $\epsilon^{\prime}_{k}=\psi_{k}+\gamma_{k}+\epsilon_{k}^{t+1}$ is the
sum of all the errors accrued by approximating the stochastic utility-to-go
with the fluid utility-to-go, and $\delta(x_{(\ell,d)}-X)$ is the extra
utility the driver collects when the trip is a dispatch trip ($\delta=1$) and
their add-passenger disutility $X$ is smaller than the threshold
$x_{(\ell,d)}$. Therefore, averaging over all trips we have

$\left|\mathbb{E}[U_{i}^{t}]-\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{t})\right|=\mathbb{P}(\delta=1)\mathbb{E}[x_{(\ell,d)}-X\mid\delta=1]-\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}+\epsilon^{\prime}_{k}.$

We turn to analyzing the
$\mathbb{P}(\delta=1)\mathbb{E}[x_{(\ell,d)}-X\mid\delta=1]$ term. Recall that
the threshold $x_{(\ell,d)}$ is the same for every destination $d$ under the
policy $\Pi^{(k)}$, and this value is
$C\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}$. Also,
conditioned on driver $i$ being allocated a dispatch trip, we know that their
add-passenger disutility $X$ is uniformly distributed between $0$ and
$x_{(\ell,d)}$. Therefore we have

$\mathbb{E}[x_{(\ell,d)}-X\mid\delta=1]=\frac{C}{2}\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}.$

Also, the probability of a dispatch trip $\mathbb{P}(\delta=1)$ can be
expressed in terms of the total number of dispatch trips:

$\mathbb{P}(\delta=1)=\mathbb{E}\left[\frac{\bm{g}^{T}\mathbf{1}_{\ell}}{S_{\ell}}\right]=\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{S_{\ell}}+\frac{\alpha_{k}}{S_{\ell}},$

where $\alpha_{k}$ is the error term bounding the convergence of $\bm{g}$ to
$\bm{g}^{*}$. Now we use the fact that $S_{\ell}\geq\beta_{k}=\sqrt{k}$ to
conclude that $\frac{\alpha_{k}}{S_{\ell}}\leq\sqrt{\alpha_{k}}\to 0$ as
$k\to\infty$. So, we have

$\left|\mathbb{P}(\delta=1)\mathbb{E}[x_{(\ell,d)}-X\mid\delta=1]-\frac{C}{2}\left(\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}\right)^{2}\right|\leq\sqrt{\alpha_{k}}.$

Defining $\epsilon_{k}=\epsilon^{\prime}_{k}+\sqrt{\alpha_{k}}$, which we know
converges to $0$ as $k\to\infty$, we have shown

$\left|\mathbb{E}[U_{i}^{t}\mid\ell_{i}^{t}=\ell]-\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{t})\right|\leq\epsilon_{k},$

finishing the proof. ∎

We restate part 2 of Theorem 1 below.

######  Theorem.

There exist nonnegative sequences $(\epsilon_{k}:k\geq 1)$ and
$(\delta_{k}:k\geq 1)$, both converging to $0$ as $k\to\infty$, such that when
the SSP mechanism is used to set prices in the stochastic two-level model with
population-size $k$, then $\Pi^{(k)}$ is an $(\epsilon_{k},\delta_{k})$
equilibrium.

###### Proof.

To show that $\Pi^{(k)}$ is an $(\epsilon_{k},\delta_{k})$-approximate
equilibrium, we have to show that from any market state
$(\omega_{t},\mathbf{S}_{t})\in\Omega_{t}\times\mathcal{S}_{t}(\gamma_{t})$,
the number of drivers who have at least $\epsilon_{k}$-conditional incentive
to deviate from any market state is smaller than $\delta_{k}k$. That is, if
$\mathcal{M}_{t}$ is the index set of drivers corresponding to the supply-
location vector $\mathbf{S}_{t}$, and
$\mathcal{M}_{t}(\epsilon_{k};\omega_{t},\mathbf{S}_{t})$ is the set of
drivers whose conditional incentive to deviate from $\Pi^{(k)}$ is no larger
than $\epsilon_{k}$, we have to show

$|\mathcal{M}_{t}\setminus\mathcal{M}_{t}(\epsilon_{k};\omega_{t},\mathbf{S}_{t})|\leq\delta_{k}k.$
(36)

Define $\delta_{k}=|\mathcal{L}|\beta_{k}$, where $(\beta_{k})_{k=1}^{\infty}$
is the sequence from Lemma 11. Define $\epsilon_{k}$ to be the maximum
incentive to deviate, over all market states $(\omega_{t},\mathbf{S}_{t})$,
for a driver positioned at a location $\ell$ which satisfies the minimum
driver volume condition described in Lemma 11, i.e. $S_{\ell}\geq\beta_{k}$.

Note the inequalities

$|\mathcal{M}_{t}\setminus\mathcal{M}_{t}(\epsilon_{k};\omega_{t},\mathbf{S}_{t})|\leq
k\sum_{\ell\in\mathcal{L}:S_{\ell}<\beta_{k}}S_{\ell}\leq k\delta_{k},$

so the equilibrium condition (36) is satisfied, and we already know
$\delta_{k}\to 0$ holds.

That the incentive to deviate term $\epsilon_{k}$ converges to $0$ follows
from the fact that there is no incentive to deviate in the fluid model, and as
$k\to\infty$ we have that the stochastic utility converges to the fluid
utility, for drivers at locations $\ell$ which satisfy the minimum driver
volume condition $S_{\ell}\geq\beta_{k}$. ∎

##  Appendix B Approximate Welfare-Robustness Proof in the Fluid Model

In this Appendix we prove the second part of the statement in Theorem 2,
stating that every $\epsilon$-equilibrium in the fluid model achieves
approximately optimal welfare.

Let $\Sigma$ be an $\epsilon$-equilibrium for the fluid model under the SSP
pricing and matching policy. Let $\mathcal{V}_{t}$ and $\mathcal{Q}_{t}$ be
the value function and Q-values associated with $\Sigma$. We proceed via
backwards induction on the time $t$, and make the following assumption about
the future time period $t+1$: There exists an error term $\epsilon_{t+1}$
(which converges to $0$ as $\epsilon\to 0$) such that the following are true:

  1. 1.

The welfare achieved by $\Sigma$ from any time $t+1$ market state is within
$\epsilon_{t+1}$ from the optimum.

  2. 2.

The value function for a location $\ell$ at any time $t+1$ state is within
$\epsilon_{t+1}$ of the partial derivative of the fluid optimization function:
i.e. for any $\ell$ and $(\omega_{t+1},\mathbf{S}_{t+1})\in\mathcal{S}_{t+1}$
we have

$\left|\mathcal{V}_{t+1}(\ell,\omega_{t+1},\mathbf{S}_{t+1})-\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1})\right|\leq\epsilon_{t+1}.$ (37)

Fix a time period $t$ and let $(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}$
be any market state from time $t$. Let $\bm{x}^{\prime}$ be the disutility
thresholds used by the drivers under $\Sigma$ at $(\omega_{t},\mathbf{S}_{t})$
and let $(\bm{g}^{\prime},\bm{f}^{\prime})$ be the vector of dispatch trips
and total trips that result under $\Sigma$ and the SSP prices and matching
process at $(\omega_{t},\mathbf{S}_{t})$. Additionally, let
$(\bm{g}^{*},\bm{f}^{*})$ denote the optimal solution for the fluid
optimization problem with respect to $(\omega_{t},\mathbf{S}_{t})$ used by the
SSP mechanism to set prices and allocate matches.

Recall an $\epsilon$-equilibrium strategy profile for the fluid model is
characterized by the approximate incentive compatibility conditions (9), which
we restate here for clarity.

$\displaystyle f^{\prime}_{(\ell,d)}-g^{\prime}_{(\ell,d)}>\epsilon$
$\displaystyle\implies\mathcal{Q}_{t}(\ell,d,0)\geq\max_{d^{\prime}\in\mathcal{L}}\mathcal{Q}_{t}(\ell,d^{\prime},0)-\epsilon,$
$\displaystyle g^{\prime}_{(\ell,d)}>\epsilon$
$\displaystyle\implies\mathcal{Q}_{t}(\ell,d,1,x^{\prime}_{(\ell,d)})\geq\max_{d^{\prime}\in\mathcal{L}}\mathcal{Q}_{t}(\ell,d^{\prime},0)-\epsilon,$
(38) $\displaystyle
g^{\prime}_{(\ell,d)}>\epsilon,S_{\ell}-\sum_{d^{\prime}}g^{\prime}_{(\ell,d^{\prime})}>\epsilon$
$\displaystyle\implies\mathcal{Q}_{t}(\ell,d,1,x^{\prime}_{(\ell,d)})\leq\max_{d^{\prime}\in\mathcal{L}}\mathcal{Q}_{t}(\ell,d^{\prime},0)+\epsilon.$
(39)

Our proof mirrors the steps in Section 4.3.

Where do the non-dispatched drivers go? First, we show that the non-dispatched
drivers, whose trips are specified by $\bm{f}^{\prime}-\bm{g}^{\prime}$, take
approximately optimal trips given the dispatch trips $\bm{g}^{\prime}$. Recall
the optimization problem (29), which depends on the vector $\bm{g}^{\prime}$,
which we restate below:

$\displaystyle\sup_{\bm{f}}$ $\displaystyle\ \ \
\sum_{(\ell,d)\in\mathcal{L}^{2}}-c_{(\ell,d)}f_{(\ell,d)}+\mathcal{U}_{\omega_{t}}^{>t}(\bm{f})$
(40) subject to $\displaystyle f_{(\ell,d)}\geq g^{\prime}_{(\ell,d)}\ $
$\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (41)
$\displaystyle\sum_{d\in\mathcal{L}}f_{(\ell,d)}=S_{\ell}\ $
$\displaystyle\forall\ell\in\mathcal{L}.$ (42)

######  Lemma 12.

Let $\epsilon^{\prime}=\max(\epsilon,\epsilon_{t+1})$, where $\epsilon$ is the
error term in our definition of approximate equilibrium, and $\epsilon_{t+1}$
is the error bound from our backwards induction assumption (37).

Then there exists a constant $C>0$ such that the total trip volumes
$\bm{f}^{\prime}$ from our equilibrium is a $C\epsilon^{\prime}$-optimal
solution for the relocation problem (40) with respect to the dispatch trips
$\bm{g}^{\prime}$. Moreover, the following dual variables form an
$\epsilon^{\prime}$-approximate Lagrange multiplier vector for
$\bm{f}^{\prime}$ (in the sense of Definition 8):

$\lambda_{(\ell,d)}^{\prime}=\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0)-\mathcal{Q}_{t}(\ell,d,0),$
(43)

associated with the inequality constraint (30) for each $(\ell,d)$, and

$\eta_{\ell}^{\prime}=\max_{d^{\prime}}\mathcal{Q}_{t}(\ell,d^{\prime},0)$
(44)

associated with the equality constraint (31) for each $\ell$.

###### Proof.

We show that $(\bm{\lambda}^{\prime},\bm{\eta}^{\prime})$ is an
$\epsilon^{\prime}$-approximate Lagrange multiplier vector for
$\bm{f}^{\prime}$, in the sense of Definition 8, where
$\epsilon^{\prime}=\max(\epsilon,\epsilon_{t+1})$.

First, observe that approximate complementary slackness conditions follow from
the approximate incentive compatibility properties. Indeed, if
$f^{\prime}_{(\ell,d)}-g^{\prime}_{(\ell,d)}>\epsilon$ then (38) states
$\lambda_{(\ell,d)}<\epsilon$.

Next, we check approximate stationarity. We work in terms of a convex cost
function instead of a concave utility function. Define

$\mathcal{C}_{\omega_{t}}(\bm{f})=\sum_{(\ell,d)\in\mathcal{L}^{2}}c_{(\ell,d)}f_{(\ell,d)}-\mathcal{U}_{\omega_{t}}^{>t}(\bm{f})$
(45)

to be the cost function of the relocation trip variables $\bm{f}$, i.e. the
negative of the objective function in the relocation problem (40).

First, observe our backwards induction assumption (37) yields the following
equalities:

$\displaystyle\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{C}_{\omega_{t}}(\bm{f}^{\prime})$
$\displaystyle=c_{(\ell,d)}-\frac{\partial}{\partial
f_{(\ell,d)}}\mathbb{E}\left[\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{\prime}))\mid\omega_{t}\right]$
$\displaystyle=c_{(\ell,d)}-\mathbb{E}\left[\frac{\partial}{\partial
S_{d}}\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{\prime}))\mid\omega_{t}\right]$
$\displaystyle=c_{(\ell,d)}-\mathbb{E}\left[\mathcal{V}_{t+1}(d;\omega_{t+1},\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}^{\prime}))\right]+\delta$
$\displaystyle=-\mathcal{Q}_{t}(\ell,d,0)+\delta,$ (46)

where $\delta$ is a constant satisfying $|\delta|\leq\epsilon_{t+1}$.

The Lagrangian for (40) is the following:

$L(\bm{f};\bm{\lambda},\bm{\eta})=\mathcal{C}_{\omega_{t}}(\bm{f})+\bm{\lambda}^{T}(\bm{g}^{\prime}-\bm{f})+\sum_{\ell}\eta_{\ell}\left(\sum_{d}f_{(\ell,d)}-S_{\ell}\right).$

Evaluate the partial derivative of
$L(\bm{f}^{\prime};\bm{\lambda}^{\prime},\bm{\eta}^{\prime})$ at each
coordinate $f^{\prime}_{(\ell,d)}$:

$\displaystyle\frac{\partial}{\partial
f_{(\ell,d)}}L(\bm{f}^{\prime};\bm{\lambda},\bm{\eta})$
$\displaystyle=c_{(\ell,d)}-\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}_{\omega_{t}}^{>t}(\bm{f}^{\prime})-\lambda_{(\ell,d)}+\eta_{\ell}$
$\displaystyle=-\mathcal{Q}(\ell,d,0)-\lambda_{(\ell,d)}+\max_{d^{\prime}}\mathcal{Q}(\ell,d,0)+\delta,$

so $|\frac{\partial}{\partial
f_{(\ell,d)}}L(\bm{f}^{\prime};\bm{\lambda}^{\prime},\bm{\eta}^{\prime})|\leq\epsilon_{t+1}$.

Therefore, $(\bm{\lambda}^{\prime},\bm{\eta}^{\prime})$ is an
$\epsilon^{\prime}$-approximate Lagrange multiplier vector for
$\bm{f}^{\prime}$, in the sense of Definition 8. By Lemma 35, it follows that
$\bm{f}^{\prime}$ is an $\epsilon^{\prime\prime}$-optimal solution for (40),
where $\epsilon^{\prime\prime}=C\epsilon^{\prime}$ for some problem-
independent constant $C$.

∎

Approximate equilibria serve approximately all available dispatch demand. The
proof of this fact follows the outline along the same line as in Section 4
using Lemma 12 in place of the exact version used there. We define an
alternate network as was done there. By Lemma 8 the flow
$(\bm{g}^{**},\bm{f}^{**},\bm{x}^{**})$ is an optimal solution to our modified
convex program, with optimal value $OPT^{**}$ and using costs
$c_{(\ell,d)}-p_{(\ell,d)}-x^{*}_{(\ell,d)}$ on the special edges.

Now consider the approximate equilibrium solution
$(\bm{g}^{\prime},\bm{f}^{\prime},\bm{x}^{\prime})$. Different drivers may use
different cutoffs for their dis-utility. We define $x^{\prime}_{(\ell,d)}$ as
lowest pick-up dis-utility by a driver who rejected a dispatch. This means
that all drivers with $x_{(\ell,d)}<x^{\prime}_{(\ell,d)}$ offered a dispatch
$(\ell,d)$ accepted it, and by the equilibrium property, all drivers with
$x_{(\ell,d)}\geq x^{\prime}_{(\ell,d)}+\epsilon$ rejected the dispatch if
offered.

Now consider the same network using the alternate cost
$c_{(\ell,d)}-p_{(\ell,d)}-x^{\prime}_{(\ell,d)}$.

By Lemma 9 (using $(\bm{g}^{**},\bm{f}^{**},\bm{x}^{**})$ as a feasible
solution), the optimum value with this new cost is now at least
$\sum_{(\ell,d)}(g^{*}_{(\ell,d)}-g^{\prime}_{(\ell,d)})(x^{*}_{(\ell,d)}-x^{\prime}_{(\ell,d)}-\epsilon)$
larger.

Next consider the solution
$(\bm{g}^{\prime\prime},\bm{f}^{\prime\prime},\bm{x}^{\prime\prime})$
constructed from the approximate equilibrium as was done in Section 4. We
claim that this solution is an approximate equilibrium for the modified
problem.

######  Lemma 13.

The flow $(\bm{g}^{\prime\prime},\bm{f}^{\prime\prime},\bm{x}^{\prime\prime})$
is an equilibrium on our modified network either with cost
$c_{(\ell,d)}-p_{(\ell,d)}-x^{*}_{(\ell,d)}$ or with costs
$c_{(\ell,d)}-p_{(\ell,d)}-x^{\prime}_{(\ell,d)}$ of the drivers with modified
costs.

Now by Lemma 12 this equilibrium solution is approximately optimal with both
version of the problem.

Using $x^{*}$ to define cost we get that the equilibrium solution has value
close to $OPT^{**}$. Using $x^{\prime}$ does not change the value of the
equilibrium, while the optimum increases by Lemma 9 by at least

$\sum_{(\ell,d)}(g^{*}_{(\ell,d)}-g^{\prime}_{(\ell,d)})(x^{*}_{(\ell,d)}-x^{\prime}_{(\ell,d)}).$

Since the shared equilibrium solution is approximately optimal for both
problems, this gives an upper bound on this difference in terms of the
optimality of the solution.

For the product
$\sum_{d}(g^{*}_{(\ell,d)}-g^{\prime}_{(\ell,d)})(x^{*}_{(\ell,d)}-x^{\prime}_{(\ell,d)}$
to be small for a location $\ell$, we must have that for each destination,
either $g^{*}_{(\ell,d)}-g^{\prime}_{(\ell,d)}$ must be small or
$x^{*}_{(\ell,d)}-x^{\prime}_{(\ell,d)}$ is small. To be able to bound the
difference between $g^{*}_{(\ell,d)}$ and $g^{\prime}_{(\ell,d)}$, we need to
show that $x^{*}_{(\ell,d)}\approx x^{\prime}_{(\ell,d)}$ implies that
$g^{*}_{(\ell,d)}\approx g^{\prime}_{(\ell,d)}$. To see this, consider the
subset of destinations that have
$x^{*}_{(\ell,d)}-x^{\prime}_{(\ell,d)}\leq\epsilon C$, and let
$S^{\epsilon}_{\ell}$ denote the driver volume that is used to offer
dispatches to one of these destinations from location $\ell$.

######  Lemma 14.

If an approximate equilibrium satisfies $x^{\prime}_{(\ell,d)}\geq
x^{*}_{(\ell,d)}-\epsilon C$ for a subset of destinations at a location
$\ell$, and let $S_{\ell}^{\epsilon}$ be the set of drivers who would be
offered rides to one of these locations in the optimum solution, then at most
$\epsilon S^{\epsilon}_{\ell}$ riders requesting rides do not receive a ride
to this subset of destinations.

###### Proof.

The price is set so that we have $g^{*}_{(\ell,d)}$ riders that will accept
the price offered. Our mechanisms offers the dispatch $(\ell,d)$ to at least
$\frac{C}{x^{*}_{(\ell,d)}}g^{*}_{(\ell,d)}$ drivers. With the lower
disutility cutoff $x^{\prime}_{(\ell,d)}$, out of these dispatch offers, a
fraction of $\frac{x^{*}_{(\ell,d)}-x^{\prime}_{(\ell,d)}}{C}$ will reject the
dispatch that would be accepted in the optimum. This is an upper bound on the
riders remaining unserved at location $\ell$ with possible extra drivers, or
other destinations where riders are already served, the mechanism may offer
the rides to additional drivers. Summing these over the different routes
starting at $\ell$, we see that at most $\epsilon S^{\epsilon}_{\ell}$ riders
do not get a ride. ∎

Approximate equilibria are approximately welfare optimal. We can now finish
the backwards induction proof analogously to the proof for the exact case in
Section 4. We start by showing that the thresholds $x^{\prime}_{(\ell,d)}$ are
approximately equal to the thresholds $x^{*}_{(\ell,d)}$.

######  Lemma 15.

For any location $\ell$ where the total driver volume $S_{\ell}$ is larger
than $\sqrt{\epsilon}$, and for any route $(\ell,d)$ where the dispatch volume
$g^{*}_{(\ell,d)}$ is larger then $\epsilon$, then the difference between the
optimal threshold $x^{*}_{(\ell,d)}$ and the threshold used by the drivers in
an approximate equilibrium $x^{\prime}_{(\ell,d)}$ is bounded by an error term
$\epsilon^{\prime\prime}$, such that $\epsilon^{\prime\prime}$ goes to $0$ as
$\max(\epsilon,\epsilon_{t+1})$ goes to $0$.

###### Proof.

Consider the following modification of the optimization problem (40), where
the pre-specified dispatch trips correspond to the fluid optimal dispatch
trips $\bm{g}^{*}$ rather than $\bm{g}^{\prime}$:

$\displaystyle\sup_{\bm{f}}$ $\displaystyle\ \ \
\sum_{(\ell,d)\in\mathcal{L}^{2}}-c_{(\ell,d)}f_{(\ell,d)}+\mathcal{U}_{\omega_{t}}^{>t}(\bm{f})$
subject to $\displaystyle f_{(\ell,d)}\geq g^{*}_{(\ell,d)}\ $
$\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$
$\displaystyle\sum_{d\in\mathcal{L}}f_{(\ell,d)}=S_{\ell}\ $
$\displaystyle\forall\ell\in\mathcal{L}.$

We have established that $\bm{g}^{\prime}\approx\bm{g}^{*}$. Therefore, by
Lemma 12, $\bm{f}^{\prime}$ is approximately optimal for the above
optimization problem, and $\bm{f}^{*}$ is an exact optimum. Let
$(\bm{\lambda}^{*},\bm{\eta}^{*})$ be the optimal dual variables associated
with $\bm{f}^{*}$. By Lemma 36, it follows that
$(\bm{\lambda}^{*},\bm{\eta}^{*})$ is an $\epsilon^{\prime}$-approximate
Lagrange multiplier vector for $\bm{f}^{\prime}$, in the sense of Definition