# Selecting a Match: Exploration vs Decision

Ishan Agarwal New York University. This work was supported in part by NSF
Grant CCF-$1909538$ Richard Cole 11footnotemark: 1 Yixin Tao London School of
Economics. Part of the work done while Yixin Tao was a Ph.D. student at
Courant Institute, NYU. This work was also supported in part by ERC Starting
Grant ScaleOpt-$757481$.

###### Abstract

In a dynamic matching market, such as a marriage or job market, how should
agents balance accepting a proposed match with the cost of continuing their
search? We consider this problem in a discrete setting, in which agents have
cardinal values and finite lifetimes, and proposed matches are random.

We seek to quantify how well the agents can do. We provide upper and lower
bounds on the collective losses of the agents, with a polynomially small
failure probability, where the notion of loss is with respect to a plausible
baseline we define. These bounds are tight up to constant factors.

We highlight two aspects of this work. First, in our model, agents have a
finite time in which to enjoy their matches, namely the minimum of their
remaining lifetime and that of their partner; this implies that unmatched
agents become less desirable over time, and suggests that their decision rules
should change over time. Second, we use a discrete rather than a continuum
model for the population. The discreteness causes variance which induces
localized imbalances in the two sides of the market. One of the main technical
challenges we face is to bound these imbalances.

In addition, we present the results of simulations on moderate-sized problems
for both the discrete and continuum versions. For these size problems, there
are substantial ongoing fluctuations in the discrete setting whereas the
continuum version converges reasonably quickly.

##  1 Introduction

What strategies make sense when deciding whether to commit to a long-term
relationship? We are interested in pairings between members of two sets of
agents, such as an employer offering a job and a worker accepting, a woman (or
man) proposing marriage to a person of the opposite sex,111Single-sex
marriages could also be studied, but then there would be just one set of
agents. In fact, this does not appear to significantly affect our results, but
in this work we have focused on the case of two sets of agents. a landlord
agreeing to rent an apartment to a potential renter.

The key feature of these relationships is that the longer they last, the
greater the utility they provide; for simplicity, we assume this utility is
linear in the duration of the match. Nonetheless, as a rule agents do not
choose to match as soon as they receive a proposal, for different potential
partners may provide different utilities. An employer may be supportive or
not, a marriage may be happy or not; the possibilities are myriad. Agents seek
to assess the utility of a proposed match and then decide whether to accept or
keep searching (such an assessment might be implicit). These judgements can be
based on some combination of idiosyncratic factors and commonly shared
perspectives. Both sides of a potential match are making this assessment, and
a match happens only if both sides accept it.

Assessing potential matches takes time and therefore an agent can consider
only a relatively small number of potential matches at any one time. In many
circumstances, choices are offered on a take it or lose it basis. Typically,
job offers are made with a short decision window. While marriage or its
equivalents have many cultural variations, as a rule offers of marriage when
made are accepted or declined; it would be unusual to collect multiple offers
and only then decide (in the somewhat unlikely event the parties on the other
side would be willing to wait). Again, for simplicity, we assume agents can
consider only one match at a time.

Furthermore, agents are aware of time slipping by. An unemployed worker cannot
afford to stay unemployed indefinitely. Businesses wish to fill open positions
promptly as they need workers to carry out the duties of these open positions.
Many men and women appear to want to pair sooner rather than later (whether
the pairing is called marriage or not). We see two forces at work here: one is
the ongoing utility from a match, which starts only when the match is formed.
The second is that at least in some circumstances partners become less
desirable as they become older.

We are interested in two questions:

What decision rules make sense and how can their effectiveness be measured?

Each potential decision rules provides a balance between the urge to form a
match soon so as to have a longer time in which to enjoy it, and the desire to
continue searching in the hopes of finding a better match.

The equilibrium properties of decision rules have been studied previously in
models with a continuum population, a continuum model for short [Ada03, BC97,
BC99, BW98, Smi06, SS00, BR00, Eec99, LN14, MC90, DLS05]. In these works,
agents are assumed to arrive according to a variety of processes, such as a
Poisson process. In some of these works, they are also assumed to use time
discounting of future utility. Either they have infinite lifetimes in which to
seek matches or they depart—die—according to another process. We discuss this
in more detail in the related work section below. Each agent has an intrinsic
appeal, a numeric value, called _charm_ in Burdett and Coles [BC99]. The
utility an agent derives from a match is assumed to be an increasing function
of their partner’s charm. Agents receive match proposals at a fixed rate and
agents either accept or reject a match immediately; for a match to succeed
both participating agents must agree to it. One natural class of agent
strategies are reservation strategies; an agent will accept a proposed match
exactly if the partner has charm at least $c$. Typically the chosen $c$ is a
function of the agent’s own charm. The right choices of reservations $c$ yield
equilibrium strategies.

In contrast, we study this problem in a discrete, albeit stochastic, setting.
By this we mean that a finite number of agents arrive at each time step; we
also choose time to be discrete. In addition, we model lifetimes differently,
viewing all lives as having duration $T$. This has the effect of making agents
less demanding over time which we believe is a real effect, and an effect that
will not arise with a departure rate that stays the same over time.

Discreteness introduces variance, which leads to localized imbalances in the
numbers of men and women (by localized, we mean agents of a given age and
charm). The analysis and bounding of these imbalances are the largest
challenge we face, and while asymptotically small, for moderate values of our
parameters these are non-trivial quantities, as confirmed by our simulation
results. This is in sharp contrast to a continuum setting, where there will be
no variance. Finally, it is not clear that our setting will converge to an
equilibrium or near-equilibrium, and while our simulations for moderate
parameter values suggest a certain level of stability, they also show that
there is continuing substantial variability. In any event, our concern is to
understand the quality of the outcomes: in a sense we make precise shortly,
our model achieves near-optimal utility with high probability.

##### Roadmap

In section 2 we formally define our setting, and in section 3 we state our
results. Following some preliminaries in section 4, we present our lower bound
in section 5, and outline the construction for our upper bound in section 6.
In section 7 we describe our simulation results and we conclude in section 8
with some additional remarks. Many proofs are deferred to the appendix.

###  1.1 Related Work

Rogerson [RSW05] surveyed issues of search cost and bargaining in job markets.
More recently, Chade, Eeckout and Smith [CES17] gave a broad survey of
matching in economic models, covering search with and without costs, and
settings with and without transferable utility. We focus on settings with
search costs and no transferable utility. Even in this domain there are many
works. We characterize these works w.rt. multiple dimensions.

The first is the treatment of time, both as regards arrivals and departures.
Most papers assume agents remain in the market till they are matched. A few
allow matches to be broken via a Poisson process (e.g., jobs end, partners
divorce) and then the agents return to the market; see Shimer and Smith [SS00]
and Smith [Smi06]. Others have agents ending their participation via various
random processes: Burdett and Wright [BW98] use a Poisson process, Adachi
[Ada03] uses an exponential random variable, and Lauermann and Noldeke [LN14]
use an exogeneous rate. Arrivals are similarly varied. Poisson processes in
Burdett and Coles [BC97], Smith [Smi06], and Shimer and Smith [SS00]. Cloning:
when agents leave due to a match they are replaced by clones thereby keeping
the available matches unchanged; see Adachi [Ada03] and Burdett and Wright
[BW98]. Fixed arrival rates: see Eeckhout [Eec99], and Lauermann and Noldeke
[LN14]. Finally, no new arrivals: see Damiano, Hao and Suen [DLS05], and
McNamara and Collins [MC90].

The second dimension is the choice of utility model. These are all functions
of the partner’s charm, though there is considerable variation. The most
common is that the utility an agent gains is a non-decreasing function, either
linear [BC97] or more general [Smi06, Eec99]; some papers allow for time
discounting [Ada03, BR00]; the utility can be the product of the partners’
charms [DLS05]; or it is given by independent random variables for each pair
of agents [BW98, MC90]; another option is that the agents obtain their utility
by dividing a reward which is a function of their individual charms [SS00].

The final dimension is the choice of equilibrium model. Most of the papers
consider a steady state equilibrium; McNamara and Collins [MC90] consider Nash
Equilibria, and Damiano, Hao and Suen [DLS05] analyze a multi-round dynamic
equilibrium.

The tension between taking a choice now and waiting for potentially better
options arises in multiple other domains, including secretary problems[Fer89],
online matching[KVV90], matching market thickening [ALG20, BLY20], and regret
minimization [BM07]. In spirit, the secretary problem seems the most analogous
as it involves a single decision, albeit by just a single agent. We discuss it
briefly in the next paragraph. In contrast, online matching has a centralized
decision maker that seeks to optimize the outcome of many choices. Regret
minimization occurs in a distributed setting, however here each agent makes
multiple decisions over time, with the goal of achieving a cumulatively good
outcome; again, this seems quite distinct from our setting. Market thickening
is used in contexts where a global matching is being computed, which seem
unlike the random matches on offer in our setting.

The standard secretary problem is expressed in terms of ranks. A cardinal
version was considered by Bearden [Bea06]; here the goal is to maximize the
expected value of the chosen secretary, with values uniform on $[0,1]$. For
each applicant the decision maker learns whether they are the best so far.
Bearden shows the optimal strategy is to reject the first $\sqrt{n}-1$
candidates, and then choose the first candidate who meets the “best so far”
criteria. Clearly, the expected value of the selected secretary is
$1-\Theta(1/\sqrt{n})$, which is analogous to the bounds we obtain, although
the settings appear quite distinct. Bearden argued that the payoff rule in
this version of the problem is more natural that the classic version. The
problem of maximizing the duration of a relatively best choice has also been
considered [Fer89].

##  2 The Model

We consider a setting in which, at each time step, $n$ agents enter a matching
pool. Agents exit the pool either when they are matched or if they have been
in the pool for $T$ time steps. There are two types of agents, called men and
women. Each match pairs a man with a women. At each time step the agents are
paired uniformly at random. Each pair comprises a proposed match. Each agent
in a pair can accept or reject the proposed match as they prefer; a match
occurs only if both agents accept it.

In a discrete setting, a random pairing seems more natural than having pairs
arrive one by one, for the process of pairing will proceed in parallel, and
pairs are necessarily mutually exclusive. While in practice the pairings under
consideration at any one time will not cover the whole of the smaller side of
the population, considering a maximal matching seems a reasonable
simplification.

We assume agents evaluate their potential partners using cardinal values, and
furthermore these are common values: every agent of the opposite type (gender)
has the same value $v_{i}$ for agent $i$. In the terminology of Burdett and
Coles, this is agent $i$’s charm.

We associate two parameters $v_{i}$ and $t_{i}$ with agent $i$. $v_{i}$ is the
agent’s charm and $t_{i}$ is the total time remaining before agent $i$ is
forced to exit the pool. Agent $i$ derives utility
$v_{j}\cdot\min(t_{i},t_{j})$ when matched with agent $j$. We assume that the
values lie in the range $[T,2T)$, and that an agent’s value, chosen when it
enters the pool, is one of $\\{T,T+1,\ldots,2T-1\\}$, picked uniformly at
random. We note that the relative utilities of an agent are scale free; in
other words, the range assumption is equivalent to assuming the values lie in
the range $[1,2]$. We could have used a separate discretization for the
values, but we preferred to avoid an additional parameter. Furthermore, it
would not affect the results qualitatively.

Entering agents are either male or female with equal probability.

Throughout this work it will be useful to view the market as a $T\times T$
size box, with agents located at grid points. The box is indexed by value on
the horizontal axis and by time on the vertical axis. Consider the set of $T$
points on the top edge: $\\{(T,0),(T+1,0),\ldots,(2T-1,0)\\}$. Agents enter
the market at one of these points, picked uniformly at random. At each time
step, an agent either matches and leaves the box or moves down vertically by
$1$ unit. After $T$ steps, if unmatched for all these times, the agent exits
the box (at the bottom).

##### A Reasonable Notion of Loss

In a single gender version of this setting, the total utility derived by the
$n$ agents that enter at any one time step is at most
$n\cdot\sum_{i}v_{i}\cdot T$; in the two-gender case, by applying a Chernoff
bound, one can obtain a similar bound with high probability. This bound can
easily be achieved if all agents simply accept whatever match is proposed to
them in the very first step in which they enter the matching pool. However
such behavior seems implausible for high value agents, as their expected
utility would be much smaller than what they might reasonably hope to achieve.
Consequently, we set $v_{i}\cdot T$ as a reasonable target for $i$’s achieved
utility. Based on this, we define the _total loss_ suffered by the agents to
be:

$\sum_{\begin{subarray}{c}i\in\\{\text{agents obtaining utility}\\\
~{}~{}~{}~{}~{}~{}~{}\text{less than their worth}\\}\end{subarray}}v_{i}\cdot
T-\text{utility obtained by agent }i.$

This measure captures the intuition that agents who obtain less than their
worth due either to a lower value partner, or to accepting a match only later
on in the process, are suffering losses. We want to capture how much utility
is lost compared to the benchmark in which each agent gets an equal value
partner for the whole length $T$ time period. It also addresses what is
implausible about the naive solution, in which all agents immediately accept
whatever match is proposed to them, and which maximizes the usual notion of
social welfare.

It is not clear how to determine an optimal strategy, let alone whether it can
be computed feasibly. For a truly optimal strategy would incorporate the
effects of past variance, a level of knowledge that seems implausible in
practice; and even an ex-ante optimal strategy seems out of reach. Instead, we
will present a strategy, which we call the _reasonable strategy_ , which seeks
to ensure that if it is followed by all the players, then the total loss will
be at most a constant factor larger than what could be achieved by the optimal
strategy. Actually, we introduce two strategies, and the second one, called
the _modified reasonable strategy_ , is the one we analyze.

##  3 Results

We obtain a lower bound on the total loss suffered by agents; no matter their
behavior, they will, with high probability, suffer an average loss of
$\Omega(T\sqrt{T})$.

######  Theorem 3.1.

Suppose the matching market runs for $\tau$ time steps. If $16\leq T+1\leq
n,c\geq 1,T\leq\tau\leq n^{c}$, and $n\geq 96T(2c+2)\ln n$, then, over $\tau$
time steps, whatever strategies the agents use, with probability at least
$1-\frac{1}{4n^{c}}$, the average loss per agent is at least
$\frac{T\sqrt{T}}{20}$.

On the other hand, we construct a strategy profile, which if followed by all
the agents, leads, with high probability, to a total loss of at most
$\mathrm{O}(T\sqrt{T})$.

######  Theorem 3.2.

Suppose $2T\leq\tau\leq n^{c}$, $c\geq 1$, $676\leq T$, and
$n\geq(3654+2436e^{12}+546(e^{12}+1)c)^{2}(3c+4)T^{3}(\log_{2}n)^{2}\ln n.$
Then, over $\tau$ time steps, if all agents follow the modified reasonable
strategy, with probability at least $1-\frac{1}{n^{c}}$, the average loss per
agent is at most $11T\sqrt{T}$.

Our results hold for large $n$ and $T$. Furthermore, Theorem 3.2 applies only
when $n$ is much larger than $T$. However, our numerical simulations suggest
that similar results hold even for quite moderate values of $n$ and $T$ and
also do not require $n$ to be much bigger than $T$. To simplify the
presentation, we assume that $T=4^{i}$ for some integer $i>0$, though the
bounds extend to all values of $T$, possibly with somewhat larger constants.

##  4 Preliminaries

We review the notion of negative cylinder dependence and make a simple
observation regarding the matching procedure.

######  Lemma 4.1.

Suppose there are $m$ men and $w$ women in total. Further suppose that for a
given man $x$, there are $w^{\prime}$ women for which a proposed match would
be accepted by both sides. Then a random match will provide man $x$ such a
match with probability $w^{\prime}/\max\\{m,w\\}$.

###### Proof.

If there are at least as many women as men, every man will be offered a match,
and the probability that it is accepted by both sides is $w^{\prime}/w$. While
if there are more men, a man will be offered a match with probability $w/m$,
and thus the probability that he is offered an acceptable match is $w/m\cdot
w^{\prime}/w=w^{\prime}/m$. ∎

##### Negative Dependence

Consider a set of $0$-$1$ valued valued random variables
$\\{X_{i}\\}_{i=1}^{n}$. The set $\\{X_{i}\\}$ is $\lambda$-_correlated_ if

$\displaystyle
E\Big{[}\prod_{i=1}^{n}X_{i}\Big{]}\leq\lambda\cdot\prod_{i=1}^{n}E\Big{[}X_{i}\Big{]},$

where $\lambda\geq 1$. The set $\\{X_{i}\\}$ is _negative cylinder dependent_
if $\\{X_{i}\\}$ and $\\{1-X_{i}\\}$ are both $1-$correlated. In our arguments
we will apply Chernoff-like bounds to negative cylinder dependent variables.
We will use the following lemmas; their proofs are deferred to Appendix A.

######  Lemma 4.2.

Let $S_{m}$ and $S_{w}$ be two sets of $N_{1}$ and $N_{2}$ agents
respectively, Suppose that $N_{1}\leq N_{2}$. Let
$S_{a}=\\{a_{1},a_{2},\ldots,a_{n}\\}\subseteq S_{m}$ and
$S_{b}=\\{b_{1},b_{2},\ldots,b_{r}\\}\subseteq S_{w}$. Consider a matching
between $S_{m}$ and $S_{w}$ chosen uniformly at random. Let $X_{i}$ be an
indicator variable which equals $1$ if agent $a_{i}$ is paired with an agent
in $S_{b}$, and $0$ otherwise. Then the set $\\{X_{i}\\}$ is negative cylinder
dependent and for any $\delta>0$,

$\displaystyle\operatorname{Pr}\left[\sum X_{i}\geq(1+\delta)\mu\right]\leq
e^{-\frac{\delta^{2}\mu}{3}}\text{~{}~{}and~{}~{}}\operatorname{Pr}\left[\sum
X_{i}\leq(1-\delta)\mu\right]\leq e^{-\frac{\delta^{2}\mu}{2}}.$

######  Lemma 4.3.

If $\\{X_{i}\\}_{i=1}^{n}$ are $1$-correlated random variables taking value
$\\{0,1\\}$ and $\overline{\mu}$ is an upper bound on $\mu=E[\sum X_{i}]$,
then, for any $\delta>0$,

$\displaystyle\operatorname{Pr}\left[\sum
X_{i}\geq(1+\delta)\overline{\mu}\right]\leq
e^{-\frac{\delta^{2}\overline{\mu}}{3}}\text{~{}~{}and~{}~{}}\operatorname{Pr}\left[\sum
X_{i}\leq\mu-\delta\overline{\mu}\right]\leq
e^{-\frac{\delta^{2}\overline{\mu}}{2}}.$

##  5 Lower Bound on the Loss for Any Strategy

The intuition for this result is fairly simple. If an agent remains unmatched
for $\sqrt{T}$ steps, then any subsequent proposed match would cause a loss of
at least $\sqrt{T}$ to one of the participating agents. Thus to avoid having
average losses of $\Omega(\sqrt{T})$, most matches would need to occur during
an agent’s first $\sqrt{T}$ steps.

But we will show that for at least a constant fraction of the agents, the
matches they are offered during their first $\sqrt{T}$ steps will all have the
property that the values of the two agents differ by at least $\sqrt{T}$, and
consequently one of the participating agents would suffer a $\sqrt{T}$ loss.
The overall result follows.

This second claim is not immediate because the probability that an agent is
offered a close-in-value match might vary significantly from agent to agent
and over time.

We somewhat optimize constants and consequently consider a period of time
$w=\Theta(\sqrt{T})$ and value differences $w$, instead of precisely the value
$\sqrt{T}$ used in the above outline.

###### Proof.

(Of Theorem 3.1) We divide the grid into width $w$ columns, where a column
includes the low-value side boundary, but not the high-value boundary; one end
column may be narrower. We will set the parameter $w$ later.

We consider the set of proposed matches at some arbitrary time $t$. We say a
proposed match is _safe_ if the paired agents are in the same or adjacent
columns. We also define the male match rate $p_{i}$ for column $i$ to be the
probability that a man in the column has a safe match. By Lemma 4.1, this is
at most the number of women in columns $i-1$, $i$, and $i+1$ divided by the
maximum of the total number of women and the total number of men, which is at
most the number of women in these columns divided by the total number of
women. Clearly the sum of the male match rates over all the columns is at most
$3$. The same claim holds for the analogous female match rates.

Consider the men entering the system at time $t$, which we call the _new_ men.
Each column contains at most $w$ points at which agents enter the market,
namely the points along the column’s top edge, and each entering agent is
equally likely to be a man or a woman. By applying a Chernoff bound, we see
that for any given column $i$,

$\operatorname{Pr}\Big{[}\text{\\# of new men in column $i$ at time
$t$}\geq\frac{(1+\delta)nw}{2T}\Big{]}\leq e^{-\delta^{2}nw/6T}.$

Applying this bound to every column over $\tau$ consecutive time steps yields:

$\displaystyle\operatorname{Pr}\Big{[}\text{every column receives at most
}\frac{(1+\delta)nw}{2T}\text{ new men}$ $\displaystyle\hskip
108.405pt\text{for each of $\tau$ consecutive time
steps}\Big{]}\geq\Big{(}1-e^{-\delta^{2}nw/6T}\Big{)}^{\tau T/w}.$

Call this event $\mathcal{E}$. Henceforth we condition on $\mathcal{E}$.

Now suppose that every time an agent was offered a safe match, they accepted
it. Recall that $p_{i}$ is the match rate for column $i$. By Lemma 4.2, for
the new men at time $t$ in column $i$, for any $t$,

$\operatorname{Pr}\Big{[}\text{\\# safely matched men
}\leq\frac{(1+\delta)nwp_{i}}{2T}\Big{]}\geq 1-e^{-\delta^{2}nwp_{i}/6T}.$

In fact, agents may not accept every proposed safe match; but this only
reduces the number of agents safely matched, and therefore the bound on the
probability continues to hold.

Furthermore, by Lemma 4.3, letting
$\overline{\mu}=\frac{nw\max\\{p_{i},\frac{w}{T}\\}}{2T}$, gives

$\displaystyle\operatorname{Pr}\Big{[}\text{number of safely matched men
}\leq\frac{(1+\delta)nw\max\\{p_{i},\frac{w}{T}\\}}{2T}\Big{]}\geq
1-e^{-\frac{\delta^{2}nw\max\\{p_{i},\frac{w}{T}\\}}{6T}}\geq
1-e^{-\frac{\delta^{2}nw^{2}}{6T^{2}}}.$

Recalling that $\sum_{i}p_{i}\leq 3$, and applying a union bound over all
$T/w$ strips for $w$ successive steps, we obtain, for any given set of new men
entering at some time $t$, over their first $w$ time steps,

$\displaystyle\operatorname{Pr}\Big{[}\text{\\# of safely matched
men}\leq\frac{2(1+\delta)nw^{2}}{T}\Big{]}\geq
1-\frac{T}{w}we^{-\delta^{2}nw^{2}/6T^{2}}.$ (1)

In addition, for any given set of new men, on applying a Chernoff bound, we
know that

$\displaystyle\operatorname{Pr}\Big{[}\text{\\# of new
men}\geq\frac{n(1-\epsilon)}{2}\Big{]}\geq 1-e^{-\epsilon^{2}n/4}.$ (2)

For each remaining man in each of the first $\tau-w$ sets of new men—of which
there are at least
$(\tau-w)\big{(}\frac{n(1-\epsilon)}{2}-\frac{2(1+\delta)nw^{2}}{T}\big{)}$—
one of the following two cases must apply.

  * •

He has not been matched after spending $w$ time in the system. Now, if and
when he is matched, the only way he can avoid suffering a $wT$ loss is to
match with a sufficiently higher value woman. In this case the higher value
woman suffers at least a $wT$ loss.

  * •

He has been matched within $w$ time but it was not a safe match. In such a
match whichever agent had the higher value suffered at least a $wT$ loss.

Since the system runs for $\tau$ time steps, this argument can be applied to
all agents except those that enter the system during the last $w$ time steps.
We deduce that the total loss generated by all these agents is at least
$(\tau-w)(\frac{n(1-\epsilon)}{2}-\frac{2(1+\delta)nw^{2}}{T})\cdot wT$.

Note that this loss is being shared by up to $n\tau$ agents. Hence there is an
average loss of at least
$\frac{1}{2}\big{(}wT(1-\epsilon)-\frac{4(1+\delta)w^{3}T}{T}\big{)}\cdot\frac{\tau-w}{\tau}.$
Setting $w=\frac{\sqrt{T}}{4}$, and using the lower bound on $\tau$ ($\tau\geq
T$), we obtain:

$\text{average loss per
agent}\geq\frac{1}{2}\Big{(}\frac{T\sqrt{T}(1-\epsilon)}{4}-\frac{T\sqrt{T}(1+\delta)}{16}\Big{)}\cdot\Big{(}1-\frac{\sqrt{T}}{4T}\Big{)}.$

Now we set $\delta=\sqrt{\frac{6T^{2}}{nw^{2}}\ln(3n^{c}T\tau)}$ and
$\epsilon=\sqrt{\frac{4}{n}\ln(3\tau n^{c})}$. We would like to have
$\delta\leq 1$, which we enforce by our choice of constraints on $n,T,\tau$
and $c$ (namely $16\leq T\leq n,c\geq 1,T\leq\tau\leq n^{c}$ and $n\geq
96T(2c+2)\ln n$). These constraints also ensure that $\epsilon\leq 1/16$.
Substituting $\delta\leq 1$ and $\epsilon\leq 1/16$ yields:

$\text{average loss per
agent}\geq\frac{7T\sqrt{T}}{128}\cdot\frac{15}{16}\geq\frac{T\sqrt{T}}{20}.$

By (1) and (2), this bound holds with probability at least

$\displaystyle\operatorname{Pr}[{\mathcal{E}}]\cdot\Big{(}1-\tau
Te^{-\frac{\delta^{2}nw^{2}}{6T^{2}}}-\tau
e^{-\frac{\epsilon^{2}n}{4}}\Big{)}$
$\displaystyle\geq\Big{(}1-\frac{1}{n^{c}}\Big{)}.$

The detailed calculation can be found in Appendix B. ∎

##  6 Upper Bound on the Loss when Using the Modified Reasonable Strategy

The lower bound suggests that plausible agent strategies will yield a constant
probability of matching every $\sqrt{T}$ steps. This would imply that the
number of agents present decreases geometrically with agent age; more
precisely, there would be a constant factor decrease for every $\sqrt{T}$
increment in age. Then, in order to maintain match probabilities, all agents
would have to be willing to match with young agents who will accept them. In
fact, the decreases we just described are far from uniform, which makes the
analysis quite non-trivial. Nonetheless, the above intuition informed the
design of the following agent strategies. The first strategy, which we call “a
reasonably good strategy” seems quite natural, but for ease of analysis we
consider a modified strategy which we prove to be asymptotically within a
constant factor of optimal.

We define the _worth_ of an agent to be $v_{i}\cdot(T-t_{i})$; this is the
maximum utility its partner could derive from a match with this agent. Note
that the worth of an agent decreases as it ages.

##### A Reasonably Good Strategy

In this strategy an agent accepts a proposed match if it gives the agent
utility at least
$v_{i}\cdot(T-t_{i})\cdot(1-\frac{1}{\sqrt{T}}-\frac{t_{i}}{T})$. The terms
$1/\sqrt{T}$ and $t_{i}/T$ are present to approximately balance the expected
loss of utility from not matching in a single step with the marginal gain in
utility agent $i$ could receive from being more demanding in terms of the
minimum worth it will accept in a partner.

##### The Modified Reasonable Strategy

We partition the $T\times T$ size space into the regions defined below, as
shown in Figure 1. In the modified strategy, an agent accepts a proposed match
exactly if the proposed partner lies in the same region. This partition uses
regions of two kinds, which we call _strips_.

  * •

Type $1$ strips: these are strips that have new people entering the strip at
the top. The $i$-th Type $1$ strip is defined as the region between the
parallel lines $v=2(t-1)+T+(i-1)\sqrt{T}$ and $v=2(t-1)+T+i\sqrt{T}$; they
have $\sqrt{T}$ width and $\sqrt{T}/2$ height. Points on the first (left) line
are included in the strip, but points on the second (right) line are excluded.
There are $\sqrt{T}$ Type $1$ strips.

  * •

_Type $2$ strips_: these strips do not touch the top boundary of the box. The
strips are again defined by parallel lines. They have successive heights
$\sqrt{T}$, $\sqrt{T}$, $2\sqrt{T}$, and then repeatedly doubling up to $T/2$.
Here the points on the first (upper) line are excluded from the strip and the
points on the second (lower) line are included in the strip. There are
$\log_{2}\sqrt{T}+1$ Type $2$ strips.

Figure 1: The two types of strips used to partition the matching pool.

We note that with the previously stated reasonable strategy, agents would be
willing to match with some agents outside their strip and would reject some
agents in the same strip. However, using the modified strategy simplifies the
analysis, for if all agents use the modified strategy, agents will definitely
get accepted when they accept a match. We will prove that the modified
strategy is not much worse than the optimal strategy in terms of the average
loss of value suffered by an agent.

##### Outline of the proof of the upper bound

Our analysis assumes the following constraints on $n$ and $T$.

$\displaystyle\begin{array}[]{l}c\geq 1,\\\ T\geq 676,\\\
n\geq(3654+2436e^{12}+546(e^{12}+1)c)^{2}(3c+4)T^{3}(\log_{2}n)^{2}\ln
n.\end{array}$ (6)

The result follows from a high-probability inductive bound on the overall
population, the strip populations, and the male-female imbalances in each
strip. We start at time $t=0$. Time $t$ will refer to the moment after the new
agents have entered in this step, but before the match occurs.

######  Lemma 6.1.

Let $N$ denote the total number of strips. Suppose that the constraints in (6)
hold. Then, with probability at least $1-1/n^{c}$, the following inductive
hypothesis $H(t)$ holds at the start of every time step $t$, immediately
following the entry of the new agents at time $t$, for $\sqrt{T}\leq t\leq
n^{c}$.

  1. 1.

The total population is at most $\frac{3}{2}nN+n$.

  2. 2.

The population of every Type $1$ strip is at most $2.6n$.

  3. 3.

The population of every Type $2$ strip is at most
$\frac{7.5n\sqrt{T}}{\text{maximum height of the strip}}$.

  4. 4.

The population in the bottommost Type $2$ strip is no more than
$60n/\sqrt{T}$.

  5. 5.

In every strip $s$, except possibly the bottommost Type 2 strip, the
imbalance, $\operatorname{Imb}(s,t)=\big{|}\text{the number of men in
$s$}-\text{the number of women in $s$}\big{|}\leq n/25\sqrt{T}$.

###### Proof.

(Sketch.) We will show in Theorems 6.3 and 6.4–6.7 that each of the above five
clauses holds with high probability. The last of these results also requires a
high-probability lower bound, Theorem 6.2, on the population size in the same
time range. In addition, in Theorem 6.8, we show that, with high probability,
the inductive hypothesis is true initially. Summing the failure probabilities
prove the lemma. This calculation can be found in Appendix C.6. ∎

With this result in hand we can upper bound the average agent loss.

###  6.1 The Theorems and Proof Sketches

Let $\widetilde{\mathcal{E}}$ be the event that the inductive hypothesis
$H(t)$ holds at the start of time step $t$ immediately following the arrival
of the new agents in this step, for $\sqrt{T}\leq t\leq n^{c}$.

####  6.1.1 Bounding the loss

We first bound an individual agent’s loss based on its match time. We then
obtain an overall bound on the loss. As argued below, Theorem 3.2 follows
immediately.

######  Lemma 6.2.

In the modified reasonable strategy, if an agent with value $v$ matches at
time $t$, its utility loss is at most $4Tt+2t\sqrt{T}$.

This result follows by a simple calculation based on the strip geometry. The
proof is in Appendix C.1.

######  Theorem 6.1.

Suppose the constraints in (6) hold. Also, suppose that all agents follow the
modified reasonable strategy. In addition, suppose the system runs for
$\tau\geq 2T$ time steps, where $\tau\leq n^{c}$. Then the average loss per
departing agent over these $\tau$ steps will be at most $11T\sqrt{T}$.

###### Proof.

Consider the first $\tau$ time steps of the matching process. Let $n_{i}$
denote the number of agents who match and thereby leave the pool at age $i$
during these $\tau$ steps. By Lemma 6.2, each such agent suffers a loss of at
most $4Ti+2T\sqrt{T}$. Thus the total loss is bounded by:

$\displaystyle\text{Total loss}\leq\sum_{i=0}^{T-1}\left(4Ti\cdot
n_{i}+2T\sqrt{T}\cdot n_{i}\right).$

Each agent who is matched at age $i$ is present in the matching pool for $i+1$
steps. By clause 1 of the inductive hypothesis in Lemma 6.1, at each time
during this period, the population of the matching pool is at most
$\frac{3}{2}nN+n\leq\frac{3}{2}n(\sqrt{T}+\log_{2}\sqrt{T}+1)+n\leq
2n\sqrt{T}$, where the last inequality follows from $\sqrt{T}\leq 26$ due to
constraint (6). Thus,

$\displaystyle\sum_{i=0}^{\tau-1}(i+1)n_{i}\leq 2n\sqrt{T}\cdot\tau.$

Therefore,

$\displaystyle\text{Total loss}\leq
8nT\sqrt{T}\cdot\tau+\sum_{i=0}^{T-1}2T(\sqrt{T}-2)\cdot n_{i}.$

Let $D\triangleq\sum_{i=0}^{\tau-1}n_{i}$, the number of agents that leave
during the first $\tau$ steps. We observe that $D$ is at most $n\tau$, the
number of agents that entered during this period. Also, as the population of
the pool at any time is at most $2n\sqrt{T}$, we see that $D\geq
n\tau-2n\sqrt{T}$. By assumption, $\tau\geq 2T$ and $\sqrt{T}\geq 26$, so

$\displaystyle\frac{12}{13}n\tau\leq D\leq n\tau.$

This yields the following bound on the total loss:

$\displaystyle\text{Total loss}\leq 8n\tau T\sqrt{T}+2n\tau T\sqrt{T}\leq
10n\tau T\sqrt{T}.$

And therefore,

$\displaystyle\text{Average loss per agent}=\frac{\text{Total
loss}}{D}\leq\frac{10nT\tau\sqrt{T}}{\frac{12}{13}n\tau}<11T\sqrt{T}.$

∎

###### Proof.

(Of Theorem 3.2) This follows immediately from Lemma 6.1 and Theorem 6.1. ∎

####  6.1.2 Total Size Lower Bound

######  Theorem 6.2.

Suppose $H(t)$ and the constraints in (6) hold. If all agents follow the
modified reasonable strategy, then with probability at least $1-1/n^{2c+1}$,
for every time $t\in[\sqrt{T},n^{c}]$, the population in the matching pool is
at least $\frac{1}{3}n\sqrt{T}$.

###### Proof.

(Idea.) We consider only the new agents that entered the matching pool over
the last $\sqrt{T}$ time steps. We then bound how many of these agents could
have been matched in this time period. Suppose that at any particular time
step $t$, the match rate experienced by the men in strip $i$ is $p_{i}$. The
critical observation is that the sum of the $p_{i}$ is at most $1$. The same
is true for the women. This allows us to prove that even if we could set the
match rates in an adversarial manner, only about $n/\sqrt{T}$ of the agents
that entered at any one time could be matched in any single time step (in the
discussion here, we neglect the effects of variance). This allows us to show
that, of the agents we consider, only about
$\sum_{i=1}^{\sqrt{T}}in/\sqrt{T}\approx n\sqrt{T}/2$ could have been matched
over the last $\sqrt{T}$ time steps. This provides a lower bound on the total
size of roughly $n\sqrt{T}/2$. Accounting for the variance that can occur when
achieving a high probability bound causes the bound on the number of matches
to degrade to $n\sqrt{T}/3$. The full proof can be found in Appendix C.2. ∎

####  6.1.3 Population Upper Bound

######  Theorem 6.3.

Suppose $H(t)$ and the constraints in (6) hold. If all agents follow the
modified reasonable strategy, then at the start of time step $t+1$, with
probability at least $1-1/n^{2c+1}$, the total population of the matching pool
will be at most $(3/2)nN+n$, where $N$ is the total number of strips.

###### Proof.

(Idea.) We seek to lower bound the number of matches in one time step. If it
exceeds the number of incoming agents, then the total population reduces. The
expected number of matches is minimized when the strip populations are equal,
and on applying Lemma 4.1, this yields the following lower bound on the number
of matched women (or men): $[N\cdot(P/2N)^{2}/(P/2)]=P/(2N)$, where $P$ is the
upper bound on the population. This yields the condition $P/N\leq n$, or
$P\leq nN$. The argument is completed by taking account of the deviations
needed to ensure a high-probability bound. The full proof can be found in
Appendix C.3. ∎

####  6.1.4 Upper Bound on the Size of a Strip.

We begin with a technical lemma.

######  Lemma 6.3.

Let $s$ be a strip, and let $S$ be an arbitrary subset of the men and women in
$s$. Let $m$ be the number of men and $w$ be the number of women in $S$. In
addition, let $X$ be the imbalance for the whole of $s$. Then the expected
number of people in $S$ that are matched in a single step is at least

$\displaystyle\frac{\frac{(m+w)^{2}}{2}-\frac{X^{2}}{2}}{\max\\{\text{\\# of
men, \\# of women}\\}\text{ in the whole population }}$

###### Proof.

We need only consider the case that $|X|\leq m+w$. 222Otherwise, the bound is
negative. Let $m_{t}$ denote the total number of men in this strip and $w_{t}$
the total number of women. In addition, let $\Delta\triangleq m-w$,
$P\triangleq m+w$, $Q\triangleq m_{t}+w_{t}$ and $X=m_{t}-w_{t}$. Then,
$m=\frac{P+\Delta}{2}$, $w=\frac{P-\Delta}{2}$, $m_{t}=\frac{Q+X}{2}$ and
$w_{t}=\frac{Q-X}{2}$. The expected number of people matched in this subset of
men and women is

$\displaystyle\frac{mw_{t}+m_{t}w}{\max\\{\text{\\# of men, \\# of
women}\\}\text{ in the whole population }}.$

We now focus on the numerator:
$mw_{t}+m_{t}w=(PQ-X\Delta)/2=(P^{2}+P(Q-P)-X^{2}-X(\Delta-X))/2$. In order to
show this is larger than $\frac{P^{2}}{2}-\frac{X^{2}}{2}$, it suffices to
show $P(Q-P)\geq X(\Delta-X)$.

As $m_{t}\geq m$ and $w_{t}\geq w$, $Q-P\geq\Delta-X$ and $Q-P\geq X-\Delta$.
Recall that it suffices to consider the case $|X|\leq m+w=P$. Combining these
two inequalities yields $P(Q-P)\geq X(\Delta-X)$, which proves the result. ∎

Next, we give an upper bound on the size of a Type $1$ strip.

######  Theorem 6.4.

Suppose $H(t)$ and the constraints in (6) hold. If all agents follow the
modified reasonable strategy, then at time $t+1$, right after the new agents
have entered, with probability $>1-\frac{1}{n^{2c+1}}$, each Type $1$ strip
will continue to have population at most $dn$, where $d=2.6$.

###### Proof.

(Sketch). Consider a strip $s^{\prime}$ and its successor strip $s$ (the strip
immediately to its left). We will follow the collection of agents occupying
$\sqrt{T}$ adjacent diagonals over $\sqrt{T}$ steps, beginning with the at
most $dn$ agents in strip $s^{\prime}$ and ending in strip $s$, with the
remainder of these agents plus any new agents who have entered these
diagonals. The heart of our proof is to show that in a single step we maintain
the $dn$ bound on the number of agents in this collection of advancing
diagonals. The basic idea is straightforward: we compute a lower bound on the
expected number of matches using Lemma 6.3 taking into account the maximum
possibly imbalance, add the incoming agents and correct for variance. One more
important detail is that the expected number of matches is minimized if, in
the collection of agents we are tracking, half are in strip $s$ and half are
in $s^{\prime}$; so this is the value we use in these calculations. The actual
proof can be found in Appendix C.4. ∎

######  Theorem 6.5.

Suppose $H(t)$ and the constraints in (6) hold. If all agents follow the
modified reasonable strategy, then at time $t+1$, right after the new agents
have entered, with probability $>1-\frac{1}{n^{2c+1}}$, each Type $2$ strip
(apart from the bottommost one) will continue to have population at most
$\frac{\textnormal{{g}}n\sqrt{T}}{\text{height of the strip}}$ where
$\textnormal{{g}}=7.5$.

###### Proof.

(Idea.) For the topmost Type 2 strip $s$ we obtain a bound of $2\cdot
2.6n=5.2n\sqrt{T}/\sqrt{T}$, as the items in $s$ are obtained from its
predecessor strip over the previous $\sqrt{T}$ steps, i.e. the sum of the
contents at times $\sqrt{T}/2$ and $\sqrt{T}$ earlier. The same bound applies
to the second Type 2 strip. Each subsequent Type 2 strip $s$ has twice the
height of its predecessor. Let $s$ have height $H$. The contents of $s$ come
from its predecessor over a period of length $H$, which by the inductive
hypothesis contain at most
$2\textnormal{{g}}n\sqrt{T}/(H/2)=4\textnormal{{g}}n\sqrt{T}/H$ agents. To
prove our bound, we need to show at least $3\textnormal{{g}}n\sqrt{T}/H$ of
them are removed during these $H$ steps. Again, as in Theorem 6.4, we seek to
track a population as it moves from $s^{\prime}$ to $s$. The challenge is that
in the analysis this population shrinks over time and the match rate is
proportional to the square of this population. To get a fairly tight bound, we
formulate this as a differential expression and determine the smallest value
for the constant g that enables this number of matches. The full proof can be
found in Appendix C.5. ∎

######  Theorem 6.6.

Suppose $H(t)$ and the constraints in (6) hold. If all agents follow the
modified reasonable strategy, then at time $t+1$, right after the new agents
have entered, the strip population for the bottommost Type $2$ strip will
continue to be at most $\frac{60n}{\sqrt{T}}$.

This simple calculation is deferred to Appendix C.5.

####  6.1.5 Bound on Imbalance

######  Theorem 6.7.

Suppose that $H(\tau)$ and the constraints in (6) hold. If all agents follow
the modified reasonable strategy, then with probability at least
$1-2/n^{2c+1}$, in every strip $s$ (except possibly the bottommost Type $2$
strip), $\operatorname{Imb}(s)\leq n/25\sqrt{T}$.

###### Proof.

We divide each strip into thin diagonals of width $1$. Let the diagonal
include the bottom but not the top boundary. Notice that for each value, a
diagonal contains at most one grid point.

We introduce the following notation w.r.t. diagonal $d$ at time step $\tau$,
where we are conditioning on the outcome of step $\tau-1$.

$\displaystyle I(d,\tau)$ $\displaystyle=E[(\text{number of men at time
$\tau$}-\text{number of women at time $\tau$})]$ $\displaystyle X(d,\tau)$
$\displaystyle=(\text{number of men matching at time $\tau$}-\text{number of
women matching at time $\tau$})$ $\displaystyle\hskip
14.45377pt-E[(\text{number of men matching at time $\tau$}-\text{number of
women matching at time $\tau$})]$ $\displaystyle Y(d,\tau)$
$\displaystyle=\text{number of men entering at time $\tau$}-\text{number of
women entering at time $\tau$}$ $\displaystyle A(d,\tau)$
$\displaystyle=(\text{number of men matching at time $\tau$}+\text{number of
women matching at time $\tau$})/2.$

$I(d,\tau)$ is measured after the entry of the new agents at time $\tau$ but
prior to the match for this step. Also, note that $Y(d,\tau)=0$ if $d$ is in a
Type $2$ strip.

In addition, observe that the imbalance $\operatorname{Imb}(s)$ at the start
of step $t$ equals $\sum_{d\in s}I(d,t)$.

We observe that a match between two agents in distinct diagonals of the same
strip will increment the $(\text{number of men }-\text{ number of women})$ in
one diagonal and decrement it in the other. Thus there is a zero net change
over all the diagonals in the strip due to the matches. However, as the agents
all age by 1 unit during a step, some agents enter the strip and some leave,
which can cause changes to the imbalance within a strip. However, the entry of
new agents can introduce new imbalances. We will need to understand more
precisely how these imbalances evolve.

It is convenient to number the diagonals as $d_{1},d_{2},d_{3},\ldots$, in
right to left order.

######  Claim 6.4.

Let $d_{i}$ and $d_{j}$ be two diagonals in the same strip $s$. For brevity,
let $I_{i}\triangleq I(d_{i},\tau-1)$, $I_{j}\triangleq I(d_{j},\tau-1)$,
$A_{i}\triangleq A(d_{i},\tau-1)$, $A_{j}\triangleq A(d_{j},\tau-1)$,
$X_{i}\triangleq X(d_{i},\tau-1)$, $X_{j}\triangleq X(d_{j},\tau-1)$. Finally,
let $R$ denote the maximum of the total number of men and the total number of
women in the system at time $\tau-1$.

Then the new imbalance on diagonal $d_{i}$, prior to every unmatched agent
adding 1 to their age (which causes the agents on $d_{i}$ to move to
$d_{i+1}$), denoted by $I^{\prime}(d_{i},\tau)$, is given by:

$\displaystyle I^{\prime}(d_{i},\tau)=$
$\displaystyle~{}~{}~{}~{}I_{i}+X_{i}-\sum_{d_{j}\in
s}\Big{[}X_{i}\frac{(2A_{j}-I_{j}-X_{j})}{4R}-X_{j}\frac{(2A_{i}-I_{i}-X_{i})}{4R}+I_{i}\frac{(2A_{j}-I_{j}-X_{j})}{4R}-I_{j}\frac{(2A_{i}-I_{i}-X_{i})}{4R}\Big{]};$
$\displaystyle\text{~{}~{}and~{}~{}}I(d_{i},\tau)=I^{\prime}(d_{i-1},\tau-1)+Y(d,\tau).$

This claim is shown by considering the expected number of matches involving
agents in diagonals $d_{i}$ and $d_{j}$. The proof can be found in Appendix
C.6.

The expression $X_{i}(2A_{j}-I_{j}-X_{j})/4R$ reflects the reduction of the
contribution of $X_{i}$ to the total imbalance on diagonal $d_{i}$ and the
corresponding increase on diagonal $d_{j}$. Thus it is convenient to view the
multiplier $(2A_{j}-I_{j}-X_{j})/4R$ as indicating the fraction of $X_{i}$
that is being moved to diagonal $j$; the remaining fraction of $X_{i}$ remains
on $d_{i}$.

$X(d,\tau)$ and $Y(d,\tau)$ are generated at diagonal $d$ at time $\tau$. In
each subsequent time step the portion on each diagonal where it is present
will be further redistributed:

  1. 1.

Due to the expected matching at time $\tau^{\prime}\geq\tau$, each portion of
$X(d,\tau)$ and $Y(d,\tau)$ spreads to other diagonals in the same strip.

  2. 2.

At the end of time step $\tau^{\prime}$ the portions of $X(d,\tau)$ and
$Y(d,\tau)$ present on diagonal $d_{i}$ move to diagonal $d_{i+1}$.

Building on these observations, we will show our bound on the imbalance by
means of the following two arguments. Specifically, we show that:

  1. 1.

For any $\tau$ and $\tau^{\prime}$, the total contribution from
$X(\cdot,\tau)$ and $Y(\cdot,\tau)$ to strip $s$ at time $\tau^{\prime}$ is
bounded.

  2. 2.

For times $\tau^{\prime}\geq\tau+\Omega(T\log n)$, the remaining portions of
$X(\cdot,\tau)$ and $Y(\cdot,\tau)$ in the market are small.

##### Bound on the contribution of $X$ to the strip $s$

Notice that $\sum_{d_{i}\in s}I^{\prime}(d_{i},\tau)=\sum_{d_{i}\in
s}I(d_{i},\tau-1)$, for the coefficients multiplying $X_{i}$ cancel, as they
also do for $I_{i}$. Thus we can think of this process as redistributing the
imbalance, but not changing the total imbalance.

Over time an imbalance $X(d_{i},\tau)$ will be redistributed over many
diagonals. We write $X(d_{i},\tau,d_{j},\tau^{\prime})$ to denote the portion
of $X(d_{i},\tau)$ on diagonal $d_{j}$ at time $\tau^{\prime}$. $d_{j}$ need
not be in the same strip as $d_{i}$. Note that
$\sum_{d_{j}}X(d_{i},\tau,d_{j},\tau^{\prime})=X(d_{i},\tau)$ for all
$\tau^{\prime}\geq\tau$. $Y(d_{i},\tau,d_{j},\tau^{\prime})$ is defined
analogously.

An important property concerns the relative distribution of the
$X(d_{i},\tau,d_{j},\tau^{\prime})$ and the
$X(d_{k},\tau,d_{j},\tau^{\prime})$. In a sense made precise in the following
claim, if $k>i$ the $d_{k}$ terms remain to the left of the $d_{i}$ terms.

For the purposes of the following claim, we treat the final strip as a single
diagonal, and in addition ignore the fact that people depart at age $T$ (which
means that once an imbalance appears in this strip it remains there). The
reason this strip is different is that it covers the whole of the bottom
boundary and so is the only strip from which people leave the system by aging
out.

######  Claim 6.5.

For all $\ell$, for all $i<k$, and for all $\tau^{\prime}\geq\tau$,
$\big{|}\sum_{j>\ell}X(d_{i},\tau,d_{j},\tau^{\prime})\big{|}\leq\big{|}\sum_{j>\ell}X(d_{k},\tau,d_{j},\tau^{\prime})\big{|}$.
The same property holds for the $Y(d_{i},\tau,d_{j},\tau^{\prime})$.

###### Proof.

We prove the result for the $X$ terms by induction on $\tau^{\prime}$; the
same argument applies to the $Y$ terms. Clearly the property holds for
$\tau^{\prime}=\tau$. Let $x_{ij}\triangleq
X(d_{i},\tau,d_{j},\tau^{\prime})/X(d_{i},\tau)$, and define $x_{kj}$
analogously. Our claim states that
$\sum_{j>\ell}x_{ij}\leq\sum_{j>\ell}x_{kj}$; we need to show it holds at time
$\tau^{\prime}+1$ also. We view the $x_{ij}$ as sitting on the unit interval,
with $x_{ij}$ taking a portion of length $x_{ij}$, ordered by increasing $j$,
and likewise for the $x_{kj}$. We map aligned portions of the $x_{ij}$ and
$x_{kj^{\prime}}$ to each other. This mapping has the property that the $j$
index in the $x_{ij}$ term is always equal to or smaller than the $j^{\prime}$
index in the $x_{kj^{\prime}}$ term.

Let’s look at how aligned portions of $x_{ij}$ and $x_{kj^{\prime}}$ are
dispersed in the next step. If they are in distinct strips, then
$j<j^{\prime}$ and this property is maintained for all the dispersed portions.

We view the multiplier $(2A_{j}-I_{j}-X_{j})/4R$ in Claim 6.4 as specifying
the fraction of $X_{i}$ that moves from diagonal $i$ to diagonal $j$. Notice
that this multiplier is the same for every diagonal in this strip.

We also note that $I_{i}$ consists of a sum of terms
$X(d_{i},\tau,d_{j},\tau^{\prime})$ and $X(d_{i},\tau,d_{j},\tau^{\prime})$
for diagonals $d_{j}$ in the same strip as $d_{i}$ or to the right of $d_{i}$.
Furthermore, the multiplier $(2A_{j}-I_{j}-X_{j})/4R$ specifies the fraction
of each of these terms that moves from diagonal $i$ to diagonal $j$. Thus if
$d_{j}$ and $d_{j^{\prime}}$ are in the same strip, the $X$ terms
corresponding to the aligned portions of $x_{ij}$ and $x_{kj^{\prime}}$ are
redistributed identically, thereby maintaining the property for these
fragments. Naturally, the property also continues to hold for undispersed
fragments.

Finally, shifting down by one diagonal, as is done following the dispersal,
will leave the property unaffected.

∎

Later, we will show a common bound $B$ on the sums $\big{|}\sum_{i\leq j\leq
k}X(d_{j},\tau)\big{|}$, which holds for all $d_{i}$ and $d_{k}$ in the same
strip and all333The calculation for the bound proved in Claim 6.7 only applies
to — $\sum_{i\leq j\leq k}X(d_{j},\tau)|$, where $\tau>\sqrt{T}$. However for
times in the initial $\sqrt{T}$ steps, the bound is only better. A calculation
of this bound for times in this initial period is done in the proof of Theorem
6.8; see Claim C.5 in Appendix C.7. $\tau$. With this bound and Claim 6.5 in
hand, for each strip $s$, we can bound the contribution of the
$X(d_{i},\tau,d_{j},\tau^{\prime})$ summed over all $d_{i}$ and over $d_{j}\in
s$ by $2B$.

######  Claim 6.6.

For all $\tau^{\prime}\geq\tau$, for every strip $s$,
$\big{|}\sum_{d_{i};d_{j}\in s}X(d_{i},\tau,d_{j},\tau^{\prime})\big{|}\leq
2B$.

###### Proof.

Let $d_{r(s)}$ be the rightmost (lowest index) diagonal in $s$ and $d_{l(s)}$
be the leftmost (highest index) diagonal in $s$. Let $w_{i}=\sum_{j\geq
r(s)}X(d_{i},\tau,d_{j},\tau^{\prime})/X(d_{i},\tau)$. Let’s consider
$\sum_{d_{i}\in s^{\prime};j\geq
r(s)}X(d_{i},\tau,d_{j},\tau^{\prime})=\sum_{d_{i}\in s^{\prime}}w_{i}\cdot
X(d_{i},\tau)$. Notice that $\sum_{r(s^{\prime})\leq i\leq
l(s)}X(d_{i},\tau)=0$. By Claim 6.5, $w_{i}\leq w_{k}$, for $i<k$. Thus,

$\displaystyle\Big{|}\sum_{d_{i}\in s^{\prime};j\geq
r(s)}X(d_{i},\tau,d_{j},\tau^{\prime})\Big{|}=\Big{|}\sum_{d_{i}\in
s^{\prime}}w_{i}\cdot X(d_{i},\tau)\Big{|}$
$\displaystyle\leq\sum_{r(s^{\prime})\leq
r<l(s^{\prime})}(w_{i}-w_{i-1})\Big{|}\sum_{r\leq i\leq
l(s^{\prime})}X(d_{i},\tau)\Big{|}$
$\displaystyle\leq(w_{l(s^{\prime})}-w_{r(s^{\prime})})\cdot\max_{r\geq
r(s^{\prime})}\Big{|}\sum_{r\leq i\leq l(s^{\prime})}X(d_{i},\tau)\Big{|}.$

We apply this bound to the diagonals from every strip to obtain:

$\displaystyle\Big{|}\sum_{d_{i};j\geq
r(s)}X(d_{i},\tau,d_{j},\tau^{\prime})\Big{|}=\Big{|}\sum_{s^{\prime}}\sum_{d_{i}\in
s^{\prime};j\geq
r(s)}X(d_{i},\tau,d_{j},\tau^{\prime})]\Big{|}\leq\sum_{s^{\prime}}(w_{l(s^{\prime})}-w_{r(s^{\prime})})\cdot
B\leq B.$ (7)

Using the same argument, $\big{|}\sum_{d_{i};j\geq
l(s)+1}X(d_{i},\tau,d_{j},\tau^{\prime})\big{|}\leq B$, since
$l(s)+1=r(s^{\prime\prime})$ where $s^{\prime\prime}$ is the strip immediately
below $s$. Therefore,

$\displaystyle\Big{|}\sum_{d_{i};d_{j}\in
s}X(d_{i},\tau,d_{j},\tau^{\prime})\Big{|}=\Big{|}\sum_{d_{i};j\geq
r(s)}X(d_{i},\tau,d_{j},\tau^{\prime})-\sum_{d_{i};j\geq
l(s)+1}X(d_{i},\tau,d_{j},\tau^{\prime})\Big{|}\leq 2B.$

∎

######  Claim 6.7.

For any time $\tau\leq n^{c}$, with probability at least
$1-\frac{1}{n^{2c+1}}$, $B\leq
96\Big{[}\frac{n\ln(4n^{3c+1}(T^{2}/32+T/8)N)}{\sqrt{T}}\Big{]}^{1/2}$.

###### Proof.

First we bound $|\sum_{d\in S}X(d,\tau)|$ for any subset $S$ of consecutive
diagonals in a strip $s$. Suppose the total number of men in $S$ is $m$ and
the total number of women is $w$.

By Theorem 6.2, the total population is at least $1/3\cdot n\sqrt{T}$. By
Theorem 6.3, it is at most $3nN/2+n$. In addition, by the inductive
hypothesis, the total imbalance is bounded by the bottommost strip population
plus the individual strip imbalances, and this is at most
$60n/\sqrt{T}+25nN/\sqrt{T}$. Therefore,

$\frac{n\sqrt{T}}{6}\leq\max\Big{\\{}\begin{array}[]{l}\text{total number of
men},\\\ \hskip 14.45377pt\text{total number of
women}\end{array}\Big{\\}}\leq\frac{1}{2}\Big{(}\frac{3n(\sqrt{T}+\log_{2}\sqrt{T}+1)}{2}+n+60n/\sqrt{T}+nN/25\sqrt{T}\Big{)}.$

As $\sqrt{T}\geq 26$ by constraint (6),

$\displaystyle\frac{n\sqrt{T}}{6}\leq\max\Big{\\{}\begin{array}[]{l}\text{total
number of men},\\\ \hskip 14.45377pt\text{total number of
women}\end{array}\Big{\\}}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>(8)

Let $M=\max\\{\text{total number of men},\text{total number of women}\\}$.
Lemmas 4.2 and 4.1 yield the following bound on the deviation from the
expected number of the number of men in $S$ matched in a given time step:

$\displaystyle\Pr\bigg{[}\Big{|}\begin{array}[]{l}\text{number of men
matched}\\\ \hskip 14.45377pt-E[\text{number of men
matched}]\end{array}\Big{|}>\frac{mw\epsilon}{M}\bigg{]}\leq
2e^{-{mw\epsilon^{2}}/{3M}}.$ (9)

By the lower bound on $M$ provided by (8):

$\displaystyle\Pr\bigg{[}\Big{|}\begin{array}[]{l}\text{number of men
matched}\\\ \hskip 7.22743pt-E[\text{number of men
matched}]\end{array}\Big{|}>\frac{6mw\epsilon}{n\sqrt{T}}\bigg{]}\leq\Pr\bigg{[}\Big{|}\begin{array}[]{l}\text{number
of men matched}\\\ \hskip 7.22743pt-E[\text{number of men
matched}]\end{array}\Big{|}>\frac{mw\epsilon}{M}\bigg{]}.$

And by the upper bound on $M$ given by (8), $2e^{-{mw\epsilon^{2}}/{3M}}\leq
2e^{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-{mw\epsilon^{2}}/{3n\sqrt{T}}}}$.

We now apply these two bounds to equation (9) to obtain:

$\displaystyle\Pr\bigg{[}\Big{|}\begin{array}[]{l}\text{number of men
matched}\\\ \hskip 14.45377pt-E[\text{number of men
matched}]\end{array}\Big{|}>\frac{6mw\epsilon}{n\sqrt{T}}\bigg{]}\leq
2e^{-{2mw\epsilon^{2}}/{9n\sqrt{T}}}.$

The same reasoning can be applied to the number of women matched in $S$.

We set
$\epsilon=\big{[}\frac{3n\sqrt{T}}{mw}\ln(4n^{3c+1}(T^{2}/32+T/8)N)\big{]}^{1/2}$.
By the inductive hypothesis, $m+w\leq 7.5n$, and therefore
$mw\leq(15n/4)^{2}$. We obtain:

$\displaystyle\frac{6mw\epsilon}{n\sqrt{T}}\Big{[}\frac{3mw\ln(4n^{3c+1}(T^{2}/32+T/8)N)}{n\sqrt{T}}\Big{]}^{1/2}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{45\sqrt{3}}{2}}\Big{[}\frac{n\ln(4n^{3c+1}(T^{2}/32+T/8)N)}{\sqrt{T}}\Big{]}^{1/2},$
$\displaystyle\text{and}\hskip
14.45377pt2e^{-{2mw\epsilon^{2}}/{9n\sqrt{T}}}\leq\frac{1}{2n^{3c+1}(T^{2}/32+T/8)N}.$

On adding the bounds for the numbers of men and women, this yields:

$\displaystyle\Pr\bigg{[}\big{|}\sum_{d\in
S}X(d,\tau)\big{|}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}45\sqrt{3}}\Big{[}\frac{n\ln(4n^{3c+1}(T^{2}/32+T/8)N)}{\sqrt{T}}\Big{]}^{1/2}\bigg{]}\leq\frac{1}{n^{3c+1}(T^{2}/32+T/8)N}.$
(10)

Recall that there are $N$ strips, at most $n^{c}$ rounds, and, for each strip,
there are at most $(T^{2}/32+T/8)$ choices of $l$ and $r$. Therefore, the
total failure probability is at most $\frac{1}{n^{2c+1}}$. ∎

##### Bound on the contribution of $Y$ to strip $s$.

As for $X$, we define $Y(d_{i},\tau,d_{j},\tau^{\prime})$ to be the portion of
$Y(d_{i},\tau)$ on diagonal $d_{j}$ at time $\tau^{\prime}$.

######  Claim 6.8.

With probability at least $1-\frac{1}{n^{2c+1}}$, for all
$\tau^{\prime}\geq\tau$, for every strip $s$, $\big{|}\sum_{d_{i};d_{j}\in
s}Y(d_{i},\tau,d_{j},\tau^{\prime})\big{|}\leq
2\sqrt{\frac{3n}{2}\ln\left(2Tn^{3c+1}\right)}$.

The proof of this claim is similar in spirit to that of Claim 6.7. We defer it
to Appendix C.6.

##### Remaining $X$ and $Y$ in the market.

Next, we want to show that after $O(T)$ time the portions of $X$ and $Y$
remaining in the market are small.

######  Claim 6.9.

$\frac{e^{2}\ln 2}{\log_{2}(4/3)}\sqrt{T}(\sqrt{T}+\log_{2}(2n^{k}))$ time
after their creation, there is only a $\frac{1}{2n^{k}}$ fraction of
$X(d,\tau)$ and $Y(d,\tau)$ remaining in the Type $1$ strips.

###### Proof.

Consider some $X(d,\tau)$ or $Y(d,\tau)$ generated in a Type $1$ strip.

We first bound $\sum_{j:d_{j}\in s}(2A_{j}-I_{j}-X_{j})/4R$ for any Type $1$
strip $s$. By Theorem 6.2, the total size of the population is lower bounded
by $(1/3)n\sqrt{T}$. By the inductive hypothesis, any Type $1$ strip $s$ has
total size at most $2.6n$. The term $\sum_{j:d_{j}\in s}(2A_{j}-I_{j}-X_{j})$
is $2$ times the total number of women in strip $s$. By the inductive
hypothesis, the number of women in $s$ is at most $1.3n+n/50\sqrt{T}$. Lemma
4.1 provides the following upper bound on the probability that a man receives
a match in a Type $1$ strip:

$\displaystyle\sum_{j:d_{j}\in
s}\frac{(2A_{j}-I_{j}-X_{j})}{4R}\leq\frac{1}{2}\cdot\frac{1.3n+\frac{n}{50\sqrt{T}}}{\frac{1}{6}n\sqrt{T}}<\frac{4}{\sqrt{T}},\hskip
14.45377pt\text{as ($\sqrt{T}\geq 26$ by
constraint~{}\ref{eqn::constraints})}.$ (11)

Consider any $X(d,\tau,d^{\prime},\tau^{\prime})$. If $d^{\prime}$ is in a
Type $1$ strip then by (11) in one step at most $\frac{4}{\sqrt{T}}$ of it
disperses to some location in the same strip, and at least
$1-\frac{4}{\sqrt{T}}$ of it moves down distance one. This implies that in
$\sqrt{T}/2$ time a Type $1$ strip loses at least $e^{-2}$ of the
$X(d,\tau,d^{\prime},\tau^{\prime})$ that had been present within it at time
$\tau^{\prime}$. Let $K_{1}=e^{2}\ln 2$. By time
$\tau^{\prime}+K_{1}\sqrt{T}/2$ at least half of the
$X(d,\tau,d^{\prime},\tau^{\prime})$ in a Type $1$ strip has moved out of the
strip.

We number the Type $1$ strips from top to bottom. Let $\gamma$ be the
distribution of $X(d,\tau)$ (or $Y(d,\tau)$) where $\gamma_{i}$ is the
fraction of $X(d,\tau)$ (or $Y(d,\tau)$) in strip $i$. Recall that there are
$\sqrt{T}$ Type $1$ strips. We consider the worst case: the $X(d,\tau)$ starts
out in the topmost strip. Define a potential function
$\phi(\gamma)=\sum_{i=1}^{\sqrt{T}}\gamma_{i}\cdot 2^{\sqrt{T}-i+1}.$ Any
fraction of $X(d,\tau)$ that has left the bottommost Type $1$ strip
contributes nothing to the potential. The initial potential is $2^{\sqrt{T}}$.
Every $K_{1}\sqrt{T}$ time steps, the potential decreases by at least $1/4$.
Therefore, after
$\frac{1}{\log_{2}(4/3)}K_{1}\sqrt{T}\log_{2}(2^{\sqrt{T}}2n^{k})$ time, the
potential would have reduced to at most $\frac{1}{2n^{k}}$, which means that
the fraction of $X(d,\tau)$ (or $Y(d,\tau)$) in the Type $1$ strips after
$\frac{1}{\log_{2}(4/3)}K_{1}\sqrt{T}(\sqrt{T}+\log_{2}(2n^{k}))$ time is at
most $\frac{1}{2n^{k}}$. ∎

We will analyze the progress through the Type 2 strips, apart from the
bottommost one, in a similar way. The proof can be found in Appendix C.6.

######  Claim 6.10.

$\frac{e^{2}\ln
2}{\log_{2}(4/3)}\sqrt{T}(\sqrt{T}+\log_{2}(2n^{k}))+\frac{e^{12}\ln
2}{4\log_{2}(4/3)}T\log_{2}(2n^{k}\sqrt{T})$ time after their creation, there
is only $\frac{1}{n^{k}}$ fraction of $X(d,\tau)$ and $Y(d,\tau)$ remaining in
any strip other than the bottommost Type 2 strip.

##### The Total Bound on Imbalance

Now we can bound the total imbalance in a strip $s$ at time $\tau^{\prime}$.
Let $\kappa=\frac{e^{2}\ln
2}{\log_{2}(4/3)}\sqrt{T}(\sqrt{T}+\log_{2}(2n^{k}))+\frac{e^{12}\ln
2}{4\log_{2}(4/3)}T\log_{2}(2n^{k}\sqrt{T})$. We divide the time interval
$[0,\tau^{\prime}]$ into two periods: $\left[0,\tau^{\prime}-{\kappa}\right]$
and $\left[\tau^{\prime}-{\kappa}+1,\tau^{\prime}\right]$.

  * •

In the first period, we bound each $|X(d,\tau)|$ and $|Y(d,\tau)|$ by $7.5n$
as no strip can have more than $7.5n$ agents on it by Lemma 6.1. By Claims 6.9
and 6.10, the total imbalance for this period is at most $15nTn^{c}/n^{k}$;

  * •

For the second period, using Claims 6.6, 6.7, and 6.8, The total imbalance is
at most
$\lceil\kappa\rceil\cdot\Big{(}192\sqrt{\frac{n\ln(4n^{3c+1}(T^{2}/32+T/8)N)}{\sqrt{T}}}+2\sqrt{\frac{3n}{2}\ln\left(2Tn^{3c+1}\right)}\Big{)}$.

We choose $k=c+4$ and sum them up. We desire that both these contributions to
the imbalance add up to no more than $n/25\sqrt{T}$. Using $n\geq T\geq 676$
(by the constraint (6)), we simplify this condition to conclude that it
suffices to have:

$n\geq(3654+2436e^{12}+546(e^{12}+1)c)^{2}(3c+4)T^{3}(\log_{2}n)^{2}\ln n.$

The details of this calculation can be found in Appendix C.6.

Finally, the failure probability of $2/n^{2c+1}$ arises from Claims 6.7 and
6.8, which each have failure probability at most $1/n^{2c+1}$.

∎

####  6.1.6 Initialization

######  Theorem 6.8.

Suppose that constraint (6) holds. If all agents follow the modified
reasonable strategy, then $H(\sqrt{T})$ holds with probability at least
$1-\frac{1}{n^{c+1}}$.

The proof is similar to the earlier analysis and can be found in Appendix C.7.

##  7 Numerical Simulations

We have demonstrated a strategy which is asymptotically close to optimal with
regard to minimizing the average loss experienced by agents. Complementing
this, in this section we simulate the evolution of the system for moderately
large values of $n$ and $T$. In order to gain a sense of the overall stability
of the system, we track the total population over time.

We now discuss some observations based on our simulations.444For every pair of
$n$ and $T$ that we considered in the discrete setting, we ran the simulation
$10$ times; letting each run for $2000$ iterations. The error ranges mentioned
below are obtained from the range of values we obtained over these $10$ runs.
The values for each run can be found in Appendix D.

Figure 2: The evolution of total population over time in the discrete (blue)
and continuum (orange) settings for $n=500$, $T=100$, using the reasonable
strategy.

Figure 3: The evolution of total population over time in the discrete (blue)
and continuum (orange) settings for $n=500$, $T=100$, using the modified
reasonable strategy.

For the continuum model we obtain reasonably rapid convergence—in about $T$
time—whereas for the discrete model in a similar time the system reaches its
long-term average value, but with somewhat chaotic oscillations about this
value, as shown in Figures 3 and 3. In addition, the long-term average
population for the discrete case is a bit larger than the continuum
equilibrium value. (This is not surprising, for both variance and male/female
imbalances will reduce the match rate.)

For moderate values of $n$ and $T$, the average loss in the modified
reasonable strategy is better than the asymptotic bound we obtain. For
example, consider the $n=500$, $T=100$ case. We prove an upper bound on the
total loss of $11T\sqrt{T}$ but the simulation achieves an average loss of
just $2.21T\sqrt{T}(\pm 1.7\%)$. The total populations are significantly
closer (an upper bound of close to $1.5nN$ in our theorem vs. close to
$n\sqrt{T}$ in the simulation).

For the case where agents use the modified reasonable strategy, we also
examine the average population size and average loss for various $T$ (with $n$
fixed at $500$). Figure 5 shows a plot of $\text{Average
Population}/n\sqrt{T}$ and $\text{Average Loss}/\sqrt{T}$ for five different
values of $n$. The result is quite consistent with the $n\sqrt{T}$ scaling of
the average total size and the $\sqrt{T}$ scaling of the average loss that we
prove hold asymptotically, even though these are only moderately large values
of $n$ and $T$, and even though we are not in the $n$ much greater than $T$
regime of our analysis.

Figure 4:  $\text{Average Population}/n\sqrt{T}$ (blue) and $\text{Average
Loss}/\sqrt{T}$ (red) for five values of $T$, using the modified reasonable
strategy.

Figure 5: The evolution of the population on a "typical diagonal" over time in
the discrete setting (for $n=500$, $T=100$), using the modified reasonable
strategy.

Finally, we examine the population on a "typical" diagonal555Here we consider
the diagonal region with width $1$ that starts at value $3T/2$ at the top
($t=0$) boundary. in the case that all agents are following the modified strip
strategy (Figure 5). Notice that the range of oscillations for this value is
large compared to the range of oscillations in the total population (Figure
3). Furthermore, these oscillations proceed at a much faster rate than the
changes in the overall population. The results also indicate that while the
system remains within reasonable bounds, there is substantial ongoing
variation, particularly at a local level.

##  8 Open Problems

Two natural extensions of our model come to mind.

  * •

The values in our model are common to all agents, but in reality agents will
have individual preferences. This could be captured with a model in which each
agent $a$ has a value for agent $b$ given by $v_{a}+w_{a,b}$, where $v_{a}$ is
a common public value while $w_{a,b}$ is an idiosyncratic private value of $a$
for $b$. The combining of public and private values has been studied in the
literature on matchings in other settings [Ash+20, Lee16].

  * •

In our model, agents receive match proposals that are generated by choosing
agents from the other side of the market uniformly at random. It would be
interesting to consider a more sophisticated method of recommending matches,
with recommended matches being localised in value and time around the agent.

Another intriguing direction concerns the stability of this system. We have
shown that if the agents play the modified reasonable strategy then with high
probability the strip sizes, the total size, and the imbalance between men and
women in any strip, all remain within some range. But we conjecture that if
any of these parameters were to have a large deviation which took it outside
its typical range, then with high probability it would soon return to being
within this range.

## References

  * [Ada03] Hiroyuki Adachi  “A search model of two-sided matching under nontransferable utility”  In _Journal of Economic Theory_ 113.2, 2003, pp. 182–198  URL: https://EconPapers.repec.org/RePEc:eee:jetheo:v:113:y:2003:i:2:p:182-198
  * [ALG20] Mohammad Akbarpour, Shengwu Li and Shayan Oveis Gharan  “Thickness and Information in Dynamic Matching Markets”  In _Journal of Political Economy_ 128.3, 2020  DOI: 10.1086/704761
  * [Ash+20] Itai Ashlagi, Mark Braverman, Yash Kanoria and Peng Shi  “Clearing matching markets efficiently: informative signals and match recommendations”  In _Management Science_ 66.5 INFORMS, 2020, pp. 2163–2193
  * [BC97] Ken Burdett and Melvyn G. Coles  “Marriage and Class*”  In _The Quarterly Journal of Economics_ 112.1, 1997, pp. 141–168  DOI: 10.1162/003355397555154
  * [BC99] Kenneth Burdett and Melvyn G. Coles  “Long-Term Partnership Formation: Marriage and Employment”  In _The Economic Journal_ 109.456, 1999, pp. 307–334  DOI: https://doi.org/10.1111/1468-0297.00435
  * [Bea06] J.N. Bearden  “A new secretary problem with rank-based selection and cardinal payoffs”  In _J. of Math.l Psych._ 50, 2006, pp. 58–9  DOI: 10.1016/j.jmp.2005.11.003
  * [BLY20] Mariagiovanna Baccara, SangMok Lee and Leeat Yariv  “Optimal dynamic matching”  In _Theoretical Economics_ 15, 2020, pp. 1221–1278
  * [BM07] Avrim Blum and Yishay Mansour  “Learning, Regret Minimization, and Equilibria”  In _Algorithmic Game Theory_ , 2007
  * [BR00] Francis Bloch and Harl Ryder  “Two-sided search, marriages, and matchmakers”  In _International Economic Review_ 41.1 Wiley Online Library, 2000, pp. 93–116
  * [BW98] Kenneth Burdett and Randall Wright  “Two-Sided Search with Nontransferable Utility”  In _Review of Economic Dynamics_ 1.1, 1998, pp. 220–245  URL: https://EconPapers.repec.org/RePEc:red:issued:v:1:y:1998:i:1:p:220-245
  * [CES17] Hector Chade, Jan Eeckhout and Lones Smith  “Sorting through Search and Matching Models in Economics”  In _Journal of Economic Literature_ 55.2, 2017, pp. 493–544  DOI: 10.1257/jel.20150777
  * [DLS05] Ettore Damiano, Hao Li and Wing Suen  “Unravelling of dynamic sorting”  In _The Review of Economic Studies_ 72.4 Wiley-Blackwell, 2005, pp. 1057–1076
  * [Eec99] Jan Eeckhout  “Bilateral search and vertical heterogeneity”  In _International Economic Review_ 40.4 Wiley Online Library, 1999, pp. 869–887
  * [Fer89] Thomas S. Ferguson  “Who Solved the Secretary Problem?”  In _Statistical Science_ 4.3, 1989, pp. 282–9  DOI: 10.1214/ss/1177012493
  * [KVV90] R.. Karp, U.. Vazirani and V.. Vazirani  “An Optimal Algorithm for On-Line Bipartite Matching”  In _Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing_ , STOC ’90  Baltimore, Maryland, USA: Association for Computing Machinery, 1990, pp. 352–358  DOI: 10.1145/100216.100262
  * [Lee16] SangMok Lee  “Incentive compatibility of large centralized matching markets”  In _The Review of Economic Studies_ 84.1 Review of Economic Studies Ltd, 2016, pp. 444–463
  * [LN14] Stephan Lauermann and Georg Nöldeke  “Stable marriages and search frictions”  In _Journal of Economic Theory_ 151 Elsevier, 2014, pp. 163–195
  * [MC90] John M McNamara and EJ Collins  “The job search problem as an employer-candidate game”  In _Journal of Applied Probability_ JSTOR, 1990, pp. 815–827
  * [PS97] Alessandro Panconesi and Aravind Srinivasan  “Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds”  In _SIAM J. Comput._ 26.2, 1997, pp. 350–368  DOI: 10.1137/S0097539793250767
  * [RSW05] Richard Rogerson, Robert Shimer and Randall Wright  “Search-Theoretic Models of the Labor Market: A Survey”  In _Journal of Economic Literature_ 43, 2005, pp. 959–988
  * [Smi06] Lones Smith  “The marriage model with search frictions”  In _Journal of political Economy_ 114.6 The University of Chicago Press, 2006, pp. 1124–1144
  * [SS00] Robert Shimer and Lones Smith  “Assortative matching and search”  In _Econometrica_ 68.2 Wiley Online Library, 2000, pp. 343–369

##  Appendix A Deferred Proofs from Section 4

###### Proof.

(Of Lemma 4.2) Let $N=\max\\{N_{1},N_{2}\\}.$ Consider any subset
$S\subseteq[n]$ where $|S|=k$. W.l.o.g. let $S=[k]$. Then,

$\displaystyle E\Big{[}\prod_{i\in S}X_{i}\Big{]}$
$\displaystyle=\operatorname{Pr}\Big{[}{\prod_{i\in
S}X_{i}=1}\Big{]}=\operatorname{Pr}\left[{X_{1}=1,X_{2}=1,\ldots,X_{k}=1}\right]\Big{]}$
$\displaystyle=\operatorname{Pr}\left[{X_{1}=1}\right]\cdot\operatorname{Pr}\left[{X_{2}=1|X_{1}=1}\right],\ldots,\operatorname{Pr}\left[{X_{k}=1|X_{1}=1,X_{2}=1,\ldots,X_{k-1}=1}\right]$
$\displaystyle=\frac{r}{N}\cdot\frac{r-1}{N-1},\ldots,\frac{r-k+1}{N-k+1}.$

Hence,

$E\Big{[}\prod_{i\in S}X_{i}\Big{]}\leq\Big{(}\frac{r}{N}\Big{)}^{k},$

while

$\prod_{i\in S}E[X_{i}]=\Big{(}\frac{r}{N}\Big{)}^{k}.$

Similarly,

$\displaystyle E\Big{[}\prod_{i\in S}(1-X_{i})\Big{]}$
$\displaystyle=\operatorname{Pr}\Big{[}{\prod_{i\in
S}(1-X_{i})=1}\Big{]}=\operatorname{Pr}\left[{X_{1}=0,X_{2}=0,\ldots,X_{k}=0}\right]\Big{]}$
$\displaystyle=\operatorname{Pr}\left[{X_{1}=0}\right]\cdot\operatorname{Pr}\left[{X_{2}=0|X_{1}=0}\right],\ldots,\operatorname{Pr}\left[{X_{k}=0|X_{1}=0,X_{2}=0,\ldots,X_{k-1}=0}\right]$
$\displaystyle=\frac{N-r}{N}\cdot\frac{N-r-1}{N-1},\ldots,\frac{N-r-k+1}{N-k+1}.$

Hence,

$E\Big{[}\prod_{i\in S}(1-X_{i})\Big{]}\leq\Big{(}\frac{N-r}{N}\Big{)}^{k},$

while

$\prod_{i\in S}E[1-X_{i}]=\Big{(}\frac{N-r}{N}\Big{)}^{k}.$

Thus the set $\\{X_{i}\\}$ is negative cylinder dependent. By [PS97, Theorem
3.4] with $\lambda=1$, Chernoff bounds for sums of independent random
variables apply to the sums of negative cylinder dependent random variables as
well. This concludes the proof. ∎

###### Proof.

(Of Lemma 4.3)

First we prove that

$\displaystyle\operatorname{Pr}\left[\sum
X_{i}\geq(1+\delta)\overline{\mu}\right]\leq
e^{-\frac{\delta^{2}\overline{\mu}}{3}}.$

Let $\overline{\mu}=(1+\theta)\mu$. By Lemma 4.2,

$\displaystyle\operatorname{Pr}\left[\sum X_{i}\geq(1+\gamma)\mu\right]\leq
e^{-\frac{\gamma^{2}\mu}{3}}.$ (12)

Set $(1+\gamma)=(1+\theta)(1+\delta)$. Then, from equation (12) we obtain,

$\displaystyle\operatorname{Pr}\left[\sum
X_{i}\geq(1+\delta)\overline{\mu}\right]$
$\displaystyle\leq\exp\bigg{[}-\frac{(\theta+\delta+\theta\cdot\delta)^{2}\mu}{3}\bigg{]}\leq\exp\bigg{[}-\frac{(\delta+\theta\cdot\delta)^{2}\mu}{3}\bigg{]}$
$\displaystyle\leq\exp\bigg{[}-\frac{\delta^{2}(1+\theta)^{2}\mu}{3}\bigg{]}\leq\exp\bigg{[}-\frac{\delta^{2}(1+\theta)\mu}{3}\bigg{]}\leq\exp\bigg{[}-\frac{\delta^{2}\overline{\mu}}{3}\bigg{]}$

which proves the claim. We will now prove that

$\displaystyle\operatorname{Pr}\left[\sum
X_{i}\leq\mu-\delta\overline{\mu}\right]\leq e^{-\frac{\delta^{2}\mu}{2}}$

Let $\theta=\frac{\mu}{\overline{\mu}}$. By Lemma 4.2,

$\displaystyle\operatorname{Pr}\left[\sum X_{i}\leq\mu-\delta\mu\right]\leq
e^{-\frac{\delta^{2}\mu}{2}}$

Let $\gamma=\frac{\overline{\mu}}{{\mu}}$. Note that $\gamma\geq 1$

$\displaystyle\operatorname{Pr}\left[\sum
X_{i}\leq\mu-\delta\overline{\mu}\right]$
$\displaystyle=\operatorname{Pr}\left[\sum
X_{i}\leq\mu-\gamma\delta\mu\right]\leq\exp\bigg{[}-\frac{(\gamma\delta)^{2}\mu}{2}\bigg{]}\leq\exp\bigg{[}-\frac{\delta^{2}\gamma\overline{\mu}}{2}\bigg{]}\leq\exp\bigg{[}-\frac{\delta^{2}\overline{\mu}}{2}\bigg{]}$

which completes the proof.

∎

##  Appendix B Deferred Calculation from Section 5

###### Proof.

(Final calculation for Theorem 3.1)

$\displaystyle\operatorname{Pr}[{\mathcal{E}}]\cdot\left(1-\tau
Te^{-\frac{\delta^{2}nw^{2}}{6T^{2}}}-\tau
e^{-\frac{\epsilon^{2}n}{4}}\right)$
$\displaystyle\geq\Big{(}1-e^{-\frac{\delta^{2}nw}{6T}}\Big{)}^{\tau\frac{T}{w}}\cdot\Big{(}1-\tau
Te^{-\frac{\delta^{2}nw^{2}}{6T^{2}}}-\tau
e^{-\frac{\epsilon^{2}n}{4}}\Big{)}$
$\displaystyle\geq\Big{[}1-\Big{(}\frac{1}{3n^{c}T\tau}\Big{)}^{4\sqrt{T}}\Big{]}^{4\tau\sqrt{T}}\cdot\Big{(}1-\frac{1}{3n^{c}}-\frac{1}{3n^{c}}\Big{)}$
$\displaystyle\geq\Big{[}1-4\tau\sqrt{T}\Big{(}\frac{1}{3n^{c}T\tau}\Big{)}^{2}\Big{]}\cdot\Big{(}1-\frac{1}{3n^{c}}-\frac{1}{3n^{c}}\Big{)}$
$\displaystyle\geq\Big{[}1-\Big{(}\frac{1}{3n^{c}}\Big{)}^{4\sqrt{T}}\Big{]}\cdot\Big{(}1-\frac{2}{3n^{c}}\Big{)}\geq\Big{(}1-\frac{1}{n^{c}}\Big{)}.$

∎

##  Appendix C Deferred Proofs from Section 6

###### Proof.

(Of Lemma 6.1.) We complete the sketch proof by bounding the failure
probability. Per time step, Theorems 6.2, 6.3, 6.4, 6.5 all have failure
probability of at most $1/n^{2c+1}$, Theorem 6.7 has failure probability at
most $2/n^{2c+1}$, and Theorem 6.8, which is applied once, has failure
probability at most $1/n^{c+1}$. Theorem 6.6 does not introduce any additional
possibility of failure. Multiplying by the $n^{c}$ possible time steps, gives
a total failure probability of at most $7/n^{c+1}<1/n^{c}$. ∎

###  C.1 Upper Bound on Loss due to a Match

###### Proof.

(of Lemma 6.2). Consider an agent (Agent $1$) at value $v$ and time $t$.
Suppose they match with another agent (Agent $2$) who is present in the same
strip. The worst location for Agent 2 is to be on the low value strip
boundary, and on this boundary to be at one of the endpoints.

_Type $1$ strip_. If Agent $2$ is at the top endpoint, Agent $1$ obtains
utility $w\cdot T-t$, where $w$ is the value at the top endpoint. We can see
that $w\geq v-\sqrt{T}-2t$ (move from $v$ horizontally to the lower boundary,
a distance of at most $\sqrt{T}$ and then move up to the $t=0$ location, which
subtracts $2t$ from the value). Thus the utility Agent $1$ receives is at
least $(T-t)(v-\sqrt{T}-2t)$. Therefore the loss is at most
$t(v+2T+\sqrt{T})\leq 4tT+2T\sqrt{T}$.

If Agent $2$ is at the lower endpoint of a Type 1 strip, we argue as follows.
The $v\cdot T-t$ product is equal at the two endpoints of a boundary, and
therefore the loss is greatest at the top endpoint, for the utility garnered
by Agent $1$ would be $w\cdot(T-t)$ and not $w\cdot T$, whereas at the bottom
endpoint the garnered utility is $2T\cdot w/2=wT$.

_Type $2$ Strip_. We define the following $t$ values: $a$ is the value for the
left end of the top boundary of the strip, $b$ the value for the left end of
the bottom boundary. and $c$ the value for the right end of the bottom
boundary, Then $a\leq(2t+T-v)/2$, $b\leq 2a+\sqrt{T}$, and $c=T/2+b\leq
T/2+2a+\sqrt{T}$.

If Agent $2$ is at the lower endpoint, then Agent 1 would receive utility
$2T\cdot(T-c)\geq 2T(v-T/2-2t-\sqrt{T})$. Thus the loss is at most
$T(T-v)+4tT+2T\sqrt{T}\leq 4tT+2T\sqrt{T}$.

If Agent $2$ is at the top endpoint and Agent 1 is older than Agent 2, then
Agent $1$ receives utility $T(T-t)$. As we are in a Type 2 strip, $(v-T)\leq
2t$ or $v\leq T+2t$. So Agent $1$ incurs a loss of at most
$vT-T(T-t)\leq(T+2t)T-T(T-t)\leq 3tT$.

While if Agent $1$ is no older than Agent $2$, then Agent $1$ receives utility
$T(T-b)\geq T(v-2t-\sqrt{T})$. Thus the loss is at most
$vT-T(v-2t-\sqrt{T})=2Tt+T\sqrt{T}$. ∎

###  C.2 Lower Bound on the Total Population

###### Proof.

(of Theorem 6.2) The agents enter with one of $T$ values chosen uniformly at
random and are equally likely to be men or women. Hence, for all $n^{c}$ time
steps, for each value $v$,

$\operatorname{Pr}\Big{[}\text{At most $\frac{n(1+\epsilon)}{2T}$ men enter
with value $v$}\Big{]}\geq 1-n^{c}Te^{-\frac{\epsilon^{2}n}{6T}}.$

Call this event $\mathcal{E}$. Henceforth we condition on $\mathcal{E}$.

Let’s consider those agents that enter at times in the range
$[\tau-\sqrt{T}+1,\tau]$ for some $\tau\leq n^{c}$. We want to lower bound the
number of these agents who are present in the pool for the match at time
$\tau$.

In fact, henceforth, We will only consider men with values in the range
$[T+\sqrt{T},2T)$. Among these men, consider those who have been in the pool
for $t$ time, where $0\leq t<\sqrt{T}$. Let $p_{i}^{t}$ be the probability
that during their $t$th time step, the men in strip $i$ are offered a match in
their own strip. Even if all these men were still present in the matching
pool,

$\displaystyle\operatorname{Pr}\Big{[}\text{\\# of these men matched in strip
$i$ at age $t$ }\leq\frac{n(1+\delta)(1+\epsilon)\cdot p_{i}\cdot
w_{i}}{2T}\Big{]}\geq 1-e^{-\frac{\delta^{2}np_{i}w_{i}}{6T}},$

where $w_{i}$ is the horizontal width of strip $i$ occupied by these men when
aged $t$. For every Type 1 strip, $w_{i}\leq\sqrt{T}$. For the one Type 2
strip, since all values are at least $T+\sqrt{T}$, for ages up to $\sqrt{T}$,
$w_{i}\leq\sqrt{T}$. By applying
$\overline{\mu}=\frac{n(1+\epsilon)\max\\{p_{i},\frac{1}{T}\\}\sqrt{T}}{2T}$
in Lemma 4.3, it follows that:

$\displaystyle\operatorname{Pr}\Big{[}\text{\\# of these men matched in strip
$i$ at age $t$
}\leq\frac{n(1+\delta)(1+\epsilon)\cdot\max\\{p_{i},\frac{1}{T}\\}}{2\sqrt{T}}\Big{]}$
$\displaystyle\geq
1-e^{-\frac{\delta^{2}n\max\\{p_{i},\frac{1}{T}\\}\sqrt{T}}{6T}}$
$\displaystyle\geq 1-e^{-\frac{\delta^{2}n}{6T^{1.5}}},$

The sum of the match probabilities—the $p_{i}$s— is at most $1$. Notice that
at any fixed time we only need to consider $\sqrt{T}$ strips, because at any
time step, the men we are considering will occupy only $\sqrt{T}$ many strips.
This implies $\sum\max\\{p_{i},\frac{1}{T}\\}\leq 1+\frac{1}{\sqrt{T}}$.
Therefore,

$\operatorname{Pr}\Big{[}\begin{array}[]{l}\text{\\# of these men being
matched}\\\ \text{over all the strips at age
$t$}\end{array}\leq\frac{(1+\frac{1}{\sqrt{T}})n(1+\delta)(1+\epsilon)}{2\sqrt{T}}\Big{]}\geq
1-\sqrt{T}\cdot e^{-\frac{\delta^{2}n}{6T^{1.5}}}.$

Hence, we can bound the probability of the number of men who entered at time
$\tau-\Delta+1$ and left by time $\tau$, for any $\Delta\leq\sqrt{T}$, as
follows:

$\operatorname{Pr}\Big{[}\begin{array}[]{l}\text{\\# men being matched}\\\
\text{in their first $\Delta$
steps}\end{array}\leq\frac{(1+\frac{1}{\sqrt{T}})n\Delta(1+\delta)(1+\epsilon)}{2\sqrt{T}}\Big{]}\geq
1-\Delta T\cdot e^{-\frac{\delta^{2}n}{6T^{1.5}}}.$

Consequently, we can bound the probability for the number of men that enter in
the time interval $[\tau-\sqrt{T}+1,\tau-1]$ and are matched no later than
time $\tau-1$ as follows, where we sum over all $\tau\leq n^{c}$:

$\displaystyle\operatorname{Pr}\bigg{[}\begin{array}[]{l}\text{\\# men who
entered and were}\\\ \text{matched in a $\sqrt{T}-1$ time
window}\end{array}\leq\frac{(1+\frac{1}{\sqrt{T}})n(1+\delta)(1+\epsilon)(\sqrt{T}-1)}{4}\bigg{]}\geq
1-\frac{1}{2}n^{c}T^{1.5}e^{-\frac{\delta^{2}n}{6T^{1.5}}}.$

We set
$\delta=\Big{[}\frac{6T^{1.5}}{n}\ln\big{(}10n^{2c+1}n^{c}T^{1.5}\big{)}\Big{]}^{1/2}$
and
$\epsilon=\Big{[}\frac{6T}{n}\ln\big{(}20n^{2c+1}n^{c}T\big{)}\Big{]}^{1/2}$.
By constraint (6), $c\geq 1$, $400\leq T\leq n$, and $n\geq 96T^{2}(3c+3)\ln
n$, therefore $\delta\leq 1/4$ and $\epsilon\leq{1}/{64}$. This yields the
bound:

$\displaystyle\operatorname{Pr}\Big{[}\begin{array}[]{l}\text{\\# men who
entered in a $\sqrt{T}-1$}\\\ \text{ window being matched
}\end{array}\geq\frac{\frac{65}{64}\cdot\frac{5}{4}n\sqrt{T}}{4}\Big{]}\geq
1-\frac{1}{20n^{2c+1}}.$

Since we have been conditioning on $\mathcal{E}$, this bound holds with
probability at least $1-\frac{1}{10n^{2c+1}}$. The same bound applies to the
women.

Recalling that we excluded the men with values less than $T+\sqrt{T}$, this
yields the following lower bound on the total population size, throughout this
$n^{c}$ time period:

$n\sqrt{T}-\frac{n(1+\epsilon)}{2\sqrt{T}}-0.635n\sqrt{T}\geq\frac{1}{3}n\sqrt{T},$

with probability at least $1-\frac{1}{5n^{2c+1}}.$ ∎

###  C.3 Upper Bound on The Total Population

###### Proof.

(Of Theorem 6.3.) Let $P(t)$ be the total population at the start of time step
$t$. Let $N$ be the total number of strips. By Constraint 6, $T\geq 676$, so
$N\leq\sqrt{T}+\log_{2}\sqrt{T}+1\leq 5\sqrt{T}/4.$

If $P(t)\leq\frac{3}{2}nN$, then $P(t+1)\leq\frac{3}{2}nN+n$. So we will only
consider the case that $P(t)>\frac{3}{2}nN$. In this case, the average strip
population at the start of step $t$ is more than $\frac{3}{2}n$.

Next, we upper bound the number of men in the population; the same bound
applies to the number of women.

By $H(t)$, clause 5, the excess of men over women in each strip is at most
$n/25\sqrt{T}$ except for the last Type $2$ strip. So the excess over all
these $N-1$ strips is at most $n(N-1)/25\sqrt{T}$. For the last Type $2$
strip, the population is less than $60n/\sqrt{T}$ which is smaller than
$40P(t)/676$ as $T\geq 676$. Consequently, there are at most
$P(t)/2+nN/50\sqrt{T}+20P(t)/676\leq 11P(t)/20$ men in the total population.

The expected number of matches in strip $i$, $\mu_{i}$, is given by

$E[\mu_{i}]=\frac{(\text{ number of women in strip }i)\times(\text{ number of
men in strip }i)}{\text{number of men in the whole population}}.$

Let $s_{i}$ denote the population of the $i$-th strip. The denominator is at
most $\tfrac{11}{20}P(t)$ and at least $\tfrac{1}{2}P(t)$. The numerator is
minimized when the number of women and men in the strip are as far apart as
possible. So, for the strips other than the last Type $2$ strip, the numerator
is at least
$(s_{i}/2+n/50\sqrt{T})(s_{i}/2-n/50\sqrt{T})=s_{i}^{2}/4-n^{2}/2500T^{2}$.
The numerator is maximized when the numbers of women and men are equal.
Therefore,

$\displaystyle\frac{s_{i}^{2}/4-n^{2}/2500T^{2}}{\frac{11}{20}P(t)}\leq
E[\mu_{i}]\leq\frac{s_{i}^{2}}{2P(t)}.$ (13)

Consider an indicator random variable $X_{i}$ for each man in this strip,
which is $1$ if that man gets matched. By Lemma 4.2 we can use a Chernoff
bound to obtain:

$\displaystyle\operatorname{Pr}\Big{[}\text{number of matches in strip
}i\leq\mu_{i}(1-\epsilon)\Big{]}\leq e^{-\epsilon^{2}\mu_{i}/2}.$ (14)

For $E[\mu_{i}]\geq\alpha n/\sqrt{T}$,

$\displaystyle\operatorname{Pr}\big{[}\text{number of matches in strip }i\leq
E[\mu_{i}](1-\epsilon)\big{]}\leq e^{-\epsilon^{2}E[\mu_{i}]/2}\leq
e^{-\epsilon^{2}\alpha n/(2\sqrt{T})}.$

Let $\epsilon=\sqrt{\frac{2\sqrt{T}}{\alpha n}\ln(Nn^{2c+1})}$. Then
$\operatorname{Pr}\big{[}\text{number of matches in strip
}i\leq\mu_{i}(1-\epsilon)\big{]}\leq\frac{1}{Nn^{2c+1}}$

For $E[\mu_{i}]<\alpha n/\sqrt{T}$, let $\epsilon=\frac{\theta}{E[\mu_{i}]}$,
then (14) becomes

$\displaystyle\operatorname{Pr}\big{[}\text{number of matches in strip }i\leq
E[\mu_{i}]-\theta\big{]}\leq e^{-\theta^{2}/(2E[\mu_{i}])}\leq
e^{-\theta^{2}\sqrt{T}/(2\cdot\alpha n)}.$

Let $\theta=\sqrt{\frac{2\alpha
n}{\sqrt{T}}\ln(Nn^{2c+1})}=\alpha\epsilon\frac{n}{\sqrt{T}}$, then
$\operatorname{Pr}\big{[}\text{number of matches in strip
}i\leq\mu_{i}-\theta\big{]}\leq\frac{1}{Nn^{2c+1}}$

Let NL be the set of all strips except for the last Type $2$ strip. Then, with
probability at least $1-\frac{1}{n^{2c+1}}$, the number of matches is larger
than $(1-\epsilon)\sum_{i\in\texttt{NL}}E[\mu_{i}]-N\theta$. In addition, by
(13), $\sum_{i\in\texttt{NL}}E[\mu_{i}]$ is lower bounded by:

$\displaystyle\sum_{i\in\texttt{NL}}\frac{s_{i}^{2}/4-n^{2}/2500T^{2}}{\tfrac{11}{20}P(t)}$
$\displaystyle\geq\sum_{i\in\texttt{NL}}\frac{\frac{1}{4}\left(\frac{9P(t)}{10N}\right)^{2}-n^{2}/2500T^{2}}{\tfrac{11}{20}P(t)}$
$\displaystyle\geq\left(\frac{81}{220}\frac{P(t)}{N}-\frac{n^{2}N}{1375T^{2}P(t)}\right)$
$\displaystyle\geq\left(\frac{243}{440}n-\frac{2n}{4125T^{2}}\right)$
$\displaystyle\geq\frac{11}{20}n.$

The first inequality follows as
$\sum_{i\in\texttt{NL}}s_{i}\geq\frac{9}{10}P(t)$, and the next to last
inequality follows as $P(t)\geq\frac{3}{2}nN$. Let $\alpha=0.4$. Since
$\epsilon\leq\frac{1}{22}$, as $n\geq 2420\sqrt{T}(2c+2)\ln n$, and
$N\theta\leq\frac{5}{4}\alpha\epsilon n$, as $N\leq\frac{5}{4}\sqrt{T}$ and
$\theta=\alpha\epsilon n/\sqrt{T}$,

$\displaystyle(1-\epsilon)\sum_{i\in\texttt{NL}}E[\mu_{i}]-N\theta\geq(1-\epsilon)\frac{11}{20}n-\frac{5}{4}\alpha\epsilon
n\geq\frac{n}{2}.$

This means the total number of people matched in the market is greater than
$n$, which is the number of people entering, which completes the proof.

∎

###  C.4 Upper Bound on the Size of a Type 1 Strip.

###### Proof.

(Of Theorem 6.4) Consider any Type $1$ strip $s$. For any two points
$(v,t_{1})$ and $(v,t_{2})$ in $s$ which have the same value $v$, we have
$|t_{2}-t_{1}|\leq\frac{\sqrt{T}}{2}$. Let $s^{\prime}$ be the strip
immediately to the right of $s$.

We are going to lower bound the number of matches in time step $t$. Let’s
consider the agents who will be in strip $s$ at time $t+1$. They will all
enter $s$ during a length $\sqrt{T}/2$ time interval ending at time $t+1$.

Let $P_{t-\sqrt{T}+1}$ be the agents in strip $s^{\prime}$ at time
$t-\sqrt{T}$. By the inductive hypothesis, applied to $s^{\prime}$ at time
$t-\sqrt{T}$, we know that $|P_{t-\sqrt{T}+1}|\leq dn$. We are going to track
the subset of these agents who remain in the system after each step of
matches, for the next $\sqrt{T}$ steps, along with the new agents who join the
diagonals used by this subset of agents. Define $S_{t-\sqrt{T}+i}$ to be the
rightmost $\sqrt{T}+1-i$ diagonals in $s^{\prime}$ plus the leftmost $i-1$
diagonals in $s$, for $1\leq i\leq\sqrt{T}+1$. Let $P_{t-\sqrt{T}+i}$ be the
population occupying $S_{t-\sqrt{T}+i}$ at the start of step $t-\sqrt{T}+i$.
Then $P_{t-\sqrt{T}+i+1}$ is obtained from $P_{t-\sqrt{T}+i}$ by removed
matched agents and then adding the new agents for the diagonals in
$S_{t-\sqrt{T}+i+1}$. Our analysis will show that, with high probability, for
each of these $\sqrt{T}$ steps, the number of matches is at least the number
of new agents. This implies the upper bound on the strip population continues
to hold.

By means of a Chernoff bound, we observe that the number of new agents per
step can be bounded with high probability as follows:

$\displaystyle\operatorname{Pr}\left[{\text{\\# new agents
}\leq\frac{n}{\sqrt{T}}(1+\delta)}\right]\geq
1-e^{-\frac{n\delta^{2}}{3\sqrt{T}}}.$ (15)

Let $\delta=\sqrt{\frac{3\sqrt{T}}{n}\ln(Nn^{2c+1})}$. As $n\geq 60T(2c+2)\ln
n$, $\delta\leq\frac{1}{20}$, which yields

$\displaystyle\operatorname{Pr}\Big{[}\text{\\# new
agents}\leq\frac{41n}{40\sqrt{T}}=1.025\frac{n}{\sqrt{T}}\Big{]}\geq
1-\frac{1}{Nn^{2c+1}}.$ (16)

By (8), the maximum of the number of men and number of women in the market is
at most $n\sqrt{T}$.

Let $P_{t^{\prime\prime},s}$ and $P_{t^{\prime\prime},s^{\prime}}$ be the
portions of population $P_{t^{\prime\prime}}$ at time $t^{\prime\prime}$ in
strips $s$ and $s^{\prime}$, resp., for $t+1-\sqrt{T}\leq t^{\prime\prime}\leq
t$.

By Lemma 6.3, the matches remove at least the following number of people from
$P_{t^{\prime\prime},s}$:

$\displaystyle\frac{(|P_{t^{\prime\prime},s}|^{2})/2-(n/25\sqrt{T})^{2}/2}{n}\sqrt{T}=\frac{|P_{t^{\prime\prime},s}|^{2}-n^{2}/625T}{2n\sqrt{T}}$

A similar bound applies to the matches involving
$P_{t^{\prime\prime},s^{\prime}}$. To minimize the terms
$|P_{t^{\prime\prime},s^{\prime}}|^{2}/2n\sqrt{T}$ for
$P_{t^{\prime\prime},s}$ and $P_{t^{\prime\prime},s^{\prime}}$, we should make
them equal. Thus the expected number of matches of population
$P_{t^{\prime\prime}}$ is at least

$\displaystyle\frac{|P_{t^{\prime\prime}}|^{2}}{4n\sqrt{T}}-\frac{n}{625T\sqrt{T}}.$
(17)

Next, we want to obtain a high probability bound.

There are four sets of people, resp. the men and women in each of
$P_{t^{\prime\prime},s}$ and $P_{t^{\prime\prime},s^{\prime}}$. Let $\mu$ be
the number of matches of one set. If $E[\mu]\geq\frac{\alpha n}{\sqrt{T}}$,
then

$\displaystyle\Pr\big{[}\mu\geq E[\mu](1-\epsilon)\big{]}\geq
1-e^{-(E[\mu]\epsilon^{2})/2}\geq 1-e^{-\epsilon^{2}\alpha n/(2\sqrt{T})};$

letting $\epsilon=\sqrt{\frac{2\sqrt{T}}{\alpha n}\ln(4Tn^{2c+1})}$ yields
$\Pr\big{[}\mu\geq E[\mu](1-\epsilon)\big{]}\geq 1-\frac{1}{4Tn^{2c+1}}$.

Otherwise, $E[\mu]\leq\frac{\alpha n}{\sqrt{T}}$, and

$\displaystyle\Pr\big{[}\mu\geq E[\mu]-\theta\big{]}\geq
1-e^{-(\theta^{2})/(2E[\mu])}\geq 1-e^{-(\sqrt{T}\theta^{2})/(2\alpha n)};$

setting $\theta=\sqrt{\frac{2\alpha
n}{\sqrt{T}}\ln(4\sqrt{T}n^{2c+1})}=\alpha\epsilon\frac{n}{\sqrt{T}}$ yields
$\Pr\Big{[}\mu\geq E[\mu]-\theta\Big{]}\geq 1-\frac{1}{4Tn^{2c+1}}$.

Recall (16), the high probability bound that the number of new agents is at
most $1.025\frac{n}{\sqrt{T}}$.

By (17), the number of people matched is at least
$(1-\epsilon)\left[\frac{|P_{t^{\prime\prime}}|^{2}}{4n\sqrt{T}}-\frac{n}{625T\sqrt{T}}\right]-4\theta$.
Recall that $|P_{t^{\prime\prime}}|\leq dn$; we let
$x=dn-|P_{t^{\prime\prime}}|$. Then, the number of people left is at most:

$\displaystyle
dn-x-\left[(1-\epsilon)\left[\frac{(dn-x)^{2}}{3n\sqrt{T}}-\frac{n}{625T\sqrt{T}}\right]-4\theta\right]\leq
dn-\left[(1-\epsilon)\left[\frac{(dn)^{2}}{4n\sqrt{T}}-\frac{n}{625T\sqrt{T}}\right]-4\theta\right],$

if $1\geq(1-\epsilon)d/2\sqrt{T}$. This number is upper bounded by
$dn-(1-\epsilon)(\frac{d^{2}}{4}-\frac{1}{422,500})\frac{n}{\sqrt{T}}+4\alpha\epsilon\frac{n}{\sqrt{T}}$
as $T\geq 676$ and $|P_{t^{\prime\prime}}|\geq dn$. Let $d=2.6$ and
$\alpha=\frac{3}{16}$. Also, $\epsilon\leq\frac{1}{10}$ as $n\geq 27(2c+2)T\ln
n$ and $676\leq T\leq n$. A final calculation shows that
$(1-\epsilon)(\frac{d^{2}}{4}-\frac{1}{422,500})\frac{n}{\sqrt{T}}-4\alpha\epsilon\frac{n}{\sqrt{T}}$
is at least $1.025\frac{n}{\sqrt{T}}$, demonstrating the result.

∎

###  C.5 Upper Bound on the Size of a Type 2 Strip

###### Proof.

(of Theorem 6.5)

Consider any Type $2$ strip s. If $s$ is the topmost Type $2$ strip, clearly
we can upper bound its size by twice the bound on the size of a Type $1$ strip
given in Theorem 6.4. In addition, if $s$ is the Type $2$ strip next to the
topmost Type $2$ strip, then the size of strip $s$ is less than that of the
topmost Type $2$ strip at time $t+1-\sqrt{T}$, which completes the proof for
this strip too.

We now assume that $s$ has at least two Type $2$ strips above it. Let
$s^{\prime}$ be the strip immediately above $s$, and let $h$ denote the height
of $s$. Then the height of $s^{\prime}$ is $h/2$ and $h\geq\sqrt{T}$.

Let’s consider the agents who will be in strip $s$ at time $t+1$. They will
all enter $s$ during a length $h$ time interval ending at time $t+1$. They can
be partitioned into two sets as follows:

  * •

$Y_{t+1}=\\{\text{agents that will have spent less than $h/2$ time in strip
$s$ by time $t+1$}\\}$. .

  * •

$O_{t+1}=\\{\text{agents that will have spent at least $h/2$ time steps in
strip $s$ by time $t+1$}\\}$.

The agents in $Y_{t+1}$ were all present at time $t^{\prime}=t+1-h/2$ as part
of the population of strip $s^{\prime}$ at that time. By the inductive
hypothesis, applied to $s^{\prime}$ at time $t^{\prime}$, we know that there
were at most $2\textnormal{{g}}n\sqrt{T}/h$ agents in $s^{\prime}$ at that
time. Let $P_{y}$ denote this population. The agents in $O_{t+1}$ were all
present at time $t^{\prime}=t+1-h$ as part of the population of strip
$s^{\prime}$ at that time. By the inductive hypothesis, applied to
$s^{\prime}$ at time $t^{\prime}$, we know that there were at most
$2\textnormal{{g}}n\sqrt{T}/h$ agents in $s^{\prime}$ at that time. Let
$P_{o}$ denote this population.

Let $P^{y}_{t^{\prime\prime},s}$ and $P^{y}_{t^{\prime\prime},s^{\prime}}$ be
the remainder of population $P_{y}$ at time $t^{\prime\prime}$ in strips $s$
and $s^{\prime}$, resp., for $t+1-\sqrt{T}\leq t^{\prime\prime}\leq t$. Also,
let $P^{y}_{t^{\prime\prime}}=P_{t^{\prime\prime},s}\cup
P_{t^{\prime\prime},s^{\prime}}$. Similarly, define
$P^{o}_{t^{\prime\prime},s}$, $P^{o}_{t^{\prime\prime},s^{\prime}}$ and
$P^{o}_{t^{\prime\prime}}$.

To this end, we need to compute lower bounds on the match rates.

By (8), the maximum of the number of men and number of women in the market is
at most $n\sqrt{T}$.

We divide the period $[t+1-h,t+1)$ into two phases; Phase 1,
$[t+1-h,t+1-h/2)$, and Phase $2$, $[t+1-h/2,t+1)$. We will show that the size
of $P^{y}_{t^{\prime\prime}}$ at the end of Phase $1$ is at most
$\textnormal{{g}}_{1}n\sqrt{T}/h$. We will specify $\textnormal{{g}}_{1}$
later. Then, at the start of Phase $2$ the size of $P^{o}\cup P^{y}$ is at
most $2\textnormal{{g}}n\sqrt{T}/h+\textnormal{{g}}_{1}n\sqrt{T}/h$. We claim
that after Phase $2$, the size of $P^{o}\cup P^{y}$ is at most
$\textnormal{{g}}n\sqrt{T}/h$.

We analyze Phase $1$ first. Consider the set $P^{o}_{t^{\prime\prime},s}$ and
time $t^{\prime\prime}\in[t+1-h,t+1-h/2)$.

By Lemma 6.3, at time $t^{\prime\prime}$ these matches remove, in expectation,
at least the following number of people from $P^{o}_{t^{\prime\prime},s}$:

$\displaystyle\frac{|P^{o}_{t^{\prime\prime},s}|^{2}-n^{2}/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}625}T}{2n\sqrt{T}}$
(18)

Similar bounds will hold for the sets $P^{o}_{t^{\prime\prime},s^{\prime}}$.
Notice that the total expected number of matches from
$P^{o}_{t^{\prime\prime}}$ is minimized if
$|P^{o}_{t^{\prime\prime},s}|=|P^{o}_{t^{\prime\prime},s^{\prime}}|$. Thus we
obtain that the size of $P^{o}_{t^{\prime\prime}}$ reduces, in expectation, by
at least

$\displaystyle\frac{|P^{o}_{t^{\prime\prime}}|^{2}}{4n\sqrt{T}}-\frac{n}{625T\sqrt{T}}.$
(19)

As in the analysis for the Type $1$ strip, we then give a high probability
bound. We have four sets of people, the men and the women in the sets
$P^{o}_{t^{\prime\prime},s^{\prime}}$ and $P^{o}_{t^{\prime\prime},s}$,
respectively. Suppose $\mu$ be the number of matches in one of these set at
time $t^{\prime\prime}$.

If $E[\mu]\geq\alpha n\sqrt{T}/h^{2}$, by Lemma 4.2,

$\displaystyle\Pr\Big{[}\mu\geq E[\mu](1-\epsilon)\Big{]}\geq
1-e^{-(E[\mu]\epsilon^{2})/2}\geq 1-e^{-\epsilon^{2}\alpha n\sqrt{T}/2h^{2}},$

Setting $\epsilon=\bigg{[}\frac{2h^{2}}{\alpha
n\sqrt{T}}\ln(T(\log_{2}\sqrt{T}+1)n^{2c+1})\bigg{]}^{\frac{1}{2}}$ yields
$\Pr\Big{[}\mu\geq E[\mu](1-\epsilon)\Big{]}\geq
1-\frac{1}{T(\log_{2}\sqrt{T}+1)n^{2c+1}}$.

Otherwise, $E[\mu]\leq\alpha n\sqrt{T}/h^{2}$, so by Lemma 4.2,

$\displaystyle\Pr\Big{[}\mu\geq E[\mu]-\theta\Big{]}\geq
1-e^{-(\theta^{2})/(2E[\mu])}\geq 1-e^{-(\theta^{2}h^{2})/(2\alpha
n\sqrt{T})},$

Setting $\theta=\bigg{[}\frac{2\alpha
n\sqrt{T}}{h^{2}}\ln(T(\log_{2}\sqrt{T}+1)n^{2c+1})\bigg{]}^{\frac{1}{2}}=\epsilon\alpha\frac{n\sqrt{T}}{h^{2}}$
yields $\Pr\Big{[}\mu\geq E[\mu]-\theta)\Big{]}\geq
1-\frac{1}{T(\log_{2}\sqrt{T}+1)n^{2c+1}}$.

For each of the four sets we can use one of the two bounds above.

We can set $\alpha=0.1,\epsilon\leq 0.1$ by imposing the constraints $c\geq
1,400\leq T\leq n,n\geq 125(2c+2.5)T\sqrt{T}\ln n$ which are provided by the
constraints in (6), $h\leq T/4$, and $\log_{2}\sqrt{T}+1\leq\sqrt{T}/4$ .

Let $\textnormal{{g}}(\cdot)$ be a real valued function. Suppose the size of
the set $P^{o}_{t^{\prime\prime}}$ at round $t^{\prime\prime}$ is smaller than
$\textnormal{{g}}(t^{\prime\prime})\cdot n\sqrt{T}/h$ and let
$X=\textnormal{{g}}(t^{\prime\prime})\cdot
n\sqrt{T}/h-|P^{o}_{t^{\prime\prime}}|$. If
$(1-\epsilon)\textnormal{{g}}(t^{\prime\prime})/(2h)\leq 1$, 666Note that this
is satisfied when $\textnormal{{g}}(t^{\prime\prime})\leq 21.5$ and
$h\geq\sqrt{T}=20$. then the size of the set $P^{o}_{t^{\prime\prime}+1}$ at
round $t^{\prime\prime}+1$ is at most

$\displaystyle\textnormal{{g}}(t^{\prime\prime})n\sqrt{T}/h-X-(1-\epsilon)\left[\frac{(\textnormal{{g}}(t^{\prime\prime})n\sqrt{T}/h-X)^{2}}{4n\sqrt{T}}-\frac{n}{625T\sqrt{T}}\right]+4\epsilon\alpha\frac{n\sqrt{T}}{h^{2}}$
$\displaystyle\vspace*{0.4in}\leq\textnormal{{g}}(t^{\prime\prime})n\sqrt{T}/h-(1-\epsilon)\left[\frac{(\textnormal{{g}}(t^{\prime\prime})n\sqrt{T}/h)^{2}}{4n\sqrt{T}}-\frac{n}{625T\sqrt{T}}\right]+4\epsilon\alpha\frac{n\sqrt{T}}{h^{2}}$
$\displaystyle\vspace*{0.4in}\leq\textnormal{{g}}(t^{\prime\prime})n\sqrt{T}/h-\frac{9\textnormal{{g}}(t^{\prime\prime})^{2}n\sqrt{T}}{40h^{2}}+\frac{9n}{6250T\sqrt{T}}+\frac{n\sqrt{T}}{25h^{2}}$
$\displaystyle\vspace*{0.4in}\leq
n\sqrt{T}/h\left[\textnormal{{g}}(t^{\prime\prime})-\frac{1}{h}\left(\frac{9\textnormal{{g}}(t^{\prime\prime})^{2}}{40}-0.041\right)\right].$

The last inequality uses the constraint that $h\leq T/4$.

Let $\textnormal{{g}}(t+1-h)=2\textnormal{{g}}$ and
$\textnormal{{g}}(t^{\prime\prime}+1)=\left[\textnormal{{g}}(t^{\prime\prime})-\frac{1}{h}\left(\frac{9\textnormal{{g}}(t^{\prime\prime})^{2}}{40}-0.041\right)\right]$
for $t^{\prime\prime}\in[t+1-h,t+1-h/2)$, then we have shown that the size of
the set $P^{o}_{t^{\prime\prime}}$ at round $t+1-h/2$ is at most
$\textnormal{{g}}(t+1-h/2)\cdot n\sqrt{T}/h$. One way to solve
$\textnormal{{g}}(\cdot)$ by using a differential equation. Consider the
differential equation
$\texttt{d}\bar{\textnormal{{g}}}/\texttt{d}t=-\frac{1}{h}\left(\frac{9\bar{\textnormal{{g}}}^{2}}{40}-0.041\right)$
and $\bar{\textnormal{{g}}}(t+1-h)=2\textnormal{{g}}$. Note that
$\bar{\textnormal{{g}}}(t^{\prime\prime})\geq\textnormal{{g}}(t^{\prime\prime})$
for all $t^{\prime\prime}\in[t+1-h,t+1-h/2]$. 777Suppose it is not true. Since
$\bar{\textnormal{{g}}}(t+1-h)=\textnormal{{g}}(t+1-h)=2\textnormal{{g}}$,
there exists a $t^{\prime}$, such that
$\bar{\textnormal{{g}}}(t^{\prime})\geq\textnormal{{g}}(t^{\prime})$ and
$\bar{\textnormal{{g}}}(t^{\prime}+1)<\textnormal{{g}}(t^{\prime}+1)$. Then,
there exist a $t^{\prime\prime}\in[t^{\prime},t^{\prime}+1)$ such that
$\bar{\textnormal{{g}}}(t^{\prime\prime})=\textnormal{{g}}(t^{\prime})$. After
time $t^{\prime\prime}$,
$\texttt{d}\bar{\textnormal{{g}}}(t^{\prime\prime})/\texttt{d}t\geq-\frac{1}{h}\left(\frac{9\bar{\textnormal{{g}}(t^{\prime\prime})}^{2}}{40}-0.041\right)=\textnormal{{g}}(t^{\prime}+1)-\textnormal{{g}}(t^{\prime})$.
Therefore,
$\bar{\textnormal{{g}}}(t^{\prime}+1)=\bar{\textnormal{{g}}}(t^{\prime\prime})+\int_{s=t^{\prime\prime}}^{t^{\prime}+1}\texttt{d}\bar{\textnormal{{g}}}(s)\geq\textnormal{{g}}(t^{\prime})+\int_{s=t^{\prime\prime}}^{t^{\prime}+1}[\textnormal{{g}}(t^{\prime}+1)-\textnormal{{g}}(t^{\prime})]\texttt{d}s\geq\textnormal{{g}}(t^{\prime}+1)$,
which contradicts the assumption.

Therefore, in order to prove
$\textnormal{{g}}(t+1-h/2)\leq\textnormal{{g}}_{1}$, we only need
$\bar{\textnormal{{g}}}(t+1-h/2)\leq\textnormal{{g}}_{1}$. We look at the
total time for $\bar{\textnormal{{g}}}$ to reduce from the value
$\textnormal{{g}}(t+1-h)=2\textnormal{{g}}$ to $\textnormal{{g}}_{1}$:
$\texttt{d}t=-h\texttt{d}\bar{\textnormal{{g}}}/(\frac{9\bar{\textnormal{{g}}}^{2}}{40}-0.041)$.
Therefore, the total time is
$\int_{\bar{\textnormal{{g}}}=\textnormal{{g}}_{1}}^{2\textnormal{{g}}}h\texttt{d}\bar{\textnormal{{g}}}/(\frac{9\bar{\textnormal{{g}}}^{2}}{40}-0.041)<=\int_{\bar{\textnormal{{g}}}=\textnormal{{g}}_{1}}^{2\textnormal{{g}}}h\texttt{d}\bar{\textnormal{{g}}}/(\frac{9\bar{\textnormal{{g}}}^{2}}{40}-0.041\frac{\bar{\textnormal{{g}}}^{2}}{\textnormal{{g}}_{1}^{2}})=(h/(\frac{9}{40}-\frac{0.041}{\textnormal{{g}}_{1}^{2}}))(1/\textnormal{{g}}_{1}-1/(2\textnormal{{g}}))$.
To have this be at most $h/2$ (the total duration of Phase $1$), we only need
$2(1/\textnormal{{g}}_{1}-1/(2\textnormal{{g}}))\leq
9/40-0.041/(\textnormal{{g}}_{1})^{2}$, which is satisfied by letting
$\textnormal{{g}}=7.5$ and $\textnormal{{g}}_{1}=6.5$.

We consider Phase $2$ next. Consider the set $P^{o}_{t^{\prime\prime},s}\cup
P^{y}_{t^{\prime\prime},s}$ and time $t^{\prime\prime}\in[t+1-h/2,t+1)$. The
analysis is exactly the same as that for Phase $1$. By Lemma 6.3, these
matches remove, in expectation, at least the following number of people from
$P^{o}_{t^{\prime\prime},s}\cup P^{y}_{t^{\prime\prime},s}$:

$\displaystyle\frac{|P^{o}_{t^{\prime\prime},s}\cup
P^{y}_{t^{\prime\prime},s}|^{2}-n^{2}/625T}{2n\sqrt{T}}$ (20)

Similar bounds will hold for the set $P^{o}_{t^{\prime\prime},s^{\prime}}\cup
P^{y}_{t^{\prime\prime},s^{\prime}}$. We also reduce the size of
$P^{o}_{t^{\prime\prime}}\cup P^{y}_{t^{\prime\prime}}$, in expectation, by at
least

$\displaystyle\frac{|P^{o}_{t^{\prime\prime}}\cup
P^{y}_{t^{\prime\prime}}|^{2}}{3n\sqrt{T}}-\frac{n}{625T\sqrt{T}}.$ (21)

Then, as in Phase $1$, suppose the size of the set
$P^{o}_{t^{\prime\prime}}\cup P^{y}_{t^{\prime\prime}}$ at time
$t^{\prime\prime}$ is smaller than $g(t^{\prime\prime})n\sqrt{T}/h$ and let
$X=g(t^{\prime\prime})n\sqrt{T}/h-|P^{o}_{t^{\prime\prime}}\cup
P^{y}_{t^{\prime\prime}}|$. If $(1-\epsilon)g(t^{\prime\prime})/(2h)\leq 1$,
then the size of the set $P^{o}_{t^{\prime\prime}}\cup
P^{y}_{t^{\prime\prime}}$ at round $t^{\prime\prime}+1$ is at most

$\displaystyle
n\sqrt{T}/h\left[g(t^{\prime\prime})-\frac{1}{h}\left(\frac{9g(t^{\prime\prime})^{2}}{40}-0.041\right)\right].$

Let $\textnormal{{g}}(t+1-h/2)=2\textnormal{{g}}+\textnormal{{g}}_{1}$ and
$g(t^{\prime\prime}+1)=\left[g(t^{\prime\prime})-\frac{1}{h}\left(\frac{9\textnormal{{g}}(t^{\prime\prime})^{2}}{40}-0.041\right)\right]$
for $t^{\prime\prime}\in[t+1-h/2,t+1)$, then we have shown that the size of
the set $P^{o}_{t^{\prime\prime}}\cup P^{y}_{t^{\prime\prime}}$ at round $t+1$
is at most $\textnormal{{g}}(t+1)\cdot n\sqrt{T}/h$. We consider the same
differential equation here,
$\texttt{d}\bar{\textnormal{{g}}}/\texttt{d}t=-\frac{1}{h}\left(\frac{9\bar{\textnormal{{g}}}^{2}}{40}-0.041\right)$,
with $\bar{\textnormal{{g}}}(t+1-h/2)=2\textnormal{{g}}+\textnormal{{g}}_{1}$.
Note that
$\bar{\textnormal{{g}}}(t^{\prime\prime})\geq\textnormal{{g}}(t^{\prime\prime})$
for all $t^{\prime\prime}\in[t+1-h/2,t+1]$.

Therefore, in order to prove $\textnormal{{g}}(t+1)\leq\textnormal{{g}}$, we
only need $\bar{\textnormal{{g}}}(t+1)\leq\textnormal{{g}}$. We look at the
total time for $\bar{\textnormal{{g}}}$ to reduce from the value $2g+g_{1}$ to
g:
$\texttt{d}t=-h\texttt{d}\bar{\textnormal{{g}}}/(\frac{9\bar{\textnormal{{g}}}^{2}}{40}-0.041)$.
Therefore, the total time is
$\int_{\bar{\textnormal{{g}}}=\textnormal{{g}}}^{2\textnormal{{g}}+\textnormal{{g}}_{1}}h\cdot\texttt{d}\bar{\textnormal{{g}}}/(\frac{9\bar{\textnormal{{g}}}^{2}}{40}-0.041)<=\int_{\bar{\textnormal{{g}}}=\textnormal{{g}}}^{2\textnormal{{g}}+\textnormal{{g}}_{1}}h\cdot\texttt{d}\bar{\textnormal{{g}}}/(\frac{9\bar{\textnormal{{g}}}^{2}}{40}-0.041\frac{\bar{\textnormal{{g}}}^{2}}{\textnormal{{g}}^{2}})=(h/(\frac{9}{40}-\frac{0.041}{\textnormal{{g}}^{2}}))(1/\textnormal{{g}}-1/(2\textnormal{{g}}+\textnormal{{g}}_{1}))$.
To have this be at most $h/2$ (the total duration of Phase $2$), we only need
$2(1/\textnormal{{g}}-1/(2\textnormal{{g}}+\textnormal{{g}}_{1}))\leq
9/40-0.041/(\textnormal{{g}})^{2}$, which is also satisfied by letting
$\textnormal{{g}}=7.5$ and $\textnormal{{g}}_{1}=6.5$.

Finally, as there are $\log_{2}\sqrt{T}+1$ Type $2$ strips, and, for each Type
$2$ strip, we consider $h\leq T/4$ steps, the success probability is at least
$1-\frac{T/4\cdot
4\cdot(\log_{2}\sqrt{T}+1)}{T(\log_{2}\sqrt{T}+1)n^{2c+1}}\leq
1-\frac{1}{n^{2c+1}}$.

∎

###### Proof.

(Of Theorem 6.6.) Let’s call the bottommost Type $2$ strip $s$ and the Type
$2$ strip immediately above it strip $s^{\prime}$. Any agent in the population
in $s$ at time $t+1$ must belong to one of the following categories:

  * •

The agent was present in $s^{\prime}$ at time $t+1-T/4$.

  * •

The agent was present in $s^{\prime}$ at time $t+1-T/2$.

However, by our inductive hypothesis $H(t)$, we know that at all time steps
before $t+1$, the size of $s$ was always less than
$\frac{7.5n\sqrt{T}}{\text{height of strip $s$}}\leq 4\cdot 7.5n/\sqrt{T}.$

Thus, the size of $s$ at time $t+1$ is bounded by $8\cdot 7.5n/\sqrt{T}\leq
60n/\sqrt{T}$, which concludes the proof. ∎

###  C.6 Bound on the Imbalance

###### Proof.

(Of Claim 6.4). The expected number of matches at time $\tau$ between men in
diagonal $d_{i}$ and women in diagonal $d_{j}$ is

$\frac{(2A_{i}+I_{i}+X_{i})(2A_{j}-I_{j}-X_{j})}{4R}.$

Similarly, the expected number of women in $d_{i}$ that match with men in
$d_{j}$ is

$\frac{(2A_{i}-I_{i}-X_{i})(2A_{j}+I_{j}+X_{j})}{4R}.$

Thus $I^{\prime}(d_{i},\tau)$ is given by:

$\displaystyle I_{i}+X_{i}-\sum_{d_{j}\in
s}\Big{[}\frac{(2A_{i}+I_{i}+X_{i})(2A_{j}-I_{j}-X_{j})}{4R}-\frac{(2A_{i}-I_{i}-X_{i})(2A_{j}+I_{j}+X_{j})}{4R}\Big{]}$
$\displaystyle~{}~{}=I_{i}+X_{i}-\sum_{d_{j}\in
s}\Big{[}X_{i}\frac{(2A_{j}-I_{j}-X_{j})}{4R}-X_{j}\frac{(2A_{i}-I_{i}-X_{i})}{4R}+I_{i}\frac{(2A_{j}-I_{j}-X_{j})}{4R}-I_{j}\frac{(2A_{i}-I_{i}-X_{i})}{4R}\Big{]}.$

∎

###### Proof.

(Of Claim 6.8.) We first give a high probability bound on $\sum
Y(d_{i},\tau)$. Let $m(d_{i},\tau)$ be the number of men entering the market
on diagonal $d_{i}$ at time $\tau$. Note that $d_{T}$ is the last Type $1$
diagonal. Let $d_{r}$ be a diagonal in Type $1$ strip $s$; then,

$\displaystyle\operatorname{Pr}\bigg{[}\Big{|}\sum_{r\leq i\leq
T}Y(d_{i},\tau)\Big{|}>\Delta\bigg{]}=\operatorname{Pr}\bigg{[}\Big{|}\sum_{r\leq
i\leq T}m(d_{i},\tau)-(T-r+1)\cdot\frac{n}{2T}\Big{|}>\Delta/2\bigg{]}.$

Note that

$\displaystyle\operatorname{Pr}\bigg{[}\Big{|}\sum_{r\leq i\leq
T}m(d_{i},\tau)-(T-r+1)\cdot\frac{n}{2T}\Big{|}>\Delta/2\bigg{]}$
$\displaystyle\leq
2\exp\Big{[}-\Delta^{2}/\Big{(}3\cdot(T-r+1)\cdot\frac{n}{2T}\Big{)}\Big{]}\leq
2\exp\Big{[}-\Delta^{2}/\Big{(}\frac{3n}{2}\Big{)}\Big{]}.$

The last inequality follows as $T-r+1\leq T$. Letting
$\Delta=\sqrt{\frac{3n}{2}\ln\left(2Tn^{3c+1}\right)}$ yields

$\displaystyle\operatorname{Pr}\bigg{[}\Big{|}\sum_{r\leq i\leq
T}Y(d_{i},\tau)\Big{|}>\sqrt{\frac{3n}{2}\ln\left(2Tn^{3c+1}\right)}\bigg{]}\leq\frac{1}{Tn^{3c+1}}.$

Therefore, with probability at least $\frac{1}{n^{3c+1}}$, for all $r$ such
that $d_{r}$ is a diagonal in a Type $1$ strip, $\left|\sum_{r\leq i\leq
T}Y(d_{i},\tau)\right|\leq\sqrt{\frac{3n}{2}\ln\left(2Tn^{3c+1}\right)}$.

With this result in hand, we prove the claim as follows. Let $d_{r(s)}$ be the
rightmost (lowest index) diagonal in $s$ and $d_{l(s)}$ be the leftmost
(highest index) diagonal in $s$. Let $w_{i}=\sum_{j\geq
r(s)}Y(d_{i},\tau,d_{j},\tau^{\prime})/Y(d_{i},\tau)$. Let’s consider
$\sum_{d_{i}\in s^{\prime};j\geq
r(s)}Y(d_{i},\tau,d_{j},\tau^{\prime})=\sum_{d_{i}\in s^{\prime}}w_{i}\cdot
Y(d_{i},\tau)$. By Claim 6.5, $w_{i}\leq w_{k}$, for $i<k$. Thus,

$\displaystyle\Big{|}\sum_{d_{i};j\geq
r(s)}Y(d_{i},\tau,d_{j},\tau^{\prime})\Big{|}=\Big{|}\sum_{i=1}^{T}w_{i}\cdot
Y(d_{i},\tau)\Big{|}\leq w_{T}\max_{r\leq T}\big{|}\sum_{r\leq i\leq
T}Y(d_{i},\tau)\Big{|}\leq\sqrt{\frac{3n}{2}\ln\left(2Tn^{3c+1}\right)}.$

Finally,

$\displaystyle\Big{|}\sum_{d_{i};d_{j}\in
s}Y(d_{i},\tau,d_{j},\tau^{\prime})\Big{|}=\Big{|}\sum_{d_{i};j\geq
r(s)}Y(d_{i},\tau,d_{j},\tau^{\prime})-\sum_{d_{i};j\geq
l(s)+1}Y(d_{i},\tau,d_{j},\tau^{\prime})\Big{|}\leq
2\sqrt{\frac{3n}{2}\ln\left(2Tn^{3c+1}\right)},$

which completes the proof. ∎

###### Proof.

(Of Claim 6.10.) We begin by bounding $\sum_{j:d_{j}\in
s}(2A_{j}-I_{j}-X_{j})/4R$ for any Type $2$ strip $s$.

$\displaystyle\sum_{j:d_{j}\in
s}\frac{(2A_{j}-I_{j}-X_{j})}{4R}\leq\frac{1}{2}\frac{\frac{3.75n\sqrt{T}}{H}+n/50\sqrt{T}}{\frac{n\sqrt{T}}{6}}<\frac{23}{2H}\hskip
14.45377pt\text{(as $\sqrt{T}\geq 26$ by
constraint~{}\ref{eqn::constraints})}.$ (22)

Let $s$ have height $H$.

Consider $X(d,\tau,d^{\prime},\tau^{\prime})$. If $d^{\prime}$ is in a Type
$2$ strip then by (22) at most $\frac{23}{2H}$ of it disperses to some
location in the same strip and at least $1-\frac{23}{2H}$ of it moves down
distance one. This implies that, within $H$ time, a Type $2$ strip loses at
least $e^{-23/2}$ of the $X(d,\tau,d^{\prime},\tau^{\prime})$ that had been
present within it at time $\tau^{\prime}$. Let $K_{2}=e^{12}\ln 2$. Therefore,
by time $\tau^{\prime}+K_{2}H$ ($\leq\tau^{\prime}K_{2}T/4$) at least half of
the $X(d,\tau,d^{\prime},\tau^{\prime})$ in a Type $2$ strip has moved out of
the strip.

Similarly, we can now carry out the same kind of argument for the Type $2$
strips. After $2e^{2}(\ln 2)\sqrt{T}(\sqrt{T}+\log_{2}(2n^{k}))$ time there is
at most $\frac{1}{2n^{k}}$ fraction of $X(d,\tau)$ in the Type $1$ strips. We
focus on the remaining $1-\frac{1}{2n^{k}}$ portion of $X(d,\tau)$ which has
already entering the type 2 strips. Number the Type $2$ strips from top to
bottom888Our argument doesn’t involve the last Type $2$ strip, so we will end
at the second to last strip.. Now consider $\gamma$ as a distribution of the
rest of the $X(d,\tau)$ where $\gamma_{i}$ is the fraction of $X(d,\tau)$ in
strip number $i$. Recall that there are $\log_{2}(\sqrt{T})$ Type $2$ strips
other than the bottom Type $2$ strip. We consider the worst case where all the
remaining $(1-\frac{1}{2n^{k}})\cdot X(d,\tau)$ starts out at the topmost Type
$2$ strip. Define a potential function
$\phi(\gamma)=\sum_{i=1}^{\log_{2}\sqrt{T}+1}\gamma_{i}\cdot
2^{(\log_{2}\sqrt{T})-i+1}$. For the remaining $(1-\frac{1}{2n^{k}})\cdot
X(d,\tau)$, The initial potential is at most $\sqrt{T}$. Every $K_{2}T/4$ time
steps, the potential decreases by at least $1/4$. Therefore, after
$\frac{1}{\log_{2}(4/3)}K_{2}T/4\log_{2}(2n^{k}\sqrt{T})$ time steps, the
potential would have reduced to at most $\frac{1}{2n^{k}}$.

There is also $\frac{1}{2n^{k}}$ fraction which might still be in the Type $1$
strips. Thus the fraction of $X(d,\tau)$ in any strip other than the
bottommost Type 2 strip after
$\frac{1}{\log_{2}(4/3)}K_{1}\sqrt{T}(\sqrt{T}+\log_{2}(2n^{k}))+$
$\frac{1}{\log_{2}(4/3)}K_{2}T/4\log_{2}(2n^{k}\sqrt{T})$ time is at most
$\frac{1}{n^{k}}$. ∎

###### Proof.

(Final Calculation in Theorem 6.7)

As $\kappa=\frac{e^{2}\ln
2}{\log_{2}(4/3)}\sqrt{T}(\sqrt{T}+\log_{2}(2n^{k}))+\frac{e^{12}\ln
2}{4\log_{2}(4/3)}T\log_{2}(2n^{k}\sqrt{T})\leq
12.35(T+\sqrt{T}+(c+4)\sqrt{T}\log_{2}n)+\frac{e^{12}}{2}(T+(c+4)T\log_{2}n+0.5T\log_{2}T)$,
the total imbalance is at most

$\displaystyle\frac{15T}{n^{3}}+$
$\displaystyle\Big{[}12.35(T+\sqrt{T}+(c+4)\sqrt{T}\log_{2}n)+\frac{e^{12}}{2}(T+(c+4)T\log_{2}n+0.5T\log_{2}T)\Big{]}\cdot$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\bigg{(}192\sqrt{\frac{n\ln(4n^{3c+1}(T^{2}/32+T/8)N)}{\sqrt{T}}}+2\sqrt{\frac{3n}{2}\ln\left(2Tn^{3c+1}\right)}\bigg{)}.$

In order to make it smaller than $\frac{n}{25\sqrt{T}}$, we only need that

$\displaystyle\frac{375T\sqrt{T}}{n^{3}}+$
$\displaystyle\Big{[}309(T+\sqrt{T}+(c+4)\sqrt{T}\log_{2}n)+\frac{25e^{12}}{2}(T+(c+4)T\log_{2}n+0.5T\log_{2}T)\Big{]}\cdot$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\bigg{(}192\sqrt{\sqrt{T}\ln[4n^{3c+1}(T^{2}/32+T/8)N]}+2\sqrt{\frac{3T}{2}\ln\left(2Tn^{3c+1}\right)}\bigg{)}\leq\sqrt{n}.$

As $375T\sqrt{T}/n^{3}\leq 0.0012\sqrt{n}$ from the constraint $n\geq T\geq
676$, we need

$\displaystyle\Big{[}309(T+\sqrt{T}+(c+4)\sqrt{T}\log_{2}n)+\frac{25e^{12}}{2}(T+(c+4)T\log_{2}n+0.5T\log_{2}T)\Big{]}\cdot$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\bigg{(}192\sqrt{\sqrt{T}\ln[4n^{3c+1}(T^{2}/32+T/8)N]}+2\sqrt{\frac{3T}{2}\ln\left(2Tn^{3c+1}\right)}\bigg{)}\leq
0.9988\sqrt{n}.$ (23)

In addition, as $n\geq T\geq 676$,

$\displaystyle\Big{[}309(T+\sqrt{T}+(c+4)\sqrt{T}\log_{2}n)+\frac{25e^{12}}{2}(T+(c+4)T\log_{2}n+0.5T\log_{2}T)\Big{]}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\leq(86.61+12.876c+57.62e^{12}+12.5e^{12}c)T\log_{2}n,$
(24)

and, as $n\geq T\geq 676$ and $n\geq N$,

$\displaystyle\bigg{(}192\sqrt{\sqrt{T}\ln[4n^{3c+1}(T^{2}/32+T/8)N]}+2\sqrt{\frac{3T}{2}\ln\left(2Tn^{3c+1}\right)}\bigg{)}\leq
42\sqrt{T(3c+4)\ln n}.$ (25)

By inequalities (23), (24), and (25),

$\displaystyle(86.61+12.876c+57.62e^{12}+12.5e^{12}c)T\log_{2}n\cdot
42\sqrt{T(3c+4)\ln n}\leq 0.9988\sqrt{n}.$

Therefore,
$n\geq(3654+2436e^{12}+546(e^{12}+1)c)^{2}(3c+4)T^{3}(\log_{2}n)^{2}\ln n$
suffices.

∎

###  C.7 Initialization

###### Proof.

(Of Theorem 6.8.) At any point in the first $\sqrt{T}$ time steps:

  * •

The total population in the entire matching pool is clearly less than
$n\sqrt{T}<nN$, as only these many agents could have even entered the matching
pool.

  * •

In any single Type $1$ strip,

$\operatorname{Pr}\left[{\text{Number of agents that entered the strip from
the top}\leq\frac{n\sqrt{T}(1+\epsilon)}{\sqrt{T}}}\right]\geq
1-e^{-\frac{n\epsilon^{2}}{3}}.$

However the agents that enter a Type $1$ strip during the first $\sqrt{T}$
time must either have entered from the top or they could have entered at the
top boundary of the previous strip. Thus, by a union bound,

$\operatorname{Pr}\left[{\text{Number of agents that entered any Type $1$
strip}\leq 2n(1+\epsilon)}\right]\geq 1-\sqrt{T}e^{-\frac{n\epsilon^{2}}{3}}.$

So by setting $\epsilon=\sqrt{\frac{3}{n}\ln(n^{c+1}\sqrt{T})}$, and imposing
the constraints $c\geq 1$, $T\leq n$, and $n\geq 35(c+2)\ln n$ that guarantee
that $\epsilon<0.3$ (from (6)), we obtain that with probability
$1-\frac{1}{n^{c+1}}$ every Type $1$ strip has a population $<2.6n$.

  * •

The agents in the first Type $2$ strip after $\sqrt{T}$ time steps (the only
Type $2$ strip with any population after $\sqrt{T}$ time) could only be those
agents that entered the leftmost two Type $1$ strips from the top. However the
previous bound already guarantees that this number is also $<2.6n$.

  * •

Also, the population in the bottom most Type 2 strip will be 0.

  * •

Now it remains only to show that in each of the strips, except possibly the
bottommost Type 2 strip, $|\text{number of men}-\text{number of
women}|\leq\frac{n}{25\sqrt{T}}$.

We will follow the proof of Theorem 6.7, though the proof will be simplified
by the fact that we only need to consider $\sqrt{T}$ many time steps.

We divide each strip into thin diagonals of width $1$. Let the diagonal
include the bottom but not the top boundary. Notice that for each value, a
diagonal contains at most one grid point.

As in Theorem 6.7, we introduce the following notation w.r.t. diagonal $d$ at
time step $\tau$, where we are conditioning on the outcome of step $\tau-1$.

$\displaystyle I(d,\tau)$ $\displaystyle=E[(\text{number of men at time
$\tau$}-\text{number of women at time $\tau$})]$ $\displaystyle X(d,\tau)$
$\displaystyle=(\text{number of men matching at time $\tau$}-\text{number of
women matching at time $\tau$})$ $\displaystyle\hskip
14.45377pt-E[(\text{number of men matching at time $\tau$}-\text{number of
women matching at time $\tau$})]$ $\displaystyle Y(d,\tau)$
$\displaystyle=\text{number of men entering at time $\tau$}-\text{number of
women entering at time $\tau$}$ $\displaystyle A(d,\tau)$
$\displaystyle=(\text{number of men matching at time $\tau$}+\text{number of
women matching at time $\tau$})/2.$

$I(d,\tau)$ is measured after the entry of the new agents at time $\tau$ but
prior to the match for this step. Also, note that $Y(d,\tau)=0$ if $d$ is in a
Type $2$ strip.

In addition, observe that the imbalance $\operatorname{Imb}(s)$ at the start
of step $t$ equals $\sum_{d\in s}I(d,t)$.

We observe that a match between two agents in distinct diagonals of the same
strip will increment the $(\text{number of men }-\text{ number of women})$ in
one diagonal and decrement it in the other. Thus there is a zero net change
over all the diagonals in the strip due to the matches. However, as the agents
all age by 1 unit during a step, some agents enter the strip and some leave,
which can cause changes to the imbalance within a strip. However, the entry of
new agents can introduce new imbalances. We will need to understand more
precisely how these imbalances evolve.

It is convenient to number the diagonals as $d_{1},d_{2},d_{3},\ldots$, in
right to left order.

We recall the following claims from the proof of Theorem 6.7.

######  Claim C.1.

Let $d_{i}$ and $d_{j}$ be two diagonals in the same strip $s$. For brevity,
let $I_{i}\triangleq I(d_{i},\tau-1)$, $I_{j}\triangleq I(d_{j},\tau-1)$,
$A_{i}\triangleq A(d_{i},\tau-1)$, $A_{j}\triangleq A(d_{j},\tau-1)$,
$X_{i}\triangleq X(d_{i},\tau-1)$, $X_{j}\triangleq X(d_{j},\tau-1)$. Finally,
let $R$ denote the maximum of the total number of men and the total number of
women in the system at time $\tau-1$. Then the new imbalance on diagonal
$d_{i}$, prior to every unmatched agent adding 1 to their age (which causes
the agents on $d_{i}$ to move to $d_{i+1}$), denoted by
$I^{\prime}(d_{i},\tau)$, is given by:

$\displaystyle I^{\prime}(d_{i},\tau)=$
$\displaystyle~{}~{}~{}~{}I_{i}+X_{i}-\sum_{d_{j}\in
s}\Big{[}X_{i}\frac{(2A_{j}-I_{j}-X_{j})}{4R}-X_{j}\frac{(2A_{i}-I_{i}-X_{i})}{4R}+I_{i}\frac{(2A_{j}-I_{j}-X_{j})}{4R}-I_{j}\frac{(2A_{i}-I_{i}-X_{i})}{4R}\Big{]};$
$\displaystyle\text{~{}~{}and~{}~{}}I(d_{i},\tau)=I^{\prime}(d_{i-1},\tau-1)+Y(d,\tau).$

$X(d,\tau)$ and $Y(d,\tau)$ are generated at diagonal $d$ at time $\tau$ and,
by Claim C.1, at any subsequent time step, $X(d,\tau)$ and $Y(d,\tau)$ will be
redistributed over other diagonals.

  1. 1.

Due to the expected matching at time $\tau^{\prime}\geq\tau$, each $X(d,\tau)$
and $Y(d,\tau)$ spreads to other diagonals in the same strip.

  2. 2.

At the end of time step $\tau^{\prime}$ the portions of $X(d,\tau)$ and
$Y(d,\tau)$ present on diagonal $d_{i}$ move to diagonal $d_{i+1}$.

Building on these observations, we will show our bound on the imbalance by
bounding the total contribution from $X(\cdot,\tau)$ and $Y(\cdot,\tau)$ to
strip $s$ at time $\tau^{\prime}$.

Notice that $\sum_{d_{i}\in s}I^{\prime}(d_{i},\tau)=\sum_{d_{i}\in
s}I(d_{i},\tau-1)$, for the coefficients multiplying $X_{i}$ cancel, as they
also do for $I_{i}$. Thus we can think of this process as redistributing the
imbalance, but not changing the total imbalance.

Over time an imbalance $X(d_{i},\tau)$ will be redistributed over many
diagonals. We write $X(d_{i},\tau,d_{j},\tau^{\prime})$ to denote the portion
of $X(d_{i},\tau)$ on diagonal $d_{j}$ at time $\tau^{\prime}$. $d_{j}$ need
not be in the same strip as $d_{i}$. Note that
$\sum_{d_{j}}X(d_{i},\tau,d_{j},\tau^{\prime})=X(d_{i},\tau)$ for all
$\tau^{\prime}\geq\tau$. $Y(d_{i},\tau,d_{j},\tau^{\prime})$ is defined
analogously.

For the purposes of the following claim, we treat the final strip as a single
diagonal, and in addition ignore the fact that people depart at age $T$ (which
means that once an imbalance appears in this strip it remains there). The
reason this strip is different is that it covers the whole of the bottom
boundary and so is the only strip from which people leave the system by aging
out.

######  Claim C.2.

For all $\ell$, for all $i<k$, and for all $\tau^{\prime}\geq\tau$,
$\big{|}\sum_{j>\ell}X(d_{i},\tau,d_{j},\tau^{\prime})\big{|}\leq\big{|}\sum_{j>\ell}X(d_{k},\tau,d_{j},\tau^{\prime})\big{|}$.
The same property holds for the $Y(d_{i},\tau,d_{j},\tau^{\prime})$.

Later, we will show a common bound $B$ on the sums $\big{|}\sum_{i\leq j\leq
k}X(d_{j},\tau)\big{|}$, which holds for all $d_{i}$ and $d_{k}$ in the same
strip and all $\tau$.

With this bound and Claim C.2 in hand, for each strip $s$, we can bound the
contribution of the $X(d_{i},\tau,d_{j},\tau^{\prime})$ summed over all
$d_{i}$ and over $d_{j}\in s$ by $2B$.

######  Claim C.3.

For all $\tau^{\prime}\geq\tau$, for every strip $s$,
$\big{|}\sum_{d_{i};d_{j}\in s}X(d_{i},\tau,d_{j},\tau^{\prime})\big{|}\leq
2B$.

This allows us to obtain the bound the imbalance in a strip $s$ at any time
$\tau^{\prime}\leq\sqrt{T}$ by considering the contributions of
$\big{|}\sum_{d_{i};d_{j}\in s}X(d_{i},\tau,d_{j},\tau^{\prime})\big{|}$ and
$\big{|}\sum_{d_{i};d_{j}\in s}Y(d_{i},\tau,d_{j},\tau^{\prime})\cdot
Y(d_{i},\tau)\big{|}$ at all possible previous times (which is at most
$\sqrt{T}$ time).

Regarding the contribution of Y, we also have the following claim,

######  Claim C.4.

With probability at least $1-\frac{1}{n^{2c+1}}$, for all
$\tau^{\prime}\geq\tau$, for every strip $s$, $\big{|}\sum_{d_{i};d_{j}\in
s}Y(d_{i},\tau,d_{j},\tau^{\prime})\big{|}\leq
2\sqrt{\frac{3n}{2}\ln\left(2Tn^{3c+1}\right)}$.

Thus,

$\displaystyle|\operatorname{Imb}(s,\tau^{\prime})|\leq\Big{[}2B+2\sqrt{\frac{3n}{2}\ln\left(2Tn^{3c+1}\right)}\Big{]}\sqrt{T}$
(26)

We now calculate $B$.

######  Claim C.5.

For any diagonal $d_{j}$ and any $d_{i}$ and $d_{k}$ that lie in the same
strip, at any time $\tau\leq\sqrt{T}$,

$\Pr\bigg{[}\Big{|}\sum_{i\leq j\leq k}X(d_{j},\tau)\Big{|}\geq
2\sqrt{\frac{n(1+\epsilon)^{2}\sqrt{3}\ln(16T\sqrt{T}(\sqrt{T}+1)n^{c+1})}{0.48\sqrt{T}}}\bigg{]}\leq\frac{1}{4n^{c+1}}.$

###### Proof.

The agents enter with one of $T$ values chosen uniformly at random and are
equally likely to be men or women. Hence, for all $\tau\leq\sqrt{T}$ time
steps, for each value $v$,

$\operatorname{Pr}\Big{[}\text{At most $\frac{n(1+\epsilon)}{2T}$ men enter
with value $v$}\Big{]}\geq 1-\tau Te^{-\frac{\epsilon^{2}n}{6T}}\geq
1-T\sqrt{T}e^{-\frac{\epsilon^{2}n}{6T}}.$

Call this event $\mathcal{E}_{m}$. Similarly,

$\operatorname{Pr}\Big{[}\text{At most $\frac{n(1+\epsilon)}{2T}$ men enter
with value $v$}\Big{]}\geq 1-\tau Te^{-\frac{\epsilon^{2}n}{6T}}\geq
1-T\sqrt{T}e^{-\frac{\epsilon^{2}n}{6T}}.$

Call this event $\mathcal{E}_{w}$. Henceforth we condition on
$\mathcal{E}_{m}$ and $\mathcal{E}_{w}$.

Consider some time $\tau$. At this time, let $M=\max\\{\text{total number of
men},\text{total number of women}\\}$ while $m=\text{number of men in strip
$s$}$ and $w=\text{number of men in strip $s$}$. Using Lemmas 4.2 and 4.1, we
obtain the following bound on the deviation from the expected number of the
number of men in $s$ matched in a given time step, $\tau$:

$\displaystyle\Pr\bigg{[}\Big{|}\begin{array}[]{l}\text{number of men
matched}\\\ \hskip 14.45377pt-E[\text{number of men
matched}]\end{array}\Big{|}>\frac{mw\delta}{M}\bigg{]}\leq
2e^{-{mw\delta^{2}}/{3M}}.$ (27)

We will later prove the following claim,

######  Claim C.6.

For all time $0\leq t\leq\sqrt{T}$, $0.12nt\leq M\leq nt$ for all
$t\leq\sqrt{T}$, with probability at least $1-\frac{1}{5n^{2c+1}}$.

Call this event $\mathcal{E}_{M}$. Henceforth, we further condition on
$\mathcal{E}_{M}$.

Thus, from equation 27, we obtain

$\displaystyle\Pr\bigg{[}\Big{|}\begin{array}[]{l}\text{number of men
matched}\\\ \hskip 14.45377pt-E[\text{number of men
matched}]\end{array}\Big{|}>\frac{mw\delta}{0.12nt}\bigg{]}\leq
2e^{-{mw\delta^{2}}/{3nt}}.$

Setting $\delta=\Big{[}\frac{3nt}{mw}\ln(n^{c}A(n,T))\Big{]}^{1/2}$, we obtain

$\displaystyle\Pr\bigg{[}\Big{|}\begin{array}[]{l}\text{number of men
matched}\\\ \hskip 14.45377pt-E[\text{number of men
matched}]\end{array}\Big{|}>\sqrt{\frac{mw\sqrt{3}\ln(n^{c}A(n,T))}{0.12nt}}\bigg{]}\leq\frac{2}{A(n,T)n^{c}}.$

We will specify $A(n,T)$ later. It is easy to see that because of
$\mathcal{E}_{m}$ and $\mathcal{E}_{w}$, $m\leq nt(1+\epsilon)/2\sqrt{T}$ and
$w\leq nt(1+\epsilon)/2\sqrt{T}$. So we obtain,

$\displaystyle\Pr\bigg{[}\Big{|}\begin{array}[]{l}\text{number of men
matched}\\\ \hskip 14.45377pt-E[\text{number of men
matched}]\end{array}\Big{|}>\sqrt{\frac{nt(1+\epsilon)^{2}\sqrt{3}\ln(n^{c}A(n,T))}{0.48T}}\bigg{]}\leq\frac{2}{A(n,T)n^{c}}.$

Since $t\leq\sqrt{T}$,

$\displaystyle\Pr\bigg{[}\Big{|}\begin{array}[]{l}\text{number of men
matched}\\\ \hskip 14.45377pt-E[\text{number of men
matched}]\end{array}\Big{|}>\sqrt{\frac{n(1+\epsilon)^{2}\sqrt{3}\ln(n^{c}A(n,T))}{0.48\sqrt{T}}}\bigg{]}\leq\frac{2}{A(n,T)n^{c}}.$

We can perform the same argument for the women to obtain,

$\displaystyle\Pr\bigg{[}\Big{|}\begin{array}[]{l}\text{number of women
matched}\\\ \hskip 14.45377pt-E[\text{number of women
matched}]\end{array}\Big{|}>\sqrt{\frac{n(1+\epsilon)^{2}\sqrt{3}\ln(n^{c}A(n,T))}{0.48\sqrt{T}}}\bigg{]}\leq\frac{2}{A(n,T)n^{c}}.$

From this it immediately follows that

$\displaystyle\Pr\bigg{[}\Big{|}\sum_{d\in
S}X(d,\tau)\Big{|}>2\sqrt{\frac{n(1+\epsilon)^{2}\sqrt{3}\ln(n^{c}A(n,T))}{0.48\sqrt{T}}}\bigg{]}\leq\frac{4}{A(n,T)n^{c}}.$

where $S$ is any subset of the diagonals in strip $s$. We have to consider