# Dynamic Spatial Matching

Yash<EMAIL_ADDRESS>[ Graduate Business School,
Columbia University,

###### Abstract

Motivated by a variety of online matching platforms, we consider demand and
supply units which are located i.i.d. in $[0,1]^{d}$, and each demand unit
needs to be matched with a supply unit. The goal is to minimize the expected
average distance between matched pairs (the “cost”). We model dynamic arrivals
of one or both of demand and supply with uncertain locations of future
arrivals, and characterize the scaling behavior of the achievable cost in
terms of system size (number of supply units), as a function of the dimension
$d$. Our achievability results are backed by concrete matching algorithms.
Across cases, we find that the platform can achieve cost (nearly) as low as
that achievable if the locations of future arrivals had been known beforehand.
Furthermore, in all cases except one, cost nearly as low as the expected
distance to the nearest neighboring supply unit is achievable, i.e., the
matching constraint does not cause an increase in cost either. The aberrant
case is where only demand arrivals are dynamic, and $d=1$; excess supply
significantly reduces cost in this case.

dynamic arrivals,

matching algorithms,

distance,

spatial heterogeneity,

length scales,

###### keywords:

##  1 Introduction

Online matching platforms serve to match units (participants) on the two sides
of the market, in contexts such as car or bike rides, lodging, dating, labor
and organ exchanges. This paper aims to understand and quantify the costs
arising from stochastic spatial heterogeneity in dynamic matching as a
function of market “thickness” and the dimensionality of the relevant “space”
in which supply and demand live, and to identify near optimal control policies
to perform such matching over time. Here space can refer to physical space, as
may be relevant, e.g., in ridehailing, as well as to other relevant
attributes, e.g., for a lodging platform like Airbnb or VRBO, in addition to
physical location (which may be two-dimensional), there are other relevant
attributes such as the “quality” of the unit and the price. Supply units live
in this attribute space and demand units can also be thought of as living in
this same attribute space, with the location of a demand unit being
interpreted as the ideal attribute vector desired.

Spatial matching costs (distances) in _static_ models with _balanced_ (i.e.,
equal) supply and demand, were precisely quantified as a function of
“thickness” (density of points) and the dimensionality of the space in the
seminal works of Ajtai, Komlos & Tusnady [1], Leighton and Shor [2], and
Talagrand [3], among others. The problem studied in [1, 3] is as follows; our
first model (which will serve as a benchmark) will be a generalization. There
are $N$ _supply_ points and $N$ _demand_ points i.i.d. uniformly located in
the $d$-dimensional unit hypercube ${\mathcal{C}}\triangleq[0,1]^{d}$, and one
wants to characterize the (expected) _cost_ , i.e., the average matching
distance, of the minimum cost perfect matching between demand and supply, in
terms of its scaling behavior with $N$. (For concreteness, we will consider
Euclidean distance; all our results extend immediately to any norm equivalent
to the Euclidean norm.) Now, the expected distance between a demand unit and
the nearest supply unit (henceforth, the _nearest-neighbor-distance_) is
$\Theta(1/N^{1/d})$, and this is clearly a lower bound on the expected average
matching distance. [1, 3] develop the following remarkable picture:

  * •

For $d\geq 3$, the expected minimum cost (average distance) is
$\Theta(1/N^{1/d})$, which is the same scaling as the nearest-neighbor-
distance [3].

  * •

For $d=2$, the expected minimum cost is $\Theta(\sqrt{\log N}/\sqrt{N})$ [1].
The nearest-neighbor-distance in this case is $\Theta(1/\sqrt{N})$, and we see
that the expected minimum cost is a factor $\Theta(\sqrt{\log N})$ larger.

  * •

For $d=1$, the expected minimum cost is $\Theta(1/\sqrt{N})$. This is much
larger than the nearest-neighbor-distance, which is only $\Theta(1/N)$.

######  Fact 1.1 (1-dimensional static random matching111There is a minimum
cost matching as follows: order both demand and supply from left to right and
then match units at the same rank in the ordering to each other. The result
then follows from Donsker’s theorem. (The expected cost of this matching is
$\Theta(1/\sqrt{N})$ since the $f$-th fractile of demand and supply are
separated by $\Theta(\sqrt{f(1-f)/N})$ distance in expectation, for all
$f\in(0,1)$.)).

Consider $N$ “supply” points and $N$ “demand” points, i.i.d. uniformly
distributed in $[0,1]$. Then the minimum cost perfect matching between the two
sets of points has expected average matching distance $\Theta(1/\sqrt{N})$,
whereas the expected distance between a given demand unit and the closest
supply unit is only $\Theta(1/N)$.

Motivated by matching platforms, we ask whether and how the above picture for
random spatial matching extends to the case of matching demand and supply
under _dynamic_ arrivals. The key challenge under dynamic arrivals is
uncertainty about the locations of future arrivals, which means that it is
unclear how to choose matches, unlike in the static case where the minimum
cost matching is easy to compute. Indeed, the dynamic spatial matching problem
is a dynamic programming problem with the system state being the locations of
the supply units currently in the system (we will assume that demand units
need to be matched immediately upon arrival), which is an infinite dimensional
state without evident helpful structure. Our task is to design a near optimal
_algorithm_ (control policy) to conduct spatial matching over time. And of
course we want to characterize the minimum achievable expected matching cost.

Locations of demand and supply are assumed to be i.i.d. uniformly random in
the unit hypercube ${\mathcal{C}}$ throughout, to enable us to focus on the
role of spatial stochasticity, as in the literature on static random spatial
matching. We study not just the case of equal demand and supply, but allow for
excess supply. Our characterizations of cost as a function of the excess
supply yield guidance on capacity planning.

We provide characterizations for three natural models:

  * •

The static model above but allowing for $M$ additional supply units. This
setting builds on the known characterizations [1, 3] for the balanced case and
serves as a benchmark.

  * •

A “semi-dynamic” model which is identical to the static model above, except
that demand units arrive sequentially and must be matched immediately upon
arrival.

  * •

A “fully dynamic” model where both supply and demand arrive over time, and
there are $m$ supply units present in the system at any time. In each period,
a demand unit arrives and must be matched immediately, the matched pair
leaves, and then a supply unit arrives, restoring the number of supply units
in the system to $m$. Arrival locations of both demand and supply are i.i.d.
uniform in ${\mathcal{C}}$.

We remark that these models are sequenced in increasing order of technical
complexity, with the fully dynamic model being the most technically
challenging by far.

Summary of contributions. We characterize the scaling behavior of the minimum
achievable cost in each of the three models for each $d$. In the static and
semi-dynamic models the scaling parameters are $N$ and $M$ (where $M\leq N$
can scale arbitrarily with $N$), and in the fully dynamic model the scaling
parameter is $m$. Our upper and lower bounds match up to a constant factor in
all cases, except for the fully dynamic model with $d=1$, where the bounds
match up to a $\log m$ factor. We provide a matching algorithm to achieve near
optimal expected cost in the dynamic models, which we call _Hierarchical
Greedy_. A key feature of the algorithm is analytical tractability; roughly,
it separates out the matching cost at different length scales, and incurs a
cost which is no larger (in terms of scaling) than the fundamental “obstacle
to matching” at each length scale.

Our findings reveal that in each model, the minimum cost achievable increases
with $d$ (by a polynomial factor in the scaling parameter(s)); this
monotonicity is unsurprising since higher $d$ means that compatibility is
measured along more dimensions, which makes the problem harder (formally, the
distance between two points in $d$ dimensions is lower bounded by the distance
between their projections onto $d-1$ dimensions). Our results quantify this
phenomenon.

In each model and for each $d$, we compare the minimum cost achievable with
the relevant nearest-neighbor-distance222The nearest neighbor distance we
compare against is optimistically computed in the dynamic models by assuming a
uniform spatial distribution persists. In reality, the spatial distribution of
existing units which arrived earlier depends on the past matching decisions
and is non-uniform in general., and find that for $d\geq 2$ in all models, and
also for $d=1$ in the fully dynamic model, cost only slightly more than the
nearest-neighbor-distance is achievable. The cost is significantly larger
(i.e., by a polynomial factor as in Fact 1.1) _only_ for $d=1$ and sublinear
excess supply in the static and semi-dynamic models; henceforth we refer to
this case as the aberrant case. Notably, a similar phenomenon does _not_ occur
for $d=1$ in the fully dynamic model, where the nearest-neighbor-distance _is_
achievable up to a polylogarithmic factor. Our analysis identifies that this
is because the fully dynamic matching in $d=1$ dimension conceptually
resembles the problem of static matching in $d+1=2$ dimensions. The intuitive
reason is that time acts like an additional spatial dimension in the fully
dynamic model (this feature extends to $d>1$ as well).

Our results illuminate the impact of uncertainty about the future on matching
cost: Happily, in both dynamic models and all cases uncertainty about the
future does _not_ lead to a substantial (i.e., a polynomial factor) increase
in achievable matching cost.

We briefly summarize our findings regarding the benefit from excess supply.
For the aberrant case $d=1$ in the static and semi-dynamic models, adding
substantial excess supply $M=\omega(\sqrt{N})$ leads to a substantial
reduction in the matching cost, and this is the only case in which excess
supply significantly reduces cost in these two models. The cost reduction from
excess supply in the aberrant case comes _without_ an accompanying reduction
in the nearest-neighbor-distance, and occurs, informally, because excess
supply smooths over stochastic mismatches in the quantities of demand and
supply at the larger length scales. In the fully dynamic model and for all
$d\geq 1$, increasing excess supply (i.e., the volume $m$ of “free” supply
present in the system at any time) reduces cost as a direct consequence of
reduction in the nearest-neighbor-distance, which is perhaps unsurprising and
an entirely different phenomenon than that which occurs in the aberrant case.

Organization of the paper. Section 2 provides characterizations for static
spatial matching with excess supply, and serves as a benchmark in our study of
dynamic spatial matching. Section 3 provides our model and results for the
semi-dynamic model. Section 4 provides our model and results for the fully
dynamic model. Section 5 provides our algorithm for matching and its analysis,
leading to the proofs of our main achievability results. The proofs of our
lower bounds are provided in an appendix. Section 6 discusses an application
of our results for the fully dynamic model to capacity planning for shared
mobility systems. We conclude with a discussion of related work and open
directions in Section 7.

##  2 Static Matching

We begin with a characterization of matching costs for _static_ spatial
matching under excess supply, which extends the celebrated characterizations
for the case of no excess supply [1, 3]. Here, all supply and demand locations
are simultaneously known, and so there is no algorithmic challenge; one simply
chooses the minimum cost matching. The question is that of characterizing (the
scaling behavior of) the minimum cost achievable. The cost in the static
setting is of interest since it will be a lower bound on the minimum cost
achievable in the corresponding dynamic setting we will investigate in the
next section, where locations of future demand arrivals are unknown.

Model. There are $N+M$ supply units and $N$ demand units located at i.i.d.
uniformly random locations in ${\mathcal{C}}\triangleq[0,1]^{d}$. We are
interested in characterizing the expected cost of the minimum cost matching,
among matchings which match all $N$ demand units, and where the cost of a
matching is the average (Euclidean) distance between matched pairs. Note that
$M$ supply units are left over at the end, hence we call $M$ the _excess
supply_. The excess supply may help reduce the expected cost and we aim to
quantify this benefit; the minimum cost for the no excess supply case $M=0$
was known from previous work. We will permit any333An exception is $d=2$,
where our theorem statement does not cover “just-sublinear”
$M\in\mathcal{I}\triangleq(N^{1-\epsilon},\epsilon N)$. Of course the
small-$M$ upper bound on cost $C_{2}\sqrt{\log N/N}$ extends immediately to
$M\in\mathcal{I}$ (since the problem is easier for larger $M$), as does the
large-$M$ lower bound $(1/C_{2})\sqrt{1/N}$ (since our problem is harder for
smaller $M$), i.e., there is a $\sqrt{\log N}$ factor gap between our lower
and upper bounds for $M\in\mathcal{I}$. $M\in\\{0,1,\dots,\Theta(N)\\}$.

######  Theorem 1 (Minimum cost for static matching).

For $d=1$, there exists a constant $C_{1}\in[1,\infty)$ such that for all
$N\geq 2$ we have

$\displaystyle\textup{Minimum achievable expected
cost}\in\left\\{\begin{array}[]{cc}\left[\frac{1}{C_{1}\sqrt{N}},\frac{C_{1}}{\sqrt{N}}\right]&\textup{for
all }M\leq\sqrt{N}\\\\[5.0pt]
\left[\frac{1}{C_{1}M},\frac{C_{1}}{M}\right]&\textup{for all
}M>\sqrt{N}\end{array}\right.\,.$ (3)

For $d=2$, for any $\epsilon\in(0,1)$, there exists a constant
$C_{2}=C_{2}(\epsilon)\in[1,\infty)$ such that for all $N\geq 2$, we have

$\displaystyle\textup{Minimum achievable expected
cost}\in\left\\{\begin{array}[]{ll}\left[(1/C_{2})\sqrt{\frac{\log
N}{N}},C_{2}\sqrt{\frac{\log N}{N}}\right]&\textup{for }M\leq
N^{1-\epsilon}\\\
\left[(1/C_{2})\sqrt{\frac{1}{N}},C_{2}\sqrt{\frac{1}{N}}\right]&\textup{for
}M\in[\epsilon N,N]\end{array}\right.\,.$ (6)

For $d\geq 3$, there exists a constant $C_{d}\in[1,\infty)$ such that for all
$N\geq 2$ and $M\in\\{0,1,\dots,N\\}$ we have

$\displaystyle\textup{Minimum achievable expected
cost}\in\left[\frac{1}{C_{d}N^{1/d}},\frac{C_{d}}{N^{1/d}}\right]\,.$ (7)

Theorem 1 quantifies how excess supply helps in the case $d=1$. For small
excess supply $M\leq\sqrt{N}$, the cost scales as $\Theta(1/\sqrt{N})$, as in
the well known case $M=0$ where this scaling is an immediate consequence of
Donsker’s theorem. Notably, this cost scaling is nearly as large as that for
$d=2$; ensuring proximity along two dimensions is not much harder than
ensuring proximity in one dimension. For $d=1$ and substantial excess supply
$M>\sqrt{N}$, the cost falls to $\Theta(1/M)$. In particular, for linear
excess supply $M=\Theta(N)$, the cost has the same scaling as the nearest-
neighbor-distance $\Theta(1/N)$.

In the case $d=2$, the minimum cost for sublinear excess supply $M\leq
N^{1-\epsilon}$ scales as $\Theta\big{(}\sqrt{\tfrac{\log N}{N}}\big{)}$, as
in the Ajtai-Komlos-Tusnady theorem [1] concerning the case $M=0$. Linear
excess supply $M=\Theta(N)$ eliminates the $\sqrt{\log N}$ factor and allows
to achieve the nearest-neighbor-distance scaling $\Theta(1/\sqrt{N})$.

In the cases $d\geq 3$, even with $M=0$ the cost is already as small as the
nearest-neighbor-distance $\Theta(1/N^{1/d})$ as known from the work of
Talagrand [3], and this clearly extends to any $M\leq N$.

##  3 Semi-dynamic model

We now consider a dynamic version of the same model, where supply units are
present beforehand but where demand units arrive sequentially and need to be
matched immediately upon arrival. Uncertainty about the locations of future
demand arrivals poses a challenge, and leads to two questions: How much larger
is the minimum achievable cost relative to the static model, i.e., how large
is the burden imposed by uncertainty about the future? And how should we
assign a supply unit to each demand unit to achieve near optimal cost?

Model. There are $N+M$ supply units present at the outset, located at i.i.d.
uniformly random locations in ${\mathcal{C}}=[0,1]^{d}$. No further supply
units will arrive thereafter and supply units do not change their location.
The following occurs at each period $t$ for $t=1,2,\dots,N$.

  * •

A demand unit arrives at a uniformly random location in ${\mathcal{C}}$
(independent of the history so far).

  * •

It must be matched immediately to one of the supply units resulting in a cost
equal to the distance between them. The matched pair leaves.

The problem is again to minimize the expected average distance between matched
pairs.

Such a model may be a reasonable approximation of reality in certain real
world settings, for example, for a lodging platform, it may provide a way to
think about the problem of dynamically managing inventory of supply for a
given geographical area and date(s) (e.g., a particular weekend in the Lake
Tahoe area), if suppliers post their inventory in advance but demand arises
closer to the date.

The following main result provides a characterization of the minimum average
matching cost achievable for all $d$ and all $M$. Note that all lower bounds
are “inherited” from the static matching model, since uncertainty about the
location of future demand only makes things harder, and the two models are
identical in all other respects. The content of the theorem lies in the upper
bounds.

######  Theorem 2.

All bounds on the expected average match distance in Theorem 1 hold verbatim
for the semi-dynamic model.444In other words, there exist constants
$(C_{d})_{d=2}^{\infty}$ and $C_{1}(\epsilon)$ such that the bounds apply to
both the static model and the semi-dynamic model.

The theorem says that the scaling behavior of the minimum cost achievable in
each case is entirely unaffected by uncertainty about the locations of future
demands, i.e., one can do nearly as well in the semi-dynamic model as in the
static model. The algorithm leading to our upper bounds in each case is the
Hierarchical Greedy algorithm which we provide in Section 5.1; with the
exception of the $d=2$ and $M\leq N^{1-\epsilon}$ where we use a result of [4]
to show achievability. Theorem 4 is proved in Section 5.2. Our analysis
illuminates how and why excess supply helps for $d=1$ (by mitigating the
obstacle to matching at the larger length scales) but does not help for larger
dimensions $d\geq 2$ (because the nearest-neighbor-distance dominates the cost
anyway). See Figure 1 for a visual representation of Theorem 4 (and Theorem
1).

Figure 1: Minimum achievable cost versus $M$ for different $d$, from Theorem 4
(and Theorem 1)

Compare our tight bounds for all $d$ and all $M$ with the analysis of [5]
which studies the special case $d=1$ and $M=\Theta(N)$ and establishes a upper
bound of $O(\log^{3}N/N)$ on the average matching cost under the standard
greedy algorithm (our results imply that the minimum cost in this case is in
fact $\Theta(1/N)$).

##  4 Fully dynamic model

Finally, we consider a model where both supply and demand units arrive over
time. This is the most technically challenging setting. We will adopt the
simplest model which captures the challenge of spatial heterogeneity, namely,
the tension between achieving a small matching cost _now_ , and maintaining a
supply distribution (state) which is well spread out and hence will facilitate
cheap matching in _future_. Demand units will need to be matched immediately
upon arrival. Our model will be set up so that there are exactly $m$ supply
units in the system at any time. (While our analysis can be extended to a
setting where supply and demand arrivals follow independent Poisson processes,
with supply units arriving slightly faster and abandoning at a certain rate,
and a cost for making demand wait, such a formulation adds unilluminating
technical complexity so we avoid it.) We will formulate a discrete time
average cost minimization problem over a finite (or infinite) horizon, and ask
how the average matching cost per pair scales with $m$ as a function of the
dimension $d$.

Model. Initially there are $m$ supply units at arbitrary locations in
${\mathcal{C}}=[0,1]^{d}$. At each period $t=1,2,\dots,N$, the following
sequence of events occurs (instantaneously):

  * •

A demand unit arrives at a uniformly random location in ${\mathcal{C}}$
(independent of the past) and requires to be matched immediately.

  * •

The system operator chooses one of the $m$ supply units in the system to match
the demand unit to. The matched pair leaves and the period cost is equal to
the Euclidean distance between them.

  * •

A supply unit arrives at a uniformly random location (independent of the
past). This restores the number of supply units present in the system to $m$.

The goal is to minimize the expected average cost per period over some horizon
$N$. Note that this model has just one key model primitive $m$, and as before,
the question will be how the minimum achievable cost scales with $m$ (for
large enough $N$).

The following lower bound on the average cost per period is immediate from
considering the expected distance between the next demand arrival and the
closest supply unit. (This lower bound applies even if the system operator is
permitted to costlessly reposition the $m$ supply units arbitrarily prior to
each time period.) The proof is in the appendix.

######  Proposition 4.1 (Nearest-neighbor-distance lower bound).

For each $d\geq 1$ there exists $\epsilon=\epsilon(d)>0$ such that for all
$m\geq 2$, the expected match cost in each period for any policy is at least
$\epsilon/m^{1/d}$. This holds for arbitrary initial locations of supply units
and any horizon $N\geq 1$.

Our first result shows that the lower bound in Proposition 4.1 is _not_
achievable for $d=1$. In other words, we show a tighter lower bound for the
one-dimension case, by (formally) developing an analogy with two-dimensional
static random matching [1]; in our analogy time acting as an additional
spatial dimension. The proof is in the appendix.

######  Theorem 3 (Tighter lower bound for $d=1$).

For $d=1$, there exists a constant $\epsilon>0$, such that for all $m\geq 2$
and any horizon $N\geq m^{2}$, the expected average cost per period for any
policy is at least $\epsilon\log m/m$. This holds for arbitrary initial
locations of supply units.

This negative result raises the question of whether the nearest-neighbor based
lower bound is unachievable also for $d\geq 2$. How does the optimal average
matching cost scale with $m$ for each $d$? We answer this question
definitively for $d\geq 2$, and up to a $\log m$ factor for $d=1$.

######  Theorem 4 (Achievability).

For each $d\geq 2$, there is a constant $C_{d}<\infty$, such that for all
$m\geq 2$, there is a matching policy which achieves an expected average cost
per match of at most $C_{d}/m^{1/d}$, both in steady state and for any finite
horizon $N\geq C_{d}m^{1.01+1/d}$. For $d=1$, there is a constant
$C_{1}<\infty$, such that for all $m\geq 2$, there is a matching policy which
achieves an expected average cost per match of at most $C_{1}(\log m)^{2}/m$,
both in steady state and for any finite horizon $N\geq C_{1}m^{3}$. For each
$d\geq 1$, if, before period 1, the $m$ supply units are at evenly spread
locations,555As an example of “evenly spread locations”, the $m$ supply units
can be located at the lattice points of a grid
$\\{(i\epsilon,j\epsilon):i,j\in\\{0,1,\dots,m^{1/d}-1\\},\epsilon=1/(m^{1/d}-1)\\}$.
the aforementioned upper bounds on the expected cost hold for arbitrary finite
horizon $N\geq 1$.

To establish Theorem 4, we use a more sophisticated version of our
Hierarchical Greedy algorithm (Section 5.1) and analyze its performance
(Section 5.3).

We are pleased to have obtained these sharp results in what appeared to be a
challenging setting to analyze. This is an average cost minimization problem
where the state of the system (the locations of $m$ supply units) belongs to a
high-dimensional continuum ${\mathcal{C}}^{m}=[0,1]^{dm}$ with $d$-coordinates
per supply unit (of course there is invariance under permutations of supply
units) and an underlying metric (here, the Euclidean distance). Discretizing
${\mathcal{C}}$ nevertheless requires us to consider $\Omega(m)$ discrete
locations arranged in a $d$-dimensional grid in order to study distances of
order $1/m^{1/d}$, and it is unclear how to solve a control problem of match-
distance-minimization in such a state space. The fully dynamic setting appears
substantially more challenging than the semi-dynamic setting studied earlier,
and indeed, to obtain our achievability results we need a more involved
version of Hierarchical Greedy with carefully chosen lower bound constraints
on the supply maintained at each “level” in the hierarchy. Recall that a sharp
analysis of the standard greedy algorithm is challenging even in the semi-
dynamic setting, and analyzing greedy in the fully dynamic setting may be even
harder.

We use Theorem 4 to derive capacity planning prescriptions for shared mobility
systems like ridehailing in Section 6.

##  5 Matching algorithm and proofs of achievability results

In Section 5.1 we provide our Hierarchical Greedy algorithm for dynamic
matching which underlies all our achievability results except for the semi-
dynamic model with $d=2$. In Section 5.2 we show achievability in the semi-
dynamic model (Theorem 4). In Section 5.3, we show achievability in the fully
dynamic model (Theorem 4).

###  5.1 The Hierarchical Greedy algorithm

Fix dimension $d$. We partition the hypercube ${\mathcal{C}}=[0,1]^{d}$ into a
sequence of successively refined partitions
${\mathcal{H}}_{\ell_{0}}\triangleq\\{{\mathcal{C}}\\},{\mathcal{H}}_{\ell_{0}-1},\dots,{\mathcal{H}}_{0}$,
where the non-negative integer $\ell_{0}$ will be chosen later. The partition
${\mathcal{H}}_{\ell_{0}-1}$ is obtained by dividing ${\mathcal{C}}$ into
$2^{d}$ smaller _child_ hypercubes by cutting ${\mathcal{C}}$ midway along
each dimension. For example for $d=2$, the four children of ${\mathcal{C}}$
are
${\mathcal{H}}_{\ell_{0}-1}=\\{[i/2,(i+1)/2]\times[j,(j+1)/2]\;\forall\;(i,j)\in\\{0,1\\}^{2}\\}$.
(The points on the boundary between the child hypercubes can be included in
any one of the adjacent hypercubes; the boundary set plays no role because it
has Lebesgue measure zero.) We call the set ${\mathcal{H}}_{\ell_{0}-1}$ of
hypercubes produced the _level- $(l_{0}-1)$ partition_. We repeat this process
of subdivision iteratively to produce successively refined partitions of
${\mathcal{C}}$, subdividing each hypercube in ${\mathcal{H}}_{\ell}$ into
_child_ hypercubes by cutting it midway along each dimension to produce a
refined partition ${\mathcal{H}}_{\ell-1}$ for
$\ell=\ell_{0},\ell_{0}-1,\dots,1$. Figure 2 provides an illustration for the
case $d=2$. Our choice of $\ell_{0}$ for the fully dynamic model will lead to
the following number of _leaf_ hypercubes in the finest partition
${\mathcal{H}}_{0}$:

$\displaystyle 2^{d\ell_{0}}=\left\\{\begin{array}[]{ll}\Theta(m)&\textup{for
}d\geq 2\\\ \Theta(m/\log m)&\textup{for }d=1\end{array}\,.\right.$ (10)

Later, for the semi-dynamic model we will use $\ell_{0}$ such that
$2^{d\ell_{0}}=\Theta(N)$ for all $d\geq 1$.

${\mathcal{H}}_{\ell_{0}}$${\mathcal{H}}_{\ell_{0}-1}$${\mathcal{H}}_{\ell_{0}-2}$

Figure 2: Hypercube partitions for Hierarchical Greedy for $d=2$

Note that the set ${\mathcal{H}}_{\ell}$ of hypercubes at level
$\ell\in\\{0,1,2,\dots,\ell_{0}\\}$ constitutes a partition of ${\mathcal{C}}$
into $2^{(\ell_{0}-\ell)d}$ hypercubes, each of side-length
$2^{-(\ell_{0}-\ell)}$ and volume $2^{-(\ell_{0}-\ell)d}$. Also note the
hypercubes defined by the above refinement process are organized (by
definition) in a $2^{d}$-ary tree with height $\ell_{0}$. The root of the tree
(whose height in the tree is $\ell_{0}$) is the original hypercube
${\mathcal{C}}$, the nodes at height $\ell$ in the tree are the hypercubes in
the level-$\ell$ partition ${\mathcal{H}}_{\ell}$, and our notion of child
hypercube uniquely specifies the child nodes of each node in the tree. Having
established this tree organization, we will find it pedagogically useful to
also deploy the standard terminology of _parent_ , _ancestor_ and _descendant_
(hypercube) in addition to the notion of child (hypercube).

Algorithm 1 Hierarchical Greedy (HG) for dynamic spatial matching

INPUTS:

The number of dimensions $d$ of the unit cube ${\mathcal{C}}=[0,1]^{d}$.

The number of initial supply units and their locations in ${\mathcal{C}}$.

The number of levels of partition refinements $\ell_{0}+1$

The minimum supply to be maintained for hypercubes at each level
$(\gamma_{l})_{l=0}^{\ell_{0}}\,$, which must satisfy
${\gamma_{\ell_{0}}\in\big{[}\,0\,,\,\textup{(\\# supply units)}\,\big{)}}$ as
well as

$\displaystyle\gamma_{l}\in\big{[}0,2^{-d}\gamma_{l+1}\big{]}\qquad\qquad\forall
l=0,1,\dots,\ell_{0}-1\,.$ (11)

In each period: The location of the demand arrival and then, if this is the
fully dynamic model, the location of the supply arrival.

OUTPUT:

In each period: The existing supply unit to match the arrived demand with.

1:Compute the (initial) number of supply units $n_{h}$ for all hypercubes $h$
in ${\mathcal{H}}_{0}\cup{\mathcal{H}}_{1}\cup\dots\cup{\mathcal{H}}_{l_{0}}$

2:for period $t\geq 1$ do

3: $n_{h}(t)\leftarrow n_{h}\ \ \forall
h\in{\mathcal{H}}_{0}\cup{\mathcal{H}}_{1}\cup\dots\cup{\mathcal{H}}_{l_{0}}$
$\triangleright$ $n_{h}(t)$ denotes supply unit count at the beginning of
period $t$

4: A demand unit arrives to some leaf hypercube
${h_{{\textup{d}}}}={h_{{\textup{d}}}}(t)\in{\mathcal{H}}_{0}$

5: ${\mathcal{S}}\leftarrow\\{l:0\leq
l\leq\ell_{0},n_{A_{l}({h_{{\textup{d}}}})}\leq\gamma_{l}\\}$ $\triangleright$
The set of undersupplied ancestors of $h$

6: if ${\mathcal{S}}=\emptyset$ then $\triangleright$ Determine the level
$\ell$ at which the demand will be matched.

7: $\ell\leftarrow 0$

8: else

9: $\ell\leftarrow 1+\max\\{l:l\in{\mathcal{S}}\\}$ $\triangleright$ Preserve
supply of all undersupplied ancestors

10: end if

11: $h^{\prime}\leftarrow A_{\ell}({h_{{\textup{d}}}})$ $\triangleright$ Start
from the level $\ell$ ancestor of $h$

12: for $l\leftarrow\ell$ to $1$ do $\triangleright$ Iteratively pick the
best-supplied child of $h^{\prime}$, to reach a leaf

13: $h^{\prime}\leftarrow\arg\max\\{n_{h}(t):h$ is a child of $h^{\prime}\\}$

14: end for

15: Match the demand unit to an arbitrary supply unit in the leaf $h^{\prime}$

16: $n_{h^{\prime}}\leftarrow n_{h^{\prime}}-1$ at $h^{\prime}$ and all its
ancestors

17: if fully dynamic setting then

18: A supply unit arrives to some leaf hypercube
${h_{{\textup{s}}}}={h_{{\textup{s}}}}(t)\in{\mathcal{H}}_{0}$

19: $n_{h}\leftarrow n_{h}+1$ at all $h\in\\{A_{l}({h_{{\textup{s}}}}):0\leq
l\leq\ell_{0}\\}$ $\triangleright$ Increment $n_{h}$ at ${h_{{\textup{s}}}}$
and all its ancestors

20: end if

21:end for

Our Hierarchical Greedy (HG) will use the finest partition ${\mathcal{H}}_{0}$
as a discretization of ${\mathcal{C}}$, i.e., it will not distinguish between
different supply units in the same leaf hypercube. We say that a demand unit
is matched at level $\ell$ if

$\displaystyle\ell=\min\\{l:\exists h\in{\mathcal{H}}_{l}\textup{ s.t. the
demand unit and its matched supply unit are both in }h\\}\,,$ (12)

i.e., the supply unit it is matched to belongs to the same hypercube at level
$\ell$, but this is not true for any $\ell^{\prime}<\ell$. Denote the number
of supply units in each hypercube $h\in{\mathcal{H}}_{\ell}$ prior to period
$t$ by $n_{h}(t)$. For a leaf $h\in{\mathcal{H}}_{0}$, denote by $A_{l}(h)$
the level $l$ ancestor of $h$, including $A_{0}(h)=h$. Hierarchical Greedy is
specified in Algorithm 1.

In the semi-dynamic model, we will deploy Hierarchical greedy with no minimum
supply requirements $\gamma_{l}=0$ for all $0\leq l\leq\ell_{0}$, and so
$\ell$ will simply be the lowest level ancestor which has at least one supply
unit. (There is always such a level as long as $M\geq 0$ since the number of
supply units $N+M$ at the beginning exceeds the number of periods $N$.)
Moreover, our analysis will not depend on which leaf descendant of that
ancestor the supply unit is taken from. In contrast, in the more challenging
fully dynamic model, both the $\gamma_{l}$s as well as the leaf to take supply
from will need to be carefully chosen.

######  Lemma 5.1 (Correctness of Hierarchical Greedy in the fully dynamic
model).

We always have $\ell_{0}\notin{\mathcal{S}}$, where ${\mathcal{S}}$ in defined
in line 5 of Hierarchical Greedy. Hence $\ell\leq\ell_{0}$ in line 9 of
Hierarchical Greedy.

###### Proof.

The fact that the root hypercube is never undersupplied
$\ell_{0}\notin{\mathcal{S}}$ is immediate from the requirement
$\gamma_{\ell_{0}}<\textup{\\# supply units}$, the definition of
${\mathcal{S}}$, and the fact that the total number of supply units in the
system remains the same over time. As a result
$\max\\{l:l\in{\mathcal{S}}\\}\leq\ell_{0}-1$ and hence
$\ell=1+\max\\{l:l\in{\mathcal{S}}\\}\leq\ell_{0}$ in line 9 of HG. ∎

The idea of the HG algorithm for the fully dynamic model is twofold:

  * •

(Lines 5–10) We match each demand unit at the lowest level – i.e., the
smallest $\ell$ – possible, subject to never using a supply unit from any
hypercube $h\in{\mathcal{H}}_{l}$ which currently has $\gamma_{l}$ or fewer
supply units, for any $l\leq\ell_{0}$. The minimum targets $\gamma_{l}$ will
be carefully chosen to balance the risk of supply depletion at different
levels.

  * •

(Lines 11–15) When matching at level $\ell>0$ there is a choice between the
leaf nodes which share the same level-$\ell$ ancestor. We make this choice by
– starting with the ancestor at level $\ell$ – iteratively picking the child
hypercube which currently has the largest $n_{h}$.

###  5.2 Semi-dynamic model: Proof of Theorem 4

In the semi-dynamic model, we use the Hierarchical Greedy algorithm with
$\gamma_{l}=0$ for all $l$, i.e., we simply match each arriving demand unit to
its lowest-level ancestor hypercube which has non-zero supply units
remaining.666Note that, here, the set $S$ takes the form
$S=\\{1,2,\dots,\ell\\}$ for some $\ell$, since if some ancestor of the leaf
where demand just arrived has non-zero supply units, all higher levels
ancestors also have non-zero supply units. Recall that the initial number of
supply units is $N+M$ and these are depleted over time as the $N$ demand units
arrive sequentially.

####  5.2.1 Intuition: Obstacles to matching at different length scales

We start by providing some intuition regarding the obstacles to matching at
each length scale, and why Hierarchical Greedy with $\gamma_{l}=0$ for all $l$
is a near optimal algorithm for the semi-dynamic model in light of these
obstacles. The phrase “obstacle to matching at length scale $L$” refers to a
lower bound on matching costs which holds due to discrepancy between demand
and supply at length scale $L$. The development in this subsubsection is
informal and may be skipped by the reader who prefers rigor. Our proof in the
next subsubsection reveals clearly the formal manifestation of the obstacles
to matching.

Consider random static matching in dimension $d$ with no excess supply $M=0$,
and a sub-hypercube $h$ of the unit hypercube ${\mathcal{C}}$ of side
length777Here $1/N^{1/d}$ is the scaling of the nearest-neighbor-distance; we
impose $L\geq 1/N^{1/d}$ to ensure that $h$ contains $\Omega(1)$ demand
(supply) units in expectation. $L\in[1/N^{1/d},1/2]$. The sub-hypercube has
volume $L^{d}$ and “surface area” $\Theta(L^{d-1})$. The realized number of
demand (supply) units in the hypercube is a Binomial($N,\textup{Volume}(h)$)
random variable, and hence has mean $NL^{d}$ and standard deviation
$\Theta(\sqrt{NL^{d}})$. As a result the expected discrepancy between the
number of supply units and the number of demand units in the hypercube is
$\Theta(\sqrt{NL^{d}})$. Suppose, for instance, the realized number of supply
units is smaller than the number of demand units. As a result, one would need
to match some of demand units in the hypercube to supply units outside the
sub-hypercube $h$. How far outside $h$? If one considers points within
distance $\Delta$ from $h$, this incorporates a region outside $h$ of volume
approximately the surface area times $\Delta$, i.e., $\Theta(\Delta L^{d-1})$.
For this outside region to include $\Theta(\sqrt{NL^{d}})$ additional supply
units, we need $N\cdot\Delta L^{d-1}\sim\sqrt{NL^{d}}\Rightarrow\Delta\sim
L^{1-d/2}/\sqrt{N}$. With a little bit of work, one can show a lower bound of
this order $\Delta_{L}\sim L^{1-d/2}/\sqrt{N}$ on the expected average
matching distance achievable for all $L\in[1/N^{1/d},1/2]$. (We formalize this
lower bound for $d=1$ in the proof of Theorem 1.) We observe that for $d=1$,
$\Delta_{L}$ is monotone increasing in $L$ and hence the largest obstacle
occurs at the “macro scale” $L\sim 1$, for $d=2$, the obstacles at all scales
$L\in[1/\sqrt{N},1/2]$ have the same scaling with $N$, and for $d\geq 3$,
$\Delta_{L}$ is monotone decreasing in $L$ and hence the largest obstacle to
matching occurs at the “micro scale” corresponding to the nearest-neighbor-
distance, i.e., $L\sim 1/N^{1/d}$. See Figure 3(a) for a visual representation
of $\Delta_{L}$ versus $L$ for different $d$.

(a) $M=0$

(b) $d=1$ and $M\gtrsim\sqrt{N}$

Figure 3: Obstacles to matching at different length scales

How does excess supply $M>0$ modify the above heuristic picture? With excess
supply $M$, the density of supply units is now $N+M$. The expected excess
supply in the sub-hypercube $h$ grows linearly in the volume as
$M\times\textup{Volume}(h)$ whereas the stochastic fluctuation in the total
demand in $h$ grows only as the square root of the volume as
$\sim\sqrt{N\times\textup{Volume}(h)}$. Comparing the two aforementioned
quantities, we deduce that for longer length scales $L\geq
L_{*}=(N/M^{2})^{1/d}$, the expected excess supply is larger than the
stochastic variability
$M\times\textup{Volume}(h)\geq\sqrt{N\times\textup{Volume}(h)}$ so one
typically does not need to match demand in $h$ to supply outside $h$, i.e.,
_excess supply (nearly) eliminates the obstacle to matching at longer length
scales_ $\Delta_{L}\sim 0$ for $L\gtrsim L_{*}=(N/M^{2})^{1/d}$. In contrast,
for $L<L_{*}$ the expected excess supply is smaller than the stochastic
variability $M\times\textup{Volume}(h)<\sqrt{N\times\textup{Volume}(h)}$ and
one can again show an a $\Delta_{L}\sim L^{1-d/2}/\sqrt{N}$ lower bound on the
expected match distance achievable, i.e., the obstacle to matching at the
smaller length scales remains as in the no-excess-supply case. For $d\geq 2$,
we saw that there is a largest obstacle to matching at the micro scale $L\sim
1/N^{1/d}$, and excess supply $M\leq N$ cannot overcome this obstacle, hence
excess supply does not reduce the achievable cost significantly. In contrast,
for $d=1$, the obstacles to matching are larger at longer length scales for
$M=0$, and excess supply $M\gtrsim\sqrt{N}$ helps significantly by (nearly)
eliminating these obstacles for length scales $L\gtrsim L_{*}=N/M^{2}$. See
Figure 3(b) for a visual representation of $\Delta_{L}$ versus $L$ for $d=1$
and $M\in[\sqrt{N},N]$.

Coming to the Hierarchical Greedy algorithm, a key attractive feature of this
algorithm is that the expected cost per period it incurs due to matches at
level $l$ of the hierarchy is only as large (in terms of scaling) as the
obstacle to matching $\Delta_{L}$ at the corresponding length scale (the side
length of hypercubes at that level $L=2^{d(l-\ell_{0})}$). (One may expect a
similar property to hold also for the standard greedy algorithm, but the state
of the system under the standard greedy algorithm is hard to keep track of
analytically [5].) The reason can be summarized as follows: for length scale
$L=2^{d(l-\ell_{0})}<L_{*}$, a fraction
$~{}\sqrt{NL^{d}}/(NL^{d})=1/\sqrt{NL^{d}}$ of demand units are matched at
that length scale (having failed to match greedily at the levels below; see
Lemma 5.2 below), and each of these demand units incurs a match cost of order
$L$. As a result, the cost incurred by HG at level $l$ is of order
$L/\sqrt{NL^{d}}=L^{1-d/2}/\sqrt{N}\sim\Delta_{L}$. As a result the total cost
of hierarchical greedy is the sum of the obstacles to matching at length
scales $1/2^{\ell_{0}d},1/2^{\ell_{0}d-1},\dots,1$. For $d=1$ this series is
geometrically increasing (by factor $\sqrt{2}$), and for $d\geq 3$ the series
is geometrically decaying (by factor $2^{1-d/2}$). For any geometric series
with factor bounded away from $1$, the largest term and the sum are within a
constant factor of each other, so Hierarchical Greedy achieves the same cost
scaling as the largest obstacle. For $d=2$, there is a $\log N$ factor gap for
$M=O(N^{0.99})$ because there are $\log N$ obstacles of roughly the same size
and so the cost of Hierarchical Greedy would be the largest obstacle times
$\log N$; in this case we use a different algorithm to improve on this
performance by a $\sqrt{\log N}$ factor (roughly, the alternate algorithm
takes advantage of cancellation in discrepancies between demand and supply at
different length scales), which yields a tight bound.

####  5.2.2 Formal proof

We now provide a formal proof of Theorem 4 characterizing the minimum
achievable cost in the semi-dynamic model.

We denote the number of demand units in $h$ which arise during up to and
including period $t$ by $\hat{n}_{h}(t)$. We fix the number of refined
partitions $\ell_{0}$ as the largest integer satisfying $2^{\ell_{0}d}\leq N$.

We will need the following lemma, which bounds the expected excess of demand
over supply for individual hypercubes at each level of the hierarchy.

######  Lemma 5.2.

Assume $M\leq N$. There exists a universal constant $C<\infty$ such that the
following occurs. Let
$\ell\triangleq\inf\big{\\{}l\in\mathbb{Z}:M\geq\sqrt{19N2^{d(\ell_{0}-l)}}\big{\\}}$.
For levels $l<\ell_{0}$, the expected excess of demand units over the initial
number of supply units in a hypercube $h\in{\mathcal{H}}_{l}$ at level $l$ is
bounded above by

$\displaystyle{\textup{E}}\big{[}\big{(}\hat{n}_{h}(N)-n_{h}(1)\big{)}_{+}\,\big{]}\leq\left\\{\begin{array}[]{ll}C\sqrt{N2^{d(l-\ell_{0})}}&\textup{for
}l\in\\{0,1,\dots,\ell-1\\}\\\
C\sqrt{N2^{d(l-\ell_{0})}}\exp\left(-\frac{M^{2}2^{d(l-\ell_{0})}}{19N}\right)&\textup{for
}l\in\\{\ell,\ell+1,\dots,\ell_{0}-1\\}\end{array}\right.\,.$ (15)

Furthermore, let $T_{h}$ denote the first time that $h$ runs out of supply,
and let $h^{\prime}$ denote the parent of $h$. Then the expected amount of
demand that arrives to $h^{\prime}$ after $h$ runs out of supply is simply
${\textup{E}}[\mathbb{I}(T_{h}<N)(\hat{n}_{h^{\prime}}(N)-\hat{n}_{h^{\prime}}(T_{h}))]=2^{d}{\textup{E}}\big{[}\big{(}\hat{n}_{h}(N)-n_{h}(1)\big{)}_{+}\,\big{]}$
and hence (15) implies an upper bound for this quantity as well.

###### Proof.

The number of supply units in $h$ at the outset is
$n_{h}(1)\sim\textup{Binomial}(N+M,2^{d(l-\ell_{0})})$, which has mean
$(N+M)2^{d(l-\ell_{0})}$ and standard deviation
$\Theta\big{(}\sqrt{(N+M)2^{d(l-\ell_{0})}}\big{)}$. The number of demand
units in $h$ which arise during up to and including period $t$ is
$\hat{n}_{h}(t)\sim\textup{Binomial}(t,2^{d(l-\ell_{0})})$ and, in particular,
$\hat{n}_{h}(N)\sim\textup{Binomial}(N,2^{d(l-\ell_{0})})$. The bound of
${\textup{E}}\big{[}(\hat{n}_{h}(N)-n_{h}(1))_{+}\big{]}\leq
C\sqrt{N2^{d(l-\ell_{0})}}$ in the lemma is immediate since it clearly holds
even for $M=0$ for some universal $C<\infty$ by Bernstein’s inequality. We now
show the tighter bound for $M\geq\sqrt{19N2^{d(\ell_{0}-l)}}$ and, along the
way, show the last part of the lemma as well.

Fix any $t<N$. By Bernstein’s inequality

$\displaystyle\mathrm{Pr}(n_{h}(1)\leq 2^{d(l-\ell_{0})}(t+N+M)/2)$
$\displaystyle\leq\exp\left(-\frac{(1/2)((N+M-t)2^{d(l-\ell_{0})}/2)^{2}}{(N+M)2^{d(l-\ell_{0})}+(N+M-t)2^{d(l-\ell_{0})}/6}\right)$
$\displaystyle\leq\exp\left(-\frac{(N+M-t)^{2}2^{d(l-\ell_{0})}}{8(N+M)+4(N+M-t)/3}\right)\leq\exp\left(-\frac{(N+M-t)^{2}2^{d(l-\ell_{0})}}{19N}\right)\,,$

using $M\leq N$. Similarly, for $\hat{n}_{h}$ we obtain

$\displaystyle\mathrm{Pr}(\hat{n}_{h}(t)\geq 2^{d(l-\ell_{0})}(t+N+M)/2)$
$\displaystyle\leq\exp\left(-\frac{(N+M-t)^{2}2^{d(l-\ell_{0})}}{10N}\right)\,.$

It follows from a union bound that

$\displaystyle\mathrm{Pr}(\hat{n}_{h}(t)\geq n_{h}(1))$ (16)
$\displaystyle\leq\mathrm{Pr}\big{(}\;(n_{h}(1)\leq
2^{d(l-\ell_{0})}(t+N+M)/2)\ \textup{OR}\ (\hat{n}_{h}(t)\geq
2^{d(l-\ell_{0})}(t+N+M)/2)\;\big{)}\,$ $\displaystyle\leq
2\exp\left(-\frac{(N+M-t)^{2}2^{d(l-\ell_{0})}}{19N}\right)\,$
$\displaystyle=2\exp\left(-(N+M-t)^{2}B_{l}\right)\,,\qquad\quad\textup{for
}B_{l}\triangleq\frac{2^{d(l-\ell_{0})}}{19N}\,.$

The probability of a demand arriving to $h$ in any period is
$2^{d(l-\ell_{0})}$, independent of the past. Excess demand accummulates only
after the supply has run out. And so,

$\displaystyle{\textup{E}}[(\hat{n}_{h}(N)-n_{h}(1))_{+}]$
$\displaystyle=\sum_{t=1}^{N-1}\mathrm{Pr}(\hat{n}_{h}(t)\geq
n_{h}(1))\mathrm{Pr}(\textup{Demand arrives to $h$ in
$t+1$}|\hat{n}_{h}(t)\geq n_{h}(1))$
$\displaystyle=2^{d(l-\ell_{0})}\sum_{t=1}^{N-1}\mathrm{Pr}(\hat{n}_{h}(t)\geq
n_{h}(1))\,.$ (17)

Note that the probability of a demand arriving to $h^{\prime}$ in any period
is $2^{d(l+1-\ell_{0})}=2^{d}2^{d(l-\ell_{0})}$, independent of the past, so
the last part of the lemma is immediate by following the aforementioned
argument verbatim for $h^{\prime}$ to arrive at

$\displaystyle{\textup{E}}[\mathbb{I}(T_{h}<N)(\hat{n}_{h^{\prime}}(N)-\hat{n}_{h^{\prime}}(T_{h}))]$
$\displaystyle=2^{d(l+1-\ell_{0})}\sum_{t=1}^{N-1}\mathrm{Pr}(\hat{n}_{h}(t)\geq
n_{h}(1))$
$\displaystyle=2^{d}{\textup{E}}\big{[}\big{(}\hat{n}_{h}(N)-n_{h}(1)\big{)}_{+}\,\big{]}\,.$

We now proceed to bound the excess demand in $h$ from above by combining (17)
and (16):

$\displaystyle{\textup{E}}[(\hat{n}_{h}(N)-n_{h}(1))_{+}]$ $\displaystyle\leq
2^{1+d(l-\ell_{0})}\sum_{t=1}^{N-1}\exp\left(-B_{l}(N+M-t)^{2}\right)$
$\displaystyle\leq
2^{1+d(l-\ell_{0})}\int_{1}^{N}\exp\left(-B_{l}(N+M-t)^{2}\right)dt$
$\displaystyle\leq
2^{1+d(l-\ell_{0})}\int_{M}^{\infty}\exp\left(-B_{l}x^{2}\right)dx$
$\displaystyle\leq
2^{1+d(l-\ell_{0})}(1/M)\int_{M}^{\infty}x\exp\left(-B_{l}x^{2}\right)dx=2^{d(l-\ell_{0})}\exp(-B_{l}M^{2})/(B_{l}M)$
$\displaystyle=\frac{19N}{M}\exp(-B_{l}M^{2})\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\textup{(using
the definition of $B_{l}$)}$
$\displaystyle\leq\sqrt{19N2^{d(l-\ell_{0})}}\exp(-B_{l}M^{2})\,,$

as required, where we used $M\geq\sqrt{19N2^{(-l+\ell_{0})d}}$ in the last
inequality. ∎

###### Proof of Theorem 4.

All lower bounds are identical to those in Theorem 1 and immediate from
Theorem 1, since the semi-dynamic setting is only harder than the static
setting due to uncertainty about the future, and the two settings are
identical otherwise.

Fix $\ell_{0}$ as the largest integer satisfying $2^{\ell_{0}d}\leq N$. Let
$\ell\triangleq\inf\big{\\{}l\in\mathbb{Z}:M\geq\sqrt{19N2^{d(\ell_{0}-l)}}\big{\\}}$.
We will find that excess supply $M$ virtually eliminates cost from levels
above $\ell$.

“Vulnerable” levels. The cost at level 0 is clearly bounded above by
$2\sqrt{d}N^{-1/d}$ in each period, since the definition of $\ell_{0}$ implies
that the side length of each hypercube at level $0$ is
$2^{-\ell_{0}}=2(2^{-(\ell_{0}+1)d})^{1/d}\leq 2N^{-1/d}$. We now bound the
cost at level $l\in\\{1,2,\dots,\ell\\}$. There is a possibility of a demand
matching at level $l$ only if the level $l-1$ ancestor of the leaf hypercube
where the demand arrived runs out of supply. Fix any $h\in{\mathcal{H}}_{l}$.
An upper bound on the expected total cost from matches at level $l$ in $h$ can
be obtained by considering the worst case where _every_ arrival to $h$ after
the first child of $h$ runs out, matches at level $l$. Using the second
(latter) part of Lemma 5.2, and the fact that there are $2^{d}$ children, it
follows that the expected number of demand units matched at level $l$ is at
most $2^{2d}$ times the upper bound in (15). Recall that there are
$2^{d(\ell_{0}-l)}$ hypercubes at level $l$ and that each of them has side
length $2^{l-\ell_{0}}$. Hence for $0<l\leq\ell$, we have that the total cost
of level $l$ over $N$ periods is bounded above by

$\displaystyle 2^{d(\ell_{0}-l)}\cdot C2^{2d}\sqrt{N2^{d(l-\ell_{0})}}\cdot
2^{l-\ell_{0}}\sqrt{d}=C\sqrt{d}\sqrt{N}2^{(l-\ell_{0})(1-d/2)+2d}\,,$ (18)

and hence the cost per match at level $l$ is bounded above by this quantity
divided by $N$, i.e.,

$\displaystyle C\sqrt{d}2^{(l-\ell_{0})(1-d/2)+2d}/\sqrt{N}\,.$ (19)

“Secure” levels. Consider any level $l>\max(\ell,0)$. Then the contribution of
level $l+1$ to our upper bound is no more than $2^{1-d/2}\max_{z\geq
1}\exp(-2^{d}z)/\exp(-z)\leq\sqrt{2}e^{-1}<2/3$ times the contribution of
level $l$ to our cost upper bound, using the second case in Lemma 5.2 and our
definition of $\ell$. Given this geometric decay, it follows that the sum of
upper bounds for all levels $\max(\ell,0)+1$ and higher is no more than thrice
the upper bound on cost for level $\max(\ell,0)+1$. In the case that $\ell\geq
1$, the cost at level $\ell+1$ is less than $2^{1-d/2}e^{-1}\leq 1$ times the
upper bound in (18) for level $l=\ell$. Thus, the total cost at levels
$\ell+1$ and higher is no more than thrice the upper bound on cost for level
$\ell$, and hence the scaling of our upper bound will be unaffected by the
contributions from levels $l>\ell$. _Excess supply $M$ effectively takes care
of spatial stochastic fluctuations at these higher levels (larger length
scales)._

With this foundation in place, a little bit of accounting (addition) will
enable us to establish the theorem for all $d\neq 2$.

For $d\geq 3$, even for $M=0$, i.e., $\ell=\infty$, given that (19) decays
geometrically in $l$ by factor $2^{1-d/2}\leq 1/\sqrt{2}$, the bound on total
cost is at most $1/(1-1/\sqrt{2})\leq 4$ times the bound on cost per match at
level $1$. The cost per match at level $1$ is bounded above by

$C\sqrt{d}2^{3d/2+2}N^{-(1/d)(1-d/2)}/\sqrt{N}=\tilde{C}_{d}/N^{1/d}\quad\textup{for
suitable }\tilde{C}_{d}<\infty\,.$

And the cost per match at level $0$ is bounded above by $2\sqrt{d}/N^{1/d}$.
Combining yields the claimed achievability result.

For $d=1$, (19) is geometrically increasing in $l$ by factor $\sqrt{2}$ for
$1\leq l\leq\ell$. We consider three cases. The first case is that
$M\in[\sqrt{19N},N]$. Note that
$\sqrt{19N2^{\ell_{0}}}\geq\sqrt{19N\cdot(N/2)}>N\geq M$ using the definition
of $\ell_{0}$, so we know that $\ell\geq 1$ using the definition of $\ell$.
Also, $M\geq\sqrt{19N}$ implies $\ell\leq\ell_{0}$. That is, we have
$\ell\in[1,\ell_{0}]$. Then the combined contribution of levels
$l=1,2,\dots,\ell_{0}$ to average cost is bounded above by the contribution of
level $\ell$ to the cost times $1/(1-1/\sqrt{2})+3\leq 7$, using our bound
above on the cost contributed by secure levels for the case $\ell\geq 1$. By
(19), the contribution of level $\ell$ to average cost is bounded above by
$\tilde{C}_{1}2^{(\ell-\ell_{0})/2}/\sqrt{N}$ for a suitable
$\tilde{C}_{1}\in(1,\infty)$. By definition of $\ell$ we know that
$2^{(\ell-\ell_{0})/2}\leq\sqrt{38N}/M\leq 7\sqrt{N}/M$, which yields an upper
bound of $49\tilde{C}_{1}/M+2/N\leq 51\tilde{C}_{1}/M$ on the expected cost
per match in this case, as desired. (We used that the cost per match at level
$0$ is at most $2/N$, and that $M\leq N$ and $\tilde{C}_{1}>1$.) We now
consider the complementary case $M<\sqrt{19N}$. Here we obtain a uniform bound
for all such $M$ by considering the hardest case of no excess supply
$M=0\Rightarrow\ell=\infty$, where the combined upper bound on average cost is
at most $1/(1-1/\sqrt{2})\leq 4$ times the upper bound on cost at level
$\ell_{0}$, where the latter is given by (19) by plugging in $l=\ell_{0}$. We
immediately obtain the desired $\hat{C}_{1}/\sqrt{N}$ upper bound for suitable
$\hat{C}_{1}<\infty$. In fact, by choosing
$C_{1}\triangleq\max(\sqrt{19}\hat{C}_{1},51\tilde{C}_{1})$ we ensure that

$\displaystyle
C_{1}/M\geq\left\\{\begin{array}[]{ll}\hat{C}_{1}/\sqrt{N}&\textup{for
}M\in(\sqrt{N},\sqrt{19N})\\\ 51\tilde{C}_{1}/M&\textup{for
}M\in[\sqrt{19N},N]\end{array}\right.\,,$ (22)

i.e., $C_{1}/M$ is an upper bound for all $M\geq\sqrt{N}$. We also know that
$\hat{C}_{1}\leq C_{1}$ and so $C_{1}/\sqrt{N}$ is an upper bound for all
$M\leq\sqrt{N}$. This completes the proof.

For $d=2$ and $M\in[\epsilon N,N]$, we have
$\ell\leq\hat{\ell}=\hat{\ell}(\epsilon)<\infty$ by definition of $\ell$ since
$M\geq\epsilon N$; here $\hat{\ell}$ does not depend on $N$ and $M$. We know
that $2^{2(\ell_{0}+1)}>N\Rightarrow 2^{2\ell_{0}}>N/4$ by definition of
$\ell_{0}$. It follows that the side length of hypercubes at each level
$l\leq\ell$ is bounded above by $2^{-\ell_{0}+l}<2^{l}\cdot
2/\sqrt{N}=2^{l+1}/\sqrt{N}\leq 2^{\hat{\ell}+1}/\sqrt{N}$. Hence each level
$0\leq l\leq\ell$ contributes at most
$\sqrt{2}2^{l+1}/\sqrt{N}=2^{l+3/2}/\sqrt{N}$ to the expected cost per match,
and hence the total contribution of these levels is bounded above by
$2^{\hat{\ell}+5/2}/\sqrt{N}$. As proved above, the cost per match from
“secure” levels above $\ell$ is bounded above by three times the upper bound
on cost incurred at level $\ell$, i.e., $3\cdot 2^{\hat{\ell}+3/2}/\sqrt{N}$.
We infer an upper bound on expected average cost per match of $5\cdot
2^{\hat{\ell}+3/2}/\sqrt{N}$, which, taking $C_{2}\geq 5\cdot
2^{\hat{\ell}+3/2}$, is the result we seek.

To get our achievability result for $d=2$ and $M\leq N^{1-\epsilon}$, we use a
matching algorithm different from Hierarchical Greedy.888In this case, under
Hierarchical Greedy we have $\ell=\infty$ and we already know that each level
$l\leq\ell_{0}$ contributes an expected cost per match of at most
$(6C)/\sqrt{N}$ from (19). Summing over levels, the expected cost per match is
bounded above by $6C(\ell_{0}+1)/\sqrt{N}=\Theta(\log N/\sqrt{N})$. [4]
provides a better (tight) bound. Here we leverage recent work on gravitational
matching for uniform points on the surface of a sphere [4]. Using the online
(gravitational matching) algorithm in that paper used to prove [4, Corollary
3], along with the translation from matching on the surface of a sphere in
$\mathbb{R}^{3}$ to matching on the unit square via stereographic projection
[4, Proposition 8], we obtain a bound of
$\tilde{C}_{2}\sqrt{\log(N+M-t+1)}/\sqrt{N+M-t+1}$ on the expected cost
incurred in period $t$. Summing over $t=1,2,\dots,N$, the total expected cost
is

$\displaystyle\tilde{C}_{2}\sum_{i=M+1}^{N+M}\sqrt{\frac{\log i}{i}}$
$\displaystyle\leq\tilde{C}_{2}\sqrt{\log(2N)}\sum_{i=M+1}^{N+M}\frac{1}{\sqrt{i}}\leq\tilde{C}_{2}\sqrt{2\log
N}\int_{M}^{M+N}\frac{1}{\sqrt{x}}dx$ (23) $\displaystyle\leq
2\tilde{C}_{2}\sqrt{2N\log N}\,.$

It follows that the expected cost per match is at most
$2\tilde{C}_{2}\sqrt{2\log N}/\sqrt{N}$.

∎

###  5.3 Analysis of Hierarchical Greedy for the fully dynamic model: Proof of
Theorem 4

The fully dynamic model is substantially more challenging technically than the
semi-dynamic model. In order to obtain our achievability bounds using
Hierarchical Greedy, we carefully select minimum supply requirements
$(\gamma_{l})_{l=0}^{\ell_{0}}$ (see (29) below), to trade off between the
cost incurred at different levels. Informally speaking, the key tradeoff is
that smaller $\gamma_{l}$ reduces the risk of depletion at level $l$ but
increases the risk of depletion at descendants (levels below $l$).

Our definition of the HG algorithm ensures the following key properties:

  * •

A demand unit arriving in $h\in{\mathcal{H}}_{l}$ is matched at level $l+1$ or
higher only if, at that time, $n_{h}(t)\leq\gamma_{l}$; this is formalized in
Lemma 5.3 below.

  * •

Only supply from “well-supplied” regions is used to serve “outside” demand
from other regions (lines 11–15) which leads to the property formalized in
Lemma 5.4 below.

  * •

The number of supply units $n_{h}(t)$ for $h\in{\mathcal{H}}_{l}$ follows a
stochastic process which – after a short initial transient; see Lemma 5.5 –
first order stochastically dominates an unbiased random walk which is
reflected from below at $\gamma_{l}$ and reflected from above at
$\eta_{l}\triangleq\gamma_{l+1}/2^{d}\geq\gamma_{l}$; see Lemma 5.6 below. As
a result the probability of being at the lower boundary $\gamma_{l}$ is at
most $1/\max(\eta_{l}-\gamma_{l},1)$ in steady state (and not much more than
that after the mixing time has elapsed); see Lemma 5.7. Moreover, the fraction
of demand that gets matched at level $l+1$ is at most this probability (by the
first bullet) and hence inherits the same upper bound; see Lemma 5.8.

######  Lemma 5.3 (Lower boundaries are respected).

For any level $l\leq\ell_{0}-1$ and any hypercube $h\in{\mathcal{H}}_{l}$, if
$n_{h}(t)\leq\gamma_{l}$ then Hierarchical Greedy does not use a supply unit
from $h$ for matching with the demand unit in period $t$.

###### Proof.

Suppose $h\in{\mathcal{H}}_{l}$ and $n_{h}(t)\leq\gamma_{l}$. Since
$n_{h}(t)\leq\gamma_{l}$, by definition of $\ell$ in lines 5-10 of HG we
cannot have both $\ell=l$ AND $A_{\ell}(\cdot)=h$, i.e., a demand unit clearly
cannot be matched at level $l$ to hypercube $h$. So the only way it can be
matched in hypercube $h$ is that it is matched at level $\ell>l$ in
$h^{\prime}=A_{\ell}(\cdot)$ in line 11 which is an ancestor of $h$, and that
$h$ is subsequently selected as the child of choice on line 13 enroute to a
leaf. But we show that even this is not possible. By definition of $\ell$, we
have $n_{h^{\prime}}>\gamma_{\ell}$. We argue by induction that this holds for
every node in the path traversed by lines 12-14 to a leaf: If a node at level
$l^{\prime}+1$ has supply (strongly) exceeding $\gamma_{l^{\prime}+1}$ its
best-supplied child (of its $2^{d}$ children) has supply (strongly) exceeding
$\eta_{l^{\prime}}\triangleq\gamma_{l^{\prime}+1}/2^{d}\geq\gamma_{l^{\prime}}$
by (11). Hence $h$ is not on the path traversed, i.e., a supply unit from $h$
is not used for matching. ∎

######  Lemma 5.4 (Only well-supplied regions are used to serve demand from
outside).

For any level $l\leq\ell_{0}-1$, any hypercube $h\in{\mathcal{H}}_{l}$ and any
period $t$, if $n_{h}(t)<\lceil\eta_{l}\rceil$ where
$\eta_{l}\triangleq\gamma_{l+1}2^{-d}$, and if the demand unit in period $t$
is not located in $h$, then a supply unit from $h$ is not used to serve it.

###### Proof.

If the demand from outside $h$ is matched to a supply unit in $h$, by
definition of HG (lines 11–15) it is matched at a level $\ell$ strictly
exceeding $l$. As in the proof of Lemma 5.3, it then follows that if the
supply unit is taken from $h$, there is more than
$\eta_{l}=\gamma_{l^{\prime}+1}/2^{d}$ supply in $h$. ∎

######  Lemma 5.5 (All lower boundaries are reached soon and remain satisfied
thereafter).

Assume $\ell_{0}$ satisfies $2^{d\ell_{0}}\leq m$. For any $l\leq\ell_{0}$ and
any $h\in{\mathcal{H}}_{l}$, under the HG algorithm we have
$n_{h}(t)\geq\lfloor\gamma_{l}\rfloor$ for all $t\geq T_{h}$ w.p. 1, where
$T_{h}\triangleq\inf\\{t\geq 1:n_{h}(t)\geq\lfloor\gamma_{l}\rfloor\\}$.
Moreover, ${\textup{E}}[T]\leq 7m(\log m+1)=O(m\log m)$ for
$T\triangleq\max_{h\in{\mathcal{H}}_{0}\cup{\mathcal{H}}_{1}\cup\dots\cup{\mathcal{H}}_{\ell_{0}}}T_{h}$.

###### Proof.

Permanence of satisfying lower bounds follows from Lemma 5.3: any
undersupplied hypercube only experiences supply arrivals and no supply
departures and hence $n_{h}(t)>\gamma_{l}-1$ continues to hold for all $t\geq
T_{h}$.

We now bound the duration of the transient $T_{h}$ for an individual hypercube
$h\in{\mathcal{H}}_{l}$. For all $t<T_{h}$, there is no supply departure from
$h$ and there is a supply arrival to $h$ with probability
$p=2^{d(l-\ell_{0})}$. Consider $\tau=m(C_{\tau}\log m+1)$. We have

$\displaystyle\mathrm{Pr}(T_{h}>\tau)$
$\displaystyle=\mathrm{Pr}\left(\textup{Binomial}(\tau,2^{d(l-\ell_{0})})\leq\gamma_{l}-1\right)$
$\displaystyle\leq\mathrm{Pr}\left(\textup{Binomial}(\tau,2^{d(l-\ell_{0}}))\leq
m2^{d(l-\ell_{0})}\right)$ $\displaystyle\leq\exp\left(-\frac{(1/2)(Cmp\log
m)^{2}}{(4/3)Cmp\log m}\right)=\exp\left(-\frac{3Cmp\log m}{8}\right)\,$
$\displaystyle\leq\exp\left(-(3/8)C_{\tau}\log m\right)=1/m^{3C_{\tau}/8}$

where the second inequality follows from Bernstein’s inequality along with the
observation that $p=2^{d(l-\ell_{0})}\geq 2^{-d\ell_{0}}\geq 1/m$; the latter
observation is used again in the third inequality. The number of hypercubes
$h$ in
${\mathcal{H}}_{0}\cup{\mathcal{H}}_{1}\cup\dots\cup{\mathcal{H}}_{\ell_{0}}$
is bounded above by $2^{\ell_{0}d}(1+2^{-d}+2^{-2d}+\dots)\leq 2m$ using
$2^{\ell_{0}d}\leq m$. Hence, it follows from a union bound that for
$T\triangleq\max_{h\in{\mathcal{H}}_{0}\cup{\mathcal{H}}_{1}\cup\dots\cup{\mathcal{H}}_{\ell_{0}}}T_{h}$

$\displaystyle\mathrm{Pr}(T>\tau)$
$\displaystyle\leq\sum_{h}\mathrm{Pr}(T_{h}>\tau)\leq 2m/m^{3C_{\tau}/8}\,.$

Let $\tau_{0}\triangleq m(3\log m+1)$; the idea is that this union bound is
useful for $C_{\tau}>3$, i.e., for $\tau>\tau_{0}$. We deduce the claimed
bound on ${\textup{E}}[T]$ as follows:

$\displaystyle{\textup{E}}[T]$
$\displaystyle=\int_{\tau=0}^{\infty}\mathrm{Pr}(T>\tau)d\tau$
$\displaystyle\leq\tau_{0}+\int_{\tau=\tau_{0}}^{\infty}\mathrm{Pr}(T>\tau)d\tau\leq
m(3\log m+7)\,,$

where we used that $\int_{\tau=\tau_{0}}^{\infty}\mathrm{Pr}(T>\tau)d\tau\leq
6m$ which follows from the union bound above and changing the variable of
integration to $C_{\tau}$. ∎

For each $h\in{\mathcal{H}}_{l},l\in\\{0,1,\dots,\ell_{0}-1\\}$, we define the
lazy, doubly reflected random walk $W_{h}$ as follows for $t\geq T_{h}$:
Define ${\underline{R}_{l}}\triangleq\lfloor\gamma_{l}\rfloor$ and
${\overline{R}_{l}}\triangleq\lceil\eta_{l}\rceil-1$. These will be the lower
and upper reflecting boundaries, respectively. The random walk $W_{h}$ starts
at999Note that, by definition of $T_{h}$, we have
$W_{h}(T_{h})\geq{\underline{R}_{l}}$.
$W_{h}(T_{h})=\min(n_{h}(T_{h}),{\overline{R}_{l}})$ and thereafter evolves as
per

$\displaystyle\tilde{W}_{h}(t)=\max\\!\big{(}\,{\underline{R}_{l}}\,,\,W_{h}(t)-\mathbb{I}\big{[}h=A_{l}({h_{{\textup{d}}}}(t))\big{]}\,\big{)}$
$\displaystyle
W_{h}(t+1)=\min\\!\big{(}\,\tilde{W}_{h}(t)+\mathbb{I}\big{[}h=A_{l}({h_{{\textup{s}}}}(t))\big{]}\,,\,{\overline{R}_{l}}\,\big{)}$
(24)

for $t\geq T_{h}$, where ${h_{{\textup{d}}}}(t)$ and ${h_{{\textup{s}}}}(t)$
are the leaf hypercubes where demand and supply arrive in period $t$. The idea
is that $n_{h}(t)$ is bounded below by $W_{h}(t)$, and that $\tilde{n}_{h}(t)$
is bounded below by $\tilde{W}_{h}(t)$, where $\tilde{n}_{h}(t)$ is defined as
the number of supply units in $h$ after the demand at period $t$ arrives but
before the supply at period $t$ arrives.

######  Lemma 5.6 ($W_{h}$ is a lower bound for supply $n_{h}$).

For all $t\geq T_{h}$, we have $n_{h}(t)\geq W_{h}(t)$ and
$\tilde{n}_{h}(t)\geq\tilde{W}_{h}(t)$.

###### Proof.

We prove the lemma by induction on $t$.

We begin by establishing the induction base for $t=T_{h}$. This is
straightforward; by definition of $W_{h}(T_{h})$, we know that
$n_{h}(T_{h})\geq W_{h}(T_{h})$. And from Lemma 5.3 (Hierarchical Greedy
respects the lower boundary) and the definition of $\tilde{W}_{h}(t)$ for
$t=T_{h}$, we know that $\tilde{n}_{h}(T_{h})\geq\tilde{W}_{h}(T_{h})$.

We will now show that if, for some $t$, we have $n_{h}(t)\geq W_{h}(t)$, then
$\tilde{n}_{h}(t)\geq\tilde{W}_{h}(t)$ and that this further implies
$n_{h}(t+1)\geq W_{h}(t+1)$. Induction will then complete the proof.

$\mathbf{n_{h}(t)\geq
W_{h}(t)\Rightarrow\tilde{n}_{h}(t)\geq\tilde{W}_{h}(t)}$. Suppose
$n_{h}(t)\geq W_{h}(t)$. If the inequality is strict then $n_{h}(t)\geq
W_{h}(t)+1$ and $\tilde{n}_{h}(t)\geq\tilde{W}_{h}(t)$ follows immediately
since $\tilde{n}_{h}(t)\geq n_{h}(t)-1$ by definition of $\tilde{n}_{h}(t)$
(at most one supply unit from $h$ is used to serve the newly arrived demand),
and $W_{h}(t)\geq\tilde{W}_{h}(t)$ by definition of $\tilde{W}_{h}(t)$. It
remains to consider the case $n_{h}(t)=W_{h}(t)$. We consider two subcases
corresponding to whether or not the demand arrival at period $t$ is located in
$h$, and show the desired result in each case.

  * •

Suppose $h$ is an ancestor of ${h_{{\textup{d}}}}(t)$, i.e., the demand
arrival at period $t$ is located in $h$. Then, if $W_{h}(t)$ is not at the
lower reflecting boundary $W_{h}(t)\geq{\underline{R}_{l}}+1$, then by
definition $\tilde{W}_{h}(t)=W_{h}(t)-1$, and we immediately infer that
$\tilde{n}_{h}(t)\geq n_{h}(t)-1\geq W_{h}(t)-1=\tilde{W}_{h}(t)$. On the
other hand, if $n_{h}(t)=W_{h}(t)={\underline{R}_{l}}$, then by definition of
${\underline{R}_{l}}$ and ${\mathcal{S}}$, $h$ is undersupplied
$l\in{\mathcal{S}}$, and the HG algorithm uses a supply node from outside $h$
to serve the newly arrived demand, i.e.,
$\tilde{n}_{h}(t)=n_{h}(t)=W_{h}(t)=\tilde{W}_{h}(t)$.

  * •

The other possibility is that the demand arrival at period $t$ is not located
in $h$. Since $n_{h}(t)=W_{h}(t)\leq{\overline{R}_{l}}<\eta_{l}$, by Lemma 5.4
we know that HG does not use supply from $h$ to serve the newly arrived
demand. As a result $\tilde{n}_{h}(t)=n_{h}(t)\geq W_{h}(t)=\tilde{W}_{h}(t)$.

$\mathbf{\tilde{n}_{h}(t)\geq\tilde{W}_{h}(t)\Rightarrow n_{h}(t+1)\geq
W_{h}(t+1)}$. If the new supply arrival at period $t$ is located in $h$ then
$n_{h}(t+1)=\tilde{n}_{h}(t)+1\geq\tilde{W}_{h}(t)+1\geq W_{h}(t+1)$ by
definition of $W_{h}(t+1)$, which is the result we seek. On the other hand, if
the new supply arrival at period $t$ is not located in $h$, then
$n_{h}(t+1)=\tilde{n}_{h}(t)\geq\tilde{W}_{h}(t)=W_{h}(t+1)$, which is again
the result we seek.

Induction completes the proof.

∎

######  Lemma 5.7 (Probability that $W_{h}$ is at its lower boundary).

There exists a universal constant $C<\infty$, such that for any level
$l\leq\ell_{0}-1$, any hypercube $h\in{\mathcal{H}}_{l}$ and for all
$t\geq\hat{T}_{h}\triangleq
T_{h}+C2^{(\ell_{0}-l)d}({\overline{R}_{l}}-{\underline{R}_{l}}+1)^{2}\log m$,
we have

$\displaystyle\mathrm{Pr}(W_{h}(t)={\underline{R}_{l}})\leq
2/({\overline{R}_{l}}-{\underline{R}_{l}}+1)\,.$

In the case that the initial supply is evenly spread out, for all $t\geq 1$ we
have $\mathrm{Pr}(W_{h}(t)={\underline{R}_{l}})\leq
1/({\overline{R}_{l}}-{\underline{R}_{l}}+1)$.

###### Proof.

The offset by $T_{h}$ is simply because $W_{h}$ starts at period $T_{h}$. By
definition, in each period $t\geq T_{h}$, $W_{h}$ first takes an downward step
with probability $q_{l}\triangleq 2^{-(\ell_{0}-l)d}$ (unless it is at the
lower boundary ${\underline{R}_{l}}$) and then takes a upward step with
probability $q_{l}$ (unless it is at the upper boundary ${\overline{R}_{l}}$).
In words, $W_{h}(t)$ is a lazy doubly reflected simple random walk with a
probability $p_{l}=2q_{l}(1-q_{l})$ of taking a step in a given period (and a
slight asymmetry in the reflecting behavior of the two boundaries). Let $\pi$
be the stationary distribution of $W_{h}$ with $\pi_{k}$ being the probability
of $W_{h}(t)=k$ in steady state. Then, $\pi$ satisfies detailed balance with
$\pi^{*}\triangleq\pi_{{\underline{R}_{l}}+1}=\pi_{{\underline{R}_{l}}+2}=\dots=\pi_{{\overline{R}_{l}}-1}$
and
$\pi_{{\overline{R}_{l}}-1}(1-q_{l})q_{l}=\pi_{\overline{R}_{l}}q_{l}(1-q_{l})$,
i.e., $\pi_{{\overline{R}_{l}}}=\pi^{*}$, and
$\pi_{{\underline{R}_{l}}}q_{l}=\pi_{{\underline{R}_{l}}+1}q_{l}(1-q_{l})$,
i.e., $\pi_{\underline{R}_{l}}=\pi^{*}(1-q_{l})$. In words, $\pi$ is a uniform
distribution over the possible values of $W_{h}$, except at the lower boundary
${\underline{R}_{l}}$, whose steady state probability of occurrence is
slightly smaller than at the other possible values. It follows that
$\pi_{{\underline{R}_{l}}}<1/({\overline{R}_{l}}-{\underline{R}_{l}}+1)$.

Let $m_{l}\triangleq{\overline{R}_{l}}-{\underline{R}_{l}}+1$. It is not hard
to show that the mixing time of the doubly reflected random walk $W_{h}(t)$ is
$\Theta(m_{l}^{2}/q_{l})$ and this will yield the claimed bound. We will
provide a formal argument using coupling from the past [6]. Consider a random
walk $\hat{W}_{h}(t)$ which is the steady version of $W_{h}(t)$; specifically,
we define that $\hat{W}_{h}(t)$ starts at period $T_{h}$ at a location
$\hat{W}_{h}(T_{h})\sim\pi$ sampled from the steady state distribution of
$W_{h}(t)$, and thereafter takes downward and upward steps in sync with
$W_{h}(t)$ pathwise, i.e., $\hat{W}_{h}(t)$ follows the same update rule (24).
Clearly, by definition of $\hat{W}_{h}(t)$, for all $t\geq T_{h}$ we have
$\hat{W}_{h}(t)\sim\pi$. Let $E$ be the event that
$W_{h}(T_{h})>\hat{W}_{h}(T_{h})$. It is immediate from the definition of
$\hat{W}_{h}(t)$ that under ${\mathcal{E}}$, for all $t\geq T_{h}$ we have
$W_{h}(t)\geq\hat{W}_{h}(t)$, and we infer that

$\displaystyle\mathrm{Pr}(W_{h}(t)={\underline{R}_{l}}|{\mathcal{E}})\leq\pi_{{\underline{R}_{l}}}$
(25)

for all $t\geq T_{h}$. Now consider ${\mathcal{E}}^{c}$, i.e.,
$W_{h}(T_{h})\leq\hat{W}_{h}(T_{h})$, which implies that
$W_{h}(t)\leq\hat{W}_{h}(t)$ for all $t\geq T_{h}$. We only need to control
the time it takes before $W_{h}(t)$ meets up with $\hat{W}_{h}(t)$ for the
first time; the two walks will be identical to each other thereafter. It
follows that the time when the two walks meet is upper bounded by
$\overline{T}_{h}\triangleq\inf\\{t\geq T_{h}:W_{h}(t)={\overline{R}_{l}}\\}$
since $\hat{W}_{h}(t)\leq{\overline{R}_{l}}$ for all $t$. In particular,

$\displaystyle\mathrm{Pr}(W_{h}(t)={\underline{R}_{l}}|\textup{any history
s.t. }\overline{T}_{h}\leq t)=\pi_{{\underline{R}_{l}}}<1/m_{l}\,.$ (26)

(This holds under both ${\mathcal{E}}$ and ${\mathcal{E}}^{c}$.) We will now
show that $\overline{T}_{h}$ is, with probability close to 1, bounded above by
$Cm_{l}^{2}\log m/q_{l}$.

Consider any “epoch” consisting of $\Delta\triangleq C_{1}m_{l}^{2}/q_{l}$
consecutive periods $\tau,\dots,\tau+\Delta-1$ for $\tau\geq T_{h}$, where the
universal constant $C_{1}<\infty$ will be chosen later. Let $E_{\tau,\Delta}$
be the event that the random walk $W_{h}$ hits ${\overline{R}_{l}}$ at least
once during this epoch $E_{\tau,\Delta}\triangleq\\{\exists
t\in[\tau+1,\tau+\Delta]:W_{h}(t)={\overline{R}_{l}}\\}$; where we find it
convenient to include the state at the start of period $\tau+\Delta$ in this
definition. Then, we can choose $C_{1}<\infty$ such that

$\displaystyle\mathrm{Pr}(E_{\tau,\Delta}|W_{h}(\tau)=w)\geq
1/2\qquad\forall\tau\geq
T_{h},w\in\\{{\underline{R}_{l}},{\underline{R}_{l}}+1,\dots,{\overline{R}_{l}}\\}\,.$
(27)

The reason is that if the number of attempted upwards steps
$\sum_{t=\tau}^{\tau+\Delta-1}\mathbb{I}\big{[}h=A_{l}({h_{{\textup{s}}}}(t))\big{]}$
minus the number of attempted downward steps
$\sum_{t=\tau}^{\tau+\Delta-1}\mathbb{I}\big{[}h=A_{l}({h_{{\textup{d}}}}(t))\big{]}$
is at least $m_{l}$, this immediately implies $E_{\tau,\Delta}$. Now, the
number of attempted upward steps is Binomial($\Delta,q_{l}$) and the number of
attempted downward steps is independently drawn from the same distribution,
and for a suitable choice of $C_{1}\leq 10$, with probability at least 1/2,
the former is at least $m_{l}=\sqrt{\Delta q_{l}}/\sqrt{C_{1}}$ larger than
the latter.

Now considering a succession of $n=\lceil\log_{2}m\rceil$ epochs of length
$\Delta$, starting at $T_{h}$ and repeatedly using (27), we obtain

$\displaystyle\mathrm{Pr}(\overline{T}_{h}>T_{h}+\Delta n)$
$\displaystyle\leq\mathrm{Pr}\big{(}\cap_{i=0}^{n-1}E_{T_{h}+i\Delta,\Delta}^{c}\big{)}=\prod_{i=0}^{n-1}\mathrm{Pr}(E_{T_{h}+i\Delta,\Delta}^{c}|\cap_{j=0}^{i-1}E_{T_{h}+j\Delta,\Delta}^{c})$
$\displaystyle\leq(1/2)^{n}\leq 1/m\leq 1/m_{l}\,.$ (28)

Here the first inequality used the definition of $E_{\tau,\Delta}$, the
equality used Bayes rule, the second inequality used (27), the third
inequality used the definition of $n$, and the last inequality used
${\overline{R}_{l}}=\lceil\eta_{l}\rceil-1\leq\lceil\gamma_{l+1}2^{-d}\rceil-1\leq\lceil
m2^{-d}\rceil-1\leq m-1$.

Combining with (26) we get the desired result. For all
$t\geq\hat{T}_{h}\triangleq T_{h}+\Delta
n=T_{h}+C_{1}m_{l}^{2}\lceil\log_{2}m\rceil/q_{l}$, we have

$\displaystyle\mathrm{Pr}(W_{h}(t)={\underline{R}_{l}})\leq\;$
$\displaystyle\mathrm{Pr}(\overline{T}_{h}\leq\hat{T}_{h})\mathrm{Pr}(W_{h}(t)={\underline{R}_{l}}|\overline{T}_{h}\leq\hat{T}_{h}\leq
t)+\mathrm{Pr}(\overline{T}_{h}>\hat{T}_{h})$ $\displaystyle\leq\;$
$\displaystyle\mathrm{Pr}(W_{h}(t)={\underline{R}_{l}}|\overline{T}_{h}\leq\hat{T}_{h}\leq
t)+1/m_{l}$ $\displaystyle\leq\;$ $\displaystyle 2/m_{l}\,,$

where the second inequality used (28), and the third inequality used (26).
This completes the proof.

In the case that the initial supply is evenly spread out, $W_{h}$ starts at
$W_{h}(1)={\overline{R}_{l}}$ and $T_{h}=1$. In particular,
${\mathcal{E}}\triangleq\\{W_{h}(T_{h})\geq\hat{W}_{h}(T_{h})\\}$ occurs w. p.
1. The result then follows from (25). ∎

######  Lemma 5.8 (Probability of being matched at level $l$).

For all $l\leq\ell_{0}-1$ define $m_{l}\triangleq
1/({\overline{R}_{l}}-{\underline{R}_{l}}+1)$. For any level
$\ell\in\\{1,2,\dots,\ell_{0}\\}$, any hypercube $h\in{\mathcal{H}}_{\ell}$
and in any period $t\geq\hat{T}_{h}$, the probability of a demand unit being
matched at level $\ell$ is bounded above by $2/m_{\ell-1}$. Hence, for
$t\geq\hat{T}\triangleq\max_{h\in{\mathcal{H}}_{0}\cup{\mathcal{H}}_{1}\cup\dots\cap{\mathcal{H}}_{\ell_{0}-1}}\hat{T}_{h}$,
the expected cost per period due to matches at level $\ell$ is bounded above
by $C^{\prime}2^{\ell-\ell_{0}}/m_{\ell-1}$ for some
$C^{\prime}=C^{\prime}(d)<\infty$ which does not depend on $m$ and $\ell$. (In
the case that the initial supply is evenly spread out, this holds for any
period $t\geq 1$.)

###### Proof.

For a match to occur at level $\ell\geq 1$, it must be that the level $\ell-1$
ancestor $h^{\prime}=A_{\ell-1}(h)$ of the arrival leaf node $h$ is in
${\mathcal{S}}$, i.e., is undersupplied
$n_{h^{\prime}}(t)\leq\gamma_{\ell-1}$, by definition of $\ell$ in lines 5–10
of HG. But for $t\geq\hat{T}_{h^{\prime}}>T_{h^{\prime}}$, this requires
$W_{h^{\prime}}(t)=n_{h^{\prime}}(t)=\underline{R}_{\ell-1}$ by Lemma 5.6,
which occurs with probability at most $2/m_{\ell-1}$, by Lemma 5.7. (In the
case that the initial supply is evenly spread out, this holds for any period
$t\geq 1$.)

Now, for each level $\ell$ hypercube has side length $2^{\ell-\ell_{0}}$, and
hence the maximum distance between any pair of points in the same level-$\ell$
hypercube is bounded by $(C^{\prime}/2)2^{\ell-\ell_{0}}$ for some
$C^{\prime}=C^{\prime}(d)<\infty$ which does not depend on $m$ and $\ell$. It
follows that the matching distance for a match at level $\ell$ is bounded
above by $(C^{\prime}/2)2^{\ell-\ell_{0}}$. Multiplying with the upper bound
$2/m_{\ell-1}$ on the probability of matching at level $\ell$ we get the
expected cost per period due to matches at level $\ell$. ∎

###### Proof of Theorem 4.

Proof for $d\geq 2$. We set $\ell_{0}$ to be the largest integer with
$2^{d\ell_{0}}\leq m/4$. This choice of $\ell_{0}$ ensures that there are
$\Theta(m)$ leaf hypercubes, and the average number of supply units per leaf
hypercube is $\Theta(1)$ (in particular, it is at least $4$ units). We fix
$\beta=2+\delta\in(2,3)$ where $\delta\in(0,1)$ will be chosen later, and
$\textup{for }\ell=0,1,\dots,\ell_{0}$, set

$\displaystyle\gamma_{\ell}$ $\displaystyle\triangleq
m2^{-(\ell_{0}-\ell)d}-\sum_{\ell^{\prime}=\ell}^{\ell_{0}}\beta^{\ell^{\prime}}2^{-d(\ell^{\prime}-\ell)}\,.$
(29)

Note that

$\displaystyle\gamma_{\ell}\geq 4\cdot 2^{\ell
d}-\beta^{\ell}\cdot\frac{1}{1-\beta 2^{-d}}\geq 4\cdot 2^{\ell d}-4\cdot
3^{\ell}\geq 0\,$

as required, where the first inequality used the definition of $\ell_{0}$, the
second inequality used $\beta<3$ and $\frac{1}{1-\beta
2^{-d}}<\frac{2^{d}}{2^{d}-3}\leq 4$ for all $d\geq 2$, and the last
inequality used $d\geq 2$. Also, it follows from the definition of
$\gamma_{\ell}$ that
$\eta_{\ell}=\gamma_{\ell+1}2^{-d}=\gamma_{\ell}+\beta^{\ell}>\gamma_{\ell}$
for all $\ell\leq\ell_{0}-1$, as required. The idea behind our definition of
$\gamma_{\ell}$ is to introduce an additional slack of $\beta^{\ell}$ as we go
down from level $\ell+1$ to level $\ell$ of the tree, for each $\ell$.
Finally, $\gamma_{\ell_{0}}<m$ holds by definition.

Now using Lemma 5.8, we know that the expected cost per match at level
$\ell\geq 1$ is bounded above by $C^{\prime}2^{\ell-\ell_{0}}/m_{\ell-1}\leq
C^{\prime}2^{\ell-\ell_{0}}/\beta^{\ell-1}$, for all $t\geq\hat{T}$ and for
all $t\geq 1$ if the supply is initially evenly distributed. For the same
$C^{\prime}$ the maximum distance between any pair of points which lie within
the same level $0$ hypercube is bounded above by
$(C^{\prime}/2)2^{-\ell_{0}}$, and hence this is an upper bound on the cost
per match at level $0$. Summing the cost per match at level $\ell$ over
$\ell=0,1,\dots,\ell_{0}$, the expected cost per period for $t\geq\hat{T}$ is
bounded above by

$\displaystyle{\textup{E}}[\textup{Distance between matched pair at
}t\,|\,t\geq\hat{T}]$
$\displaystyle\leq(C^{\prime}/2)2^{-\ell_{0}}+2C^{\prime}\cdot
2^{-\ell_{0}}\sum_{\ell=1}^{\ell_{0}}(2/\beta)^{\ell-1}$
$\displaystyle\leq\Big{(}1/2+\frac{2}{1-2/\beta}\Big{)}C^{\prime}2^{-\ell_{0}}$
$\displaystyle\leq(3/2+2/\delta)C^{\prime}4m^{-1/d}\leq(14/\delta)C^{\prime}m^{-1/d}\,,$
(30)

where the second inequality follows from plugging in $\beta=2+\delta$ and the
definition of $\ell_{0}$ which implies $2^{d(\ell_{0}+1)}>m/4\Rightarrow
2^{-\ell_{0}}<2\cdot 4^{1/d}\cdot m^{-1/d}\leq 4m^{-1/d}$ for $d\geq 2$. This
completes the proof for the case where the supply is initially evenly
distributed.

To accommodate arbitrary initial locations of supply units, we now show that
${\textup{E}}[\hat{T}]=o(m^{1.01})$ for an appropriate choice of $\delta$. Now

$\displaystyle{\textup{E}}[\hat{T}]$
$\displaystyle\leq{\textup{E}}[T]+\max_{l\leq\ell_{0}-1}C2^{(\ell_{0}-l)d}({\overline{R}_{l}}-{\underline{R}_{l}}+1)^{2}\log
m$ $\displaystyle\leq 7m\log m+C(m/4)\log
m\max_{l\leq\ell_{0}-1}(\beta^{l}+2)^{2}2^{-2l}\,,$

where the second inequality uses Lemma 5.5, $2^{\ell_{0}d}\leq m/4$,
$\eta_{l}-\gamma_{l}=\beta^{l}$ along with the definitions of
${\overline{R}_{l}}$ and ${\underline{R}_{l}}$, and $d\geq 2\Rightarrow
2^{-dl}\leq 2^{-2l}$. We have $\beta^{l}+2\leq 2\beta^{l}$ for $l\geq 1$ and
the maximizer of $4\beta^{2l}2^{-2l}$ is at $l=\ell_{0}-1$, leading to

$\displaystyle\max_{l\leq\ell_{0}-1}(\beta^{l}+2)^{2}2^{-2l}\leq
4(\beta/2)^{2(\ell_{0}-1)}=4(1+\delta/2)^{2(\ell_{0}-1)}\leq 4m^{\delta/(2\log
2)}\,,$

Plugging back into the bound on ${\textup{E}}[\hat{T}]$ we get

$\displaystyle{\textup{E}}[\hat{T}]$ $\displaystyle\leq(C+7)m^{1+\delta/(2\log
2)}\log m\,=o(m^{1.01})\,,$ (31)

by choosing $\delta\triangleq 0.01$. The total cost which accrues prior to
$\hat{T}$ is bounded above by $\hat{T}$ since the cost per period is at most
$1$, and hence the contribution of the cost of this initial transient to the
average cost over $N$ periods is bounded above by ${\textup{E}}[\hat{T}]/N$.
To get our result we will require that $N$ is large enough that this
contribution is no more than $(C^{\prime}/\delta)m^{-1/d}$. Specifically, we
define $N_{d}(m)\triangleq(C+7)(\log m)m^{1+\delta/(2\log
2)+1/d}(\delta/C^{\prime})=O(m^{1.01+1/d})$ and demand $N\geq N_{d}$ so that,
using (30) and (31), the expected average cost per period is bounded above by

$\displaystyle\frac{{\textup{E}}[\hat{T}]}{N}+\frac{(N-\hat{T})_{+}}{N}(14C^{\prime}/\delta)m^{-1/d}$
$\displaystyle\leq{\textup{E}}[\hat{T}]/N_{0}+(14C^{\prime}/\delta)m^{-1/d}$
$\displaystyle\leq(C^{\prime}/\delta)m^{-1/d}+(14C^{\prime}/\delta)m^{-1/d}\leq(15C^{\prime}/\delta)m^{-1/d}$

We remark that this argument provides the desired bound on expected cost per
period for any fixed $\beta\in\big{(}\,2\,,\,(3/4)\cdot 2^{d}\,\big{)}$, under
a long enough horizon (e.g., in steady state). Here $\beta<(3/4)\cdot 2^{d}$
is needed to ensure that the $\gamma_{\ell}$s are non-negative (the
contribution of slack from higher levels of the tree decays exponentially),
whereas $\beta>2$ ensures that the contribution to cost from level $\ell$ of
the tree decays exponentially in $\ell$. Our choice of $\beta=2.01$, just
above the minimum requirement $\beta>2$, ensures that the transient $\hat{T}$
is short by ensuring that the auxiliary random walks at the higher levels of
the hierarchy mix rapidly (though a more refined analysis would control the
cost during the transient and obtain a similar bound even for the case where a
larger $\beta$ is used).

Proof for $d=1$. For $d=1$, we set $\ell_{0}$ to be the largest integer with
$2^{\ell_{0}}\leq m/(1+\log_{2}m)$. This choice of $\ell_{0}$ ensures that
there are $\Theta(m/\log m)$ leaf hypercubes, and the average number of supply
units per leaf hypercube is $\Theta(\log m)$ (in particular, it is at least
$1+\log_{2}m$). We fix $\beta=2$ and use the same definition (29) for the
$\gamma_{\ell}$s as before. Plugging in $\beta=2$ and $d=1$ we have

$\gamma_{\ell}=m2^{-(\ell_{0}-\ell)}-2^{\ell}(\ell_{0}-\ell+1)\geq
2^{\ell}(1+\log_{2}m-\ell_{0}+\ell-1)\geq 0\,,$

using the definition of $\ell_{0}$ which implies $m2^{-\ell_{0}}\geq
1+\log_{2}m$. Also, once again
$\eta_{\ell}=\gamma_{\ell}+\beta^{\ell}=\gamma_{\ell}+2^{\ell}>\gamma_{\ell}$.
Thus we have verified that our choice of $\gamma_{l}$s satisfies the
requirements.

Again using Lemma 5.8, the cost per match at level $\ell\geq 1$ for
$t\geq\hat{T}$ is bounded above by $C^{\prime}2^{\ell-\ell_{0}}/m_{\ell-1}\leq
C^{\prime}2^{\ell-\ell_{0}}/(\eta_{l-1}-\gamma_{l-1})=C^{\prime}2^{-\ell_{0}+1}\leq
4C^{\prime}(1+\log_{2}m)/m$ for all $0\leq\ell\leq\ell_{0}$, where we used
$2^{\ell_{0}+1}>m/(1+\log_{2}m)$ by definition of $\ell_{0}$. For the same
$C^{\prime}$ the maximum distance between any pair of points which lie within
the same level $0$ hypercube is bounded above by
$(C^{\prime}/2)2^{-\ell_{0}}\leq C^{\prime}(1+\log_{2}m)/m$, and hence this is
an upper bound on the cost per match at level $0$. Since there are
$\ell_{0}+1\leq 1+\log_{2}m$ levels, the total cost per match for
$t\geq\hat{T}$ is bounded above by $4C^{\prime}(1+\log_{2}m)^{2}/m$. This
completes the proof for the case where the supply is initially evenly
distributed.

Towards accommodating arbitrary initial locations of supply units, we now show
that $\hat{T}=O(m^{2})$. We have

$\displaystyle{\textup{E}}[\hat{T}]$
$\displaystyle\leq{\textup{E}}[T]+\max_{l\leq\ell_{0}-1}C2^{\ell_{0}-l}({\overline{R}_{l}}-{\underline{R}_{l}}+1)^{2}\log_{2}m\leq
7m\log m+Cm\max_{l\leq\ell_{0}-1}(2^{l}+2)^{2}2^{-l}$

where the second inequality uses Lemma 5.5, $2^{\ell_{0}d}\leq
m/(1+\log_{2}m)\Rightarrow 2^{\ell_{0}d}\log_{2}m\leq m$, and
$\eta_{l}-\gamma_{l}=2^{l}$ along with the definitions of ${\overline{R}_{l}}$
and ${\underline{R}_{l}}$. Now

$\displaystyle\max_{l\leq\ell_{0}-1}(2^{l}+2)^{2}2^{-l}$
$\displaystyle\leq\max((2^{\ell_{0}})^{2}2^{-\ell_{0}+1},9)=\max(2^{\ell_{0}+1},9)$
$\displaystyle\leq\max(2m/(1+\log_{2}m),9)\leq 5m\,,$

where we used that for $\ell_{0}\geq 3$, the maximizer occurs at
$l=\ell_{0}-1$ and $2^{\ell_{0}-1}+2\leq 2^{\ell_{0}}$, and $m\geq 2$ in the
last inequality. Plugging back into the previous bound, we obtain

$\displaystyle{\textup{E}}[\hat{T}]$ $\displaystyle\leq 7m\log
m+5Cm^{2}\leq(5C+7)m^{2}=O(m^{2})\,,$

using $\log m\leq m$. We define $N_{0}(m)\triangleq(5C+7)m^{3}$ and require
$N\geq N_{0}$ so that, as in the proof for $d\geq 2$, the expected average
cost per period is bounded above by

$\displaystyle\frac{{\textup{E}}[\hat{T}]}{N}+\frac{(N-\hat{T})_{+}}{N}4C^{\prime}(1+\log_{2}m)^{2}/m$
$\displaystyle\leq{\textup{E}}[\hat{T}]/N_{0}+4C^{\prime}(1+\log_{2}m)^{2}/m$
$\displaystyle\leq m^{-1}+4C^{\prime}(1+\log_{2}m)^{2}/m$
$\displaystyle\leq(4C^{\prime}+1)(1+\log_{2}m)^{2}/m\,.$

This completes the proof.

We remark that in this case no other choice of $\beta$ works. Our choice
$\beta=2$ balances between the challenge of ensuring non-negativity of the
$\gamma_{\ell}$s and ensuring that the cost at level $\ell$ does not grow with
$\ell$. Our upper bound in this case is a factor $(\log m)^{2}$ larger than
the nearest-neighbor-distance $\Theta(1/m)$. Since all levels of the tree
contribute the same order of cost, this accounts for one factor $\log m$ in
our upper bound. The second factor of $\log m$ enters since the slack
introduced at all levels of the tree in the definition of the $\gamma_{\ell}$s
adds up as $\ell_{0}$ equal terms (in our definition of $\gamma_{0}$), we need
to have $\Theta(\log m)$ average supply at each leaf node to obtain
$\gamma_{0}\geq 0$ instead of $\Theta(1)$ average supply per leaf node needed
for $d\geq 2$. ∎

##  6 Application: Capacity planning for shared mobility systems

Motivated by applications like ride-hailing and bikesharing, consider the
fully dynamic model, augmented (interpreted) as follows:

  * •

We define physical time as $t/n$ where $n$ will be our scaling parameter,
interpreted as the rate of arrival of demand with respect to physical time. We
call $n$ the _load factor_.

  * •

Our system will have $n+m$ supply units circulating in it. New supply units
will not arrive and existing supply units will not leave.

  * •

Each supply unit becomes “busy” when it is matched to a demand unit. It
remains busy for $n$ periods (a physical time interval of length 1, the time
taken to complete a ride) and then reappears as a free supply unit at a
uniformly random location. With regard to the ride-hailing application, the
interpretation is that each demand unit has an i.i.d. uniformly random origin
and an i.i.d. uniformly random destination. In each period, one supply unit
becomes free (“arrives”) at a uniformly random location.101010This includes
the initial periods $1,2,\dots,n$. Notionally, those supply units were already
in transit at period 1.

  * •

The platform is able to choose the excess supply $m\geq 0$ beforehand. ($m$
cannot vary over time.) Excess supply costs $m$ per unit of physical time,
i.e., $m/n$ per period.

  * •

As before, the matching cost is equal to the distance between the demand unit
and the matched supply unit.

  * •

The platform’s objective is to choose the excess supply $m$ (and the matching
policy) so as to minimize the sum of the excess supply cost and the expected
matching cost, over some time horizon.

  * •

For simplicity, assume that initially the $m$ free supply units are at evenly
spread locations.

Consider $d\geq 2$. For any fixed $m$, Theorem 4 and Proposition 4.1 tell us
that the smallest achievable expected matching cost per period is
$\Theta(1/m^{1/d})$, over any time horizon. The supply cost per period is
$m/n$. Hence the total expected cost per period is $m/n+\Theta(1/m^{1/d})$
which is minimized by choosing $m=\Theta(n^{d/(d+1)})$. In words, the platform
should ensure that the excess supply scales up as the $d/(d+1)$-th power of
the load factor $n$ to minimize the total cost; this choice causes the system
to be in the so-called quality-and-efficiency driven (QED) regime (i.e., the
regime where two types of costs have the same scaling; the QED regime was
first identified by Halfin and Whitt [7]).

This model for $d=2$ is a close cousin of that of Besbes, Castro and Lobel
[8]. The goal of [8] was the same, namely, to quantify the (scaling of) the
optimal amount of excess supply needed, and motivated by ridehailing, they
focus on111111A difference between the two models is that [8] incorporate
pickup times (proportional to the match distance) in their formulation,
whereas we don’t. $d=2$. An important distinction between the models is that
whereas we concretely deal with the spatial supply state resulting from past
matching decisions and the consequent match cost, [8] study an optimistic
“reduced form” model which simply assumes that a crudely estimated nearest-
neighbor-distance is achievable. Like us, [8] finds that the service firm
should use excess supply which scales as the offered load to the exponent
$d/(d+1)=2/3$. Thus, our finding above can be viewed as verifying the
“prediction” of [8] regarding the optimal scaling of excess supply and
extending it to all $d\geq 2$, by showing that the nearest-neighbor-distance
is indeed achievable.

Note that for $d=1$, repeating our analysis above leveraging Theorem 3 and
Theorem 4 reveals that the optimal scaling of excess supply is between
$\sqrt{n}\sqrt{\log n}$ and $\sqrt{n}\log n$. In contrast, applying the
nearest-neigbor reasoning of [8] would lead to a “predicted” optimal excess
supply which scales as $\sqrt{n}$, which would be _nearly_ correct, but would
miss an additional polylogarithmic factor. We emphasize that we consider our
findings that the nearest-neighbor-distance is nearly achievable for all
$d\geq 1$ in the fully dynamic setting to be a pleasant surprise in light of
the fact that nearest-neighbor based reasoning leads us badly astray in the
case of 1-dimensional static matching (Fact 1.1).

##  7 Discussion

Note that the Hierarchical Greedy algorithm which powers our achievability
results has the attractive feature that it does not require prior knowledge of
the horizon (number of demand units).121212The same holds for the
gravitational matching algorithm we adopt from [4].

In the rest of this section we will discuss related work, and point out some
open directions.

###  7.1 Related work

This work builds on and is inspired by the deep and beautiful results on
static spatial matching of Ajtai, Komlos & Tusnady [1] in two dimensions, and
Talagrand [3] in three and higher dimensions, and the work of Shor on average-
case dynamic bin packing [9, 10], among others. In the average-case dynamic
bin packing problem [9, 10], an unknown number of items of size i.i.d.
Uniform$(0,1)$ arrive sequentially and must be packed in bins of size $1$, so
as to minimize the expected wasted space; Shor shows that this problem is
related to static spatial matching in two dimensions, with time in the bin
packing problem being analogous to a spatial dimension in the latter problem.
[9] inspires our proof of the lower bound for our fully dynamic model for
$d=1$, while [10] bears a spiritual resemblance to our Hierarchical Greedy-
based approach to achievability.

There is a rich line of work on (static) matching between a Poisson process
(or other translation invariant point processes) and the Lebesgue measure in
$\mathbb{R}^{d}$. Interest in this infinite setup originated from the fact
that an allocation rule gives rise to a shift-coupling between a point process
and its Palm version; see, e.g., [11]. [12] study the so-called stable
matching between the two measures and prove lower bounds on the typical
allocation distance. [13] study gravitational allocation in the same setting
for $d\geq 3$ and show exponential decay of the “allocation diameter”;
subsequently [14] obtained a Poisson allocation with optimal tail behavior for
$d\geq 3$ using a different approach inspired by [1]. Recently, Holden, Peres,
and Zhai [4] study gravitational matching for uniform points on the surface of
a sphere and recover the achievability result of [1] for 2-dimensional static
spatial matching. Recall that we use a dynamic implementation of [4] to obtain
a tight upper bound in our semi-dynamic model for $d=2$ and $M\leq
N^{1-\epsilon}$.

We remark that while a dynamic implementation of gravitational matching (or
other approaches developed previously for static matching) may yield tight
achievability results in our (easier) semi-dynamic setting, such an approach
would yield inferior results in our fully dynamic model for $d=1$ (by a
polynomial factor) and $d=2$ (by a polylogarithmic factor), forcing us to
develop a novel algorithmic and analytical methodology.131313The idea is to
construct a matching (transport) between $m$ i.i.d. “supply” points in
$[0,1]^{d}$ and the $m$-times the Lebesgue measure on $[0,1]^{d}$, and to
match each demand arrival to one of the $m$ points based on this transport.
Such an approach ensures that the locations of the $m$ points remains i.i.d.
uniform. However, for $d=1$ the cost of any transport between $m$ i.i.d.
points and the Lebesgue measure is $\Omega(1/\sqrt{m})$. We achieve a much
better scaling of $(\log m)^{2}/m$ via Hierarchical Greedy. Specifically, our
Hierarchical Greedy-based approach takes advantage of averaging over time,
which static matching-based approaches fail to do.

Recently, Besbes, Castro and Lobel [8] estimate the scaling for the amount of
“safety” supply (the excess of supply over demand) in order to be in the
“quality and efficiency driven (QED) regime”; see the discussion in Section 5.

We briefly mention the earlier work of Bertsimas and Van Ryzin [15] which
studies the problem of routing vehicles in the plane under stochastic and
dynamic vehicle arrivals, and allows for capacitated vehicles, i.e., each
vehicle must return to its “depot” after serving a certain maximum number of
demand units. They characterize system stability and the minimum achievable
expected waiting time; their results on the scaling of the expected waiting
time are driven by the fact that the nearest-neighbor-distance in two
dimensions scales as $1/\sqrt{\textup{Density of points}}$.

The very recent work [5] considers the semi-dynamic model in one dimension
$d=1$ (the setting we termed the “aberrant case”) and observes that excess
supply significantly reduces the matching distance. [5] studies only the
specific case $M=\Theta(N)$ and $d=1$ and shows an upper bound of
$O(\log^{3}N/N)$ for the average match distance under the greedy algorithm.
Our hierachical analysis leading to tight bounds for all $d$ and $M$ – e.g.,
our results imply that the minimum achievable cost in the special case studied
in [5] is in fact $\Theta(1/N)$ – is unrelated to the analysis in
[5].141414The technical contribution of [5] appears to be an analysis of the
_greedy_ algorithm in particular (for $d=1$ and $M=\Theta(N)$), since an
alternative binning-based approach which partitions $[0,1]$ into subintervals
of length $\Theta(\log N/N)$ each, can be immediately shown to have cost upper
bounded by $O(\log N/N)$, which is $(\log N)^{2}$ smaller than their upper
bound on greedy. The greedy algorithm indeed appears hard to analyze sharply,
which motivated us to introduce a hierarchical variant of greedy. [5] do not
study the fully dynamic model, which may be setting closest to applications
such as ridehailing. Our analysis reveals that, in fact, the fully dynamic
model in $d$ dimensions loosely resembles the semi-dynamic model in $d+1$
dimensions, i.e., there is no analog in the fully dynamic model of the $d=1$
case in the semi-dynamic model. Moreover, in the semi-dynamic model the cost
in the aberrant $d=1$ case is driven by the longer length scales which makes
this case fundamentally different from $d\geq 2$, and hence the aberrant case
is unrelated to the fully dynamic model for any $d\geq 1$.

###  7.2 Open directions

We leave it as a challenging open problem to close the logarithmic factor gap
between our upper and lower bounds for $d=1$ in the fully dynamic model. We
expect that the resolution of this open problem will lead to new algorithmic
insights, specifically, on how to take advantage of “cancellation” between
mismatches in the quantities of demand and supply at different length scales.
We conjecture that our lower bound is tight, and moreover expect that greedy
(or any similar approach) will _not_ achieve the optimal scaling because it
does not leverage such cancellation.

Our achievability results relying on Hierarchical Greedy need the match cost
to not grow too fast with match distance (here we assumed match cost equal to
the match distance). Suppose match cost is equal to the $\textup{(Euclidean
distance)}^{p}$ for $p>1$. First consider the semi-dynamic model with $d\geq
3$ and $M=0$. For $p<d/2$ our approach using Hierarchical Greedy yields an
upper bound of $O(1/N^{p/d})$ on the expected average match cost (the micro
length scale dominates the cost) which matches the nearest-neighbor-based
lower bound. In contrast for $p>d/2$, the expected cost of Hierarchical Greedy
scales as $O(1/\sqrt{N})$ (here the macro length scale dominates the cost),
whereas we conjecture that the nearest-neighbor-based lower bound
$\Omega(1/N^{p/d})$ is tight for $p<d$. Next, consider the fully-dynamic model
with $d=1$. For any $p>1$, we expect our Hierarchical Greedy-based approach
will only yield an upper bound of $O(1/{m})$, whereas expected average match
cost of $O(\textup{polylog}\,m/m^{p})$ may be achievable by a different
algorithm. Establishing these conjectures would require a novel approach(es),
to overcome the deficiency of Hierarchical Greedy that it matches some demand
units over a large distance. A related direction is to obtain tail bounds on
the matching distance in our dynamic matching models.

We ask the following question: As $d\to\infty$, is it possible to achieve
expected cost per match which is within a $1+o_{d}(1)$ factor of the expected
distance to the nearest neighbor, cf. the bounds of Talagrand for static
spatial matching [3]? We believe this is an interesting question in both the
semi-dynamic and the fully dynamic models.

It is of interest to explore what happens when demand and supply have
different spatial distributions. In this case, the expected average matching
cost must exceed the minimum average cost achievable in the continuum limit,
and one might hope that the excess cost on top of the cost in the continuum
limit may have the same scaling as the characterizations in the present paper.
This direction may lead, moreover, to the development of a theory of network
revenue management [16] with many types.

[Acknowledgments] This paper has greatly benefited from extensive
conversations with Itai Ashlagi, Omar Besbes, Yeon-Koo Che, David Goldberg,
Akshit Kumar, Jacob Leshno, Amin Saberi, Michel Talagrand, and Shawn
(Shangzhou) Xia.

## References

  * [1] M. Ajtai, J. Komlós, and G. Tusnády, “On optimal matchings,” _Combinatorica_ , vol. 4, no. 4, pp. 259–264, 1984.
  * [2] T. Leighton and P. Shor, “Tight bounds for minimax grid matching with applications to the average case analysis of algorithms,” _Combinatorica_ , vol. 9, no. 2, pp. 161–187, 1989.
  * [3] M. Talagrand, “Matching random samples in many dimensions,” _The Annals of Applied Probability_ , pp. 846–856, 1992.
  * [4] N. Holden, Y. Peres, and A. Zhai, “Gravitational allocation for uniform points on the sphere,” _The Annals of Probability_ , vol. 49, no. 1, pp. 287–321, 2021.
  * [5] M. Akbarpour, Y. Alimohammadi, S. Li, and A. Saberi, “The value of excess supply in spatial matching markets,” _arXiv preprint arXiv:2104.03219_ , 2021\.
  * [6] J. Propp and D. Wilson, “Coupling from the past: a user’s guide,” _Microsurveys in discrete probability_ , vol. 41, pp. 181–192, 1998.
  * [7] S. Halfin and W. Whitt, “Heavy-traffic limits for queues with many exponential servers,” _Operations research_ , vol. 29, no. 3, pp. 567–588, 1981.
  * [8] O. Besbes, F. Castro, and I. Lobel, “Spatial capacity planning,” _Available at SSRN 3292651_ , 2018.
  * [9] P. W. Shor, “The average-case analysis of some on-line algorithms for bin packing,” _Combinatorica_ , vol. 6, no. 2, pp. 179–200, 1986.
  * [10] ——, “How to pack better than best fit: tight bounds for average-case online bin packing,” in _[1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science_. IEEE Computer Society, 1991, pp. 752–759.
  * [11] A. E. Holroyd and Y. Peres, “Extra heads and invariant allocations,” _The Annals of Probability_ , vol. 33, no. 1, pp. 31–52, 2005.
  * [12] C. Hoffman, A. E. Holroyd, and Y. Peres, “A stable marriage of poisson and lebesgue,” _The Annals of Probability_ , vol. 34, no. 4, pp. 1241–1272, 2006\.
  * [13] S. Chatterjee, R. Peled, Y. Peres, and D. Romik, “Gravitational allocation to poisson points,” _Annals of mathematics_ , pp. 617–671, 2010.
  * [14] R. Markó and Á. Timár, “A poisson allocation of optimal tail,” _The Annals of Probability_ , vol. 44, no. 2, pp. 1285–1307, 2016.
  * [15] D. J. Bertsimas and G. Van Ryzin, “Stochastic and dynamic vehicle routing in the euclidean plane with multiple capacitated vehicles,” _Operations Research_ , vol. 41, no. 1, pp. 60–76, 1993.
  * [16] K. T. Talluri, G. Van Ryzin, and G. Van Ryzin, _The theory and practice of revenue management_. Springer, 2004, vol. 1.
  * [17] M. Talagrand, _Upper and lower bounds for stochastic processes: decomposition theorems_. Springer International Publishing, 2021, vol. 60.

## Proofs of Proposition 4.1, Theorem 1 and Theorem 3

###### Proof of Proposition 4.1.

The state of the system consists of the locations of the $m$ supply units
prior to a period. For arbitrary state, we will show that the expected
distance between the next demand arrival and the closest supply unit is at
least $1/(Ck^{1/d})$ for some $C=C(d)<\infty$ which does not depend on the
state. As a result, the expected cost in each period is at least this much,
establishing the proposition.

Fix a state. Let $B_{i}$ be the ball of radius $r=2/(Ck^{1/d})$ around the
$i$-th supply unit, for $1\leq i\leq m$. The volume of $B_{i}$ is proportional
to $r^{d}=\frac{2^{d}}{C^{d}m}$, and hence for large enough $C<\infty$, the
$\textup{Vol}(B_{i})\leq\frac{1}{2m}$. Hence the
$\textup{Vol}(\cup_{i=1}^{m}B_{i})\leq 1/2$. On the other hand,
${\textup{Vol}}({\mathcal{C}})=1$ and hence
${\textup{Vol}}({\mathcal{C}}\backslash(\cup_{i=1}^{m}B_{i}))\geq 1/2$. It
follows that with probability at least $1/2$, the demand arrival will be
outside this union of balls $\cup_{i=1}^{m}B_{i}$, i.e., the distance to the
nearest supply unit will be at least $r$. We immediately infer that the
expected distance between the next demand arrival and the closest supply unit
is at least $r/2=1/(Ck^{1/d})$. ∎

###### Proof of Theorem 1.

All our upper bounds (i.e., achievability results) in this setting are
immediate from Theorem 4 since the semi-dynamic setting is only harder than
the static setting due to uncertainty about the locations of future arrivals.
Hence, we only need to prove the lower bounds.

The lower bound for $d\geq 3$ follows from the fact that the nearest-neighbor-
distance remains $\Omega(1/N^{1/d})$ for any $M\leq N$.

The lower bound for $d=1$ is proved by building on the intuition we provide
next. Observe that (i) the density of demand units is $N$ and the density of
supply units is $N+M$, (ii) the stochastic fluctuations in the number of
demand (supply) units in an interval of length $L$ are of order $\sqrt{NL}$.
As a result, for $M\in[\sqrt{N},N]$, the excess supply density $M$ ensures
that there is no supply shortage over subintervals of length $L$ exceeding
$L_{*}\sim N/M^{2}$ since the excess supply $ML$ is larger than the stochastic
fluctuation $\sqrt{NL}$ for such intervals. Now, the supply shortage over a
subinterval of length $L\lesssim L_{*}$ requires matching over an expected
distance $\Delta_{L}\sim\sqrt{L/N}$ for $L\lesssim L_{*}$, since we must have
$N\Delta_{L}\sim\sqrt{NL}\Rightarrow\Delta_{L}\sim\sqrt{L/N}$. The matching
cost is dominated by that from scale $L\sim L_{*}$ (provided
$N/M^{2}>1/N\Leftrightarrow M<N$, where $1/N$ is the nearest-neighbour
distance), which is $\Delta_{L_{*}}\sim 1/M$.

We now turn this intuition into a formal proof. Fix $M\in[\sqrt{N},N]$. Define
$L_{0}\triangleq N/(2M^{2})\leq 1/2$. For any matching $\pi$ between supply
and demand which matches all $N$ demand units, define
$f:[0,1]\to\\{0,1,2,\dots\\}$ as

$f(x)\triangleq\\{\\#\textup{ matched pairs s.t. the members of the pair are
located on opposite sides of }x\\}\,.$

The distance for any individual match may be expressed as

$\int_{0}^{1}\mathbb{I}(\textup{the members of the pair are located on
opposite sides of }x)dx\,.$

and, summing over matched pairs and dividing by $N$, the average matching
distance across all pairs is clearly $(1/N)\int_{0}^{1}f(x)dx$. We now
establish the lower bound

$\displaystyle\mathbb{E}\Big{[}\min_{\pi}\int_{0}^{1}f(x)dx\Big{]}\geq
N/(C_{1}M)\,,$ (32)

and dividing by $N$ on both sides this will immediately imply the desired
lower bound $1/(C_{1}M)$ on the expected average matching distance.

Consider any subinterval $[x,x+L_{0}]$ of length $L_{0}$. The number of demand
units in the subinterval is Binomial$(N,L_{0})$ which has mean
$NL_{0}=N^{2}/(2M^{2})$ and standard deviation $\sqrt{NL_{0}(1-L_{0}}\geq
N/(2M)$. The number of supply units is a Binomial with mean
$N^{2}/(2M^{2})+N/(2M)$ and standard deviation less than
$\sqrt{(N+M)L_{0}(1-L_{0})}\geq N/(2M)$. As a result the excess of demand over
supply in the subinterval (defined as 0 if the demand is weakly less than the
supply) has expected value at least $4N/(C_{1}M)$ for some $C_{1}<\infty$.
(With probability at least $4/C_{1}$, the demand exceeds supply by at least
$N/M$.) All this excess demand must be matched to supply outside the
subinterval under any matching $\pi$ which matches all the demand. Hence
${\textup{E}}\big{[}\min_{\pi}(f(x)+f(x+L_{0}))\big{]}\geq 2N/(C_{1}M)$.
Integrating the left hand side over $x\in[0,1-L_{0}]$, we have

$\displaystyle{\textup{E}}\Big{[}\int_{0}^{1-L_{0}}\min_{\pi}(f(x)+f(x+L_{0}))dx\Big{]}\geq(1-L_{0})4N/(C_{1}M)\geq
2N/(C_{1}M)\,,$ (33)

using $L_{0}\leq 1/2$. Now, the left-hand side is bounded above by

$\displaystyle{\textup{E}}\Big{[}\min_{\pi}\int_{0}^{1-L_{0}}(f(x)+f(x+L_{0}))dx\Big{]}\leq
2\int_{0}^{1}f(x)dx\,.$

Putting the prior inequalities together, we obtain (32) as required, and this
completes the proof.

For $d=2$, the proof of the lower bound of the AKT theorem [1] (we refer to
the version in Talagrand’s book [17, Section 4.6]) extends easily to any
$M<N^{1-\epsilon}$ since all length scales $L$ with $\sqrt{NL^{2}}\gtrsim
ML^{2}\Leftrightarrow L\lesssim\sqrt{N}/M$, which includes scales
$L\in[\sqrt{\log N}/\sqrt{N},N^{\epsilon}/\sqrt{N}]$, contribute
$\Theta(1/\sqrt{N\log N})$ to the lower bound on cost (additively) and there
are at least order $\log_{2}\Big{(}\frac{N^{\epsilon}}{\sqrt{\log
N}}\Big{)}=\Omega(\log N)$ such scales for $M<N^{1-\epsilon}$. (Here we used
that the smallest length scale is $\sqrt{\frac{\log N}{N}}$ and that
consecutive length scales are separated by a factor
$2^{\Theta(1)}=1+\Theta(1)$ from each other in the proof.) For $d=2$ and
$M\in[\epsilon N,N]$, as for $d\geq 3$, the total number of supply units $M+N$
is no more than $2N$, hence the expected distance to the nearest neighbor is
at least $1/(C_{2}\sqrt{N})$ which immediately yields the desired lower bound.
∎

Towards the proof of Theorem 3, we will need the following duality lemma for a
minimum cost rightward perfect matching between two sets of points located in
the unit square. While we will need only weak duality, we provide the full
strong duality version.

######  Lemma .1.

Let $(X_{i})_{i\leq n}$ and $(Y_{j})_{j\leq n}$ be located in $[0,1]^{2}$ such
that it is possible to construct a “rightward” matching, i.e., a permutation
$\pi$ on $(1,2,\dots,n)$ such that the horizontal($x$) coordinate of
$Y_{\pi(i)}$ is strictly larger than the horizontal coordinate of $X_{i}$,
$x(Y_{\pi(i)})>x(X_{i})$ for all $i\leq n$. Denote the set of allowed pairs by
$E\triangleq\\{(i,j):Y_{j}\textup{ is strictly to the right of }X_{i}\\}$, the
set of allowed matchings by $\Pi_{\textup{rt}}\triangleq\\{\pi:(i,\pi(i))\in
E\;\forall i\leq n\\}\neq\emptyset$, and the “vertical distance” between
$X_{i}$ and $Y_{j}$ by
$d^{\textup{v}}(X_{i},Y_{j})\triangleq|y(X_{i})-y(Y_{j})|$ where $y(\cdot)$ is
the vertical coordinate of a point. Then we have

$\inf_{\pi\in\Pi_{\textup{rt}}}\sum_{i\leq
n}d^{\textup{v}}(X_{i},Y_{\pi(i)})=\sup_{f\in{\mathcal{F}}}\sum_{i\leq
n}f(Y_{i})-f(X_{i})\,,$

where ${\mathcal{F}}$ is the set of functions $f$ on $[0,1]^{2}$ satisfying:

  * •

For each $y\in[0,1]$, the function $f(\cdot,y)$ is non-increasing.

  * •

For each $x\in[0,1]$, the function $f(x,\cdot)$ is 1-Lipschitz.

###### Proof.

We start by establishing “weak duality” (LHS $\geq$ RHS). Note that for any
$f\in{\mathcal{F}}$ and any matching $\pi\in\Pi_{\textup{rt}}$, for all $i\leq
n$ we have

$\displaystyle f(Y_{\pi(i)})-f(X_{i})\leq
f(Y_{\pi(i)})-f(x(Y_{\pi(i)}),y(X_{i}))\leq
d^{\textup{v}}(X_{i},Y_{\pi(i)})\,$ (34)

where we used that $f(\cdot,y(X_{i}))$ is non-increasing to get the first
inequality, and that $f(x(Y_{\pi(i)}),\cdot)$ is 1-Lipschitz to get the second
inequality. Summing over $i\leq n$ we get

$\displaystyle\sum_{i\leq n}f(Y_{i})-f(X_{i})=\sum_{i\leq
n}f(Y_{\pi(i)})-f(X_{i})$ $\displaystyle\leq\sum_{i\leq
n}d^{\textup{v}}(X_{i},Y_{\pi(i)})\,.$

Since this holds for any $f\in{\mathcal{F}}$ and any matching
$\pi\in\Pi_{\textup{rt}}$, we have

$\inf_{\pi\in\Pi_{\textup{rt}}}\sum_{i\leq
n}d^{\textup{v}}(X_{i},Y_{\pi(i)})\geq\sup_{f\in{\mathcal{F}}}\sum_{i\leq
n}f(Y_{i})-f(X_{i})\,.$

We now establish the reverse inequality (“strong duality”). We make use of
[17, Proposition 4.3.2] with

$\displaystyle
c_{ij}\triangleq\left\\{\begin{array}[]{ll}d^{\textup{v}}(X_{i},Y_{\pi(i)})&\textup{for
all }(i,j)\in E\\\ \infty&\textup{otherwise}\end{array}\,\right.$

which tells us that there exists a dual optimum $(w_{i})_{i\leq n}$ and
$(w_{j}^{\prime})_{j\leq n}$ such that

$\displaystyle w_{i}+w_{j}^{\prime}\leq d^{\textup{v}}(X_{i},Y_{j})\ \textup{
for all }(i,j)\in E$ (35)

and

$\displaystyle\sum_{i\leq
n}w_{i}+w^{\prime}_{i}=\inf_{\pi\in\Pi_{\textup{rt}}}\sum_{i\leq
n}d^{\textup{v}}(X_{i},Y_{\pi(i)})\,.$ (36)

Define $f:[0,1]^{2}\rightarrow\mathbb{R}$ by

$f(X)\triangleq\max_{j:Y_{j}\in\textup{Rt}(X)}w_{j}^{\prime}-d^{\textup{v}}(X,Y_{j})\quad\textup{
where }\textup{Rt}(X)\triangleq\\{Y:x(Y)>x(X)\\}\,.$

It is easy to check that this $f\in{\mathcal{F}}$. Note that
$w_{j}^{\prime}\leq f(Y_{j})$ by definition and $w_{i}\leq-f(X_{i})$ using the
inequalities (35). It follows that
$\sum_{i}w_{i}+w^{\prime}_{i}\leq\sum_{i}f(Y_{i})-f(X_{i})$. Combining with
(36) we have $\inf_{\pi\in\Pi_{\textup{rt}}}\sum_{i\leq
n}d^{\textup{v}}(X_{i},Y_{\pi(i)})\leq\sum_{i}f(Y_{i})-f(X_{i})$ for this
$f\in{\mathcal{F}}$, which completes the proof. ∎

Our proof of Theorem 3 will draw crucially upon the Ajtai-Komlos-Tusnady [1]
lower bound for two-dimensional static matching, and thus our proof may be
viewed as a formalization of the connection between the fully dynamic model in
1 dimension and the static model in 2 dimensions. Our proof here resembles a
proof of Shor [9, Lemma 1].151515There is an analogy between the quantity $m$
here and the quantity $\sqrt{n\log n}$ there, i.e., $n\sim m^{2}/\log m$. The
“right-matching” constraint in [9, Lemma 1] is analogous to the obvious
constraint in our setting that a demand unit can only match with a supply unit
which arrived previously. The expected cost (“vertical distance”) per match
there is shown to be at least $\sqrt{\log n/n}$ which evaluates to $\log m/m$
as the corresponding lower bound on expected match distance in our setting.,
who establishes a lower bound for average-case online bin packing.

###### Proof of Theorem 3.

Consider a horizon $N=N_{0}=Cm^{2}/\log m$ for some $C$ which we will choose
later. (We will show how to extend to general horizons later.) Suppose we had
perfect foresight regarding the locations of all supply and demand arrivals,
and could choose matches accordingly. (We will show that the claimed lower
bound holds even with this additional information.) This turns our matching
problem into a 2-dimensional static rightward perfect matching problem with
the vertical($y$) axis corresponding to space in the fully dynamic model, and
the horizontal($x$) axis corresponding to scaled time $t/N$ in the fully
dynamic model. The 2-d rightward static matching problem is specified as
follows (parentheses will capture the corresponding features in the fully
dynamic model, towards readability):

  * •

(Total number of supply and demand units) There are $n=N+m-1$ supply units
whose locations we will denote by $(X_{i})_{i\leq n}$, and an equal number of
demand units located at $(Y_{i})_{i\leq n}$, in the unit square.

  * •

(Initial supply inventory) There are $m$ supply units with horizontal
coordinate $x=0$ (i.e., present at time $t=0$), and arbitrary $y$ coordinates
(spatial locations).

  * •

(Demand and supply spatial locations are i.i.d. uniform) All other supply and
demand units have a $y$-coordinate which is drawn i.i.d. uniformly from
$[0,1]$. We will specify their horizontal coordinates next.

  * •

(One demand and one supply unit arrival in each period) One supply unit and
one demand unit are at $x=t/N$ for all $t=1,2,\dots,N-1$. There are no supply
units and $m$ demand units at $x=N/N=1$ (one is the demand unit which arrives
at $t=N$ in the fully dynamic model; the remaining $m-1$ are “dummy” demand
units we introduce for technical convenience so that there are an equal number
of demand and supply units in our static problem).

  * •

(Each demand unit must be matched immediately, hence to a supply unit which
arrived previously) Each demand unit must be matched, to a supply unit with a
strictly smaller $x$-coordinate that the demand unit. (Note that it is
feasible to construct a matching which satisfies this requirement.)

  * •

(Match cost) Each matched pair incurs a cost equal to the absolute difference
between the $y$-coordinates of the demand unit and the supply unit. The goal
is to minimize the total match cost.

We will prove that the expected total (vertical) match cost of any feasible
perfect matching in this model is at least $(\epsilon_{1}/3)\sqrt{n\log
n})\geq(\epsilon_{1}/3)\sqrt{N\log N}$ for some $\epsilon_{1}>0$ and any
$C\geq 36/\epsilon_{1}^{2}$, for large enough $m$. We fix
$C=36/\epsilon_{1}^{2}$. Then the contribution of the $m-1$ dummy demand nodes
to the total cost is bounded above by $m-1\leq\sqrt{(N\log
N)/C})=(\epsilon_{1}/6)\sqrt{N\log N}$, so that we obtain an
$(\epsilon_{1}/6)\sqrt{N\log N}$ lower bound on the expected total cost for
the $N$ actual demand nodes, i.e., an expected average cost per period in the
fully dynamic model of at least $(\epsilon_{1}/6)\sqrt{\log
N/N}\geq(\epsilon_{1}/6)\sqrt{(\log m)^{2}/Cm^{2}}=(\epsilon_{1}^{2}/36)\log
m/m$ for horizon $N=N_{0}=Cm^{2}/\log m$ in the fully dynamic model, for any
matching policy. We will later show how to expect this lower bound to
arbitrary horizon $N\geq m^{2}$.

AKT [1] showed (as captured in our Theorem 1) that for some $\epsilon_{1}>0$,
we have

$\displaystyle{\textup{E}}\bigg{[}\inf_{\tilde{\pi}}\sum_{i\leq
n}d(\tilde{X}_{i},\tilde{Y}_{\tilde{\pi}(i)})\bigg{]}\geq\epsilon_{1}\sqrt{n\log
n}$ (37)

for $(\tilde{X_{i}})_{i\leq n}$ and $(\tilde{Y_{i}})_{i\leq n}$ distributed
i.i.d. uniformly in the unit square. (37) does not directly enable us to prove
the desired lower bound on expected cost because there are some differences
between the distributions of points, the constraints, and the definition of
cost, in the two models. In the AKT model the points $(\tilde{X_{i}})_{i\leq
n}$ and $(\tilde{Y_{i}})_{i\leq n}$ are distributed i.i.d. uniformly in the
unit square, whereas the $x$-coordinates in our case are deterministic (also
the $y$-coordinates of the $m$ supply units at $x=0$ are arbitrary). We have a
rightward matching constraint which is absent in AKT, and our cost is the
vertical distance, whereas AKT consider the Euclidean distance.

The difference in the horizontal distributions of supply (demand) points in
the two models is relatively easy to handle. To move the locations in the AKT
model $(\tilde{X_{i}})_{i\leq n}$ and $(\tilde{Y_{i}})_{i\leq n}$ to the
locations in our model $({X_{i}})_{i\leq n}$ and $({Y_{i}})_{i\leq n}$, we
index the supply (demand) units from left to right in both models, and then
move each AKT supply (demand) unit leftwards or rightwards so that it is
located at the $x$-coordinate of the corresponding supply (demand) unit in our
model. By the central limit theorem, along with $m=\Theta(\sqrt{n\log n})$ and
the fact that the $x$-locations of $({X_{i}})_{i\leq n}$ and $({Y_{i}})_{i\leq
n}$ deviate from even spacing by at most $m/(n+1)$, the expected distance
moved by the $i$-th supply unit in this process, for each $i\leq n$, is
bounded as

$\displaystyle{\textup{E}}[|x(\tilde{X}_{i})-x(X_{i})|]$ $\displaystyle\leq
m/(n+1)+O(1/\sqrt{n})\leq\sqrt{(\log n)/(2Cn)}+O(1/\sqrt{n})$
$\displaystyle\leq\sqrt{\log n/(nC)}$

for large enough $m$, and the same bound holds for the difference in demand
unit locations. In the case of the $m$ initially present supply units, we also
need to move those points vertically (by at most $1$ unit each) to allow for
arbitrary $y$-coordinates in our model, i.e., $|y(\tilde{X}_{i})-y(X_{i})|\leq
1\ \textup{for all }i\leq m\,,$ while all other $y$-coordinates are identical.
It follows that

$\displaystyle{\textup{E}}\bigg{[}\sum_{i\leq
n}d(\tilde{X}_{i},X_{i})\bigg{]}$ $\displaystyle\leq\sqrt{(n\log n)/C}+m\leq
2\sqrt{(n\log n)/C}\quad\textup{and}$ (38)
$\displaystyle{\textup{E}}\bigg{[}\sum_{i\leq
n}d(\tilde{Y}_{i},Y_{i})\bigg{]}$ $\displaystyle\leq\sqrt{(n\log n)/C}\,.$

AKT [1] construct a “witness” dual function with large empirical discrepancy
to establish their lower bound (37). We will transform the AKT dual function
into a function $f$ which is a dual function for our rightward matching
problem, and inherits (with small slack) the AKT lower bound on the empirical
discrepancy.

The (random) dual function $\tilde{f}:[0,1]^{2}\rightarrow\mathbb{R}$
constructed in the lower bound proof of AKT [1] satisfies the following
properties:

  * •

$\tilde{f}$ is 1-Lipschitz.

  * •

Large empirical discrepancy:

$\displaystyle{\textup{E}}\bigg{[}\sum_{i\leq
n}\tilde{f}(\tilde{Y}_{i})-\tilde{f}(\tilde{X}_{i})\bigg{]}\geq\epsilon_{1}\sqrt{n\log
n}\,.$ (39)

Their lower bound (37) then follows since $\tilde{f}$ being 1-Lipschitz
implies that
$d(\tilde{X}_{i},\tilde{Y}_{\tilde{\pi}(i)})\geq\tilde{f}(\tilde{Y}_{\tilde{\pi}(i)})-\tilde{f}(\tilde{X}_{i})$,
which leads to ${\textup{E}}\big{[}\inf_{\tilde{\pi}}\sum_{i\leq
n}d(\tilde{X}_{i},\tilde{Y}_{\tilde{\pi}(i)}\big{]}\geq{\textup{E}}\big{[}\sum_{i\leq
n}\tilde{f}(\tilde{Y}_{i})-\tilde{f}(\tilde{X}_{i})\big{]}\geq\epsilon_{1}\sqrt{n\log
n}$.

We define $f(x,y)\triangleq\tilde{f}(x,y)-x$. Here we subtract $x$ to ensure
that $f(\cdot,y)$ is non-increasing for all $y\in[0,1]$. Since $\tilde{f}$ is
1-Lipschitz in $[0,1]^{2}$, it follows that $f(x,\cdot)$ is 1-Lipschitz for
all $x\in[0,1]$. With these two properties, we know from Lemma .1 that
$f(\cdot)$ is a dual function for our rightward matching problem, and weak
duality tells us that:

$\inf_{\pi\in\Pi_{\textup{rt}}}\sum_{i\leq
n}d^{\textup{v}}(X_{i},Y_{\pi(i)})\geq\sum_{i\leq
n}f(Y_{i})-f(X_{i})=\sum_{i\leq
n}\tilde{f}(Y_{i})-\tilde{f}(X_{i})-x(Y_{i})+x(X_{i})\,.$

By definition of horizontal coordinates in our problem $\sum_{i\leq
n}x(Y_{i})-x(X_{i})=m$. Taking expectations in the previous inequality, we
obtain

$\displaystyle{\textup{E}}\bigg{[}\inf_{\pi\in\Pi_{\textup{rt}}}\sum_{i\leq
n}d^{\textup{v}}(X_{i},Y_{\pi(i)})\bigg{]}\geq-m+{\textup{E}}\bigg{[}\sum_{i\leq
n}\tilde{f}(Y_{i})-\tilde{f}(X_{i})\bigg{]}\,.$ (40)

Now, since $\tilde{f}$ is 1-Lipschitz, we know that
$|\tilde{f}(\tilde{Y}_{i})-\tilde{f}(Y_{i})|\leq d(\tilde{Y}_{i},Y_{i})$ and
$|\tilde{f}(\tilde{X}_{i})-\tilde{f}(X_{i})|\leq d(\tilde{X}_{i},X_{i})$. It
follows that

$\displaystyle\sum_{i\leq n}\tilde{f}(Y_{i})-\tilde{f}(X_{i})\geq\sum_{i\leq
n}\big{(}\tilde{f}(\tilde{Y}_{i})-\tilde{f}(\tilde{X}_{i})\big{)}-\sum_{i\leq
n}d(\tilde{Y}_{i},Y_{i})-\sum_{i\leq n}d(\tilde{X}_{i},X_{i})\,.$

Plugging back into (40) and leveraging (39), (38) and $m\leq\sqrt{(n\log
n)/C}$, we obtain

$\displaystyle{\textup{E}}\bigg{[}\inf_{\pi\in\Pi_{\textup{rt}}}\sum_{i\leq
n}d^{\textup{v}}(X_{i},Y_{\pi(i)})\bigg{]}\geq\epsilon_{1}\sqrt{n\log
n}-4\sqrt{(n\log n)/C}\geq(\epsilon_{1}/3)\sqrt{n\log n}\,,$

where we ensure the second inequality holds by choosing $C\geq
36/\epsilon_{1}^{2}$.

As explained previously, this gives us a lower bound of
$(\epsilon_{1}^{2}/36)\log m/m$ on the expected cost per period in the fully
dynamic model for $N=N_{0}$ and large enough $m$. We can extend to any horizon
$N\geq N_{0}$ by dividing the horizon into epochs of duration $N_{0}$ periods
each. For an epoch of duration $N_{0}$, for arbitrary initial state at the
beginning of the epoch, the aforementioned argument shows that the expected
average cost in the epoch is at least $(\epsilon_{1}^{2}/36)\epsilon\log m/m$
for any matching policy. Even if the last epoch of length $N_{0}$ extends past
period $N$ (because $N$ is not divisible by $N_{0}$) we immediately deduce a
lower bound of $(\epsilon_{1}^{2}/72)\log m/m$ on the expected cost per period
over the horizon $N$, for large enough $m$. A lower bound of $\epsilon\log
m/m$ for arbitrary $N\geq m^{2}$ and $m\geq 2$ follows, for
$\epsilon\in(0,\epsilon_{1}^{2}/72]$ chosen to ensure that the lower bound
holds for all $m\geq 2$. ∎