# Regret, stability, and fairness
in matching markets with bandit learners

Sarah H. Cen and Devavrat Shah

(Department of Electrical Engineering and Computer Science
Massachusetts Institute of Technology)

###### Abstract

We consider the two-sided matching market with bandit learners. In the
standard matching problem, users and providers are matched to ensure incentive
compatibility via the notion of _stability_. However, contrary to the core
assumption of the matching problem, users and providers do not know their true
preferences a priori and must learn them. To address this assumption, recent
works propose to blend the matching and multi-armed bandit problems. They
establish that it is possible to assign matchings that are stable (i.e.,
incentive-compatible) at every time step while also allowing agents to learn
enough so that the system converges to matchings that are stable under the
agents’ true preferences. However, while some agents may incur low regret
under these matchings, others can incur high regret—specifically, $\Omega(T)$
optimal regret, where $T$ is the time horizon. In this work, we incorporate
_costs_ and _transfers_ in the two-sided matching market with bandit learners
in order to faithfully model competition between agents. We prove that, under
our framework, it is possible to simultaneously guarantee four desiderata: (1)
incentive compatibility, i.e., stability, (2) low regret, i.e., $O(\log(T))$
optimal regret, (3) fairness in the distribution of regret among agents, and
(4) high social welfare.

##  1 Introduction

We consider the two-sided, competitive matching market (e.g. Uber or
Thumbtack), in which there are users (e.g. riders or consumers) on one side of
the market and providers (e.g., drivers or services) on the other. Each user
has a set of preferences over the providers, and each provider has a set of
preferences over the users. The _two-sided matching problem_ studies how users
and providers should be paired under the agents’ individual preferences, and
the resulting assignment is known as a _matching_. Due to matching
constraints—in particular, that users and providers are matched one-to-one—a
user may not be matched to its most preferred provider, or vice versa, which
leads to competition between agents.

Such considerations led Gale and Shapley (1962) to define a notion of
incentive compatibility in the context of college admissions and marriages
known as _stability_. In the standard centralized two-sided matching problem,
as posed by Gale and Shapley (1962), each user knows its true preferences over
providers a priori, and vice versa. These preferences are reported to a
central platform, which assigns a matching. The resulting matching $M$ is
stable if there is no user-provider pair such that both the user and provider
prefer to be matched to one another rather than to their matches under $M$. If
$M$ is not stable, then there exists a user and a provider who prefer to
defect from $M$ and pair off together. While stability is one desideratum of
matching under competition, it does not necessarily reflect a matching’s
_global_ performance. In fact, as studied by Axtell and Kimbrough (2008),
local incentive compatibility (i.e., stability) can come at the expense of
global performance objectives, such as _social welfare_ or _fairness_.

Contrary to the core assumption of the standard two-sided matching problem,
users and providers rarely know their own true preferences prior to
interacting with one another. Rather, agents learn their true preferences
through experiences (i.e., by being matched). For example, consider the dating
setting, in which individuals learn their romantic preferences from dates with
potential partners. Alternatively, consider the internship market in which
workers present employers with qualifications, and employers present workers
with career options. In this setting, internships are matches between workers
and employers that allow workers to learn their preferences over careers and
employers to learn their preferences over worker qualifications.

In such settings, agents on the same side of the market _compete_ for a
limited number of pairings, as studied in the matching problem. However, since
agents are uncertain about their preferences, they balance a desire to receive
good experiences in the short term with a desire to better learn their
preferences so as to maximize long-term happiness in what is known as the
_exploration-exploitation trade-off_. The task of learning one’s preferences
over multiple options from repeated interactions is at the core of the multi-
armed bandit (MAB) problem or, more generally, sequential decision-making
frameworks, such as the Markov decision process and reinforcement learning,
cf. (Cesa-Bianchi and Lugosi, 2006; Bubeck and Cesa-Bianchi, 2012).

In this way, blending the matching and MAB problems provides a framework for
modeling the sequential decision-making of learning agents that compete for
resources under uncertainty. This is precisely what Liu et al. (2020a) do in a
recent work that considers the _centralized two-sided matching market with
bandit learners_. In this setting, at each of $T$ time steps, agents are
matched based on their upper confidence bounds—an index from the MAB
problem—using a classical matching algorithm by Gale and Shapley (1962). As an
important result, Liu et al. (2020a) establish that, even though agents do not
know their true preferences a priori, it is possible to assign matchings that
are incentive-compatible at every time step while also allowing agents to
learn enough so that they system converges to matchings that are stable under
the agents’ true preferences.

However, Liu et al. (2020a) also show that, even though the matchings at every
time step are stable, they can lead some agents to incur high regret,
specifically $\Omega(T)$ optimal regret. For instance, it is possible for a
user $u$ to be repeatedly matched with a provider for which $u$ has a very low
preference even when there exists a true stable matching that pairs $u$ with a
provider that $u$ prefers more. This result would imply that low regret cannot
be guaranteed without sacrificing incentive compatibility, yet this finding
does not reflect the outcomes of various representative settings (Ashlagi et
al., 2017). Further, we note that Liu et al. (2020a) do not examine global
performance objectives, such as fairness or social welfare.

In this work, we add a layer of complexity that is absent in the work by Liu
et al. (2020a) and, in doing so, show that it is possible to _simultaneously
guarantee stability, low regret, fairness, and high social welfare_. Our
adjustment to the problem formulation is the addition of _costs_ and
_transfers_. Intuitively, competition between agents for a limited number of
available matches can give rise to prices and payments, which results in
transfers between agents. Additionally, due to competition, an agent $a$ may
be repeatedly refused a match with its preferred agent $a^{\prime}$ and
accumulate fatigue, which manifests as a cost that $a$ associates with
$a^{\prime}$. It is therefore natural for costs and transfers to arise when
agents compete for resources.

Our contributions are summarized as follows:

  * •

We provide a model for the centralized matching problem with bandit learners
that allows transfers between agents and allows agents to incur costs (see
Section 3).

  * •

We show that, without costs or transfers, it is not possible to simultaneously
guarantee incentive compatibility (i.e., stability) and low regret, the fair
distribution of regret, or high social welfare (see Proposition 3 and Example
1).

  * •

We study various cost and transfer rules and prove that, with costs and
transfers, it is possible for the platform to simultaneously guarantee
incentive compatibility, low regret, the fair distribution of regret, and, in
some cases, high social welfare (see Theorems 9 and 11). These results provide
guidance on designing matching markets to balance local and global desiderata.

Intuitively, we show that there is a way to match sequential decision-making
agents who must learn their preferences while competing for resources such
that the assignments are incentive-compatible and yield high social welfare at
_every_ time step while allowing agents to learn enough about their own
preferences so that _all_ agents efficiently converge to their optimal true
stable matching.

##  2 Related work

Two-sided matching. In the two-sided matching (stable marriage) problem, there
are two distinct populations that wish to be matched one-to-one. Examples of
two-sided matchings are numerous, ranging from how individuals find romantic
partners or workers fill job openings to how platforms match content to users
or doctors are assigned to patients. One of the challenges of this problem is
finding a stable matching: one for which no pair of agents is incentivized to
defect from the assignment and pair off together.

Gale and Shapley (1962) show that, given the preferences of all agents, there
exists at least one stable matching and provide an algorithm—known as the
Gale-Shapley (GS) or deferred acceptance algorithm—that finds a stable
matching. Since then, there has been a large body of ensuing work (Knuth and
De Bruijn, 1997; Roth, 2008). In the footsteps of Gale and Shapley (1962), one
line of work studies _centralized_ matchings, in which agents’ preferences are
reported to a central platform that assigns the matches. Another of line of
work studies decentralized (or distributed) matchings, in which there is no
coordination between agents (Roth and Vate, 1990; Echenique and Yariv, 2012).
Rather individuals on one of the market independently propose a match while
individuals on the other accept or reject.

There are many closely related problems, such as the the generalized
assignment problem (Kuhn, 1955; Ross and Soland, 1975; Pentico, 2007); housing
allocation problem (Shapley and Scarf, 1974); college admissions or hospital-
residents problem (Gale and Shapley, 1962; Roth, 1984); stable roommates
problem (Irving, 1985); and more. One related line of work is the generalized
stable allocation problem, which studies stable matchings for graphs in which
the edges have weights (Dean and Swar, 2009).

Multi-armed bandit (MAB) problem. The MAB problem is a decision-making problem
in which an agent (the bandit) sequentially chooses between $K$ options (or
arms) (Bubeck and Cesa-Bianchi, 2012; Lattimore and Szepesvári, 2020). If
chosen, the arm returns a noisy reward to the agent. At the start, the agent
does not know the arms’ expected rewards, and its goal is to maximize the
reward that it accumulates over $T$ time steps or, equivalently, to minimize
_regret_. For example, suppose that an individual would like to learn her
favorite dish or brand of headphones. Each time the individual orders a dish
or purchases headphones, she is effectively sampling that item. Even if the
individual has historically received good rewards from item $i$, she cannot be
certain that another item $j$ does not return higher rewards on average unless
she occasionally forgoes $i$ in favor of sampling $j$. In this way, a bandit
learner must balance its short-term desire to sample arms with high known
rewards with its need to learn the expected (possibly higher) reward of other
arms in order to maximize its long-term happiness. This balance is known as
the exploitation-exploration trade-off (Wilson et al., 2014; Schnabel et al.,
2018; Wilson et al., 2021), which is focal point of reinforcement learning
(RL) (Sutton and Barto, 2018; Wiering and Van Otterlo, 2012).

The primary objective of the MAB algorithm is to design a decision-making
algorithm that achieves low regret. In a seminal work, Lai and Robbins (1985)
showed that, for a large class of sampling policies, regret must grow
$\Omega(\log(T))$. This result catalyzed a research area devoted to creating
algorithms that guarantee $O(\log(T))$ regret (Thompson, 1933; Bubeck and
Cesa-Bianchi, 2012; Lattimore and Szepesvári, 2020). One of the most popular
algorithms is known as the Upper Confidence Bound (UCB) strategy (Auer et al.,
2002), which is a pure (or deterministic) decision-making strategy that
guarantees $O(\log(T))$ regret. Under the UCB strategy, the agent, at each
time step, selects the option with the highest UCB at that time.

Matching markets with bandit learners. Sequential decision-making under
uncertainty and competition is a setting of long-standing interest. Recently,
such settings have been modeled as a combined two-sided matching and MAB
problem (Das and Kamenica, 2005; Liu et al., 2020a). Das and Kamenica (2005)
introduce the combined problem, but they do so under the strict assumption
that all agents on one side of the market have identical preferences. We
therefore focus on the setting presented by Liu et al. (2020a).

In the _centralized matching market with bandit learners_ (Liu et al., 2020a),
there are two distinct sets of agents—users and providers—on opposite sides of
the market. As in the matching problem, users compete for matches with
providers, and vice versa. As in the MAB problem, agents do not know their
true preferences a priori and instead learn them by observing the rewards they
receive from previous matches. At each time step $t$, each user computes its
UCBs for all providers, and vice versa. These UCB preferences are reported to
a central platform, which then runs the GS algorithm to obtain a stable
matching at each time step.

There are related works on how competition for users affects the provider’s
learning (Mansour et al., 2018; Aridor et al., 2020), bandits with collisions
(Liu and Zhao, 2010; Kalathil et al., 2014; Bubeck et al., 2020), and
coordinated resource allocation (Avner and Mannor, 2019). Although related,
these settings are one-sided (i.e., only one side of the market has
preferences), and they do not consider costs or transfers in matching, as done
in this work. There have also been several works on variations of the
centralized two-sided matching problem with bandit learners, including works
that study decentralized matchings, matching robustness, and the addition of
information exchange (Chawla et al., 2020; Boursier and Perchet, 2020;
Sankararaman et al., 2020; Vial et al., 2020; Liu et al., 2020b).

Costs and transfers. Recall that, in the MAB problem, an agent’s regret is low
if it is $O(\log(T))$. Liu et al. (2020a) show that, in the centralized two-
sided matching problem with bandit learners, it is possible to guarantee
stability and $O(\log(T))$ pessimal regret $\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to6.13614pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.13614pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.29529pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to3.06805pt{}}}$\hss}}}R$. However, under their
framework, they show that it is not possible to guarantee that the optimal
regret $\bar{R}\geq\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R$ grows $O(\log(T))$ while assigning stable matches.
As such, there are settings in which the optimal regret for at least one agent
is $\Omega(T)$. Intuitively, this occurs when competition results in
collisions that benefit one agent at the expense of another.

However, this impossibility result does not reflect findings that empirically
observed cores are small (Ashlagi et al., 2017), indicating that people tend
to arrive at a set of preferences that is optimal or near-optimal for them
under stability. We propose this dissonance can be resolved by adding a layer
of complexity not present in the work by Liu et al. (2020a): costs and
transfers. Intuitively, due to the competition in matching markets, it is
natural for prices and compensation to arise (which manifest as transfers
between agents) or for agents to develop fatigue if, for instance, repeatedly
refused by another agent (which manifests as costs). It is therefore natural
for costs and transfers to arise when agents compete for limited resources.

The idea to incorporate transfers into the matching problem is not new.
Several works on the standard two-sided matching problem (that do not consider
the learning component) allow transfers between agents (Shapley and Shubik,
1971; Becker, 1973). They show that transfers are important to balancing
supply and demand, which allows markets to clear (Shapley and Shubik, 1971;
Kelso Jr. and Crawford, 1982). In addition to these theoretical results, it
has also been suggested that transfers (e.g., prices) and costs (e.g., search
frictions) can explain discrepancies between predicted and observed matching
behaviors (Hitsch et al., 2010).

Stability, social welfare, and fairness. Early works on the matching problem
focus on stability, which is a local objective in that it guarantees that no
pair of agents is incentivized to defect (Gale and Shapley, 1962). Later works
consider other objectives of interest, such as social welfare (Axtell and
Kimbrough, 2008), fairness (Masarani and Gokturk, 1989; Klaus and Klijn, 2006;
Sühr et al., 2019), envy-freeness (Wu and Roth, 2018), and strategy-proofness
(Roth, 1982; Ashlagi and Gonczarowski, 2018).

Liu et al. (2020a) consider stability but no other criteria. While important,
stability is a local objective that does not necessarily reflect global
performance. For example, stability can come at the expense of social welfare
(i.e., the sum of all agents’ payoffs under a given matching) and fairness
(i.e., the balanced distribution of utility across agents) (Axtell and
Kimbrough, 2008).

In this work, we consider stability, fairness, social welfare, and regret. We
do not study envy-freeness or strategy-proofness. In contrast to the work by
Liu et al. (2020a), we show that, with costs and transfers, it is possible to
simultaneously guarantee stability, fairness, and high social welfare as well
as low regret.

##  3 Problem statement

###  3.1 Setup

Suppose there are $N$ users and $L$ providers on opposite sides of the market,
where $N\geq L$. The set of users is denoted by
$\mathcal{U}=\\{u_{1},u_{2},\ldots,u_{N}\\}$, the set of providers is denoted
by $\mathcal{P}=\\{p_{1},p_{2},\ldots,p_{L}\\}$, and
$\mathcal{U}\cap\mathcal{P}=\emptyset$. Let
$\mathcal{A}=\mathcal{U}\cup\mathcal{P}$ be the set of all agents, and let
$\mathcal{A}^{+}=\mathcal{A}\cup\emptyset$, where $\emptyset$ denotes no
agent.

Each user has a set of preferences over providers, and each provider has a set
of preferences over users. These _true_ preferences are unknown a priori and
must be learned with time. Let $\mu(a_{1},a_{2})$ denote agent $a_{1}$’s true
(unknown) preference for agent $a_{2}$, where
$\mu:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}_{\geq 0}$, and
$a_{1}$ and $a_{2}$ cannot both belong to $\mathcal{U}$ or to $\mathcal{P}$.
For simplicity, we assume that there are no ties, i.e., $a^{\prime}\neq
a^{\prime\prime}\implies\mu(a,a^{\prime})\neq\mu(a,a^{\prime\prime})$ for all
$a\in\mathcal{A}$.

In this work, we use two notational shorthands. Let
$\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ denote an
arbitrary function (e.g., preferences). We say that
$a_{1}\succ_{\psi(a_{3},\cdot)}a_{2}$ if
$\psi(a_{3},a_{1})>\psi(a_{3},a_{2})$. We denote the rank—or ordinal
preference—of agent $a^{\prime}$ under $\psi(a,\cdot)$ by
$r(a^{\prime};\psi(a,\cdot))$, where
$r:\mathcal{A}^{+}\rightarrow\mathbb{N}_{>0}$ and
$r(a^{\prime};\psi(a,\cdot))<r(a^{\prime\prime};\psi(a,\cdot))\iff\psi(a,a^{\prime})>\psi(a,a^{\prime\prime})$.
For example, if $p=\operatorname*{arg\,max}_{p\in\mathcal{P}}\psi(u,p)$, then
$r(p;\psi(u,\cdot))=1$. Accordingly, $r^{-1}(n;\psi(a,\cdot))$ is the $n$-th
highest ranked user under $\psi(a,\cdot)$.

Let $T\in\mathbb{N}_{>0}$ be the time horizon. At each time step $t\in[T]$, a
central platform matches users to providers based on information about the
agents’ preferences at time $t$. We denote this information by $\nu_{t}$ for
reasons that will become clear below. Let $\mathcal{M}(a;\nu_{t})$ denote the
agent to which $a$ is matched at time $t$, where
$\mathcal{M}:\mathcal{A}\rightarrow\mathcal{A}^{+}$, and
$\mathcal{M}(a;\nu_{t})=\emptyset$ implies that agent $a$ is unmatched at time
$t$. Without loss of generality, we assume that agents always prefer to be
matched than to be unmatched. A feasible matching is one in which each user is
matched to at most one provider, and all providers are matched to exactly one
user. Let $\mathcal{W}$ be the set of all feasible matchings between users and
providers.

Since each agent does not know its own true preferences a priori, it must
learn them from experience—specifically, through feedback that it receives
after every matching. If agent $a$ is matched to agent $a^{\prime}$ at time
$t$, then agent $a$ receives a reward
$X_{t}(a,a^{\prime})\stackrel{{\scriptstyle\scriptscriptstyle{\text{i.i.d.}}}}{{\sim}}\mathcal{D}(a,a^{\prime})$,
where $\mathcal{D}(a,a^{\prime})$ is a sub-Gaussian distribution with
parameter $\sigma^{2}$ centered at $\mu(a,a^{\prime})$. We adopt the
convention that $\mu(a,\emptyset)=0$ and $X_{t}(a,\emptyset)=0$.

In addition to being matched and receiving reward $X_{t}(a,a^{\prime})$,
agents may also incur a cost and/or partake in a transfer. Suppose the
information state at time step $t$ is $\nu_{t}$. Let
$\mathcal{C}(a,a^{\prime};\nu_{t})$ denote the _cost_ that agent $a$ would
incur if matched to $a^{\prime}$, where
$\mathcal{C}:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$.
Similarly, let $\mathcal{T}(a,a^{\prime};\nu_{t})$ denote the _transfer_ that
$a$ would receive from $a^{\prime}$ if matched to $a^{\prime}$, where
$\mathcal{T}:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ and
$\mathcal{T}(a,a^{\prime};\nu_{t})=-\mathcal{T}(a^{\prime},a;\nu_{t})$.
$\mathcal{C}$ and $\mathcal{T}$ are determined by the platform. We adopt the
convention that $\mathcal{C}(a,\emptyset)=\mathcal{T}(a,\emptyset)=0$ for all
$a\in\mathcal{A}$.

As such, if agent $a$ is matched to $a^{\prime}$ based on information
$\nu_{t}$, the observed payoff for agent $a$ is:

$\displaystyle
U_{t}(a,a^{\prime};\nu_{t})=X_{t}(a,a^{\prime})-\mathcal{C}(a,a^{\prime};\nu_{t})+\mathcal{T}(a,a^{\prime};\nu_{t}).$

Each agent $a$ observes its own match, reward, cost, and transfer. Agents
cannot observe other agents’ private information, including other agents’
preferences, matches, rewards, costs, or transfers. Other than the matchings,
costs, and transfers that it assigns, the platform only observes the
information $\nu_{t}$ that it is given at time $t$. The platform cannot
observe the agents’ other private information.

Bandit learners. We refer to the agents as _bandit learners_ because their
task—to learn one’s preferences across options by sequentially sampling each
option—resembles the multiarmed bandit (MAB) problem.

Let all $a\in\mathcal{A}$ begin with $T_{0}(a,a^{\prime})>0$ noisy samples
$\\{X^{1}(a,a^{\prime}),\ldots,X^{T_{0}(a,a^{\prime})}(a,a^{\prime})\\}$ for
all $a^{\prime}\in\mathcal{P}$ when $a\in\mathcal{U}$ and for all
$a^{\prime}\in\mathcal{U}$ when $a\in\mathcal{P}$, where
$X^{\tau}(a,a^{\prime})\stackrel{{\scriptstyle\scriptscriptstyle{\text{i.i.d.}}}}{{\sim}}\mathcal{D}(a,a^{\prime})$
and $T_{0}(a,a^{\prime})=T_{0}(a^{\prime},a)$. (Note that this construction
can be removed with small modifications by devoting the first $N$ time steps
to cyclically matching users and providers, as commonly done in the MAB
setting.) Let:

$\displaystyle
T_{t}(a,a^{\prime})=T_{0}(a,a^{\prime})+\sum_{\tau=1}^{t}\mathbf{1}(\mathcal{M}(a;\nu_{\tau})=a^{\prime})$

be the number of times $a$ samples $a^{\prime}$ up to time $t$, and let:

$\displaystyle\hat{\mu}_{t}(a,a^{\prime})=\frac{1}{T_{t-1}(a,a^{\prime})}\left(\sum_{\tau=1}^{t-1}\mathbf{1}(\mathcal{M}(a;\nu_{\tau})=a^{\prime})X_{\tau}(a,a^{\prime})+\sum_{\tau=1}^{T_{0}(a,a^{\prime})}X^{\tau}(a,a^{\prime})\right)$

be the empirical mean of these samples at time step $t\in[T]\cup{0}$. Under
the $\sigma^{2}$-sub-Gaussian assumption above, an agent $a$’s $\alpha$-upper
confidence bound (UCB) for agent $a^{\prime}$ is:

$\displaystyle\nu_{t}(a,a^{\prime})=\hat{\mu}_{t}(a,a^{\prime})+\sqrt{\frac{2\sigma^{2}\alpha\log(t)}{T_{t-1}(a,a^{\prime})}},$
(1)

where $\alpha\in\mathbb{R}\cap(2,\infty)$. We call $\nu_{t}(a,\cdot)$ the
_transient_ preferences of agent $a$. We adopt the convention that
$\nu_{t}(a,\emptyset)=0$ for all $a\in\mathcal{A}$.

Recall that $\nu_{t}$ is the information state that the centralized platform
uses to determine the matching, cost rule, and transfer rule at time $t$. To
see why, note that in the absence of competition between agents and if
$\mathcal{C}=\mathcal{T}=0$, the setup becomes the classical MAB problem. As
such, a bandit learner $a$’s preference for being matched to (i.e., sampling)
arm $a^{\prime}$ at time step $t$ is precisely its UCB
$\nu_{t}(a,a^{\prime})$.

Matching process. In summary, we study the centralized two-sided matching
problem with bandit learners under costs and transfers. When we say that the
platform has decided on $(\mathcal{M},\mathcal{C},\mathcal{T})$, we mean that
it has an algorithm $\mathcal{M}$ for assigning matches, an algorithm
$\mathcal{C}$ for assigning costs, and an algorithm $\mathcal{T}$ for
assigning transfers based on any information state $\nu_{t}$ that arises.

The matching process proceeds as follows:

  1. At $t=0$, the platform decides on the matching mechanism $\mathcal{M}$, cost rule $\mathcal{C}$, and transfer rule $\mathcal{T}$. These rules are made known to all the agents.

  2. For $t\in[T]$:

    1. (a)

Update. Every agent $a$ updates its estimate $\hat{\mu}_{t}(a,\cdot)$.

    2. (b)

Report. Every agent $a$ reports its transient preferences $\nu_{t}(a,\cdot)$
to the central platform.

    3. (c)

Match and observe. Based on the transient preferences $\nu_{t}$, the platform
matches users and providers. Each agent $a$ observes its own match
$\mathcal{M}(a;\nu_{t})$ and stochastic reward
$X_{t}(a,\mathcal{M}(a;\nu_{t}))$.

    4. (d)

Pay and transfer. In exchange for its match, each agent $a$ incurs the cost
$\mathcal{C}(a,\mathcal{M}(a;\nu_{t});\nu_{t})$ and receives the transfer
$\mathcal{T}(a,\mathcal{M}(a;\nu_{t});\nu_{t})$ from its match
$\mathcal{M}(a;\nu_{t})$.

As mentioned above, the platform can only observe the agents’ transient
preferences as well as the matches, costs, and transfers that it assigns to
the agents. An agent can only observe its own information, including its
preferences, match, reward, cost, and transfer.

###  3.2 Desiderata

The platform’s role is to design the matching mechanism $\mathcal{M}$, cost
rule $\mathcal{C}$, and transfer rule $\mathcal{T}$. In this work, there are
four desiderata of interest: incentive-compatibility, regret, fairness, and
social welfare.

In order to formalize these criteria, let
$V:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ denote a payoff
function such that $V(a,a^{\prime})$ is the payoff agent $a$ receives if
matched to agent $a^{\prime}$ according to $V$. Let
$\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ denote an
arbitrary preference function. Overloading the payoff notation, we define the
payoff under preferences $\psi$ as:

$\displaystyle V(a,a^{\prime};\psi)$
$\displaystyle=\psi(a,a^{\prime})-\mathcal{C}(a,a^{\prime};\psi)+\mathcal{T}(a,a^{\prime};\psi),$

for all $a\in\mathcal{A}$ and $a^{\prime}\in\mathcal{A}^{+}$. In words, the
payoff $V(a,a^{\prime};\psi)$ that $a$ receives if matched to $a^{\prime}$
under preferences $\psi$ is the utility that $a$ receives when matched to
$a^{\prime}$ (i.e., $a$’s preference for $a^{\prime}$) minus the cost $a$
incurs for this match plus the transfer it receives from this match.

In designing $(\mathcal{M},\mathcal{C},\mathcal{T})$, we consider four
desiderata of interest, as follows.

(1) Incentive compatibility. Local incentive compatibility is captured through
the notion of stability. Recall that a _stable_ matching $M\in\mathcal{W}$ is
a matching under which no user-provider pair is incentivized to defect and
separately pair off together. Formally, a matching $M\in\mathcal{W}$ is _not_
stable under payoffs $V$ if there exist $a,a^{\prime}\in\mathcal{A}$ such that
$V(a,M(a))<V(a,a^{\prime})$ and
$V(a^{\prime},M(a^{\prime}))<V(a^{\prime},a)$111In some works, this definition
of stability is known as “weak stability” (Irving, 1994; Manlove, 2002). In
this work, when we use “stability”, we refer to “weak stability”.. In other
words, a matching is not stable when there exists a user and a provider whose
payoffs when pairing together are higher than when participating in the
matching. Let $S(V)\subset\mathcal{W}$ be the set of stable matchings under
payoffs $V$.

######  Definition 1.

The system is _incentive-compatible_ if and only if
$\mathcal{M}(\cdot;\nu_{t})\in S(V(\cdot,\cdot;\nu_{t}))$ for all $t\in[T]$.

It is well known that, for any payoff function $V$, there exists at least one
stable matching but that this stable matching is not necessarily unique, i.e.,
$|S(V)|\geq 1$ for any payoff function $V$ (Gale and Shapley, 1962). As such,
it is always possible for the platform to guarantee incentive compatibility.

(2) Low regret. Regret is a performance measure that quantifies the long-term
loss incurred by an agent as it learns. Let the _optimal_ and _pessimal_
matchings for agent $a$ at time $t$ be defined as:

$\displaystyle\mkern 4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{a}_{t}$ $\displaystyle\in\arg\max_{M\in
S(V(\cdot,\cdot;\mu))}\mathbb{E}_{X_{t}\sim\mathcal{D}}\left[U_{t}(a,M(a);\nu_{t})\right],$
$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.04333pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M_{t}^{a}$ $\displaystyle\in\arg\min_{M\in
S(V(\cdot,\cdot;\mu))}\mathbb{E}_{X_{t}\sim\mathcal{D}}\left[U_{t}(a,M(a);\nu_{t})\right],$

respectively. $\mkern 4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{a}_{t}$ and $\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.04333pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M_{t}^{a}$ are matchings that are stable under the true
payoffs $V(\cdot,\cdot;\mu)$. Recall that a stable matching is not necessarily
unique (i.e., $|S(V(\cdot,\cdot;\mu))|\geq 1$). $\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern 4.5mu^{a}_{t}$ and
$\mathchoice{\hbox to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.04333pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.31667pt{}}}$\hss}}}M_{t}^{a}$, respectively,
denote stable matchings under $V(\cdot,\cdot;\mu)$ with the highest and lowest
expected payoffs for agent $a$ at time $t$.

Accordingly, let the optimal regret for agent $a$ under matching mechanism
$\mathcal{M}$ be:

$\displaystyle\bar{R}(a;\mathcal{M})$
$\displaystyle=\mathbb{E}_{X_{t}\sim\mathcal{D}}\left[\sum_{t=1}^{T}\left(U_{t}(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{a}_{t}(a);\nu_{t})-U_{t}(a,\mathcal{M}(a;\nu_{t});\nu_{t})\right)\right],$

and the pessimal regret for agent $a$ under $\mathcal{M}$ be:

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})$
$\displaystyle=\mathbb{E}_{X_{t}\sim\mathcal{D}}\left[\sum_{t=1}^{T}\left(U_{t}(a,\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.04333pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M^{a}_{t}(a);\nu_{t})-U_{t}(a,\mathcal{M}(a;\nu_{t});\nu_{t})\right)\right].$

Note that $\bar{R}(a)\geq\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a)$ and, if there is a unique stable matching in
$S(V(\cdot,\cdot;\mu))$, then $\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu_{t}^{a}=\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.04333pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M_{t}^{a}$ and
$\bar{R}(a;\mathcal{M})=\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})$ for all $a\in\mathcal{A}$ and
$t\in[T]$.

One of the platform’s objectives is to design
$(\mathcal{M},\mathcal{C},\mathcal{T})$ such that agents incur low regret. We
say that an agent incurs _low regret_ when both its optimal and pessimal
regret can be upper bounded by a function that grows logarithmically in $T$,
i.e., $\bar{R}(a;\mathcal{M})=O(\log(T))$.

(3) Fairness. In this work, fairness requires the balanced distribution of
regret across agents, as follows.

######  Definition 2.

$(\mathcal{M},\mathcal{C},\mathcal{T})$ is _unfair_ if there exists
$\mathcal{A}^{-}\subset\mathcal{A}$, where
$0<|\mathcal{A}^{-}|<|\mathcal{A}|$, such that
$\bar{R}(a;\mathcal{M})=O(\log(T))$ and
$\bar{R}(a^{\prime};\mathcal{M})=\omega(\log(T))$ for some
$a\in\mathcal{A}^{-}$ and $a^{\prime}\in\mathcal{A}\setminus\mathcal{A}^{-}$.
Otherwise, it is fair.

Intuitively, $(\mathcal{M},\mathcal{C},\mathcal{T})$ is unfair if some agents
incur low regret at the expense of others incurring high regret. Note that, as
above, we suppress $\mathcal{C}$ and $\mathcal{T}$ in the notation of
$\bar{R}(a;\mathcal{M})$.

(4) High social welfare. Social welfare is a global, utilitarian metric
defined as the sum of all agents’ payoffs.
$(\mathcal{M},\mathcal{C},\mathcal{T})$ yields high social welfare when the
sum of all agents’ payoffs is within factor-2 of the maximum social welfare
achievable under any (not necessarily stable) matching at every time
step222The definition of high social welfare can be modified such that the
social welfare of $(\mathcal{M},\mathcal{C},\mathcal{T})$ is $\kappa$-high at
time $t$ when it is within constant factor of the maximum social welfare
achievable under feasible matchings, i.e.,
$W_{t}(\mathcal{M})\geq\frac{1}{\kappa}\max_{M\in\mathcal{W}}\sum_{a\in\mathcal{A}}V(a,M(a);\nu_{t})$
for $\kappa\geq 1$. Since the results in this work would remain the same, with
small modifications, we use the factor-2 definition for simplicity..

######  Definition 3.

The _social welfare_ of $(\mathcal{M},\mathcal{C},\mathcal{T})$ at time step
$t$ is
$W_{t}(\mathcal{M})=\sum_{a\in\mathcal{A}}V(a,\mathcal{M}(a;\nu_{t});\nu_{t})$.
If
$W_{t}(\mathcal{M})\geq\frac{1}{2}\max_{M\in\mathcal{W}}\sum_{a\in\mathcal{A}}V(a,M(a);\nu_{t})$
for all $t\in[T]$, we say that high social welfare is guaranteed under
$(\mathcal{M},\mathcal{C},\mathcal{T})$. When $W_{t}(\mathcal{M})=0$ or
$W_{t}(\mathcal{M})<\frac{1}{2}\max_{M\in\mathcal{W}}\sum_{a\in\mathcal{A}}V(a,M(a);\nu_{t})$,
we say that the social welfare of $(\mathcal{M},\mathcal{C},\mathcal{T})$ is
low at time step $t$.

As above, $\mathcal{C}$ and $\mathcal{T}$ are suppressed in the notation of
$V$ and $W_{t}$.

##  4 Main results

In this section, we study various cost and transfer rules. We show that, under
costs and transfers, it is possible to _simultaneously guarantee incentive
compatibility, low optimal regret, fairness, and high social welfare_. Our
main results are:

  * •

Without costs or transfers, we have an impossibility result: that it is not
possible to simultaneously guarantee incentive compatibility and $O(\log(T))$
regret, fairness, or high social welfare (see Proposition 3 and Example 1).

  * •

We explore whether common cost and transfer rules can resolve this
impossibility. Specifically, we study three settings: (1) agents incur costs
proportional to their preference in Section 4.3; (2) agents transfer goods to
compensate for preference imbalances in Section 4.4; and (3) users pay
providers based on a “market price” in Section 4.5.

  * •

We show that, in the latter two settings, it is possible to simultaneously
guarantee incentive compatibility, $O(\log(T))$ optimal regret, and fairness
(see Theorems 9 and 11). Moreover, in the second setting, this guarantee also
coincides with high social welfare (see Theorem 9).

In short, our main contribution is to show that, under appropriate cost and
transfer rules, it is possible to simultaneously guarantee all four
desiderata, thereby aligning local and global performance objectives.

###  4.1 Incentive compatibility: The Gale-Shapley algorithm

The first desideratum in designing $(\mathcal{M},\mathcal{C},\mathcal{T})$ is
incentive compatibility. We guarantee incentive compatibility by making use of
the well-known Gale-Shapley (GS) algorithm, which is given in Algorithm 1. We
begin by reviewing the following result, cf. Gale and Shapley (1962) and Roth
(2008).

######  Lemma 1.

Let $\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ denote an
arbitrary preference function. Let $\mathcal{M}(\cdot;\psi)$ denote a matching
returned by the GS algorithm, as given in Algorithm 1, when applied over
payoffs $V(\cdot,\cdot;\psi)$. Then, $\mathcal{M}(\cdot;\psi)$ is a stable
matching under payoffs $V(\cdot,\cdot;\psi)$: i.e.,
$\mathcal{M}(\cdot;\psi)\in S(V(\cdot,\cdot;\psi))$.

###### Proof.

See Appendix B. ∎

Therefore, applying the GS algorithm over payoffs $V(\cdot,\cdot;\nu_{t})$ at
time step $t$ returns a matching that is stable under
$V(\cdot,\cdot;\nu_{t})$. This result implies that ensuring incentive
compatibility is straightforward.

######  Lemma 2.

Consider the setup in Section 3.1. Suppose that, at every time step $t\in[T]$,
$\mathcal{M}(\cdot;\nu_{t})$ is a matching returned by the GS algorithm when
applied over payoffs $V(\cdot,\cdot;\nu_{t})$. Then,
$(\mathcal{M},\mathcal{C},\mathcal{T})$ is incentive-compatible.

###### Proof.

This result follows directly from Lemma 1 and Definition 1. ∎

Lemma 2 provides a way to ensure $(\mathcal{M},\mathcal{C},\mathcal{T})$ is
incentive-compatible. In the remainder of this work, we therefore assume that
the matching $\mathcal{M}(\cdot;\nu_{t})$ at time $t$ is one returned by the
GS algorithm under payoffs $V(\cdot,\cdot;\nu_{t})$. Doing so guarantees that
the matching at every time step is incentive-compatible.

Input: Set of agents $\mathcal{A}=\mathcal{U}\cup\mathcal{P}$, where the set
of users is $\mathcal{U}=\\{u_{1},u_{2},\ldots,u_{N}\\}$, the set of providers
is $\mathcal{P}=\\{p_{1},p_{2},\ldots,p_{L}\\}$,
$\mathcal{U}\cap\mathcal{P}=\emptyset$, and $N\geq L$. A payoff function
$V:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$.

Output: Matching $M\in S(V)\subset\mathcal{W}$.

1 Initialize matching $M:\mathcal{A}\rightarrow\mathcal{A}$ such that
$M(a)\leftarrow\emptyset$ for all $a\in\mathcal{A}$;

2 Initialize empty (FIFO) queues $Q(p)\leftarrow[\hskip 1.0pt]$ for all
$p\in\mathcal{P}$;

// Fill each provider’s queue with users in order of decreasing preference.

3 for  _$p\in\mathcal{P}$_ do

4 for  _$i=1,2,\ldots,N$_ do

Append $r^{-1}(i;V(p,\cdot))$ to $Q(p)$;

// Add $p$’s $i$-th ranked user.

5

6 end for

7

8 end for

9

// As long as there exists a provider who is unmatched...

10 while  _$\exists p\in\mathcal{P}:M(p)=\emptyset$_ do

$u\leftarrow\text{pop}(Q(p))$;

// Provider $p$’s favorite user of those remaining in $p$’s queue.

// If user $u$ is unmatched, match $u$ and $p$.

11 if  _$M(u)=\emptyset$_ then

12 $M(u)\leftarrow p$;

13 $M(p)\leftarrow u$;

14

// If user $u$ prefers $p$ to its current match $M(u)$, match $u$ and $p$.

15 else if  _$V(u,p) >V(u,M(u))$_ then

16 $M^{\prime}(M(u))\leftarrow\emptyset$;

17 $M(u)\leftarrow p$;

18 $M(p)\leftarrow u$;

19

20

21 end while

22Return $M$;

Algorithm 1 Gale-Shapley algorithm (with providers as proposers)

###  4.2 No cost or transfer

We begin with the no-cost, no-transfer setting, in which:

$\displaystyle\mathcal{C}(a_{1},a_{2};\psi)$ $\displaystyle=0,$ (2)
$\displaystyle\mathcal{T}(a_{1},a_{2};\psi)$ $\displaystyle=0,$ (3)

for all $a_{1}\in\mathcal{A}$, $a_{2}\in\mathcal{A}^{+}$, and
$\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$.

The no-cost, no-transfer setting with bandit learners is analogous to that
examined by Liu et al. (2020a), and we extend their results. The following
result shows that, while all agents’ pessimal regret grows $O(\log(T))$, there
are settings in which at least one agent’s optimal regret grows $\Omega(T)$.

Let
$\Delta_{\max}(a)=\max_{a_{1},a_{2}\in\mathcal{A}^{+}}(\mu(a,a_{1})-\mu(a,a_{2}))$
and
$\Delta_{\min}=\min_{a_{1}\in\mathcal{A},a_{2}\in\mathcal{A}^{+},a_{3}\in\mathcal{A}^{+}\setminus
a_{2}}|\mu(a_{1},a_{2})-\mu(a_{1},a_{3})|$.

######  Proposition 3.

Consider the setup described in Section 3.1 with no costs or transfers, as
stated in (2)-(3). Then, if the GS algorithm is applied over
$V(\cdot,\cdot;\nu_{t})$ at every time step $t\in[T]$, the system is
incentive-compatible. Moreover,

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})$ $\displaystyle\leq
2N^{2}L\Delta_{\max}(a)\left(\frac{8\sigma^{2}\alpha\log(T)}{\Delta_{\min}^{2}}+\frac{\alpha}{\alpha-2}\right),$

for all $a\in\mathcal{A}$. However, under incentive compatibility, it is not
possible to guarantee fairness or that social welfare is high at every
$t\in[T]$, and there exist settings $(\mathcal{A},\mu)$ for which
$\bar{R}(a;\mathcal{M})=\Omega(T)$ for at least one agent $a\in\mathcal{A}$.

###### Proof.

See Appendix C. ∎

To see why, without costs or transfers, it is not possible to guarantee
$O(\log(T))$ optimal regret, fairness, or high social welfare alongside
stability, consider the following example, which is further detailed in the
proof of Proposition 3 in Appendix C.

######  Example 1.

Suppose $\mathcal{U}=\\{u_{1},u_{2},u_{3}\\}$,
$\mathcal{P}=\\{p_{1},p_{2},p_{3}\\}$, and:

$\displaystyle
u_{1}\succ_{\mu(p_{1},\cdot)}u_{2}\succ_{\mu(p_{1},\cdot)}u_{3},$
$\displaystyle\qquad\qquad
p_{3}\succ_{\mu(u_{1},\cdot)}p_{2}\succ_{\mu(u_{1},\cdot)}p_{1},$
$\displaystyle
u_{1}\succ_{\mu(p_{2},\cdot)}u_{2}\succ_{\mu(p_{2},\cdot)}u_{3},$
$\displaystyle\qquad\qquad
p_{3}\succ_{\mu(u_{2},\cdot)}p_{1}\succ_{\mu(u_{2},\cdot)}p_{2},$
$\displaystyle
u_{3}\succ_{\mu(p_{3},\cdot)}u_{2}\succ_{\mu(p_{3},\cdot)}u_{1},$
$\displaystyle\qquad\qquad
p_{1}\succ_{\mu(u_{3},\cdot)}p_{2}\succ_{\mu(u_{3},\cdot)}p_{3}.$

Without costs or transfers, the only two stable matchings under true payoffs
$V(\cdot,\cdot;\mu)=\mu(\cdot,\cdot)$ are:

$\displaystyle M_{1}(a)$ $\displaystyle=\begin{cases}p_{2},&a=u_{1},\\\
p_{1},&a=u_{2},\\\ p_{3},&a=u_{3},\\\ u_{2},&a=p_{1},\\\ u_{1},&a=p_{2},\\\
u_{3},&a=p_{3}.\end{cases}\qquad\qquad\qquad
M_{2}(a)=\begin{cases}p_{2},&a=u_{1},\\\ p_{3},&a=u_{2},\\\ p_{1},&a=u_{3},\\\
u_{3},&a=p_{1},\\\ u_{1},&a=p_{2},\\\ u_{2},&a=p_{3}.\end{cases}$

In particular, the optimal matching across agents is not the same. For
example, $\mkern 4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{p_{1}}_{t}=M_{1}$ while $\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern 4.5mu^{u_{2}}_{t}=M_{2}$,
which means that every time $\mathcal{M}(\cdot;\nu_{t})=M_{2}$, provider
$p_{1}$ experiences optimal regret $\mu(p_{1},u_{2})-\mu(p_{1},u_{3})>0$,
which is strictly positive because, by assumption, there are no ties (i.e.,
$a^{\prime}\neq
a^{\prime\prime}\implies\mu(a,a^{\prime})\neq\mu(a,a^{\prime\prime})$ for all
$a\in\mathcal{A}$). Similarly, every time $\mathcal{M}(\cdot;\nu_{t})=M_{1}$,
user $u_{2}$ experiences optimal regret $\mu(u_{2},p_{3})-\mu(u_{2},p_{1})>0$.
In the proof of Proposition 3, we show that
$T(M(\cdot;\nu_{t})=M_{1})+T(M(\cdot;\nu_{t})=M_{2})=\Omega(T)$, which implies
that the optimal regret of at least one agent is $\Omega(T)$. Intuitively,
because it is impossible for the matching at time $t$ to simultaneously be
both $M_{1}$ and $M_{2}$, at least one agent must incur a non-zero optimal
regret for $\Omega(T)$ time steps, which implies that its optimal regret grows
$\Omega(T)$.

In the proof of Proposition 3, we also show that it is possible for the
platform to choose matchings such that
$T(\mathcal{M}(\cdot;\nu_{t})=M_{2})=O(\log(T))$, which implies
$\bar{R}(p_{1};\mathcal{M})=O(\log(T))$ while
$\bar{R}(u_{2};\mathcal{M})=\Omega(T)=\omega(\log(T))$, thereby violating the
fairness condition. To show that high social welfare is not guaranteed,
suppose $\mathcal{M}(\cdot;\nu_{t})=M_{1}$ and
$\nu_{t}(u_{2},p_{3})>3W_{t}(\mathcal{M})=3\sum_{a\in\mathcal{A}}\nu_{t}(a,M_{1}(a))$
at some time $t\in[T]$, which is possible because the terms over which
$W_{t}(\mathcal{M})$ is summed does not include $\nu_{t}(u_{2},p_{3})$ because
$u_{2}$ and $p_{3}$ are not matched under $M_{1}$. Then,
$\max_{M\in\mathcal{W}}\sum_{a\in\mathcal{A}}\nu_{t}(a,M(a))\geq\nu_{t}(u_{2},p_{3})>3W_{t}(\mathcal{M})$,
which implies that the social welfare is low at time step $t$.

The first part of Proposition 3 states that, in the absence of costs and
transfers, applying the GS algorithm at each time step ensures that every
matching is incentive-compatible and that the pessimal regret of every agent
grows $O(\log(T))$, i.e., $\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})=O(\log(T))$ for all agents
$a\in\mathcal{A}$. Intuitively, this result means that, even under the
requirement that all matchings are stable, the agents can still learn enough
about their true preferences so that the matchings—which are based on the
agents’ transient (learned) preferences—converge to matchings that are stable
under the agents’ true preferences in $O(\log(T))$ time steps.

However, the second half of Proposition 3 reveals an impossibility result. It
first states that, without costs or transfers, there is no guarantee that the
_optimal_ regret of agents is $O(\log(T))$ under incentive compatibility. In
fact, there are settings in which the optimal regret of at least one agent
grows $\Omega(T)$, as shown in Example 1. Recall that the optimal regret
$\bar{R}(a;\mathcal{M})$ of an agent $a$ is the cumulative loss that $a$
incurs with the respect to the smallest loss it would have incurred under a
true stable matching while the pessimal regret $\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to6.13614pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.13614pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.29529pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})$ is taken
with respect to the largest loss under a true stable matching such that
$\bar{R}(a;\mathcal{M})\geq\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})$. As such, ensuring $\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to6.13614pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.13614pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.29529pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})=O(\log(T))$ reassures pessimistic
agents that they will at least reach their worst-case performance under a true
stable matching in $O(\log(T))$ time steps. However, the fact that
$\bar{R}(a;\mathcal{M})=\Omega(T)$ in some settings means that any optimistic
agent will be disappointed: it may take $\Omega(T)$ time steps to surpass the
worst-case performance under a true stable matching. Proposition 3 also states
that, under incentive compatibility, neither fairness nor high social welfare
are guaranteed, begging the question: Is it possible to guarantee low regret,
fairness, or high social welfare alongside stability?

###  4.3 Proportional cost with no transfer

In the previous section, we prove that, without costs or transfers, it is not
possible to guarantee all four desiderata simultaneously. We now turn to
another setting, showing that, while appealing to the platform, it also fails
to guarantee that incentive compatibility and low regret, fairness, or high
social welfare hold simultaneously. In the proportional-cost, no-transfer
setting,

$\displaystyle\mathcal{C}(a_{1},a_{2};\psi)$
$\displaystyle=\gamma\psi(a_{1},a_{2}),$ (4)
$\displaystyle\mathcal{T}(a_{1},a_{2};\psi)$ $\displaystyle=0,$ (5)

for all $a_{1}\in\mathcal{A}$, $a_{2}\in\mathcal{A}^{+}$, and
$\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$, where
$\gamma\in[0,1]$. Intuitively, the amount of resources that an agent $a_{1}$
expends when matched to $a_{2}$ is proportional to its desire to be matched to
$a_{2}$. For example, the amount of effort or time that $a_{1}$ devotes to a
date with $a_{2}$ depends on how much $a_{1}$ likes $a_{2}$.

######  Proposition 4.

Consider the setup described in Section 3.1 with no transfer and proportional
costs, as stated in (4)-(5). Then, if the GS algorithm is applied over
$V(\cdot,\cdot;\nu_{t})$ at every time step $t\in[T]$, the system is
incentive-compatible. Moreover, if $\gamma\in[0,1)$, then,

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R$ $\displaystyle(a;\mathcal{M})\leq
2N^{2}L(1-\gamma)\Delta_{\max}(a)\left(\frac{8\sigma^{2}\alpha\log(T)}{(1-\gamma)^{2}\Delta_{\min}^{2}}+\frac{\alpha}{\alpha-2}\right),$

for all $a\in\mathcal{A}$. However, under incentive compatibility, it is not
possible to guarantee fairness or that social welfare is high at every
$t\in[T]$, and there exist settings $(\mathcal{A},\mu)$ for which
$\bar{R}(a;\mathcal{M})=\Omega(T)$ for at least one agent $a\in\mathcal{A}$.

###### Proof.

Incentive compatibility follows from Lemma 1. For $\gamma\in[0,1)$, the
setting described in this claim is equivalent to that in Proposition 3, except
that the payoffs are scaled by $(1-\gamma)$. To see this, observe that
$V(a,a^{\prime};\psi)=\psi(a,a^{\prime})-\gamma\psi(a,a^{\prime})=(1-\gamma)\psi(a,a^{\prime})$.
Therefore, the same results as in Proposition 3 apply with the appropriate
scaling. ∎

Proposition 4 shows that, when $\gamma\in[0,1)$, we obtain the same
impossibility result as in Section 4.2, meaning that proportional costs with
$\gamma\in[0,1)$ do not improve upon the no-cost, no-transfer setting. We
therefore shift our attention to $\gamma=1$, which turns out to be
particularly appealing to the platform.

######  Lemma 5.

Consider the setup described in Section 3.1 and (4)-(5). If $\gamma=1$, then
all matchings are stable, i.e., for any
$\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ and
$M\in\mathcal{W}$, $M\in S(V(\cdot,\cdot;\psi))$.

###### Proof.

When $\gamma=1$, $V(\cdot,\cdot;\psi)=0$ for all
$\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$. Under any
matching $M\in\mathcal{W}$, there cannot exist another matching
$M^{\prime}\in\mathcal{W}$ such that $V(a,M^{\prime}(a);\psi)>V(a,M(a);\psi)$
for some $a$ since $0>0$ is always false, which implies that $M$ is stable.
This result holds for any $M\in\mathcal{W}$. ∎

######  Corollary 6.

Consider the setup described in Section 3.1 and (4)-(5). Suppose that the
platform wishes to maximize some objective function
$F_{t}:\mathcal{W}\rightarrow\mathbb{R}$ at every time step $t$. Then, when
$\gamma=1$, there is no performance cost to incentive compatibility: i.e.,
$\arg\max_{M\in\mathcal{W}}F_{t}(M)\in S(V(\cdot,\cdot;\nu_{t}))\forall
t\in[T]$.

###### Proof.

This result follows from Lemma 5. Since all matchings are stable at every time
step, all matchings are incentive-compatible, including
$\arg\max_{M\in\mathcal{W}}F_{t}(M)$. ∎

Corollary 6 suggests that the platform may be inclined to use proportional
costs, as given in (4)-(5), because these rules allow the platform to maximize
any objective function it desires while remaining incentive-compatible.
However, the next result shows that, under incentive compatibility,
proportional costs cannot guarantee low regret, fairness, or high social
welfare and are therefore undesirable.

######  Proposition 7.

Consider the setup described in Section 3.1 with no transfer and proportional
costs, as stated in (4)-(5). If the GS algorithm is applied over
$V(\cdot,\cdot;\nu_{t})$ at every time step $t\in[T]$, the system is
incentive-compatible. Suppose $\gamma=1$. Then, $\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to6.13614pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.13614pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.29529pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})\leq 0$ for
all $a\in\mathcal{A}$. However, under incentive compatibility, it is not
possible to guarantee fairness or that social welfare is high at every
$t\in[T]$, and there exist settings $(\mathcal{A},\mu)$ for which
$\bar{R}(a;\mathcal{M})=\Omega(T)$ for at least one agent $a\in\mathcal{A}$.

###### Proof.

See Appendix D. ∎

In other words, proportional costs cannot guarantee that even incentive
compatibility and low regret hold simultaneously. To understand the
impossibility result in Proposition 7, consider the following example, which
is further detailed in the proof of Proposition 7 in Appendix D.

######  Example 2.

Under the conditions in Proposition 7, the optimal regret of an agent $a$ is:

$\displaystyle\bar{R}(a;\mathcal{M})$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}\left[U_{t}(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu_{t}^{a}(a);\nu_{t})-U_{t}(a,\mathcal{M}(a;\nu_{t});\nu_{t})\right],$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}\left[X_{t}(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu_{t}^{a}(a))-\nu_{t}(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu_{t}^{a}(a);\nu_{t})-X_{t}(a,\mathcal{M}(a;\nu_{t}))+\nu_{t}(a;\mathcal{M}(a;\nu_{t});\nu_{t})\right],$
$\displaystyle=\sum_{t=1}^{T}\sqrt{2\sigma^{2}\alpha\log(t)}\mathbb{E}\left[(T_{t-1}(a,\mathcal{M}(a;\nu_{t})))^{-1/2}-(T_{t-1}(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu_{t}^{a}(a)))^{-1/2}\right],$

where the last line follows from the definition of $\nu_{t}$. By Lemma 5, all
matchings are stable, irrespective of the payoff function, meaning that the
platform can choose $\mathcal{M}(\cdot;\nu_{t})$ from any matching in
$\mathcal{W}$ while remaining incentive compatible. As such,

$\displaystyle\bar{R}(a;\mathcal{M})$
$\displaystyle=\sum_{t=1}^{T}\sqrt{2\sigma^{2}\alpha\log(t)}\mathbb{E}\left[(T_{t-1}(a,\mathcal{M}(a;\nu_{t})))^{-1/2}-(T_{t-1}(a,\eta^{*}_{t}(a)))^{-1/2}\right],$

where
$\eta^{*}_{t}(a)\in\operatorname*{arg\,max}_{a^{\prime}\in\mathcal{A}^{+}}\mathbb{E}\left[T_{t-1}(a,a^{\prime}))\right]$.

Suppose there are two providers $p_{1}$ and $p_{2}$, where $N\geq L>2$.
Suppose that, at every time step, $\mathcal{M}$ repeatedly matches $p_{1}$ to
the same $u_{1}$, $p_{2}$ uniformly at random to one of the remaining users
$u\in\mathcal{U}\setminus u_{1}$, and all remaining providers arbitrarily to
complete the matching. Such matchings are incentive compatible by Lemma 5 and
are therefore valid choices of $\mathcal{M}(\cdot;\nu_{t})$.

Under this matching scheme, after $\max_{u\in\mathcal{U}}T_{0}(p_{1},u)$ time
steps, $p_{1}$ is always matched to $\eta_{t}^{*}(p_{1})$, where
$|\eta_{t}^{*}(p_{1})|=1$, which implies that
$\bar{R}(p_{1};\mathcal{M})=O(1)$. However, since $p_{2}$ is matched uniformly
at random, it experiences non-zero regret whenever it is not matched to a user
$u\in\eta_{t}^{*}(p_{2})$. As long as $|\eta_{t}^{*}(p_{2})|\neq N$ at time
$t$, then $p_{2}$ is matched to a user $u\notin\eta_{t}^{*}(p_{2})$ with
probability at least $1/N$ and therefore incurs non-zero regret. It is clear
that $|\eta_{t}^{*}(p_{2})|=N$ can only occur at most $\lceil T/N\rceil$
times. As such, $\bar{R}(p_{2};\mathcal{M})=\Omega(T)$.

This example shows that it is neither possible to guarantee low regret nor the
fair distribution of regret across agents. Intuitively, because all matchings
are stable, the platform is afforded so much flexibility that it can choose
matchings that have detrimental regret outcomes. It is additionally not
possible to guarantee high social welfare. Recall that social welfare is the
sum of payoffs over all agents. Under $\gamma=1$, $V(\cdot,\cdot;\nu_{t})=0$
for all $t\in[T]$, which implies that the social welfare is always $0$. By
Definition 3, the social welfare is therefore low at every time step.

We see that this intuitively pleasing setting yields the same impossibility
result as in the no-cost, no-transfer setting. Interestingly, this setting is
appealing to platforms because, when $\gamma=1$, there is no performance cost
to incentive compatibility (Corollary 6). In other words, the platform can
chose a matching that maximizes any objective function that it desires while
being assured that the agents will not defect.

For example, suppose the platform has its own objective function
$F_{t}:\mathcal{W}\rightarrow\mathbb{R}$ that it wishes to maximize at each
time step $t$. Then, the platform can assign the matching
$\operatorname*{arg\,max}_{M\in\mathcal{W}}F_{t}(M)$ that maximizes $F_{t}$
without sacrificing incentive compatibility, meaning that the platform can
feel confident that both the users and providers will continue to use the
platform’s services.

However, by the impossibility result given in Proposition 7, the fact that
users and providers continue to use the platform for matching does not mean
that they do so happily. In fact, some agents may be unhappy because the
platform’s matchings impose a large penalty on them by causing them to incur
high optimal regret. Moreover, they may be unhappy because they incur high
optimal regret while other agents are allowed to incur low optimal regret (due
to unfairness). This finding suggests that the platform may suffer if an
alternate platform that offers higher payoffs to the agents arises.

Adding to the discussion at the end of Section 4.2, this setting also
illustrates why it may be prudent to pay attention to the agents’ optimal
regret in addition to their pessimal regret. In particular, under the
conditions in Proposition 7, $\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})\leq 0$ for all agents
$a\in\mathcal{A}$ while it is possible that $\bar{R}(a;\mathcal{M})=\Omega(T)$
for some $a\in\mathcal{A}$. As a result, even though pessimal regret is
guaranteed to be non-positive, optimal regret can grow linearly in $T$. This
finding reinforces the notion that it is not enough to upper bound the
pessimal regret because there may be a very large gap between optimal and
pessimal regrets.

###  4.4 Balanced transfer

We now show that there exists a transfer rule under which the platform can
guarantee all four desiderata simultaneously. In the no-cost and balanced-
transfer setting,

$\displaystyle\mathcal{C}(a_{1},a_{2};\psi)$ $\displaystyle=0$ (6)
$\displaystyle\mathcal{T}(a_{1},a_{2};\psi)$
$\displaystyle=\frac{1}{2}(\psi(a_{2},a_{1})-\psi(a_{1},a_{2})),$ (7)

for all $a_{1}\in\mathcal{A}$, $a_{2}\in\mathcal{A}^{+}$, and
$\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$.

To gain an intuition for this setting, suppose
$\psi(a_{1},a_{2})>\psi(a_{2},a_{1})$. Then, agent $a_{1}$ attributes greater
value to being matched with $a_{2}$ than vice versa. Under (6)-(7), agent
$a_{1}$ benefits more from the match $(a_{1},a_{2})$ than $a_{2}$ does, and
$a_{1}$ compensates for this imbalance by investing resources to make the
experience more amenable for $a_{2}$. For example, suppose that an athlete
$a_{1}$ is more interested in receiving lessons from coach $a_{2}$ than
$a_{2}$ is interested in coaching $a_{1}$. Then, $a_{1}$ can offset this
difference by offering to pay more for lessons with $a_{2}$. In the
literature, the balanced transfer is viewed as compensation or a bargaining
solution.

We previously required that each agent’s true preferences are unique in that,
for all $a_{1}\in\mathcal{A}$, $\mu(a_{1},a_{2})\neq\mu(a_{1},a_{3})$ when
$a_{2}\neq a_{3}$. In this section, we require a slightly stronger notion of
uniqueness.

######  Definition 4.

A function $h:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ is
_pairwise-unique_ if $h(a_{1},a_{2})\neq h(a_{3},a_{4})$ unless
$(a_{1},a_{2})=(a_{3},a_{4})$ or $(a_{2},a_{1})=(a_{3},a_{4})$.

######  Lemma 8.

Consider the setup described in Section 3.1 and (6)-(7). If payoffs
$V(\cdot,\cdot;\psi)$ are pairwise-unique, then there is a unique stable
matching under these payoffs: i.e., $|S(V(\cdot,\cdot;\psi))|=1$.

###### Proof.

See Appendix E. ∎

We now show that, under a pairwise-uniqueness condition, the platform can
simultaneously guarantee all four desiderata. Let
$\rho(a,a^{\prime})=\frac{1}{2}(\mu(a,a^{\prime})+\mu(a^{\prime},a))$ and
$\Delta^{\rho}_{\min}=\min_{a_{1}\in\mathcal{A},a_{2}\in\mathcal{A}^{+},a_{3}\in\mathcal{A}^{+}\setminus
a_{2}}|\rho(a_{1},a_{2})-\rho(a_{1},a_{3})|$. By Lemma 8, if $\rho$ is
pairwise-unique, $S(\rho)$ contains only one element, which we denote by
$M^{*,\rho}=S(\rho)$. Accordingly, let
$\Delta_{\max}^{*,\rho}(a)=\max_{a^{\prime}\in\mathcal{A}^{+}}(\rho(a,M^{*,\rho}(a))-\rho(a,a^{\prime}))$.

######  Theorem 9.

Consider the setup described in Section 3.1 with no cost and a balanced
transfer, as stated in (6)-(7). Then, if the GS algorithm is applied over
$V(\cdot,\cdot;\nu_{t})$ at every time step $t\in[T]$, the system is
incentive-compatible and the social welfare is high at all $t\in[T]$.
Moreover, if $\rho$ is pairwise-unique, then,

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R$
$\displaystyle(a;\mathcal{M})=\bar{R}(a;\mathcal{M})\leq\Delta_{\max}^{*,\rho}(a)N^{2}L\left(\frac{8\sigma^{2}\alpha\log(T)}{(\Delta^{\rho}_{\min})^{2}}+\frac{\alpha}{\alpha-2}\right),$

for all $a\in\mathcal{A}$, and $\mathcal{M}$ is fair.

###### Proof.

See Appendix E. ∎

In other words, when there are balanced transfers, applying the GS algorithm
at every time step _simultaneously guarantees stability, low regret, fairness,
and high social welfare_. Put differently, as long as the platform facilitates
balanced transfers between matched agents, once it ensures that the matchings
are incentive-compatible, it gets low optimal regret, fairness, and high
social welfare for free.

In this way, this key result shows that balanced transfers (i.e., bargaining
or compensation) elegantly align local and global desiderata. It illustrates
that, for sequential decision-making agents who must learn their preferences
while competing for resources, there is a way to be matched such that the
assignment is incentive-compatible and yields high social welfare at _every_
time step while allowing agents to learn enough about their own preferences so
that _all_ agents efficiently converge to their optimal true stable matching.

In Section 5, we discuss the key ingredients in the proof of Theorem 9.

###  4.5 Pricing

In the previous section, we show that it is possible to simultaneously
guarantee all four desiderata via transfers that depend on the preferences of
both agents being matched. While such transfers are often feasible, there are
settings in which the amount transferred cannot be tailored to the individual
parties involved in the match. For example, suppose each provider is selling a
good. A good is typically priced at a value that does not depend on which user
purchases it. We therefore turn our attention to the pricing setting, in
which:

$\displaystyle\mathcal{C}(p,u;\psi)$
$\displaystyle=c_{1}\qquad\qquad\qquad\hskip
2.0pt~{}\mathcal{C}(u,p;\psi)=c_{2}$ (8) $\displaystyle\mathcal{T}(p,u;\psi)$
$\displaystyle=g(p;\psi)\qquad\qquad~{}\mathcal{T}(u,p;\psi)=-g(p;\psi)$ (9)

for all $u\in\mathcal{U}$, $p\in\mathcal{P}$, and
$\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$, where
$c_{1},c_{2}\in\mathbb{R}$ and $g:\mathcal{P}\rightarrow\mathbb{R}$.

In this way, the transfer $g(p;\psi)$ can be viewed as the “price” of being
matched with $p$ that is constant across all agents wishing to “purchase” a
match with $p$. This setting differs from previous ones in that $\mathcal{C}$
and $\mathcal{T}$ do not depend on the preferences of the specific agents
being matched. Rather, based on the information state $\nu_{t}$,
$g(p;\nu_{t})$ is assigned to providers in a way that is reminiscent of
assigning prices to goods. In this way, $\nu_{t}$ can be viewed as revealing
the demand for providers, and $g(p;\psi)$ can be viewed as the “market price”
of being matched with $p$ (or the good that $p$ offers).

For example, suppose $\mathcal{U}$ is a set of patients, each hoping to book
an appointment with a doctor $p\in\mathcal{P}$. Suppose the price of an
appointment with $p$ is fixed such that $g(p;\nu_{t})$ does not depend on the
specific patient $u$. Since there are a limited number of available
appointments, $g(p;\nu_{t})$ may depend on the current demand $\nu_{t}$, which
can reflect, for instance, different patient needs and different doctor
specialties. If an appointment is booked (i.e., a match is made), then the
patient pays the doctor’s office (i.e., makes a transfer). With time, patients
learn their preferences over doctors, and doctors learn which patients require
their services (e.g., if a doctor feels that another doctor can better meet
the patient’s needs, it is in the interest of the former to refer the patient
to avoid poor reviews). In such settings, fairness and social welfare matter
greatly, and preferences must be learned from a small number of sparse
interactions.

Note that the presence of costs $c_{1}$ and $c_{2}$ is a technical detail. For
those interested, recall that, without loss of generality, we assumed that all
agents prefer to be matched than unmatched, and
$\mathcal{C}(a,\emptyset)=\mathcal{T}(a,\emptyset)=0$ for all
$a\in\mathcal{A}$. $c_{1}$ and $c_{2}$ are normalizing constants to ensure
that this assumption is consistent with our analysis. For instance, in one
setting that we examine in the Appendix, $c_{1}=0$ and $c_{2}<0$, which
implies that matching a user increases its payoff by $-c_{2}>0$. In this way,
$-c_{2}$ can be viewed as a baseline utility that all agents gain if they are
matched versus when they are unmatched.

We now prove that, under mild conditions, there always exists at least one
pricing rule that simultaneously guarantees incentive compatibility, low
regret, and fairness.

######  Lemma 10.

Consider the setup described in Section 3.1 and (8)-(9). Suppose there exists
a $B\in\mathbb{R}_{>0}$ such that $|\mu(u,\cdot)|\leq B$ for all
$u\in\mathcal{U}$. Then, there always exist constants $c_{1},c_{2}$ and
pricing $g$ such that $|S(V(\cdot,\cdot;\mu))|=1$, i.e., there is a unique
stable matching under payoffs $V(\cdot,\cdot;\mu)$.

###### Proof.

See Appendix F. ∎

Under the conditions of Lemma 10, $|S(V(\cdot,\cdot;\mu))|=1$. Denote this
matching by $M^{*,{\scriptscriptstyle B}}$, and let
$\Delta^{*,{\scriptscriptstyle
B}}_{\max}(a)=2B(L-1)\mathbf{1}(a\in\mathcal{U})+\max_{a^{\prime}\in\mathcal{A}^{+}}(\mu(a,M^{*,{\scriptscriptstyle
B}}(a))-\mu(a,a^{\prime}))$.

######  Theorem 11.

Consider the setup described in Section 3.1 with constant costs and market
prices, as stated in (8)-(9). Then, if the GS algorithm is applied over
$V(\cdot,\cdot;\nu_{t})$ at every time step $t\in[T]$, the system is
incentive-compatible. Moreover, if there exists a $B\in\mathbb{R}_{>0}$ such
that $|\mu(u,\cdot)|\leq B$ for all $u\in\mathcal{U}$, then there exist
constants $c_{1}$ and $c_{2}$ as well as a pricing rule $g$ such that

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R$
$\displaystyle(a;\mathcal{M})=\bar{R}(a;\mathcal{M})\leq
2\Delta_{\max}^{*,{\scriptscriptstyle
B}}(a)N^{2}L\left(\frac{8\sigma^{2}\alpha\log(T)}{(\Delta_{\min})^{2}}+\frac{\alpha}{\alpha-2}\right),$

for all $a\in\mathcal{A}$, and $\mathcal{M}$ is fair.

###### Proof.

See Appendix F. ∎

This result shows that, under mild conditions, there is always at least one
way to price matches such that the platform _simultaneously guarantees
incentive-compatibility, low optimal regret, and fairness_. Put differently,
the platform can always find at least one pricing rule such that once it
ensures the matchings are incentive-compatible, it gets low optimal regret and
fairness for free. Under the particular pricing rule through which we show
existence in our proof, high social welfare is not guaranteed, but it may be
possible to do so under other pricing rules. In Section 5, we discuss the key
ingredients in the proof of Theorem 11, which may provide a roadmap for the
formulation of other pricing rules.

Finally, note that the results in this section hold with small modifications,
such as if users and providers are switched; if
$\mathcal{C}(u,p;\psi)=g(p;\psi)-c_{1}$, $\mathcal{C}(p,u;\psi)=0$, and
$\mathcal{T}=0$; or if
$\mathcal{C}(u,p;\psi)=c_{2}+(1-\gamma^{\prime})g(p;\psi)$,
$\mathcal{T}(u,p;\psi)=-\gamma^{\prime}g(p;\psi)$,
$\mathcal{C}(p,u;\psi)=c_{1}-(1-\gamma^{\prime})g(p;\psi)$, and
$cT(p,u;\psi)=\gamma^{\prime}g(p;\psi)$.

##  5 Discussion

Summary. In this work, we model the sequential decision-making of learning
agents under uncertainty and competition by blending the matching and MAB
problems. As in the two-sided matching problem, users compete for matches with
providers, and vice versa. As in the MAB problem, agents do not know their
preferences over matches a priori and must learn them from experience.

We focus our attention on the _centralized matching market with bandit
learners_ , extending the results of Liu et al. (2020a). In particular, the
framework offered by Liu et al. (2020a) suggests that it is not possible for
competitive matching markets to simultaneously guarantee incentive
compatibility and low optimal regret—an agent’s regret when taken with respect
to its optimal true stable matching. We add a layer of complexity not present
in the work by Liu et al. (2020a) and, in doing so, show that it is possible
to _simultaneously guarantee four key desiderata_ : (1) _incentive
compatibility_ such that no pair of agents is incentivized to defect from the
matching; (2) _low regret_ such that all agents incur $O(\log(T))$ optimal and
pessimal regret; (3) the _fair_ distribution of regret (or, equivalently,
payoffs) across agents; and (4) high _social welfare_. These results
illustrate that, for sequential decision-making agents who must learn their
preferences while competing for resources, there is a way to be matched such
that the assignment is incentive-compatible and yields high social welfare at
_every_ time step while allowing all agents to learn enough about their own
preferences so that _all_ agents efficiently converge to their optimal true
stable matching.

The key to aligning these desiderata is the incorporation of costs
$\mathcal{C}$ and transfers $\mathcal{T}$ on top of the matching mechanism
$\mathcal{M}$. Costs and transfers arise naturally in settings where agents
compete for limited resources. For example, when user $u$ is repeatedly
refused a match with provider $p$, $u$ may develop fatigue, which manifests as
a cost $u$ associates with $p$. Similarly, when there is more demand for a
match with provider $p$ than supply, $p$ may charge a user $u$ for the match,
which manifests as a payment, or transfer, from $u$ to $p$.

Key intuition. Ensuring $(\mathcal{M},\mathcal{C},\mathcal{T})$ satisfies the
first three desiderata above consists of three main ingredients. First, the GS
algorithm is applied over $V(\cdot,\cdot;\nu_{t})$ at every time step
$t\in[T]$ to guarantee incentive compatibility. Second, $\mathcal{C}$ and
$\mathcal{T}$ are chosen such that, under the appropriate conditions,
$|S(V(\cdot,\cdot;\psi))|=1$. This step ensures that it is not possible for
the system to converge to a stable matching $M\in S(V(\cdot,\cdot;\mu))$ for
which one agent incurs $O(\log(T))$ regret at the expense of another agent $a$
whose optimal stable matching is $M^{\prime}\in S(V(\cdot,\cdot;\mu))\setminus
M$ such that $a$ incurs $\Omega(T)$ regret. Third, in order for agents to
achieve low regret, they must be allowed to learn a sufficient amount about
their true preferences $\mu$. The final challenge is therefore ensuring that
the addition of costs and transfers does not hinder this learning process. In
particular, $\mathcal{C}$ and $\mathcal{T}$ must allow agents to learn enough
such that the system converges to the unique stable matching
$S(V(\cdot,\cdot;\mu))$ in $O(\log(T))$ time steps. Combining these latter two
observations is key to both low regret and fairness.

Optimal versus pessimal regret. In their work, Liu et al. (2020a) show that it
is possible to assign matchings that are incentive compatible at every time
step while ensuring that the pessimal regret of every agent is low (i.e.,
$\mathchoice{\hbox to0.0pt{{$\underline{{\hbox to6.13614pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.13614pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.29529pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})=O(\log(T))$ for all
$a\in\mathcal{A}$). Intuitively, this guarantee reassures pessimistic agents
that they will at least reach their worst-case performance under a true stable
matching in $O(\log(T))$ time steps. However, under the framework offered by
Liu et al. (2020a), it is not possible to simultaneously guarantee incentive
compatibility and low _optimal regret_. In fact, there are settings in which
an agent’s optimal regret grows linearly in $T$, which means that any
optimistic agent will be disappointed: it may take $\Omega(T)$ time steps to
surpass its worst-case performance under a true stable matching.

In this work, we therefore focus on providing guarantees on not only pessimal
but also optimal regret. As discussed in Sections 4.2 and 4.3, it is also
prudent to pay attention to the agents’ optimal regret because there are
settings in which the gap between an agent’s optimal and pessimal regret is
very large. As such, low pessimal regret does not indicate low optimal regret.

Guidance for matching platforms. This work shows that, under the appropriate
cost and transfer rules, it is possible to guarantee stability, low regret,
fairness, and, in some cases, high social welfare. Put differently, as long as
the platform facilitates the appropriate costs and transfers between matched
agents, once it ensures that the matchings are incentive-compatible, it gets
low regret, fairness, and, in some cases, high social welfare for free. We
provide one such rule—the balanced transfer—in Section 4.4. In this setting,
the transfer rule depends on the specific pair of agents being matched. While
feasible in some scenarios, there are settings in which the amount transferred
cannot be tailored to the individual parties involved in the match. As such,
we provide another example in Section 4.5 in which the costs and transfers do
not depend on both matched agents in a way that is reminiscent of the pricing
of goods. We believe that there are many more cost and transfer rules that can
be analyzed and are not included in this work.

As an additional note, one of the broad takeaways is that it is possible to
guarantee incentive compatibility _without_ ensuring low regret, as shown in
the no-cost, no-transfer setting of Section 4.2 and the proportional costs
setting of Section 4.3. This means that users and providers may continue to
use a platform, but the platform _should not necessarily interpret the agents’
continued participation as a sign that the agents are satisfied_ with the
platform’s matchings. Indeed, as discussed in Section 4.3, the agents may be
quite unhappy even if they do not leave the platform. They do not leave the
platform is because incentive compatibility by definition ensures that agents
are not incentivized to defect. However, they may be unhappy because they
incur high losses (i.e., $\Omega(T)$ regret), possibly even while other agents
incur low losses (as shown by our unfairness results). It may be to the long-
term benefit of platforms to remedy this issue because such dissatisfaction
leaves room for another platform that can guarantee low regret to take its
place.

Future work. There are many paths for future work, such as considering
strategy-proofness (or truthfulness) as a desideratum, allowing information
sharing between agents, or studying related problems with bandit learners
under costs and transfers, including decentralized (or distributed) matchings,
matchings with ties, the hospital-residents problem in which multiple users
can be matched to the same provider, and more. Another direction would be to
apply the theoretical findings in this work to various machine learning
systems, such as recommender or resource allocation algorithms.

## References

  * Gale and Shapley (1962) David Gale and Lloyd S. Shapley.  College Admissions and the Stability of Marriage.  _The American Mathematical Monthly_ , 69(1):9–15, 1962.
  * Axtell and Kimbrough (2008) Robert L. Axtell and Steven O. Kimbrough.  The High Cost of Stability in Two-Sided Matching: How Much Social Welfare Should be Sacrificed in the Pursuit of Stability.  In _Proceedings of the 2008 World Congress on Social Simulation (WCSS 2008)_ , Fairfax, USA, 2008.
  * Cesa-Bianchi and Lugosi (2006) Nicol‘o Cesa-Bianchi and Gábor Lugosi.  _Prediction, Learning, and Games_.  Cambridge University Press, New York, NY, USA, 2006.
  * Bubeck and Cesa-Bianchi (2012) Sébastien Bubeck and Nicolò Cesa-Bianchi.  Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems.  _Foundations and Trends in Machine Learning_ , 5(1), 2012\.
  * Liu et al. (2020a) Lydia T. Liu, Horia Mania, and Michael I. Jordan.  Competing Bandits in Matching Markets.  In Silvia Chiappa and Roberto Calandra, editors, _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS 2020)_ , pages 1618–1628, Online, 2020a. PMLR.
  * Ashlagi et al. (2017) Itai Ashlagi, Yash Kanoria, and Jacob D. Leshno.  Unbalanced Random Matching Markets: The Stark Effect of Competition.  _Journal of Political Economy_ , 125(1):69–98, 2017.
  * Knuth and De Bruijn (1997) Donald Ervin Knuth and N. G. De Bruijn.  _Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms_ , volume 10 of _CRM proceedings & lecture notes_.  American Mathematical Society, 1997.
  * Roth (2008) Alvin E Roth.  Deferred acceptance algorithms: history, theory, practice, and open questions.  _International Journal of Game Theory_ , 36:537–569, 2008\.
  * Roth and Vate (1990) Alvin E. Roth and John H. Vande Vate.  Random Paths to Stability in Two-Sided Matching.  _Econometrica_ , 58(6):1475–1480, 1990.
  * Echenique and Yariv (2012) Federico Echenique and Leeat Yariv.  An Experimental Study of Decentralized Matching.  Technical report, California Institute of Technology, Pasadena, CA, USA, 2012.
  * Kuhn (1955) Harold W. Kuhn.  The Hungarian method for the assignment problem.  _Naval Research Logistics Quarterly_ , 2(1-2):83–97, 1955.
  * Ross and Soland (1975) G. Terry Ross and Richard M. Soland.  A branch and bound algorithm for the generalized assignment problem.  _Mathematical Programming_ , 8:91–103, 1975.
  * Pentico (2007) David W. Pentico.  Assignment problems: A golden anniversary survey.  _European Journal of Operational Research_ , 176(2):774–793, 2007.
  * Shapley and Scarf (1974) Lloyd Shapley and Herbert Scarf.  On cores and indivisibility.  _Journal of Mathematical Economics_ , 1:23–37, 1974.
  * Roth (1984) Alvin E. Roth.  The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory.  92(6):991–1016, 1984.
  * Irving (1985) Robert W. Irving.  An Efficient Algorithm for the “Stable Roommates” Problem.  _Journal of Algorithms_ , 6(4):577–595, 1985\.
  * Dean and Swar (2009) Brian C Dean and Namrata Swar.  The Generalized Stable Allocation Problem.  In _Proceedings of Third International Workshop on Algorithms and Computation (WALCOM 2009)_ , volume 5431, pages 238–249, Kolkata, India, 2009\. Springer-Verlag.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit Algorithms_.  Cambridge University Press, Cambridge, UK, 2020.
  * Wilson et al. (2014) Robert C. Wilson, Andra Geana, John M. White, and Jonathan D. Ludvig, Elliot A .and Cohen.  Humans use directed and random exploration to solve the explore–exploit dilemma.  _Journal of Experimental Psychology: General_ , 143(6):2074–2081, 2014.
  * Schnabel et al. (2018) Tobias Schnabel, Paul N. Bennett, Susan T. Dumais, and Thorsten Joachims.  Short-Term Satisfaction and Long-Term Coverage: Understanding How Users Tolerate Algorithmic Exploration.  In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining (WSDM 2018)_ , pages 513–521, Marina Del Rey, CA, USA, 2018.
  * Wilson et al. (2021) Robert C. Wilson, Elizabeth Bonawitz, Vincent D. Costa, and R. Becket Ebitz.  Balancing exploration and exploitation with information and randomization.  _Current Opinion in Behavioral Sciences_ , 38:49–56, 2021\.
  * Sutton and Barto (2018) Richard S. Sutton and Andrew G. Barto.  _Reinforcement Learning: An Introduction_.  The MIT Press, 2nd edition, 2018.
  * Wiering and Van Otterlo (2012) Marco Wiering and Martijn Van Otterlo.  Reinforcement Learning: State-of-the-Art.  _Adaptation, Learning, and Optimization_ , 12(3), 2012.
  * Lai and Robbins (1985) T. L. Lai and Herbert Robbins.  Asymptotically efficient adaptive allocation rules.  _Advances in Applied Mathematics_ , 6(1):4–22, 1985.
  * Thompson (1933) William R. Thompson.  On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples.  _Biometrika_ , 25(3-4):285–294, 1933.
  * Auer et al. (2002) Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer.  Finite-time Analysis of the Multiarmed Bandit Problem.  _Machine learning_ , 47(2):235–256, 2002.
  * Das and Kamenica (2005) Sanmay Das and Emir Kamenica.  Two-Sided Bandits and the Dating Market.  In Leslie Pack Kaelbling, editor, _Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI 2005)_ , volume 5, pages 947–952, Edinburgh, Scotland, 2005.
  * Mansour et al. (2018) Yishay Mansour, Aleksandrs Slivkins, and Zhiwei Steven Wu.  Competing Bandits: Learning Under Competition.  In Anna R. Karlin, editor, _9th Innovations in Theoretical Computer Science Conference (ITCS 2018)_ , volume 94 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 48:1–48:27, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * Aridor et al. (2020) Guy Aridor, Yishay Mansour, Aleksandrs Slivkins, and Zhiwei Steven Wu.  Competing Bandits: The Perils of Exploration Under Competition.  _arXiv:2007.10144 [cs.GT]_ , 2020.
  * Liu and Zhao (2010) Keqin Liu and Qing Zhao.  Distributed Learning in Multi-Armed Bandit With Multiple Players.  _IEEE Transactions on Signal Processing_ , 58(11):5667–5681, 2010.
  * Kalathil et al. (2014) Dileep Kalathil, Naumaan Nayyar, and Rahul Jain.  Decentralized Learning for Multiplayer Multiarmed Bandits.  _IEEE Transactions on Information Theory_ , 60(4):2331–2345, 2014.
  * Bubeck et al. (2020) Sébastien Bubeck, Yuanzhi Li, Yuval Peres, and Mark Sellke.  Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without.  In Jacob Abernethy and Shivani Agarwal, editors, _Proceedings of Thirty Third Annual Conference on Learning Theory (COLT 2020)_ , volume 125, pages 961–987, Online, 2020. PMLR.
  * Avner and Mannor (2019) Orly Avner and Shie Mannor.  Multi-User Communication Networks: A Coordinated Multi-Armed Bandit Approach.  _IEEE/ACM Transactions on Networking_ , 27(6):2192–2207, 2019.
  * Chawla et al. (2020) Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai.  The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits.  In Silvia Chiappa and Roberto Calandra, editors, _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS 2020)_ , pages 3471–3481, Online, 2020. PMLR.
  * Boursier and Perchet (2020) Etienne Boursier and Vianney Perchet.  Selfish Robustness and Equilibria in Multi-Player Bandits.  In Jacob Abernethy and Shivani Agarwal, editors, _Proceedings of Thirty Third Annual Conference on Learning Theory (COLT 2020)_ , pages 530–581, Online, 2020. PMLR.
  * Sankararaman et al. (2020) Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman.  Dominate or Delete: Decentralized Competing Bandits with Uniform Valuation.  _arXiv:2006.15166 [cs.LG]_ , 2020.
  * Vial et al. (2020) Daniel Vial, Sanjay Shakkottai, and R. Srikant.  Robust Multi-Agent Multi-Armed Bandits.  _arXiv:2007.03812 [cs.LG]_ , 2020.
  * Liu et al. (2020b) Lydia T. Liu, Feng Ruan, Horia Mania, and Michael I. Jordan.  Bandit Learning in Decentralized Matching markets.  _arXiv:2012.07348 [cs.LG]_ , 2020b.
  * Shapley and Shubik (1971) Lloyd S. Shapley and Martin Shubik.  The Assignment Game I: The Core.  _International Journal of Game theory_ , 1(1):111–130, 1971.
  * Becker (1973) Gary S. Becker.  A Theory of Marriage: Part I.  _Journal of Political Economy_ , 81(4):813–846, 1973.
  * Kelso Jr. and Crawford (1982) Alexander S. Kelso Jr. and Vincent P. Crawford.  Job Matching, Coalition Formation, and Gross Substitutes.  _Econometrica_ , 50(6):1483–1504, 1982.
  * Hitsch et al. (2010) Gunter J. Hitsch, Ali Hortaçsu, and Dan Ariely.  Matching and Sorting in Online Dating.  _The American Economic Review_ , 100(1):130–63, 2010.
  * Masarani and Gokturk (1989) F. Masarani and Sadik S. Gokturk.  On the existence of fair matching algorithms.  _Theory and Decision_ , 26(3):305–322, 1989.
  * Klaus and Klijn (2006) Bettina Klaus and Flip Klijn.  Procedurally fair and stable matching.  _Economic Theory_ , 27(2):431–447, 2006.
  * Sühr et al. (2019) Tom Sühr, Asia J. Biega, Meike Zehlike, Krishna P. Gummadi, and Abhijnan Chakraborty.  Two-Sided Fairness for Repeated Matchings in Two-Sided Markets: A Case Study of a Ride-Hailing Platform.  In _Proceedings of the Twenty Fifth ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 3082–3092, New York, NY, USA, 2019. Association for Computing Machinery.
  * Wu and Roth (2018) Qingyun Wu and Alvin E. Roth.  The lattice of envy-free matchings.  _Games and Economic Behavior_ , 109:201–211, 2018.
  * Roth (1982) Alvin E. Roth.  The Economics of Matching: Stability and Incentives.  _Mathematics of Operations Research_ , 7(4):617–628, 1982.
  * Ashlagi and Gonczarowski (2018) Itai Ashlagi and Yannai A. Gonczarowski.  Stable matching mechanisms are not obviously strategy-proof.  _Journal of Economic Theory_ , 177:405–425, 2018.
  * Irving (1994) Robert W. Irving.  Stable marriage and indifference.  _Discrete Applied Mathematics_ , 48(3):261–272, 1994.
  * Manlove (2002) David F. Manlove.  The structure of stable marriage with indifference.  _Discrete Applied Mathematics_ , 122(1-3):167–181, 2002.
  * Vershynin (2018) Roman Vershynin.  _High-Dimensional Probability: An Introduction with Applications in Data Science_ , volume 47 of _Cambridge Series in Statistical and Probabilistic Mathematics_.  Cambridge University Press, Cambridge, UK, 2018.

Appendix

Below, we provide proofs of the results stated in work titled “Regret,
stability, and fairness in matching markets with bandit learners.” All results
and definitions that appear in the manuscript are numbered in the same manner
below. Results that appear in the Appendix but not in the manuscript are
preceded by the letter of the corresponding section in the Appendix.

##  Appendix A Preliminary results

Assumptions. At various points in our analysis, we make assumptions about the
uniqueness of preferences or payoffs. This is a fairly mild assumption, as it
requires that the corresponding real-valued preferences (or payoffs) differ by
some amount, however small. Intuitively, an assumption of uniqueness is
equivalent to an assumption that an agent has a strict ordering of preferences
(or payoffs). This assumption is therefore not valid when there are ties
(i.e., indifference) in an agent’s preferences (or payoffs).

Let $T(\mathcal{E})=\sum_{t=1}^{T}\mathbf{1}(\mathcal{E}\text{ occurs at time
step }t)$ denote the number of times event $\mathcal{E}$ occurs over all $T$
time steps.

######  Lemma A.1.

Consider an agent faced with $K$ arms, as in the standard multi-armed bandit
(MAB) problem. Let $T\in\mathbb{N}_{>0}$ be the time horizon. Suppose that, at
each time step $t\in[T]$, the agent is either: (1) matched with arm $I_{t}$,
in which case it receives reward $Y_{I_{t},t}$; or (2) unmatched, in which
case it receives no reward. Suppose $Y_{i,t}$ is drawn i.i.d. from a sub-
Gaussian distribution with parameter $\sigma^{2}$ for all $i\in[K]$. Let
$m(i)=\mathbb{E}[Y_{i,0}]$, $m^{*}=\max_{i\in[K]}m(i)$, and
$T_{t}(i)=\sum_{\tau=1}^{t}\mathbf{1}(I_{\tau}=i)$. Let

$\displaystyle
v_{t}(i)=\frac{1}{T_{t-1}(i)}\sum_{t=1}^{T}Y_{i,t}\mathbf{1}(I_{t}=i)+\sqrt{\frac{2\sigma^{2}\alpha\log(t)}{T_{t-1}(i)}},$

be the agent’s upper confidence bound (UCB) for all arms $i\in[K]$, where
$\alpha>2$. Then,

$\displaystyle\mathbb{E}[T(I_{t}=i\cap v_{t}(i)\geq v_{t}(j)\cap m(i)<m(j))]$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}\mathbf{1}(I_{t}=i\cap
v_{t}(i)\geq v_{t}(j)\cap m(i)<m(j))\right]$
$\displaystyle\leq\frac{8\sigma^{2}\alpha\log(T)}{(m(j)-m(i))^{2}}+\frac{\alpha}{\alpha-2},$

for all $i,j\in[K]$ and $i\neq j$, where the expectation is taken with respect
to the randomness of rewards $Y_{I_{t},t}$.

###### Proof.

This proof is adapted from the proof that upper bounds regret in the MAB
problem under the UCB strategy, cf. Theorem 2.1 presented by Bubeck and Cesa-
Bianchi (2012).

Let
$\hat{m}_{t}(i)=\frac{1}{T_{t-1}(i)}\sum_{\tau=1}^{t}Y_{i,\tau}\mathbf{1}(I_{\tau}=i)$,
$\Delta(i,j)=|m(i)-m(j)|$, and
$\Psi^{*}(\epsilon):=\frac{\epsilon^{2}}{2\sigma^{2}}$. If $I_{t}=i$,
$v_{t}(i)\geq v_{t}(j)$, and $m(i)<m(j)$, then at least one of the following
must be true:

$\displaystyle\hat{m}_{t}(j)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(j)}\right)\leq
m(j),$ (10)
$\displaystyle\hat{m}_{t}(i)>m(i)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(i)}\right),$
(11) $\displaystyle T_{t-1}(i)<\frac{\alpha\log(t)}{\Psi^{*}(\Delta(i,j)/2)}.$
(12)

To confirm that one of the prior statements must be true, suppose that all
three statement are false. Then,

$\displaystyle v_{t}(j)$
$\displaystyle=\hat{m}_{t}(j)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(j)}\right)$
(13) $\displaystyle>m(j)$ (14) $\displaystyle=m(i)+\Delta(i,j)$ (15)
$\displaystyle\geq
m(i)+2(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(i)}\right)$ (16)
$\displaystyle\geq\hat{m}_{t}(i)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(i)}\right)$
(17) $\displaystyle=v_{t}(i),$ (18)

where (13) and (18) follow from the definition of $v_{t}$; (14) follows from
the assumption that (10) is false; (15) follows from the definition of
$\Delta(i,j)$ and that $m(j)>m(i)$; (16) follows from the assumption that (12)
is false; and (17) follows from the assumption that (11) is false. However,
(18) implies that $v_{t}(j)>v_{t}(i)$, which cannot be true by assumption.

Therefore, we have a contradiction, which implies that, if $I_{t}=i$,
$v_{t}(i)\geq v_{t}(j)$, and $m(i)<m(j)$, then at least one of the statements
(10)-(12) must be true. Let
$\bar{T}_{ij}=\lceil\frac{\alpha\log(T)}{\Psi^{*}(\Delta(i,j)/2)}\rceil$.
Then,

$\displaystyle\mathbb{E}[T(I_{t}=i\cap v_{t}(i)\geq v_{t}(j)\cap m(i)<m(j))]$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}\mathbf{1}(I_{t}=i\cap
v_{t}(i)\geq v_{t}(j)\cap m(i)<m(j))\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{t=1}^{T}\mathbf{1}\left(I_{t}=i\cap
T_{t-1}(i)<\frac{\alpha\log(t)}{\Psi^{*}(\Delta(i,j)/2)}\right)\right]$
$\displaystyle\qquad+\mathbb{E}\left[\sum_{t=\bar{T}_{ij}+1}^{T}\mathbf{1}\left(\hat{m}_{t}(j)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(j)}\right)\leq
m(j)\cup\hat{m}_{t}(i)>m(i)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(i)}\right)\right)\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{t=1}^{T}\mathbf{1}\left(I_{t}=i\cap
T_{t-1}(i)<\frac{\alpha\log(T)}{\Psi^{*}(\Delta(i,j)/2)}\right)\right]$
$\displaystyle\qquad+\mathbb{E}\left[\sum_{t=\bar{T}_{ij}+1}^{T}\mathbf{1}\left(\hat{m}_{t}(j)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(j)}\right)\leq
m(j)\cup\hat{m}_{t}(i)>m(i)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(i)}\right)\right)\right]$
$\displaystyle\leq\bar{T}_{ij}+\mathbb{E}\left[\sum_{t=\bar{T}_{ij}+1}^{T}\mathbf{1}\left(\hat{m}_{t}(j)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(j)}\right)\leq
m(j)\cup\hat{m}_{t}(i)>m(i)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(i)}\right)\right)\right]$
$\displaystyle\leq\bar{T}_{ij}+\sum_{t=\bar{T}_{ij}+1}^{T}\left[\mathbb{P}\left(\hat{m}_{t}(j)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(j)}\right)\leq
m(j)\right)+\mathbb{P}\left(\hat{m}_{t}(i)>m(i)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(i)}\right)\right)\right].$
(19)

It remains to bound the probabilities on the right-hand side in (19).
Beginning with the left term under the sum in (19):

$\displaystyle\mathbb{P}$
$\displaystyle\left(\hat{m}_{t}(j)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(j)}\right)\leq
m(j)\right)$
$\displaystyle\leq\mathbb{P}\left(\exists\tau\in\\{1,\ldots,t\\}:T_{t-1}(j)=\tau\cap\hat{m}_{t}(j)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{\tau}\right)\leq
m(j)\right)$
$\displaystyle\leq\sum_{\tau=1}^{t}\mathbb{P}\left(T_{t-1}(j)=\tau\cap\hat{m}_{t}(j)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{\tau}\right)\leq
m(j)\right)$ $\displaystyle\leq\sum_{\tau=1}^{t}\frac{1}{t^{\alpha}}$
$\displaystyle=\frac{1}{t^{\alpha-1}},$

where the second-to-last line follows from the concentration properties of
sub-Gaussian random variables (Vershynin, 2018). Incorporating the sum in
(19),

$\displaystyle\sum_{t=\bar{T}_{ij}+1}^{T}\mathbb{P}\left(\hat{m}_{t}(j)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(j)}\right)\leq
m(j)\right)$
$\displaystyle\leq\sum_{t=\bar{T}_{ij}+1}^{T}\frac{1}{t^{\alpha-1}}$
$\displaystyle\leq\sum_{t=\bar{T}_{ij}+1}^{\infty}\frac{1}{t^{\alpha-1}}$
$\displaystyle\leq\sum_{t=2}^{\infty}\frac{1}{t^{\alpha-1}}$
$\displaystyle\leq\int_{1}^{\infty}\frac{1}{t^{\alpha-1}}dt$
$\displaystyle=\frac{1}{\alpha-2}.$ (20)

Using a symmetric analysis, the right term under the sum in (19) can be upper
bounded by the same quantity, such that

$\displaystyle\sum_{t=\bar{T}_{ij}+1}^{T}\mathbb{P}\left(\hat{m}_{t}(i)>m(i)+(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(i)}\right)\right)$
$\displaystyle\leq\frac{1}{\alpha-2}.$ (21)

Combining with (20) and (21) with (19):

$\displaystyle\mathbb{E}[T(I_{t}=i\cap v_{t}(i)\geq v_{t}(j)\cap m(i)<m(j))]$
$\displaystyle\leq\bar{T}_{ij}+\frac{2}{\alpha-2}$
$\displaystyle\leq\frac{\alpha\log(T)}{\Psi^{*}(\Delta(i,j)/2)}+1+\frac{2}{\alpha-2}$
$\displaystyle\leq\frac{\alpha\log(T)}{\Psi^{*}(\Delta(i,j)/2)}+\frac{\alpha}{\alpha-2},$

which, after substituting in for the definition of $\Psi^{*}$, gives the
result as stated in the lemma.

To connect this proof to Theorem 2.1 presented by Bubeck and Cesa-Bianchi
(2012), note that $\Psi^{*}$ is the Legendre transform (convex-conjugate) of
$Y-\mathbb{E}[Y]$, where $Y$ is a sub-Gaussian random variable with parameter
$\sigma^{2}$ and that

$\displaystyle(\Psi^{*})^{-1}\left(\frac{\alpha\log(t)}{T_{t-1}(i)}\right)$
$\displaystyle=\sqrt{\frac{2\sigma^{2}\alpha\log(t)}{T_{t-1}(i)}},$

is the additive term in the UCB formula. ∎

######  Lemma A.2.

Consider the setup described in Section 3.1. Let
$\psi,\psi^{\prime}:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$. If
$\mathcal{M}(\cdot;\psi^{\prime})\in S(V(\cdot,\cdot;\psi^{\prime}))$ and
$\mathcal{M}(\cdot;\psi^{\prime})\notin S(V(\cdot,\cdot;\psi))$, then there
exists $a_{1},a_{2},a_{3},a_{4}\in\mathcal{A}$ such that
$\mathcal{M}(a_{1};\psi^{\prime})=a_{2}$ and
$\mathcal{M}(a_{3};\psi^{\prime})=a_{4}$, but
$V(a_{1},a_{4};\psi)>V(a_{1},a_{2};\psi)$ and
$V(a_{4},a_{1};\psi)>V(a_{4},a_{3};\psi)$ and either
$V(a_{1},a_{4};\psi^{\prime})\leq V(a_{1},a_{2};\psi^{\prime})$ or
$V(a_{4},a_{1};\psi^{\prime})\leq V(a_{4},a_{3};\psi^{\prime})$.

###### Proof.

If $\mathcal{M}(\cdot;\psi^{\prime})\notin S(V(\cdot,\cdot;\psi))$, then there
exists $a_{1},a_{2}\in\mathcal{A}$ such that
$\mathcal{M}(a_{1};\psi^{\prime})=a_{2}$ but $(a_{1},a_{2})$ is not stable
under payoffs $V(\cdot,\cdot;\psi)$. The latter implies that there exists
$a_{3},a_{4}\in\mathcal{A}$ such that $\mathcal{M}(a_{3};\psi^{\prime})=a_{4}$
and $V(a_{1},a_{4};\psi)>V(a_{1},a_{2};\psi)$ and
$V(a_{4},a_{1};\psi)>V(a_{4},a_{3};\psi)$. However, because the matches
$(a_{1},a_{2})$ and $(a_{3},a_{4})$ are stable under
$V(\cdot,\cdot;\psi^{\prime})$, either $V(a_{1},a_{4};\psi^{\prime})\leq
V(a_{1},a_{2};\psi^{\prime})$ or $V(a_{4},a_{1};\psi^{\prime})\leq
V(a_{4},a_{3};\psi^{\prime})$. ∎

######  Lemma A.3.

Consider the setup described in Section 3.1. Let
$\Delta_{\min}=\min_{a_{1}\in\mathcal{A},a_{2}\in\mathcal{A}^{+},a_{3}\in\mathcal{A}^{+}\setminus
a_{2}}|\mu(a_{1},a_{2})-\mu(a_{1},a_{3})|$. Suppose there is no cost and no
transfer such that $\mathcal{C}=\mathcal{T}=0$. Then,

$\displaystyle\mathbb{E}T(\mathcal{M}(\cdot;\nu_{t})\notin
S(V(\cdot,\cdot,;\mu)))=\mathbb{E}T(\mathcal{M}(\cdot;\nu_{t})\notin S(\mu))$
$\displaystyle\leq
2N^{2}L\left(\frac{8\sigma^{2}\alpha\log(T)}{\Delta_{\min}^{2}}+\frac{\alpha}{\alpha-2}\right).$

###### Proof.

Under no cost and no transfer, $V(\cdot,\cdot;\mu)=\mu(\cdot,\cdot)$ and
$V(\cdot,\cdot;\nu_{t})=\nu_{t}(\cdot,\cdot)$. Recall that, by construction,
$\mathcal{M}(\cdot;\nu_{t})\in S(V(\cdot,\cdot;\nu_{t}))=S(\nu_{t})$. If,
additionally, $\mathcal{M}(\cdot;\nu_{t})\notin S(V(\cdot,\cdot;\mu))=S(\mu)$,
then, by Lemma A.2, there exists $a_{1},a_{2},a_{3},a_{4}\in\mathcal{A}$ such
that $\mathcal{M}(a_{1};\nu_{t})=a_{2}$, $\mathcal{M}(a_{3};\nu_{t})=a_{4}$,
$\mu(a_{1},a_{4})>\mu(a_{1},a_{2})$, and $\mu(a_{4},a_{1})>\mu(a_{4},a_{3})$
and either $\nu_{t}(a_{1},a_{4})\leq\nu_{t}(a_{1},a_{2})$ or
$\nu_{t}(a_{4},a_{1})\leq\nu_{t}(a_{4},a_{3})$. As such,

$\displaystyle\mathbb{E}T(\mathcal{M}(\cdot;\nu_{t})$ $\displaystyle\notin
S(\mu))$ $\displaystyle\leq\mathbb{E}T(\exists
a_{1},a_{2},a_{3},a_{4}\in\mathcal{A}:\mathcal{M}(a_{1};\nu_{t})=a_{2}\cap\mathcal{M}(a_{3};\nu_{t})=a_{4}$
$\displaystyle\qquad\cap\mu(a_{1},a_{4})>\mu(a_{1},a_{2})$
$\displaystyle\qquad\cap\mu(a_{4},a_{1})>\mu(a_{4},a_{3})$
$\displaystyle\qquad\cap(\nu_{t}(a_{1},a_{4})\leq\nu_{t}(a_{1},a_{2})\cup\nu_{t}(a_{4},a_{1})\leq\nu_{t}(a_{4},a_{3}))$
$\displaystyle\leq\mathbb{E}T(\exists
a_{1},a_{2},a_{3},a_{4}\in\mathcal{A}:\mathcal{M}(a_{1};\nu_{t})=a_{2}\cap\mathcal{M}(a_{3};\nu_{t})=a_{4}$
$\displaystyle\qquad\qquad\cap\mu(a_{1},a_{4})>\mu(a_{1},a_{2})$
$\displaystyle\qquad\qquad\cap\mu(a_{4},a_{1})>\mu(a_{4},a_{3})$
$\displaystyle\qquad\qquad\cap\nu_{t}(a_{1},a_{4})\leq\nu_{t}(a_{1},a_{2}))$
$\displaystyle\qquad+\mathbb{E}T(\exists
a_{1},a_{2},a_{3},a_{4}\in\mathcal{A}:\mathcal{M}(a_{1};\nu_{t})=a_{2}\cap\mathcal{M}(a_{3};\nu_{t})=a_{4}$
$\displaystyle\qquad\qquad\cap\mu(a_{1},a_{4})>\mu(a_{1},a_{2})$
$\displaystyle\qquad\qquad\cap\mu(a_{4},a_{1})>\mu(a_{4},a_{3})$
$\displaystyle\qquad\qquad\cap\nu_{t}(a_{4},a_{1})\leq\nu_{t}(a_{4},a_{3}))$
$\displaystyle\leq\mathbb{E}T(\exists
a_{1},a_{2},a_{4}:\mathcal{M}(a_{1};\nu_{t})=a_{2}\cap\mu(a_{1},a_{4})>\mu(a_{1},a_{2})\cap\nu_{t}(a_{1},a_{4})\leq\nu_{t}(a_{1},a_{2}))$
$\displaystyle\qquad+\mathbb{E}T(\exists
a_{1},a_{3},a_{4}:\mathcal{M}(a_{3};\nu_{t})=a_{4}\cap\mu(a_{4},a_{1})>\mu(a_{4},a_{3})\cap\nu_{t}(a_{4},a_{1})\leq\nu_{t}(a_{4},a_{3}))$
$\displaystyle=2\mathbb{E}T(\exists
a_{1},a_{2},a_{3}:\mathcal{M}(a_{1};\nu_{t})=a_{2}\cap\mu(a_{1},a_{3})>\mu(a_{1},a_{2})\cap\nu_{t}(a_{1},a_{3})\leq\nu_{t}(a_{1},a_{2})).$

Then,

$\displaystyle\mathbb{E}T(\mathcal{M}(\cdot;\nu_{t})$ $\displaystyle\notin
S(\mu))$ $\displaystyle\leq 2\mathbb{E}T(\exists
a_{1},a_{2},a_{3}:\mathcal{M}(a_{1};\nu_{t})=a_{2}\cap\mu(a_{1},a_{3})>\mu(a_{1},a_{2})\cap\nu_{t}(a_{1},a_{3})\leq\nu_{t}(a_{1},a_{2}))$
$\displaystyle\leq
2\sum_{a_{1},a_{2},a_{3}\in\mathcal{A}}\mathbb{E}T(\mathcal{M}(a_{1};\nu_{t})=a_{2}\cap\mu(a_{1},a_{3})>\mu(a_{1},a_{2})\cap\nu_{t}(a_{1},a_{3})\leq\nu_{t}(a_{1},a_{2}))$
$\displaystyle\leq
2N^{2}L\left(\frac{8\sigma^{2}\alpha\log(T)}{\Delta_{\min}^{2}}+\frac{\alpha}{\alpha-2}\right),$

where the last line follows from Lemma A.1 since, from the perspective of
agent $a_{1}$, being matched with $a_{2}$ is identical to $a_{1}$ sampling arm
$a_{2}$ in the MAB problem. ∎

##  Appendix B Proofs for incentive compatibility results (Section 4.1)

######  Lemma 1.

Let $\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ denote an
arbitrary preference function. Let $\mathcal{M}(\cdot;\psi)$ denote a matching
returned by the GS algorithm, as given in Algorithm 1, when applied over
payoffs $V(\cdot,\cdot;\psi)$. Then, $\mathcal{M}(\cdot;\psi)$ is a stable
matching under payoffs $V(\cdot,\cdot;\psi)$: i.e.,
$\mathcal{M}(\cdot;\psi)\in S(V(\cdot,\cdot;\psi))$.

###### Proof.

This is a well-known result, cf. Gale and Shapley (1962) or Roth (2008). To
prove it, consider Algorithm 1. Suppose that the result is not true, in which
case there exists a $p_{1}\in\mathcal{P}$, $p_{2}\in\mathcal{P}\cup\emptyset$,
and $u_{1},u_{2}\in\mathcal{U}$ such that $\mathcal{M}(u_{1};\psi)=p_{1}$ and
$\mathcal{M}(u_{2};\psi)=p_{2}$, but $u_{2}\succ_{V(p_{1},\cdot;\psi)}u_{1}$
and $p_{1}\succ_{V(u_{2},\cdot;\psi)}p_{2}$ by the definition of stability
(see Section 3.2).

$u_{2}\succ_{V(p_{1},\cdot;\psi)}u_{1}$ implies that $p_{1}$ proposes to
$u_{2}$ before proposing to $u_{1}$. However, since
$p_{1}\succ_{V(u_{2},\cdot;\psi)}p_{2}$, it is not possible that (a) $u_{2}$
rejects $p_{1}$ in favor of $p_{2}$ or (b) $u_{2}$ rejects $p_{1}$ in favor of
$p_{3}\in\mathcal{P}\setminus\\{p_{1},p_{2}\\}$ but that $u_{2}$ does not
reject $p_{2}$ in favor of $p_{3}$. Therefore, we have a contradiction,
implying that the GS algorithm returns a stable matching. ∎

######  Lemma 2.

Consider the setup in Section 3.1. Suppose that, at every time step $t\in[T]$,
$\mathcal{M}(\cdot;\nu_{t})$ is a matching returned by the GS algorithm when
applied over payoffs $V(\cdot,\cdot;\nu_{t})$. Then,
$(\mathcal{M},\mathcal{C},\mathcal{T})$ is guaranteed to be incentive-
compatible.

###### Proof.

This result follows from Lemma 1 and Definition 1. ∎

In the remaining analysis, we will also make use of the following definition
and lemma.

######  Definition B.1.

A stable matching $M\in S(V)$ is _$\mathcal{G}$ -optimal_ under payoffs
$V:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ if $V(a,M(a))\geq
V(a,M^{\prime}(a))$ for all $M^{\prime}\in S(V)$ and $a\in\mathcal{G}$. A
stable matching $M\in S(V)$ is _$\mathcal{G}$ -pessimal_ under payoffs
$V:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ if $V(a,M(a))\leq
V(a,M^{\prime}(a))$ for all $M^{\prime}\in S(V)$ and $a\in\mathcal{G}$.

######  Lemma B.4.

Suppose that the GS algorithm is performed over payoffs
$V:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ and with
$\mathcal{G}$ as proposers. Suppose further that $a^{\prime}\neq
a^{\prime\prime}\implies V(a,a^{\prime})\neq V(a,a^{\prime\prime})$ for all
$a\in\mathcal{A}$. Then, if the matching $M$ is returned by the GS algorithm,
$M\in S(V)$ is $\mathcal{G}$-optimal and
$(\mathcal{A}\setminus\mathcal{G})$-pessimal.

###### Proof.

This result is well-known, cf. Theorem 3 given by Roth (2008). ∎

##  Appendix C Proofs for no-cost, no-transfer setting (Section 4.2)

Recall that

$\displaystyle\Delta_{\max}(a)$
$\displaystyle=\max_{a_{1},a_{2}\in\mathcal{A}^{+}}(\mu(a,a_{1}),-\mu(a,a_{2}))$
$\displaystyle\Delta_{\min}$
$\displaystyle=\min_{a_{1}\in\mathcal{A},a_{2}\in\mathcal{A}^{+},a_{3}\in\mathcal{A}^{+}\setminus
a_{2}}|\mu(a_{1},a_{2})-\mu(a_{1},a_{3})|.$

######  Proposition 3.

Consider the setup described in Section 3.1 with no costs or transfers, as
stated in (2)-(3). Then, if the GS algorithm is applied over
$V(\cdot,\cdot;\nu_{t})$ at every time step $t\in[T]$, the system is
incentive-compatible. Moreover,

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})$ $\displaystyle\leq
2N^{2}L\Delta_{\max}(a)\left(\frac{8\sigma^{2}\alpha\log(T)}{\Delta_{\min}^{2}}+\frac{\alpha}{\alpha-2}\right),$

for all $a\in\mathcal{A}$. However, under incentive compatibility, it is not
possible to guarantee fairness or that social welfare is high at every
$t\in[T]$, and there exist settings $(\mathcal{A},\mu)$ for which
$\bar{R}(a;\mathcal{M})=\Omega(T)$ for at least one agent $a\in\mathcal{A}$.

###### Proof.

By Lemma 2, the system is incentive-compatible since the GS algorithm is
applied at each time step. Next, we perform the regret analysis.

Logarithmic pessimal regret. Recall that $\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.04333pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.31667pt{}}}$\hss}}}M_{t}^{a}\in\arg\min_{M\in
S(V(\cdot,\cdot;\mu))}\mathbb{E}\left[U_{t}(a,M(a);\nu_{t})\right]$. Under no
cost or transfer, $\mathbb{E}[U_{t}(a,a^{\prime};\nu_{t})]=\mu(a,a^{\prime})$
and $V(\cdot;\cdot;\mu)=\mu(\cdot,\cdot)$. As such, $\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.04333pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.31667pt{}}}$\hss}}}M_{t}^{a}\in\arg\min_{M\in
S(\mu)}\mu(a,M(a))$, and the pessimal regret is

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}\left(X_{t}(a,\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.04333pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M^{a}_{t}(a))-X_{t}(a,\mathcal{M}(a;\nu_{t}))\right)\right]$
$\displaystyle=\sum_{t=1}^{T}\mu(a,\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.04333pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M^{a}_{t}(a))-\mu(a,\mathcal{M}(a;\nu_{t}))$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}(\mathcal{M}(\cdot;\nu_{t})\in
S(\mu))\left(\mu(a,\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.04333pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M^{a}_{t}(a))-\mu(a,\mathcal{M}(a;\nu_{t}))\right)$
$\displaystyle\qquad+\sum_{t=1}^{T}\mathbf{1}(\mathcal{M}(\cdot;\nu_{t})\notin
S(\mu))\left(\mu(a,\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.04333pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M^{a}_{t}(a))-\mu(a,\mathcal{M}(a;\nu_{t}))\right)$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}(\mathcal{M}(\cdot;\nu_{t})\notin
S(\mu))\left(\mu(a,\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.04333pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M^{a}_{t}(a))-\mu(a,\mathcal{M}(a;\nu_{t}))\right),$

where the last line follows from the definition of $\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.04333pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.31667pt{}}}$\hss}}}M_{t}^{a}$. Converting the
sum over time steps to a sum over possible matches:

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}(\mathcal{M}(\cdot;\nu_{t})\notin
S(\mu))\left(\mu(a,\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.04333pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M^{a}_{t}(a))-\mu(a,\mathcal{M}(a;\nu_{t}))\right)$
$\displaystyle=\sum_{M^{\prime}\notin
S(\mu)}T(\mathcal{M}(\cdot;\nu_{t})=M)\left(\mu(a,\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.04333pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M^{a}_{t}(a))-\mu(a,M(a;\nu_{t}))\right).$

Note that, in this setting, $\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to8.63335pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.04333pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M^{a}_{t}(a)$ does not depend on $t$ because
$\mathchoice{\hbox to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.04333pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.31667pt{}}}$\hss}}}M_{t}^{a}\in\arg\min_{M\in
S(\mu)}\mu(a,M(a))$. Let $\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.6667pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.6667pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.66669pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.33334pt{}}}$\hss}}}\Delta(a,a^{\prime})=\mu(a,\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to8.63335pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.04333pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox
to4.31667pt{}}}$\hss}}}M^{a}_{t}(a))-\mu(a,a^{\prime})$. Then,

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})$
$\displaystyle\leq\sum_{M^{\prime}\notin
S(\mu)}T(\mathcal{M}(\cdot;\nu_{t})=M)\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to6.6667pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.6667pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.66669pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to3.33334pt{}}}$\hss}}}\Delta(a,M(a))$
$\displaystyle\leq\max_{a^{\prime}\in\mathcal{A}^{+}}\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to6.6667pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.6667pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.66669pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox
to3.33334pt{}}}$\hss}}}\Delta(a,a^{\prime})T(\mathcal{M}(\cdot;\nu_{t})\notin
S(\mu)).$

Then, applying Lemma A.3:

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R(a;\mathcal{M})$
$\displaystyle\leq\max_{a^{\prime}\in\mathcal{A}}\mathchoice{\hbox
to0.0pt{{$\underline{{\hbox to6.6667pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to6.6667pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox to4.66669pt{}}}$\hss}}}{\hbox
to0.0pt{{$\underline{{\hbox
to3.33334pt{}}}$\hss}}}\Delta(a,a^{\prime})T(\mathcal{M}(\cdot;\nu_{t})\notin
S(\mu))$ $\displaystyle\leq
2N^{2}L\Delta_{\max}(a)\left(\frac{8\sigma^{2}\alpha\log(T)}{\Delta_{\min}^{2}}+\frac{\alpha}{\alpha-2}\right).$

Linear optimal regret. Recall that $\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern 4.5mu^{a}_{t}\in\arg\max_{M\in
S(V(\cdot,\cdot;\mu))}\mathbb{E}\left[U_{t}(a,M(a);\nu_{t})\right]$. In the
no-cost, no-transfer setting, $\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern 4.5mu_{t}^{a}\in\arg\max_{M\in
S(\mu)}\mu(a,M(a)))$ such that

$\displaystyle\bar{R}(a;\mathcal{M})$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}\left(X_{t}(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{a}_{t}(a))-X_{t}(a,\mathcal{M}(a;\nu_{t}))\right)\right]$
$\displaystyle=\sum_{t=1}^{T}\mu(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{a}_{t}(a))-\mu(a,\mathcal{M}(a;\nu_{t}))$ $\displaystyle\leq
T\Delta_{\max}(a).$ (22)

Since $a^{\prime}\neq
a^{\prime\prime}\implies\mu(a,a^{\prime})\neq\mu(a,a^{\prime\prime})$ for all
$a\in\mathcal{A}$, $\Delta_{\max}(a)>0$, which implies that
$\bar{R}(a;\mathcal{M})=O(T)$ for all agents $a\in\mathcal{A}$. In other
words, the optimal regret of any agent can be upper bounded by a function that
grows linearly in $T$. To show that this upper bound is tight, we now
construct an example in which at least one agent $a\in\mathcal{A}$ experiences
regret that grows $\Omega(T)$, i.e., the optimal regret of at least one agent
$a$ can be lower bounded by a function that grows linearly in $T$ such that
$\bar{R}(a;\mathcal{M})=\Omega(T)$.

Suppose $\mathcal{U}=\\{u_{1},u_{2},u_{3}\\}$,
$\mathcal{P}=\\{p_{1},p_{2},p_{3}\\}$, and

$\displaystyle
u_{1}\succ_{\mu(p_{1},\cdot)}u_{2}\succ_{\mu(p_{1},\cdot)}u_{3},$
$\displaystyle\qquad\qquad
p_{3}\succ_{\mu(u_{1},\cdot)}p_{2}\succ_{\mu(u_{1},\cdot)}p_{1},$
$\displaystyle
u_{1}\succ_{\mu(p_{2},\cdot)}u_{2}\succ_{\mu(p_{2},\cdot)}u_{3},$
$\displaystyle\qquad\qquad
p_{3}\succ_{\mu(u_{2},\cdot)}p_{1}\succ_{\mu(u_{2},\cdot)}p_{2},$
$\displaystyle
u_{3}\succ_{\mu(p_{3},\cdot)}u_{2}\succ_{\mu(p_{3},\cdot)}u_{1},$
$\displaystyle\qquad\qquad
p_{1}\succ_{\mu(u_{3},\cdot)}p_{2}\succ_{\mu(u_{3},\cdot)}p_{3}.$

Then, the only two stable matchings under $V(\cdot,\cdot;\mu)$ are

$\displaystyle M_{1}(a)$ $\displaystyle=\begin{cases}p_{2},&a=u_{1},\\\
p_{1},&a=u_{2},\\\ p_{3},&a=u_{3},\\\ u_{2},&a=p_{1},\\\ u_{1},&a=p_{2},\\\
u_{3},&a=p_{3}.\end{cases}\qquad\qquad\qquad
M_{2}(a)~{}=~{}\begin{cases}p_{2},&a=u_{1},\\\ p_{3},&a=u_{2},\\\
p_{1},&a=u_{3},\\\ u_{3},&a=p_{1},\\\ u_{1},&a=p_{2},\\\
u_{2},&a=p_{3}.\end{cases}$

As such, $\mkern 4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{u_{1}}_{t}\in\\{M_{1},M_{2}\\}$, $\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern 4.5mu^{u_{2}}_{t}=M_{2}$,
$\mkern 4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{u_{3}}_{t}=M_{2}$, $\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern 4.5mu^{p_{1}}_{t}=M_{1}$,
$\mkern 4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{p_{2}}_{t}\in\\{M_{1},M_{2}\\}$, and $\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern 4.5mu^{p_{3}}_{t}=M_{1}$. The
optimal regret of $p_{1}$ and $u_{2}$ can be lower bounded as follows.

$\displaystyle\bar{R}(a;\mathcal{M})$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}\left(X_{t}(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{a}_{t}(a))-X_{t}(a,\mathcal{M}(a;\nu_{t}))\right)\right]$
$\displaystyle=\sum_{t=1}^{T}\mu(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{a}_{t}(a))-\mu(a,\mathcal{M}(a;\nu_{t}))$ $\displaystyle\geq
T(\mathcal{M}(a;\nu_{t})=M_{1})(\mu(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{a}_{t}(a))-\mu(a,M_{1}(a)))$
$\displaystyle\qquad+T(\mathcal{M}(a;\nu_{t})=M_{2})(\mu(a,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{a}_{t}(a))-\mu(a,M_{2}(a))),$ (23)

which implies that

$\displaystyle\bar{R}(p_{1};\mathcal{M})$ $\displaystyle\geq
T(\mathcal{M}(\cdot;\nu_{t})=M_{1})(\mu(p_{1},\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{p_{1}}_{t}(p_{1}))-\mu(p_{1},M_{1}(p_{1})))$
$\displaystyle\qquad+T(\mathcal{M}(\cdot;\nu_{t})=M_{2})(\mu(p_{1},\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{p_{1}}_{t}(p_{1}))-\mu(p_{1},M_{2}(p_{1})))$
$\displaystyle=T(\mathcal{M}(\cdot;\nu_{t})=M_{1})(\mu(p_{1},M_{1}(p_{1}))-\mu(p_{1},M_{1}(p_{1})))$
$\displaystyle\qquad+T(\mathcal{M}(\cdot;\nu_{t})=M_{2})(\mu(p_{1},M_{1}(p_{1}))-\mu(p_{1},M_{2}(p_{1})))$
$\displaystyle=T(\mathcal{M}(\cdot;\nu_{t})=M_{2})(\mu(p_{1},M_{1}(p_{1}))-\mu(p_{1},M_{2}(p_{1})))$
$\displaystyle=T(\mathcal{M}(\cdot;\nu_{t})=M_{2})(\mu(p_{1},u_{2})-\mu(p_{1},u_{3})).$
(24)

Recall that $\mu(p_{1},u_{2})-\mu(p_{1},u_{3})>0$. Therefore, the optimal
regret for $p_{1}$ grows linearly in $T$ if
$T(\mathcal{M}(\cdot;\nu_{t})=M_{2})$ grows linearly in $T$. Similarly,
applying (23) to agent $u_{2}$ gives

$\displaystyle\bar{R}(u_{2};\mathcal{M})$ $\displaystyle\geq
T(\mathcal{M}(\cdot;\nu_{t})=M_{1})(\mu(u_{2},\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{u_{2}}_{t}(u_{2}))-\mu(u_{2},M_{1}(u_{2})))$
$\displaystyle\qquad+T(\mathcal{M}(\cdot;\nu_{t})=M_{2})(\mu(u_{2},\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{u_{2}}_{t}(u_{2}))-\mu(u_{2},M_{2}(u_{2})))$
$\displaystyle=T(\mathcal{M}(\cdot;\nu_{t})=M_{1})(\mu(u_{2},M_{2}(u_{2}))-\mu(u_{2},M_{1}(u_{2})))$
$\displaystyle\qquad+T(\mathcal{M}(\cdot;\nu_{t})=M_{2})(\mu(u_{2},M_{2}(u_{2}))-\mu(u_{2},M_{2}(u_{2})))$
$\displaystyle=T(\mathcal{M}(\cdot;\nu_{t})=M_{1})(\mu(u_{2},M_{2}(u_{2}))-\mu(u_{2},M_{1}(u_{2})))$
$\displaystyle=T(\mathcal{M}(\cdot;\nu_{t})=M_{1})(\mu(u_{2},p_{3})-\mu(u_{2},p_{1}))).$
(25)

Recall that $\mu(u_{2},p_{3})-\mu(u_{2},p_{1})>0$. Therefore, the optimal
regret for $u_{2}$ grows linearly in $T$ if
$T(\mathcal{M}(\cdot;\nu_{t})=M_{1})$ grows linearly in $T$.

We now show that either $T(\mathcal{M}(\cdot;\nu_{t})=M_{1})$ or
$T(\mathcal{M}(\cdot;\nu_{t})=M_{2})$ grows linearly in $T$, or both do.

$\displaystyle T$
$\displaystyle=\sum_{M\in\mathcal{W}}T(\mathcal{M}(\cdot;\nu_{t})=M)$
$\displaystyle=\sum_{M\in S(\mu)}T(\mathcal{M}(\cdot;\nu_{t})=M)+\sum_{M\notin
S(\mu)}T(\mathcal{M}(\cdot;\nu_{t})=M),$ $\displaystyle\implies\sum_{M\in
S(\mu)}T(\mathcal{M}(\cdot;\nu_{t})=M)$ $\displaystyle=T-\sum_{M\notin
S(\mu)}T(\mathcal{M}(\cdot;\nu_{t})=M)$
$\displaystyle=T-T(\mathcal{M}(\cdot;\nu_{t})\notin S(\mu))$
$\displaystyle\geq
T-2N^{2}L\left(\frac{8\sigma^{2}\alpha\log(T)}{\Delta_{\min}^{2}}+\frac{\alpha}{\alpha-2}\right)$

which implies that
$T(\mathcal{M}(\cdot;\nu_{t})=M_{1})+T(\mathcal{M}(\cdot;\nu_{t})=M_{2})=\Omega(T)$.
Since $T(\mathcal{E})\geq 0$ and $T>0$, it is not possible that
$T(\mathcal{M}(\cdot;\nu_{t})=M_{1})$ and
$T(\mathcal{M}(\cdot;\nu_{t})=M_{2})$ both grow sub-linearly in $T$.
Therefore, $T(\mathcal{M}(\cdot;\nu_{t})=M_{1})=\Omega(T)$,
$T(\mathcal{M}(\cdot;\nu_{t})=M_{2})=\Omega(T)$, or both. By (24) and (25),
the optimal regret of at least one agent grows $\Omega(T)$.

Intuitively, since it is impossible for the matching at a given time step to
simultaneously be both $M_{1}$ and $M_{2}$, at least one agent must incur a
non-zero optimal regret for $\Omega(T)$ time steps.

Fairness not guaranteed. To show that fairness is not guaranteed, it suffices
to show the existence of an example in which the matchings are unfair. That
fairness is not guaranteed follows directly from the example under “Linear
optimal regret” above. In particular, we use the same example and show that it
is possible for at least one agent’s optimal regret to grow $O(\log(T))$ while
another agent’s regret grows $\Omega(T)$.

Suppose $T(\mathcal{M}(\cdot;\nu_{t})=M_{2})=O(\log(T))$ such that
$T(\mathcal{M}(\cdot;\nu_{t})=M_{1})=\Omega(T)$. (This is possible under
Algorithm 1, which returns matchings $\mathcal{M}(\cdot;\nu_{t})$ that are
$\mathcal{P}$-optimal at every time step by Lemma B.4.) As such, for all
$p\in\mathcal{P}$,

$\displaystyle\bar{R}(p;\mathcal{M})$
$\displaystyle=\sum_{t=1}^{T}\mu(p,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{p}_{t}(p))-\mu(p,\mathcal{M}(p;\nu_{t}))$ $\displaystyle=(\mu(p,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{p}_{t}(p))-\mu(p,M_{1}(p)))T(\mathcal{M}(\cdot;\nu_{t})=M_{1})+(\mu(p,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{p}_{t}(p))-\mu(p,M_{2}(p)))T(\mathcal{M}(\cdot;\nu_{t})=M_{2})$
$\displaystyle\qquad\qquad+\sum_{M\in\mathcal{W}\setminus\\{M_{1},M_{2}\\}}(\mu(p,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{p}_{t}(p))-\mu(p,M(p)))T(\mathcal{M}(\cdot;\nu_{t})=M)$
$\displaystyle=(\mu(p,\mkern 4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{p}_{t}(p))-\mu(p,M_{2}(p)))T(\mathcal{M}(\cdot;\nu_{t})=M_{2})$
$\displaystyle\qquad\qquad+\sum_{M\in\mathcal{W}\setminus\\{M_{1},M_{2}\\}}(\mu(p,\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern
4.5mu^{p}_{t}(p))-\mu(p,M(p)))T(\mathcal{M}(\cdot;\nu_{t})=M)$
$\displaystyle\leq\Delta_{\max}(a)\left[T(\mathcal{M}(\cdot;\nu_{t})=M_{2})+\sum_{M\in\mathcal{W}\setminus\\{M_{1},M_{2}\\}}T(\mathcal{M}(\cdot;\nu_{t})=M)\right]$
$\displaystyle=O(\log(T)),$

where the second to last line follows from the fact that $\mkern
4.5mu\overline{\mkern-4.5muM\mkern-4.5mu}\mkern 4.5mu^{p}_{t}=M_{1}$ for all
$p\in\mathcal{P}$, and the last line follows from Lemma A.3 and that
$\mathcal{M}$ can be chosen such that
$T(\mathcal{M}(\cdot;\nu_{t})=M_{2})=O(\log(T))$. However, as shown in the
example under “Linear optimal regret”, when
$T(\mathcal{M}(\cdot;\nu_{t})=M_{2})=O(\log(T))$, it must hold true that
$T(\mathcal{M}(\cdot;\nu_{t})=M_{1})=\Omega(T)$, which implies that the regret
of a user must grow $\Omega(T)$. By the definition of fairness (Definition 2),
since there exists at least one agent (i.e., a provider) whose optimal regret
grows $O(\log(T))$ and at least one agent (i.e., a user) whose optimal regret
grows $\Omega(T)$, fairness is not guaranteed.

High social welfare not guaranteed. To show that high social welfare is not
guaranteed, it suffices to show the existence of an example in which the
social welfare is low. Let us again use the example under “Linear optimal
regret”. Suppose $\mathcal{M}(\cdot;\nu_{t})=M_{1}$ and
$\nu_{t}(u_{2},p_{3})>3W_{t}(\mathcal{M})=3\sum_{a\in\mathcal{A}}\nu_{t}(a,M_{1}(a))$.
This outcome is possible because (1) $u_{2}$ and $p_{3}$ are not matched under
$M_{1}$, which means that the values over which $W_{t}(\mathcal{M})$ is summed
does not include $\nu_{t}(u_{2},p_{3})$; (2) the magnitude of $u_{2}$’s
transient preferences does not affect the GS algorithm; and (3) it is possible
for $\nu_{t}(u_{2},p_{3})>\nu_{t}(u_{2},p_{1})$ even when
$\mathcal{M}(u_{2};\nu_{t})=p_{1}$ (simply apply the same logic as that given
in the example under “Linear optimal regret”).

As such,
$\max_{M\in\mathcal{W}}\sum_{a\in\mathcal{A}}\nu_{t}(a,M(a))\geq\nu_{t}(u_{2},p_{3})>3W_{t}(\mathcal{M})$,
which implies that, by Definition 3, the social welfare is low. Therefore,
high social welfare is not guaranteed under (2)-(3). ∎

##  Appendix D Proofs for proportional-cost, no-transfer setting (Section 4.3)

######  Proposition 4.

Consider the setup described in Section 3.1 with no transfer and proportional
costs, as stated in (4)-(5). Then, if the GS algorithm is applied over
$V(\cdot,\cdot;\nu_{t})$ at every time step $t\in[T]$, the system is
incentive-compatible. Moreover, if $\gamma\in[0,1)$, then,

$\displaystyle\mathchoice{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to6.13614pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to4.29529pt{}}}$\hss}}}{\hbox to0.0pt{{$\underline{{\hbox
to3.06805pt{}}}$\hss}}}R$ $\displaystyle(a;\mathcal{M})\leq
2N^{2}L(1-\gamma)\Delta_{\max}(a)\left(\frac{8\sigma^{2}\alpha\log(T)}{(1-\gamma)^{2}\Delta_{\min}^{2}}+\frac{\alpha}{\alpha-2}\right),$

for all $a\in\mathcal{A}$. However, under incentive compatibility, it is not
possible to guarantee fairness or that social welfare is high at every
$t\in[T]$, and there exist settings $(\mathcal{A},\mu)$ for which
$\bar{R}(a;\mathcal{M})=\Omega(T)$ for at least one agent $a\in\mathcal{A}$.

###### Proof.

For $\gamma\in[0,1)$, the setting described in this claim is equivalent to
that in Proposition 3, except that the payoffs are scaled by $(1-\gamma)$. To
see this, observe that
$V(a,a^{\prime};\psi)=\psi(a,a^{\prime})-\gamma\psi(a,a^{\prime})=(1-\gamma)\psi(a,a^{\prime})$.
Therefore, the same results as in Proposition 3 can be applied here with the
appropriate scaling. ∎

######  Lemma 5.

Consider the setup described in Section 3.1 and (4)-(5). If $\gamma=1$, then
all matchings are stable, i.e., for any
$\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$ and
$M\in\mathcal{W}$, $M\in S(V(\cdot,\cdot;\psi))$.

###### Proof.

When $\gamma=1$, $V_{t}(\cdot,\cdot;\psi)=0$ for all
$\psi:\mathcal{A}\times\mathcal{A}^{+}\rightarrow\mathbb{R}$. Under any
matching $M\in\mathcal{W}$, there cannot exist another matching
$M^{\prime}\in\mathcal{W}$ such that $V(a,M^{\prime}(a);\psi)>V(a,M(a);\psi)$
for some $a$ since $0>0$ is always false, which implies that $M$ is stable.
This result holds for any $M\in\mathcal{W}$. ∎

######  Corollary 6.

Consider the setup described in Section 3.1 and (4)-(5). Suppose that the
platform wishes to maximize some objective function
$F_{t}:\mathcal{W}\rightarrow\mathbb{R}$ at every time step $t$. Then, when