Learning Equilibria in Matching Markets from Bandit Feedback
Authors: Meena Jagadeesan
Alexander Wei
Yixin Wang
Michael Jordan
Jacob Steinhardt
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: matching markets
learning equilibria
multi-armed bandits

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.

Learning Equilibria in Matching Markets from Bandit Feedback
Meena Jagadeesan' UC Berkeley mj jaaaadeesanneerzeeeeyy edu
Alexander Weif UC Berkeley awei@berkeley. edu
Yixin Wang UC Berkeley ywangBeecs berkeley.
Michael I. Jordan
Jacob Steinhardt UC Berkeley
UC Berkeley
jordanêcs. berkeley.
jateinhhardttberkkeeey
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) 1) 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 matching with transferable utilities, where the platform both matches agents and sets mone- tary 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 uncertainty," the principle underlying many bandit algorithms, applies to primal -daal formulation of matching with transfers and leads npar-optimal regret bounds. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces
Introduction
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 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 align with agent incentives?
marketplace efficiently explore and learn market outcomes that
We center our investigation around model called matching with transferuble utilities, proposed by Shapley and Shubik 322. In this model, there a two-sided market of customers and service providers. Each customer has utility that they derive from being matched to given provider and vice versa. The platform selects matching between the two sides and assigns a monetary transfer between each pair of matched agents. Transfers are salient feature of most real-world matching
1 Equal contribution.
A full version of this paper (referenced as 18 is available at atttttp::/aaxxww.rrr////
08843
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

markets: riders pay drivers on Lyft, clients pay freelancers on TaskRabbit, and guests pay hosts on Airbnb. An agent's '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, 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 is learning problem using stochastic multi-armed bandits, which lets us leverage the extensive body of techniques in the bandit literature analyze the data efficiency of learning. Specifically, our main contributions are: (i) We develop an incentive- aware learning
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-brr -baeedd algorithm can be adapted this incentive-aware setting. (iii) We instantiate this idea for two families of preference structures to design efficient algorithms for incentive-awe learning, helping elucidate how preference structure affects the complexity of learning stable matchings.
Srrrctive-Subbee
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 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 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 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 market outcome (i.c., a matching along with transfers), with the goal of minimizing cumulative instability.
We develop general approach for designing bandit algorithms within our framework. Our approach based on a primal-duat formulation of matching with transfers 332 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 the agent utilities and compute, in each round, 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 VrTT 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 logarithmic factors.)
2

---

Theorem 1.2 (Separable Linear Preferences, Informal). Suppose each agent a gets utility (ó(a), Car) from matching with d', where Φ(a) E Rdd is unknown and ca E RRd is known. Then there exists UCB-style algorithm that incurs ((dv N VnT) regret according to Subset Instability after T rounds, for N the number of agents on the platform and nu 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 ... In this case, our regret bound for unstructured preferences is superlinear in N: and this dependence on N 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 insiiions-instannedeeeeeaa regret bounds and matching markets with -on-transferable utilities.
1.1 Related work
In the machine learning literature, starting with Das and Kamenica [ and Liu al. [24] several works [1124 30 25 6 study learning stable matchings from bandit feedback in the Gale-Shapley stable marriage model [S]. 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 [6 33 and query complexity
12 (2 Of these works, Shi [3). which studies the communication complexity of finding approxi- mately 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 ane-grained and having primal view that motivates a clean
algorithm.
Our notion of instability connects to historical works in coalitional game theory: related are the concepts of the strong-s core of Shapley and Shubik (3I and the indirect function of Martínez-Legat 277, although each was introduced 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 com- binatorial bandits [8]
14
9 1O 2T.. Other applications at the interface of bandit methodology and
economics include dynamic pricing (28) 20, [], incentivizing exploration [33 26), learning under
competition M. and learning in matching markets without incentives 19
Finally, primal-dual methods have also featured elsewhere in the bandits literature (e.g..
2
Preliminaries
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.
2.1 Matching with transferable utilities
Consider a two-sided market that consists of a finite set of customers on one side and a finite set J of providers on the other. Let A = IU J be the set of all agents. A matching X CI J is
3

---

a set of pairs (i that are pairwise disjoint, representing the pairs of agents that are matched. Let
AAA denote the set of all matchings on A. For notational convenience, we define for each matching X E LA an equivalent functional representation μx: A -> A, where μxx (i) j and px (j) for all matched pairs (i. E X, and μx (a) = a if a E A is unmatched.
When a pair of agents ( X J matches, each experiences a utility gain. We denote these utilities by a global utility function : A x 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 utilitiies to be negative, if if matching results in a net cost (e.g., if an agent is providing a service). We assume each agent E A receives zero utility if unmatched, i.e., u(a, a) O. When we wish to emphasize the role of an individual agent's utility function, we will use the equivalent notation Un (a') = u(a, a').
A market outcome consists of matching X LA along with a vector r E R-A of transfers, where Ta is the amount of money transferred from the platform to agent a for each a E A. These monetary transfers are 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 + Tj - 0 for all matched pairs (i.j) E X and Ta 0 if a unmatched. Here, X represents how agents are matched and Ta represents the transfer that agent receives (or pays). The net utility that an agent derives from a matching with transfers (X, 7) is therefore uxa, (a)) + Ta-
Stable matchings. In matching theory, stability captures when a market outcome aligns with individual agents' preferences. Roughly speaking. a market outcome (X, r) is stable if: (i) no individual agent would rather be unmatched, and (ii) no pair of agents (i. 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) is individually rational, i.e.,
ua(()((a) + Ta 20 0 for all agents a E A, and (ii) it has no blocking pairs, i.e.
(1)
(1)()x(1) + T.) + +",((x(()) + +T,) 2 u;(i) + (1)
(2)
for all pairs of agents (i.5) E I J
A fundamental property of the matching with transfers model is that if (X, r) is stable, then X is maximum weight matching, i.c., X maximizes Eae Ua (ax (a)) over all matchings X E 2AA (2)
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 [ as 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 I then Charlene would prefer Quinn, but Quinn's '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].
3 Learning Problem and Feedback Model
We instantiate the platform's '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" U J*. Each agent E AA has an associated context Ca E C, where 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 Finally, the platform receives noisy feedback about the utilities of each matched pair.
We observe that 22 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, T). Notice that a pair (i.j) violates (2) if and only if they find a transfer 7. -73 such that (j) 7 > u. (ux (1)) + 7: and u, (1) + TJ > uy (ux (i) + T3.

---

Matching market:
True utilities + stable outcome:
Platform's uncertainty sets:
Customers Providers
Customers
Providers
Customers
Providers
ue 9 pay
P
P
uc 9
up (C) = 5
(C = -
C
uq (C) -10
uq (C) -10
uc(Q) = 12
uc (Q) = 12 + 4
Q
The left panel depicts a schematic of matching (blue) with transfers (green). The center panel depicts matching market with three agents and a stable matching with transfers for that market. (If the transfer is replaced with any value between and 7, the outcome remains stable.) The right panel depicts the same market, but with utilities replaced by uncertainty sets; note that no matching with transfers is stable for all realizations of utilities.
Figure 1:
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 be sparse and noisy. For simplicity, 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 I' I customers and a set J S J providers arrive to the market. Write
I' ='''' A'. The platform observes A' and the context Ca C of each agent A'.
2. The platform selects matching with zero-sum transfers (X*,r) between I' and J
3. The platform observes noisy utilities un (fxx (a)) + &a, for each agent I J where the Ea, are independent, 1-subgaussian random variables.
4. The platform incurs regret equal to the instability of the selected market outcome (X*,
The platform's 's total regret Rr is thus the cumulative instability incurred up through round T.
3.1 Preference structure
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 Z be the set of functions u: A x A" - IR i.e., t/ 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. Specif- ically, we consider the class of utility functions Hunstructured { [u E U u(a, d') [_1, In this setup, the platform must learn each agent's utility function u.(-) 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.c., C = Bd) where Bd is the & unit ball in Rd We also assume that there exists function d: A + Bd mapping each agent to the hidden information associated to that agent. The preference class Ui can then be defined as
Ugeer E U1 u(a, a') = (Car, ②(a)) for some Φ: A - Bdd
4 Measuring Approximate Stability
When learning stable matchings, we must settle for guarantees of approximate stability, since exact stability-a binary notion- unattainable when preferences are uncertain. To see this, return to
5

---

the example from Figure 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 impossible for the platform to find an (exactly) stable matching, so it is necessary to introduce measure of approximate stability 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--i it might seem natural 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 A at time step in the bandits model.) The utility difference of market outcome (X, is
En (ulluxx(a)) - Σ va(xx(a)) + + ) aaE
max X'EZA
(3)
aEA
The first term the maximum total utility of any matching, and the second term is the total utility of market outcome 7X Since transfers are zero-sum, (3) can be equivalently written as
ua (a(xxx(a)) Σ aEA
Σ ua(ux(())
max X'EXA
BEA
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.I). Utility difference is therefore not areentvveawarg making unsuitable stable matchings with transfers.
objective for learning
In the remainder of this section, we propose measure of instability- Subset Instability- and show that it serves as a well-motivated and suitable objective for learning stable matchings with transfers.
4.1 Subset Instability
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 matching with transfers (X,+) r) is
max [
( (uxx + )
Σ _ua(ux((a)))
E'u
I(,, max SEA
X'EXS aES
LEES
(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 more extensive economic interpretation below; but before doing so, we first illustrate Definition 4.1 in the context of the example Figure [
Consider the matching X = {(C, Q)) with transfers TO = - -11 and TO = 11, (This market outcome stable for the upper bounds of the uncertainty sets of the platform in Figure [ but not stable for the true utilities.) Note that the subset S that maximizes Subset Instability is S = (C, P). in which case maxx's EnES un ( (a)) and Eaes (ux (o)) + 7.) 1. Thus, the Subset Instability of (X, is I(X, T; A) 4 = 3. In contrast, the utility difference of (X,r) is
(C,
We now give two interpretations of Subset Instability to provide further insight into why Subset Instability is 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 terms of monetary subsidies from the platform to the agents. Specifically, the Subset
Utility 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, fundamentally different measure of regret needed.

---

Instability of 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 8 E 1R22 20 denote subsidies made by the platform, where &a 2 O is the subsidy provided agent For a market outcome (X,7), r), the minimum stabilizing subsidy is
min SERC 20
Σ aE
(X,++3) is stable
where we define stability in analogy to Definition 2.1. Specifically, we say that market outcome
7) with subsidies is stable if is individually rational, i.., ua (a(xx(()) + To S 2 for all
agents E A. and has no blocking pairs, i.e., (u((xx(i) + T, + +s) + (2,( + sy) 2 u,(i) + (i) for all pairs of agents (i. 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, rewrite the minimum stabilizing subsidy as the solution to the following linear program:
Σ 80 min SERIA AI
(5)
aEA
s.t. (u,( + T; + s:) + (u,( (i) + + +s) 2 u((i + uz(
v(i,)) E J
ua(ux (a)) + Ta + sa 0
Va E A
S. 0
Va 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 's perspective, show that Subset Instability can also be interpreted as a measure of user unhappiness. Given a subset S C A of agents, which we call a coalition, we define the unhappiness of S with respect to market outcome (X, 7) be the maximum gain (relative to (X,T)) T)) 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 C A with respect to (X, r) equals the Subset Instability T(X, T.u, u, A).
The main takeaway from Proposition 4.3 platform, but also costs to users, terms of the maximum amount they "leave on the table" by not negotiating an alternate arrangement amongst themselves.
is that Subset Instability not only measures costs to the
4.2 Properties of Subset Instability
We now describe additional properties of our instability measure that are important for learning. We show that Subset Instability is: (i) zero and only if the matching with transfers is stable, (ii) Lipschitz in the true utility functions, and (ii)) 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 (X. T) is stable.
2. Subset Instability is Lipschitz continuous with respect to agent utilities. That is, for any possible market outcome (X,T), and any pair of utility functions u and it holds that:
[[XX, A; I(X, T; ū, A) 2 Σ
|ua ú lloo
aEA
3. Subset Instability is always at least the utility difference.
7

---

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 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 socially optimal matching.
5 Learning Stable Matchings in a Bandits Framework
In this section, 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 maximum weight matching, our setting has crucial differences: (i) in each round, the platform must choose Iransfers in addition to a matching, and (ii) loss is measured with respect 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 ap- proach, we derive regret bounds for the preference structures introduced in Section We start with the simplest case unstructured preferences, where we assume no structure on the utilities.
Theorem 5.1.
For preference class Munstructured (see Section 3), MATCHUCB (defined in Sec- tion 5.2 incurs expected regret of ((R)) = O(All nT log( (T))), where max, AAe-
In Section 5.3 we additionally give matching (up to logarithmic factors) lower bound showing for n = |Ai that such scaling |A| is indeed necessary. Thus, regret must scale as |AA] /n, which superlinear in the size of the market. This bound means that the platform needs to learn superconstant amount of information per agent in the marketplace. This suggests that, without preference structure, it is unlikely that platform can efficiently learn a stable matching in large market.
The next bound demonstrates that, with preference structure, efficient learning of stable matching becomes possible. Specifically, we consider separable linear preferences, where the platform needs learn hidden information associated to each agent. We show the following:
Theorem 5.2. For preference class Minear (see Section 3). MATCHLINUCB (defined Section S.2 incurs expected regret of B(Rr) = O(dv/A(d//nn nTT log((AA))) where max, [AA.].
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) constant amount of information per agent the marketplace. We interpret this as indicating that the platform efficiently learn stable matching in large markets for separable linear preferences.
5.1
Algorithm
Algorithm COMPUTEMATCH Compute matching with transfers from confidence sets
1: procedure COMPUTEMATCH
2: for (i.j) E J do
b Instantiate UCB estimates of utilities.
3:
u, UCB (j) + max max(Ci,)) u. UCB <- max (Cts)
4: (X',p) x") optimal primal-dual pair for (P) and (D) given utilities UCB D Set transfers based on (X*, "p")"") and UCB utilities.
5: for E A do
6: Ta p4 ua LCB ((xx
7: return (X",T)
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 market outcome each round. A particular consequence that any UCB-based algorithm for learning matchings in semi-bandit setting can be transformed into an algorithm for learning both the matching and the prices.
8

---

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 stable market outcome in the full information setting. Shapley and Shubik [32] show that stable market outcomes 7X correspond to optimal primal-dual solutions to the following pair of primal and dual linear programs (where we omit the round index & and consider matchings over A = -UU T):
Primal (P)
Dual (D)
max ZERI 16
Σ (c)(u:())+uppp
min PERIA aEA
Σ Pa
(KJ)
s.t.
Σ Zzij 1
VIEI
s.t. ps + Pj 2 u1()) + 4y(1)
Vi.,) EIX Va E A
Pa 2 0
JET
Z $1
VjEJ
iEI 3r 20
v(i.))
Given any optimal primal-dual solution (2,p) to (P) and (D), one can recover matching μ. from the nonzero entries of Z and set transfers Ta = Pa "4a (ax (a)) to obtain stable outcome T), Moreover, any stable outcome induces an optimal primal-dual pair p).
Overview of the algorithm. Each round, we compute matching with transfers by solving (P) and (D) for our upper confidence bounds: Suppose that we have a collection &6 of confidence sets Cij, CJ. R such that (ī)) Ct, and (t) Cy,s for all (i.j) E I x J. We use ' to get an upper confidence bound estimate for each agent's 's utility function and then compute a stable matching with transfers as if these estimates were the true utilities Algorithm [ [COMPUTTEMATCH) ATCH..
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 the following lemma, where we again omit the round index
Lemma 5.3. Suppose a collection of confidence sets '6 is such that uz( E Ci,y and uz(i) E Cj. for all (i, I x T. Then the instability of (XUCB ,UCB) COMPUTEMATCH((6) satisfies
1(X UCB. u. A²) < Σ
max max((C., (Cappptt)))))) - min miinCCappyue (Ca..xuen(aa))
(6)
GEA
To prove this, write 7 I(XUCB, , ,UCB, A²) Now, it may be tempting to bound this difference using the Lipschitz continuity of Subset Instability. However, such 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 u UCB is a pointwise upper bound on to obtain tighter analysis.
TUBUB u. A') - 1UUXUUB,,UC, ,CCB; UCB ..).
5.2 Explicit algorithms
The regret bound of Lemma 5.3 suggests algorithmic approach: each round, select the matching with transfers returned by COMPUTEM ATCH and update confidence sets accordingly. To instantiate this approach, it remains 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 ap- proach: for each utility value involving the pair (i,j) IxJ, we take length O (Vloo(( [og([AA())/a 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 (MTTCHUC
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 confidence set for each hidden vector Φaa) using a least squares estimate and use that to get confidence sets Co for the utilities. We detail this precisely in Appendix B.3

---

Algorithm 2 MATCHUCB: A bandit algorithm for matching with transferable utilities for unstruc- tured preferences.
1: procedure MATCHUCB(T)
2:
for (i.j) E x J do
Initialize confidence intervals.
3:
Ci.j - [-1, C2 6 [-1,1
4: for < T do
5:
(X 7²) COMPUTEMATCH(())
6:
for (i,5) E X do
Set confidence intervals and update means.
7:
Update empirical means ús (i) and 0g (x) from feedback; increment counter Raj-
8:
Crj - (i.(s) - 8 Cz,- (i) 8 (lolo((( ( + 8 /olog( (AT))(A))//)))))) [-11
(i( + 8 (lgg(lll()))////a
[-1.1]
9:
5.3
Matching lower bound
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 stable matching with respect to unstructured preferences has an instance on which has expected regret Q[[A 3/2 TT) (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 [1]] From this perspective, the contribution of MATCHUCB an approach set the dual variables while asymptotically maintaining the same regret as the primal-only problem.
6 Extensions
Instance-dependent regret bounds While we have focused on bounds that hold uniformly for all problem instances, we now explore instance-dependen regret bounds. Instance-dependent bounds capture 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 7) regret bounds in the full version (18).
Matching with non-transferable utilities 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 the matching with non-tran transferable utilities (NTU) model (15]. which has also been studied in a learning context [T]] [4 7 30). The
While we have focused on matching with transferable
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
this setting.
7 Discussion
We introduced a framework for learning equilibria in matching markets from bandit feedback. A core component Subset Instability, which captures the distance of a market outcome from equilibrium. Using Subset Instability as loss function, we designed UCB-based learning algorithms that optimize for alignment with agent incentives. The resulting regret bounds for different preference structures take step towards elucidating when marketplace can efficiently learn stable outcomes.
While we focused matching markets with stochastic bandit feedback in this work, we believe that the question of learning equilibria in data-driven marketplaces is much more general interest, An interesting direction for future inquiry would be explore in what other settings, and with what other algorithmic methods, can equilibria be learned?
For detailed discussion of directions for future work, see the full version of the paper 18
10

---

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-Dinner, 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.
References
[1] Guy Aridor, Yishay Mansour, Aleksandrs Slivkins, and Zhiwei Steven Wu. Competing bandits: The perils of exploration under competition. CoRR, abs/2007.10144, 2020.
[2] Itai Ashlagi, Mark Braverman, Yash Kanoria, and Peng Shi. Clearing matching markets efficiently: informative signals and match recommendations. Management Science, 66(5): 2193, 2020.
[3] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3) 256, 2002.
[4] Peter Auer, Nicolò Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(():48--)) 2002.
[5] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. J. ACM, 65(3):13:1-13:55 2018
[6] Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log (I") regret for decentralized bandits in matching markets. CoRR, abs/2103.07501, 2021.
[7] Sarah H. Cen and Devavrat Shah. Regret, stability, and fairness in matching markets with bandit learners. CoRR, Abss2102.00246, 2021.
[8] Nicolò Cesa- Basschianchi and Gábor Lugosi. Combinatorial bandits. Comput. Syst. Sci., 78(5): 1402-1422, 2012.
[9] Wei Chen, Yajun Wang. and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of JMLR Workshop and Conference Proceedings, pages 151-159, JMLR.org, 2013.
[10] Richard Combes, Mohammad Sadegh Talebi, Alexandre Proutière, and Marc Lelarge. Com- binatorial bandits revisited. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pages 1116-1124, 2015.
[11] Sanmay Das and Emir Kamenica. Two-sided bandits and the dating market. In Leslie Pack Kaelbling and Alessandro Saffiotti, editors, IJCAI-O5, Proceedings of the Nineteenth Interna- tional Joint Conference Artificial Intelligence, pages 947-952. Professional Book Center, 2005.
[12] Ehsan Emamjomeh-Zadee Zadeh, Yannai A. Gonczarowski, and David Kempe. The complexity of interactively learning stable matching by trial and error. In Péter Biró, Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia, editors, EC '20: The 2 ACM Conference on Economics and Computation, page 599. ACM, 2020.
[13] Peter I. Frazier, David Kempe, Jon M. Kleinberg, and Robert Kleinberg. Incentivizing explo- ration. In Moshe Babaioff, Vincent Conitzer, and David A. Easley, editors, ACM Conference on Economics and Computation, EC '14, pages 5-22. ACM, 2014.
[14] Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Trans. Netw, 20(5): 111114666477. 2012.
[15] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962.

---

[16] Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum. A stable marriage requires communication. Games Econ. Behav., 118:626-447 2019.
[17] Nicole Immorlica, Karthik Abinav Sankararaman, Robert E. Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 202-219. IEEE Computer Society, 2019.
[18] Meena Jagadeesan, Alexander Wei, Yixin Wang. Michael I. Jordan, and Jacob Steinhardt. Learning equilibria in matching markets from bandit feedback. CoRR, abs/2108 0.8843,, 2021.
[19] Ramesh Johari, Vijay Kamble, and Yash Kanoria. Matching while learning. Oper. Res., 69(2):
655-681, 2021.
[20] Robert D. Kleinberg and Frank Thomson Leighton. The value of knowing a demand curve: Bounds on regret for online posted- -price auctions. 44th Symposium on Foundations of Computer Science (FOCS 2003), pages 594-605. IEEE Computer Society, 2003.
[21] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvári. Tight regret bounds for stochastic combinatorial semi-bandits In Guy Lebanon and S. V. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of JMLR Workshop and Conference Proceedings. JMLR.org. 2015.
[22] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[23] Xiaocheng Li. Chunlin Sun, and Yinyu Ye. The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks. CoRR, abs/2102.06385, 2021.
[24] Lydia T. Liu, Horia Mania, and Michael I. Jordan. Competing bandits in matching markets. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages PMLR, 2020.
[25] Lydia T. Liu, Feng Ruan, Horia Mania, and Michael I. Jordan. Bandit learning in decentralized matching markets. CoRR, abs/2012.07348, 2020.
[26] Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian incentive-compatible bandit exploration. In Tim Roughgarden, Michal Feldman, and Michael Schwarz, editors, Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, pages 565-582, ACM, 2015.
[27] E. Martinez-Legaz, Dual representation of cooperative games based on Fenchel-Moreau conjugation. Optimization, 36(4):291-3)) 1996.
[28] Michael Rothschild. A two-armed bandit theory of market pricing. Journal of Economic Theory, 9(2):185-20 1974.
[29] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013, pages 2256-2264 2264, 2013.
[30] Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate or delete: Decentralized competing bandits in serial dictatorship. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1252-1220 1260. PMLR, 2021.
[31] I.. S. Shapley and Shubik. Quasi-cores in a monetary economy with nonconvex preferences. Econometrica, (4(44)8055822) 1966.
[32] L. S. Shapley and M. Shubik. The assignment game I: The core. International Journal of Game Theory, 1(1):111-30. December 1971.
12

---

[33] Peng Shi. Efficient matchmaking in assignment games with application to online platforms. In Péter Biró. Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia, editors, EC '20: The 2 stt ACM Conference on Economics and Computation, pages 601-602. ACM, 2020.
[34] Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. In Advances in Neural Information Processing Systems 33: Anmual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
13


Reviews:
[{"review_id": "s0ln_PAjFZR", "reviewer": "Reviewer_nPa8", "summary": "The paper considers two-sided platforms who seek to match users on\n  both sides under uncertainty about user preferences. The focus is on\n  the transferable utility setting, where the platform, in addition to\n  orchestrating a matching, imposes transfers between each pair (as\n  well as from the platform to the pair). After each matching, the\n  platform receives noisy (bandit) feedback regarding the utilities\n  received by each member in a matched pair. The goal of the platform\n  is to learn a stable market outcome efficiently. To capture the\n  (in)efficiency of learning, the authors introduce a measure of\n  instability of any matching, namely subsidy instability, which is\n  equal to the smallest total (non-negative) transfer the platform\n  needs to make to the users so that matching is stable. The regret of\n  any learning algorithm is then defined as the total subsidy\n  instability accumulated over a time horizon.\n\n  The authors first show that the subsidy instability is indeed an\n  appropriate notion to capture learning efficiency, by providing\n  natural economic interpretations as well as exhibiting a number of\n  smoothness properties and bounds. The authors then propose a natural\n  UCB-type algorithm, where each agent reports upper confidence bounds\n  on their preferences and the platform computes the optimal stable\n  matching and transfers under these reported preferences. The authors\n  show that this algorithm achieves an expected regret that is of\n  order $O(\\sqrt{T\\log T})$, and furthermore provide a matching lower\n  bound. (The bounds also establish regret dependence on other model\n  parameters.) ", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "* Pros:\n  - The authors consider a natural learning setting that is\n    practically important and relevant to many online platforms.\n  - The main contribution of the work is in introducing/using the\n    notion of subsidy instability to measure the efficiency of the\n    learning algorithm. Since subsidy instability accurately captures\n    the economic incentives of such platforms, exhibiting the\n    performance of any algorithm in the terms of subsidy instability\n    would be appealing to practitioners.\n  - The resulting algorithm is simple and intuitive, and uses natural\n    UCB-type ideas to achieve low regret. This simplicity would also\n    be appealing in practice.\n  - The paper is very well written, and the main results and the\n    contributions are described with clarity.\n\nOverall, the paper provides a clean and complete characterization of a practically relevant learning problem. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "guXXfblZOx", "reviewer": "Reviewer_SoA5", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros\n- The paper studies an important problem for learning in matching markets, where agents are matched, and transfers are made to distribute the generated welfare in a stable manner.  This captures many important markets as mentioned in the paper.\n- The introduction of the Subsidy Instability is interesting as it formulates the stability in two-sided markets in a centralized manner. The provided extensions show the flexibility of the proposed Subsidy Instability framework. \n- The regret upper bound and the matching lower bound in the instance independent setting highlights the optimality (orderwise) of the proposed solution.  \n- The theoretical results in the extensions cover many important settings (e.g. instance dependent, linear reward), so the work is quite comprehensive within the scope of the paper. \n- The writing is clear and easy to follow, and highlights the important aspect of the Subsidy Instability metric. \n\nDrawbacks\n-  How does the Subsidy Instability ensure (or fail to do so) the four points in the desiderata of [6]? I think parts of this is discussed in Appendix F, a summary of which is better suited for the main body of the paper. \n- The global minimization of subsidy instability does not capture fairness, as acknowledged by the authors. Some discussion on how the Subsidy Instability per agent/max-min ratio  can grow under their proposed solution will be insightful. \n- The (non)-uniqueness of the solution under Subsidy Instability needs more discussions. If the solutions are non-unique under UCB does the algorithm converge to a single solution? Some numerical validation may shed some light on this.    \n- Some discussion on the decentralization of the proposed Subsidy Instability will be useful as centralized algorithms are undesired due to privacy concerns.  \n- This paper does not mention some of the related works properly. \n1. The difference from [6] which also study the matching with transfer setting should be elaborated. (see the first bullet)\n2. The comparison with learning a stable matching in two sided market without transfer is incomplete. The results in the paper [5], [23], and [28] are not mentioned in the paper, although they are cited. Does the current formulation capture the heterogeneous ranking in both sides therein? \n3. The application of a primal-dual algorithm with bandit feedback in prior works is not discussed. Please cite the appropriate works, e.g. 'An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits', Tirinzoni et al. \n- The instance dependent regret does not capture the dependence on various reward gaps, but  just uses the minimum gap. Can this be made more finer (following Chen et al. and their gap definitions for super-arms) ? In general, the proofs of the extensions are somewhat incomplete (akin to sketches). I encourage the authors to complete the proofs in a technical report. \n\nMinor\n- In Lemma 4.4 it should be \\mathcal{A} instead of A.\n\n\nNote: All the citations are numbered according to the main paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors highlight that the paper lacks the study of fairness in utility allocation across agents of the proposed algorithm. They also discuss the scope of social impact of the paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "Naf6nklSjh", "reviewer": "Reviewer_PkCM", "summary": "This paper proposes a generalization of the stable matching problem to the case of uncertain input on agent preferences, which are learned via bandit feedback, with a loss function aiming to minimize instability. To define this loss function, the notion of transferable utility is used, whereby monetary subsidies offered by the platform to agents, in addition to transfer between those agents, quantify the instability of a certain matching.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes novel algorithms that learn user preferences via optimism in the face of uncertainty from noisy user feedback in a multi-armed bandit setting, aiming to minimize a measure of instability in lieu of producing strictly stable matchings, providing near-optimal bounds. This economically motivated formulation extends to the case of structured preferences.\n\nThe work is well motivated by the case of data-driven markets, where agents may be incentivized to participate in a matching via monetary transfers. The concept of a stable matching, whereby the sum of agent utilities is maximized, is well generalized to the case of uncertainty, where users cannot report their full preferences, and instead those are learned via bandit feebdack.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper considers  a problem where the objective is to achieve social benefit.", "review_text": "", "extra_scores": {"ethical_concerns": "The paper has a strong similarity to another NeurIPS submission. (11554)", "needs_ethics_review": "Yes", "ethics_review_area": ["Research Integrity Issues (e.g., plagiarism)"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9OV_-39BEl", "reviewer": "Reviewer_noAP", "summary": "The paper aims at learning stable matchings in settings with monetary transfers, when the learner does not initially know agents’ preferences and has to learn them over time. The authors provide a no-regret algorithm to do so, based on the idea of upper confidence bounds (UCB).", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n- I like the subsidy instability notion. I think this is a good notion of instability as it measures exactly how far you are (monetarily) from a stable solution. Proposition 3.3 strengthens this notion, by showing that the instability notion is well-behaved and upper bounds the utility difference, which implies convergence to a socially optimal matching.\n- The algorithms and results of the paper do not directly follow from applying UCB to the Lipschitz case. The authors use a primal-dual approach to compute the solutions they work with at each time step, in a way that they show reduces the size of the confidence interval at each step. The authors are then able to get an instance-independent regret of $\\sqrt{T}$.\n- The authors show a matching lower bound for the expected regret\n- The authors also provide instance-dependent bounds.\n\nMinor weakness:\n- Overall, the algorithm still follows the general idea of UCB (even if there is some additional work to make it work in this setting) and does not seem super novel. Most of the novelty seems to come from understanding the properties of their instability measure/optimization programs.\n\nTypos:\n- Is there a sum missing in Equation 2 when defining the utility difference?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal impact and fairness are not the primary concern of this paper. The authors acknowledge that computing a stable solution may come with unfairness, and that adding a fairness constraint is an interesting research direction.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers unilaterally supported the paper - the approach is simple and the introduced subsidy idea aligns well with platform markets' realities, the characterization of the problem is reasonably complete, exposition is good, and the results are clean.  The most critical reviewer, SoA5, brings up solid points about regret and exposition/motivation around the subsidy, and in future versions of this work it would beneficial for the authors to address these concerns directly.
Decision: Accept (Spotlight)