Learning Equilibria in Matching Markets from Bandit Feedback
Year: 2021

Abstract:
Large-scale, two-sided matching platforms must find market outcomes that align with user preferences while simultaneously learning these preferences from data. But since preferences are inherently uncertain during learning, the classical notion of stability (Gale and Shapley, 1962; Shapley and Shubik, 1971) is unattainable in these settings. To bridge this gap, we develop a framework and algorithms for learning stable market outcomes under uncertainty. Our primary setting is matching with transferable utilities, where the platform both matches agents and sets monetary transfers between them. We design an incentive-aware learning objective that captures the distance of a market outcome from equilibrium. Using this objective, we analyze the complexity of learning as a function of preference structure, casting learning as a stochastic multi-armed bandit problem. Algorithmically, we show that “optimism in the face of uncertainty,” the principle underlying many bandit algorithms, applies to a primal-dual formulation of matching with transfers and leads to near-optimal regret bounds. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces.1

heading: 1 Introduction
text: Data-driven marketplaces face the simultaneous challenges of learning agent preferences and aligning market outcomes with the incentives induced by these preferences. Consider, for instance, online platforms that match two sides of a market to each other (e.g., Lyft, TaskRabbit, and Airbnb). On these platforms, customers are matched to service providers and pay for the service they receive. If agents on either side are not offered desirable matches at fair prices, they would have an incentive to leave the platform and switch to a competing platform. Agent preferences, however, are often unknown to the platform and must be learned. When faced with uncertainty about agent preferences (and thus incentives), when can a marketplace efficiently explore and learn market outcomes that align with agent incentives?
We center our investigation around a model called matching with transferable utilities, proposed by Shapley and Shubik [32]. In this model, there is a two-sided market of customers and service providers. Each customer has a utility that they derive from being matched to a given provider and vice versa. The platform selects a matching between the two sides and assigns a monetary transfer between each pair of matched agents. Transfers are a salient feature of most real-world matching
†Equal contribution. 1A full version of this paper (referenced as [18]) is available at https://arxiv.org/abs/2108.08843.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
markets: riders pay drivers on Lyft, clients pay freelancers on TaskRabbit, and guests pay hosts on Airbnb. An agent’s net utility is their value for being matched to their partner plus the value of their transfer (either of which can be negative in the cases of costs and payments). In matching markets, the notion of stability captures alignment of a market outcome with agent incentives. Informally, a market outcome is stable if no pair of agents would rather match with each other than abide by the market outcome, and stable matchings can be computed when preferences are fully known.
However, in the context of large-scale matching platforms, the assumption that preferences are known breaks down. Platforms usually cannot have users report their complete preference profiles. Moreover, users may not even be aware of what their own preferences are. For example, a freelancer may not exactly know what types of projects they prefer until actually trying out specific ones. In reality, a data-driven platform is more likely to learn information about preferences from repeated feedback over time. Two questions now emerge: In such marketplaces, how can stable matchings be learned? And what underlying structural assumptions are necessary for efficient learning to be possible?
Toward answering these questions, we propose and investigate a model for learning stable matchings from noisy feedback. We model the platform’s learning problem using stochastic multi-armed bandits, which lets us leverage the extensive body of techniques in the bandit literature to analyze the data efficiency of learning. Specifically, our main contributions are: (i) We develop an incentiveaware learning objective—Subset Instability—that captures the distance of a market outcome from equilibrium. (ii) Using Subset Instability as a measure of regret, we show that any “UCB-based” algorithm can be adapted to this incentive-aware setting. (iii) We instantiate this idea for two families of preference structures to design efficient algorithms for incentive-aware learning, helping elucidate how preference structure affects the complexity of learning stable matchings.
Designing the learning objective. Since mistakes are inevitable while exploring and learning, achieving exact stability at every time step is an unattainable goal. To address this issue, we lean on approximation, focusing on learning market outcomes that are approximately stable. Thus, we need a metric that captures the distance of a market outcome from equilibrium.
We introduce a notion for approximate stability that we call Subset Instability. Specifically, we define the Subset Instability of a market outcome to be the maximum difference, over all subsets S of agents, between the total utility of the maximum weight matching on S and the total utility of S under the market outcome.We show Subset Instability can be interpreted as how much the platform would have to subsidize participants to keep them on the platform and make the resulting matching stable. We also show that Subset Instability is the maximum gain in utility that a coalition of agents could have derived from an alternate matching such that no agent in the coalition is worse off.
Subset Instability also satisfies the following properties, which make it suitable for learning: (i) Subset Instability is equal to 0 if and only if the market outcome is (exactly) stable; (ii) Subset Instability is robust to small perturbations to the utility functions of individual agents, which is essential for learning with noisy feedback; (iii) Subset Instability upper bounds the utility difference of a market outcome from the socially optimal market outcome.
Designing algorithms for learning a stable matching. Using Subset Instability, we investigate the problem of learning a stable market outcome from noisy user feedback in a stochastic bandit model. In each round, the platform selects a market outcome (i.e., a matching along with transfers), with the goal of minimizing cumulative instability.
We develop a general approach for designing bandit algorithms within our framework. Our approach is based on a primal-dual formulation of matching with transfers [32] We find that “optimism in the face of uncertainty,” the principle underlying many UCB-style bandit algorithms [3, 22], can be adapted to this primal-dual setting. The resulting algorithm is simple: maintain upper confidence bounds on the agent utilities and compute, in each round, an optimal primal-dual pair in terms of these upper confidence bounds. Following this approach, we show regret bounds for two sets of structural assumptions on agent preferences, which we now state.
Theorem 1.1 (Unstructured Preferences, Informal). There exists a UCB-style algorithm that incurs Õ(N √ nT ) regret according to Subset Instability after T rounds, where N is the number of agents on the platform and n is the number of agents that arrive in any round. (In fact, this bound is optimal up to logarithmic factors.)
Theorem 1.2 (Separable Linear Preferences, Informal). Suppose each agent a gets utility 〈φ(a), ca′〉 from matching with a′, where φ(a) ∈ Rd is unknown and ca′ ∈ Rd is known. Then there exists a UCB-style algorithm that incurs Õ(d √ N √ nT ) regret according to Subset Instability after T rounds, for N the number of agents on the platform and n the maximum number of agents in any round.
These results highlight the role of preference structure on the complexity of learning a stable matching. To see this concretely, consider the case where all agents show up each round, so n = N . In this case, our regret bound for unstructured preferences is superlinear in N ; and this dependence on N is necessary due to a lower bound (see Lemma 5.4). On the other hand, our regret bound is linear in N for separable linear preferences. This means that in large markets, a centralized platform can efficiently learn a stable matching with this preference structure assumption.
Extensions. In the full version [18], we provide several extensions of our framework and results to additional classes of preference structures, alternative forms of regret bounds, and richer platform objectives, and other models of matching markets. In Section 6, we briefly discuss two of these extensions—instance-dependent regret bounds and matching markets with non-transferable utilities.

heading: 1.1 Related work
text: In the machine learning literature, starting with Das and Kamenica [11] and Liu et al. [24], several works [11, 24, 30, 25, 7, 6] study learning stable matchings from bandit feedback in the Gale-Shapley stable marriage model [15]. A major difference between this setting and ours is the absence of monetary transfers between agents. These works focus on the utility difference rather than the instability measure that we consider. Cen and Shah [7] extend this bandits model to incorporate fixed, predetermined cost/transfer rules. However, they do not allow the platform to set arbitrary transfers between agents. Moreover, they also consider a weaker notion of stability that does not consider agents negotiating arbitrary transfers: defecting agents must set their transfers according to a fixed, predetermined structure. In contrast, we follow the classical definition of stability [32].
Outside of machine learning, several papers also consider the complexity of finding stable matchings in other feedback and cost models, e.g., communication complexity [16, 2, 33] and query complexity [12, 2]. Of these works, Shi [33], which studies the communication complexity of finding approximately stable matchings with transferable utilities, is most similar to ours. Shi assumes agents know their preferences and focuses on the communication bottleneck, whereas we study the costs associated with learning preferences. Moreover, the approximate stability notion in Shi [33] is the maximum unhappiness of any pair of agents, whereas Subset Instability measures the maximum unhappiness over any subset of agents. For learning stable matchings, Subset Instability has the advantages of being more fine-grained and having a primal view that motivates a clean UCB-based algorithm.
Our notion of instability connects to historical works in coalitional game theory: related are the concepts of the strong-ε core of Shapley and Shubik [31] and the indirect function of Martínez-Legaz [27], although each was introduced in a very different context than ours. Nonetheless, they reinforce the fact that our instability notion is a very natural one to consider.
Multi-armed bandits have also been applied to learning in other economic contexts. For example, learning a socially optimal matching (without learning transfers) is a standard application of combinatorial bandits [8, 14, 9, 10, 21]. Other applications at the interface of bandit methodology and economics include dynamic pricing [28, 20, 5], incentivizing exploration [13, 26], learning under competition [1], and learning in matching markets without incentives [19].
Finally, primal-dual methods have also featured elsewhere in the bandits literature (e.g., [17, 34, 23]).

heading: 2 Preliminaries
text: The foundation of our framework is the matching with transfers model of Shapley and Shubik [32]. In this section, we introduce this model along with the concept of stable matching.

heading: 2.1 Matching with transferable utilities
text: Consider a two-sided market that consists of a finite set I of customers on one side and a finite set J of providers on the other. Let A := I ∪ J be the set of all agents. A matching X ⊆ I × J is
a set of pairs (i, j) that are pairwise disjoint, representing the pairs of agents that are matched. Let XA denote the set of all matchings on A. For notational convenience, we define for each matching X ∈XA an equivalent functional representation µX : A → A, where µX(i) = j and µX(j) = i for all matched pairs (i, j) ∈ X , and µX(a) = a if a ∈ A is unmatched. When a pair of agents (i, j) ∈ I × J matches, each experiences a utility gain. We denote these utilities by a global utility function u : A × A → R, where u(a, a′) denotes the utility that agent a gains from being matched to agent a′. (If a and a′ are on the same side of the market, we take u(a, a′) to be 0 by default.) We allow these utilities to be negative, if if matching results in a net cost (e.g., if an agent is providing a service). We assume each agent a ∈ A receives zero utility if unmatched, i.e., u(a, a) = 0. When we wish to emphasize the role of an individual agent’s utility function, we will use the equivalent notation ua(a′) := u(a, a′).
A market outcome consists of a matching X ∈XA along with a vector τ ∈ RA of transfers, where τa is the amount of money transferred from the platform to agent a for each a ∈ A. These monetary transfers are a salient feature of most real-world matching markets: riders pay drivers on Lyft, clients pay freelancers on TaskRabbit, and guests pay hosts on Airbnb. Shapley and Shubik [32] capture this aspect of matching markets by augmenting the classical two-sided matching model with transfers of utility between agents. Transfers are typically required to be zero-sum, meaning that τi + τj = 0 for all matched pairs (i, j) ∈ X and τa = 0 if a is unmatched. Here, X represents how agents are matched and τa represents the transfer that agent a receives (or pays). The net utility that an agent a derives from a matching with transfers (X, τ) is therefore u(a, µX(a)) + τa.
Stable matchings. In matching theory, stability captures when a market outcome aligns with individual agents’ preferences. Roughly speaking, a market outcome (X, τ) is stable if: (i) no individual agent a would rather be unmatched, and (ii) no pair of agents (i, j) can agree on a transfer such that both would rather match with each other than abide by (X, τ). Formally: Definition 2.1. A market outcome (X, τ) is stable if: (i) it is individually rational, i.e.,
ua(µX(a)) + τa ≥ 0 (1)
for all agents a ∈ A, and (ii) it has no blocking pairs, i.e.,( ui(µX(i)) + τi ) + ( uj(µX(j)) + τj ) ≥ ui(j) + uj(i) (2)
for all pairs of agents (i, j) ∈ I × J .2
A fundamental property of the matching with transfers model is that if (X, τ) is stable, then X is a maximum weight matching, i.e., X maximizes ∑ a∈A ua(µX(a)) over all matchings X ∈XA [32]. The same work shows that stable market outcomes coincide with Walrasian equilibria.
To make the matching with transfers model concrete, we use the simple market depicted in the center panel of Figure 1 as a running example throughout the paper. This market consists of a customer Charlene and two providers Percy and Quinn, which we denote by I = {C} and J = {P,Q}. If the agents’ utilities are as given in Figure 1, then Charlene would prefer Quinn, but Quinn’s cost of providing the service is much higher. Thus, matching Charlene and Percy is necessary for a stable outcome. This matching is stable for any transfer from Charlene to Percy in the interval [5, 7].

heading: 3 Learning Problem and Feedback Model
text: We instantiate the platform’s learning problem in a stochastic contextual bandits framework. Matching takes place over the course of T rounds. We denote the set of all customers by I∗, the set of all providers by J ∗, and the set of all agents on the platform by A∗ = I∗ ∪ J ∗. Each agent a ∈ A∗ has an associated context ca ∈ C, where C is the set of all possible contexts. The context ca represents the side information available to the platform about a (e.g., demographic or location information). Each round, a set of agents arrives to the market. The platform then selects a market outcome and incurs a regret equal to the instability of the market outcome (which we introduce formally in Section 4). Finally, the platform receives noisy feedback about the utilities of each matched pair.
2We observe that (2) corresponds to no pair of agents (i, j) being able to agree on a transfer such that both would rather match with each other than abide by (X, τ). Notice that a pair (i, j) violates (2) if and only if they can find a transfer τ ′i = −τ ′j such that ui(j) + τ ′i > ui(µX(i)) + τi and uj(i) + τ ′j > uj(µX(j)) + τj .
To interpret the noisy feedback, note that platforms in practice often receive feedback both explicitly (e.g., riders rating drivers after a Lyft ride) and implicitly (e.g., engagement metrics on an app). In either instance, feedback is likely to be sparse and noisy. For simplicity, we do not account for agents strategically manipulating their feedback to the platform and focus on the problem of learning preferences from unbiased reports.
We now describe this model more formally. In the t-th round:
1. A set It ⊆ I∗ of customers and a set J t ⊆ J ∗ of providers arrive to the market. Write It ∪ J t =: At. The platform observes At and the context ca ∈ C of each agent a ∈ At. 2. The platform selects a matching with zero-sum transfers (Xt, τ t) between It and J t. 3. The platform observes noisy utilities ua(µXt(a)) + εa,t for each agent a ∈ It ∪ J t, where
the εa,t are independent, 1-subgaussian random variables. 4. The platform incurs regret equal to the instability of the selected market outcome (Xt, τ t).
The platform’s total regret RT is thus the cumulative instability incurred up through round T .

heading: 3.1 Preference structure
text: In this bandits framework, we can embed varying degrees of structure on agent preferences. We capture these preference structures by the functional form of agents’ utility functions and its relation to agent contexts. More formally, let U be the set of functions u : A∗ ×A∗ → R, i.e., U is the set of all possible (global) utility functions. We introduce our preference structures as subsets of U .
Unstructured preferences. The basic setting is one where the preferences are unstructured. Specifically, we consider the class of utility functions Uunstructured = { u ∈ U | u(a, a′) ∈ [−1, 1] } . In this setup, the platform must learn each agent’s utility function ua(·) = u(a, ·).
Separable linear preferences. We also consider markets where each agent has known information given by their context as well as hidden information that must be learned by the platform. We explore this setting under the assumption that agents’ contexts and hidden information interact linearly.
We assume that all contexts belong to Bd (i.e., C = Bd) where Bd is the `2 unit ball in Rd. We also assume that there exists a function φ : A∗ → Bd mapping each agent to the hidden information associated to that agent. The preference class Udlinear can then be defined as
Udlinear = { u ∈ U ∣∣ u(a, a′) = 〈ca′ , φ(a)〉 for some φ : A∗ → Bd}.

heading: 4 Measuring Approximate Stability
text: When learning stable matchings, we must settle for guarantees of approximate stability, since exact stability—a binary notion—is unattainable when preferences are uncertain. To see this, we return to
the example from Figure 1. Suppose that the platform has uncertainty sets given by the right panel. Recall that for the true utilities, all stable outcomes match Charlene with Percy. If the true utilities were instead the upper bounds of each uncertainty set, then all stable outcomes would match Charlene and Quinn. Given only the uncertainty sets, it is impossible for the platform to find an (exactly) stable matching, so it is necessary to introduce a measure of approximate stability as a relaxed benchmark for the platform; we turn to this now.
Given the insights of Shapley and Shubik [32]—that all stable outcomes maximize the sum of agents’ utilities—it might seem natural to measure distance from stability simply in terms of the utility difference. Formally, let A be the set of agents participating in the market. (This corresponds to At at time step t in the bandits model.) The utility difference3 of a market outcome (X, τ) is(
max X′∈XA ∑ a∈A ua(µX′(a))
) − (∑ a∈A ua(µX(a)) + τa) ) . (3)
The first term is the maximum total utility of any matching, and the second term is the total utility of market outcome (X, τ). Since transfers are zero-sum, (3) can be equivalently written as(
max X′∈XA ∑ a∈A ua(µX′(a)) ) − ∑ a∈A ua(µX(a)).
But this shows that utility difference ignores the transfers τ entirely! In fact, the utility difference can be zero even when the transfers lead to a market outcome that is far from stable (see Appendix A.1). Utility difference is therefore not incentive-aware, making it unsuitable as an objective for learning stable matchings with transfers.
In the remainder of this section, we propose a measure of instability—Subset Instability—and show that it serves as a well-motivated and suitable objective for learning stable matchings with transfers.

heading: 4.1 Subset Instability
text: Subset Instability is based on utility difference, but rather than only looking at the market in aggregate, it takes a maximum ranging over all subsets of agents. Definition 4.1. Given utilities u, the Subset Instability of a matching with transfers (X, τ) is
I(X, τ ;u,A) := max S⊆A [( max X′∈XS ∑ a∈S ua(µX′(a)) ) − (∑ a∈S ua(µX(a)) + τa )] . (∗)
(The first term is the maximum total utility of any matching over S, and the second term is the total utility of the agents in S under market outcome (X, τ).)
Intuitively, Subset Instability captures stability because it checks whether any subset of agents would prefer an alternate outcome. We provide a more extensive economic interpretation below; but before doing so, we first illustrate Definition 4.1 in the context of the example in Figure 1.
Consider the matching X = {(C,Q)} with transfers τC = −11 and τQ = 11. (This market outcome is stable for the upper bounds of the uncertainty sets of the platform in Figure 1, but not stable for the true utilities.) Note that the subset S that maximizes Subset Instability is S = {C,P}, in which case maxX′∈XS ∑ a∈S ua(µX′(a)) = 4 and ∑ a∈S (ua(µX(a)) + τa) = 1. Thus, the Subset Instability of (X, τ) is I(X, τ ;u,A) = 4− 1 = 3. In contrast, the utility difference of (X, τ) is 2. We now give two interpretations of Subset Instability to provide further insight into why Subset Instability is a meaningful notion of approximate stability in online marketplaces. Specifically, we interpret Subset Instability as the minimum stabilizing subsidy and as a measure of user unhappiness.
Subset Instability as the platform’s minimum stabilizing subsidy. Subset Instability can be interpreted in terms of monetary subsidies from the platform to the agents. Specifically, the Subset
3Utility difference is standard as a measure of regret for learning a maximum weight matching in the combinatorial bandits literature (see, e.g., [14]). However, we show that for learning stable matchings, a fundamentally different measure of regret is needed.
Instability of a market outcome equals the minimum amount the platform could subsidize agents so that the subsidized market outcome is individually rational and has no blocking pairs.
Formally, let s ∈ RA≥0 denote subsidies made by the platform, where sa ≥ 0 is the subsidy provided to agent a. For a market outcome (X, τ), the minimum stabilizing subsidy is
min s∈RA≥0 {∑ a∈A sa ∣∣∣∣ (X, τ + s) is stable } , (4)
where we define stability in analogy to Definition 2.1. Specifically, we say that a market outcome (X, τ) with subsidies s is stable if it is individually rational, i.e., ua(µX(a)) + τa + sa ≥ 0 for all agents a ∈ A, and has no blocking pairs, i.e., (ui(µX(i)) + τi + si) + (uj(µX(j)) + τj + sj) ≥ ui(j) + uj(i) for all pairs of agents (i, j) ∈ I × J . We show the following equivalence: Proposition 4.2. Minimum stabilizing subsidy equals Subset Instability for any market outcome.
The proof boils down to showing that the two definitions are “dual” to each other. To formalize this, we rewrite the minimum stabilizing subsidy as the solution to the following linear program:
min s∈R|A| ∑ a∈A sa (5)
s.t. ( ui(µX(i)) + τi + si ) + ( uj(µX(j)) + τj + sj ) ≥ ui(j) + uj(i) ∀(i, j) ∈ I × J
ua(µX(a)) + τa + sa ≥ 0 ∀a ∈ A sa ≥ 0 ∀a ∈ A.
The crux of our argument is that the dual linear program to (5) maximizes the combinatorial objective (∗). The equivalence of (∗) and (5) then follows from strong duality.
Subset Instability as a measure of user unhappiness. While the above interpretations focus on Subset Instability from the platform’s perspective, we show that Subset Instability can also be interpreted as a measure of user unhappiness. Given a subset S ⊆ A of agents, which we call a coalition, we define the unhappiness of S with respect to a market outcome (X, τ) to be the maximum gain (relative to (X, τ)) in total utility that the members of coalition S could achieve by matching only among themselves, such that no member is worse off than they were in (X, τ). (See Appendix A.3 for a formal definition.) The condition that no member is worse off ensures that all agents would actually want to participate in the coalition (i.e. they prefer it to the original market outcome).
User unhappiness differs from the original definition (∗) of Subset Instability, since (∗) does not require agents to be better off in any alternative matching. We show this difference is inconsequential: Proposition 4.3. The maximum unhappiness of any coalition S ⊆ A with respect to (X, τ) equals the Subset Instability I(X, τ ;u,A).
The main takeaway from Proposition 4.3 is that Subset Instability not only measures costs to the platform, but also costs to users, in terms of the maximum amount they “leave on the table” by not negotiating an alternate arrangement amongst themselves.

heading: 4.2 Properties of Subset Instability
text: We now describe additional properties of our instability measure that are important for learning. We show that Subset Instability is: (i) zero if and only if the matching with transfers is stable, (ii) Lipschitz in the true utility functions, and (iii) lower bounded by the utility difference. Proposition 4.4. Subset Instability satisfies the following properties:
1. Subset Instability is always nonnegative and is zero if and only if (X, τ) is stable. 2. Subset Instability is Lipschitz continuous with respect to agent utilities. That is, for any
possible market outcome (X, τ), and any pair of utility functions u and ũ it holds that: |I(X, τ ;u,A)− I(X, τ ; ũ,A)| ≤ 2 ∑ a∈A ‖ua − ũa‖∞.
3. Subset Instability is always at least the utility difference.
These three properties show that Subset Instability is useful as a regret measure for learning stable matchings. The first property establishes that Subset Instability satisfies the basic desideratum of having zero instability coincide with exact stability. The second property shows Subset Instability is robust to small perturbations to agents’ utility functions. The third property ensures that, when learning using Subset Instability as a loss function, the platform learns a socially optimal matching.

heading: 5 Learning Stable Matchings in a Bandits Framework
text: In this section, we develop a general approach for designing algorithms that achieve near-optimal regret within our framework. While our framework bears some resemblance to the (incentive-free) combinatorial bandit problem of learning a maximum weight matching, our setting has two crucial differences: (i) in each round, the platform must choose transfers in addition to a matching, and (ii) loss is measured with respect to instability rather than the utility difference. Nonetheless, we show that a suitable interpretation of “optimism in the face of uncertainty” can still apply.
Regret bounds for different preference structures. By instantiating this optimism-based approach, we derive regret bounds for the preference structures introduced in Section 3. We start with the simplest case of unstructured preferences, where we assume no structure on the utilities.
Theorem 5.1. For preference class Uunstructured (see Section 3), MATCHUCB (defined in Section 5.2) incurs an expected regret of E(RT ) = O ( |A| √ nT log(|A|T ) ) , where n = maxt |At|.
In Section 5.3, we additionally give a matching (up to logarithmic factors) lower bound showing for n = |A| that such scaling in |A| is indeed necessary. Thus, regret must scale as |A| √ n, which is superlinear in the size of the market. This bound means that the platform needs to learn a superconstant amount of information per agent in the marketplace. This suggests that, without preference structure, it is unlikely that a platform can efficiently learn a stable matching in a large market.
The next bound demonstrates that, with preference structure, efficient learning of a stable matching becomes possible. Specifically, we consider separable linear preferences, where the platform needs to learn hidden information associated to each agent. We show the following:
Theorem 5.2. For preference class Ulinear (see Section 3), MATCHLINUCB (defined in Section 5.2) incurs an expected regret of E(RT ) = O ( d √ |A| √ nT log(|A|T ) ) , where n = maxt |At|.
When n is comparable to |A|, the regret bound in Theorem 5.2 scales linearly with the market size (captured by |A|) and linearly with the dimension d. This means that the platform learns (at most) a constant amount of information per agent in the marketplace. We interpret this as indicating that the platform can efficiently learn a stable matching in large markets for separable linear preferences.

heading: 5.1 Algorithm
text: Algorithm 1 COMPUTEMATCH: Compute matching with transfers from confidence sets 1: procedure COMPUTEMATCH(C ) 2: for (i, j) ∈ I × J do . Instantiate UCB estimates of utilities. 3: uUCBi (j)← max ( Ci,j ) ; uUCBj (i)← max ( Cj,i
) 4: (X∗, p∗)← optimal primal-dual pair for (P) and (D) given utilities uUCB 5: for a ∈ A do . Set transfers based on (X∗, p∗) and UCB utilities. 6: τa ← p∗a − uUCBa (µX∗(a)) 7: return (X∗, τ )
Following the principle of optimism, our algorithm selects at each round a stable market outcome using upper confidence bounds as if they were the true agent utilities. To design and analyze this algorithm, we leverage the fact that, in the full-information setting, stable market outcomes are optimal solutions to a pair of primal-dual linear programs whose coefficients depend on agents’ utility functions. This primal-dual perspective lets us compute a market outcome each round. A particular consequence is that any UCB-based algorithm for learning matchings in a semi-bandit setting can be transformed into an algorithm for learning both the matching and the prices.
Stable market outcomes via linear programming duality. Before proceeding with the details of our algorithm, we review how the primal-dual framework can be used to select a stable market outcome in the full information setting. Shapley and Shubik [32] show that stable market outcomes (X, τ) correspond to optimal primal-dual solutions to the following pair of primal and dual linear programs (where we omit the round index t and consider matchings over A = I ∪ J ):
Primal (P)
max Z∈R|I|×|J | ∑ (i,j)∈I×J Zi,j(ui(j) + uj(i))
s.t. ∑ j∈J
Zi,j ≤ 1 ∀i ∈ I∑ i∈I Zi,j ≤ 1 ∀j ∈ J
Zi,j ≥ 0 ∀(i, j) ∈ I × J
Dual (D)
min p∈R|A| ∑ a∈A pa
s.t. pi + pj ≥ ui(j) + uj(i) ∀(i, j) ∈ I × J pa ≥ 0 ∀a ∈ A
Given any optimal primal-dual solution (Z, p) to (P) and (D), one can recover a matching µX from the nonzero entries of Z and set transfers τa = pa − ua(µX(a)) to obtain a stable outcome (X, τ). Moreover, any stable outcome induces an optimal primal-dual pair (Z, p).
Overview of the algorithm. Each round, we compute a matching with transfers by solving (P) and (D) for our upper confidence bounds: Suppose that we have a collection C of confidence sets Ci,j , Cj,i ⊆ R such that ui(j) ∈ Ci,j and uj(i) ∈ Cj,i for all (i, j) ∈ I × J . We use C to get an upper confidence bound estimate for each agent’s utility function and then compute a stable matching with transfers as if these estimates were the true utilities—see Algorithm 1 (COMPUTEMATCH).
The key fact we need to analyze our algorithms is that Subset Instability is upper bounded by the sum of the sizes of the relevant confidence sets, assuming that the confidence sets contain the true utilities. We show this in the following lemma, where we again omit the round index t: Lemma 5.3. Suppose a collection of confidence sets C is such that ui(j) ∈ Ci,j and uj(i) ∈ Cj,i for all (i, j) ∈ I × J . Then the instability of (XUCB, τUCB) := COMPUTEMATCH(C ) satisfies
I(XUCB, τUCB;u,At) ≤ ∑ a∈A ( max ( Ca,µXUCB (a) ) −min ( Ca,µXUCB (a) )) . (6)
To prove this, write I(XUCB, τUCB;u,At) = I(XUCB, τUCB;u,At)−I(XUCB, τUCB;uUCB,At). Now, it may be tempting to bound this difference using the Lipschitz continuity of Subset Instability. However, such a bound would depend on the sizes of the confidence sets for all pairs of agents, including those not matched in XUCB, making it too weak to analyze UCB-style algorithms. Thus, we use the fact that uUCB is a pointwise upper bound on u to obtain a tighter analysis.

heading: 5.2 Explicit algorithms
text: The regret bound of Lemma 5.3 suggests an algorithmic approach: each round, select the matching with transfers returned by COMPUTEMATCH and update confidence sets accordingly. To instantiate this approach, it remains to construct confidence intervals that contain the true utilities with high probability. This last step naturally depends on the assumptions made about the utilities and the noise.
Unstructured preferences. We construct confidence intervals following the classical UCB approach: for each utility value involving the pair (i, j) ∈ I×J , we take a lengthO (√ log(|A|T )/nij ) confidence interval centered around the empirical mean, where nij is the number of times the pair has been matched so far. We give this construction precisely in Algorithm 2 (MATCHUCB).
To analyze MATCHUCB, recall that Lemma 5.3 bounds the regret at each step by the lengths of the confidence intervals of each pair in the selected matching. Bounding the lengths of the confidence intervals parallels the analysis of UCB for classical stochastic multi-armed bandits.
Separable Linear Preferences. We build confidence sets using the high-level idea from LinUCB [29, 22]: we compute a confidence set for each hidden vector φ(a) using a least squares estimate and use that to get confidence sets Ca,a′ for the utilities. We detail this precisely in Appendix B.3.
Algorithm 2 MATCHUCB: A bandit algorithm for matching with transferable utilities for unstructured preferences.
1: procedure MATCHUCB(T ) 2: for (i, j) ∈ I × J do . Initialize confidence intervals. 3: Ci,j ← [−1, 1]; Cj,i ← [−1, 1] 4: for 1 ≤ t ≤ T do 5: (Xt, τ t)← COMPUTEMATCH(C ) 6: for (i, j) ∈ Xt do . Set confidence intervals and update means. 7: Update empirical means ûi(j) and ûj(i) from feedback; increment counter nij . 8: Ci,j ← [ ûi(j)− 8 √ log(|A|T )/nij , ûi(j) + 8 √ log(|A|T )/nij ] ∩ [−1, 1]
9: Cj,i ← [ ûj(i)− 8 √ log(|A|T )/nij , ûj(i) + 8 √ log(|A|T )/nij ] ∩ [−1, 1]

heading: 5.3 Matching lower bound
text: For the case of unstructured preferences, we now show MATCHUCB achieves optimal regret (up to logarithmic factors) by showing a lower bound that (nearly) matches the upper bound in Theorem 5.1.
Lemma 5.4. Any algorithm that learns a stable matching with respect to unstructured preferences has an instance on which it has expected regret Ω̃(|A|3/2 √ T ) (as measured by Subset Instability).
To show the lower bound, we prove a lower bound for the easier (by Proposition 4.4) problem of learning a maximum weight matching. This lower bound illustrates the close connection between our setting and that of learning a maximum weight matching. Indeed, by applying MATCHUCB and simply disregarding the transfers every round, we recover the classical UCB-based algorithm for learning the maximum weight matching [14, 9, 21]. From this perspective, the contribution of MATCHUCB is an approach to set the dual variables while asymptotically maintaining the same regret as the primal-only problem.

heading: 6 Extensions
text: Instance-dependent regret bounds While we have focused on bounds that hold uniformly for all problem instances, we now explore instance-dependent regret bounds. Instance-dependent bounds capture a different facet of bandit algorithms: how does the number of mistakes made by the algorithm on each instance scale with respect to T ? We show O(log T ) regret bounds in the full version [18].
Matching with non-transferable utilities While we have focused on matching with transferable utilities, utilities are not always transferable with money in practice (e.g., dating markets and college admissions). In the full version [18], we extend our findings to the matching with non-transferable utilities (NTU) model [15], which has also been studied in a learning context [11, 24, 7, 30]. The definition of Subset Instability extends naturally and has advantages over the “utility difference” metric used in prior work. We further show that a suitable interpretation of UCB can also be applied to this setting.

heading: 7 Discussion
text: We introduced a framework for learning equilibria in matching markets from bandit feedback. A core component is Subset Instability, which captures the distance of a market outcome from equilibrium. Using Subset Instability as a loss function, we designed UCB-based learning algorithms that optimize for alignment with agent incentives. The resulting regret bounds for different preference structures take a step towards elucidating when a marketplace can efficiently learn stable outcomes.
While we focused on matching markets with stochastic bandit feedback in this work, we believe that the question of learning equilibria in data-driven marketplaces is of much more general interest. An interesting direction for future inquiry would be to explore in what other settings, and with what other algorithmic methods, can equilibria be learned? 4
4For a more detailed discussion of directions for future work, see the full version of the paper [18].
Acknowledgments and Disclosure of Funding
We would like to thank Itai Ashlagi, Jiantao Jiao, Scott Kominers (along with the Lab for Economic Design), Cassidy Laidlaw, Celestine Mendler-Dünner, and Banghua Zhu for valuable feedback. Meena Jagadeesan acknowledges support from the Paul and Daisy Soros Fellowship; Alexander Wei acknowledges support from an NSF Graduate Research Fellowship under Grant No. 1752814.

Review summaries:
The paper considers two-sided platforms who seek to match users on   both sides under uncertainty about user preferences. The focus is on   the transferable utility setting, where the platform, in addition to   orchestrating a matching, imposes transfers between each pair (as   well as from the platform to the pair). After each matching, the   platform receives noisy (bandit) feedback regarding the utilities   received by each member in a matched pair. The goal of the platform   is to learn a stable market outcome efficiently. To capture the   (in)efficiency of learning, the authors introduce a measure of   instability of any matching, namely subsidy instability, which is   equal to the smallest total (non-negative) transfer the platform   needs to make to the users so that matching is stable. The regret of   any learning algorithm is then defined as the total subsidy   instability accumulated over a time horizon.    The authors first show that the subsidy instability is indeed an   appropriate notion to capture learning efficiency, by providing   natural economic interpretations as well as exhibiting a number of   smoothness properties and bounds. The authors then propose a natural   UCB-type algorithm, where each agent reports upper confidence bounds   on their preferences and the platform computes the optimal stable   matching and transfers under these reported preferences. The authors   show that this algorithm achieves an expected regret that is of   order $O(\sqrt{T\log T})$, and furthermore provide a matching lower   bound. (The bounds also establish regret dependence on other model   parameters.) 

The authors study stability in two-sided markets with transferable utilities where each agent has no a-priori knowledge of her own preference. They introduce the measure of 'Subsidy Instability' that is defined as the minimum total subsidy (extra payment to all the agents) that can stabilize a (matching, transfer) pair. They propose a UCB based primal-dual algorithm that tries to minimize the Subsidy Instability with bandit feedback for the above system. The proposed algorithm is proved to have a O(|A|^3/2\sqrt{T}) regret in a time horizon of T, where A is the set of all agents. They provide an orderwise matching  lower bound for this setting.