8, where $\epsilon^{\prime}$ goes to $0$ as the suboptimality of
$\bm{f}^{\prime}$ goes to $0$. In particular, this means that the norm of the
gradient of the mixed-solution Lagrangian is small:
$\|\nabla_{\bm{f}}L(\bm{f}^{\prime};\bm{\lambda}^{*},\bm{\eta}^{*})\|_{2}\leq\epsilon^{\prime}$,
where the Lagrangian is

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

In particular, for any pair of origin and destination locations $(\ell,d)$ we
have the bound

$\left|\frac{\partial}{\partial
f_{(\ell,d)}}L(\bm{f}^{\prime};\bm{\lambda}^{*},\bm{\eta}^{*})\right|\leq\epsilon^{\prime}.$

Evaluating the partial derivative, , we have

$\displaystyle\frac{\partial}{\partial
f_{(\ell,d)}}L(\bm{f}^{\prime};\bm{\lambda}^{*},\bm{\eta}^{*})$
$\displaystyle=$ $\displaystyle\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{C}_{\omega_{t}}(\bm{f}^{\prime})-\lambda^{*}_{(\ell,d)}+\eta^{*}_{\ell}$
$\displaystyle\approx$
$\displaystyle-\mathcal{Q}^{\prime}(\ell,d,0)-\lambda^{*}_{(\ell,d)}+\eta^{*}_{\ell}$
$\displaystyle=$
$\displaystyle-\mathcal{Q}^{\prime}(\ell,d,0)-\left(\max_{d^{\prime}}\mathcal{Q}^{*}(\ell,d^{\prime},0)-\mathcal{Q}^{*}(\ell,d,0)\right)+\max_{d^{\prime}}\mathcal{Q}^{*}(\ell,d^{\prime},0)$
$\displaystyle=$
$\displaystyle\mathcal{Q}^{*}(\ell,d,0)-\mathcal{Q}^{\prime}(\ell,d,0).$

The first line uses the approximate equality established in equation (46),
which shows that, under our backwards induction assumption that the
continuation utilties at a location are approximately equal to the partial
derivative of the optimal welfare function with respect to driver supply at
that location, the partial derivative of the cost function with respect to
driver volume along a route is approximately equal to the negative utility of
taking a relocation trip along that route. Therefore,

$\left|\mathcal{Q}^{\prime}(\ell,d,0)-\mathcal{Q}^{*}(\ell,d,0)\right|\leq\epsilon^{\prime}+\epsilon_{t+1},$

where $\mathcal{Q}^{\prime}(\ell,d,0)$ is the utility generated by a
relocation trip from $\ell$ to $d$ under the approximate equilibrium
$(\bm{f}^{\prime},\bm{g}^{\prime},\bm{x}^{\prime})$, and
$\mathcal{Q}^{*}(\ell,d,0)$ is the utility generated by the same relocation
trip under the exact equilibrium $(\bm{f}^{*},\bm{g}^{*},\bm{x}^{*})$.

Now recall that, since the actions
$(\bm{f}^{\prime},\bm{g}^{\prime},\bm{x}^{\prime})$ come from an approximate
equilibrium, we know the following properties are satisfied:

$\displaystyle g^{\prime}_{(\ell,d)}>\epsilon$
$\displaystyle\implies\mathcal{Q}^{\prime}(\ell,d,1,x^{\prime}_{(\ell,d)})\geq\max_{d^{\prime}}\mathcal{Q}^{\prime}(\ell,d^{\prime},0)-\epsilon$
(47) $\displaystyle
S_{\ell}-\sum_{d^{\prime}}g^{\prime}_{(\ell,d^{\prime})}>\epsilon,g^{\prime}_{(\ell,d)}>\epsilon$
$\displaystyle\implies\mathcal{Q}^{\prime}(\ell,d,1,x^{\prime}_{(\ell,d)})\leq\max_{d^{\prime}}\mathcal{Q}^{\prime}(\ell,d^{\prime},0)+\epsilon.$
(48)

The above properties formalize what we mean when we say that a driver, whose
add-passenger disutility is exactly the threshold value
$x^{\prime}_{(\ell,d)}$, is approximately indifferent between serving a
dispatch trip from $\ell$ to $d$ and serving a relocation trip to any
destination. The first line (47) says that, for a route $(\ell,d)$ where a
non-negligible volume of drivers serve a dispatch trip, then the utility
collected by a driver who serves a dispatch trip along $(\ell,d)$, and whose
add-passenger disutility is exactly equal to the threshold
$x^{\prime}_{(\ell,d)}$, is (approximately) at least as large as the maximum
relocation-trip utility achievable from the same origin location. The second
line (48) says that, for a route $(\ell,d)$ where a non-negligible volume of
drivers serve a dispatch trip, and where a non-negligible volume of drivers
also serve a relocation trip, then the utility collected by a driver whose
add-passenger disutility is exactly $x^{\prime}_{(\ell,d)}$ who serves a
dispatch-trip from $\ell$ to $d$ is (approximately) no larger than the maximum
relocation-trip utility achievable from the same origin location.

We proceed by analyzing two cases. In the first case, suppose that the volume
of drivers at $\ell$ who serve a relocation trip is no larger than $\epsilon$,
i.e. $S_{\ell}-\sum_{d^{\prime}}g^{\prime}_{(\ell,d^{\prime})}<\epsilon$.

In this case, since the realized dispatch trip volumes $g^{\prime}_{(\ell,d)}$
cannot be larger than the optimal dispatch trip volumes $g^{*}_{(\ell,d)}$, we
also have $S_{\ell}-\sum_{d^{\prime}}g^{*}_{(\ell,d)}<\epsilon$. Recall that
under the fluid optimal solution $(\bm{f}^{*},\bm{g}^{*},\bm{x}^{*})$, the
thresholds along each route $(\ell,d)$ depend only on the origin location
$\ell$, i.e. there is a threshold $x^{*}_{\ell}$ such that
$x^{*}_{(\ell,d)}=x^{*}_{\ell}$, and the following equation holds:

$\sum_{d}g^{*}_{(\ell,d)}=S_{\ell}\frac{x^{*}_{\ell}}{C},$

where $\frac{x^{*}_{\ell}}{C}$ is the probability any driver from $\ell$
accepts a dispatch. Therefore,

$\epsilon\geq S_{\ell}-\sum_{d}g^{*}_{(\ell,d)}\geq
S_{\ell}-S_{\ell}\frac{x^{*}_{\ell}}{C}.$

So,

$x^{*}_{\ell}\geq C-\epsilon\frac{C}{S_{\ell}}\geq C-\sqrt{\epsilon}C,$

where the final inequality follows from our assumption that
$S_{\ell}\geq\sqrt{\epsilon}$.

Now we want to compare the optimal threshold to the chosen driver thresholds
$x^{\prime}_{(\ell,d)}$. Observe the total dispatch demand volume is larger
than if every destination used the minimum threshold
$\min_{d}x^{\prime}_{(\ell,d)}$:

$\sum_{d}g^{\prime}_{(\ell,d)}\geq
S_{\ell}\frac{\min_{d}x^{\prime}_{(\ell,d)}}{C}.$

By the same logic as above, we have

$\min_{d}x^{\prime}_{(\ell,d)}\geq C-\sqrt{\epsilon}C.$

Therefore we have $|x^{\prime}_{(\ell,d)}-x^{*}_{\ell}|\leq\sqrt{\epsilon}C$
for any route $(\ell,d)$ where $g^{*}_{(\ell,d)}>\epsilon$. Taking
$\epsilon^{\prime\prime}=\sqrt{\epsilon}C$ establishes the claimed result in
the case where approximately every driver serves a dispatch trip.

In the next case, we consider the thresholds when a non-negligible fraction of
drivers serve a relocation trip, i.e. where
$S_{\ell}-\sum_{d}g^{\prime}_{(\ell,d)}>\epsilon$. In this case, for any route
$(\ell,d)$ where $g^{\prime}_{(\ell,d)}>\epsilon$, the approximate incentive
compatibility conditions (47) and (48) establish the following equality:

$P_{(\ell,d)}-x^{\prime}_{(\ell,d)}+\mathcal{Q}^{\prime}(\ell,d,0)+\delta^{\prime}=\max_{d^{\prime}}\mathcal{Q}^{\prime}(\ell,d^{\prime},0),$

where $\delta^{\prime}$ is an error term smaller than $\epsilon$. Now, the
exact incentive compatibility conditions on
$(\bm{f}^{*},\bm{g}^{*},\bm{x}^{*})$ state the relationship

$P_{(\ell,d)}-x^{*}_{(\ell,d)}+\mathcal{Q}^{*}(\ell,d,0)=\max_{d^{\prime}}\mathcal{Q}^{*}(\ell,d^{\prime},0)$

holds. Combining the two equations, we have the difference between
$x^{*}_{(\ell,d)}$ and $x^{\prime}_{(\ell,d)}$ is bounded as follows:

$|x^{*}_{(\ell,d)}-x^{\prime}_{(\ell,d)}|\leq\delta^{\prime}+\left|\mathcal{Q}^{\prime}(\ell,d,0)-\mathcal{Q}^{*}(\ell,d,0)\right|+\left|\max_{d^{\prime}}\mathcal{Q}^{\prime}(\ell,d^{\prime},0)-\max_{d^{\prime}}\mathcal{Q}^{*}(\ell,d,0)\right|\leq\epsilon+2(\epsilon^{\prime}+\epsilon_{t+1}).$

Taking $\epsilon^{\prime\prime}=\epsilon+2(\epsilon^{\prime}+\epsilon_{t+1})$
shows the bound
$|x^{*}_{(\ell,d)}-x^{\prime}_{(\ell,d)}|\leq\epsilon^{\prime\prime}$,
finishing the proof of Lemma 15. ∎

We now finish the proof, by showing that both our backwards induction
assumptions hold at time period $t$. First, we show that the
$\epsilon$-equilibrium strategy profile produces actions which have total
welfare at most $\epsilon_{t}$ away from the optimal expected welfare, where
$\epsilon_{t}$ goes to $0$ as $\epsilon$ goes to $0$.

We have already established that $\bm{f}^{\prime}$ are approximately optimal
relocation trips with respect to the fluid dispatch trips $\bm{g}^{*}$. Lemma
15 shows that $(\bm{f}^{\prime},\bm{g}^{\prime},\bm{x}^{\prime})$ is an
approximately optimal fluid solution, when we additionally include the welfare
from dispatch trips in the objective function. Indeed, the welfare from
dispatch trips is a function of the dispatch trip volumes and the add-
passenger disutility thresholds. We know that
$\bm{g}^{\prime}\approx\bm{g}^{*}$, and Lemma 15 establishes
$\bm{x}^{\prime}\approx\bm{x}^{*}$, so the welfare generated by dispatch trips
at time $t$ under $(\bm{f}^{\prime},\bm{g}^{\prime},\bm{x}^{\prime})$ is
approximately equal to the welfare generated by dispatch trips at time $t$
under $(\bm{f}^{*},\bm{g}^{*},\bm{x}^{*})$. From the backwards induction
assumption, we know that from any time $t+1$ state, the drivers will achieve
welfare that is at most $\epsilon_{t+1}$ away from the optimal welfare from
that state. Therefore, it follows that the $\epsilon$-equilibrium strategy
which produces actions $(\bm{f}^{\prime},\bm{g}^{\prime},\bm{x}^{\prime})$
achieves approximately optimal social welfare at time $t$.

It remains to establish our second backwards induction assumption, i.e. we
need to establish that the expected utility of a driver positioned at a
location $\ell$, under the approximate equilibrium
$(\bm{f}^{\prime},\bm{g}^{\prime},\bm{x}^{\prime})$, is approximately equal to
the partial derivative of the state-dependent welfare function. Recall
$\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})$ denotes the expected value
for a driver of being positioned at $\ell$, under scenario $\omega_{t}$, and
supply-location vector $\mathbf{S}_{t}$. We characterize the value of being
positioned at $\ell$ as follows:

$\displaystyle\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})$
$\displaystyle=$
$\displaystyle\sum_{d\in\mathcal{L}}\frac{g^{\prime}_{(\ell,d)}}{S_{\ell}}\left(P_{(\ell,d)}-\frac{x^{\prime}_{(\ell,d)}}{2}+\mathcal{Q}^{\prime}(\ell,d,0)\right)+\sum_{d\in\mathcal{L}}\frac{f^{\prime}_{(\ell,d)}-g^{\prime}_{(\ell,d)}}{S_{\ell}}\mathcal{Q}^{\prime}(\ell,d,0)$
$\displaystyle\approx$
$\displaystyle\sum_{d\in\mathcal{L}}\frac{g^{\prime}_{(\ell,d)}}{S_{\ell}}\left(P_{(\ell,d)}-\frac{x^{\prime}_{(\ell,d)}}{2}+\mathcal{Q}^{\prime}(\ell,d,0)\right)+\frac{S_{\ell}-\sum_{d}g^{\prime}_{(\ell,d)}}{S_{\ell}}\left(\max_{d}\mathcal{Q}^{\prime}(\ell,d,0)\right)$
$\displaystyle\approx$
$\displaystyle\sum_{d\in\mathcal{L}}\frac{g^{*}_{(\ell,d)}}{S_{\ell}}\left(P_{(\ell,d)}-\frac{x^{*}_{(\ell,d)}}{2}+\mathcal{Q}^{*}(\ell,d,0)\right)+\frac{S_{\ell}-\sum_{d}g^{*}_{(\ell,d)}}{S_{\ell}}\left(\max_{d}\mathcal{Q}^{*}(\ell,d,0)\right)$
$\displaystyle=$ $\displaystyle\eta_{\ell}^{*}$ $\displaystyle=$
$\displaystyle\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{t}).$

The first line is the definition of the expected utility for a driver
positioned at $\ell$, the second line follows because all but a negligible
fraction of drivers who serve a relocation trip will serve an optimal
relocation trip, the third line follows because we have established that the
thresholds $\bm{x}^{\prime}$, the dispatch trips $\bm{g}^{\prime}$, and the
relocation utilities $\mathcal{Q}^{\prime}$, are all approximately equal to
their exact-equilibrium counterparts, and the fourth and fifth lines follow
from our earlier characterizations of the dual variables for the state
dependent optimization problem (Lemma 3).

Therefore, there is an error term $\epsilon_{t}$ such that $\epsilon_{t}$ is
an upper bound on the difference
$|\mathcal{V}_{t}(\ell,\omega_{t},\mathbf{S}_{t})-\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{t})|$, and such that $\epsilon_{t}$
goes to $0$ as $\max(\epsilon,\epsilon_{t+1})$ goes to $0$. This establishes
our backwards induction assumption, and therefore finishes the proof of
approximate welfare robustness in the fluid model.

##  Appendix C Approximate Welfare-Robustness Proof in the Two Level Model

###  C.1 Expected Welfare of a Strategy Profile in the Two Level Model

Let $W_{i}^{t}$ denote the welfare generated in the action driver by $i$ at
time $t$. The welfare $W_{i}^{t}$ differs from the driver reward $R_{i}^{t}$
when driver $i$ fulfils a dispatch in time $t$; in this case, the rider
collects utility equal to the difference between their value for the trip and
the trip price. Let $V_{i}^{t}$ be the value held by the rider whose dispatch
driver $i$ fulfils in time $t$, if any such rider exists. The welfare term
$W_{i}^{t}$ is defined as follows:

$W_{i}^{t}=\begin{cases}R_{i}^{t}+(V_{i}^{t}-P_{(\ell,d)}^{t})&\mbox{if
}a_{i}^{t}=(\ell,d,1),\\\ R_{i}^{t}&\mbox{otherwise.}\end{cases}$ (49)

The total welfare generated by the marketplace is then the sum over welfare
terms $W_{i}^{t}$ for all drivers $i$ and time periods $t$. In the context of
the two-level model, where the number of riders and drivers scales with the
population-size parameter $k$, we normalize the expected welfare by dividing
by $k$, so that expected welfare terms are comparable across different
population sizes.

Let $W_{\omega_{t}}(\mathbf{S}_{t};\Pi)$ be the expected welfare-to-go given a
strategy profile $\Pi$, a population size $k$, as a function of the market
state $(\omega_{t},\mathbf{S}_{t})$:

$W_{\omega_{t}}(\mathbf{S}_{t};\Pi,k)=\frac{1}{k}\mathbb{E}^{\Pi}\left[\sum_{i\in\mathcal{M}}\sum_{\tau=t}^{T}W_{i}^{\tau}\mid(\omega_{t},\mathbf{S}_{t})\right].$
(50)

Notice the expected welfare term $\Phi_{\omega_{t}}(\mathbf{S}_{t};\Pi)$
implicitly depends on the population size parameter $k$, but we omit this
dependence from the notation for convenience.

Recall that $\Phi_{\omega_{t}}(\mathbf{S}_{t})$ denotes the optimal value of
the state-dependent optimization problem given the state
$(\omega_{t},\mathbf{S}_{t})$, which corresponds to the optimal welfare
achievable given the state $(\omega_{t},\mathbf{S}_{t})$ in the stochastic
fluid model. The following Lemma states that the optimal fluid welfare is
always an upper bound on the expected welfare in the two-level model.

######  Lemma 16.

Let $\Pi$ be any strategy profile and consider any time $t$ with state
$(\omega_{t},\mathbf{S}_{t})$. The optimal welfare from the state
$(\omega_{t},\mathbf{S}_{t})$ in the fluid model is always larger than the
expected welfare generated by $\Pi$ in the two-level model, i.e.

$\Phi_{\omega_{t}}(\mathbf{S}_{t})\geq W_{\omega_{t}}(\mathbf{S}_{t};\Pi)$
(51)

always holds.

###  C.2 Proof of Theorem 3

In this section we summarize the key steps we take to prove Theorem 3. We
prove Theorem 3 by backwards induction on the time period. Fix a time period
$t\in[T]$. For each $k\geq 1$ assume there exists an error term
$\epsilon_{t+1}(k)$, converging to $0$ as $k\to\infty$, such that the the
following properties hold:

  * •

For every market state
$(\omega_{t+1},\mathbf{S}_{t+1})\in\mathcal{S}_{t+1}(\gamma)$, and any
approximate equilibrium $\Pi\in\mathcal{P}^{k}$,

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

  * •

For any approximate equilibrium $\Pi\in\mathcal{P}^{k}$, at time $t+1$, every
driver has expected utility-to-go that is close to the partial derivative of
the fluid optimization function. Specifically, for any market state
$(\omega_{t+1},\mathbf{S}_{t+1})$ and any driver $i\in\mathcal{M}_{t+1}$ whose
location is $\ell_{i}^{t+1}=\ell$, the following bound holds:

$\left|\mathbb{E}^{\Pi}[U_{i}^{t+1}\mid\ell_{i}^{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}(k).$
(52)

Our proof technique is to convert the stochastic actions taken by a strategy
profile $\Pi$ to an approximate equilibrium fluid strategy. We proceed via a
series of lemmas. The first Lemma shows that in an approximate equilibrium,
drivers at the same location use approximately the same disutility acceptance
thresholds. We provide the proof of Lemma 17 in Appendix C.3

######  Lemma 17.

There exists an error function $\delta(k)\geq 0$, converging to $0$ as
$k\to\infty$, such that the following is true: For any $k\geq 1$, any
approximate equilibrium $\Pi\in\mathcal{P}^{k}$, and any market state
$(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}(\gamma)$, let
$\bm{x}_{i}=(x_{i}^{d}:d\in\mathcal{L})$ be the disutility acceptance
threshold used by each active driver $i\in\mathcal{M}_{t}$. Then for each
location $\ell$ there exists a disutility threshold vector
$\bm{x}_{\ell}=(x_{(\ell,d)}:d\in\mathcal{L})$ such that the disutility
threshold vector used by every driver positioned at $\ell$ is at most
$\delta(k)$ away from $\bm{x}_{\ell}$, i.e.

$\max_{d\in\mathcal{L}}|x_{i}^{d}-x_{(\ell,d)}|\leq\delta(k),\ \ \ \ \forall
i\in\mathcal{M}_{t,\ell}.$ (53)

Our next Lemma shows that the stochastic actions taken under equilibrium
strategy profile $\Pi$ concentrate towards the fluid actions which arise under
the common disutility threshold established by Lemma 17.

For any $k\geq 1$, $\Pi\in\mathcal{P}^{k}$ and
$(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}(\gamma)$, let $(\bm{f},\bm{g})$
encode the stochastic trip volumes that occur on each route. Recall that
$a_{i}^{t}$ is a random variable which corresponds to the action that each
active driver $i\in\mathcal{M}_{t}$ takes in time period $t$. Define
$g_{(\ell,d)}$ by

$g_{(\ell,d)}=\frac{1}{k}\sum_{i\in\mathcal{M}_{t}}\mathbf{1}\left\\{a_{i}^{t}=(\ell,d,1)\right\\},\
\ \ \ \forall(\ell,d)\in\mathcal{L}^{2}$ (54)

and $f_{(\ell,d)}$ by

$f_{(\ell,d)}=g_{(\ell,d)}+\frac{1}{k}\sum_{i\in\mathcal{M}_{t}}\mathbf{1}\left\\{a_{i}^{t}=(\ell,d,0)\right\\}.\
\ \ \ \forall(\ell,d)\in\mathcal{L}^{2}$ (55)

Note that $(\bm{f},\bm{g})$ are random variables that depend on stochastic
dispatch demand, stochastic add-passenger disutilities, as well as the
randomness inherent to the matching process.

We want to compare $(\bm{f},\bm{g})$ to trips that arise in a fluid version of
the strategy $\Pi$. Define a fluid strategy profile that produces a disutility
threshold vector $\bm{x}$, where $\bm{x}$ is the common disutility threshold
vector whose existence is established by Lemma 17, and define the relocation
distribution $\mathbf{e}$ using the relocation destinations selected by all
drivers in the population: For each destination $d$ define

$e_{(\ell,d)}=1/|\mathcal{M}_{t,\ell}|\sum_{i\in\mathcal{M}_{t,\ell}}\mathbf{1}\\{r_{i}=d\\}$

where $r_{i}$ is the relocation destination selected by each driver $i$. Let
$\bar{\bm{f}},\bar{\bm{g}}$ be the fluid trip volumes that occur under the
market state $(\omega_{t},\mathbf{S}_{t})$ and the fluid strategy
$(\bm{x},\mathbf{e})$.

Recall that $\mathbf{S}_{\omega_{t+1}}(\bm{f})$ is the stochastic time $t+1$
supply location vector, given the time $t$ trips $\bm{f}$ and a time $t+1$
scenario $\omega_{t+1}$, and $\bar{\mathbf{S}}_{\omega_{t+1}}(\bar{\bm{f}})$
is the deterministic time $t+1$ supply location vector arising in the fluid
model. The following Lemma states that $\mathbf{S}_{\omega_{t+1}}(\bm{f})$ is
close to $\bar{\mathbf{S}}_{\omega_{t+1}}(\bar{\bm{f}})$ with high probability
for large $k$. We provide the proof of Lemma 18 in Appendix C.4.

######  Lemma 18.

There exists an error function $\kappa(k)\geq 0$, and another function
$q(k)\geq 0$, both converging to $0$ as $k\to\infty$, such that the following
is true: For any $k\geq 1$, any approximate equilibrium
$\Pi\in\mathcal{P}^{k}$, and any market state
$(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}(\gamma)$, let $(\bm{f},\bm{g})$
be the stochastic trip volumes and $(\bar{\bm{f}},\bar{\bm{g}})$ be the fluid
trip volumes as defined above. Then following inequalities holds:

$\displaystyle\mathbb{P}\left(\|\bm{g}-\bar{\bm{g}}\|_{1}\geq\kappa(k)\right)$
$\displaystyle\leq q(k),$
$\displaystyle\mathbb{P}\left(\|\bm{f}-\bar{\bm{f}}\|_{1}\geq\kappa(k)\right)$
$\displaystyle\leq q(k),$
$\displaystyle\mathbb{P}\left(\|\mathbf{S}_{\omega_{t+1}}(\bm{f})-\bar{\mathbf{S}}_{\omega_{t+1}}(\bar{\bm{f}})\|_{1}\geq\kappa(k)\right)$
$\displaystyle\leq q(k).$

Our final lemma shows that $(\bar{\bm{f}},\bar{\bm{g}},\bm{x})$ corresponds to
an approximate equilibrium in the fluid model. We defer the proof of Lemma 19
to Appendix C.5.

######  Lemma 19.

There exists an error function $\iota(k)\geq 0$, converging to $0$ as
$k\to\infty$, such that the following is true: For any $k\geq 1$, any
approximate equilibrium $\Pi\in\mathcal{P}^{k}$, and any market state
$(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}(\gamma)$, let
$(\bar{\bm{f}},\bar{\bm{g}})$ be the fluid trip volumes associated with $\Pi$
under the market state $(\omega_{t},\mathbf{S}_{t})$, and let $\bm{x}$ be the
common disutility threshold that drivers use under $\Pi$, established in Lemma
17. Then $(\bar{\bm{f}},\bar{\bm{g}},\bm{x})$ corresponds to an
$\iota(k)$-approximate equilibrium for the fluid model.

Lemma 18 and 19 are sufficient to conclude the proof of Theorem 3.

From the second part of Theorem 2 we know that there is an error function
$\epsilon(k)\geq 0$ which converges to $0$ as $k\to\infty$, such that the
welfare achieved by $(\bar{\bm{f}},\bar{\bm{g}},\bm{x})$ in the fluid model is
at most $\epsilon(k)$ off from the optimal welfare.

Next, observe a consequence of Lemma 18 is the expected welfare under $\Pi$
converges to the welfare of the associated fluid strategy, and the expected
utility of drivers at $\ell$ under $\Pi$ converges to the expected utility of
drivers at $\ell$ in the associated fluid strategy. That is, there exists an
error function $\theta(k)\geq 0$ converging to $0$ as $k\to\infty$ such that

$|W_{\omega_{t}}(\mathbf{S}_{t};\Pi,k)-\mathcal{W}_{\omega_{t}}(\bar{\bm{f}},\bar{\bm{g}},\bm{x})|\leq\theta(k),$

and

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

holds for every $k\geq 1$, $\Pi\in\mathcal{P}^{k}$,
$(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}(\gamma)$.

The above inequality establishes the second part of our backwards induction
assumption. The first part our backwards induction assumption also follows:

$W_{\omega_{t}}(\mathbf{S}_{t};\Pi,k)\geq\mathcal{W}_{\omega_{t}}(\bar{\bm{f}},\bar{\bm{g}},\bm{x})-\theta(k)\geq\Phi_{\omega_{t}}(\mathbf{S}_{t})-\epsilon(k)-\theta(k).$

###  C.3 Proof of Lemma 17

Below is a restatement of Lemma 17.

######  Lemma.

There exists an error function $\delta(k)\geq 0$, converging to $0$ as
$k\to\infty$, such that the following is true: For any $k\geq 1$, any
approximate equilibrium $\Pi\in\mathcal{P}^{k}$, and any market state
$(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}(\gamma)$, let
$\bm{x}_{i}=(x_{i}^{d}:d\in\mathcal{L})$ be the disutility acceptance
threshold used by each active driver $i\in\mathcal{M}_{t}$. Then for each
location $\ell$ there exists a disutility threshold vector
$\bm{x}_{\ell}=(x_{(\ell,d)}:d\in\mathcal{L})$ such that the disutility
threshold vector used by every driver positioned at $\ell$ is at most
$\delta(k)$ away from $\bm{x}_{\ell}$, i.e.

$\max_{d\in\mathcal{L}}|x_{i}^{d}-x_{(\ell,d)}|\leq\delta(k),\ \ \ \ \forall
i\in\mathcal{M}_{t,\ell}.$

###### Proof.

Fix $k\geq 1$, let $\Pi\in\mathcal{P}^{k}$ be an $\alpha_{k}$-equilibrium, and
let $(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}(\gamma)$ be any market
state with less than $\gamma$ total driver volume.

Consider any two drivers $i$ and $j$ positioned at the same location $\ell$,
and suppose there is some destination $d$ for which driver $i$ uses a lower
acceptance threshold than driver $j$, i.e. $x^{i}_{d}<x^{j}_{d}$. Let
$x\in(x_{i}^{d},x_{j}^{d})$ be a number in between the two thresholds and
consider the following events:

  1. 1.

Driver $i$ is allocated a dispatch towards $d$ and samples $X_{i}=x$ as their
add-passenger disutility.

  2. 2.

Driver $j$ is allocated a dispatch towards $d$ and samples $X_{j}=x$ as their
add-passenger disutility.

In event 1, driver $i$ rejects the dispatch towards $d$ and drives empty
towards their relocation destination $r_{i}$. The utility-to-go that driver
$i$ collects conditioned on event 1 is thus equal to

$\mathbb{E}[U^{t}_{i}\mid
d_{i}=d,X_{i}=x]=-c_{(\ell,r_{i})}+\mathbb{E}\left[U_{i}^{t+1}|\ell_{i}^{t+1}=r_{i}\right].$
(56)

From the definition of $\Pi$ being an approximate equilibrium, we know that
conditioned on event 1 the alternate action of accepting the dispatch towards
$d$ can only increase driver $i$’s utility to go by at most $\alpha_{k}$. This
implies the inequality

$-c_{(\ell,r_{i})}+\mathbb{E}\left[U_{i}^{t+1}|\ell_{i}^{t+1}=r_{i}\right]+\alpha_{k}\geq
P_{(\ell,d)}-x-c_{(\ell,d)}+\mathbb{E}\left[U_{i}^{t+1}\mid\ell_{i}^{t+1}=d\right].$
(57)

Let $Z=-c_{(\ell,d^{\prime})}+\alpha_{k}-P_{(\ell,d)}+x+c_{(\ell,d)}$ be a
temporary variable to track the non-utility to go terms from the above
expression, so we have

$Z+\mathbb{E}\left[U_{i}^{t+1}|\ell_{i}^{t+1}=r_{i}\right]\geq\mathbb{E}\left[U_{i}^{t+1}\mid\ell_{i}^{t+1}=d\right].$
(58)

From the backwards induction assumption (52), the time $t+1$ utilities are
approximately functions of the locations and market state:

$\displaystyle Z+\mathbb{E}\left[\frac{\partial}{\partial
S_{r_{i}}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1})+\epsilon_{t+1}(k)\mid\ell_{i}^{t+1}=r_{i}\right]$
(59) $\displaystyle\geq\ \ \ $ $\displaystyle
Z+\mathbb{E}\left[U_{i}^{t+1}|\ell_{i}^{t+1}=r_{i}\right]$ (60)
$\displaystyle\geq\ \ \ $
$\displaystyle\mathbb{E}\left[U_{i}^{t+1}\mid\ell_{i}^{t+1}=d\right]$ (61)
$\displaystyle\geq\ \ \ $
$\displaystyle\mathbb{E}\left[\frac{\partial}{\partial
S_{d}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1})-\epsilon_{t+1}(k)\mid\ell_{i}^{t+1}=d\right].$
(62)

In the above, $\mathbf{S}_{t+1}$ is the (stochastic) supply-location vector
the time $t+1$, and $\epsilon(\omega_{t+1},\mathbf{S}_{t+1})$ is the error
term provided in the backwards induction assumption Assumption 3.

Next, Assumption 4 states that we can move from a conditional expectation to
an unconditional expectation, at the cost of an error term $\beta_{k}$ which
converges to $0$ as $k\to\infty$:

$Z+\mathbb{E}\left[\frac{\partial}{\partial
S_{r_{i}}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1})-\frac{\partial}{\partial
S_{d}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1})\right]+2\epsilon_{t+1}(k)+\beta_{k}\geq
0.$ (63)

In the second event, driver $j$ accepts the dispatch and drives a passenger
towards $d$. The utility to go that driver $j$ collects conditioned on event 2
is equal to

$\mathbb{E}[U_{j}^{t}\mid
d_{j}=d,X_{j}=x]=P_{(\ell,d)}-x-c_{(\ell,d)}+\mathbb{E}\left[U_{j}^{t+1}\mid\ell_{j}^{t+1}=d\right].$

From $\Pi$ being an approximate equilibrium, we know that the utility of
accepting the dispatch towards $d$ is at most $\alpha_{k}$ short of the
utility from any other action, in particular it is at most $\alpha_{k}$ short
from the utility of taking a relocation trip towards driver $i$’s destination
$r_{i}$. This implies the inequality

$P_{(\ell,d)}-x-c_{(\ell,d)}+\mathbb{E}\left[U_{j}^{t+1}\mid\ell_{j}^{t+1}=d\right]+\alpha_{k}\geq-
c_{(\ell,r_{i})}+\mathbb{E}\left[U_{j}^{t+1}|\ell_{j}^{t+1}=r_{i}\right].$

Following the same steps as before, we deduce the bound

$Z^{\prime}+\mathbb{E}\left[\frac{\partial}{\partial
S_{d}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1})-\frac{\partial}{\partial
S_{r_{i}}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1})\right]+2\epsilon_{t+1}(k)+\beta_{k}\geq
0,$ (64)

where $Z^{\prime}=-Z+2\alpha_{k}.$

Now, recall the terms $Z$ in equation (63) and $Z^{\prime}$ in equation (64)
include an arbitrary disutility threshold $x$ in between $x^{d}_{i}$ and
$x^{d}_{j}$. Let us now write $Z(x)$ and $Z^{\prime}(x)$ to explicitly denote
the dependence on $x$. Next, consider what happens when we add the equations
(63) using the threshold $x=x_{i}^{d}$ and (64) using the threshold
$x=x_{j}^{d}$. The partial derivative terms cancel, and we are left with

$Z(x_{i}^{d})+Z^{\prime}(x_{j}^{d})+4\epsilon_{t+1}(k)+2\beta_{k}\geq 0.$

Observe that
$Z(x_{i}^{d})+Z^{\prime}(x_{j}^{d})=x_{i}^{d}-x_{j}^{d}+2\alpha_{k}$.
Therefore, we have

$x_{j}^{d}-x_{i}^{d}\leq 2\alpha_{k}+4\epsilon_{t+1}(k)+\beta_{k}.$

Therefore, the Lemma holds by setting $\delta_{k}$ equal to the right hand
side of the above equation and taking $\bm{x}_{\ell}$ to be the threshold
vector $\bm{x}_{i}$ used by any driver located at $\ell$. ∎

###  C.4 Proof of Lemma 18

Below is a restatement of Lemma 18.

######  Lemma.

There exists an error function $\kappa(k)\geq 0$, and another function
$q(k)\geq 0$, both converging to $0$ as $k\to\infty$, such that the following
is true: For any $k\geq 1$, any approximate equilibrium
$\Pi\in\mathcal{P}^{k}$, and any market state
$(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}(\gamma)$, let $(\bm{f},\bm{g})$
be the stochastic trip volumes and $(\bar{\bm{f}},\bar{\bm{g}})$ be the fluid
trip volumes as defined above. Then following inequalities holds:

$\displaystyle\mathbb{P}\left(\|\bm{g}-\bar{\bm{g}}\|_{1}\geq\kappa(k)\right)$
$\displaystyle\leq q(k),$
$\displaystyle\mathbb{P}\left(\|\bm{f}-\bar{\bm{f}}\|_{1}\geq\kappa(k)\right)$
$\displaystyle\leq q(k),$
$\displaystyle\mathbb{P}\left(\|\mathbf{S}_{\omega_{t+1}}(\bm{f})-\bar{\mathbf{S}}_{\omega_{t+1}}(\bar{\bm{f}})\|_{1}\geq\kappa(k)\right)$
$\displaystyle\leq q(k).$

###### Proof.

These bounds follow from the matching process concentration results discussed
in Appendix E.

From Lemma LABEL:lem:matching_process_concentration we have concentration
functions $\epsilon_{1}(k)$, $q_{1}(k)$, with $\epsilon_{1}(k)/k\to 0$ and
$q_{1}(k)\to 0$ as $k\to 0$, such that

$\mathbb{P}\left(|G_{(\ell,d)}-\bar{G}_{(\ell,d)}|\geq\epsilon_{1}(k)\right)\leq
q_{1}(k),$

where $G_{(\ell,d)}$ and $\bar{G}_{(\ell,d)}$ are the unscaled number of
dispatches and fluid dispatches along the route $(\ell,d)$. Take
$\kappa_{1}(k)=\epsilon_{1}(k)|\mathcal{L}|^{2}/k$,
$p_{1}(k)=|\mathcal{L}|^{2}q_{1}(k)$ and observe:

$\displaystyle\mathbb{P}\left(\|\bm{g}-\bar{\bm{g}}\|_{1}\geq\kappa_{1}(k)\right)$
$\displaystyle\leq\sum_{(\ell,d)}\mathbb{P}(|g_{(\ell,d)}-\bar{g}_{(\ell,d)}|\leq\kappa_{1}(k)/|\mathcal{L}|^{2})$
$\displaystyle=\sum_{(\ell,d)}\mathbb{P}(|G_{(\ell,d)}-\bar{G}_{(\ell,d)}|\leq\epsilon_{1}(k))$
$\displaystyle\leq|\mathcal{L}|^{2}q_{1}(k)=p_{1}(k)$

From Lemma 28 we have concentration functions $\epsilon_{2}(k)$, $q_{2}(k)$,
with $\epsilon_{2}(k)/k\to 0$ and $q_{2}(k)\to 0$ as $k\to 0$, such that

$\mathbb{P}\left(|H_{(\ell,d)}-\bar{H}_{(\ell,d)}|\geq\epsilon_{2}(k)\right)\leq
q_{2}(k),$

where $H_{(\ell,d)}$ is the number of relocation trips along $(\ell,d)$. Take
$\kappa_{2}(k)=\kappa_{1}(k)+\epsilon_{2}(k)|\mathcal{L}|^{2}/k$ and
$p_{2}(k)=p_{1}(k)+|\mathcal{L}|^{2}q_{2}(k)$ and observe:

$\displaystyle\mathbb{P}\left(\|\bm{f}-\bar{\bm{f}}\|_{1}\geq\kappa_{2}(k)\right)$
$\displaystyle\leq\mathbb{P}\left(\|\bm{f}-\bar{\bm{f}}\|_{1}\geq\kappa_{2}(k)\mid\|\bm{g}-\bar{\bm{g}}\|_{1}\leq\kappa_{1}(k)\right)+\mathbb{P}\left(\|\bm{g}-\bar{\bm{g}}\|_{1}\geq\kappa_{1}(k)\right)$
$\displaystyle\leq\sum_{(\ell,d)}\mathbb{P}\left(|H_{(\ell,d)}-\bar{H}_{(\ell,d)}|\geq\epsilon_{2}(k)\right)+p_{1}(k)$
$\displaystyle\leq|\mathcal{L}|^{2}q_{2}(k)+p_{1}(k)=p_{2}(k).$

Finally, we observe that

$\|\mathbf{S}_{\omega_{t+1}}(\bm{f})-\bar{\mathbf{S}}_{\omega_{t+1}}(\bar{\bm{f}})\|_{1}\leq\|\bm{f}-\bar{\bm{f}}\|_{1}+\|\mathbf{M}_{\omega_{t+1}}-\bar{\mathbf{M}}_{\omega_{t+1}}\|_{1}$

where $\mathbf{M}_{\omega_{t+1}}$ is the vector counting driver-entry at time
$t+1$ under scenario $\omega_{t+1}$. By Assumption 1 we have concentration
functions $\epsilon_{3}(k)$ and $q_{3}(k)$ which bound the convergence of
$\mathbf{M}_{\omega_{t+1}}$ to $\bar{\mathbf{M}}_{\omega_{t+1}}$. We define
$\kappa_{3}(k)=\kappa_{2}(k)+\epsilon_{3}(k)|\mathcal{L}|^{2}/k$ and
$p_{3}(k)=p_{2}(k)+|\mathcal{L}|q_{3}(k)$.

∎

###  C.5 Proof of Lemma 19

Below is a restatement of Lemma 19.

######  Lemma.

There exists an error function $\iota(k)\geq 0$, converging to $0$ as
$k\to\infty$, such that the following is true: For any $k\geq 1$, any
approximate equilibrium $\Pi\in\mathcal{P}^{k}$, and any market state
$(\omega_{t},\mathbf{S}_{t})\in\mathcal{S}_{t}(\gamma)$, let
$(\bar{\bm{f}},\bar{\bm{g}})$ be the fluid trip volumes associated with $\Pi$
under the market state $(\omega_{t},\mathbf{S}_{t})$, and let $\bm{x}$ be the
common disutility threshold that drivers use under $\Pi$, established in Lemma
17. Then $(\bar{\bm{f}},\bar{\bm{g}},\bm{x})$ corresponds to an
$\iota(k)$-approximate equilibrium for the fluid model.

###### Proof.

We outline the proof for Lemma 19. For any $k\geq 1$ and
$\alpha_{k}$-equilibrium $\Pi$, let $\Sigma$ be the fluid strategy we
associate with $\Pi$, which maps market states $(\omega_{t},\mathbf{S}_{t})$
to a disutility threshold vector $\bm{x}$ that is approximately common to all
drivers (see Lemma 17), and a relocation distribution $\mathbf{e}$ which is
derived from the population distribution of relocation destinations.

To show that $\Sigma$ is an approximate equilibrium under the fluid model, it
is sufficient to show that the continuation utility under the two-level model
with strategy $\Pi$ (which is approximately incentive compatible) is close to
the continuation utility in the fluid model with strategy $\Sigma$. This can
be accomplished by providing a bound

$\left|\mathbb{E}\left[\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\mathbf{S}_{t+1}(\bm{f}))-\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{t+1}(\bar{\bm{f}}))\right]\right|\leq\epsilon_{k},$

that holds uniformly in the market state and location $\ell$, where the
constant $\epsilon_{k}$ goes to $0$ as $k\to\infty$. Approximate incentive
compatibility conditions on $\Sigma$ then follow from approximate incentive
compatibility conditions on $\Pi$.

To provide this bound, recall that Lemma 3 establishes that the partial
derivative $\frac{\partial}{\partial S_{\ell}}\Phi_{\omega_{t+1}}(\cdot)$
exists and is continuous. The space of supply-location vectors $\mathbf{S}$
satisfying $\sum_{\ell}S_{\ell}\leq\gamma$ is compact, and a continuous
function over a compact set is bounded. Let $U$ be the maximum value.

Moreover, a continuous function over a compact set is uniformly continuous.
Therefore, for every $\epsilon>0$ there exists a $\delta(\epsilon)>0$ such
that, for any $\mathbf{S}_{1},\mathbf{S}_{2}$ in $\mathcal{S}(\gamma)$
satisfying $\|\mathbf{S}_{1}-\mathbf{S}_{2}\|\leq\delta$, we have
$\|\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\mathbf{S}_{1})-\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\mathbf{S}_{2})\|\leq\epsilon$.

For any $\delta>0$, define

$\epsilon(\delta)=\max\left(\|\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\mathbf{S}_{1})-\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\mathbf{S}_{2})\|:\mathbf{S}_{1},\mathbf{S}_{2}\in\mathcal{S}(\gamma),\|\mathbf{S}_{1}-\mathbf{S}_{2}\|\leq\delta\right).$

Because the partial derivative $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\cdot)$ is uniformly continuous, the error term
$\epsilon(\delta)$ goes to $0$ as $\delta$ goes to $0$.

Next, we use the fact from Lemma 18 that $\mathbf{S}_{\omega_{t+1}}(\bm{f})$
concentrates towards $\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f})$. Let
$\kappa(k)$, $q(k)$ be functions such that

$\mathbb{P}\left(\|\mathbf{S}_{\omega_{t+1}}(\bm{f})-\bar{\mathbf{S}}_{\omega_{t+1}}(\bar{\bm{f}})\|_{1}\geq\kappa(k)\right)\leq
q(k).$

For simplicity, write $\mathbf{S}=\mathbf{S}_{\omega_{t+1}}(\bm{f})$,
$\bar{\mathbf{S}}=\bar{\mathbf{S}}_{\omega_{t+1}}(\bar{\bm{f}})$, and
$F(\mathbf{S})=\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t+1}}(\mathbf{S})$. We have:

$\displaystyle\mathbb{E}[F(\mathbf{S})-F(\bar{\mathbf{S}})]|$
$\displaystyle\leq\mathbb{E}[F(\mathbf{S})-F(\bar{\mathbf{S}})\mid|\mathbf{S}-\bar{\mathbf{S}}|\leq\kappa_{k}]|+Uq_{k}$
$\displaystyle\leq\epsilon(\kappa_{k})+U(1-q_{k}).$

Therefore the term we needed to bound is uniformly bounded by a term
$\epsilon(\kappa_{k})+Uq_{k}$ which converges to $0$ as $k\to\infty$, so
incentive compatibility conditions on $\Sigma$ follow from incentive
compatibility conditions on $\Pi$. ∎

##  Appendix D Partial Derivatives of the State-Dependent Optimization Problem

In this section we prove a number of results about the fluid optimization
problem.

###  D.1 Proof of Lemma 1

######  Lemma.

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>0$, and the derivative at each $g>0$ satisfies:

$\frac{d}{dg}U_{(\ell,d,\omega_{t})}(g)=P_{(\ell,d,\omega_{t})}(g).$

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

###### Proof.

Let us write the utility function as $U(f)=U_{(\ell,d,\omega_{t})}(f),$ First,
observe that the utility function can be equivalently written as the following
equation

$U(g)=\bar{D}\mathbb{E}\left[V\mathbf{1}_{\left\\{V\geq
F^{-1}\left(1-\frac{g\wedge\bar{D}}{\bar{D}}\right)\right\\}}\right],$ (65)

where we write $\bar{D}$ in place of $\bar{D}_{(\ell,d,\omega_{t})}$, $F$ to
mean $F_{(\ell,d,\omega_{t})}$, and $f\wedge\bar{D}$ to mean
$\min(f,\bar{D})$. This characterization is justified by the following series
of equalities:

$\displaystyle\mathbb{E}\left[V\mathbf{1}_{\left\\{V\geq
F^{-1}\left(1-\frac{g\wedge\bar{D}}{\bar{D}}\right)\right\\}}\right]$
$\displaystyle=\mathbb{E}\left[V\mid V\geq
F^{-1}\left(1-\frac{g\wedge\bar{D}}{\bar{D}}\right)\right]\mathbb{P}\left(V\geq
F^{-1}\left(1-\frac{g\wedge\bar{D}}{\bar{D}}\right)\right)$
$\displaystyle=\mathbb{E}\left[V\mid V\geq
F^{-1}\left(1-\frac{g\wedge\bar{D}}{\bar{D}}\right)\right]\left(1-F\left(F^{-1}\left(1-\frac{g\wedge\bar{D}}{\bar{D}}\right)\right)\right)$
$\displaystyle=\mathbb{E}\left[V\mid V\geq
F^{-1}\left(1-\frac{g\wedge\bar{D}}{\bar{D}}\right)\right]\frac{g\wedge\bar{D}}{\bar{D}}.$

Next, recall that if $X$ is a uniform $[0,1]$ random variable then $F^{-1}(X)$
is a random variable with distribution function $F$. Using the fact that if
$X$ is uniform $[0,1]$ then so too is $1-X$, from the characterization (65) we
have the following equalities:

$\displaystyle U(g)$
$\displaystyle=\bar{D}\int_{0}^{1}F^{-1}(u)\mathbf{1}_{\left\\{F^{-1}(u)\geq
F^{-1}\left(1-\frac{g\wedge\bar{D}}{\bar{D}}\right)\right\\}}du$
$\displaystyle=\bar{D}\int_{0}^{1}F^{-1}(1-u)\mathbf{1}_{\left\\{F^{-1}(1-u)\geq
F^{-1}\left(1-\frac{g\wedge\bar{D}}{\bar{D}}\right)\right\\}}du$
$\displaystyle=\bar{D}\int_{0}^{1}F^{-1}(1-u)\mathbf{1}_{\left\\{\frac{g\wedge\bar{D}}{\bar{D}}\geq
u\right\\}}du$
$\displaystyle=\bar{D}\int_{0}^{\frac{g\wedge\bar{D}}{\bar{D}}}F^{-1}(1-u)du.$

Now, fix any $0<g<\bar{D}$ and consider the above expression. The assumption
$g<\bar{D}$ means that the integral upper bound
$\frac{g\wedge\bar{D}}{\bar{D}}$ is simply $\frac{g}{\bar{D}}$, and from the
assumption that $F^{-1}$ satisfies Assumption 2 we know that $F^{-1}(\cdot)$
is continuous. Hence, by the fundamental theorem of calculus the function
$U(g)$ is differentiable at $0<g<\bar{D}$, and using the chain rule we compute
the derivative to be:

$\frac{d}{dg}U(g)=\bar{D}F^{-1}\left(1-\frac{g}{\bar{D}}\right)\frac{1}{\bar{D}}=F^{-1}\left(1-\frac{g}{\bar{D}}\right).$

Further, note that $U(g)$ is constant for $g\geq\bar{D}$, from which we
conclude that $\frac{d}{dg}U(g)=0$ for $g>\bar{D}$. Finally, we must establish
existence of the derivative at the point $g=\bar{D}$. To this end, it suffices
to show that limit of the partial derivatives from below $g=\bar{D}$ and from
above $g=\bar{D}$ are equal. This fact follows from the second assertion in
Assumption 2 which states that $F^{-1}(0)=0$:

$\lim_{g\uparrow\bar{D}}\frac{d}{dg}U(g)=\lim_{g\uparrow\bar{D}}F^{-1}\left(1-\frac{g}{\bar{D}}\right)=0=\lim_{g\downarrow\bar{D}}\frac{d}{dg}U(g).$

Thus, we have established the derivative $\frac{d}{dg}U(g)$ exists for all
$g>0$ and is equal to $P_{(\ell,d,\omega_{t})}(g).$ Concavity of $U(\cdot)$
follows from the observation that this derivative is non-increasing in $g$.

To show that (10) we has a concave objective we have to show that the
remaining terms in $\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})$ are also concave.
Well, clearly the linear costs are concave. And finally, the add-passenger
disutility cost function
$-A(\bm{g}^{T}\mathbf{1}_{\ell},\bm{f}^{T}\mathbf{1}_{\ell})$ is convex, from
the equation (17) and Lemma 20. ∎

######  Lemma 20.

Define

$f(x,y)=\begin{cases}\frac{y^{2}}{x}&\mbox{if }x>0,\\\ 0&\mbox{if
}x=0.\end{cases}$

Then $f$ is convex over the domain $x,y\geq 0$, $y\leq x$.

###### Proof.

Let $(x_{1},y_{1})$ and $(x_{2},y_{2})$ be two points in the domain of $f$,
and let $\lambda\in[0,1]$. We need to check

$f(\lambda(x_{1},y_{1})+(1-\lambda)(x_{2},y_{2}))\leq\lambda
f(x_{1},y_{1})+(1-\lambda)f(x_{2},y_{2}).$

Let’s start with the case where $x_{1}$ and $x_{2}$ are both nonzero. In this
case, the inequality we have to check is given by

$\frac{\left(\lambda y_{1}+(1-\lambda)y_{2}\right)^{2}}{\lambda
x_{1}+(1-\lambda)x_{2}}\leq\lambda\frac{y_{1}^{2}}{x_{1}}+(1-\lambda)\frac{y_{2}^{2}}{x_{2}}.$

We will verify this inequality by applying the Cauchy-Schwarz inequality.
Define the following values:

$u_{1}=\frac{\lambda y_{1}}{\sqrt{\lambda x_{1}}}\ \
u_{2}=\frac{(1-\lambda)y_{2}}{\sqrt{(1-\lambda)x_{2}}}\ \ v_{1}=\sqrt{\lambda
x_{1}}\ \ v_{2}=\sqrt{(1-\lambda)x_{2}}.$

The Cauchy-Schwarz inequality says $u^{T}v\leq\|u\|\|v\|$. Observe the
following equalities:

$\displaystyle(u^{T}v)^{2}$ $\displaystyle=\left(\lambda
y_{1}+(1-\lambda)y_{2}\right)^{2},$ $\displaystyle\|v\|^{2}$
$\displaystyle=\lambda x_{1}+(1-\lambda)x_{2},$ $\displaystyle\|u\|^{2}$
$\displaystyle=\lambda\frac{y_{1}^{2}}{x_{1}}+(1-\lambda)\frac{y_{2}^{2}}{x_{2}}.$

Rearranging C-S we have

$\frac{(u^{T}v)^{2}}{\|v\|^{2}}\leq\|u\|^{2},$

which implies the desired inequality holds, and hence $f$ is convex whenever
$x_{1}$ and $x_{2}$ are both nonzero.

The case where $x_{1}$ and $x_{2}$ are both zero is immediate. It remains to
check the case where $x_{1}$ is nonzero and $x_{2}$ is $0$. In this case,
$y_{2}$ must also be zero, because of the constraint $y\leq x$. Therefore we
have to verify

$f(\lambda(x_{1},y_{1}))\leq\lambda f(x_{1},y_{1}).$

By inspection we see that $f(\lambda(x,y))=\lambda f(x,y)$ is always
satisfied, so $f$ is convex in this case as well. ∎

###  D.2 State-Dependent Optimization Problem

For clarity we restate the state-dependent optimization problem below. Fix a
time period $t$ and a scenario $\omega_{t}$. The state-dependent optimization
problem depends on a supply-location vector
$\mathbf{S}=(S_{\ell}:\ell\in\mathcal{L})$ where each component $S_{\ell}\geq
0$ specifies the volume of active drivers at location $\ell$. Active drivers
at a location $\ell$ consist of drivers who took a trip destined towards
$\ell$ at the previous time period $t-1$, as well as new drivers who enter the
market at location $\ell$ in the current time period $t$. The state-dependent
optimization problem solves for the welfare-optimal trips in the current time
period in the stochastic fluid model, given the market state specified by the
scenario $\omega_{t}$ and the supply-location vector $\mathbf{S}$. We write
$\Phi_{\omega_{t}}(\mathbf{S})$ to denote the value of the state-dependent
optimization problem under the scenario $\omega_{t}$ as a function of the
supply-location vector $\mathbf{S}$. The function
$\Phi_{\omega_{t}}(\mathbf{S})$ is formally defined as the value of the
following optimization problem:

$\displaystyle\Phi_{\omega_{t}}(\mathbf{S})\equiv\ \ \ \
\;\;\;\sup_{\bm{f},\bm{g}}$ $\displaystyle\ \ \
\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})+\mathbb{E}_{\omega_{t}}\left[\Phi_{\omega_{t+1}}(\mathbf{S}_{\omega_{t+1}}(\bm{f}))\right]$
(66) subject to $\displaystyle f_{(\ell,d)}\geq 0\ $
$\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (67) $\displaystyle
g_{(\ell,d)}\geq 0\ $ $\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (68)
$\displaystyle f_{(\ell,d)}\geq g_{(\ell,d)}\ $
$\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (69)
$\displaystyle\sum_{d\in\mathcal{L}}f_{(\ell,d)}=S_{\ell}$
$\displaystyle\forall\ell\in\mathcal{L}$ (70)

The decision variable $\bm{f}=(f_{(\ell,d)}:(\ell,d)\in\mathcal{L}^{2})$ has
components $f_{(\ell,d)}$ which specify the total trip volume along each route
$(\ell,d)$. By total trip volume we mean$f_{(\ell,d)}$ specifies the sum of
the relocation-trip volume and the dispatch trip-volume. The decision variable
$\bm{g}=(g_{(\ell,d)}:(\ell,d)\in\mathcal{L}^{2})$ has components
$g_{(\ell,d)}$ which specify the dispatch trip volume along each route
$(\ell,d)$.

The objective function is the sum of two functions:
$\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})$ specifies the welfare collected in
the current time period $t$, and
$\mathbb{E}_{\omega_{t}}\left[\Phi_{\omega_{t+1}}(\mathbf{S}_{\omega_{t+1}}(\bm{f}))\right]$
specifies the welfare to be collected in future time periods.

When $t=T$ is the final time period we just take
$\mathbb{E}_{\omega_{t}}\left[\Phi_{\omega_{t+1}}(\mathbf{S}_{\omega_{t+1}}(\bm{f}))\right]$
to be $0$. When $t<T$, we define $\mathbf{S}_{\omega_{t+1}}(\bm{f})$ to be the
supply-location vector arising at time $t+1$ under the trip volumes specified
by $\bm{f}$ and the future scenario $\omega_{t+1}$. The expectation
$\mathbb{E}_{\omega_{t}}\left[\cdot\right]$ is taken over all time $t+1$
scenarios given the time $t$ scenario $\omega_{t}$. The function
$\mathbf{S}_{\omega_{t+1}}(\bm{f})$ follows the convention that upply-location
vectors include new drivers who enter the market in the relevant time period.
Let us write $S_{\omega_{t+1},\ell}(\bm{f})$ for the component of the supply-
location vector $\mathbf{S}_{\omega_{t+1}}(\bm{f})$ corresponding to location
$\ell$. $S_{\omega_{t+1},\ell}(\bm{f})$ is defined formally by the following
equation

$S_{\omega_{t+1},\ell}(\bm{f})=\frac{1}{k}M_{\omega_{t+1},\ell}+\sum_{o\in\mathcal{L}}f_{(o,\ell)},$
(71)

where $M_{\omega_{t+1},\ell}$ is the volume of new drivers who enter the
market at location $\ell$ under the scenario $\omega_{t+1}$ and the sum is
over all routes whose destination location is $\ell$.

The utility collected in the current time period is the difference between the
rider value we generate by serving dispatches and the disutility that drivers
incur. Since we assume the price is a transfer from riders to drivers the
price does not appear explicitly in the objective function. The function
$\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})$ is formally 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)})-\left(\sum_{(\ell,d)\in\mathcal{L}^{2}}c_{(\ell,d)}f_{(\ell,d)}+\sum_{\ell}A(\bm{g}^{T}\mathbf{1}_{\ell},\bm{f}^{T}\mathbf{1}_{\ell})\right).$
(72)

The function $U_{(\ell,d,\omega_{t})}(g_{(\ell,d)})$ specifies the total rider
value generated as a function of dispatch-trip volume along the route
$(\ell,d)$, the function
$A(\bm{g}^{T}\mathbf{1}_{\ell},\bm{f}^{T}\mathbf{1}_{\ell})$ specifies the
total add-passenger disutility incurred by drivers located at $\ell$, as a
function of the volume of dispatch trips originating from $\ell$,
$\bm{g}^{T}\mathbf{1}_{\ell}$, and the total volume of available drivers
located at $\ell$, $\bm{f}^{T}\mathbf{1}_{\ell}$.

We take $\mathbf{1}_{\ell}$ to be an indicator vector indexed by pairs of
locations, where the value corresponding to each
$(\ell^{\prime},d)\in\mathcal{L}^{2}$ is $1$ if $\ell^{\prime}=\ell$ and $0$
otherwise. With this convention, the quantities $\bm{g}^{T}\mathbf{1}_{\ell}$
and $\bm{f}^{T}\mathbf{1}_{\ell}$ specify the volume of dispatch trips
originating from $\ell$ and the total volume of trips originating from $\ell$,
respectively:

$\displaystyle\bm{g}^{T}\mathbf{1}_{\ell}$
$\displaystyle=\sum_{d\in\mathcal{L}}g_{(\ell,d)},$
$\displaystyle\bm{f}^{T}\mathbf{1}_{\ell}$
$\displaystyle=\sum_{d\in\mathcal{L}}f_{(\ell,d)}.$

Assuming $\bm{f}$ satisfies the flow-conservation constraint (70), the total
trip volume originating from $\ell$ is equal to the total volume of supply
positioned at $\ell$:

$\bm{f}^{T}\mathbf{1}_{\ell}=S_{\ell}.$

###  D.3 Optimality Conditions

We now derive the Lagrangian optimality conditions for the state-dependent
optimization problem (66). For succinctness, we use the following notation for
the objective function:

$\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})+\mathbb{E}_{\omega_{t}}\left[\Phi_{\omega_{t+1}}(\mathbf{S}_{\omega_{t+1}}(\bm{f}))\right].$
(73)

We begin by converting the optimization problem to a convex minimization
problem where all inequality constraints have an upper bound of $0$:

$\displaystyle-\Phi_{\omega_{t}}(\mathbf{S})\equiv\ \ \ \
\;\;\;\inf_{\bm{f},\bm{g}}$ $\displaystyle\ \ \
-\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})$ (74) subject to $\displaystyle-
f_{(\ell,d)}\leq 0\ $ $\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (75)
$\displaystyle-g_{(\ell,d)}\leq 0\ $
$\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (76) $\displaystyle
g_{(\ell,d)}-f_{(\ell,d)}\leq 0\ $
$\displaystyle\forall(\ell,d)\in\mathcal{L}^{2}$ (77)
$\displaystyle\sum_{d\in\mathcal{L}}f_{(\ell,d)}-S_{\ell}=0$
$\displaystyle\forall\ell\in\mathcal{L}$ (78)

We associate dual variables $\alpha_{(\ell,d)}$, $\beta_{(\ell,d)}$,
$\gamma_{(\ell,d)}$ and $\eta_{\ell}$ with each of the constraints (75), (76),
(77), (78), respectively. We will write
$\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta}$ to indicate the vector of dual
variables.

Since all we have done is changed the sign and direction of the objective
function and algebraically rearranged the inequality constraint functions, the
optimization problems (74) and (66) have the same set of optimal solutions.

We now obtain the Lagrangian function for the optimization problem (74):

$\displaystyle L(\bm{f},\bm{g};\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta})$
$\displaystyle=-\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})+\sum_{(\ell,d)}\left[\gamma_{(\ell,d)}(g_{(\ell,d)}-f_{(\ell,d)})-\alpha_{(\ell,d)}f_{(\ell,d)}-\beta_{(\ell,d)}g_{(\ell,d)}\right]$
$\displaystyle\hskip
71.13188pt+\sum_{\ell}\eta_{\ell}\left(\sum_{d}f_{(\ell,d)}-S_{\ell}\right).$

Because all of the constraints for the problem (74) are linear, and the primal
problem (66) has a finite optimal solution, we know strong duality holds Lewis
(2006). Therefore, a feasible solution $(\bm{f},\bm{g})$ is optimal if and
only if there exist feasible dual variables
$\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta}$ for which the stationarity
conditions and the complementary slackness conditions hold. For dual
feasibility to hold the variables associated with inequality constraints must
be nonnegative, that is the following inequalities must hold pointwise:

$\bm{\alpha}\geq 0,\ \bm{\beta}\geq 0,\ \bm{\gamma}\geq 0.$

The complementary slackness conditions are satisfied when the following
equations hold for all origin-destination pairs $(\ell,d)\in\mathcal{L}^{2}$:

$\alpha_{(\ell,d)}f_{(\ell,d)}=0,\ \beta_{(\ell,d)}g_{(\ell,d)}=0,\
\gamma_{(\ell,d)}(g_{(\ell,d)}-f_{(\ell,d)})=0,$

that is the dual variables associated with inequality constraints must be $0$
unless the corresponding inequality constraint is tight at the primal
solution.

Finally, the stationarity conditions are satisfied when the primal solution
$(\bm{f},\bm{g})$ are a stationary point of the Lagrangian function when the
dual variables are held fixed. Notice that when we hold the dual variables
fixed the Lagrangian is a convex function of the primal solution, so a primal
solution $(\bm{f},\bm{g})$ is a stationary point if and only if $0$ is a
subgradient of the Lagrangian at $(\bm{f},\bm{g})$. We use the notation
$\partial L(\bm{f},\bm{g};\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta})$ to
refer to the subgradient of the Lagrangian where the dual variables
$\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta}$ are held fixed. The subgradient
condition for a primal solution $(\bm{f},\bm{g})$ to be a stationary point can
thus be expressed as follows

$0\in\partial L(\bm{f},\bm{g};\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta}).$

We work in terms of the subgradient because the objective function
$\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})$ is not differentiable at coordinates
where $f_{(\ell,d)}=0$ or $g_{(\ell,d)}=0$. However, we can use the following
property (see Theorem 3.1.8 in Lewis (2006)) about general convex functions to
obtain a stationarity condition in terms of the partial derivatives for the
nonzero coordinates of $\bm{f}$ and $\bm{g}$:

######  Lemma.

Let $h:\mathbb{R}^{m}\to\mathbb{R}^{n}$ be a convex function and consider any
point $x\in\mathbb{R}^{m}$ in its domain. Let $\partial h(x_{0})$ be the
subdifferential of $h$ at $x$ and assume the partial derivative
$\frac{\partial}{\partial x_{j}}h(x)$ exists for some coordinate $j$. Then the
$j$th component of every subgradient in the subdifferential of $h$ at $x$ is
equal to the partial derivative of $h$ at $x$. That is, for every
$\phi\in\partial h(x)$ the equality $\phi_{j}=\frac{\partial}{\partial
x_{j}}h(x)$ holds.

Therefore, for any pair of locations $(\ell,d)$ where the objective function
is differentiable with respect to $f_{(\ell,d)}$, the stationarity conditions
require the following equality hold:

$\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\eta_{\ell}-\alpha_{(\ell,d)}-\gamma_{(\ell,d)}.$
(79)

And, for any pair of locations $(\ell,d)$ where the objective function is
differentiable with respect to $g_{(\ell,d)}$, the stationarity conditions
require the following equality hold:

$\frac{\partial}{\partial
g_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\gamma_{(\ell,d)}-\beta_{(\ell,d)}.$
(80)

###  D.4 Statement of Lemma 3

For the rest of this document we will focus on properties of the state-
dependent optimization function (66). Recall the function
$\Phi_{\omega_{t}}(\mathbf{S})$ gives the optimal value of the state-dependent
optimization problem with respect to the time-scenario $\omega_{t}$ as a
function of a supply-location vector $\mathbf{S}$. In this section we will
show that the partial derivative $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S})$ exists for every location $\ell$ with
a nonzero volume of drivers under $\mathbf{S}$.

First, let us introduce notation to refer to optimal primal and dual solutions
of the state-dependent optimization problem. Let

$F^{*}(\mathbf{S})=\left\\{(\bm{f},\bm{g}):\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\Phi_{\omega_{t}}(\mathbf{S}),\
(\bm{f},\bm{g})\mbox{ is feasible for (\ref{eq:state_dep_opt}) with respect to
}\mathbf{S}\right\\}$

denote the set of primal optimal solutions as a function of the supply-
location vector $\mathbf{S}$. Let

$D^{*}(\mathbf{S})=\left\\{(\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta}):\exists(\bm{f}^{*},\bm{g}^{*})\in
F^{*}(\mathbf{S})\mbox{ such that }0\in\partial
L(\bm{f}^{*},\bm{g}^{*};\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta}),\
\bm{\alpha}\geq 0,\bm{\beta}\geq 0,\bm{\gamma}\geq 0\right\\}$

denote the set of dual optimal solutions as a function of the supply-location
vector $\mathbf{S}$.

Our main result in this section is the following Lemma, which characterizes
important properties about partial derivatives of the state-dependent
optimization function. Below is a restatement of Lemma 3.

######  Lemma.

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 (66) with respect to $\mathbf{S}$
the value of any optimal dual variable associated with the flow conservation
constraint (70) 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}$.

Below, in Section D.5 we prove Lemma 3.

###  D.5 Proof of Lemma 3

We prove Lemma 3 by backwards induction on the time $t$. For the rest of this
section we hold fixed a time-scenario $\omega_{t}$, a supply-location vector
$\mathbf{S}=(S_{\ell}:\ell\in\mathcal{L})$, and we fix a location
$\ell\in\mathcal{L}$ for which the volume of supply at $\ell$ under
$\mathbf{S}$ is nonzero, i.e. $S_{\ell}>0$.

Our backwards induction hypothesis states that the conclusion of Lemma 3 holds
for all supply-location vectors at all time $t+1$ scenarios. For clarity we
formally state our backwards induction hypothesis in Assumption 3.

######  Assumption 3.

When $t=T$ is the final time period then we make no assumption. When $t<T$,
let $\omega_{t+1}$ be any time $t+1$ scenario, let $\mathbf{S}^{\prime}$ be
any supply location vector, and let $\ell^{\prime}$ be any location for which
the volume of supply at $\ell^{\prime}$ under $\mathbf{S}^{\prime}$ is
nonzero. Then Lemma 3 parts 1, 2, and 3 are true, with respect to
$\omega_{t+1}$, $\mathbf{S}^{\prime}$ and $\ell^{\prime}$.

In the following subsections we prove parts 1, 2, and 3 of Lemma 3 assuming
the backwards induction hypothesis.

####  D.5.1 Proof of Part 1

Lemma 3 Part 1 claims that the optimal dual variable associated with the flow-
conservation constraint for location $\ell$ is unique. We prove this claim by
invoking Lemma 21 which states that the Lagrangian optimality conditions for
the state-dependent optimization problem hold between any pair of primal and
dual optima.

Specifically, let
$(\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta}),(\bm{\alpha^{\prime}},\bm{\beta^{\prime}},\bm{\gamma^{\prime}},\bm{\eta^{\prime}})\in
D^{*}(\mathbf{S})$ be any pair of dual optima and let $(\bm{f},\bm{g})\in
F^{*}(\mathbf{S})$ be any primal optimum. Lemma 21 states that the
stationarity conditions and complementary slackness conditions hold between
the primal optimum $(\bm{f},\bm{g})$ and both dual optima
$(\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta}),(\bm{\alpha^{\prime}},\bm{\beta^{\prime}},\bm{\gamma^{\prime}},\bm{\eta^{\prime}})$.

We first consider the stationarity optimality conditions. From the assumption
that location $\ell$ has nonzero supply-volume under $\mathbf{S}$, there must
be a destination $d\in\mathcal{L}$ for which a nonzero volume of drivers
traverse from $\ell$ to $d$ under any feasible solution. In particular,
consider a location $d$ for which the $f_{(\ell,d)}$ component of the optimal
solution $(\bm{f},\bm{g})$ is nonzero.

Observe that under the backwards induction hypothesis, the objective function
$\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})$ is differentiable with respect to
$f_{(\ell,d)}$ at the primal optimum $(\bm{f},\bm{g})$. Recall the objective
function $\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})$ is the sum of the current
reward $\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})$ and the future reward
$\mathbb{E}_{\omega_{t}}\left[\Phi_{\omega_{t+1}}(\mathbf{S}_{\omega_{t+1}}(\bm{f}))\right]$.
That the current reward $\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})$ is
differentiable with respect to any nonzero component of $\bm{f}$ follows from
Lemma 1. That the future reward is differentiable with respect to
$f_{(\ell,d)}$ follows from the backward induction hypothesis. Specifically,
for any time $t+1$ scenario $\omega_{t+1}$, there will be nonzero supply-
volume at location $d$ under the resulting time $t+1$ supply-location vector,
since there is a nonzero volume of drivers driving from $\ell$ to $d$.
Therefore the state-dependent optimization function
$\Phi_{\omega_{t+1}}(\mathbf{S}_{\omega_{t+1}}(\bm{f}))$ is differentiable
with respect to the volume of supply at location $d$. Therefore, it follows
from the chain rule that the partial derivative of the future reward exists
and can be written as follows:

$\frac{\partial}{\partial
f_{(\ell,d)}}\mathbb{E}_{\omega_{t}}\left[\Phi_{\omega_{t+1}}(\mathbf{S}_{\omega_{t+1}}(\bm{f}))\right]=\mathbb{E}_{\omega_{t}}\left[\frac{\partial}{\partial
S_{d}}\Phi_{\omega_{t+1}}(\mathbf{S}_{\omega_{t+1}}(\bm{f}))\right].$

Having established differentiability of the objective function with respect to
the $f_{(\ell,d)}$ variable, let’s return to the stationarity optimality
conditions. It follows from equation (79) that the stationarity conditions
imply the following equality:

$\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\eta_{\ell}-\alpha_{(\ell,d)}-\gamma_{(\ell,d)}.$

The above equation gives us a useful characterization of the dual variable
$\eta_{\ell}$, whenever the supply-volume $S_{\ell}$ is greater than $0$:

$\displaystyle\eta_{\ell}$
$\displaystyle=\frac{1}{S_{\ell}}\sum_{d\in\mathcal{L}}f_{(\ell,d)}\left[\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})+\alpha_{(\ell,d)}+\gamma_{(\ell,d)}\right]$
$\displaystyle=\frac{1}{S_{\ell}}\sum_{d\in\mathcal{L}}\left[f_{(\ell,d)}\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})+g_{(\ell,d)}\gamma_{(\ell,d)}\right]$
$\displaystyle=\frac{1}{S_{\ell}}\sum_{d\in\mathcal{L}}\left[f_{(\ell,d)}\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})+g_{(\ell,d)}\frac{\partial}{\partial
g_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})\right]$ (81)

For the remainder of this proof we consider two cases: in one case a nonzero
volume of drivers traversing $(\ell,d)$ have no passenger, i.e.
$g_{(\ell,d)}<f_{(\ell,d)}$; in the other case, we have all drivers traversing
$(\ell,d)$ are carrying a passenger, i.e. $g_{(\ell,d)}=f_{(\ell,d)}$. In the
first case, since the constraint $g_{(\ell,d)}\leq f_{(\ell,d)}$ is strict it
follows from the complementary slackness conditions that dual variable
associated with the constraint, $\gamma_{(\ell,d)}$, is $0$. Similarly, since
$f_{(\ell,d)}$ is nonzero, the dual variable associated with the nonnegativity
constraint on $f_{(\ell,d)}$, that is $\alpha_{(\ell,d)}$, is $0$. Therefore,
the stationarity condition simplifies to the following:

$\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\eta_{\ell}.$

Since Lemma 21 states the optimality conditions hold between any pair of
primal and dual optima, we can apply the same line of reasoning to our other
dual solution and conclude

$\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\eta^{\prime}_{\ell},$

from which $\eta_{\ell}=\eta^{\prime}_{\ell}$ follows.

In the second case where all drivers along $(\ell,d)$ have a passenger the
dual variable $\gamma_{(\ell,d)}$ need not be $0$, but equation (80) gives us
the following characterization:

$\frac{\partial}{\partial
g_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\gamma_{(\ell,d)}-\beta_{(\ell,d)}.$

Note that the objective function only depends on $\bm{g}$ for the current
reward $\mathcal{U}_{\omega_{t}}(\bm{f},\bm{g})$, and this is differentiable
with respect to any nonzero component $g_{(\ell,d)}$. Further,
$\beta_{(\ell,d)}$ is the dual variable associated with the nonnegativity
constraint on $g_{(\ell,d)}$, and from the assumption that
$g_{(\ell,d)}=f_{(\ell,d)}$ and $f_{(\ell,d)}>0$ the complementary slackness
conditions imply that $\beta_{(\ell,d)}$ is $0$. Therefore we obtain the
equality

$\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})+\frac{\partial}{\partial
g_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\eta_{\ell}$

and

$\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})+\frac{\partial}{\partial
g_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\eta^{\prime}_{\ell}$

from which $\eta^{\prime}_{\ell}=\eta_{\ell}$ follows.

####  D.5.2 Proof of Part 2

We give a high-level outline of the proof for part 2. We start by using Lemma
22, which considers the _value function_ associated with an optimization
problem, which gives the optimal value of an optimization problem as a
function of the constraint vector. Lemma 22 shows that the set of optimal dual
variables for the optimization problem at a particular constraint vector is
the same as the set of negative subgradients for the value function at that
constraint vector.

The negative state-dependent optimization function
$-\Phi_{\omega_{t}}(\mathbf{S})$ is similar to the value function considered
by Lemma 22, except the state-dependent optimization problem has a mix of
equality constraints and inequality constraints whereas the optimization
problem considered in Lemma 22 only explicitly includes inequality
constraints, and the supply-location vector $\mathbf{S}$ that
$-\Phi_{\omega_{t}}(\mathbf{S})$ takes as an argument only varies the bounds
for the equality constraints.

To use the result of Lemma 22 in the context of our state-dependent
optimization function we first rewrite the state-depent optimization problem
solely in terms of inequality constraints, where each equality constraint is
replaced by two inequality constraints pointing in opposite directions. When
the state-dependent optimization problem is written in this way it has the
same structure as the optimization problem considered in Lemma 22, so we can
associate a “value function” with the problem in the same manner as Lemma 22,
and then the state-dependent optimization problem
$-\Phi_{\omega_{t}}(\mathbf{S})$ is equivalent to this value function applied
to a linear transformation of the supply-location vector $\mathbf{S}$.

Finally we invoke Lemma 23 which gives a version of the chain-rule that
applies to subgradients. Invoking Lemma 23 tells us that a vector $\bm{\phi}$
is a subgradient of $(-\Phi_{\omega_{t}})(\mathbf{S})$ if and only iff
$\bm{\phi}=-\bm{\eta}$, where $\bm{\eta}$ is the restriction of any optimal
dual variable $(\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta})\in
D^{*}(\mathbf{S})$ to the components associated with the flow-conservation
equality constraints.

The conclusion of part 2 follows from the results of part 1, which states that
there is a unique optimal dual variable for the flow-conservation constraint
associated with location $\ell$. It follows that there is a unique value for
the $\ell$th component of any subgradient for the negative state-dependent
optimization function evaluated at $\mathbf{S}$. We know that a function is
differentiable at a point when the subderivative of that function at that
point is unique . Therefore, the partial derivative of the negative state-
dependent value function with respect to the $\ell$th component of the input
vector exists and is equal to the negative dual variable associated with the
$\ell$th flow-conservation constraint. Taking negatives on both sides of the
equality, we conclude $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S})$ exists and is equal to
$\eta_{\ell}^{*}$, as claimed.

####  D.5.3 Proof of Part 3

The final result left to establish for Lemma 3 is that the state-dependent
optimization function has continuous partial derivatives at any location where
the supply-location vector is nonzero. We prove this result by showing that,
for any sequence of supply-location vectors converging to $\mathbf{S}$, the
corresponding sequence of partial derivatives with respect to location $\ell$
converges to the partial derivative evaluated at $\mathbf{S}$.

Formally, let $(\mathbf{S}_{k}:k=1,2,\dots)$ be a sequence of supply-location
vectors converging to $\mathbf{S}$, and assume without loss of generality that
the $\ell$th component of each iterate $\mathbf{S}_{k}$ is nonzero. Having
already established parts 1 and 2 of Lemma 3, we know the following:

  * •

For the state-dependent optimization problem with respect to each supply-
location vector $\mathbf{S}_{k}$ there is a unique optimal dual variable
associated with the flow-conservation constraint for location $\ell$.

  * •

The state-dependent optimization function evaluated at $\mathbf{S}_{k}$ is
partially differentiable in the direction $\ell$, and the value of the partial
derivative is equal to the optimal dual variable for the location $\ell$ flow-
conservation constraint.

Let $\eta_{\ell}^{*}(\mathbf{S}_{k})$ denote the optimal dual variable for the
location $\ell$ flow-conservation constraint with respect to $\mathbf{S}_{k}$
and let $\eta_{\ell}^{*}(\mathbf{S})$ denote the same optimal dual variable
with respect to $\mathbf{S}$. We will show that the partial derivative of the
state-dependent optimization function is continuous at $\mathbf{S}$ by showing
that the sequence of optimal dual variables
$(\eta_{\ell}^{*}(\mathbf{S}_{k}):k=1,2,\dots)$ converges to
$\eta_{\ell}^{*}(\mathbf{S})$, i.e.

$\lim_{k\to\infty}\eta_{\ell}^{*}(\mathbf{S}_{k})=\eta_{\ell}^{*}(\mathbf{S}).$
(82)

Our approach for establishing the equality in equation (82) is to use the
Lagrangian optimality conditions to obtain an equivalent expression in terms
of primal solutions. To obtain this equivalent expression that works in the
space of primal solutions, we construct a function that takes as input a
primal optimal solution and produces the value of the optimal dual variable
for location $\ell$ as the output. Define
$\mathcal{S}=\left\\{\mathbf{S}_{k}:k=1,2,\dots\right\\}\cup\left\\{\mathbf{S}\right\\}$
to be the set of all supply-location vectors in our sequence and the limiting
supply-location vector to which they converge, and define

$\mathcal{F}=\bigcup_{\mathbf{S}^{\prime}\in\mathcal{S}}F^{*}(\mathbf{S}^{\prime})$

to be the set of all primal solutions that are optimal for some supply-
location vector in $\mathcal{S}$.

We write $E_{\ell}:\mathcal{F}\to\mathbb{R}$ to denote our function that
recovers the optimal dual variable associated with location $\ell$ from a
primal optimal solution. For a primal optimal solution
$(\bm{f}^{*},\bm{g}^{*})\in\mathcal{F}$, the exact definition of
$E_{\ell}(\bm{f}^{*},\bm{g}^{*})$ will reflect the optimality conditions
associated with a particular route $(\ell,d)$. The choice of the destination
location $d$ will depend on which components of $\bm{f}^{*}$ are nonzero.
Specifically, order the locations in $\mathcal{L}$ as
$d_{1},d_{2},\dots,d_{n}$ where $n=|\mathcal{L}|$, and let $i(\bm{f}^{*})=i$
be the smallest index in $\\{1,2,\dots,n\\}$ such that $f^{*}_{(\ell,d_{i})}$
is nonzero. Note that by construction every supply-location vector in
$\mathcal{S}$ has nonzero volume on location $\ell$, so every primal optimal
solution $(\bm{f}^{*},\bm{g}^{*})\in\mathcal{F}$ always has at least one
destination $d$ for which $f^{*}_{(\ell,d)}$ is nonzero; in particular, the
index $i(\bm{f}^{*})$ is always well-defined.

Now, consider any sequence of optimal solutions
$(\bm{f}^{*}_{k},\bm{g}^{*}_{k})\in F^{*}(\mathbf{S}_{k})$ for $k\geq 1$, and
observe the sequence $(\bm{f}^{*}_{k},\bm{g}^{*}_{k})$ is bounded, in
particular there is a convergent subsequence
$((\bm{f}^{*}_{k}(i),\bm{g}^{*}_{k}(i)):i\geq 1)$. Let $\bm{f}^{*},\bm{g}^{*}$
be the limit point of this subsequence, and observe that
$(\bm{f}^{*},\bm{g}^{*})\in F^{*}(\mathbf{S})$. Define the function
$E_{\ell}(\bm{f},\bm{g})$ as

$E_{\ell}(\bm{f},\bm{g})=\frac{1}{S_{\ell}}\sum_{d\in\mathcal{L}}\left[f_{(\ell,d)}\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})+g_{(\ell,d)}\frac{\partial}{\partial
g_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})\right]$

From the equation (81), we know that $\eta_{\ell}^{*}(\mathbf{S}^{\prime})$ is
equal to $E_{\ell}(\bm{f}^{*},\bm{g}^{*})$, if $(\bm{f}^{*},\bm{g}^{*})\in
F^{*}(\mathbf{S}^{\prime})$ for any $\mathbf{S}^{\prime}\in\mathcal{F}$.

Observe that for $i$ large enough, the convergent subsequence
$((\bm{f}^{*}_{k(i)},\bm{g}^{*}_{k(i)}):i\geq 1)$ will be nonzero on the same
components as $(\bm{f}^{*},\bm{g}^{*})$. Therefore

$\lim_{i\to\infty}\eta_{\ell}^{*}(\mathbf{S}_{k(i)})=\lim_{i\to\infty}E_{\ell}(\bm{f}^{*}_{k(i)},\bm{g}^{*}_{k(i)})=E_{\ell}(\bm{f}^{*},\bm{g}^{*})=\eta_{\ell}^{*}(\mathbf{S}).$

Also observe that the sequence of dual variables
$(\eta_{\ell}^{*}(\mathbf{S}_{k}):k\geq 1)$ is the same sequence as
$(E_{\ell}(\bm{f}^{*}_{k},\bm{g}^{*}_{k}):k\geq 1)$. From the above equation
it follows that every limit point is equal to $\eta_{\ell}^{*}(\mathbf{S})$.
Since the sequence $(\eta_{\ell}^{*}(\mathbf{S}_{k}):k\geq 1)$ is bounded and
since there is a single limit point, it follows the sequence converges:
$\lim_{k\to\infty}\eta_{\ell}^{*}(\mathbf{S}_{k})=\eta_{\ell}^{*}(\mathbf{S})$,
finishing the proof.

####  D.5.4 Additional Lemma for Proof of Lemma 3

######  Lemma 21.

For any convex optimization problem the stationarity and complementary
slackness conditions hold between any pair of primal and dual optima. In
particular, for the state-dependent optimization problem (66) with respect to
any scenario $\omega_{t}$ and supply location vector $\mathbf{S}$, if
$(\bm{f},\bm{g})\in F^{*}(\mathbf{S})$ is any primal optimum and
$(\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta})\in D^{*}(\mathbf{S})$ is any
dual optimum then the stationarity conditions hold, i.e.

$0\in\partial L(\bm{f},\bm{g};\bm{\alpha},\bm{\beta},\bm{\gamma},\bm{\eta}),$

and the complementary slackness conditions hold, i.e.

$\alpha_{(\ell,d)}f_{(\ell,d)}=0,\ \beta_{(\ell,d)}g_{(\ell,d)}=0,\
\gamma_{(\ell,d)}(g_{(\ell,d)}-f_{(\ell,d)})=0.$

For the following lemma, consider the optimization problem

$\inf_{x\in\mathbb{R}^{m}}\left\\{f(x)\mid g(x)\leq 0\right\\},$ (83)

where $f:\mathbb{R}^{m}\to\mathbb{R}$ is our objective function and
$g:\mathbb{R}^{m}\to\mathbb{R}^{n}$ is our constraint function. We assume that
$f$ and $g_{1},\dots,g_{n}$ are convex functions, where $g_{j}(x)$ is the
$j$th component function of the multivariate constraint function $g$. The
Lagrangian function $L:\mathbb{R}^{m}\times\mathbb{R}^{n}_{+}\to\mathbb{R}$ is
defined by

$L(x,\lambda)=f(x)+\lambda^{T}g(x).$

The dual function $\Gamma:\mathbb{R}^{n}_{+}\to\mathbb{R}$ is defined by

$\Gamma(\lambda)=\inf_{x\in\mathbb{R}^{m}}L(x;\lambda).$

The _value function_ associated with the mathematical program (83) describes
how the optimal value changes as we perturb the constraint vector away from
$0$. Formally, it is a function $v:\mathbb{R}^{n}\to\mathbb{R}$ defined by the
equation

$v(b)=\inf_{x\in\mathbb{R}^{m}}\left\\{f(x)\mid g(x)\leq b\right\\}.$ (84)

The problem (83) is said to have zero duality gap when strong duality holds,
i.e. when the primal optimum is equal to the dual optimum, as described by the
following equation:

$\inf_{x\in\mathbb{R}^{m}}\left\\{f(x)\mid g(x)\leq
0\right\\}=\sup_{\lambda\in\mathbb{R}^{m}_{+}}\Gamma(\lambda).$

Any $\lambda^{*}\in\mathbb{R}_{m}^{*}$ which achieves the optimum on the right
side of the above equation is said to be an optimal dual solution. The
following lemma appears as Corollary 4.3.6 in Lewis (2006).

######  Lemma 22.

The mathematical program (83) has zero duality gap if and only if the value
function $v$ is lower semicontinuous at $0$. In this case the set of dual
optimal solutions is $-\partial v(0)$.

In order to apply the result of Lemma 22 we also make use of the following
result from Lewis (2006), which provides a chain rule for subdifferentials of
convex functions composed with linear functions.

######  Lemma 23.

Let $f:\mathbb{R}^{m}\to\mathbb{R}$ be a convex function and let
$A\in\mathbb{R}^{m\times n}$ be a matrix. Then the following equality is
satisfied for $x\in\mathbb{R}^{n}$:

$\partial(f\circ A)(x)=A^{T}\partial f(Ax).$

###  D.6 Proof of Lemma 4

We re-state Lemma 4 below.

######  Lemma.

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}\\}$.

Also, in the case where $S_{\ell}=0$, there exists an optimal dual solution
such that the dual variable $\eta_{\ell}$ associated with the $\ell$th flow-
conservation constraint is equal to the right derivative
$\frac{\partial}{\partial S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}^{+})$.

We prove Lemma 4 by characterizing optimal primal solutions to the state-
dependent optimization problem, in the regime where there is an infinitesimal
volume of drivers at $\ell$.

We start by defining the continuation utilities associated with a primal
solution. Let $\omega_{t}$ be any scenario, and let $\bm{f}=(f_{(\ell,d)}\geq
0:(\ell,d)\in\mathcal{L}^{2})$ be any flow vector. For a destination
$d\in\mathcal{L}$ define the continuation utility associated with $d$ and
$\bm{f}$ to be

$U_{d}(\bm{f})=\mathbb{E}\left[\frac{\partial}{\partial
S_{d}}\Phi_{\omega_{t+1}}(\bar{\mathbf{S}}_{\omega_{t+1}}(\bm{f}))\mid\omega_{t}\right].$
(85)

The following lemma states that the continuation utilities associated with
optimal solutions to the state-dependent optimization problem all take the
same value.

######  Lemma 24.

Let $\omega_{t}$ be any scenario and let $\mathbf{S}$ be any feasible supply-
location vector. Let $(\bm{f}_{i},\bm{g}_{i})\in
F^{*}_{\omega_{t}}(\mathbf{S})$, for $i=1,2$, be any optimal solutions to the
state-dependent optimization problem with respect to
$(\omega_{t},\mathbf{S}_{t})$. Then the continuation utilities under
$\bm{f}_{1}$ and $\bm{f}_{2}$ are the same, i.e.
$U_{d}(\bm{f}_{1})=U_{d}(\bm{f}_{2})$ for any choice of destination $d$.

Lemma 24 follows from the optimality conditions, and the fact that
complementary slackness holds between any pair of primal and dual optima.

Our next Lemma characterizes optimal solutions for the state-dependent
optimization problem in the regime where there is an infinitesimal volume of
drivers at $\ell$.

######  Lemma 25.

Let $\omega_{t}$ be any scenario and let $\mathbf{S}$ be any feasible supply-
location vector. Assume $S_{\ell}=0$ for some location $\ell$. Let
$(\mathbf{S}_{n})_{n=1}^{\infty}$ be a sequence of feasible supply-location
vectors converging to $\mathbf{S}$, such that each element of the sequence has
a nonzero volume of drivers at $\ell$, i.e. $S^{n}_{\ell}>0$ for all $n$. Let
$(\bm{f}^{*}_{n},\bm{g}^{*}_{n})\in F^{*}_{\omega_{t}}(\mathbf{S}_{n})$ be an
optimal primal solution for each $n$, and define

$\bm{f}_{\ell}^{n}=\frac{1}{S^{n}_{\ell}}\left(f^{*}_{n,(\ell,d)}:d\in\mathcal{L}\right)\
\ \
\bm{g}_{\ell}^{n}=\frac{1}{S^{n}_{\ell}}\left(g^{*}_{n,(\ell,d)}:d\in\mathcal{L}\right)$

to be the restriction of $(\bm{f}^{*}_{n},\bm{g}^{*}_{n})$ to components that
correspond to trips originating from $\ell$, divided by the volume of drivers
at $\ell$ under the $n$th iterate in the sequence. Then every limit point of
the sequence $(\bm{f}_{\ell,n},\bm{g}_{\ell,n})_{n=1}^{\infty}$ is an optimal
solution to the following optimization problem:

$\displaystyle\sup\ \ \ $
$\displaystyle\sum_{d\in\mathcal{L}}V_{d}g_{d}+\sum_{d\in\mathcal{L}}(U_{d}-c_{(\ell,d)})f_{d}-A\left(\sum_{d\in\mathcal{L}}g_{d},\sum_{d\in\mathcal{L}}f_{d}\right)$
(86) such that $\displaystyle 0\leq g_{d}\leq f_{d}\ \ \forall
d\in\mathcal{L},$ (87) $\displaystyle\sum_{d\in\mathcal{L}}f_{d}=1.$ (88)

In the above, $V_{d}$ is to the maximum rider value held by riders requesting
a trip from $\ell$ to $d$ under $\omega_{t}$, $U_{d}$ is the continuation
utility associated with each destination $d\in\mathcal{L}$ under an optimal
solution for the limiting supply-location vector $\mathbf{S}$, and
$A(\cdot,\cdot)$ is the add-passenger disutility cost function
$A(g,f)=\frac{C}{2}\frac{g^{2}}{f}$.

Moreover, the optimization problem (86) has a unique optimal dual variable
$\eta_{\ell}$ associated with the constraint (88), and the value of this dual
variable is equal to the right-derivative limit $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}^{+})$.

###### Proof.

We give a high-level outline for the proof of Lemma 25. First, a backwards
induction argument lets us assume that the objective function of the original
state-dependent optimization problem $\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})$
has continuous right derivatives on the boundary of the feasible region (the
backwards induction assumption applies to the future-period reward function
$\Phi_{\omega_{t+1}}(\mathbf{S}_{\omega_{t+1}}(\bm{f}))$ which appears as a
summand in the objective $\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})$).

Next, by considering convergent subsequences, we can assume without loss of
generality that the sequence of optimal solutions
$(\bm{f}^{*}_{n},\bm{g}^{*}_{n})$, $n=1,2,\dots$, converges to some limit
$(\bm{f}^{*},\bm{g}^{*})$, and by continuity of the objective function it
follows that the limit point is optimal with respect to the limiting supply-
location vector $(\bm{f}^{*},\bm{g}^{*})\in F^{*}_{\omega_{t}}(\mathbf{S})$.

Also by considering convergent subsequences, we can assume without loss of
generality that the scaled sequence of points

$\bm{f}_{\ell}^{n}=\frac{1}{S^{n}_{\ell}}\left(f^{*}_{n,(\ell,d)}:d\in\mathcal{L}\right)\
\ \
\bm{g}_{\ell}^{n}=\frac{1}{S^{n}_{\ell}}\left(g^{*}_{n,(\ell,d)}:d\in\mathcal{L}\right)$

converges to some limit $(\bar{\bm{f}}_{\ell},\bar{\bm{g}}_{\ell})$, and by
virtue of the scaling it follows that this limit is a feasible solution for
the linearized optimization problem (86).

Next, we consider the optimality conditions associated with each iterate in
our sequence of supply-location vectors. Let $\eta_{\ell}^{n}$ be the dual
variable associated with the $\ell$th flow-conservation constraint, for the
$n$th supply-location vector in our sequence. Since every iterate in our
sequence has nonzero volume of drivers at $\ell$, the dual variable
$\eta_{\ell}^{n}$ is unique. Further, the characterization (81) of this dual
variable yields the following expression:

$\eta_{\ell}^{n}=\frac{1}{S_{\ell}^{n}}\sum_{d\in\mathcal{L}}\left[f^{n}_{(\ell,d)}\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f}^{*}_{n},\bm{g}^{*}_{n})+g^{n}_{(\ell,d)}\frac{\partial}{\partial
g_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f}^{*}_{n},\bm{g}^{*}_{n})\right].$

Notice that the partial derivatives of the objective function have the
following expressions:

$\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=-c_{(\ell,d)}+\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}_{\omega_{t}}^{>t}(\bm{f})-\frac{\partial}{\partial
f_{(\ell,d)}}A(\bm{g}^{T}\mathbf{1}_{\ell},\bm{f}^{T}\mathbf{1}_{\ell}),$

and

$\frac{\partial}{\partial
g_{(\ell,d)}}\mathcal{W}_{\omega_{t}}(\bm{f},\bm{g})=\frac{d}{dg}U_{(\ell,d,\omega_{t})}(g_{(\ell,d)})-\frac{\partial}{\partial
g_{(\ell,d)}}A(\bm{g}^{T}\mathbf{1}_{\ell},\bm{f}^{T}\mathbf{1}_{\ell}).$

Also, notice that the partial derivatives of the add-passenger disutility
function have the following expressions:

$\frac{\partial}{\partial
f_{(\ell,d)}}A(\bm{g}^{T}\mathbf{1}_{\ell},\bm{f}^{T}\mathbf{1}_{\ell})=-\frac{C}{2}\left(\frac{\bm{g}^{T}\mathbf{1}_{\ell}}{\bm{f}^{T}\mathbf{1}_{\ell}}\right)^{2}\
\ \mbox{and}\ \ \frac{\partial}{\partial
g_{(\ell,d)}}A(\bm{g}^{T}\mathbf{1}_{\ell},\bm{f}^{T}\mathbf{1}_{\ell})=C\frac{\bm{g}^{T}\mathbf{1}_{\ell}}{\bm{f}^{T}\mathbf{1}_{\ell}}.$

Therefore, the partial derivatives of $A(\cdot,\cdot)$ are invariant to both
of its arguments being scaled by the same multiple. In particular, we have the
equality

$\frac{\partial}{\partial
f_{(\ell,d)}}A(\bm{g}_{n}^{*T}\mathbf{1}_{\ell},\bm{f}_{n}^{*T}\mathbf{1}_{\ell})=\frac{\partial}{\partial
f_{(\ell,d)}}A(\frac{\bm{g}_{n}^{*T}\mathbf{1}_{\ell}}{S_{\ell}^{n}},\frac{\bm{f}_{n}^{*T}\mathbf{1}_{\ell}}{S_{\ell}^{n}})\
\ \mbox{and}\ \ \frac{\partial}{\partial
g_{(\ell,d)}}A(\bm{g}_{n}^{*T}\mathbf{1}_{\ell},\bm{f}_{n}^{*T}\mathbf{1}_{\ell})=\frac{\partial}{\partial
g_{(\ell,d)}}A(\frac{\bm{g}_{n}^{*T}\mathbf{1}_{\ell}}{S_{\ell}^{n}},\frac{\bm{f}_{n}^{*T}\mathbf{1}_{\ell}}{S_{\ell}^{n}}).$

We can rewrite our expression for the optimal dual variable $\eta_{\ell}^{n}$
as follows:

$\displaystyle\eta_{\ell}^{n}=$
$\displaystyle\sum_{d\in\mathcal{L}}\frac{f^{n}_{(\ell,d)}}{S_{\ell}^{n}}\left(\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}_{\omega_{t}}^{>t}(\bm{f}^{*}_{n})-c_{(\ell,d)}-\frac{\partial}{\partial
f_{(\ell,d)}}A(\frac{\bm{g}_{n}^{*T}\mathbf{1}_{\ell}}{S_{\ell}^{n}},\frac{\bm{f}_{n}^{*T}\mathbf{1}_{\ell}}{S_{\ell}^{n}})\right)$
$\displaystyle+\sum_{d\in\mathcal{L}}\frac{f^{n}_{(\ell,d)}}{S_{\ell}^{n}}\left(\frac{d}{dg}U_{(\ell,d,\omega_{t})}(g^{n}_{(\ell,d)})-\frac{\partial}{\partial
g_{(\ell,d)}}A(\frac{\bm{g}_{n}^{*T}\mathbf{1}_{\ell}}{S_{\ell}^{n}},\frac{\bm{f}_{n}^{*T}\mathbf{1}_{\ell}}{S_{\ell}^{n}})\right)$

We know that $(\bm{f}^{*}_{n},\bm{g}^{*}_{n})$ converges as $n\to\infty$, as
does $\frac{f^{n}_{(\ell,d)}}{S_{\ell}^{n}}$ and
$\frac{g^{n}_{(\ell,d)}}{S_{\ell}^{n}}$. Therefore the sequence of optimal
dual variables converges to the following limit.

$\displaystyle\lim_{n\to\infty}\eta_{\ell}^{n}=$
$\displaystyle\sum_{d\in\mathcal{L}}\bar{f}_{(\ell,d)}\left(\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}_{\omega_{t}}^{>t}(\bm{f}^{*})-c_{(\ell,d)}-\frac{\partial}{\partial
f_{(\ell,d)}}A(\bar{\bm{g}}^{T}\mathbf{1}_{\ell},\bar{\bm{f}}^{T}\mathbf{1}_{\ell})\right)$
$\displaystyle+\sum_{d\in\mathcal{L}}\bar{g}_{(\ell,d)}\left(\frac{d}{dg}U_{(\ell,d,\omega_{t})}(g^{*}_{(\ell,d)})-\frac{\partial}{\partial
g_{(\ell,d)}}A(\bar{\bm{g}}^{T}\mathbf{1}_{\ell},\bar{\bm{f}}^{T}\mathbf{1}_{\ell})\right).$

However, since $\bm{g}^{*}$ is feasible for the limiting supply-location
vector $\mathbf{S}$, we know

$\frac{d}{dg}U_{(\ell,d,\omega_{t})}(g^{*}_{(\ell,d)})=\frac{d}{dg}U_{(\ell,d,\omega_{t})}(0)=V_{d},$

where $V_{d}$ is the maximum rider value for riders requesting from $\ell$ to
$d$ under $\omega_{t}$. Also, since $(\bm{f}^{*},\bm{g}^{*})$ is an optimal
solution with respect to $\mathbf{S}$, we have the partial derivative
$\frac{\partial}{\partial
f_{(\ell,d)}}\mathcal{U}_{\omega_{t}}^{>t}(\bm{f}^{*})$ is equal to the
optimal continuation utility $U_{d}$ associated with $d$. Therefore, the limit
of the sequence of dual variables,
$\eta_{\ell}=\lim_{n\to\infty}\eta_{\ell}^{n}$, is equal to

$\displaystyle\eta_{\ell}=$
$\displaystyle\sum_{d\in\mathcal{L}}\bar{f}_{(\ell,d)}\left(U_{d}-c_{(\ell,d)}-\frac{\partial}{\partial
f_{(\ell,d)}}A(\bar{\bm{g}}^{T}\mathbf{1}_{\ell},\bar{\bm{f}}^{T}\mathbf{1}_{\ell})\right)$
$\displaystyle+\sum_{d\in\mathcal{L}}\bar{g}_{(\ell,d)}\left(V_{d}-\frac{\partial}{\partial
g_{(\ell,d)}}A(\bar{\bm{g}}^{T}\mathbf{1}_{\ell},\bar{\bm{f}}^{T}\mathbf{1}_{\ell})\right).$

Optimality of $(\bar{\bm{f}},\bar{\bm{g}})$ and $\eta_{\ell}$ follow by using
the above characterization of $\eta_{\ell}$ to show that
$(\bar{\bm{f}},\bar{\bm{g}})$ satisfies optimality conditions for the
optimization problem (86). Finally, uniqueness of the dual variable
$\eta_{\ell}$ follows from the same argument we used in Part one (appendix
D.5.1) of the proof for Lemma 3. ∎

Lemma 25 shows that the right-hand derivative limit $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}^{+})$ is well-defined when $S_{\ell}=0$,
and that every sequence of partial derivatives $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{n})$ with $S_{\ell}^{n}>0$ converges to
the same limit. To finish showing that the partial derivative function To
finish proving Lemma 4 it suffices to show that sequences of right-hand
derivatives $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{n}^{+})$ converge, for supply-location
vectors $\mathbf{S}_{n}^{+}$ on the boundary of the feasible space, i.e. with
$S_{\ell}^{n}=0$.

Lemma 26 follows from analyzing the optimization problem (86) using the same
logic as part three of our proof of Lemma 3.

######  Lemma 26.

Let $(\mathbf{S}_{n})_{n=1}^{\infty}$ be a sequence of supply location vectors
which converge to $\mathbf{S}$, all of which have $0$ driver volume at $\ell$,
i.e. $S_{\ell}^{n}=0$ for all $n$. Then $\frac{\partial}{\partial
S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S}_{n}^{+})$ converges to
$\frac{\partial}{\partial S_{\ell}}\Phi_{\omega_{t}}(\mathbf{S})$ as
$n\to\infty$.

##  Appendix E Matching Process Details

We view the matching process as a generic procedure for allocating trips to
available drivers. In general, we assume there is a stochastic matching
process for the two-level model as well as a deterministic matching process
for the fluid model. Our analysis holds for any matching process that
satisfies three properties, stated informally below:

######  Assumption 4.

  1. 1.

The random trip-volumes produced by the stochastic two-level model matching
process converge to their corresponding deterministic fluid trip-volumes as
the population size parameter grows to infinity.

  2. 2.

In the deterministic fluid matching process, the only way for the trip volume
produced by the matching process along a route to be smaller than the optimal
trip volume along that route is if the drivers are using an acceptance
threshold smaller than the optimal acceptance threshold.

  3. 3.

In the stochastic two-level model matching process, conditioning on the action
taken by a single driver has negligible effect on the overall distribution of
aggregate trip counts in the limit as the population size grows to infinity.
Specifically, we assume there exists a sequence $(\beta_{k})_{k=1}^{\infty}$
converging to $0$ as $k\to\infty$ such that the conditional distribution
$\mathbb{P}(\mathbf{S}_{t+1}\mid a_{i}^{t})$ is at most $\beta_{k}$ different
from the unconditional distribution $\mathbb{P}(\mathbf{S}_{t+1})$, i.e.
$|\mathbb{P}(\mathbf{S}_{t+1}\mid
a_{i}^{t})-\mathbb{P}(\mathbf{S}_{t+1})|\leq\beta_{k}$. We assume the sequence
$(\beta_{k})_{k=1}^{\infty}$ works for all initial states
$(\omega_{t},\mathbf{S}_{t})$ and all driver strategy profiles.

For completeness, we define one example of a matching process that the
platform can use, and show that it satisfies properties 1 and 2 listed above.
We conjecture that this process also satisfies 3, but have not yet verified
this.

###  E.1 Example Matching Process Definition

The SSP matching process definition differs slightly between the fluid model
and the two-level model, because granular rider and driver decisions which
affect the dynamics of the matching process are stochastic in the two level
model but deterministic in the fluid model.

In both cases the SSP matching process makes use of a subroutine which takes a
collection of drivers and a collection of riders all heading towards the same
destination, and allocates dispatches towards that destination until either no
drivers or riders remain.

######  Definition 4.

The single destination dispatch subroutine in the fluid model is a procedure
that takes as input a rider volume $\bar{R}$, driver volume $\bar{M}$, and a
single disutility threshold $x$. The output is a number
$\bar{G}(\bar{R},\bar{M},x)$ specifying the volume of dispatches that were
accepted, and a number $\bar{U}(\bar{R},\bar{M},x)$ specifying the volume of
drivers who were not allocated a dispatch in the process. The function
definitions are stated below.

$\displaystyle\bar{G}(\bar{R},\bar{M},x)$
$\displaystyle=\min\left(Z(\bar{R},x),\bar{M}\right)\frac{x}{C},$ (89)
$\displaystyle\bar{U}(\bar{R},\bar{M},x)$
$\displaystyle=\bar{M}-\min\left(Z(\bar{R},x),\bar{M}\right).$ (90)

(Recall $Z(\bar{R},x)$ is the volume of drivers (5) who need to be allocated a
dispatch in order to see $\bar{R}$ accepted dispatches given a disutility
threshold $x$).

In the two level model it is a procedure that takes as input a number of
riders $R$, a number of drivers $M$, and a choice of disutility thresholds
$x_{1},\dots,x_{M}$ for each driver. The procedure allocates dispatches to
riders until all rides have been served or no drivers remain. The output is a
number of drivers $G$ who accepted a dispatch, and a set $U\subseteq[M]$ of
driver labels who were not allocated a dispatch in the process. The stochastic
dynamics governing $G$ and $U$ are stated in Algorithm 1.

  1. 1.

Input: A number of dispatch requests $R$, a number of drivers $M$, a choice of
disutility threshold $x_{i}$ for each $i=1,2,\dots,M$.

  2. 2.

Randomly permute the driver labels: select a permutation $\pi:[M]\to[M]$
uniformly at random and define new labels $j=\pi(i)$.

  3. 3.

Initialize $G\leftarrow 0$, $U\leftarrow\\{1,2,\dots,M\\}$.

  4. 4.

For $j=1,2,\dots,M$:

     * •

Allocate a dispatch to driver $j$.

     * •

Sample the accept/reject decision $\delta_{j}\sim\mathrm{Ber}(x_{j}/C)$.

     * •

Record the decision: $R\leftarrow R-\delta_{j}$, $G\leftarrow G+\delta_{j}$.

     * •

Remove $j$ from $U$: $U\leftarrow U\setminus\\{j\\}$.

     * •

If $R=0$: go to step 5.

  5. 5.

Return $G$, $U$.

Algorithm 1 The Single Destination Dispatch Subroutine in the Two Level Model

The SSP matching process, in both the fluid model and the two level model,
uses the single destination dispatch subroutine in two separate stages. In the
first stage, drivers are subdivided into groups, where there is one group for
each destination, and group sizes are determined by the dispatch volumes and
the disutility threshold from the optimal solution. The single destination
subroutine is then used to allocate dispatches for each destination to drivers
in the group associated with that destination. This is the first stage of the
matching process. If any drivers remain undispatched after the first stage,
the second stage goes through the dispatch destinations one by one and it uses
the single destination dispatch subroutine to allocate all remaining demand
for that destination to all remaining drivers.

Notice that the disutility threshold associated with the optimal solution
$(\bm{f}^{*},\bm{g}^{*})$ is the same for every destination $d$:

$x^{*}_{\ell}=C\frac{\bm{g}^{*T}\mathbf{1}_{\ell}}{\bm{f}^{*T}\mathbf{1}_{\ell}}.$
(91)

Let

$Z_{(\ell,d)}=Z(g^{*}_{(\ell,d)},x^{*}_{\ell})=g^{*}_{(\ell,d)}\frac{x^{*}_{\ell}}{C}$
(92)

be the volume of drivers we need to allocate a dispatch toward $d$ in order to
see $g^{*}_{(\ell,d)}$ accepted dispatches under the threshold $x^{*}_{\ell}$.
Observe

$\sum_{d\in\mathcal{L}}Z_{(\ell,d)}=\sum_{d\in\mathcal{L}}Z(g^{*}_{(\ell,d)},x^{*}_{\ell})=\sum_{d\in\mathcal{L}}g^{*}_{(\ell,d)}\frac{C}{x^{*}_{\ell}}=\bm{f}^{*T}\mathbf{1}_{\ell}=S_{\ell},$

so the fractions $Z_{(\ell,d)}/S_{\ell}$ sum to $1$ over all $d$. These
fractions are used to determine the partition sizes in the first stage of the
matching process.

  1. 1.

Input: A location $\ell$, a number of dispatch requests $R_{(\ell,d)}$ for
each destination $d$, a number of drivers $M_{\ell}$, an add-passenger
threshold vector $\bm{x}_{i}=(x^{i}_{(\ell,d)}:d\in\mathcal{L})$ for each
driver $i=1,2,\dots,M_{\ell}$, the fluid optimal actions
$(\bm{f}^{*},\bm{g}^{*},\bm{x}^{*})$.

  2. 2.

Stage one:

    1. (a)

Compute partition sizes $Z^{*}_{(\ell,d)}$ for each destination $d$, using
equation (92) with the fluid optimal trip volume $g^{*}_{(\ell,d)}$ and
threshold $x^{*}_{\ell}$.

    2. (b)

Partition the $M_{\ell}$ drivers into groups of size $M_{(\ell,d)}$, where
each $M_{(\ell,d)}$ is rounded up or down from $Z^{*}_{(\ell,d)}$.

    3. (c)

Use the single-destination dispatch subroutine to allocate the $R_{(\ell,d)}$
dispatch requests to the $M_{(\ell,d)}$ drivers, for each destination $d$.

    4. (d)

Record the output from the single-destination dispatch subroutine: Let
$G^{(1)}_{(\ell,d)}$ be the number of dispatch trips accepted and
$U^{(1)}_{(\ell,d)}$ the number of drivers who were not allocated a trip.

  3. 3.

Stage two:

    1. (a)

Let $R^{(2)}_{(\ell,d)}=R_{(\ell,d)}-G^{(1)}_{(\ell,d)}$ be the number of
riders who have not been matched to a driver at the end of the first stage.

    2. (b)

Let $M^{(2)}_{\ell}=\sum_{d}U^{(1)}_{(\ell,d)}$ be the number of drivers who
were not allocated a dispatch at the end of the first stage.

    3. (c)

Pick an ordering of the destinations $d_{1},d_{2},\dots,d_{|\mathcal{L}|}$.
For each destination $d=d_{1},d_{2},\dots,d_{|\mathcal{L}|}$:

       * •

Use the single-destination dispatch subroutine to allocate the
$R^{(2)}_{(\ell,d)}$ dispatch requests to the $M^{(2)}_{\ell}$ remaining
drivers.

       * •

Record the output from the single-destination dispatch subroutine: let
$G^{(2)}_{(\ell,d)}$ be the number of dispatch trips accepted, and
$U^{(2)}_{(\ell,d)}$ be the number of drivers who remain undispatched.

       * •

Update the number of remaining drivers: set
$M^{(2)}_{\ell}=U^{(2)}_{(\ell,d)}$.

Algorithm 2 The Matching Process in the Two Level Model

######  Definition 5.

The matching process in the fluid model takes as input a market state
$(\omega_{t},\mathbf{S}_{t})$, a volume of requests $\bar{R}_{d}$ for each
destination $d$, a location $\ell$, a volume of drivers $\bar{M}_{\ell}$, and
a disutility threshold vector $\bm{x}_{\ell}=(x_{(\ell,d)}:d\in\mathcal{L})$.
It proceeds in two stages:

  1. 1.

In the first stage, it partitions the $M_{\ell}$ drivers into groups of size
$\bar{M}_{(\ell,d)}=\frac{Z_{(\ell,d)}}{S_{\ell}}\bar{M}_{\ell}$ for each $d$.
It uses the single destination dispatch subroutine for each $d$ to allocate
the $\bar{R}_{d}$ dispatches to the $\bar{M}_{(\ell,d)}$ drivers. The first
stage produces
$\bar{G}_{d}^{(1)}=\bar{G}(\bar{R}_{d},\bar{M}_{(\ell,d)},x_{(\ell,d)})$
accepted dispatches towards each destination $d$, and
$\bar{U}_{d}=\bar{U}(\bar{R}_{d},\bar{M}_{(\ell,d)},x_{(\ell,d)})$ drivers
remain unallocated from each group $d$.

  2. 2.

In the second stage the initial volume of drivers who were not allocated in
the first stage is equal to $\bar{U}^{(0)}=\sum_{d\in\mathcal{L}}\bar{U}_{d}$.
The matching process orders the locations $d_{1},\dots,d_{L}$ and it goes
through the destinations and uses the single destination dispatch subroutine
to allocate all remaining dispatches to the pool of unallocated drivers, until
either all demand has been served or all drivers have been allocated.
Specifically, for each destination $i=1,2,\dots,L$, it runs the single
destination dispatch subroutine on $\bar{R}_{d}-\bar{G}_{d}^{(1)}$,
$\bar{U}^{(i-1)}$, $x_{(\ell,d_{i})}$, and it records
$\bar{G}^{(2)}=\bar{G}(\bar{R}_{d}-\bar{G}_{d}^{(1)},\bar{U}^{(i-1)},x_{(\ell,d_{i})})$
accepted dispatches and
$\bar{U}^{(i)}=\bar{U}(\bar{R}_{d}-\bar{G}_{d}^{(1)},\bar{U}^{(i-1)},x_{(\ell,d_{i})})$
remaining unallocated drivers.

The matching process in the two level model takes as input a market state
$(\omega_{t},\mathbf{S}_{t})$, a number of requests $R_{d}$ for each
destination $d$, a location $\ell$, a number of drivers $M_{\ell}$, and a
disutility threshold vector $\bm{x}_{i}=(x_{d}^{i}:d\in\mathcal{L})$ for each
driver $i=1,2,\dots,M_{\ell}$. It proceeds in two stages:

  1. 1.

In the first stage, it partitions the $M_{\ell}$ drivers into groups of size
$M_{(\ell,d)}$, which are either rounded up or down from
$\frac{Z_{(\ell,d)}}{S_{\ell}}M_{\ell}$, for each $d$. The allocation of
drivers to groups happens uniformly at random. It uses the single destination
dispatch subroutine for each $d$ to allocate the $R_{d}$ dispatches to the
$M_{(\ell,d)}$ drivers. The first stage produces $G_{d}^{(1)}$ accepted
dispatches towards each destination $d$, and $U_{d}$ is the set of driver
indices which remain unallocated from each group $d$.

  2. 2.

In the second stage the initial volume of drivers who were not allocated in
the first stage is equal to $U^{(0)}=\cup_{d\in\mathcal{L}}U_{d}$. The
matching process orders the locations $d_{1},\dots,d_{L}$ and it goes through
the destinations and uses the single destination dispatch subroutine to
allocates all remaining dispatches to the pool of unallocated drivers, until
either all demand has been served or all drivers have been allocated.
Specifically, for each destination $i=1,2,\dots,L$, it runs the single
destination dispatch subroutine on $R_{d}-G_{d}^{(1)}$, $U^{(i-1)}$, and the
thresholds $x_{d}^{i}$ for $i\in U^{(i-1)}$. The output is $G^{(2)}$ accepted
dispatches and $U^{(i)}$ is the index set of unallocated drivers.

######  Lemma 27.

Let $(\omega_{t},\mathbf{S}_{t})$ be any market state, let
$(\bm{f}^{*},\bm{g}^{*})\in F^{*}_{\omega_{t}}(\mathbf{S}_{t})$ be a solution
to the fluid optimization problem. Consider the fluid matching process which
allocates all dispatch demand $(g^{*}_{(\ell,d)}:d\in\mathcal{L})$ originating
from $\ell$ to all $S_{\ell}$ drivers positioned at $\ell$. Let
$\bm{x}=(x_{(\ell,d)}:d\in\mathcal{L})$ be any disutility threshold vector
used by drivers at $\ell$ and let
$\bm{g}_{\ell}=(g_{(\ell,d)}:d\in\mathcal{L})$ be the output of the matching
process. Then $g_{(\ell,d)}<g^{*}_{(\ell,d)}$ implies
$x_{(\ell,d)}<x^{*}_{\ell}$.

###  E.2 Matching Process Concentration Properties

In this section of the appendix we establish that the matching process
satisfies good concentration properties as the population size goes to
infinity. For ease of use in the analysis of our main algorithm, we establish
concentration inequalities that hold uniformly across all relevant market
states. Informally, the relevant market states are those in which
approximately every agent uses approximately the same add-passenger
disutilities. In addition, we require that the total number of drivers is no
larger than a multiple of the population-size parameter.

To describe the relevant market states to which our concentration inequalities
apply, fix a time period $t$ and scenario $\omega_{t}$. Let $\mathcal{M}$ be
an index set of all active drivers in the marketplace, and let
$\mathcal{M}_{\ell}$ be the subset of drivers who are positioned at each
location $\ell$. For a driver $i\in\mathcal{M}_{\ell}$, we use
$\bm{x}_{i}=(x^{i}_{(\ell,d)}:d\in\mathcal{L})$ to denote the add-passenger
disutility threshold vector selected by driver $i$, and we use
$r_{i}\in\mathcal{L}$ to denote the relocation destination selected by driver
$i$, which is the destination towards which driver $i$ will drive empty if
they do not accept a dispatch trip. We use the term _driver-state_ to mean the
specification of add-passenger disutility threshold vector $\bm{x}_{i}$ and
relocation destination $r_{i}$ for each driver $i\in\mathcal{M}_{\ell}$ for
each location $\ell$. At a location $\ell$, we will use
$\bm{r}_{\ell}=(r_{(\ell,d)}:d\in\mathcal{L})$ to mean the distribution of
relocation destinations used by drivers positioned at $\ell$. Each component
$r_{(\ell,d)}$ is the probability a randomly selected driver from $\ell$ would
have selected $d$ as their relocation destination:

$r_{(\ell,d)}=\frac{\sum_{i\in\mathcal{M}_{\ell}}\mathbf{1}\left\\{r_{i}=d\right\\}}{|\mathcal{M}_{\ell}|}.$

To simplify notation we will use $\mathcal{M}$ to refer to the set of driver
indices, as well as their choice of disutility threshold and relocation
destinations.

For each location $\ell$ let $\bm{x}_{\ell}=(x_{(\ell,d)}:d\in\mathcal{L})$
denote a common add-passenger threshold vector, potentially used by drivers at
$\ell$. For an error term $\epsilon>0$, define

$\mathcal{M}_{\ell}(\epsilon,\bm{x}_{\ell})=\\{i\in\mathcal{M}_{\ell}:\|\bm{x}_{i}-\bm{x}_{\ell}\|_{\infty}<\epsilon\\}$

to be the subset of drivers positioned at $\ell$ whose threshold vector is no
more than $\epsilon$ away from $\bm{x}_{\ell}$ in any component. Let
$\bm{x}=(\bm{x}_{\ell}:\ell\in\mathcal{L})$ denote a common threshold vector
for each location. For $\epsilon>0$, define

$\mathcal{M}(\epsilon,\bm{x})=\bigcup_{\ell\in\mathcal{L}}\mathcal{M}_{\ell}(\epsilon,\bm{x}_{\ell}).$

######  Definition 6.

Let $\gamma$ be any constant, and let $(\epsilon_{k}:k\geq 1)$ and
$(\delta_{k}:k\geq 1)$ be nonnegative sequences which converge to $0$ as
$k\to\infty$. For any population-size $k\geq 1$ and any driver state
$\mathcal{M}$, we say $\mathcal{M}$ is permissible with respect to
$\gamma,\epsilon_{k},\delta_{k}$ if the following conditions are satisfied:

  1. 1.

The total number of drivers is no larger than $\gamma k$, i.e
$|\mathcal{M}|\leq\gamma k$.

  2. 2.

There exists a common disutility threshold vector
$\bm{x}=(\bm{x}_{\ell}:\ell\in\mathcal{L})$ such that the number of drivers
who use a disutility threshold vector that is further than $\epsilon_{k}$ from
$\bm{x}$ is vanishingly small, relative to $k$:

$\frac{|\mathcal{M}\setminus\mathcal{M}(\epsilon_{k},\bm{x})|}{k}\leq\delta_{k}.$

The concentration inequalities we provide in this section show that, when the
matching process is applied to a driver state that is permissible with respect
to $\gamma,\epsilon_{k},\delta_{k}$, then with high probability, the
difference between the stochastic output of the matching process and the
corresponding fluid output is small.

We now describe what we mean by the fluid outcome associated with a particular
driver state. Given population-size parameter $k\geq 1$, a driver state
$\mathcal{M}$ determines the supply-location vector $\mathbf{S}_{t}$ by, in
each component $\ell$, taking the ratio between the total number of drivers at
$\ell$ and $k$:

$S_{\ell}=\frac{|\mathcal{M}_{\ell}|}{k}.$

The market state $(\omega_{t},\mathbf{S}_{t})$ then determines the prices,
$P_{(\ell,d)}$ for $(\ell,d)\in\mathcal{L}^{2}$, set by the SSP mechanism. The
prices then determine the expected number of riders who request a dispatch:

$\bar{R}_{(\ell,d)}=\mathbb{E}[D^{k}_{(\ell,d)}](1-F_{(\ell,d)}(P_{(\ell,d)})),$

where $D^{k}_{(\ell,d)}$ is the (stochastic) number of riders who are
potentially interested in a dispatch from $\ell$ to $d$.

######  Definition 7.

Fix a population-size parameter $k$ and let $\mathcal{M}$ be a driver-state
that is permissible with respect to parameters
$(\gamma,\epsilon_{k},\delta_{k})$. Let $\bm{x}$ be the common disutility
threshold vector used by approximately all drivers in $\mathcal{M}$ (which
exists from the second condition in the definition of permissible driver
state, Definition 6). Let $\bm{r}=(\bm{r}_{\ell}:\ell\in\mathcal{L})$ denote
the relocation distributions used by the population of drivers across each
location.

The fluid outcome associated with $\mathcal{M}$, $k$, are, for each route
$(\ell,d)$, the dispatch trip volumes $\bar{G}_{(\ell,d)}$ and total trip
volumes $\bar{F}_{(\ell,d)}$, which result from using the fluid matching
process to allocate the dispatch demand volumes $\bar{R}_{(\ell,d)}$, along
each route $(\ell,d)$, assuming $|\mathcal{M}_{\ell}|$ drivers are positioned
at each location $\ell$, and the drivers at $\ell$ use disutility threshold
vector $\bm{x}_{\ell}$ and relocation-trip distribution $\bm{r}_{\ell}$.

We also define $\bar{f}_{(\ell,d)}=\frac{\bar{F}_{(\ell,d)}}{k}$ and
$\bar{g}_{(\ell,d)}=\frac{\bar{G}_{(\ell,d)}}{k}$ to be the fluid outcome,
normalized by the population size $k$.

To summarize, a permissible driver state $\mathcal{M}$ and a population-size
parameter $k$ induce both a deterministic fluid trip specification, denoted by
dispatch trip volumes $\bar{G}_{(\ell,d)}$ and total trip volumes
$\bar{F}_{(\ell,d)}$, for each route $(\ell,d)$, and stochastic trip
specifications, denoted by dispatch trip volumes $G_{(\ell,d)}$ and total trip
volumes $F_{(\ell,d)}$, for each $(\ell,d)$. The stochastic procedure
governing $G_{(\ell,d)}$ and $F_{(\ell,d)}$ is described in Algorithm 2, and
the deterministic procedure governing $\bar{G}_{(\ell,d)}$ and
$\bar{F}_{(\ell,d)}$ is described in Definition 5. We will use $\mathbf{F}$,
$\bm{G}$, $\bar{\mathbf{F}}$, $\bar{\bm{G}}$, to mean the corresponding
vectors of trip counts (the vectors are indexed by routes
$(\ell,d)\in\mathcal{L}^{2}$).

Also, define $H_{(\ell,d)}=F_{(\ell,d)}-G_{(\ell,d)}$ to mean the (stochastic)
total number of relocation trips along $(\ell,d)$, and define
$\bar{H}_{(\ell,d)}=\bar{F}_{(\ell,d)}-\bar{G}_{(\ell,d)}$ to mean the
deterministic fluid number of relocation trips along $(\ell,d)$. Let $\bm{H}$
be the vector with components $H_{(\ell,d)}$ for each
$(\ell,d)\in\mathcal{L}^{2}$ and let $\bar{\bm{H}}$ be the vector with
components $\bar{H}_{(\ell,d)}$ for each $(\ell,d)\in\mathcal{L}^{2}$.

For each $k\geq 1$, let $\mathcal{D}_{k}$ be the set of driver states
$\mathcal{M}$ that are permissible with respect to
$(\gamma,\epsilon_{k},\delta_{k})$ when the population-size parameter is $k$.
The main concentration lemma that we prove in this section is stated below:

######  Lemma 28.

There exist nonnegative sequences $(\alpha_{k}:k\geq 1)$ and $(q_{k}:k\geq
1)$, both converging to $0$ as $k\to\infty$, such that the following equation
is true for every $k$:

$\sup_{\mathcal{M}\in\mathcal{D}_{k}}\mathbb{P}\left(\frac{1}{k}\left(\|\bm{H}-\bar{\bm{H}}\|_{1}+\|\bm{G}-\bar{\bm{G}}\|_{1}\right)\leq\alpha_{k}\right)\geq
1-q_{k}.$ (93)

In the above equation, it is understood that the trip specifications $\bm{H}$,
$\bm{G}$, $\bar{\bm{H}}$, $\bar{\bm{G}}$ are those which arise from the driver
state $\mathcal{M}$ and the population-size parameter $k$.

###### Proof.

We give a brief summary of the proof of Lemma 28, the details of which are
contained in the Lemmas below.

Observe that the outcome of the matching process, i.e. the vector $\bm{G}$, is
the sum of two vectors $\bm{G}=\bm{G}_{1}+\bm{G}_{2}$ where $\bm{G}_{1}$
encodes the output from the first stage of the matching process and
$\bm{G}_{2}$ encodes the output from the second stage. We analyze the
convergence of $\bm{G}_{1}$ and $\bm{G}_{2}$ separately.

Lemma 31 provides an asymptotic concentration result for the output of the
single-destination dispatch procedure with deterministic inputs, which we use
to deduce that $\bm{G}_{1}$ converges asymptotically to $\bar{\bm{G}}_{1}$.
Next, Lemma 32 provides asymptotic concentration for the single-destination
dispatch procedure with inputs that have small stochastic perturbations. These
small stochastic perturbations correspond to the second stage of the matching
process, and are used to show that $\bm{G}_{2}$ converges to
$\bar{\bm{G}}_{2}$.

Finally, Lemma 33 shows that the remaining undispatched drivers, i.e. the
trips encoded by $\bm{H}$, converge to the deterministic fluid approximation
$\bar{\bm{H}}$. ∎

Before proving Lemma 28, we provide a number of Lemmas that help us analyze
the different components of the matching process. The following Lemma follows
from standard concenteration inequalities for sub-Gaussian random variables.

######  Lemma 29.

Let $\mathcal{I}$ be an arbitrary index set and let $\gamma>0$ be a constant.
For each $k\geq 1$ and $i\in\mathcal{I}$, let $X_{k,i}$ be a Binomial random
variable and let $R_{k,i}$ be a constant no larger than $\gamma k$. Let
$Z_{k,i}=\min(R_{k,i},X_{k,i})$ and let
$\bar{Z}_{k,i}=\min(R_{k,i},\mathbb{E}[X_{k,i}])$. Then there exists
concentration functions $\epsilon(k)$, $q(k)$ such that

$\sup_{i\in\mathcal{I}}\mathbb{P}\left(|Z_{k,i}-\bar{Z}_{k,i}|\geq\epsilon(k)\right)\leq
q(k).$ (94)

######  Lemma 30.

Moreover, for each $k$ and $i$ let $Y_{k,i}$ have a negative binomial
distribution, let $M_{k,i}$ be a constant no larger than $\gamma k$. Define
$Z_{k,i}=\min(Y_{k,i},M_{k,i})$ and
$\bar{Z}_{k,i}=\min(\mathbb{E}[Y_{k,i}],M_{k,i})$. Then there exist
concentration functions $\epsilon(k)$, $q(k)$ such that

$\sup_{i\in\mathcal{I}}\mathbb{P}\left(|Z_{k,i}-\bar{Z}_{k,i}|\geq\epsilon(k)\right)\leq
q(k).$ (95)

Next, we analyze asymptotic convergence of the single destination dispatch
subroutine.

For a population-size parameter value $k$, consider the single destination
dispatch subroutine with $R$ riders and $M$ drivers, both of which are smaller
than $\gamma k$. Assume that, except for a subset of size at most
$k\delta_{k}$ drivers, each driver has probability of accepting a dispatch no
more than $\epsilon_{k}$ away from some constant $p$.

Let $G$ and $U$ be random variables counting the number of accepted
dispatches, and the number of undispatched drivers, respectively. Let
$\bar{G}$ and $\bar{U}$ be the volume of accepted dispatches and undispatched
drivers from the fluid matching process, with $R$ riders, $M$ drivers, and
acceptance probability $p$.

######  Lemma 31.

There exists sequences of nonnegative numbers, $(\alpha_{k}:k\geq 1)$ and
$(q_{k}:k\geq 1)$, both of which converge to $0$ as $k\to\infty$, such that
the following statement is true for every $k$:

$\displaystyle\sup_{M\leq\gamma k,\ R\leq\gamma k,\
p\in[0,1]}\mathbb{P}\left(\frac{1}{k}|G-\bar{G}|\leq\alpha_{k}\right)\geq
1-q_{k}$ (96) $\displaystyle\sup_{M\leq\gamma k,\ R\leq\gamma k,\
p\in[0,1]}\mathbb{P}\left(\frac{1}{k}|U-\bar{U}|\leq\alpha_{k}\right)\geq
1-q_{k}.$ (97)

In the above equations, it is understood that $G$ and $\bar{G}$ are the
stochastic and fluid number of accepted dispatches from the single-destination
dispatch subroutine with $M$ drivers, $R$ riders, and, except for a subset of
size at most $k\delta_{k}$ drivers, drivers use an acceptance probability
within $\epsilon_{k}$ of $p$. Similarly, it is understood that $U$ and
$\bar{U}$ are the stochastic and fluid number of remaining undispatched
drivers.

We defer the proof of Lemma 31 to Appendix E.3.

Our next Lemma proves asymptotic convergence when the single-destination
dispatch subroutine is called twice, where the number of riders and drivers
remaining unmatched in the first call are used as input for the second call to
the procedure. We consider a situation where the input parameters for the
single-destination dispatch subroutine are stochastically perturbed by a
random variable which satisfies asymptotic concentration properties. We show
the conclusion of Lemma 31 still hold despite this stochastic perturbation.

Specifically, for each $k\geq 1$, let $\mathcal{I}_{k}$ be a set of tuples of
random variables $(X,Y)\in\mathcal{I}_{k}$, with deterministic fluid
approximations $(\bar{X},\bar{Y})$, such that the following concentration
property is satisfied:

$\displaystyle\sup_{(X,Y)\in\mathcal{I}_{k}}\mathbb{P}\left(\frac{1}{k}\left(|X-\bar{X}|+|Y-\bar{Y}|\right)\leq\alpha_{k}\right)\geq
1-q_{k},$ (98)

where $(\alpha_{k}:k\geq 1)$ and $(q_{k}:k\geq 1)$ are nonnegative sequences
which converge to $0$ as $k\to\infty$.

Our next Lemma analyzes convergence of the single-destination dispatch
subroutine when the initial number of drivers and riders are perturbed by
subtracting $X$ and $Y$. Let $G$ and $U$ be the stochastic output from when
the single-destination dispatch subroutine when $M-X$ is the initial number of
drivers and $R-Y$ is the initial number of drivers. Let $\bar{G}$ and
$\bar{U}$ be the fluid number of drivers when the initial driver volume is
$M-\bar{X}$ and the initial rider volume is $R-\bar{Y}$. We show that $G$ and
$U$ converge asymptotically to $\bar{G}$ and $\bar{U}$, assuming that $X$ and
$Y$ satisfy the concentration property (98).

######  Lemma 32.

For each $k\geq 1$, let $\mathcal{I}_{k}$ be a set of tuples of nonnegative
random variables $(X,Y)\in\mathcal{I}_{k}$, with deterministic fluid
approximations $(\bar{X},\bar{Y})$, which satisfy the asymptotic concentration
property (98). Let $(M,R,p)$ be any constants satisfying $M\leq\gamma k$,
$R\leq\gamma k$, and $p\in[0,1]$. Let $G$ be the number of dispatches and $U$
the number of remaining drivers, when the single-destination dispatch
subroutine (1) is used to allocate $R-Y$ dispatch requests to $M-X$ drivers,
assuming that, except for a subset of size at most $k\delta_{k}$ drivers,
drivers use an acceptance probability within $\epsilon_{k}$ of $p$. Let
$\bar{G}$ and $\bar{U}$ be the output of the fluid subroutine when $R-\bar{Y}$
riders are allocated to $M-\bar{X}$ drivers. Then $G$ converges asymptotically
to $\bar{G}$ and $U$ converges asymptotically to $\bar{U}$, in the sense that
the following equation holds for all $k\geq 1$:

$\displaystyle\sup_{M\leq\gamma k,\ R\leq\gamma k,\ p\in[0,1],\
(X,Y)\in\mathcal{I}_{k}}\mathbb{P}\left(\frac{1}{k}|G-\bar{G}|\leq\beta_{k}\right)\geq
1-p_{k}$ (100) $\displaystyle\sup_{M\leq\gamma k,\ R\leq\gamma k,\ p\in[0,1],\
(X,Y)\in\mathcal{I}_{k}}\mathbb{P}\left(\frac{1}{k}|U-\bar{U}|\leq\beta_{k}\right)\geq
1-p_{k},$ (101)

where $(\beta_{k}:k\geq 1)$ and $(p_{k}:k\geq 1)$ are nonnegative sequences
which converge to $0$ as $k\to\infty$.

Our final intermediate Lemma analyzes the asymptotic convergence of the
relocation trips taken by the drivers. Recall that, in the fluid matching
process, the volume of relocation trips towards each location is proportional
to the volume of drivers who selected that destination as their relocation
destination. Specifically, the fluid volume of relocation trips from $\ell$ to
$d$ is determined by the following equation:

$\bar{H}_{(\ell,d)}=\left(M_{\ell}-\sum_{d^{\prime}}\bar{G}_{(\ell,d^{\prime})}\right)\left(\frac{\sum_{i\in\mathcal{M}_{\ell}}\mathbf{1}\left\\{r_{i}=d\right\\}}{|\mathcal{M}_{\ell}|}\right).$

The factor on the left, i.e.
$M_{\ell}-\sum_{d^{\prime}}\bar{G}_{(\ell,d^{\prime})}$, counts the volume of
supply that does not serve a dispatch in the fluid model (recall
$M_{\ell}=|\mathcal{M}_{\ell}|$ is the unnormalized volume of drivers at
$\ell$), and the factor on the right,
$\frac{\sum_{i\in\mathcal{M}_{\ell}}\mathbf{1}\left\\{r_{i}=d\right\\}}{|\mathcal{M}_{\ell}|}$,
counts the proportion of drivers positioned at $\ell$ who choose $d$ as their
relocation destination.

The stochastic number of relocation trips along each route $(\ell,d)$ is
defined as the total number of undispatched drivers positioned at $\ell$ who
chose $d$ as their relocation destination. For a driver state $\mathcal{M}$,
let $\mathcal{M}^{R}_{\ell}\subseteq\mathcal{M}_{\ell}$ be the (stochastic)
subset of drivers who take a relocation trip. The number of relocation trips
$H_{(\ell,d)}$ is defined by

$H_{(\ell,d)}=\sum_{i\in\mathcal{M}^{R}_{\ell}}\mathbf{1}\left\\{r_{i}=d\right\\}.$

Let us also use the notation $\bar{H}_{\ell}$ to mean the total volume of
fluid relocation trips, and $H_{\ell}$ to mean the stochastic total number of
relocation trips in the two level model:

$\bar{H}_{\ell}=\sum_{d}\bar{H}_{(\ell,d)}\ \ \mbox{and}\ \
H_{\ell}=\sum_{d}H_{(\ell,d)}.$

The following Lemma shows that the distribution of relocation trips converges
asymptotically to the fluid distribution of relocation trips.

######  Lemma 33.

Suppose that the total number of relocation trips converges to the fluid
volume of relocation trips, as $k\to\infty$, for all admissible driver states.
That is, assume there exists sequences $(\alpha_{k}:k\geq 1)$ and
$(q_{k}:k\geq 1)$ such that
$\lim_{k\to\infty}\alpha_{k}=\lim_{k\to\infty}q_{k}=0$, for which the
following inequality holds for every $k$ and every $\ell$

$\sup_{\mathcal{M}\in\mathcal{D}_{k}}\mathbb{P}\left(\frac{1}{k}|H_{\ell}-\bar{H}_{\ell}|\leq\alpha_{k}\right)\geq
1-q_{k}.$

Then the relocation trip volumes along each individual route converge to their
fluid approximations, i.e. there exist sequences $(\beta_{k}:k\geq 1)$ and
$(p_{k}:k\geq 1)$ such that
$\lim_{k\to\infty}\beta_{k}=\lim_{k\to\infty}p_{k}=0$, for which the following
inequality holds for every $k$:

$\sup_{\mathcal{M}\in\mathcal{D}_{k}}\mathbb{P}\left(\frac{1}{k}\|\bm{H}-\bar{\bm{H}}\|_{1}\leq\beta_{k}\right)\geq
1-p_{k}.$

Note that in the above equation, $\bm{H}$ and $\bar{\bm{H}}$ are vectors with
components corresponding to $H_{(\ell,d)}$ and $\bar{H}_{(\ell,d)}$ for each
route $(\ell,d)$. Therefore, the difference inside the probability is equal to
the following:

$\|\bm{H}-\bar{\bm{H}}\|_{1}=\sum_{(\ell,d)\in\mathcal{L}^{2}}|H_{(\ell,d)}-\bar{H}_{(\ell,d)}|.$

We defer the proof of Lemma 33 to Appendix E.5

###  E.3 Proof of Lemma 31

We restate Lemma 31 below.

######  Lemma.

There exists sequences of nonnegative numbers, $(\alpha_{k}:k\geq 1)$ and
$(q_{k}:k\geq 1)$, both of which converge to $0$ as $k\to\infty$, such that
the following statement is true for every $k$:

$\displaystyle\sup_{M\leq\gamma k,\ R\leq\gamma k,\
p\in[0,1]}\mathbb{P}\left(\frac{1}{k}|G-\bar{G}|\leq\alpha_{k}\right)\geq
1-q_{k}$ (102) $\displaystyle\sup_{M\leq\gamma k,\ R\leq\gamma k,\
p\in[0,1]}\mathbb{P}\left(\frac{1}{k}|U-\bar{U}|\leq\alpha_{k}\right)\geq
1-q_{k}.$ (103)

In the above equations, it is understood that $G$ and $\bar{G}$ are the
stochastic and fluid number of accepted dispatches from the single-destination
dispatch subroutine with $M$ drivers, $R$ riders, and, except for a subset of
size at most $k\delta_{k}$ drivers, drivers use an acceptance probability
within $\epsilon_{k}$ of $p$. Similarly, it is understood that $U$ and
$\bar{U}$ are the stochastic and fluid number of remaining undispatched
drivers.

###### Proof.

We start with a proof of equation (102), which states that $G$ converges to
$\bar{G}$ as $k\to\infty$.

Fix $k\geq 1$ and any $M\leq\gamma k,\ R\leq\gamma k,\ p\in[0,1]$. Write the
number of drivers $M$ as $M=M^{\prime}+M^{\prime\prime}$, such that
$M^{\prime}$ is the number of drivers whose acceptance probability is within
$\epsilon_{k}$ of $p$, and $M^{\prime\prime}$ is the number of drivers whose
acceptance probability is further from $p$ than $\epsilon_{k}$. By assumption
we have $M^{\prime\prime}\leq\delta_{k}k$.

Consider the following modification of the single-destination dispatch
subroutine parameters, which is designed to slightly underestimate the total
number of dispatches produced the matching process. Assume that the dispatches
are only allocated to the $M^{\prime}$ drivers whose acceptance probability is
within $\epsilon_{k}$ of $p$, and assume that all $M^{\prime}$ drivers exactly
use acceptance threshold $p-\epsilon_{k}$. Let the number of riders stay $R$.
Let $G_{L}$ be the number of accepted dispatches from this version of the
single-destination dispatch subroutine. Also, define

$\bar{G}_{L}=\min(M^{\prime}(p-\epsilon_{k}),R)$

to be the fluid output from this version of the single-destination dispatch
subroutine.

Also consider the following modification, which is desgined to slightly
overestimate the total number of dispatches. Assume that all the
$M^{\prime\prime}$ drivers agree to serve a dispatch before the single-
destination dispatch subroutine is called, so that the remaining number of
riders is $R^{\prime}=R-\min(R,M^{\prime\prime})$ and the remaining number of
drivers is $M^{\prime}$. Also assume that all $M^{\prime}$ drivers exactly use
threshold value $p+\epsilon_{k}$. Let $G_{U}$ be the number of accepted
dispatches from this process, i.e. $G_{U}$ is equal to
$\min(R,M^{\prime\prime})$ plus the stochastic number of dispatches that occur
when $R^{\prime}$ riders are matched to $M^{\prime}$ drivers using the single-
destination dispatch subroutine, assuming all $M^{\prime}$ drivers have
acceptance probability exactly equal to $p+\epsilon_{k}$. Define

$\bar{G}_{U}=\min(R,M^{\prime\prime})+\min(R^{\prime},M^{\prime}(p+\epsilon_{k}))$

to be the fluid output from this version of the dispatch subroutine.

Notice that when all drivers use the same acceptance probability, the
resulting number of dispatch trips is equal in distribution to the minimum of
the number of drivers and a Binomial distribution parameterized by the number
of drivers and the common acceptance probability. Therefore, by Lemma 29, we
have the following bounds:

$\displaystyle\sup_{M\leq\gamma k,\ R\leq\gamma k,\
p\in[0,1]}\mathbb{P}\left(\frac{1}{k}|G_{U}-\bar{G}_{U}|\leq\alpha^{\prime}_{k}\right)\geq
1-q^{\prime}_{k}$ $\displaystyle\sup_{M\leq\gamma k,\ R\leq\gamma k,\
p\in[0,1]}\mathbb{P}\left(\frac{1}{k}|G_{L}-\bar{G}_{L}|\leq\alpha^{\prime}_{k}\right)\geq
1-q^{\prime}_{k},$

where $(\alpha^{\prime}_{k}:k\geq 1)$ and $(q^{\prime}_{k}:k\geq 1)$ are
sequences that converge to $0$ as $k\to\infty$. Also, Notice that for any
parameter values $M\leq\gamma k,\ R\leq\gamma k,\ p\in[0,1]$, we have the
upper bound

$\bar{G}_{U}-\bar{G}_{L}\leq M^{\prime\prime}+M^{\prime}2\epsilon_{k}\leq
k(\delta_{k}+2\gamma\epsilon_{k}).$ (104)

By construction, we have that $G$ stochastically dominates $G_{L}$, and
$G_{U}$ stochastically dominates $G$. That is, for any $g\geq 0$, we have the
following:

$\mathbb{P}(G\leq g)\leq\mathbb{P}(G_{L}\leq g),$

and

$\mathbb{P}(G_{U}\leq g)\leq\mathbb{P}(G\leq g).$

Therefore we obtain the following bounds, for any $\epsilon>0$:

$\displaystyle\mathbb{P}\left(|G-\bar{G}|\geq\epsilon\right)$
$\displaystyle\leq\mathbb{P}\left(G-\bar{G}\geq\epsilon\right)+\mathbb{P}\left(\bar{G}-G\geq\epsilon\right)$
$\displaystyle\leq\mathbb{P}\left(G_{U}-\bar{G}\geq\epsilon\right)+\mathbb{P}\left(\bar{G}-G_{L}\geq\epsilon\right)$
$\displaystyle\leq\mathbb{P}\left(|G_{U}-\bar{G}_{U}|\geq\epsilon+\bar{G}-\bar{G}_{U}\right)$
$\displaystyle\ \ \ \
+\mathbb{P}\left(|\bar{G}_{L}-G_{L}|\geq\epsilon+\bar{G}_{L}-\bar{G}\right).$
(105)

Finally, define

$\alpha_{k}=\alpha^{\prime}_{k}+(\delta_{k}+2\gamma\epsilon_{k}).$

By equation (105) we have the bound

$\displaystyle\mathbb{P}\left(\frac{1}{k}|G-\bar{G}|\geq\alpha_{k}\right)$
$\displaystyle\leq\mathbb{P}\left(|G_{U}-\bar{G}_{U}|\geq
k\alpha_{k}+\bar{G}-\bar{G}_{U}\right)$ $\displaystyle\ \ \ \
+\mathbb{P}\left(|\bar{G}_{L}-G_{L}|\geq
k\alpha_{k}+\bar{G}_{L}-\bar{G}\right).$ (106)

Now, from equation (104), we have

$k\alpha_{k}+\bar{G}-\bar{G}_{U}\geq k\alpha_{k}^{\prime},$

and similarly

$k\alpha_{k}+\bar{G}_{L}-\bar{G}\geq k\alpha_{k}^{\prime}.$

Therefore, continuing from (106), we have

$\displaystyle\mathbb{P}\left(\frac{1}{k}|G-\bar{G}|\geq\alpha_{k}\right)$
$\displaystyle\leq\mathbb{P}\left(|G_{U}-\bar{G}_{U}|\geq
k\alpha^{\prime}_{k}\right)+\mathbb{P}\left(|\bar{G}_{L}-G_{L}|\geq
k\alpha^{\prime}_{k}\right)$ $\displaystyle\leq
q^{\prime}_{k}+q^{\prime}_{k}.$ (107)

Taking $q_{k}=2q^{\prime}_{k}$ finishes the proof.

The proof of $U$ converging to $\bar{U}$ is analogous to the above argument.
We first define $U_{L}$ and $U_{U}$ to mean the random number of undispatched
drivers assuming all drivers use the acceptance probability $p-\epsilon_{k}$
and $p+\epsilon_{k}$, respectively, and we observe show that $U_{U}$
stochastically dominates $U$ which in turn stochastically dominates $U_{L}$.
Stochastic dominance lets us bound the convergence of $U$ in terms of the
convergence of $U_{U}$ and $U_{L}$. We then observe that each $U_{L}$ and
$U_{U}$ is equal in distribution to the minimum of a constant and a negative
binomial distribution, so Lemma 30 gives us large-population convergence.

∎

###  E.4 Proof of Lemma 32

To prove Lemma 32 we first state and prove the following Lemma.

######  Lemma 34.

For each $k\geq 1$, let $\mathcal{Z}_{k}$ be a set of random variables
$Z\in\mathcal{Z}_{k}$ with deterministic fluid approximations $\bar{Z}$.
Assume that $Z$ converges asymptotically to $\bar{Z}$, in the sense that there
exists sequences $(\alpha_{k}:k\geq 1)$ and $(q_{k}:k\geq 1)$, both converging
to $0$ as $k\to\infty$, such that the following holds for every $k\geq 1$:

$\sup_{Z\in\mathcal{Z}_{k}}\mathbb{P}\left(\frac{1}{k}|Z-\bar{Z}|\leq\alpha_{k}\right)\geq
1-q_{k}.$

Let $f$ be a Lipschitz continuous function with Lipschitz constant $L$. Then
$f(Z)$ converges asymptotically to $f(\bar{Z})$, in the sense that the
following equation holds:

$\sup_{Z\in\mathcal{Z}_{k}}\mathbb{P}\left(\frac{1}{k}|f(Z)-f(\bar{Z})|\leq
L\alpha_{k}\right)\geq 1-q_{k}.$

###### Proof.