# Stable Matching: Choosing Which Proposals to Make

Ishan Agarwal New York University. This work was supported in part by NSF
Grant CCF-1909538. Richard Cole 11footnotemark: 1

###### Abstract

To guarantee all agents are matched in general, the classic Deferred
Acceptance algorithm needs complete preference lists. In practice, preference
lists are short, yet stable matching still works well. This raises two
questions:

  * •

Why does it work well?

  * •

Which proposals should agents include in their preference lists?

We study these questions in a model, introduced by Lee [17], with preferences
based on correlated cardinal utilities: these utilities are based on common
public ratings of each agent together with individual private adjustments. Lee
showed that for suitable utility functions, in large markets, with high
probability, for most agents, all stable matchings yield similar valued
utilities. By means of a new analysis, we strengthen Lee’s result, showing
that in large markets, with high probability, for _all_ but the agents with
the lowest public ratings, all stable matchings yield similar valued
utilities. We can then deduce that for _all_ but the agents with the lowest
public ratings, each agent has an easily identified length $O(\log n)$
preference list that includes all of its stable matches, addressing the second
question above. We note that this identification uses an initial communication
phase.

We extend these results to settings where the two sides have unequal numbers
of agents, to many-to-one settings, e.g. employers and workers, and we also
show the existence of an $\epsilon$-Bayes-Nash equilibrium in which every
agent makes relatively few proposals. These results all rely on a new
technique for sidestepping the conditioning between the tentative matching
events that occur over the course of a run of the Deferred Acceptance
algorithm. We complement these theoretical results with an experimental study.

##  1 Introduction

Consider a doctor applying for residency positions. Where should she apply? To
the very top programs for her specialty? Or to those where she believes she
has a reasonable chance of success (if these differ)? And if the latter, how
does she identify them? We study these questions in the context of Gale and
Shapley’s deferred acceptance (DA) algorithm [5]. It is well-known that in DA
the optimal strategy for the proposing side is to list their choices in order
of preference. However, this does not address which choices to list.

The DA algorithm is widely used to compute matchings in real-world
applications: the National Residency Matching Program (NRMP), which matches
future residents to hospital programs [25]; university admissions programs
which match students to programs, e.g. in Chile [24], school choice programs,
e.g. for placement in New York City’s high schools [1], the Israeli psychology
Masters match [9], and no doubt many others (e.g. [8]).

Recall that each agent provides the mechanism a list of its possible matches
in preference order, including the possibility of “no match” as one of its
preferences. These mechanisms promise that the output will be a stable
matching with respect to the submitted preference lists. In practice,
preference lists are relatively short. This may be directly imposed by the
mechanism or could be a reflection of the costs—for example, in time or
money—of determining these preferences. Note that a short preference list is
implicitly stating that the next preference after the listed ones is “no
match”.

Thus it is important to understand the impact of short preference lists. Roth
and Peranson observed that the NRMP data showed that preference lists were
short compared to the number of programs and that these preferences yielded a
single stable partner for most participants; we note that this single stable
partner could be the “no match” choice, and in fact this is the outcome for a
constant fraction of the participants. They also confirmed this theoretically
for the simplest model of uncorrelated random preferences; namely that with
the preference lists truncated to the top O(1) preferences, almost all agents
have a unique stable partner. Subsequently, in [10] the same result was
obtained in the more general popularity model which allows for correlations
among different agents’ preferences; in their model, the first side—men—can
have arbitrary preferences; on the second side—women—preferences are selected
by weighted random choices, the weights representing the “popularity” of the
different choices. These results were further extended by Kojima and Parthak
in [15].

The popularity model does not capture behavior in settings where bounds on the
number of proposals lead to proposals being made to plausible partners, i.e.
partners with whom one has a realistic chance of matching. One way to capture
such settings is by way of tiers [3], also known as block correlation [4].
Here agents on each side are partitioned into tiers, with all agents in a
higher tier preferred to agents in a lower tier, and with uniformly random
preferences within a tier. Tiers on the two sides may have different sizes. If
we assign tiers successive intervals of ranks equal to their size, then, in
any stable matching, the only matches will be between agents in tiers whose
rank intervals overlap.

A more nuanced way of achieving these types of preferences bases agent
preferences on cardinal utilities; for each side, these utilities are
functions of an underlying common assessment of the other side, together with
idiosyncratic individual adjustments for the agents on the other side. These
include the separable utilities defined by Ashlagi, Braverman, Kanoria and Shi
in [3], and another class of utilities introduced by Lee in [17]. This last
model will be the focus of our study.

To make this more concrete, we review a simple special case of Lee’s model,
the _linear separable model_. Suppose that there are $n$ men and $n$ women
seeking to match with each other. Each man $m$ has a public rating $r_{m}$, a
uniform random draw from $[0,1]$. These ratings can be viewed as the women’s
joint common assessment of the men. In addition, each woman $w$ has an
individual adjustment, which we call a score, $s_{w}(m)$ for man $m$, again a
uniform random draw from $[0,1]$. All the draws are independent. Woman $w$’s
utility for man $m$ is given by $\tfrac{1}{2}[r_{m}+s_{w}(m)]$; her full
preference list has the men in decreasing utility order. The men’s utilities
are defined similarly.

Lee stated that rather than being assumed, short preference lists should arise
from the model; this appears to have been a motivation for the model he
introduced. A natural first step would be to show that for some or all stable
matchings, the utility of each agent can be well-predicted, for this would
then allow the agents to limit themselves to the proposals achieving such a
utility. Lee proved an approximate version of this statement, namely that with
high probability (w.h.p., for short) most agents obtain utility within a small
$\epsilon$ of an easily-computed individual benchmark. However, this does not
imply that agents can restrict their proposals to a reduced utility range.
(See the paragraph preceding Definition 4 for the specification of the
benchmarks.)

Our work seeks to resolve this issue. We obtain the following results. Note
that in these results, when we refer to the bottommost agents, we mean when
ordered by decreasing public rating. Also, we let the term loss mean the
difference between an agent’s benchmark utility and their achieved utility.

  1. 1.

We show that in the linearly separable model, for any constant $c>0$, with
probability $1-1/n^{c}$, in every stable matching, apart from a sub-constant
$\sigma$ fraction of the bottommost agents, _all_ the other agents obtain
utility equal to an easily-computed individual benchmark $\pm\epsilon$, where
$\epsilon$ is also sub-constant.

We show that both $\sigma,\epsilon=\widetilde{\Theta}(n^{-1/3})$.111The
$\widetilde{\Theta}(\cdot)$ notation means up to a poly-logarithmic term; here
$\sigma,\epsilon=\Theta((n/\ln n)^{-1/3})$. As we will see, this implies,
w.h.p., that for all the agents other than the bottommost $\sigma$ fraction,
each agent has $\Theta(\ln n)$ possible edges (proposals) that could be in any
stable matching, namely the proposals that provide both agents utility within
$\epsilon$ of their benchmark. Furthermore, we show our bound is tight: with
fairly high probability, there is no matching, let alone stable matching,
providing every agent a partner if the values of $\epsilon$ and $\sigma$ are
reduced by a suitable constant factor.

An interesting consequence of this lower bound on the agents’ utilities is
that the agents can readily identify a moderate sized subset of the edge set
to which they can safely restrict their applications. More precisely, any
woman $w$ outside the bottommost $\sigma$ fraction, knowing only her own
public rating, the public ratings of the men, and her own private score for
each man, can determine a preference list of length
$\widetilde{\Theta}(n^{1/3})$ which, w.h.p, will yield the same result as her
true full-length list. Our analysis also shows that if $w$ obtained the men’s
private scores for these proposals, then w.h.p. she could safely limit herself
to a length $O(\ln n)$ preference list.

  2. 2.

The above bounds apply not only to the linearly separable model, but to a
significantly more general bounded derivative model (in which derivatives of
the utility functions are bounded).

  3. 3.

The result also immediately extends to settings with unequal numbers of men
and women. Essentially, our analysis shows that the loss for an agent is small
if there is a $\sigma$ fraction of agents of lower rank on the opposite side.
Thus even on the longer side, w.h.p., the topmost $n(1-\sigma)$ agents all
obtain utility close to their benchmark, where $n$ is the size of the shorter
side. This limits the “stark effect of competition” [2]—namely that the agents
on the longer side are significantly worse off—to a lower portion of the
agents on the longer side.

  4. 4.

The result extends to the many-to-one setting, in which agents on one side
seek multiple matches. Our results are given w.r.t. a parameter $d$, the
number of matches that each agent on the “many” side desires. For simplicity,
we assume this parameter is the same for all these agents. In fact, we analyze
a more general many-to-many setting.

  5. 5.

A weaker result with arbitrarily small $\sigma,\epsilon=\Theta(1)$ holds when
there is no restriction on the derivatives of the utility functions, which we
call the general values model. Again, we show this bound cannot be improved in
general. This setting is essentially the general setting considered by Lee
[17]. He had shown there was a $\sigma$ fraction of agents who might suffer
larger losses; our bound identifies this $\sigma$ fraction of agents as the
bottommost agents.

  6. 6.

In the bounded derivative model, with slightly stronger constraints on the
derivatives, we also show the existence of an $\epsilon$-Bayes-Nash
equilibrium in which no agent proposes more than $O(\ln^{2}n)$ times and all
but the bottommost $O((\ln n/n)^{1/3})$ fraction of the agents make only the
$O(\ln n)$ proposals identified in (1) above. Here $\epsilon=\Theta(\ln
n/n^{1/3})$.

These results all follow from a lemma showing that, w.h.p., each non-
bottommost agent has at most a small loss. In turn, the proof of this lemma
relies on a new technique which sidesteps the conditioning inherent to runs of
DA in these settings.

##### Experimental results

Much prior work has been concerned with preference lists that have a constant
bound on their length. For moderate values of $n$, say $n\in[10^{3},10^{6}]$,
$\ln n$ is quite small, so our $\Theta(\ln n)$ bound may or may not be
sufficiently small in practice for this range of $n$. What matters are the
actual constants hidden by the $\Theta$ notation, which our analysis does not
fully determine. To help resolve this, we conducted a variety of simulation
experiments.

We have also considered how to select the agents to include in the preference
lists, when seeking to maintain a constant bound on their lengths, namely a
bound that, for the values of $n$ we considered, was smaller than the
$\Theta(\ln n)$ bound determined by the above simulations; again, our
investigation was experimental.

##### Other Related work

The random preference model was introduced by Knuth [13] (for a version in
English see [14]), and subsequently extensively analyzed [22, 12, 20, 18, 23,
21, 16]. In this model, each agent’s preferences are an independent uniform
random permutation of the agents on the other side. An important observation
was that when running the DA algorithm, the proposing side obtained a match of
rank $\Theta(\ln n)$ on the average, while on the other side the matches had
rank $\Theta(n/\ln n)$.

A recent and unexpected observation in [2] was the “stark effect of
competition”: that in the random preferences model the short side, whether it
was the proposing side or not, was the one to enjoy the $\Theta(\ln n)$ rank
matches. Subsequent work showed that this effect disappeared with short
preference lists in a natural modification of the random preferences model
[11]. Our work suggests yet another explanation for why this effect may not be
present: it does not require that short preference lists be imposed as an
external constraint, but rather that the preference model generates few edges
that might ever be in a stable matching.

The number of edges present in any stable matching has also been examined for
a variety of settings. When preference lists are uniform the expected number
of stable pairs is $\Theta(n\ln n)$ [20]; when they are arbitrary on one side
and uniform on the other side, the expected number is $O(n\ln n)$ [12]. This
result continues to hold when preference lists are arbitrary on the men’s side
and are generated from general popularities on the women’s side [6]. Our
analysis shows that in the linear separable model (and more generally in the
bounded derivative setting) the expected number of stable pairs is also
$O(n\ln n)$.

Another important issue is the amount of communication needed to identify who
to place on one’s preference lists when they have bounded length. In general,
the cost is $\Omega(n)$ per agent (in an $n$ agent market) [7], but in the
already-mentioned separable model of Ashlagi et al. [3] this improves to
$\widetilde{O}(\sqrt{n})$ given some additional constraints, and further
improves to $O(\ln^{4}n)$ in a tiered separable market [3]. We note that for
the bounded derivatives setting, with high probability, the communication cost
will be $O(n^{1/3}\ln^{2/3}n)$ for all agents except the bottommost
$\Theta(n^{2/3}\ln^{1/3}n)$, for whom the cost can reach
$O(n^{2/3}\ln^{1/3}n)$.

Another approach to selecting which universities to apply to was considered by
Shorrer who devised a dynamic program to compute the optimal choices for
students assuming universities had a common ranking of students [26].

##### Roadmap

In Section 2 we review some standard material. In Section 3 we state our main
result in two parts: Theorem 3.1, which bounds the losses in the setting of
the linear model, and Theorem 3.2, which shows it suffices to limit preference
lists to a small set of edges. We prove these theorems in Sections 4 and 5,
respectively. We also present some numerical simulations for the linear
separable model in Section 6 We conclude with a brief discussion of open
problems in Section 7.

Following this, in the appendices, we formally state and prove all the other
results alluded to in the introduction and we also present further numerical
simulations for the linear separable model. A complete summary of their
content is given in Appendix A.

##  2 Preliminaries

###  2.1 Stable Matching and the Deferred Acceptance (DA) Algorithm

Let $M$ be a set of $n$ men and $W$ a set of $n$ women. Each man $m$ has an
ordered list of women that represents his preferences, i.e. if a woman $w$
comes before a woman $w^{\prime}$ in $m$’s list, then $m$ would prefer
matching with $w$ rather than $w^{\prime}$. The position of a woman $w$ in
this list is called $m$’s ranking of $w$. Similarly each woman $w$ has a
ranking of her preferred men222Throughout this paper, we assume that each man
$m$ (woman $w$) ranks all the possible women (men), i.e. $m$’s ($w$’s)
preference list is complete.. The stable matching task is to pair (match) the
men and women in such a way that no two people prefer each other to their
assigned partners. More formally:

######  Definition 1 (Matching).

A matching is a pairing of the agents in $M$ with the agents in $W$. It
comprises a bijective function $\mu$ from $M$ to $W$, and its inverse
$\nu=\mu^{-1}$, which is a bijective function from $W$ to $M$.

######  Definition 2 (Blocking pair).

A matching $\mu$ has a blocking pair $(m,w)$ if and only if:

  1. 1.

$m$ and $w$ are not matched: $\mu(m)\neq w$.

  2. 2.

$m$ prefers $w$ to his current match $\mu(m)$.

  3. 3.

$w$ prefers $m$ to her current match $\nu(w)$.

######  Definition 3 (Stable matching).

A matching $\mu$ is stable if it has no blocking pair.

Initially, all the men and women are unmatched.

while  _some woman $w$ with a non-empty preference list is unmatched_ do

let $m$ be the first man on her preference list;

if  _$m$ is currently unmatched_ then

tentatively match $w$ to $m$.

end if

if  _$m$ is currently matched to $w^{\prime}$, and $m$ prefers $w$ to
$w^{\prime}$_ then

make $w^{\prime}$ unmatched and tentatively match $w$ to $m$.

else

remove $m$ from $w$’s preference list.

end if

end while

ALGORITHM 1 Woman Proposing Deferred Acceptance (DA) Algorithm.

Gale and Shapley [5] proposed the seminal deferred acceptance (DA) algorithm
for the stable matching problem. We present the woman-proposing DA algorithm
(Algorithm $1$); the man-proposing DA is symmetric. The following facts about
the DA algorithm are well known. We state them here without proof and we shall
use them freely in our analysis.

######  Observation 1.

  1. 1.

DA terminates and outputs a stable matching.

  2. 2.

The stable matching generated by DA is independent of the order in which the
unmatched agents on the proposing side are processed.

  3. 3.

Woman-proposing DA is woman-optimal, i.e. each woman is matched with the best
partner she could be matched with in any stable matching.

  4. 4.

Woman-proposing DA is man-pessimal, i.e. each man is matched with the worst
partner he could be matched with in any stable matching.

###  2.2 Useful notation and definitions

There are $n$ men and $n$ women. In all of our models, each man $m$ has a
utility $U_{m,w}$ for the woman $w$, and each woman $w$ has a utility
$V_{m,w}$ for the man $m$. These utilities are defined as

$\displaystyle U_{m,w}=U(r_{w},s_{m}(w)),\text{ and}$ $\displaystyle
V_{m,w}=V(r_{m},s_{w}(m)),$

where $r_{m}$ and $r_{w}$ are common public ratings, $s_{m}(w)$ and $s_{w}(m)$
are private scores specific to the pair $(m,w)$, and $U(\cdot,\cdot)$ and
$V(\cdot,\cdot)$ are continuous and strictly increasing functions from
$\mathbb{R}^{2}_{+}$ to $\mathbb{R}_{+}$. The ratings are independent uniform
draws from $[0,1]$ as are the scores.

In the _Linear Separable Model_ , each man $m$ assigns each woman $w$ a
utility of $U_{m,w}=\lambda\cdot r_{w}+(1-\lambda)\cdot s_{m}(w)$, where
$0<\lambda<1$ is a constant. The women’s utilities for the men are defined
analogously as $V_{m,w}=\lambda\cdot r_{m}+(1-\lambda)\cdot s_{w}(m)$. All our
experiments are for this model.

We let $\\{m_{1},m_{2},\ldots,m_{n}\\}$ be the men in descending order of
their public ratings and $\\{w_{1},w_{2},\ldots,w_{n}\\}$ be a similar
ordering of the women. We say that $m_{i}$ has public rank $i$, or rank $i$
for short, and similarly for $w_{i}$. We also say that $m_{i}$ and $w_{i}$ are
_aligned_. In addition, we often want to identify the men or women in an
interval of public ratings. Accordingly, we define $M(r,r^{\prime})$ to be the
set of men with public ratings in the range $(r,r^{\prime})$, and
$M[r,r^{\prime}]$ to be the set with public ratings in the range
$[r,r^{\prime}]$; we also use the notation $M(r,r^{\prime}]$ and
$M[r,r^{\prime})$ to identify the men with ratings in the corresponding semi-
open intervals. We use an analogous notation, with $W$ replacing $M$, to refer
to the corresponding sets of women.

We will be comparing the achieved utilities in stable matchings to the
following benchmarks: the rank $i$ man has as benchmark $U(r_{w_{i}},1)$, the
utility he would obtain from the combination of the rank $i$ woman’s public
rating and the highest possible private score; and similarly for the women.
Based on this we define the loss an agent faces as follows.

######  Definition 4 (Loss).

Suppose man $m$ and woman $w$ both have rank $i$. The _loss_ $m$ sustains from
a match of utility $u$ is defined to be $U(r_{w},1)-u$. The loss for women is
defined analogously.

In our analysis we will consider a complete bipartite graph whose two sets of
vertices correspond to the men and women, respectively. For each man $m$ and
woman $w$, we view the possible matched pair $(m,w)$ as an edge in this graph.
Thus, throughout this work, we will often refer to edges being proposed, as
well as edges satisfying various conditions.

##  3 Upper Bound in The Linear Separable Model

To illustrate our proof technique for deriving upper bounds, we begin by
stating and proving our upper bound result for the special case of the linear
separable model with $\lambda=\tfrac{1}{2}$.

######  Theorem 3.1.

In the linear separable model with $\lambda=1/2$, when there are $n$ men and
$n$ women, for any given constant $c>0$, for large enough $n$, with
probability at least $1-n^{-c}$, in every stable matching, for every $i$, with
$r_{w_{i}}\geq\overline{\sigma}\triangleq 3\overline{L}/2$, agent $m_{i}$
suffers a loss of at most $\overline{L}$, where $\overline{L}=(16(c+2)\ln
n/n)^{1/3}$, and similarly for the agents $w_{i}$.

In words, w.h.p., all but the bottommost agents (those whose aligned agents
have public rating less than $\overline{\sigma}$) suffer a loss of no more
than $\overline{L}$. This is a special case of our basic upper bound for the
bounded utilities model (Theorem D.1).

One of our goals is to be able to limit the number of proposals the proposing
side needs to make. We identify the edges that could be in some stable
matching, calling them acceptable edges. Our definition is stated generally so
that it covers all our results; accordingly we replace the terms
$\overline{L}$ and $\overline{\sigma}$ in Theorem 3.1 with parameters $L$ and
$\sigma$.

######  Definition 5 (Acceptable edges).

Let $0<\sigma<1$ and $0<L<1$ be two parameters. An edge $(m_{i},w_{j})$ is
$(L,\sigma)$-_man-acceptable_ either if it provides $m_{i}$ utility at least
$U(r_{w_{i}},1)-L$, or if $m_{i}\in M[0,\sigma)$. The definition of
$(L,\sigma)$-woman-acceptable is symmetric. Finally, $(m_{i},w_{j})$ is
$(L,\sigma)$-_acceptable_ if it is both $(L,\sigma)$-man and
$(L,\sigma)$-woman-acceptable.

To prove our various results, we choose $L$ and $\sigma$ so that w.h.p. the
edges in every stable matching are $(L,\sigma)$-_acceptable_. We call this
high probability event $\mathcal{E}$. We will show that if $\mathcal{E}$
occurs, then running DA on the set of acceptable edges, or any superset of the
acceptable edges obtained via loss thresholds, produces the same stable
matching as running DA on the full set of edges.

######  Theorem 3.2.

If $\mathcal{E}$ occurs, then running woman-proposing DA with the edge set
restricted to the acceptable edges or to any superset of the acceptable edges
obtained via loss thresholds (including the full edge set) result in the same
stable matching.

The implication is that w.h.p. a woman can safely restrict her proposals to
her acceptable edges, or to any overestimate of this set of edges obtained by
her setting an upper bound on the loss she is willing to accept. There is a
small probability— at most $n^{-c}$—that this may result in a less good
outcome, which can happen only if $\mathcal{E}$ does not occur. Note that
Theorem 3.2 applies to every utility model we consider. Then, w.h.p., every
stable matching gives each woman $w$, whose aligned agent $m$ has public
rating $r_{m}\geq\overline{\sigma}=\Omega((\ln n/n)^{1/3})$, a partner with
public rating in the range
$[r_{m}-2\overline{L},r_{m}+\tfrac{5}{2}\overline{L}]$ (see Theorem F.2 in
Appendix F.1). The bound $r_{m}-2\overline{L}$ is a consequence of the bound
on the woman’s loss; the bound $r_{m}+\tfrac{5}{2}\overline{L}$ is a
consequence of the bound on the men’s losses. An analogous statement applies
to the men.

This means that if we are running woman-proposing DA, each of these women
might as well limit her proposals to her woman-acceptable edges, which is at
most the men with public ratings in the range $r_{m}\pm\Theta(\overline{L})$
for whom she has private scores of at least $1-\Theta(\overline{L})$. In
expectation, this yields $\Theta(n^{1/3}(\ln n)^{2/3})$ men to whom it might
be worth proposing. It also implies that a woman can have a gain of at most
$\Theta(\overline{L})$ compared to her target utility.

If, in addition, each man can inexpensively signal the women who are man-
acceptable to him, then the women can further limit their proposals to just
those men providing them with a signal; this reduces the expected number of
proposals these women can usefully make to just $\Theta(\ln n)$.

##  4 Sketch of the Proof of Theorem 3.1

$\circ$rating $r_{m_{i}}$, man $m_{i}$$\circ$woman
$w_{i}$$M_{i}=[r_{m_{i}}-\alpha,1]$$h_{i}$ men, rating range
$\alpha$$\ell_{i}$ womenmenwomencutoff
$r_{m_{i}}-\alpha$$\widetilde{W}_{i}=W[r_{\overline{w}_{i}},1]$$\circ$woman
$\overline{w}_{i}=w_{i+\ell_{i}}$ Figure 1:

We begin by outlining the main ideas used in our analysis. Our goal is to show
that when we run woman proposing DA, w.h.p. each man receives a proposal that
gives him a loss of at most $L$ (except possibly for men among the bottommost
$\Theta(nL)$). As the outcome is the man-pessimal stable matching, this means
that w.h.p., in all stable matchings, these men have a loss of at most $L$. By
symmetry, the same bound holds for the women.

Next, we provide some intuition for the proof of this result. See Fig. 1. Our
analysis uses 3 parameters $\alpha,\beta,\gamma=\Theta(L)$. Let $m_{i}$ be a
non-bottommost man. We consider the set of men with public rank at least
$r_{m_{i}}-\alpha$: $M_{i}=M[r_{m_{i}}-\alpha,1]$. We consider a similar,
slightly larger set of women: $\widetilde{W}_{i}=W[r_{w_{i}}-3\alpha,1]$. Now
we look at the best proposals by the women in $\widetilde{W}_{i}$, i.e. the
ones they make first. Specifically, we consider the proposals that give these
women utility at least $V(r_{m_{i}}-\alpha,1)$, proposals that are therefore
guaranteed to be to the men in $M_{i}$. Let $\big{|}M_{i}\big{|}=i+h_{i}$ and
$\big{|}W_{i}\big{|}=i+\ell_{i}$. In expectation, $\ell_{i}-h_{i}=2\alpha n$.
Necessarily, at least $\ell_{i}-h_{i}+1$ women in $M_{i}$ cannot match with
men in $M_{i}\setminus\\{m_{i}\\}$. But, as we will see, these women all have
probability at least $\beta$ of having a proposal to $m_{i}$ which gives them
utility at least $V(r_{m_{i}}-\alpha,1)$. These are proposals these women must
make before they make any proposals to men with public rating less than
$r_{m_{i}}-\alpha$. Furthermore, for each of these proposals, $m_{i}$ has
probability at least $\gamma$ of having a loss of $L$ or less. Thus, in
expectation, $m_{i}$ receives at least $2\alpha\beta\gamma n$ proposals which
give him a loss of $L$ or less.

We actually want a high-probability bound. So we choose $\alpha,\beta,\gamma$
so that $\alpha\beta\gamma n\geq c\log n$ for a suitable constant $c>0$, and
then apply a series of Chernoff bounds. There is one difficulty. The Chernoff
bounds requires the various proposals to be independent. Unfortunately, in
general, this does not appear to be the case. However, we are able to show
that the failure probability for our setting is at most the failure
probability in an artificial setting in which the events are independent,
which yields the desired bound.

We now embark on the actual proof.

We formalize the men’s rating cutoff with the notion of DA stopping at public
rating $r$.

######  Definition 6 (DA stops).

The women _stop at public rating $r$_ if, in each woman’s preference list, all
the edges with utility less than $V(r,1)$ are removed. The women _stop at man
$m$_ if, in each woman’s preference list, all the edges following her edge to
$m$ are removed. The women _double cut at man $m$ and public rating $r$_, if
they each stop at $m$ or $r$, whichever comes first. Men stopping and double
cutting are defined similarly. Finally, an edge is said to _survive_ the
cutoff if it is not removed by the stopping.

To obtain our bounds for man $m_{i}$, we will have the women double cut at
rating $r_{m_{i}}-\alpha$ and at man $m_{i}$, where $\alpha>0$ is a parameter
we will specify later.

Our upper bounds in all of the utility models depend on a parameterized key
lemma (Lemma 4.1) stated shortly. This lemma concerns the losses the men face
in the woman-proposing DA; a symmetric result applies to the women. The
individual theorems follow by setting the parameters appropriately. Our key
lemma uses three parameters: $\alpha,\beta,\gamma>0$. To avoid rounding
issues, we will choose $\alpha$ so that $\alpha n$ is an integer. The other
parameters need to satisfy the following constraints.

$\displaystyle\text{for $r\geq\alpha$:}\hskip 36.135ptV(r-\alpha,1)\leq
V(r,1-\beta)$ (1) $\displaystyle\text{for $r\geq 3\alpha$:}\hskip
36.135ptU(r,1)-U(r-3\alpha,1-\gamma)\leq L$ (2)

Equation (1) relates the range of private values that will yield a woman an
edge to $m_{i}$ that survives the cut at $r_{m_{i}}-\alpha$, or equivalently
the probability of having such an edge. Observation 2 below, shows that
Equation (2) identifies the range of $m_{i}$’s private values for proposals
from $\widetilde{W}_{i}$ that yield him a loss of at most $L$ (for we will
ensure the women in $\widetilde{W}_{i}$ have public rating at least
$r_{w_{i}}-3\alpha$).

######  Observation 2.

Consider the proposal from woman $w$ to the rank $i$ man $m_{i}$. Suppose the
rank $i$ woman $w_{i}$ has rating $r_{w_{i}}\geq 3\alpha$. If $w$ has public
rating $r\geq r_{w_{i}}-3\alpha$ and $m_{i}$’s private score for $w$ is at
least $1-\gamma$, then $m_{i}$’s utility for $w$ is at least
$U(r_{w_{i}}-3\alpha,1-\gamma)\geq U(r_{w_{i}},1)-L$.

In the linear separable model with $\lambda=\tfrac{1}{2}$, we set
$\alpha=\beta=\gamma$ and $L=2\alpha$.

The next lemma determines the probability that man $m_{i}$ receives a proposal
causing him a loss of at most $L$. The lemma calculates this probability in
terms of the parameters we just defined. Note that the result does not depend
on the utility functions $U(\cdot,\cdot)$ and $V(\cdot,\cdot)$ being linear.
In fact, the same lemma applies to much more general utility models which we
also study (see Section C) and it is the crucial tool we use in all our upper
bound proofs.

In what follows, to avoid heavy-handed notation, by $r_{m_{i}}-\alpha$ we will
mean $\max\\{0,r_{m_{i}}-\alpha\\}$.

In order to state our next result crisply, we define the following Event
${\cal E}_{i}$. It concerns a run of woman-proposing DA with double cut at the
rank $i$ man $m_{i}$ and at public rating $r_{m_{i}}-\alpha$. Let
$h_{i}=\big{|}M[r_{m_{i}}-\alpha,r_{m_{i}})\big{|}$,
$\ell_{i}=\big{|}W[r_{w_{i}}-3\alpha,r_{w_{i}})\big{|}$, and
$\overline{w}_{i}$ be the woman with rank $i+\ell_{i}$. See Figure 1 for an
illustration of these definitions. Event ${\cal E}_{i}$ occurs if
$r_{w_{i}}\geq 3\alpha$ and between them the $i+\ell_{i}$ women in
$W[r_{{w}_{i}}-3\alpha,1]$ make at least one proposal to $m_{i}$ that causes
him a loss of at most $L$.

Finally we define Event $\cal E$: it happens if ${\cal E}_{i}$ occurs for all
$i$ such that $r_{w_{i}}\geq 3\alpha$.

######  Lemma 4.1.

Let $\alpha>0$ and $L>0$ be given, and suppose that $\beta$ and $\gamma$
satisfy (1) and (2), respectively. Then, Event $\cal E$ occurs with
probability at least $1-p_{f}$, where the failure probability

$p_{f}=n\cdot\exp(-\alpha(n-1)/12)+n\cdot\exp(-\alpha(n-1)/24)+n\exp(-\alpha\beta
n/8)+n\cdot\exp(-\alpha\beta\gamma n/2).$

The following simple claim notes that the men’s loss when running the full DA
is no larger than when running double-cut DA.

######  Claim 4.1.

Suppose a woman-proposing double-cut DA at man $m_{i}$ and rating
$r_{m_{i}}-\alpha$ is run, and suppose $m_{i}$ incurs a loss of $L$. Then in
the full run of woman-proposing DA, $m_{i}$ will incur a loss of at most $L$.

###### Proof.

Recall that when running the women-proposing DA the order in which unmatched
women are processed does not affect the outcome. Also note that as the run
proceeds, whenever a man’s match is updated, the man obtains an improved
utility. Thus, in the run with the full edge set we can first use the edges
used in the double-cut DA and then proceed with the remaining edges. Therefore
if in the double-cut DA $m_{i}$ has a loss of $L$, in the full run $m_{i}$
will also have a loss of at most $L$. ∎

To illustrate how this lemma is applied, we now prove Theorem 3.1. Note that
$\overline{L}$ is the value of $L$ used in this theorem. Our other results use
other values of $L$.

###### Proof.

(Of Theorem 3.1) By Lemma 4.1, in the double-cut DA, for all $i$ with
$r_{w_{i}}\geq 3\alpha$, $m_{i}$ obtains a match giving him loss at most
$\overline{L}$, with probability at least
$1-n\cdot\exp(-\alpha(n-1)/12)-n\cdot\exp(-\alpha
n/24)-n\exp(-\alpha^{2}n/8)-n\cdot\exp(-\alpha^{3}n/2)$.

By Claim 4.1, $m_{i}$ will incur a loss of at most $\overline{L}$ in the full
run of woman-proposing DA with at least as large a probability. But this is
the man-pessimal match. Consequently, in every stable match, $m_{i}$ has a
loss of at most $\overline{L}$. By symmetry, the same bound applies to each
woman $w_{i}$ such that $r_{m_{i}}\geq 3\alpha$.

We choose $\overline{L}=[16(c+2)\ln n/n]^{1/3}$. Recalling that
$\alpha=\overline{L}/2$, we see that for large enough $n$ the probability
bound, over all the men and women, is at most $1-n^{-c}$. The bounds
$r_{w_{i}}\geq 3\alpha$ and $r_{m_{i}}\geq 3\alpha$ imply we can set
$\overline{\sigma}=3\alpha=\tfrac{3}{2}\overline{L}$. ∎

###### Proof.

(Of Lemma 4.1.) We run the double-cut DA in two phases, defined as follows.
Recall that $h_{i}=\big{|}M[r_{m_{i}}-\alpha,r_{m_{i}})\big{|}$ and
$\ell_{i}=\big{|}W[r_{w_{i}}-3\alpha,r_{w_{i}})\big{|}$. Note that women with
rank at most $i+\ell_{i}$ have public rating at least $r_{w_{i}}-3\alpha$.
_Phase 1_. Every unmatched woman with rank at most $i+\ell_{i}$ keeps
proposing until her next proposal is to $m_{i}$, or she runs out of proposals.
_Phase 2_. Each unmatched women makes her next proposal, if any, which will be
a proposal to $m_{i}$.

Our analysis is based on the following four claims. The first two are simply
observations that w.h.p. the number of agents with public ratings in a given
interval is close to the expected number. We defer the proofs to the appendix.

A critical issue in this analysis is to make sure the conditioning induced by
the successive steps of the analysis does not affect the independence needed
for subsequent steps. To achieve this, we use the Principle of Deferred
Decisions, only instantiating random values as they are used. Since each
successive bound uses a different collection of random variables this does not
present a problem.

######  Claim 4.2.

Let ${\mathcal{B}}_{1}$ be the event that for some $i$,
$h_{i}\geq\tfrac{3}{2}\alpha(n-1)$. ${\mathcal{B}}_{1}$ occurs with
probability at most $n\cdot\exp(-\alpha(n-1)/12)$. The only randomness used in
the proof are the choices of the men’s public ratings. The same bound applies
to the women.

###### Proof.

(Sketch.) As $\text{E}[h_{i}]=\alpha(n-1)$, w.h.p.,
$h_{i}<\tfrac{3}{2}\alpha(n-1)$. This claim uses a Chernoff bound with the
randomness coming from the public ratings of the men. ∎

######  Claim 4.3.

Let ${\mathcal{B}}_{2}$ be the event that for some $i$,
$\ell_{i}\leq\tfrac{5}{2}\alpha(n-1)$. ${\mathcal{B}}_{2}$ occurs with
probability at most $n\cdot\exp(-\alpha(n-1)/24)$. The only randomness used in
the proof are the choices of the women’s public ratings. The same bound
applies to the men.

###### Proof.

This is very similar to the proof of Claim 4.2. ∎

######  Claim 4.4.

Let ${\mathcal{B}}_{3}$ be the event that between them, the women with rank at
most $i+\ell_{i}$ make fewer than $\tfrac{1}{2}\alpha\beta n$ Step 2 proposals
to $m_{i}$. If events ${\mathcal{B}}_{1}$ and ${\mathcal{B}}_{2}$ do not
occur, then ${\mathcal{B}}_{3}$ occurs with probability at most
$\exp(-\alpha\beta n/8)$. The only randomness used in the proof are the
choices of the women’s private scores.

This bound uses the private scores of the women and employs a novel argument
given below to sidestep the conditioning among these proposals.

######  Claim 4.5.

If none of the events ${\mathcal{B}}_{1}$, ${\mathcal{B}}_{2}$, or
${\mathcal{B}}_{3}$ occur, then at least one of the Step 2 proposals to
$m_{i}$ will cause him a loss of at most $L$ with probability at least
$1-(1-\gamma)^{\alpha\beta n/2}\geq 1-\exp(-\alpha\beta\gamma n/2)$. The only
randomness used in the proof are the choices of the men’s private scores.

###### Proof.

Note that each Phase 2 proposal is from a woman $w$ with rank at most
$i+\ell_{i}$. As already observed, her public rating is at least
$r_{w_{i}}-3\alpha$. Recall that man $m_{i}$’s utility for $w$ equals
$U(r_{w},s_{m_{i}}(w))\geq U(r_{w_{i}}-3\alpha,s_{m_{i}}(w))$. To achieve
utility at least $U(r_{w_{i}},1)-L\leq U(r_{w_{i}}-3\alpha,1-\gamma)$ (using
(2)) it suffices to have $s_{m_{i}}(w)\geq 1-\gamma$, which happens with
probability $\gamma$. Consequently, utility at least $U(r_{w_{i}},1)-L$ is
achieved with probability at least $\gamma$.

For each Phase 2 proposal these probabilities are independent as they reflect
$m_{i}$’s private scores for each of these proposals. Therefore the
probability that there is no proposal providing $m_{i}$ a loss of at most $L$
is at most

$\displaystyle\big{(}1-\gamma\big{)}^{\alpha\beta
n/2}\leq\exp(\alpha\beta\gamma n/2).$

∎

Concluding the proof of Lemma 4.1: The overall failure probability summed over
all $n$ choices of $i$ is

$\displaystyle
n\cdot\exp(-\alpha(n-1)/12)+n\cdot\exp(-\alpha(n-1)/24)+n\exp(-\alpha\beta
n/8)+n\cdot\exp(-\alpha\beta\gamma n/2).$

∎

###### Proof.

(Of Claim 4.4.) First, we simplify the action space by viewing the decisions
as being made on a discrete utility space, as specified in the next claim,
proved in the appendix.

######  Claim 4.6.

For any $\delta>0$, there is a discrete utility space in which for each woman
the probability of selecting $m_{i}$ is only increased, and the probability of
having any differences in the sequence of actions in the original continuous
setting and the discrete setting is at most $\delta$.

We represent the possible computations of the double-cut DA in this discrete
setting using a tree $T$. Each woman will be going through her possible
utility values in decreasing order, with the possible actions of the various
women being interleaved in the order given by the DA processing. Each node $u$
corresponds to a woman $w$ processing her next utility value. The possible
choices at this utility are each represented by an edge descending from $u$.
These choices are:

i. Proposing to some man (among those men $w$ has not yet proposed to); or

ii. “no action”. This corresponds to $w$ making no proposal achieving the
current utility.

We observe the following important structural feature of tree $T$. Let $S$ be
the subtree descending from the edge corresponding to woman $w$ proposing to
$m_{i}$; in $S$ there are no further actions of $w$, i.e. no nodes at which
$w$ makes a choice, because the double cut DA cuts at the proposal to $m_{i}$.

The assumption that ${\cal B}_{1}$ and ${\cal B}_{2}$ do not occur means that
for all $i$, $h_{i}<\tfrac{3}{2}\alpha(n-1)$ and
$\ell_{i}>\tfrac{5}{2}\alpha(n-1)$, and therefore
$\ell_{i}-h_{i}>\alpha(n-1)$.

At each leaf of $T$, up to $i+h_{i}-1$ women will have been matched with
someone other than $m_{i}$. The other women either finished with a proposal to
$m_{i}$ or both failed to match and did not propose to $m_{i}$. Let $w$ be a
woman in the latter category. Then, on the path to this leaf, $w$ will have
traversed edges corresponding to a choice at each discrete utility in the
range $[V(r_{m_{i}}-\alpha,1),V(1,1)]$.

We now create an extended tree, $T_{x}$, by adding a subtree at each leaf;
this subtree will correspond to pretending there were no matches; the effect
is that each women will take an action at all their remaining utility values
in the range $[V(r_{m_{i}}-\alpha,1),V(1,1)]$, except that in the sub-subtrees
descending from edges that correspond to some woman $w$ selecting $m_{i}$, $w$
has no further actions. For each leaf in the unextended tree, the probability
of the path to that leaf is left unchanged. The probabilities of the paths in
the extended tree are then calculated by multiplying the path probability in
the unextended tree with the probabilities of each woman’s choices in the
extended portion of the tree.

Next, we create an artificial mechanism $\mathcal{M}$ that acts on tree
$T_{x}$. The mechanism $\mathcal{M}$ is allowed to put $i+h_{i}-1$ “blocks” on
each path; blocks can be placed at internal nodes. A block names a woman $w$
and corresponds to her matching (but we no longer think of the matches as
corresponding to the outcome of the edge selection; they have no meaning
beyond making all subsequent choices by this woman be the “no action” choice).

DA can be seen as choosing to place up to $i+h_{i}-1$ blocks at each of the
nodes corresponding to a leaf of $T$. $\mathcal{M}$ will place its blocks so
as to minimize the probability $p$ of paths with at least
$\tfrac{1}{2}\alpha\beta n$ women choosing edges to $m_{i}$. Clearly $p$ is a
lower bound on the probability that the double-cut DA makes at least
$\tfrac{1}{2}\alpha\beta n$ proposals in Step 2. Given a choice of blocks we
call the resulting probability of having fewer than $\tfrac{1}{2}\alpha\beta
n$ women choosing edges to $m_{i}$ the _blocking probability_.

######  Claim 4.7.

The probability that $\mathcal{M}$ makes at least $\tfrac{1}{2}\alpha\beta n$
proposals to $m_{i}$ is at least $1-\exp(-\alpha\beta n/8)$.

######  Corollary 1.

The probability that the double-cut DA makes at least $\tfrac{1}{2}\alpha\beta
n$ proposals to $m_{i}$ is at least $1-\exp(-\alpha\beta n/8)$.

###### Proof.

For any fixed $\delta$, by Claim 4.7, the probability that $\mathcal{M}$ makes
at least $\tfrac{1}{2}\alpha\beta n$ proposals to $m_{i}$ is at least
$1-\exp(-\alpha\beta n/8)$. By construction, the probability is only larger
for the double-cut DA in the discrete space.

Therefore, by Claim 4.1, the probability that the double-cut DA makes at least
$\tfrac{1}{2}\alpha\beta n$ proposals to $m_{i}$ in the actual continuous
space is at least $1-\exp(-\alpha\beta n/8)-\delta$, and this holds for any
$\delta>0$, however small. Consequently, this probability is at least
$1-\exp(-\alpha\beta n/8)$. ∎

###### Proof.

(Of Claim 4.7.) We will show that the most effective blocking strategy is to
block as many women as possible before they have made any choices. This leaves
at least $(i+\ell_{i})-(i-1+h_{i})\geq 1+\alpha(n-1)\geq\alpha n$ women
unmatched. Then, as we argue next, each of these remaining at least $\alpha n$
women $w$ has independent probability at least $\beta$ that their proposal to
$m_{i}$ is cutoff-surviving. To be cutoff-surviving, it suffices that
$V(r_{m_{i}},s_{w}(m_{i}))\geq V(r_{m_{i}}-\alpha,1)$. But we know by (1) that
$V(r_{m_{i}}-\alpha,1)\leq V(r_{m_{i}},1-\beta)$, and therefore it suffices
that $s_{w}(m_{i})\geq 1-\beta$, which occurs with probability $\beta$.

Consequently, in expectation, there are at least $\alpha\beta n$ proposals to
$m_{i}$, and therefore, by a Chernoff bound, at least $\tfrac{1}{2}\alpha\beta
n$ proposals with probability at least $\exp(-\alpha\beta n/8)$.

We consider the actual blocking choices made by $\mathcal{M}$ and modify them
bottom-up in a way that only reduces the probability of there being
$\tfrac{1}{2}\alpha\beta n$ or more proposals to $m_{i}$.

Clearly, ${\mathcal{M}}$ can choose to block the same maximum number of women
on every path as it never hurts to block more women (we allow the blocking of
women who have already proposed to $m_{i}$ even though it does not affect the
number of proposals to $m_{i}$).

Consider a deepest block at some node $u$ in the tree, and suppose $b$ women
are blocked at $u$. Let $v$ be a sibling of $u$. As this is a deepest block,
there will be no blocks at proper descendants of $u$, and furthermore as there
are the same number of blocks on every path, $v$ will also have $b$ blocked
women.

Observe that if there is no blocking in a subtree, then the probability that a
woman makes a proposal to $m_{i}$ is independent of the outcomes for the other
women. Therefore the correct blocking decision at node $u$ is to block the $b$
women with the highest probabilities of otherwise making a proposal to
$m_{i}$, which we call their _proposing probabilities_ ; the same is true at
each of its siblings $v$.

Let $x$ be $u$’s parent. Suppose the action at node $x$ concerns woman
$\widetilde{w}_{x}$. Note that the proposing probability for any woman
$w\neq\widetilde{w}_{x}$ is the same at $u$ and $v$ because the remaining
sequence of actions for woman $w$ is the same at nodes $u$ and $v$, and as
they are independent of the actions of the other women, they yield the same
probability of selecting $m_{i}$ at some point.

We need to consider a number of cases.

Case 1. $w$ is blocked at every child of $x$.
Then we could equally well block $w$ at node $x$.

Case 2. At least one woman other than $\widetilde{w}_{x}$ is blocked at some
child of $x$.
Each such blocked woman $w$ has the same proposing probability at each child
of $x$. Therefore by choosing to block the women with the highest proposing
probabilities, we can ensure that at each node either $\widetilde{w}_{x}$ plus
the same $b-1$ other women are blocked, or these $b-1$ woman plus the same
additional woman $w^{\prime}\neq\widetilde{w}_{x}$ are blocked. In any event,
the blocking of the first $b-1$ women can be moved to $x$.

Case 2.1. $\widetilde{w}_{x}$ is not blocked at any child of $x$.
Then the remaining identical blocked woman at each child of $x$ can be moved
to $x$.

Case 2.2. $\widetilde{w}_{x}$ is blocked at some child of $x$ but not at all
the children of $x$.
Notice that we can avoid blocking $\widetilde{w}_{x}$ at the child $u$ of $x$
corresponding to selecting $m_{i}$, as the proposing probability for
$\widetilde{w}_{x}$ after it has selected $m_{i}$ is $0$, so blocking any
other women would be at least as good. Suppose that $w\neq\widetilde{w}_{x}$
is blocked at node $u$.

Let $v$ be another child of $x$ at which $\widetilde{w}_{x}$ is blocked.
Necessarily, $p_{v,\widetilde{w}_{x}}$, the proposing probability for
$\widetilde{w}_{x}$ at node $v$, is at least the proposing probability
$p_{v,w}$ for $w$ at node $v$ (for otherwise $w$ would be blocked at node
$v$); also, $p_{v,w}$ equals the proposing probability for $w$ at every child
of $x$ including $u$; in addition, $p_{v,\widetilde{w}_{x}}$ equals the
proposing probability for $\widetilde{w}_{x}$ at every child of $x$ other than
$u$. It follows that $w$ is blocked at $u$ and $\widetilde{w}_{x}$ can be
blocked at every other child of $x$. But then blocking $\widetilde{w}_{x}$ at
$x$ only reduces the proposing probability.

Thus in every case one should move the bottommost blocking decisions at a
collection of sibling nodes to a single blocking decision at their parent. ∎

∎

##  5 Making Fewer Proposals

We identify a sufficient set of edges that contains all stable matchings, and
on which the DA algorithm produces the same outcome as when it runs on the
full edge set.

######  Definition 7 (Viable edges).

An edge $(m,w)$ is _man-viable_ if, according to $m$’s preferences, $w$ is at
least as good as the woman he is matched to in the man-pessimal stable match.
Woman-viable is defined symmetrically. An edge is _viable_ if it is both man
and woman-viable. $E_{v}$ is the set of all viable edges.

######  Lemma 5.1.

Running woman-proposing DA with the edge set restricted to $E_{v}$ and with
any superset obtained via loss thresholds, including the full edge set,
results in the same stable matching.

###### Proof.

Suppose a new stable matching, $S$, now exists in the restricted edge set: it
could not be present when using the full edge set, therefore there must be a
blocking edge $(m,w)$ in the full edge set. But neither $m$ nor $w$ would have
removed this edge when forming their restricted edge set since for both of
them it is better than an edge they did not remove (the edge they are matched
with in $S$).

It follows that w.h.p. the set of stable matchings is the same when using
$E_{v}$ (or any super set of it generated by truncation with larger loss
thresholds) and the whole set. Thus woman-proposing DA run on the restricted
edge set will yield the same stable matching as on the full edge set.

∎

###### Proof.

(Of Theorem 3.2.) If $\mathcal{E}$ occurs, the set of acceptable edges
contains all the viable edges. Furthermore, the acceptable edges are defined
by means of loss thresholds. The result now follows from Lemma 5.1. ∎

For some of the very bottommost agents, almost all edges may be acceptable.
However, in the bounded derivatives model, with slightly stronger constraints
on the derivatives, we also show (see Appendix H) the existence of an
$\epsilon$-Bayes-Nash equilibrium in which all but a bottom $\Theta((\ln
n/n)^{1/3})$ fraction of agents use only $\Theta(\ln n)$ edges, and all agents
propose using at most $\Theta(\ln^{2}n)$ edges, with $\epsilon=O(\ln
n/n^{1/3})$.

##  6 Numerical Simulations

We present several simulation results which are complementary to our
theoretical results. Throughout this section, we focus on the linear separable
model.

###  6.1 NRMP Data

We used NRMP data to motivate some of our choices of parameters for our
simulations. The NRMP provides extensive summary data [19]. We begin by
discussing this data.

Over time, the number of positions and applicants has been growing. We mention
some numbers for 2021. There were over 38,000 positions available and a little
over 42,000 applicants. The main match using the DA algorithm (modified to
allow for couples, who comprise a little over 5% of the applicants) filled
about 95% of the available positions. The NRMP also ran an aftermarket, called
SOAP, after which about 0.5% of the positions remained unfilled.

The positions cover many different specialities. These specialities vary
hugely in the number of positions available, with the top 11, all of size at
least 1,000, accounting for 75% of the positions. In addition, about 75% of
the doctors apply to only one speciality. We think that as a first
approximation, w.r.t. the model we are using, it is reasonable to view each
speciality as a separate market. Accordingly, we have focused our simulations
on markets with 1,000–2,000 positions (though the largest speciality in the
NRMP data had over 9,000 positions).

On average, doctors listed 12.5 programs in their preference lists, hospital
programs listed 88 doctors, and the average program size was 6.5 (all numbers
are approximate). While there is no detailed breakdown of the first two
numbers, it is clear they vary considerably over the individual doctors and
hospitals. For our many-to-one simulations we chose to use a fixed size for
the hospital programs. Our simulations cause the other two numbers to vary
over the individual doctors and programs because the public ratings and
private scores are chosen by a random process.

###  6.2 Numbers of Available Edges

The first question we want to answer is how long do the preference lists need
to be in order to have a high probability of including all acceptable edges,
for all but the bottommost agents?

We chose bottommost to mean the bottom 20% of the agents, based on where the
needed length of the preference lists started to increase in our experiments
for $n=\text{1,000--2,000}$.

We ran experiments with $\lambda=0.5,0.67,0.8$, corresponding to the public
rating having respectively equal, twice, and four times the weight of the
private scores in their contribution to the utility. We report the results for
$\lambda=0.8$. The edge sets were larger for smaller values of $\lambda$, but
the results were qualitatively the same. We generated 100 random markets and
determined the smallest value of $L$ that ensured all agents were matched in
all 100 markets. $L=0.12$ sufficed. In Figure 2, we show results by decile of
women’s rank (top 10%, second 10%, etc.), specifically the average length of
the preference list and the average number of edges proposed by a woman in
woman-proposing DA, over these 100 randomly generated markets. We also show
the max and min values over the 100 runs; these can be quite far from the
average value. Note that the min values in Figure 2(a) are close to the max
values in Figure 2(b), which suggests that being on the proposing side does
not significantly reduce the value of $L$ that the women could use compared to
the value the men use. We also show data for a typical single run in Figure 3.

(a) Number of edges in the acceptable edge set, per woman, by decile; average
in blue with circles, minimum in red with stars. ($n=\text{2,000}$,
$\lambda=0.8$, $L=0.12$.)

(b) Number of edges in the acceptable edge set proposed during the run of DA,
per women, by decile; average in blue with circles, maximum in red with stars.

Figure 2: One-to-one case: summary statistics.

(a) Number of edges in the acceptable edge set for each woman.

(b) Number of edges in the acceptable edge set proposed by each woman.

Figure 3: One-to-one case: a typical run.

We repeated the simulation for the many-to-one setting. In Figure 4, we show
the results for 2000 workers and 250 companies, each with 8 positions. Now, on
average, a typical worker (i.e. among the top 80%) has an average preference
list length of 55 and makes 7 proposals.

(a) Many to One Setting: Number of edges in the acceptable edge set per
worker, by decile; average in blue with circles, minimum in red with stars.
($n_{w}=\text{2,000}$, $d=8$, $\lambda=0.8$, $L_{c}=0.14$, $L_{w}=0.24$.)

(b) Number of edges in the acceptable edge set proposed during the run of DA,
per worker, by decile; average in blue with circles, maximum in red with
stars.

Figure 4: Many to One Setting.

The one-to-one results show that for non-bottommost agents, the preference
lists have length 150 on the average, while women make 30 proposals on the
average (these numbers are slightly approximate). What is going on? We believe
that the most common matches provide a small loss or gain ($\Theta(n^{-1/3})$
in our theoretical bounds) as opposed to the maximum loss possible
($\Theta(n^{-1/3}\ln^{1/3}n)$ in our theoretical bounds), as is indicated by
our distribution bound on the losses (see item 4 in Section E.1). The question
then is where do these edges occur in the preference list, and the answer is
about one fifth of the way through (for one first has the edges providing a
gain, which only go to higher up agents on the opposite side, and then one has
the edges providing a loss, and these go both up and down). However, a few of
the women will need to go through most of their list, as indicated by the fact
that the max and min lines (for example in Figure 4) roughly coincide.

This effect can also be seen in the many-to-one experiment but it is even more
stark on the worker’s side. The reason is that the number of companies with
whom a worker $w$ might match which are above $w$, based on their public
ratings alone, is $\Theta(L_{c}n_{c})$, while the number below $w$ is
$\Theta(L_{w}n_{c})$, a noticeably larger number. (See Appendix F.1 for a
proof of these bounds.) The net effect is that there are few edges that
provide $w$ a gain, and so the low-loss edges, which are the typical matches,
are reached even sooner in this setting.

Now we turn to why the number of edges in the available edge set per woman
changes at the ends of the range. There are two factors at work. The first
factor is due to an increasing loss bound as we move toward the bottommost
women, which increases the sizes of their available edge sets. The second
factor is due to public ratings. For a woman $w$ the range of men’s public
ratings for its acceptable edges is
$[r_{m}-\Theta(\overline{L}),r_{m}+\Theta(\overline{L})]$, where $m$ is
aligned with $w$. But at the ends a portion of this range will be cut off,
reducing the number of acceptable edges, with the effect more pronounced for
low public ratings. Because $\lambda=0.8$, initially, as we move to lower
ranked women, the gain due to increasing the loss bound dominates the loss due
to a reduced public rating range, but eventually this reverses. Both effects
can be clearly seen in Figure 3(a), for example.

###  6.3 Unique Stable Partners

Another interesting aspect of our simulations is that they showed that most
agents have a unique stable partner. This is similar to the situation in the
popularity model when there are short preference lists, but here this result
appears to hold with full length preference lists. In Figure 5, we show the
outcome on a typical run and averaged over 100 runs, for $n=\text{2,000}$ in
the one-to-one setting. We report the results for the men, but as the setting
is symmetric they will be similar for the women. On the average, among the top
90% of agents by rank, 0.5% (10 of 1,800) had more than one stable partner,
and among the remainder another 2% had multiple stable partners (40 of 200).

Also, as suggested by the single run illustrated in Figure 5(a), the pair
around public rank 1,600 and the triple between 1,200 and 1,400 have multiple
stable partners which they can swap (or exchange via a small cycle of swaps)
to switch between different stable matchings. This pattern is typical for the
very few men with multiple stable partners outside the bottommost region.

(a) Public ranks of men with multiple stable partners in a typical run.

(b) Average numbers of men with multiple stable partners, by decile.

Figure 5: Unique stable partners, one-to-one setting.

###  6.4 Constant Number of Proposals

Our many-to-one experiments suggest that the length of the preference lists
needed by our model are larger than those observed in the NRMP data. In
addition, even though there is a simple rule for identifying these edges, in
practice the communication that would be needed to identify these edges may
well be excessive. In light of this it is interesting to investigate what can
be done when the agents have shorter preference lists.

We simulated a strategy where the workers’ preference lists contain only a
constant number of edges. We construct an Interview Edge Set which contains
the edges $(w,c)$ satisfying the following conditions:

  1. 1.

Let $r_{w}$ and $r_{c}$ be the public ratings of $w$ and $c$ respectively.
Then $|r_{w}-r_{c}|\leq p$.

  2. 2.

The private score $w$ has for $c$ as well as the private score of $c$ for $w$
are both greater than $q$.

We choose the parameters $p$ and $q$ so as to have 15 edges per agent on
average. Many combinations of $p$ and $q$ would work. We chose a pair that
caused relatively few mismatches. We then ran worker proposing DA on the
Interview Edge Set.

One way of identifying these edges is with the following communication
protocol: the workers signal the companies which meet their criteria (the
workers’ criteria); the companies then reply to those workers who meet their
criteria. In practice this would be a lot of communication on the workers’s
side, and therefore it may be that an unbalanced protocol where the workers
use a larger $q_{w}$ as their private score cutoff and the companies a
correspondingly smaller $q_{c}$ is more plausible. Clearly this will affect
the losses each side incurs when there is a match, but we think it will have
no effect on the non-match probability, and as non-matches are the main source
of losses, we believe our simulation is indicative. We ran the above
experiment with $p=0.19$ and $q=0.60$, with the company capacity being $8$.
Figure 6(a) shows the locations of unmatched workers in a typical run of this
experiment while 6(b) shows the average numbers of unmatched workers per
quantile (of public ratings) over $100$ runs. We observe that the number of
unmatched workers is very low (about 1.5% of the workers) and most of these
are at the bottom of the public rating range.

Figure 6(c) compares the utility obtained by the workers in the match obtained
by running worker-proposing DA on the Interview Edge Set to the utility they
obtain in the worker-optimal stable match. We observe that only a small number
of workers have a significantly worse outcome when restricted to the Interview
Edge Set.

(a) Public ranks of unmatched workers in a typical run.

(b) Average numbers of unmatched workers by public rating decile.

(c) Distribution of workers’ utilities with worker-proposing DA: (full edge
set result) $-\text{(Interview edge set result)}$

Figure 6: Constant number of proposals.

##  7 Discussion and Open Problems

Our work shows that in the bounded derivatives model, apart from a sub-
constant fraction of the agents, each of the other agents has $O(\ln n)$
easily identified edges on their preference list which cover all their stable
matches w.h.p.

As described in Section 6, our experiments for the one-to-one setting yield a
need for what appear to be impractically large preference lists. While the
results in the many-to-one setting are more promising, even here the
preference lists appear to be on the large side. Also, while our rule for
identifying the edges to include is simple, in practice it may well require
too much communication to identify these edges. At the same time, our outcome
is better than what is achieved in practice: we obtain a complete match with
high probability, whereas in the NRMP setting a small but significant
percentage of positions are left unfilled. Our conclusion is that it remains
important to understand how to effectively select smaller sets of edges.

In the popularity model, it is reasonable for each agent to simply select
their favorite partners. But in the current setting, which we consider to be
more realistic, it would be an ineffective strategy, as it would result in
most agents remaining unmatched. Consequently, we believe the main open issue
is to characterize what happens when the number of edges $k$ that an agent can
list is smaller than the size of the allowable edge set. We conjecture that
following a simple protocol for selecting edges to list, such as the one we
use in our experiments (see Section 6.4), will lead to an $\epsilon$-Bayes-
Nash equilibrium, where $\epsilon$ is a decreasing function of $k$. Strictly
speaking, as the identification of allowable edges requires communication, we
need to consider the possibility of strategic communication, and so one would
need to define a notion of $\epsilon$-equilibrium akin to a Subgame Perfect
equilibrium. We conjecture that even with this, it would still be an
$\epsilon$-equilibrium.

Finally, it would be interesting to resolve whether the experimentally
observed near uniqueness of the stable matching for non-bottom agents is a
property of the linear separable model. We conjecture that in fact it also
holds in the bounded derivatives model.

##  Appendix A Overview of the Appendices

Here we provide an overview of the appendices that follow.

Appendix B provides the omitted proofs of claims from the main body of the
paper. Appendix C defines all the utility models we consider, Appendix D
states the remaining results, and Appendix E gives sketch proofs of all these
results. Complete analyses are given in the following appendices: The upper
bound results are shown in Appendix F; they are based on the key ideas
involved in proving Theorems 3.1 and 3.2. The lower bounds are shown in
Appendix G. The analysis of the $\epsilon$-Nash equilibrium is given in
Appendix H; this uses ideas from our analysis of Theorem 3.1 as well as
several other ideas, resulting in a quite involved proof. Finally, further
experimental results are described in Appendix I.

##  Appendix B Missing Proofs

###### Proof.

(Of Claim 4.2.) We prove the bound for an arbitrary man $m$ with public rating
$r_{m}$. The expected number $n_{x}$ of men other than $m$ in
$M[r_{m}-\alpha,r_{m}]$ is $\alpha(n-1)$. This bound depends on the
independent random choices of the men’s public ratings. Thus, by a Chernoff
bound,

$\displaystyle\Pr[n_{x}\geq\tfrac{3}{2}\alpha(n-1)]\leq\exp(\alpha(n-1)/12).$

Now, we apply a union bound to all $n$ men to obtain the stated result. ∎

###### Proof.

(Of Claim 4.3.) We prove the bound for an arbitrary woman $w$ with public
rating $r_{w}\geq 3\alpha$. The expected number $n_{y}$ of women other than
$w$ in $W[r_{w}-3\alpha,r_{m}]$ is $3\alpha(n-1)$. This bound depends on the
independent random choices of the women’s public ratings. Thus, by a Chernoff
bound,

$\displaystyle\Pr[n_{y}\leq\tfrac{5}{2}\alpha(n-1)]\leq\exp(\alpha(n-1)/24).$

Now, we apply a union bound to all $n$ women to obtain the stated result. ∎

###### Proof.

(Of Claim 4.6.) We do this in such a way that for each woman the probability
of selecting $m_{i}$ is only increased, and the probability of having any
differences in the sequence of actions in the original continuous setting and
the discrete setting is at most $\delta$. We detail how to construct this
discrete utility space in the appendix. The space depends on $\delta$, which
can be arbitrarily small. For each man $m$ we partition the interval
$[V(r_{m},0),V(r_{m},1)]$ of utilities it can provide into the following $z$
subintervals:
$[V(r_{m},0),V(r_{m},1/z)),[V(r_{m},1/z),V(r_{m},2/z)),\ldots,[V(r_{m},(z-2)/z),V(r_{m},(z-1)/z)),[V(r_{m},(z-1)/z),V(r_{m},1)]$.
Note that the probability that woman $w$’s edge to $m$ occurs in any one
subinterval is $1/z$. Over all $n$ men this specifies $n(z-1)$ utility values
that are partitioning points. Now, for each man $m$, we partition the interval
$[V(r_{m},0),V(r_{m},1)]$ about all $n(z-1)$ of these points, creating
$n(z-1)+1$ subintervals. The values at these partition points plus the
endpoint $V(r_{m},0)$ are the discrete utilities available to the women for
evaluating man $m$, obtained by rounding down her actual utility.

Consider a single interval $I=[V(r_{m},a),V(r_{m},b))$ and an arbitrary woman
$w$. Let $p^{I,c}_{j}$ be the probability that in the original continuous
private score setting, the probability exactly one man $m_{j}$ provides her a
utility in $I$, let $p^{I,c}_{\text{none}}$ be the probability no one provides
her a utility in $I$, and let $\overline{p}^{I,c}$ be the probability that two
or more men provide her a utility in $I$. Note that $\overline{p}^{I,c}\leq
n(n-1)/2z^{2}$. In the discrete setting, we remove the possibility of making
two proposals and increase the probability of selecting man $m_{i}$ by this
amount: the probability of selecting man $m_{j}\neq m_{i}$ alone, with private
score $a$ will be $p^{I,c}_{j}$, the probability of selecting no one will be
$p^{I,c}_{\text{none}}$, while the probability of selecting man $m_{i}$ with
private score $a$ becomes $p^{I,d}_{i}=p^{I,c}_{i}+\overline{p}^{I,c}$.

Recall that in the run of double-cut DA, each woman repeatedly makes the next
highest utility proposal. We view this as happening as follows. For each
successive discrete utility value, woman $w$ has the following choices.

i. she selects some man to propose to (among the men $w$ she has not yet
proposed to); or

ii. she takes “no action”. This corresponds to $w$ making no proposal
achieving the current utility.
Every run of DA in the continuous setting that does not have a woman selecting
two men over the course of a single utility interval will result in the
identical run in the discrete setting in terms of the order in which each
woman proposes to the men. Thus, the probability that in the discrete setting
$w$’s action in terms of who she selects and in what order differs from her
actions in the continuous setting is at most $n^{3}/2z\triangleq\delta/n$
(because, in each possible computation, $w$ makes at most $nz$ choices, and
for each choice the probability difference is at most $n^{2}/2z^{2})$.
Furthermore, the probability of selecting man $m_{i}$ is only increased. So
over all $n$ women, the probability of anything changing is at most $\delta$.
Clearly, $\delta$ can be made arbitrarily small. ∎

##  Appendix C More General Models

###  C.1 Utility Models

##### The General Utilities Model

There are $n$ men and $n$ women. Each man $m$ has a utility $U_{m,w}$ for the
woman $w$, and each woman $w$ has a utility $V_{m,w}$ for the man $w$. These
utilities are defined as

$\displaystyle U_{m,w}=U(r_{w},s_{m}(w)),\text{ and}$ $\displaystyle
V_{m,w}=V(r_{m},s_{w}(m)),$

where $r_{m}$ and $r_{w}$ are common public ratings, $s_{m}(w)$ and $s_{w}(m)$
are private scores specific to the pair $(m,w)$, and $U(\cdot,\cdot)$ and
$V(\cdot,\cdot)$ are continuous and strictly increasing functions from
$\mathbb{R}^{2}_{+}$ to $\mathbb{R}_{+}$.

The public ratings and private scores are drawn independently from
distributions with positive density functions with bounded support on
$\mathbb{R}_{+}$. We assume without loss of generality that all public ratings
and private scores are drawn uniformly and independently from $[0,1]$ since
there is always a change of variables that transforms them into uniform draws
while transforming the utility functions monotonically.

$U$ and $V$ are not explicitly assumed to be bounded. However they are
continuous and for the purpose of our analysis we can restrict the domain of
$U$ and $V$ to the product of the bounded supports of our ratings and score
distributions. These restricted $U$ and $V$ are continuous functions on a
compact set and hence are bounded. Now, WLOG, by scaling appropriately, we can
assume the range of $U$ and $V$ are both $[0,1]$.

##### The Bounded Derivatives Model

We add a notion of bounded derivatives to the general utilities model.

######  Definition 8.

A function $f(x,y):{\mathbb{R}}^{2}\rightarrow{\mathbb{R}}^{+}$ has
_$(\rho,\mu)$ -bounded derivatives_ if for all $(x,y)\in{\mathbb{R}}^{2}$,

$\displaystyle\rho\leq\partialderivative{f}{x}\Big{/}\partialderivative{f}{y}~{}~{}\text{\rm---
the ratio bound};$ $\displaystyle\partialderivative{f}{x}\leq\mu~{}~{}\hskip
23.12692pt\text{\rm--- the first derivative bound}.$

Note that this definition implies $\partialderivative{f}{y}$ is upper bounded
by $\mu/\rho$.

In the bounded derivatives model, the utility functions $U$ and $V$ are
restricted to having $(\rho,\mu)$-bounded derivatives, for some constants
$\rho,\mu>0$. In the linear separable model, which is a special case of this
model, $\mu=\lambda$ and $\rho=\lambda/(1-\lambda)$.

###  C.2 Other Generalizations

##### Unequal numbers of men and women

We generalize the above models to allow for $n$ women and $p$ men, where $n$
and $p$ need not be equal. Suppose that $n\leq p$. It is then convenient to
change the public rating ranges to be $[0,p/n]$ for the men and $[p/n-1,p/n]$
for the women. We proceed symmetrically when $n>p$. We will keep the private
score range at $[0,1]$. The effect of this change is to ensure that with high
probability the top $n$ public ratings for the men cover approximately the
same range as the women’s public ratings.

##### Many-to-one matchings

The stable matching problem has also been studied in the setting of many-to-
one matchings. For example, in the setting of employees and employers, often
employers want to hire multiple employees. For this setting, we will refer to
the two sides as companies and workers. Also, we will focus on the bounded
derivatives setting.

There are $n_{c}$ companies and $n_{w}$ workers. Each company has $d$
positions, meaning that it wants to match with $d$ workers. Each worker can be
hired by only one company. The total capacity of all the companies exactly
matches the number of workers, i.e. $n_{c}\cdot d=n_{w}$.333Our results
generalize easily to the case in which the number of workers differs from the
number of available positions. We omit the details.

$r_{c}$ will denote the public rating of company $c$, and $r_{w}$ the public
rating of worker $w$. Worker $w$ has private score $s_{w}(c)$ for company $c$,
and company $c$ has private score $s_{c}(w)$ for worker $w$.
$U(r_{w},s_{c}(w))$ denotes the utility company $c$ has for worker $w$, and
$V(r_{c},s_{w}(c))$ denotes the utility worker $w$ has for company $c$.

To define the loss in the many-to-one setting, we need to define a non-
symmetric notion of alignment of workers and companies.

######  Definition 9 (Alignment).

Suppose company $c$ has rank $i$ (as per its public rating). Let $w$ be the
worker of rank $d\cdot i$ (also as per its public rating). Then $w$ is aligned
with $c$. Likewise, suppose worker $w^{\prime}$ has rank $j$. Let $c^{\prime}$
be the company with rank $\lceil j/d\rceil$. Then $c^{\prime}$ is aligned with
$w^{\prime}$.

######  Definition 10 (Loss, cont.).

Let $c$ be a company and let $w$ be aligned with $c$. The _loss_ $c$ sustains
from a match of utility $u$ is defined to be $U(r_{w},1)-u$. Similarly, let
$w^{\prime}$ be a worker and let $c^{\prime}$ be aligned with $w^{\prime}$.
The _loss_ $w^{\prime}$ sustains from a match of utility $u$ is defined to be
$V(r_{c^{\prime}},1)-u$.

##  Appendix D Results

##### The Bounded Derivatives Model

We begin by stating our basic result for this model.

######  Theorem D.1.

In the bounded derivatives model, when there are $n$ men and $n$ women, for
any given constant $c>0$, for large enough $n$, with probability at least
$1-n^{-c}$, in every stable match, for every $i$, if
$r_{w_{i}}\geq\overline{\sigma}\triangleq 3\overline{L}/4\mu$, agent $m_{i}$
suffers a loss of at most $\overline{L}$, where $\overline{L}=\Theta((\ln
n/n)^{1/3})$, and similarly for the agents $w_{i}$.

Note that w.h.p., the public ratings of aligned agents are similar.

In words, w.h.p., all but the bottommost agents (those whose aligned agent has
public rating less than $\overline{\sigma}$) suffer a loss of no more than
$\overline{L}$. We call this high probability outcome $\mathcal{E}$.

By Theorem 3.2, the implication is that w.h.p. a woman can safely restrict her
proposals to her acceptable edges, or to any overestimate of this set of edges
obtained by her setting an upper bound on the loss she will accept from a
match. There is a small probability— at most $n^{-c}$—that this may result in
a less good outcome, namely the probability that $\mathcal{E}$ does not occur.

Then, w.h.p., every stable match gives each woman $w$, whose aligned agent $m$
has public rating $r_{m}\geq\overline{\sigma}=\Omega((\ln n/n)^{1/3})$, a
partner with public rating in the range
$[r_{m}-\overline{L}/\mu,r_{m}+5/4\overline{L}/\mu]$ (see appendix F.1). An
analogous statement applies to the men.

This means that if we are running woman-proposing DA, each of these women
might as well limit her proposals to her woman-acceptable edges, which is at
most the men with public ratings in the range $r_{m}\pm\Theta(\overline{L})$
for whom she has private scores of at least $1-\Theta(\overline{L})$. In
expectation, this yields $\Theta(n^{1/3}(\ln n)^{2/3})$ men to whom it might
be worth proposing. It also implies that a woman can have a gain of at most
$\Theta(\overline{L})$ compared to her target utility.

If, in addition, each man can inexpensively signal the women who are man-
acceptable to him, then the women can further limit their proposals to just
those men providing them with a signal; in the case of accurate signals, this
reduces the expected number of proposals these women can usefully make to just
$\Theta(\ln n)$.

Our next result provides a distribution bound on the losses. It states that
for most agents, the losses are at most $\Theta(\overline{L}/(\ln n)^{1/3})$,
with a geometrically decreasing number of agents facing larger losses.

######  Theorem D.2.

In the bounded derivatives model, when there are $n$ men and $n$ women, for
any given constant $c>0$, for large enough $n$, with probability at least
$1-n^{-c}$, in every stable match, among the agents whose aligned partner has
public score at least $\overline{\sigma}\triangleq 3\overline{L}/4\mu$, at
most $2n\cdot\exp(-(c+2)\ln n/2^{3h})$ men suffer a loss of more than
$\overline{L}/2^{h}$, for integer $h$ with $\frac{1}{3}\log\Big(\frac{(c+2)\ln
n}{\ln[n/3(c+2)\ln n]}\Big{missing})\leq h\leq\frac{1}{3}\log[(c+2)\ln n]$,
and likewise for the women.

We now generalize Theorem D.1 to possibly unequal numbers of men and women,
and also state what can be said for agents with low public ratings.

######  Theorem D.3.

Suppose there are $p$ men and $w$ woman, with $p\geq n$. Let $t\geq 1$ be a
parameter. In the bounded derivatives model, for any given constant $c>0$, for
large enough $n$, with probability at least $1-n^{-c}$, in every stable match,
every agent, except possibly the men whose aligned agents have public rating
less than $\tfrac{p-n}{n}+\tfrac{\overline{\sigma}}{t}$ and the women whose
aligned agents have public rating less than $\tfrac{\overline{\sigma}}{t}$,
suffers a loss of at most $\overline{L}t^{2}$, where $\overline{L}=\Theta((\ln
n/n)^{1/3})$ and $\overline{\sigma}=3\overline{L}/4\mu$.

Note that when $L=1$ (i.e. 100% loss), $t=\Theta((n/\ln n)^{1/6})$ and
therefore $\overline{\sigma}/t=\Theta((\ln n)/n)^{1/2})$, providing a lower
bound on the range for which this result bounds the loss.

Setting $t=1$ and $p=n$ yields Theorem D.1.

The implication is similar to that for Theorem D.1, but as $t$ increases,
i.e., for women whose aligned agents have increasingly low public ratings, the
bound on the number of proposals she can usefully make grows by roughly a
$t^{2}$ factor.

#####  $\epsilon$-Bayes-Nash Equilibrium

######  Definition 11.

A function $f(x,y):{\mathbb{R}}^{2}\rightarrow{\mathbb{R}}^{+}$ has
_$(\rho_{\ell},\rho_{u},\mu_{\ell},\mu_{u})$ -bounded derivatives_ if for all
$(x,y)\in{\mathbb{R}}^{2}$,

$\displaystyle\text{\rm The ratio
bound:}~{}~{}\rho_{\ell}\leq\partialderivative{f}{x}\Big{/}\partialderivative{f}{y}\leq\rho_{u}.$
$\displaystyle\text{\rm The first derivative
bound:}~{}~{}\mu_{\ell}\leq\partialderivative{f}{x}\leq\mu_{u}.$

Then $f$ is said to have the _strong bounded derivative_ property. Note that
in the linearly separable model, $\rho_{\ell}=\rho_{u}$ and
$\mu_{\ell}=\mu_{u}$.

Let $t\geq 1$ be a parameter and $\overline{\sigma}=\Theta([\ln n/n]^{1/3})$.
Define. $L^{m}_{t}\triangleq U(r_{w},1)-U(r_{w}-\overline{\sigma}t^{2},1)$ and
$L^{w}_{t}\triangleq V(s_{m},1)-V(r_{m}-\overline{\sigma}t^{2},1)$. For this
to be meaningful when $r_{w}-\overline{\sigma}t^{2}<0$, we extend the
definition of $U$ to this domain as follows. For $s<0$,
$\partialderivative{U(r,s)}{r}=\mu_{\ell}$ and
$\partialderivative{U(r,s)}{s}=\rho_{\ell}$. We proceed analogously to handle
the case that $r_{m}-\overline{\sigma}t^{2}<0$. Define parameters
$\sigma_{m}=\beta/n^{1/3}$ and $\sigma_{w}=\nu/n^{1/3}$, where $\beta>1$ and
$\nu<1$ are constants. We then define $t_{m}=\overline{\sigma}/\sigma_{m}$ and
$t_{w}=\overline{\sigma}/\sigma_{w}$. Note that in the strongly bounded
derivatives model,
$L^{m}_{t_{m}}\leq\Theta\Big{(}\frac{\mu_{u}}{\beta^{2}}\cdot\frac{\ln
n}{n^{1/3}}\Big{)}$ and
$L^{w}_{t_{w}}\leq\Theta\Big{(}\frac{\mu_{u}}{\nu^{2}}\cdot\frac{\ln
n}{n^{1/3}}\Big{)}$.

######  Theorem D.4.

Let $\epsilon=\Theta(1/n^{1/3})$. There are constants $\beta>1$ and $\nu<1$
such that in the strongly bounded derivatives model, there exists an
$\epsilon$-Bayes-Nash equilibrium where, with probability a least $1-n^{c}$,
agents with public ratings greater than $\overline{\sigma}$ make at most
$\Theta(\ln n)$ proposals and all agents make at most $\Theta(\ln^{2}n)$
proposals. Furthermore, in this equilibrium, with probability a least
$1-n^{c}$, every man has a loss of at most $L^{m}_{t_{m}}$, and every woman
$w$ has a loss of at most $L^{w}_{t_{w}}$.

##### The General Utilities Model

######  Theorem D.5.

Let $0<\epsilon<1$, $0<\sigma<1$, and $c>0$ be constants. In the general
utilities model, for large enough $n$, with probability at least
$1-\exp(-\Theta(n))$, in every stable matching, every agent, except possibly
those whose aligned agents have public rating less than $\sigma$, suffers a
loss of at most $\epsilon$.

Clearly the smaller $\epsilon$, the smaller the ranges of public ratings and
private scores that can yield acceptable proposals; however, there does not
appear to be a simple functional relationship between $\epsilon$ and the sizes
of these ranges in this general model.

##### The Many to One Setting

Next, we state our many-to-one result, expressing it in terms of the $n_{w}$
workers and $n_{c}$ companies, each having $d$ positions. We now have possibly
different bounds

$\displaystyle\overline{L}_{w}$ $\displaystyle=\Theta([(\ln
n_{w})/n_{c}]^{1/3})=\Theta([(d\ln
n_{w})/n_{w}]^{1/3}),~{}~{}~{}~{}\text{and}$ $\displaystyle\overline{L}_{c}$
$\displaystyle=\left\\{\begin{array}[]{ll}\Theta((\max\\{d,\ln
n_{w}\\}/n_{w})^{1/3})&d=O((n_{w}/\ln n_{w})^{2/3})\\\ \Theta((d\ln
n_{w})/n_{w})&d=\Omega(n_{w}/\ln n_{w})^{2/3})\end{array}\right.$

on the losses for non-bottommost workers and companies. Analogous to the one-
to-one case, we define $\overline{\sigma}_{c}=3\overline{L}_{c}/4\mu$ and
$\overline{\sigma}_{w}=3\overline{L}_{w}/4\mu$, the public rating thresholds
below which these loss bounds need not hold.

######  Theorem D.6.

Let $\overline{L}_{c}$, $\overline{L}_{w}$, $\overline{\sigma}_{c}$ and
$\overline{\sigma}_{w}$ be as defined above. Suppose that $d=O((n/\ln
n)^{2/3})$. Then, for any given constant $k>0$, with probability at least
$1-n^{-k}$, in every stable match, every company, except possibly those whose
aligned agent has public rating less than $\overline{\sigma}_{w}$, suffers a
loss of at most $\overline{L}_{c}$, and every worker, except possibly those
whose aligned agent has public rating less than $\overline{\sigma}_{c}$,
suffers a loss of at most $\overline{L}_{w}$.

##### Lower Bounds

The next two theorems show that the bounded derivative result is tight in two
senses. First, we show that the bound $\overline{L}$ on the loss is tight up
to a constant factor.

######  Theorem D.7.

In the linear separable model with $\lambda=\tfrac{1}{2}$, if $n\geq 32,000$
and $L=\tfrac{1}{8}(\ln n/n)^{1/3}$, then with probability at least
$\tfrac{1}{4}n^{-1/8}$ there is no perfect matching, let alone stable
matching, in which every agent with public rating $\tfrac{3}{2}L$ or larger
suffers a loss of at most $L$. (Here $\mu=\tfrac{1}{2}$, so
$\tfrac{3}{2}L=3L/4\mu.)$

Next, we show that to obtain sub-constant losses in general, one needs
constant bounds on the derivatives. We first define a notion of a sub-constant
function, which we use to specify sub-constant losses.

######  Definition 12 (Sub-constant function).

A function $f(x):{\mathbb{R}}\rightarrow{\mathbb{R}}^{+}$ is sub-constant if
for every choice of constant $c>0$, there exists an $\overline{x}$ such that
for all $x\geq\overline{x}$, $f(x)\leq c$.

######  Theorem D.8.

Let $f:N\rightarrow{\mathbb{R}}^{+}$ be a continuous, strictly decreasing sub-
constant function, and let $\delta,\sigma\in(0,1)$ be constants. Then, in the
following two cases, there exist continuous and strictly increasing utility
functions $U(.,.)$ and $V(.,.)$ such that for some $\overline{n}>0$, for all
$n\geq\overline{n}$, with probability at least $1-\delta$, in every perfect
matching, some rank $i$ man $m_{i}$ or woman $w_{i}$ with public rating at
least $\sigma$ receives utility less than $U(r_{w_{i}},1)-f(n)$ or
$V(r_{m_{i}},1)-f(n)$, respectively.

i. $U(.,.)$ and $V(.,.)$ have derivatives w.r.t. their second variables that
are bounded by a constant, but for (at least) one of which the derivative
w.r.t. their first variable is not bounded by any constant.

ii. $U(.,.)$ and $V(.,.)$ have derivatives w.r.t. their first variables that
are bounded by a constant, but for (at least) one of which the derivative
w.r.t. their second variable is not bounded by any constant.

##  Appendix E Proof Sketches for the Remaining Results

In Section 3, we proved Theorem D.1 for the special case of the linear
separable model with $\lambda=1/2$. We will now briefly outline how we extend
the analysis to the bounded derivative model and the general utilities model,
as well as to the case where the number of men and women is unequal and the
setting of many-to-one matchings. The full analyses can be found in Appendix
F.

We will also briefly discuss our construction of an $\epsilon$-Bayes-Nash
equilibrium in the bounded derivatives model as well as sketch our lower bound
proofs in both the bounded derivatives and the general utility models. The
full proofs can be found in Appendices H and G, respectively.

###  E.1 Extending the Upper Bound Result

1\. Weaker bounds on the losses for agents with lower ranks.
This is obtained by reducing $\alpha$ to $\alpha/t$, where $t>1$, and
replacing $\overline{L}$ by $L=4\alpha t^{2}$. The only change occurs in
recalculating the loss probability.

2\. Unequal numbers of men and women.
The critical condition for the bound on $m_{i}$’s loss is $r_{w_{i}}\geq
3\alpha$. This simply states that there is a range of $3\alpha$ ratings below
$w_{i}$. But this statement is independent of how many agents there are on
each side. Similarly, the bound on $w_{i}$’s loss requires that there be a
range of $3\alpha$ ratings below $m_{i}$. So all one has to do is rephrase
these conditions in terms of $p$ and $n$, the numbers of men and women,
respectively.

3\. The bounded derivatives model.
It suffices to scale the values of $\alpha$, $\beta$, $\gamma$ and $L$ to take
account of the bounded derivative property so as to ensure that Equations (1)
and (2) still hold. As we shall see, setting $\beta=\alpha\rho$,
$\gamma=\alpha\rho$ and $L=4\alpha\mu$ suffices.

4\. The many-to-one result.
We actually analyze the many-to-many setting. The main issue is that a company
(replacing a man in the previous argument) seeks $d_{c}$ matches rather than 1
and a worker seeks $d_{w}$ matches. We need to restate Lemma 4.1, for now the
alignment we seek is between positions sought by the workers and provided by
the companies, rather than between men and women.

However, the significant change occurs in deducing the theorem, for now we
need to determine the probability that a company receives $d_{c}$ matches. The
remaining changes are due to replacing $n$, the number of men and of women,
with $n_{c}$ and $n_{w}$, the numbers of companies and workers, respectively.

5\. A distribution bound on the losses.
By reducing both $\alpha$ and $L$ by a factor $s>1$, we increase the failure
probability for a single agent from $n^{-(c+1)}$ to $n^{-(c+1)/s^{3}}$. This
implies, for example, that in expectation half the agents have a loss of
$O(1/n^{1/3})$. In fact an analysis along the lines of observation (3) in the
sketch proof shows that this bound holds with high probability.

###  E.2 Extensions to More General Models

1\. The bounded derivative setting.
The only places we use the bounds on the derivatives are to determine $\beta$,
$\gamma$, and $L$ satisfying (1) and (2). As we show in Appendix D,
$\beta=\gamma=\alpha\rho$, and $L=4\alpha/\mu$ suffice.

2\. The general utilities model.
Given constants $\epsilon,\sigma>0$, we need to choose $\alpha,\beta,\gamma>0$
and $n$ large enough so that (1) and (2) are satisfied. The existence of such
constant valued $\alpha$, $\beta$, and $\gamma$ follows using the fact that
$U$ and $V$, the utility functions, are continuous and strictly increasing.

###  E.3 $\epsilon$-Bayes-Nash Equilibrium

In the bounded derivative model, with slightly stronger constraints on the
derivatives, we also show the existence of an $\epsilon$-Bayes-Nash
equilibrium in which agents make relatively few proposals. Specifically, there
is an equilibrium in which no agent proposes more than $O(\ln^{2}n)$ times and
all but the bottommost $O((\ln n/n)^{1/3})$ fraction of the agents make only
$O(\ln n)$ proposals. Here $\epsilon=\Theta(\ln n/n^{1/3})$.

We use the idea of considering a run of DA with cuts just as in the proof of
Theorem D.1; in addition, the proposal receiving side will impose reservation
thresholds based on their public rank. We also apply the distribution bound on
losses described in (4) in the previous subsection. The resulting analysis is
somewhat involved (see Appendix H).

###  E.4 Lower Bounds

1\. The lower bound complementing the one-to-one upper bound.
The main idea is to show by a direct computation that for each woman, with
probability at least $1/n^{1/8}$, all her incident edges provide a loss of
more than $L$ to either her or her partner. We will need to exclude some low-
probability events in which the number of agents in an interval is far from
its expectation, and also eliminate the agents with public ratings less than
$\tfrac{3}{2}L$. The net effect is that with probability at least $1/4n^{1/8}$
some woman has no incident $(L,\tfrac{3}{2}L)$-acceptable edge, where
$L=\tfrac{1}{8}(\ln n/n)^{1/3}$, and hence with this probability there is no
matching using solely $(L,\tfrac{3}{2}L)$-acceptable edges. Consequently, in
order to obtain a stable matching with high probability, we need to increase
the value of $L$.

2\. The lower bound complementing the general utilities model upper bound.
To show that no sub-constant loss bound (such as $(\ln n/n)^{1/3}$) is
possible, we consider a loss bound that is shrinking (slowly) as a function of
$n$. For a given $n$, this can be expressed as a loss bound $\epsilon(n)$. We
provide two similar constructions as there are two separate derivative bounds.

Our first construction uses a utility function $U(s,v)=\tfrac{1}{2}(s+g(v))$,
with $g(1)=1$ and $g(\cdot)$ being unboundedly rapidly growing as
$v\rightarrow 1$. $g$ is designed to ensure that with high probability the
edges to the women with public ratings $s\geq 1-2\epsilon(n)$ all have private
scores less than $1-\epsilon(n)$. This will ensure that with high probability
$m_{1}$, the man with the highest public ranking, will have no edge providing
him a loss of at most $\epsilon(n)$. However slowly $\epsilon(n)$ decreases as
a function of $n$, we show that we can construct a corresponding $g$ that
grows suitably quickly. This construction demonstrates that the parameter
$\epsilon$ needs to be constant. Notice that our construction actually shows
that, in the general setting, w.h.p, there is not only no stable matching
where all high public rating agents face sub-constant losses, but in fact no
perfect matching.

##  Appendix F Proofs of the Remaining Upper Bound Results

###### Proof.

(Of Theorem D.1.) We now consider what changes occur when we are no longer
restricted to the linear separable model with $\lambda=\tfrac{1}{2}$.

First, we need to determine the values for $\beta$, $\gamma$ and
$\overline{L}$ implied by the bounded derivative parameters $\rho$ and $\mu$.
We show the following values, $\beta=\alpha\rho$, $\gamma=\alpha\rho$ and
$L=4\alpha\mu$, satisfy (1) and (2).

For by the definition of $\rho$, $V(r-\alpha,1)\leq
V(r,1-\alpha\rho)=V(r,1-\beta)$, satisfying (1). And by the definition of
$\rho$ and $\mu$, $U(r,1)-U(r-3\alpha,1-\gamma)\leq
U(r,1)-U(r-3\alpha-\gamma/\rho,1)\leq(3\alpha+\gamma/\rho)\mu=4\alpha\mu=L$,
satisfying (2).

To complete the argument, it suffices to determine the failure probability on
setting $L=\overline{L}$ when running the double-cut DA. Recall that the
failure probability (summed over the $2n$ men and women) is given by:

$\displaystyle p_{f}$
$\displaystyle=2n\cdot\exp(-\alpha(n-1)/12)+2n\cdot\exp(-\alpha(n-1)/24)+2n\exp(-\alpha\beta
n/8)+2n\cdot\exp(-\alpha\beta\gamma n/2)$ $\displaystyle\leq
2n\cdot\exp(-\alpha(n-1)/12)+2n\cdot\exp(-\alpha(n-1)/24)+2n\exp(-\alpha^{2}\rho
n/8)+2n\cdot\exp(-\alpha^{3}\rho^{2}n/2).$

We note that $\alpha=\overline{L}/4\mu$, and set
$\overline{L}=[128(c+2)\mu^{3}\ln n/(\rho^{2}n)]^{1/3}$. For large enough $n$
this ensures a failure probability of at most $n^{-c}$. ∎

###### Proof.

(Of Theorem D.3.) We now need to consider smaller intervals of men and women
below $m_{i}$ and $w_{i}$ respectively.

We set $\sigma=\overline{\sigma}/t$, where $t\geq 1$. We then set
$\alpha=\sigma/4$ and $\beta=\alpha\rho$ as before, but to keep the most
significant term in the probability bound unchanged
($2n\cdot\exp(-\alpha\beta\gamma n/2)$), we increase $\gamma$ by a factor of
$t^{2}$. We also set $L=\overline{L}t^{2}$.

The failure probability continues to be at most $n^{-c}$ for large enough $n$
so long as $\alpha\beta n=\Omega(c\ln n)$; this holds for $\sigma=\Omega((\ln
n)/n)^{1/2}$.

Now let’s consider what happens when there are $p$ men and $n$ women. We start
with the case $p\geq n$. Our key lemma is stated w.r.t. the rank $i$ man
$m_{i}$ and the rank $i$ woman $w_{i}$, and requires $r_{w_{i}}\geq 3\alpha$
when the bottom of the rating range is 0 for both men and women.

It is convenient to have the range of ratings for the men be $[0,p/n]$ and for
the women be $[p/n-1,p/n]$. The effect is that the expected values for
$r_{w_{i}}$ and $r_{m_{i}}$ are equal. The condition for $m_{i}$ to have a
loss of at most $L$ becomes $r_{w_{i}}\geq\tfrac{p}{n}+3\alpha$ (i.e. $w_{i}$
has a rating at least $3\alpha$ greater than the bottommost possible rating
for the women). But the condition for $w_{i}$ to have a loss of at most $L$
remains $r_{m_{i}}\geq 3\alpha$ (i.e. $m_{i}$ has a rating at least $3\alpha$
greater than the bottommost possible rating for the men).

Symmetric bounds apply when $n\geq p$. ∎

###### Proof.

(Of Theorem D.5) We set $\alpha=\sigma/3$ and $L=\epsilon$. Again, we need to
satisfy (1) and (2).

To define $\beta$ we begin by specifying a parameter $\beta(r,\alpha)$. There
are two cases. If $V(r-\alpha,1)\leq V(r,0)$, then $\beta(r,\alpha)=1$.
Otherwise, as $V$ is continuous and strictly increasing, there must be a value
$\beta(r,\alpha)>0$ such that $V(r-\alpha,1)=V(r,1-\beta(r,\alpha))$. Now, we
define $\beta=\min_{r\in[\alpha,1]}\\{\beta(r,\alpha)\\}$. As this is the
minimum of strictly positive values on a compact set, it follows that
$\beta>0$, also. Note that $V(r-\alpha,1)\leq V(r,1-\beta)$ for all
$r\in[\alpha,1]$, satisfying (1). Also, $\beta=\Theta(1)$ if
$\alpha=\Theta(1)$.

Similarly, to define $\gamma$ we begin by specifying a parameter
$\gamma(r,\alpha,\epsilon)$. Again, there are two cases. If
$U(r,1)-U(r-3\alpha,0)\leq L=\epsilon$ then $\gamma(r,\alpha,\epsilon)=1$.
Otherwise, as $U$ is continuous and strictly increasing, there must be a value
$\gamma(r,\alpha,\epsilon)>0$ such that
$U(r,1)-U(r-3\alpha,1-\gamma(r,\alpha,\epsilon))=\epsilon$. Now, we define
$\gamma\triangleq\min_{r\in[3\alpha,1]}\\{\gamma(r,\alpha,\epsilon)\\}$.
Again, as this is a minimum of strictly positive values on a compact set,
$\gamma>0$ also. Note that $U(r,1)-\epsilon\leq U(r-3\alpha,1-\gamma)$ for all
$r\in[3\alpha,1]$, satisfying (2). Also, $\gamma=\Theta(1)$ if
$\alpha=\Theta(1)$.

As $\sigma=\Theta(1)$, all of $\alpha,\beta,\gamma=\Theta(1)$. Therefore, by
Lemma 4.1, the failure probability is $\exp(-\Theta(n))$. ∎

Because the many-to-one setting is non-symmetric it is actually simpler to
analyze the many-to-many setting, many-to-one being just a special case of
this. We will use the terminology of workers and companies, for want of a
better alternative. (One could think of these workers as being consultants or
gig workers who seek multiple tasks at a time.)

In this setting there are $n_{c}$ companies $c_{1},c_{2},\ldots,c_{n_{c}}$,
and $n_{w}$ workers, $w_{1},w_{2},\ldots,w_{n_{w}}$, both ordered by their
public ranks. Each company has $d_{c}$ tasks, and each worker desires $d_{w}$
tasks. For simplicity, we suppose $n_{c}\cdot d_{c}=n_{w}\cdot d_{w}\triangleq
n$. We let $n_{\max}=\max\\{n_{c},n_{w}\\}$. There will be two loss
parameters, $\overline{L}_{c}$, for the companies, and $\overline{L}_{w}$, for
the workers. Finally, we use the notation $C(I)$ and $W(I)$, where $I$ is an
interval of public ratings, to denote, respectively, the companies and workers
with public ratings in the interval $I$.

######  Definition 13 (Alignment).

Suppose company $c$ has rank $i$. Let $w$ be the worker with rank $\lceil
d_{c}\cdot i/d_{w}\rceil$. Then $w$ is aligned with $c$. Likewise, suppose
worker $w^{\prime}$ has rank $j$. Let $c^{\prime}$ be the company with rank
$\lceil d_{w}\cdot j/d_{c}\rceil$. Then $c^{\prime}$ is aligned with
$w^{\prime}$.

######  Definition 14 (company-acceptable edges).

Let $0<\sigma_{c},\sigma_{w}<1$, $0<\overline{L}_{c},\overline{L}_{w}<1$ be
parameters. An edge $(c,w)$ is company-acceptable if either $c\in
C[0,\sigma_{c})$, or the utility $c$ gets from this match is at least
$U(r_{w^{\prime}},1)-\overline{L}_{c}$, where $w^{\prime}$ is the worker
aligned with $c$. Worker-acceptability requires either $c\in[0,\sigma_{w})$,
or utility at least $V(r_{c^{\prime}},1)-\overline{L}_{w}$, where $c^{\prime}$
is the company aligned with $w$. An edge is acceptable if it is both company
and worker-acceptable. (Strictly speaking, the definition is w.r.t. the four
parameters $\sigma_{c}$, $\sigma_{w}$, $\overline{L}_{c}$, and
$\overline{L}_{w}$, but for the sake of readability, we omit them from the
terms company- and worker-acceptable.)

######  Definition 15 (DA stops).

The workers _stop at public rating $r$_ if in each worker’s preference list
all the edges with utility less than $V(r,1)$ are removed. The workers _stop
at company $c$_ if in each worker’s preference list all the edges following
their edge to $c$ are removed. The workers _double cut at $c$ and public
rating $r$_, if they each stop at $c$ or $r$, whichever comes first. Companies
stopping and double cutting are defined similarly.

######  Theorem F.1.

Suppose that $d_{w}/d_{c}=O((n_{w}/\ln n_{\max})^{2/3})$. Then, in the bounded
derivatives model, for any given constant $k>0$, with probability at least
$1-n^{-k}$, in every stable matching, every company $c_{i}$, for which the
aligned worker $w_{j_{i}}$ has public rating at least
$\sigma_{w}=\Theta(\overline{L}_{w})$, suffers loss at most

$\displaystyle\overline{L}_{c}=\left\\{\begin{array}[]{ll}\Theta([(\ln
n_{\max})/n_{w}]^{1/3})&d_{c}=O(\ln n_{\max})\\\
\Theta([d_{c}/n_{w}]^{1/3})&\ln n_{\max}\leq d_{c}=O(d_{w}(n_{w}/\ln
n_{\max})^{2/3})\\\ \Theta(d_{c}\ln
n_{\max}/[d_{w}n_{w}])&d_{c}=\Omega(d_{w}(n_{w}/\ln
n_{\max})^{2/3})\end{array}\right.$

and a corresponding symmetric bound for the workers’ loss.

###### Proof.

We need to take account of the fact that each company seeks to fill $d_{c}$
positions and each worker seeks $d_{w}$ positions. So we slightly redefine the
double-cut DA to state that each worker who is not fully matched, i.e., who
has fewer than $d_{w}$ matches, keeps trying to match, stopping when she runs
out of proposals, or she is fully matched, or her next proposal is to $c_{i}$.

First, to avoid rounding issues, we assume $\alpha$ is chosen so that
$\alpha(n_{w}-\tfrac{5}{2})$ is an integer for the argument bounding
$\overline{L}_{c}$, and similarly $\alpha(n_{c}-\tfrac{5}{2})$ is an integer
for the argument bounding $\overline{L}_{w}$.

We introduce one more index: $j_{i}=\lceil d_{c}\cdot i/d_{w}\rceil$. We then
define $\ell_{i}=\lfloor
d_{c}(i+h_{i}-1)/d_{w}\rfloor+\alpha(n_{w}-\tfrac{5}{2})-j_{i}$ (this is where
we use the assumption that $\alpha(n_{w}-\tfrac{5}{2})$ is an integer as
$\ell_{i}$ has to be an integer). This will ensure that after running the
double cut DA, the number of not fully matched workers is at least
$\alpha(n_{w}-\tfrac{5}{2})$. To see this, note that the number of available
positions is $d_{c}(i+h_{i}-1)$ (remember $c_{i}$ is not matched in Step 1);
therefore, the number of fully matched workers is at most $\lfloor
d_{c}(i+h_{i}-1)/d_{w}\rfloor$ and therefore the number of not-fully matched
workers is at least $\ell_{i}+j_{i}-\lfloor
d_{c}(i+h_{i}-1)/d_{w}\rfloor\geq\lfloor
d_{c}(i+h_{i}-1)/d_{w}\rfloor+\alpha(n_{w}-\tfrac{5}{2})-\lfloor
d_{c}(i+h_{i}-1)/d_{w}\rfloor\geq\alpha(n_{w}-\tfrac{5}{2})$.

We need to make small changes to Claims 4.2–4.5 and to their proofs. It seems
simplest to restate and, as necessary, reprove the claims.

######  Claim F.1.

Let ${\mathcal{B}}_{1}$ be the event that for some $i$,
$h_{i}=\big{|}C[r_{c_{i}}-\alpha,r_{c_{i}})\big{|}\geq\tfrac{3}{2}\alpha(n_{c}-1)$.
${\mathcal{B}}_{1}$ occurs with probability at most
$n_{c}\cdot\exp(-\alpha(n_{c}-1)/12)$. The only randomness used in the proof
are the choices of the companies’ public ratings. An analogous bound applies
to the workers.

Its proof is unchanged. We just replace $n$ by $n_{c}$.

######  Claim F.2.

Let ${\mathcal{B}}_{2}$ be the event that for some $i$,
$\ell_{i}=\big{|}W[r_{w_{i}}-3\alpha,r_{w_{i}})\big{|}\leq\tfrac{5}{2}\alpha(n_{w}-1)$.
Then ${\mathcal{B}}_{2}$ occurs with probability at most
$n_{w}\cdot\exp(-\alpha(n_{w}-1)/24)$. The only randomness used in the proof
are the choices of the workers’ public ratings. An analogous bound applies to
the companies.

Its proof is unchanged. We just replace $n$ by $n_{w}$.

######  Claim F.3.

Let ${\mathcal{B}}_{3}$ be the event that between them, the workers with rank
at most $j_{i}+\ell_{i}$ make at least $\tfrac{1}{2}\alpha\beta(n_{w}-5/2)$
Step 2 proposals to $c_{i}$. If events ${\mathcal{B}}_{1}$ and
${\mathcal{B}}_{2}$ do not occur, then ${\mathcal{B}}_{3}$ occurs with
probability at most $\exp(-\alpha\beta(n_{w}-5/2)/8)$.

It’s proof is largely unchanged. The first issue is that now in the run of the
DA algorithm placing a block on a worker $w$ corresponds to $w$ having matched
$d_{w}$ times. The proof is otherwise unchanged as any unblocked worker will
run through her full utility range as before. However, the calculations change
as follows. The number of not-fully matched workers is at least

$\displaystyle d_{w}(j_{i}+\ell_{i})-d_{c}(i-1+h_{i})$ $\displaystyle\geq
d_{w}\cdot\frac{5}{2}\alpha(n_{w}-1)+d_{c}-d_{c}\cdot\frac{3}{2}\alpha(n_{c}-1)$
$\displaystyle\geq\alpha d_{w}n_{w}-\frac{5}{2}\alpha d_{w}\geq\alpha
d_{w}(n_{w}-\frac{5}{2}).$

This causes the replacement of $n$ by $n_{w}-5/2$ in the bounds.

######  Claim F.4.

If none of the events ${\mathcal{B}}_{1}$, ${\mathcal{B}}_{2}$, or
${\mathcal{B}}_{3}$ occur, then at least
$\tfrac{1}{4}\alpha\beta\gamma(n_{w}-5/2)$ of the Step 2 proposals to $c_{i}$
will each cause $c_{i}$ a loss of at most $\overline{L}_{c}$ with probability
at least $1-\exp(-\alpha\beta\gamma(n_{w}-5/2)/16)$.

To ensure $c_{i}$ receives at least $d_{c}$ proposals that each cause it a
loss at most $\overline{L}_{c}$, by Claim F.4, we need that

$\displaystyle\tfrac{1}{4}\alpha\beta\gamma\big{(}n_{w}-\tfrac{5}{2}\big{)}\geq
d_{c}.$ (3)

Then the overall failure probability summed over all companies is at most

$\displaystyle
n_{c}\cdot\exp(-\alpha(n_{c}-1)/12)+n_{w}\cdot\exp(-\alpha(n_{w}-1)/24)+n_{c}\exp(-\alpha\beta(n_{w}-5/2)/8)$
$\displaystyle+n_{c}\exp(-\alpha\beta\gamma(n_{w}-5/2)/16).$

In the bounded derivative setting, we continue to set $\beta=\alpha\rho$,
$\gamma=\alpha\rho$ and $\overline{L}_{c}=4\alpha\mu$. Then, for large enough
$n_{c},n_{w}$, with $\overline{L}_{c}\geq 4\mu\cdot[16(k+2)\ln
n_{\max}/\rho^{2}(n_{w}-5/2)]^{1/3}$ and $\overline{L}_{c}\geq 48\mu(k+2)\ln
n_{\max}/(n_{c}-1)\geq 47\mu(d_{c}/d_{w})[(k+2)\ln n_{\max}/(n_{w}-1)]$, the
overall failure probability is at most $n_{\max}^{-k}$. The first of the two
bounds on $\overline{L}_{c}$ dominates if $d_{c}/d_{w}=O((n_{w}/\ln
n_{\max})^{2/3})$. In addition, with $\overline{L}_{c}\geq
4\mu\cdot(4d_{c}/\rho^{2}(n_{w}-\tfrac{5}{2}))^{1/3}$, (3) is satisfied. Thus,
the overall condition is that $\overline{L}_{c}=\Omega(\max\\{d_{c},\ln
n_{\max}\\}/n_{w})^{1/3})$.

The corresponding bound $\overline{L}_{w}=\Omega(\max\\{d_{w},\ln
n_{\max}\\}/n_{c})^{1/3})$ can be deduced using the company-proposing DA.

It remains to prove Claim F.4, which we do below. ∎

###### Proof.

(Of Claim F.4.) As $\mathcal{B}_{3}$ does not occur, by Claim F.3, there are
at least $\tfrac{1}{2}\alpha\beta(n_{w}-5/2)$ Step 2 proposals to $c_{i}$. As
explained in observation (4) of the sketch proof, each Step 2 proposal has
independent probability at least $\gamma$ of causing $c_{i}$ a loss of at most
$\overline{L}_{c}$ (the independence is because this is due to the private
score of $c_{i}$ for this proposal). In expectation, there are at least
$\tfrac{1}{2}\alpha\beta\gamma(n_{w}-5/2)$ of the proposals causing $c_{i}$ a
loss of at most $\overline{L}_{c}$, and by a Chernoff bound at least
$\tfrac{1}{4}\alpha\beta\gamma(n_{w}-5/2)$ such proposals to $c_{i}$ with
failure probability at most $\exp(-\alpha\beta\gamma(n_{w}-5/2)/16)$. ∎

###  F.1 Range of Public Ratings for Acceptable Edges

Here we prove that in the one-to-one bounded derivative setting, with high
probability, for each $i$, the acceptable edges from women $w_{i}$ are to men
with public rating in the range $[r_{m_{i}}-4\alpha,r_{m_{i}}+5\alpha]$, which
we call $w_{i}$’s _cone_. A symmetric bound applies to the men.

We then obtain a similar bound for the many-to-one setting.

######  Theorem F.2.

In the one-to-one bounded derivative setting with $n$ men and $n$ women, for
large enough $n$, with probability $1-n^{-c}$, for each $i$, the acceptable
edges from women $w_{i}$ are to men with public rating in the range
$[r_{m_{i}}-4\alpha,r_{m_{i}}+5\alpha]$, where $\alpha=\overline{L}/4\mu$. A
symmetric bound applies to the men.

###### Proof.

Theorem D.1 bounds the loss by $\overline{L}$ for non-bottommost agents with
probability $1-n^{-c}$ for large enough $n$. Therefore $w_{i}$ will not be
interested in matching with any man with public rating less than
$r_{m_{i}}-\overline{L}/\mu$ (for any such man would give a loss greater than
$\overline{L}$).

The situation to higher rated men needs a little more calculation. Let $m_{g}$
be such a man. Then what matters is whether $m_{g}$ incurs a loss of more than
$\overline{L}$ if matched to $w_{i}$. This happens if
$r_{w_{g}}-r_{w_{i}}>\overline{L}/\mu=4\alpha$. We now show that to obtain
$r_{w_{g}}-r_{w_{i}}\leq 4\alpha$, w.h.p. we must have
$r_{m_{g}}-r_{m_{i}}\leq 5\alpha$.

We prove this in two steps: first, we show that w.h.p., if
$r_{w_{g}}-r_{w_{i}}\leq 4\alpha$ then
$i-g<4\alpha(n-1)+\tfrac{1}{2}\alpha(n-1)$. Second, we show that w.h.p.,
$r_{m_{g}}-r_{m_{i}}\leq(4\alpha+\tfrac{1}{2}\alpha)+\tfrac{1}{2}\alpha=5\alpha=\tfrac{5}{4}L/\mu$.

The expected number of women in $W[r_{w_{g}}-4\alpha,r_{w_{g}}]$ other than
$w_{g}$ is at most $4\alpha(n-1)$; and so by a Chernoff bound this number is
at least $4\alpha(n-1)+\tfrac{1}{2}\alpha(n-1)$ with probability at most
$\exp(-\alpha(n-1)/48)$. Call this bad event ${\mathcal{B}}_{4}$. Note that by
assumption, $w_{i}\in W[r_{w_{g}}-4\alpha,r_{w_{g}}]$, and so if
${\mathcal{B}}_{4}$ does not occur $i-g<4\tfrac{1}{2}\alpha(n-1)$.

Now suppose ${\mathcal{B}}_{4}$ does not occur, and consider the set
$M[r_{m_{g}}-5\alpha,r_{m_{g}}]$. In expectation, other than $m_{g}$, it
contains $5\alpha(n-1)$ men. By a Chernoff bound, it contains at most
$4\tfrac{1}{2}\alpha(n-1)$ men other than $m_{g}$ with probability at most
$\exp(-\alpha(n-1)/40)$. Call this bad event ${\mathcal{B}}_{5}$.

If neither ${\mathcal{B}}_{4}$ nor ${\mathcal{B}}_{5}$ occur, as
$i-g<4\tfrac{1}{2}\alpha(n-1)$, $m_{i}\in M(r_{m_{g}}-5\alpha,r_{m_{g}}]$, and
therefore $r_{m_{g}}-r_{m_{i}}<5\alpha\leq\tfrac{5}{4}\overline{L}/\mu$.

A union bound over the $n$ women and $n$ men gives a failure probability of
$2n\cdot\exp(-\alpha(n-1)/48)+2n\cdot\exp(-\alpha(n-1)/40)$, plus the failure
probability from the proof of Theorem D.1, which was actually at most

$\displaystyle 2n\cdot\exp(-\alpha(n-1)/12)+2n\cdot\exp(-\alpha
n/24)+2n\exp(-\alpha^{2}\rho n/8)+2n\cdot\exp(-\alpha^{3}\rho^{2}n/2).$

Even adding the new terms, for large enough $n$ it still suffices to set
$\overline{L}=[128(c+2)\mu^{3}\ln n/(\rho^{2}n)]^{1/3}$ to achieve an overall
$n^{-c}$ failure probability. ∎

We now extend the result to the many-to-many setting.

######  Theorem F.3.

In the many-to-many bounded derivative setting with $n_{c}$ companies and
$n_{w}$ workers, for large enough $n_{c}$ and $n_{w}$, with probability
$1-n^{-k}$, for each $i$, the acceptable edges from worker $w_{i}$ are to
companies with public rating in the range
$[r_{c_{j_{i}}}-L_{w}/\mu,r_{c_{j_{i}}}+5L_{c}n_{c}/4\mu(n_{c}-1)]$, where
$c_{j_{i}}$ is the company aligned with $w_{i}$. A symmetric bound applies to
the companies.

###### Proof.

We need to adapt the previous proof to account for the fact that there are
$n_{c}$ companies and $n_{w}$ workers.

The argument demonstrating the lower limit is unchanged, except we replace
$\overline{L}$ with $L_{w}$. For the upper limit, we change the argument as
follows. Now, we replace $\overline{L}$ by $L_{c}$ .

We first observe that the number of workers in
$W[r_{w_{g}}-4\alpha,r_{w_{g}}]$ other than $w_{g}$ is at least
$4\alpha(n_{w}-1)+\tfrac{1}{2}\alpha(n_{w}-1)$ with probability at most
$\exp(-\alpha(n_{w}-1)/48)$. Call this bad event ${\mathcal{B}}_{4}$.

Second, if ${\mathcal{B}}_{4}$ does not occur, the set $M[r_{c_{g}}-5\alpha
n_{c}/(n_{c}-1),r_{c_{g}}]$ contains at most $4\tfrac{1}{2}\alpha n_{c}$
companies other than $c_{g}$ with probability at most $\exp(-\alpha
n_{c}/40)$. Call this bad event ${\mathcal{B}}_{5}$.

Suppose neither ${\mathcal{B}}_{4}$ nor ${\mathcal{B}}_{5}$ occur. Then, the
number of positions sought by the workers in $M[r_{w_{i-1}},r_{w_{g}}]$ is
$d_{w}(i-g)<4\tfrac{1}{2}d_{w}\alpha(n_{w}-1)=4\tfrac{1}{2}\alpha
d_{c}n_{c}-4\tfrac{1}{2}d_{w}\alpha$, while the number of positions available
in $C[r_{c_{g}}-5\alpha,r_{c_{g}}]$ is more than $4\tfrac{1}{2}d_{c}\alpha
n_{c}=4\tfrac{1}{2}\alpha d_{c}n_{c}$. Thus the number of available positions
is at least the number sought, and therefore $c_{i}\in C[r_{c_{g}}-5\alpha
n_{c}/(n_{c}-1),r_{c_{g}}]$.

It remains to revisit the probability bounds. The failure probability from the
proof of Theorem D.6 summed over all workers is

$\displaystyle
n_{w}\cdot\exp(-\alpha(n_{w}-1)/12)+\min\\{n_{c},n_{w}\\}\cdot\exp(-\alpha(n_{c}-1)/24)$
$\displaystyle+n_{w}\exp(-\alpha\beta(n_{c}-5/2)/8)+n_{w}\exp(-\alpha\beta\gamma(n_{c}-5/2)/16),$

where $\beta=\gamma=\alpha\rho$. There is an analogous bound for the
companies. Again, for large enough $n_{c}$ and $n_{w}$, we can use the same
values for $L_{c}$ and $L_{w}$ as before while maintaining the total failure
probability at $n^{-k}$. ∎

###  F.2 Distribution Bound on Losses (Proof of Theorem D.2)

Recall event ${\mathcal{B}}_{3}$ from the proof of Lemma 4.1 (see Appendix B),
that the women with rank at most $i+\ell_{i}$ make fewer than
$\tfrac{1}{2}\alpha\beta n$ Step 2 proposals to $m_{i}$. Claim 4.4 shows that
if ${\mathcal{B}}_{1}$ and ${\mathcal{B}}_{2}$ do not occur then
${\mathcal{B}}_{3}$ occurs with probability at most $\exp(-\alpha\beta n/8)$.

Now, consider a man $m$ and the aligned woman $w$, where $r_{w}\geq 4\alpha$.
Let $\beta=\gamma=\alpha\rho$. We will bound the probability that $m$ has a
loss of more than $L^{m}_{\alpha}\triangleq U(r_{w},1)-(r_{w}-4\alpha,1)$.

If, in addition, $r_{w}\geq\overline{\sigma}$ and
$\alpha=\overline{\sigma}/(4\cdot 2^{h})=\overline{L}/(4\mu\cdot 2^{h})$, as
$U(r,1)-U(r-4\alpha,1)\leq 4\alpha\mu=\overline{L}/2^{h}$, this implies a loss
of at most $\overline{L}/2^{h}$.

######  Lemma F.1.

Let $m$ be a man and let $w$ be the aligned woman. Suppose we run the DA
algorithm cutting at $m$ and $r_{m}-\alpha$. Then the probability that every
Step 2 proposal to $m$ gives him a loss of more than $L^{m}_{\alpha}$ is at
most $\exp(-\alpha\beta\gamma n/2)$.

###### Proof.

Let $m$ be a man in $M[r_{m},r_{m}+\delta]$. As ${\mathcal{B}}_{3}$ does not
occur, $m$ receives at least $\tfrac{1}{2}\alpha\beta n$ Step 2 proposals. As
shown in Observation 4 of the proof sketch, each proposal gives a loss of more
than $L^{m}_{\alpha}$ with probability at most $\gamma$. Thus, the probability
that every one of these proposals give $m$ a loss of more than
$L^{m}_{\alpha}$ is at most

$\displaystyle(1-\gamma)^{\alpha\beta n/2}\leq\exp(-\alpha\beta\gamma n/2).$

∎

######  Corollary 2.

Suppose we run the DA algorithm cutting at $m$ and $r_{m}-\alpha$. Let
${\mathcal{B}}_{6}^{h}$ be the event that at least
$2[1+(n-1)\delta]\cdot\exp(-\alpha\beta\gamma n/2)$ men in
$M[r_{m},r_{m}+\delta]$ suffer loss greater than $L^{m}_{\alpha}$, where
$0<\delta\leq 1$ and $\alpha=\overline{\sigma}/(4\cdot 2^{h})$. If
$r_{w}\geq\overline{\sigma}$, $\beta=\gamma=\alpha\rho$, and none of
${\mathcal{B}}_{1}$–${\mathcal{B}}_{3}$ occur, then ${\mathcal{B}}_{6}^{h}$
occurs with probability at most $n^{-(c+2)}$, where
$\tfrac{1}{3}\log\big(\frac{(c+2)\ln n}{\ln[\delta n/(3(c+2)\ln
n)]}\big{missing})\leq h\leq\tfrac{1}{3}\log[(c+2)\ln n]$.

###### Proof.

Consider a man $m$ in $M[r_{m},r_{m}+\delta]$. By Lemma F.1 it follows that
the probability that $m$ experiences a loss of more than $L^{m}_{\alpha}$ is
at most $\exp(-\alpha\beta\gamma n/2)$.

This bound depends only on $m$’s private scores for the Step $2$ proposals
made to him. Thus the outcomes for the different men in
$M[r_{m},r_{m}+\delta]$ are independent.

In expectation, at most $(1+(n-1)\delta)\cdot\exp(-\alpha\beta\gamma n/2)$ men
in $M[r_{m},r_{m}+\delta]$ suffer a loss of more than $L^{m}_{\alpha}$, and by
a Chernoff bound, at most $2(1+(n-1)\delta)\cdot\exp(-\alpha\beta\gamma n/2)$
men suffer such a loss with probability $\exp(-\delta
n\cdot\exp(-\alpha\beta\gamma n/2)/3)$.

Now $\exp(-\alpha\beta\gamma
n/2)=\exp(-\overline{L}^{3}n\rho^{2}/[128\mu^{3}2^{3h}])=\exp(-(c+2)\ln
n/2^{3h})$. Let $h=\tfrac{1}{3}\log[(c+2)\ln n]-\tfrac{1}{3}\log g$. Then
$\exp(-\alpha\beta\gamma n/2)=\exp(-g)$. In sum, at most
$2(1+(n-1)\delta)/\exp(g)$ men in $M[r_{m},r_{m}+\delta]$ have a loss of more
than $L^{m}_{\alpha}$ with probability at least $1-\exp(-\delta
n\cdot\exp(-g)/3)$. So the failure probability is at most $n^{-(c+2)}$ if
$g\leq\ln(\delta n/[3(c+2)\ln n])$. ∎

###### Proof.

(Of Theorem D.2) We apply Corollary 2 with $\delta=1$. Over all the men and
women whose aligned partners have public score at least $\overline{\sigma}$,
this yields that at most $2n\cdot\exp(-\alpha\beta\gamma
n/2)=2n\cdot\exp(-(c+2)\ln n/2^{3h})$ men suffer a loss of more than
$\overline{L}/2^{h}$, and likewise for the women, with failure probability at
most $2n^{-(c+1)}\log\log n$, for integer $h$ in the range stated in the
lemma.

Applying the prior analysis, if none of
${\mathcal{B}}_{1}$–${\mathcal{B}}_{3}$ occur, then the outcome is a stable
matching with the bounds on the losses as stated in the previous paragraph.
For large enough $n$, the failure probability will be at most $n^{-c}$. ∎

##  Appendix G Lower Bounds

###  G.1 A Lower Bound in the Linear Model

The following theorem shows that the upper bound we obtained is the best
possible up to a constant factor. The intuition is as follows: the expected
number of acceptable edges per agent is $\Theta(\ln n)$, excluding the agents
with public ratings of less than $L$. So long as the constant is small enough,
the variance in the number of these edges over all the agents will be
sufficient to ensure a good probability that at least one agent will have no
incident acceptable edge.

For the lower bound we set $\lambda=\tfrac{1}{2}$. We begin by identifying and
bounding the probability of some bad events, denoted by ${\mathcal{B}}_{4}$
and ${\mathcal{B}}_{5}$. We then perform an analysis for the case that
${\mathcal{B}}_{4}$ and ${\mathcal{B}}_{5}$ do not occur.

To do this, we need some additional notation. In the following lemmas, we let
$(m,w)$ and $(m^{\prime},w^{\prime})$ be two pairs of men and women with equal
public ranks, and suppose their public ratings are
$r_{m},r_{w},r_{m^{\prime}},r_{w^{\prime}}$, respectively. We let
$x=r_{m}-r_{m^{\prime}}$ and $y=r_{w}-r_{w^{\prime}}$. Note that
$\text{sign}(x)=\text{sign}(y)$.

Event ${\mathcal{B}}_{4}$. Let ${\mathcal{E}}_{4}$ be the following event: If
$|x|\leq 4L$, then the number of men with public ratings in the range
$[r_{m},r_{m^{\prime}}]$ lies in the range
$(2+x\cdot(n-2)-L(n-2),2+x\cdot(n-2)+L(n-2))$, and similarly for the women.
${\mathcal{B}}_{4}$ is the (bad) event that ${\mathcal{E}}_{4}$ does not
occur.

######  Lemma G.1.

${\mathcal{B}}_{4}$ occurs with probability at most $2n^{2}\cdot
n^{-L(n-2)/12\ln n}$.

###### Proof.

Not counting $m$ and $m^{\prime}$, the expected number of men with public
ratings in the range $[r_{m},r_{m^{\prime}}]$ is $|x|(n-2)$. By a Chernoff
bound, this number lies outside the range $(|x|(n-2)-L(n-2),|x|(n-2)+L(n-2))$
with probability at most $e^{-L^{2}(n-2)/2|x|}+e^{-L^{2}(n-2)/3|x|}\leq
2e^{-L(n-2)/12}$, as $|x|\leq 4L$ by assumption.

The same bound applies to the women. Now we apply a union bound to all
$\tfrac{1}{2}n(n-1)$ pairs $(m,w)$ and $(m^{\prime},w^{\prime})$ to obtain the
result. ∎

Event ${\mathcal{B}}_{5}$. This is the event that for some pairs $(m,w)$ and
$(m^{\prime},w^{\prime})$, either (i)
$|y|=\big{|}r_{w^{\prime}}-r_{w}\big{|}>4L$ and the number of women in the
range $[r_{w},r_{w^{\prime}}]$ is at most $2+3L(n-2)$, or (ii)
$|x|=\big{|}r_{m^{\prime}}-r_{m}\big{|}>4L$ and the number of men in the range
$[r_{m},r_{m^{\prime}}]$ is at most $2+3L(n-2)$.

######  Lemma G.2.

${\mathcal{B}}_{5}$ occurs with probability at most $n^{2}\cdot
n^{-L(n-2)/8\ln n}$.

###### Proof.

We obtain a bound in case (i). Excluding $w$ and $w^{\prime}$, the expected
number of women in the range $[r_{w},r_{w^{\prime}}]$ is at least $|y|(n-2)$.
By a Chernoff bound it is at most $y(n-2)-(|y|-3L)\cdot(n-2)$ with probability
at most
$\exp(-(|y|-3L)^{2}(n-2)/2|y|)\leq\exp(-(|y|/4)^{2}(n-2)/2|y|)\leq\exp(-L(n-2)/8)$.

The same bound holds in case (ii). Now we apply a union bound to all
$\tfrac{1}{2}n(n-1)$ pairs $(m,w)$ and $(m^{\prime},w^{\prime})$ to obtain the
result. ∎

######  Theorem G.1.

If $n\geq 32,000$ and $L=\tfrac{1}{8}(\ln n/n)^{1/3}$ then with probability at
least $\tfrac{1}{4}n^{-1/8}$ there is no perfect matching, let alone stable
matching, in which every edge is $(L,\tfrac{3}{2}L)$-acceptable.

###### Proof.

Suppose that ${\mathcal{B}}_{4}$ and ${\mathcal{B}}_{5}$ do not occur. Then,
we will show that the expected number of women with no acceptable incident
edge is greater than or equal to $\tfrac{1}{2}n^{7/8}$. As there are $n$
women, it immediately follows that with probability at least
$\tfrac{1}{2}n^{-1/8}$ there is no matching in which every edge is acceptable.
The result now follows if the probability of
${\mathcal{B}}_{4}\cup{\mathcal{B}}_{5}$ is at most $\tfrac{1}{4}n^{-1/8}$,
i.e. that $2n^{2}\cdot n^{-L(n-2)/12\ln n}+n^{2}\cdot n^{-L(n-2)/8\ln
n}\leq\tfrac{1}{4}n^{-1/8}$; $n\geq 32,000$ suffices.

Lemma G.7 below shows that in expectation there are at least $n^{7/8}$ women
(and men) such that every possible proposal to one of these women would cause
at least one of the two parties a loss greater than $L$. Recall that every
edge to a woman with a public rating less than $\tfrac{3}{2}L$ is woman-
acceptable. Let $w^{\prime}$ be the topmost such woman (i.e. the one with the
highest public rating). Let $w$ be the woman with the lowest public rating
equal to or greater than $r_{w^{\prime}}+2L$, and let $m$ be $w$’s aligned
partner. Then the edge $(m,w^{\prime})$ gives $m$ a loss greater than $L$, and
thus every edge $(m,w^{\prime\prime})$ that is man-acceptable to $m$ will be
acceptable to $w^{\prime\prime}$ only if it gives $w^{\prime\prime}$ a loss of
at most $L$. So for men with public rating at least $r_{m}$, an edge is
acceptable only if it gives both partners a loss of at most $L$. We show that
there are at most $5Ln$ such men if ${\mathcal{B}}_{4}$ does not occur. For if
this event does not occur, then the number of women in the range
$[r_{w_{n}},r_{w}]$, and hence the number of men in the range
$[r_{m_{n}},r_{m}]$, is at most $2+\tfrac{9}{2}L(n-2)\leq 5Ln$, if
$2\leq\tfrac{1}{16}(n-2)\ln^{1/3}n/n^{1/3}$; $n\geq 256$ suffices. The same
bound applies to the women.

Thus, there are at least $n^{7/8}-5Ln$ women who do not have acceptable
matches. So long as $\tfrac{1}{2}n^{7/8}\geq
5Ln=\tfrac{5}{16}n^{2/3}\ln^{1/3}n$, this implies that the number of women
with no acceptable match is at least $\tfrac{1}{2}n^{7/8}$. This condition
holds when $n\geq 1$. ∎

######  Lemma G.3.

Suppose that ${\mathcal{B}}_{4}$ and ${\mathcal{B}}_{5}$ do not occur. Further
suppose that either $|x|\leq 2L$ or $|y|\leq 2L$. Then, $\big{|}x-y|<2L$.

###### Proof.

We consider the case that $x\leq 2L$. The proof for the other case is
symmetric.

Let $h$ be the the number of men in the range $[r_{m},r_{m^{\prime}}]$; $h$ is
also the number of women in the range $[r_{w},r_{w^{\prime}}]$. By Lemma G.1,
$h\in 2+\big{(}|x|(n-2)-L(n-2),|x|(n-2)+L(n-2)\big{)}$ and if $|y|\leq 4L$,
$h\in 2+\big{(}|y|(n-2)-L(n-2),|y|(n-2)+L(n-2)\big{)}$. Consequently
$|x-y|<2L$ if $|y|\leq 4L$.

If $|y|>4L$, as ${\mathcal{B}}_{5}$ does not occur, the number of women in the
range $[r_{w},r_{w^{\prime}}]$ is more than $2+3L(n-2)$. But as
${\mathcal{B}}_{4}$ does not occur, the number of men is at most $2+3L(n-2)$.
These numbers are supposed to be equal, and therefore $|y|>4L$ cannot happen.
∎

######  Lemma G.4.

Suppose that ${\mathcal{B}}_{4}$ and ${\mathcal{B}}_{5}$ do not occur. Further
suppose that $y=r_{w}-r_{w^{\prime}}\geq 0$. Then, the probability that edge
$(m,w^{\prime})$ causes a loss of at most $L$ to both $m$ and $w^{\prime}$ is
at most $(2L-y)\cdot(4L+y)\leq 8L^{2}$. A symmetric bound applies if
$\overline{x}=r_{m^{\prime}}-r_{m}\geq 0$.

###### Proof.

We show the proof for the first bound. The argument for the second bound is
identical. $m$ has a loss of at least $y$ on edge $(m,w^{\prime})$. Therefore,
for $(m,w^{\prime})$ to be acceptable to $m$, we need $y\leq 2L$. The
probability that $(m,w^{\prime})$ is acceptable is $(2L-y)\cdot(2L+x)$, and by
Lemma G.3, this is at most $(2L-y)\cdot(2L+y+2L)$. ∎

######  Lemma G.5.

Consider an edge $(m,w^{\prime})$. If $x<-2L$ or $y>2L$ then $(m,w^{\prime})$
is not acceptable.

###### Proof.

If $y>2L$ then $m$ has a loss of more than $2L$, and if $x<-2L$ then
$w^{\prime}$ has a loss of more than $2L$. ∎

######  Definition 16.

Let $(m,w^{\prime})$ be an edge. If $x\geq-2L$ and $y\leq 2L$ we say
$(m,w^{\prime})$ passes the public rating test, and otherwise it fails the
test.

######  Lemma G.6.

Suppose that ${\mathcal{B}}_{4}$ and ${\mathcal{B}}_{5}$ do not occur. Then
apart from at most $3+6L(n-2)$ edges $(m,w^{\prime})$ all other edges incident
on $m$ fail the public rating test.

###### Proof.

Let $w^{\prime}$ be the lowest rated woman in $W[r_{w}-2L,r_{w}]$. By Lemma
G.1, there are at most $2+3L(n-2)$ women in $W[r_{w^{\prime}},r_{w}]\subseteq
W[r_{w}-2L,r_{w}]$. By Lemma G.5, for any woman $w^{\prime\prime}$ with a
lower rating than $w^{\prime}$, $(m,w^{\prime\prime})$ will fail the public
rating test (as for $w^{\prime\prime}$, $y>2L$).

Now let $m^{\prime}$ be the highest rated man in $M[r_{m},r_{m}+2L]$. By Lemma
G.1, for any woman $w^{\prime\prime}$ with a higher rating than $w^{\prime}$,
$(m,w^{\prime\prime})$ will fail the public rating test (as for
$w^{\prime\prime}$, $x<-2L$). By Lemma G.1, there are at most $2+3L(n-2)$ men
in $M[r_{m},r_{m}+2L]$, and therefore there are at most $2+3L(n-2)$ women in
$W[r_{w},r_{w^{\prime}}]$.

$w$ belongs to both these sets of women. So there are at most $3+6L(n-2)$
women who pass the public rating test. ∎

######  Lemma G.7.

Suppose that ${\mathcal{B}}_{4}$ and ${\mathcal{B}}_{5}$ do not occur and
$n\geq 100$. If $L\leq\tfrac{1}{8}(\ln n/n)^{1/3}$, and there are equal
numbers of men and women, then the expected number of unmatched men (and
women) is at least $n^{7/8}$.

###### Proof.

Consider an arbitrary man $m$. By Lemma G.4, each edge which passes the public
rating test is acceptable with probability at most $8L^{2}$. By Lemma G.6,
there are at most $3+6L(n-2)$ such edges incident on $m$. Therefore the
probability that all $n$ edges incident on $m$ cause one or both parties a
loss of more than $L$ is at least

$\displaystyle\big{(}1-8L^{2}\big{)}^{3+6L(n-2)}=e^{(3+(6L(n-2))\ln(1-8L^{2})}\geq
n^{-1/8},$

as we argue next.

For this to hold, it suffices that

$\displaystyle-8\cdot\frac{3+6L(n-2)}{\ln
n}\Big{(}-8L^{2}-\frac{1}{2}(8L^{2})^{2}-\frac{1}{3}(8L^{2})^{3}-\ldots\Big{)}\leq
1$ or that $\displaystyle 8\cdot\frac{7Ln}{\ln
n}\cdot\frac{8L^{2}}{1-8L^{2}}\leq 1\hskip 36.135pt\text{(if $3\leq Ln$)}$ or
that $\displaystyle
56\cdot\frac{n^{2/3}}{8\ln^{2/3}n}\cdot\frac{\ln^{2/3}n}{8n^{2/3}-\ln^{2/3}n}\leq
1$ or that $\displaystyle\frac{7}{8}\cdot\frac{1}{1-\ln^{2/3}n/8n^{2/3}}\leq
1$

which holds if $\ln^{2/3}n/8n^{2/3}\leq 1/8$, which holds for $n\geq 1$. Our
other condition, $3\leq Ln$, or $3\leq\tfrac{1}{8}n^{2/3}\ln^{1/3}n$, holds if
$n\geq 100$.

Thus the expected number of women having all incident edges causing a loss of
more than $L$ to both parties is at least $n^{7/8}$. ∎

###  G.2 Lower Bound on Performance for the General Utility Model

Now we show that without the bounds on the derivatives, no sub-constant loss
is achievable in general.

######  Definition 17 (Sub-constant function).

A function $f(x):{\mathbb{R}}\rightarrow{\mathbb{R}}^{+}$ is sub-constant if
for every choice of constant $c>0$, there exists an $\overline{x}$ such that
for all $x\geq\overline{x}$, $f(x)\leq c$.

We first examine what happens if the derivatives w.r.t. private scores are not
bounded, but the derivatives w.r.t. public ratings are bounded; this implies
there is no lower bound on the ratio of the derivatives of the utility
functions w.r.t. public ratings and private scores (recall Definition 8).

######  Lemma G.8.

Let $f:N\rightarrow{\mathbb{R}}^{+}$ be a continuous, strictly decreasing sub-
constant function, and let $\sigma,\delta\in(0,1)$ be constants. Suppose the
public ratings and private scores of the $n$ men and $n$ women are drawn
uniformly and independently from $[0,1]$. Then there exist continuous and
strictly increasing utility functions $U(.,.)$ and $V(.,.)$ having derivatives
w.r.t. their first variables that are bounded by a constant, but for (at
least) one of which the derivatives w.r.t. their second variables are not
bounded by any constant, having the following property: for some
$\overline{n}>0$, for all $n\geq\overline{n}$, with probability at least
$1-\delta$, in every perfect matching, some rank $i$ man $m_{i}$ or woman
$w_{i}$ with public rating at least $\sigma$ receives utility less than
$U(r_{w_{i}},1)-f(n)$ or $V(r_{m_{i}},1)-f(n)$, respectively.

###### Proof.

We will give an example where, with probability at least $1-\delta$, in every