Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
Authors: Chinmay Maheshwari
Shankar Sastry
Eric Mazumdar
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stable matching
Multi-armed bandits
Decentralized Algorithm

Abstract: We study the problem of online learning in competitive settings in the context of two-sided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach to their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent's own history of play and requires no foreknowledge of the firms' preferences. Our algorithms are constructed by splitting up the statistical problem of learning one's preferences, from noisy observations, from the problem of competing for firms. We show that under realistic structural assumptions on the underlying preferences of the agents and firms, the proposed algorithms incur a regret which grows at most logarithmically in the time horizon. However, we note that in the worst case, it may grow exponentially in the size of the market.  

Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
Chinmay Maheshwari EECS
Shankar Sastry
EECS
University of California Berkeley edu
University of California Berkeley
chinmay, www..mmaasaaabbrerieeee httpwwawwwrbrrereeegeeereeeeeeee chimaayy.aheshwariieerrrr.
sastry@eecs berkeley beeeryeeecs..bbeeeeeeeee...e edu
Eric Mazumdar
CMS and Economics Caltech
mazumdar@cal edu
Abstract
We study the problem of online learning in competitive settings in the context of two-sided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches. We propose class of decentralized, communication- and coordination-fra algorithms that agents can use to reach to their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent's 's own history of play and requires no foreknowledge of the firms' preferences. Our algorithms are constructed by splitting up the statistical problem of learning one's preferences, from noisy observations, from the problem of competing for firms. We show that under realistic structural assumptions on the underlying preferences of the agents and firms, the proposed algorithms incur regret which grows at most logarithmically in the time horizon. However, we note that in the worst case, it may grow exponentially in the size of the market.
Introduction
Online decision-maie making under uncertainty is of the central problems in modern machine learning, reflecting the need for efficient and high performing algorithms for real-time learning in real-world settings. Despite being such well-researched area, there is broad lack of understanding of how to deploy online learning algorithms into settings in which they must compete with each other for resources information. Indeed, while classic problems of online learning deal with trading off the exploration of possible choices and the exploitation current knowledge (i.e., the exploration-
exploitation tradeoff Lattimore and Szepesvári (2020); [Slivkins| (2019). the addition of competition adds a new axis upon which algorithms must operate Mansour et al. (2017); Aridor et al. (2020) namely that of competing (perhaps unsuccessfully) for highly desired outcomes settling for less desired (but also less competitive) outcomes. Broadly, speaking, the dominant approach to dealing with competition in machine learning remains treat opponents adversarial CetersariaCesaa--- Bianchi and Lugosi (2006), despite a long literature in economics and game theory Littman (1994); Fudenberg et al. (1998) showing how agents who understand the competitive structure of problems can sometimes vastly outperform solutions based upon worst-case modeling.
Cesa-Bianchii
In this paper, address the problem of online learning in competitive settings in the context of two-sided matching markets. Two-sided matching markets match users on one side of the market
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

to those on the other to facilitate the exchange of goods or services. In such settings, each user on one side of the market has an inherent preference ordering for the users on the other side of the market. Since each user seeks to find their most desired match, this results in a game in which natural equilibrium that of stable matching wherein no two users would prefer switching from their current match to each other given their preferences. In seminal work, Gale and Shapley (9622) proposed a simple and effective algorithm- the Deferred Acceptance (DA) Algorithm- that users on one side of the market can implement to find such solution when every user knows their own preferences. The algorithm has been widely used in examples ranging from kidney exchanges to medical resident matching where preferences can be assigned or reported to central authority which does the matching. However, recent years have seen the emergence of a new kinds of online matching markets like online labor markets (e.g. TaskRabbit, Upwork), online dating markets (e.g. Tinder, Match.com), online crowdsourcing platforms (e.g. Amazon mechanical turk) where the users do not know their preferences apriori, and can repeatedly interact with the market to improve their match quality.
Motivated by these applications we consider a generalization of the problem studied in Gale and Shapley 1962) wherein one side of the market- the agents- do not know their own preferences, but are able to interact repeatedly with the market. In particular, we analyze a repeated game in which, at each round, agents can request to match with a user or firm on the other side of the market. If, at a given round, multiple agents request the same firm, the firm- assumed to be a myopic utility maximizer- accepts the request of its most preferred agent (who receives a noisy measurement of their utility of the match from which they can learn their preferences) and rejects the others (who receive no information about their preferences). This setup has been studied in a line of recent works on online matching markets Liu al. (2000 2021 Sankararaman et al. (2021) Basu et al. (2021).
Successful algorithms for this framework must simultaneously solve a statistical learning problem (that of learning about their own preferences) and a competitive problem (ensuring that agents get their most desired match despite the presence of other self-interested agents in the market). Previous works for addressing this problem propose algorithms that are centralized Liu et al. (2020) (whereby agents send their current beliefs over their preferences to a central platform which does the matching), require coordination between agents (i.e., choreographed set of strategies to minimize rejections) Sankararaman et al. p: [asu et al. (202I), or require agents to fully observe the market outcomes of other agents Liu et al. (222)) In contrast, the DA algorithm- which we take to be the full-information benchmark to which we compare algorithms- is (i) fully decentralized, (ii) coordination-fret and (iii) requires agents to make decisions only based upon their own history of rejections and successful matchings. Designing learning algorithms that operate under conditions (i)-(ii)) ensures scalability and privacy in large-scale systems where is unrealistic to assume that agents can keep track of all other agents' matchings. Thus in this work we focus on the question: Does there exist decentralized and coordination-free algorithms that are based only on local history of interactions and provably converges to stable matching?
Contributions. In this work we design algorithms for learning while matching in a class of structured matching markets known as a-reducible matching market:] This condition ensures that there exists an unique stable matching and encompasses many realistic preference structures including serial dictatorship and no crossing conditions Clark (2006). We show that the proposed algorithms incur a stable regret with respect to the unique stable matching that grows at most logarithmically in the time horizon. However, in the worst case it can grow exponentially in the number of agents and firms, which we believe is an artifact of the proof technique. The particular contributions of this paper are:
1. We present general framework for the construction of decentralized, communication. and coordination-free algorithms for learning while matching. In particular, we combine a index stochastic bandit module (in particular the Upper Confidence Bounds algorithm and Thomp- son Sampling) Auer (2002): Lattimore and Szepesvári (2020); Slivkins (2019) for solving the statistical problem of learning
agent's 's preferences with a path-length adversarial bandit mod- ule Bubeck et al. (2019); Wei and Luo (2018) for dealing with the competitive problem. The resulting algorithms make are fully decentralized, and communication and coordination-free since they make use of only an agent's 's history of collisions, matches, and rewards to choose which firm
'The results in this paper extend under the assumption of Sequential Preference Condition (SPC) on the underlying market (ref. Remark 5).

---

to request at a given time. Furthermore the algorithms are not require knowledge of time horizon and do not require any specific parameters of the bandit instance beyond the sub-gaussian parameter of the noise.
algorithms, in that they do
2. We show that when the agents' and firms' preferences satisfy the a a-reducibility condition and every agent uses the algorithm, the regret accumulated by any agent against the stable match is O (GlAI1F(ooo(T where A is the set of agents, F is the set of firms, A is the minimum sub- optimality gap of any agent in the market, and C. is a constant that depends on the a- reducibeee structure of the market. We note that in the worst case this constant may grow exponentially with the size of the market.
Prior work. The particular intersection of MABs and two-sided matching markets that we analyze has seen a flurry of recent works Liu et al. (2020 2021); [asu et al. (202T): Sankararaman et al.) (202T). To the best of our knowledge, Das and Kamenica (2005), presented the first numerical study on effectively using MAB algorithms to learn preferences in matching markets. However, was only recently that Liu et al. (2020) rigorously formulated the bandit learning problem in the matching markets, and generalized the notion of regret from the MAB literature to matching markets in terms of stable regret-iee ie.. the expected cumulative utility benchmarked against the expected cumulative reward that would have been received everyone in the market requested their match in a certain stable match Morcover. they proposed centralized (CB-based algorithm that facilitates the matching between agents and firms given each agents' current beliefs over their preferences and history of play, while ensuring that O [[[AA|]F || (T)) regret for UCB based algorithm, where A is the number of agents. F is the number of Firms, and T is the time horizon of the problem. In follow up work [iu et al. (2021) proposed decentralized bandit learning algorithm that allows each user to take its decision in a decentralized manner and still "converge" to stable matching while incurring ((exp log (T)) regret. However, the algorithm requires the knowledge of outcomes other firms every round, leaving algorithms that based solely on agents' own history of play as an open problem. Concurrently, Sankararaman et al. (202T) proposed an algorithm that works in phases and makes use of communication between agents coordinate agents' actions. Under this information structure the algorithm achieves O [ log(T)) regret. Moreover their guarantees require that firms have homogeneous preference over the agents (also referred serial dictatorship). Follow-up work, [asu et al. (2021) improved the regret for serial dictatorship to O ([FI] log(T)) by proposing new algorithm. Additionally, they also showed that the assumption of serial dictatorship is relaxed to a weaker structural condition then they obtain Oppoly(I (IA), (FI) lTg( regret. Even thought the proposed algorithm in Basu et al. (202T) has decentralization is a phase based algorithm where the agents act according to coordinated protocol at some rounds. In this paper we propose a simple, decentralized, communication and coordination free algorithm in which agents make use of their own local information to learn while matching. Unlike previous works Liu et al. (2020) 202T); Sankararaman et al.] (202T); y Basu et al. (202T) where the algorithms are constructed using a UCB subroutine, we also show that our algorithmic design paradigm can be also based on Thompson Sampling.
The paper is organized as follows: In Section 2 we introduce the general problem setup, introduce matching markets and discuss the structural assumptions on the preferences of agents and firms. In Section 3 we present the algorithmic design paradigm along with specific algorithm. In Section D we present the main result about the regret bound along with a brief sketch of the proof. We conclude the paper in Section 5 and also provide some future rescarch directions. Due to space limitations a detailed comparison to related works and the proofs of our results are relegated to the Supplementary material.
Organization
2 Setting
We define a two-sided market M as collection of agents A and firms F. In the setting under consideration, we assume that every agent E A has unknown preferences over firms f E F which are captured by utilities (f) E R. Moreover, no two firms give the same utility to given agent,
NNote that the stable matching need not be unique in general. Thus the stable regret has to be always specified with respect to which stable matching is being used. Typically, in literature two main stable matchings are considered namely agent optimal stable matching and firm optimal stable matching.
3

---

Le. (f( & ff f'. We assume that every agent seeks to be matched to their most preferred firm, and that firms have preferences over all the agents which are also captured by utilities Wy(a) for each a and I such that no two agents give same utility to firms i.e. " "f(a) o uy(a') Importantly, we assume that firms know their own preference orderings over agents and that there are more firms than agents, i.e. |A| & [FF. The interaction between agents and firms happens as follows: In each time step & = 1..... .,, '" every agent a E A independently requests a firm fa(t) E F. As the agents request independently, it is possible that more than one agent requests the same firm f. For f E F. let (t) == {a E A: fa = f} denote the set of agents that request firm f at time step t. At each time step t, we assume that the firm f accepts the request of their most preferred agent in (t) denoted by a (t) == arg a A (()) (a) and rejects the request of all other agents. That agent a (t) is said to be the agent who got matched with firm f at time t. Moreover every matched agent receives a noisy measurement of their utility, denoted Ua.f such that Ua.5 "a( + Sa. where Ga.f is zero-mean,
Gausssan random variable Meanwhile, all the agents that are rejected are said to have collided on firm ʃ. for which they receive no utility i.e. (1) = O.
We restrict that agents only receive the following information at any time step t:
1. (t(t) 1 (a is matched to (t)) which captures if agent a gets matched at time 2. if they get matched, the noisy measurement of their utility, (t)
Remark 1. We note that in this setup agent does not know anything about how other agents are performing in the market. Agents do not observe any information about the matching and collisions of other agents. We remark that this is the same information structure as that assumed by the DA algorithm and is the key assumption that differentiates our work from prior work on this problem Liu
al. 2020 202 Basu al. (2027) Sankararaman el al. (207))
In the following subsection, we recall some important results from matching market literature that are crucial to further exposition.
2.1 Preliminaries on matching markets
To analyze the matching market defined in the previous section we recall key concepts from the literature on matching markets. A matching M : A + Fis an injective function such that MI(a) = f denotes that a and firm f are matched. We call matching unstable if there is an agent-firm firm tuple (a, E A x F such that u.a (M)))) < (f) and (a(a) > u (M- (f)). In words, there is a pair (a, f) who both prefer each other over their current match, such pair is called a blocking pair. A matching is stable if it is not unstable. It is usually the case that market may have multiple stable matchings. However, for the purpose of this paper we focus on markets which are aereuucible, first introduced in Alcalde| (1994) and further analyzed in Clark (2006), that ensures there is a unique stable matching. Before formally deseribing this property we introduce the notion of submarket and fixed pair.
A sub-market of M is a market M' such that M' A'UF where A' C A. and |A' < FF). Meanwhile, a pair (a, f) E A x F is a fixed pair of market M un (f) u. (f') for all f' E J and (a(a)= 2 (a(a") for all a' E A. In words, fixed pair is any agent-firm pair that prefer each other over any other options in the market. We now define the notion of a aeduuiibbilit
Definition 2 (a-reducibility). A market M = AUU is a-reducible every sub-market of M has fixed pair.
One important class of markets which satisfy a-reducibility is that where one side of the market has uniform preferences over the other side. We note that every sub-market of of M has a unique stable matching if M is a-reducible Clark (2006). The preceding property of a- reducible markets will be crucial to obtain regret guarantees for the proposed algorithm in this paper. Thus, we assume that M is a-reducible
An important property of a a-reducibility assumption that is central to the subsequent analysis that it allows us to partition the market into various sub-markets by sequentially eliminating
Remark 3.
3 'Hrre we assume that the random noise is appropriately bounded such that Ua, 2 for all (a. 'We can also handle the scenarios where the underlying preferences satisfies SPC condition Clark 2006 More discussion is provided in Remark 5.
4

---

fixed pairs. More formally, lets define Ao = Fu 2 and Ma = M. Now for i 2 1 lets define inductively A, S A-
C =- be the set of agents and set of firms that constitute fixed pair in market Mi-1. That is, for every ageni a E A, there exists unique/ / E Fi such that (a, is a fixed pair of market Mi- The iteration evolves as M; == (o such decomposition of market is unique.
F Let K be the total number of such sub-marker (M.). Moreover
For any agent A we denote by fa its match in the unique stable matching. Furthermore, let F. = {J F uo(s) un ( be the set of firms that agent a prefers over its stable match. We call such firms super-oplimal firms for a. Similarly, let E, == (J E F: (f) < un (a())) be the set of firms which are less preferred than the stable match by agent We call such firms sub-optimal firms for o. Note that we have following lemma which states a crucial property of super-optimal firms for a-reducible markets.
Lemma 4. For any E [K] and agent a E A; the set of super-optimal firms are contained in U T
An immediate conclusion of Lemma is that it creates a hierarchy in the market. That is, an agent a E Ai, for some i E [K] is in a sense "higher ranked" than a agent a' E Aj for j >> i as the former's s stable match can be super-optimal for the latter. This sort of hierarchy naturally manifests itself in the learning process where learning of agent a creates externality for agent a'.
Before we formally present the algorithm, we make the following remark about the preference structure for which the results in this article hold.
The notion of a-reducibility is weaker than the no crossing condition and serial dic- tatorship Clark (2006). These conditions have been introduced in the effort to characterize the existence and uniqueness of a stable matching. We note that a-reducibility is a stricter condition than Sequential Preference Condition (SPC) Clark (2006). However, the results presented in this work extend directly under the assumption of SPC. This is because all of the results are derived based on the decomposition stated in Remark 3 which can be also obtained from the definition of SPC Clark (2006); Karpov 2019). However, as pointed out by Clark (2006), given any population P of agents hipha-reducibilae is necessary and sufficient condition for unique stable matching regardless of subpopulation sampled from P. However, this property does not hold for SPC.
Remark 5.
For ease of reference, all key notations used in paper are presented in a table in the Supplementary
material.
3 Algorithms
In this section we present a novel algorithm design principle for agents to learn about the preferences while ensuring that they perform competitively against the match that they could have achieved if they knew their preferences and used the DA algorithm. Throughout this section, we assume that every agent a E AA uses these algorithms in order to decide which firm choose any time The proposed algorithms-by design- make use of only the feedback information outlined in - in Section 1, and have no implicit or explicit communication and coordination strategies like e-g.. phase based strategies with coordinated actions Basu et al.] (2021) or partial observation of actions of other agents [iu et al. (202I) etc. Thus, the algorithms operate in the same regime as the DA algorithm, but without the assumption that agents know their preferences. Key to our approach, is the blending stochastic bandit (SB) algorithms with an adversarial bandit (AB) algorithms. In the subsequent exposition we will formally describe our approach and show its desirable properties in terms of regret and convergence.
Before doing so, however, we comment on the difficulties of the problem at hand, and what makes the analysis of these algorithms highly non-trivial. The key challenge in designing algorithms for matching while learning is understanding when to stop requesting super-optimal firms (i.e. firms that they prefer more than their stable match) without any foreknowledge of the market structure. The crux of this problem is having an agent learn that certain firms are unattainable due to competition despite the non-stationarity in the environment stemming from fact that other agents are learning simultaneously and not knowing who they collide with and who is successfully getting matched at each round. Furthermore, due to a lack of communication or coordination, agents cannot learn about which firms are super-optimal without risking many collisions.
5

---

A sketch of the algorithm is described in words in Algorithm 1 and the exact algorithm for the setting which agents use the UCB algorithm as subroutine presented in Algorithm 2 A corresponding version of algorithm with Thompson sampling based stochastic subroutine is presented each agent is equipped with stochastic bandit (SB)
in Supplemental material. As per Algorithm 2
Algorithm 1: High-level algorithmic description
Each agent a E A at every time E [T]:
1. Keeps an ordering of firms as per an index-based stochastic bandit subroutine
Agent a goes over the firms as per the ordering one by one
3. Using adversarial bandit subroutine decides whether to request the firm to prune it
(a) If firm is requested then agent either gets matched gets collided
(b) If pruned then then the agent moves to next firm as per the ordering in Step
4. Updates the stochastic and adversarial bandit subroutine based the feedback received
subroutine. At every time step t E [T], the SB subroutine every agent a maintains ordering of firms in decreasing order of preferences according an index (e.g. UCB). We denote this index of firm as maintained by agent as r()) Next, at that time step, every agent considers each firm one by one in decreasing order of (t). For any firm ff considered by agent
time I, the agent makes decision either request or to prunc it (that is, reject that firm). In particular, agent a requests firm f with probability pa, Let (t) ~ Bernoulli(pa. (t)). If a firm is pruned (i.e. Pa. (t) 0) then the next best firm from the sorted list is chosen and the process continues until a firm is requested (i.e. (t) = 1). However, if all of the firms are pruned then at that time instant the agent simply requests the firm arg max, UCB.,,, (t). Once an agent decides which firm to request, it obtains a noisy utility if it gets successfully matched. This feedback is used by the agent to update its UCB-inde index. Based on whether an agent decides to prune or request particular firm f. updates Pa.s using an AB subroutine. The details about this are stated in Section 3.2 We note that all firms are considered by agent a at every time t. Once an agent decides to request a firm f. it does not consider firms in the set {ʃ' E F UCB (t) < UCB (()). Formally, for any agent-firm tuple (a, f) E A let the event that the agent a considers the firm f at time f, to decide whether to request it or prune it, be denoted by Ei.) (1) = (Pa, (4) = 0, A s UCB S UCB a. (1)) If a firm f is considered by agent a then the event when agent requests f is denoted by E (1)
(1a)(()= 1, (10) (1) 11)
In Section we describe the UCB computation method for the SB subroutine. Finally, in Section
3.2 we illustrate how the matchings and collisions used to update the probability Pa. (t) as per an AB subroutine.
3.1 Stochastic Bandit Subroutine
The stochastic bandit subroutine is used to efficiently deal with inherent uncertainty in the payoff obtained upon successful matching. In this section we develop the theory for the setting in which agents use UCB based SB subroutine. Similar results for Thompson Sampling are supplied in the supplementary material.
To begin, we denote the number of times agent gets successfully matched with firm f till time t as Ma. (t). Similarly, the number of times agent a gets collided with firm till time t be Ca, Given this notation, the UCB Auer (2002) estimate of agent a for every f at time t is given by
2 log((1 + M, log" (Maa)
UCB -a., (1-))
Ma,
$ 'Note that by pruning here we not mean permanent pruning. used to describe that a particular firm not consider at that time step 'The corresponding algorithmic subroutine 1B__ouuuue is presented in the Supplementary material.

---

Algorithm 2: UCB based Decentralized Matching Algorithm (UCB-DMA)
Pa.f 0, Ma.f PaP 0.5, Fa.f 0.5, T.a.f 0, Va E A. E for i 1
Initialize:
do
for E do
Set UCB..f = Po.f + 2lo((1 (M,)) log " (MM.)
where Mo = -ESF Ma.1
Ma.
end
Set ArgUCB = ArgDescendingSrt((CC,,, (EF) and
while I | do
Set f = ! and sample Pa.s Bernoull((pa.))
if Pa. 0 then
Update (Fa.f (Za.f-Pa.f) Iaa.f) - AB [B__Subroutine fa, Fa Pa.f La.f Ya) end pa, then
11
Request firm and receive (U Y.)
13
Ma, --1 + (1 - Ya) Ya) Ma.s - Ma.f f + Ya. AB Subroutine(Pa,, Pa.j.Po.1 La. Ya) Update (Fa. Pa.s La.
Update Po.s - Yu Po. Ma,
14
15
break while;
16
end
17
i+1
end
19
if
F + then
Request firm ArgUCB!" and receive (Ua: Ya)
20
Update Pa. -- Yo P tU + (1 Ya)Pa. Ma.s - Ma. + Ya
21
Ma
end
23
end
where Mt(t) = E (t) and Pa. 1) are the total number of successful matches for agent a and the empirical average of the payoffs received from successfully matching firm f until time f respectively. The UCB estimate is composed of two parts: (i) the empirical mean which captures the exploitation aspect; and (ii) exploration bonus that decreases as Ma. increases. We remark that it does not depend on the number of collisions (t).
3.2 Adversarial Bandit Subroutine
A key component of the proposed methodology is to use an adversarial bandit subroutine to deal with the competitive aspect the problem. particular, the AB subroutine updates the request probability (Pa.f)fEF such that agent stops requesting firm on which the collisions are high (but ensures that it does not miss out on the firm if achievable). Intuitively, by construction, algorithm learns to prune firms on which collisions would happen frequently, and request firms where it is possible to successfully match very often. We show this by analyzing its regret and showing that high regret is incurred if the algorithm either prunes too often when successfully matching is possible or requesting a firm that is unachievable due to the frequent presence of higher ranked agents. By bounding the regret of the AB subroutine we immediately get bound on the number of collisions.
adversarial bandit
We now describe the update scheme for Pa. (t) for any (a, f) at any time E [T] In this work we consider an optimistic mirror descent based AB subroutine specialized from Bubeck et al. (2019). Interestingly such AB algorithms have data dependent regret bounds Wei and Luo (2018): Bubeck et al. 2019) unlike other AB algorithms like Exp3] Lattimore and Szepesvári (2020): Slivkins (2019). Since the competition the matching market is not actually adversarial such data-dependent regret bounds enables us characterize the competition more effectively in the analysis than just treating

---

competition as adversarial" 7 We note that the proof techniques developed here can also be used to analyze an Exp3 based AB subroutine but the regret bounds of such an approach will not be as sharp.
For a given agent a, our algorithm associates a separate AB subroutine to every firm f E F. Each AB algorithm has two arms which correspond to the action of requesting the firm I or pruning it, each of which incurs different losses depending. In particular, if (t) = 0 then it receives fixed the loss received +1 or -1 if it collides or matches respectively. If we denote the loss received by the AB subroutine associated with (a, f) at time ć by La, (t), we note that La, (t) = / (t) (1 (t)) Note that Ya is unknown to any agent before requesting any firm as it also depends on the requests made by other agents.
loss of O; if 5 (t)
We note that the request probability Pa.f is not updated at every time t, but only when F (t) = 1 (i.e., if all firms with a higher UCB index have been pruned). As such the adversarial bandit algorithms can be seen operating on random timescale Ta (2) {t E [T' E (t) 1} which are the time steps on which agent a considers firm f. We note that for any (T) we have Pa, (1 + 1) Pa.s (().
For the specific AB algorithm we analyze (which is version of optimistic mirror descent with log-barrier regularizer first analyzed in Wei and Luo (2018)), the simple setup of the losses leads to closed form update for the probability of requesting or pruning firm. In particular, for every f) E A x F and t E Ta.r (T). the optimistic mirror descent AB subroutine creates an unbiased estimate of the loss due to pruning and requesting i (((pun))(t))
(t) and _
(t) respectively. In
particular, if Pa. (t) =1
(iorume (t) + (t aaf
1 - -t) - -ta + 1 La, - (1)
i( (t)
2
2
On the other hand, if Pa,s(() = 0 then
-La (t 1)
1 (t-
1 1 La. - 1)
(oruune) (t) 2(1 Po,, (t))
i 100.0 (t)
2
2
The term 1+ (tt,)(t-1) is an optimistic prediction of the losses based on the last round of interac-
tion Bubeck et al. (2019). Given these estimators the probability of requesting firm is updated as:
Pa, + = (1-Aa, -o.. (1)) + A (t),
where:
Ka. (t) = (2 E(t) - /
- E(t))
(2E(t))
for E(t) 17 (1.0.))) (1) (1)-L,
(prune) i a.
(1) [a,(1-1] 1-2a,f(1-Ij is the result of a step of mirror de- X(1Lo,,
scent with the log-barrier regularizer, and (1) = 2+ ((1))) for À > 0, promotes exploration.
The algorithmic description of this process is stated in the Supplementary material.
4 Regret bounds for decentralized matching algorithms
To capture the performance of the algorithm we use the natural notion of stable regret as introduced in Liu et al. (2020). More formally, the stable regret accrued by any agent E is
T
T
RR (T)) = E
f.)
S Σ (T()) + the (Fa) Σ ((Ca,,(T),, FEF
JEE.
(4.1)
where = (f()) Ura u.( the gap between the mean that agent a gets upon successfully matching with its stable match compared firm f. If there are no collisions, then this regret definition is same as that used in stochastic bandits literature (Lattimore and Szepesvári (2020). In
=
the following theorem, we present the regret of any agent using Algorithm
We review the required background on optimistic mirror descent based AB algorithms in the Supplementary material along with a result which captures the corresponding data- data-dependent regret bounds in the setting of matching markets.
8

---

Theorem 6. Suppose every agent A uses Algorithm
2
Then for any E [K]
ΣΣ J=1 aE
B (T)] =
(G)F)LA -CCIFFAAlO)))
(1+
A2
where A = m f and C iB for some positive scalar 0 1. Note that C1 < C2 <.. Cк.
We see that the regret of any agent a E A is logarithmic in horizon T. which matches the lower bound for single player stochastic bandit algorithms Lai and Robbins (1985). As such, perhaps surprisingly, observe that in a-reducible markets, it is possible for agents to learn while competing without incurring drastically worse regret in the long run. is interesting to note that the learning of agent depends its position in the market per preferences (Remark B). An agent low in the hierarchy incurs more regret during the learning process due to the agents higher up in the hierarchy driven mainly by the larger number of collisions incurred while waiting for agents higher in the hierarchy to stop exploring. We note that in the worst case the constant C₁ can grow exponentially in the number of agents in the market. We note that this is consequence of the proof technique and fundamental limitation of the algorithmic design paradigm as we show in the supplementary material through numerical studies. We leave this future work establish tighter regret bounds in terms of number of agents. In the supplementary material we also show that in Algorithm 2 if we use a SB subroutine based on Thompson Sampling then similar regret guarantee can be obtained. We now present a sketch of the proof of Theorem
Sketch of the proof. Before presenting the sketch, we first define few notations that would make the exposition clear. Let Ma,F, (T) = >EE,, Ma.j (T') M (T) = >xEr_ MT) Moreover, for any A define Ha.r:(t) Aa' s.t. uz-(aa) 2 uy; (a), that characterizes any other more preferred agent has requested the stable match of agent a at time t. Against the preceding backdrop, we present the following crucial lemma:
f} which is an event
Lemma 7. Suppose every agent uses Algorithm 2
(LI) For any [K]. the cumulative regret be decomposed
(R) O
Σ 1 REA:
Σ
[E|M,F (T))+
Σ
B|Ca. (T)
E
H Ha (t1)
JEF
1=1
(L2) For any E [K], the expected matches with suboptimal firm satisfies
(1 (1+
11))
Σ E[Mog, (T)] 0 Σ Σ jla
[L log())
+
Σ Ho (t)
A
J=1 aEA;
(L3) The expected number of collisions between for any agent E A satisfies
E(Ca,, (IFT)1O((T)
Σ
+ E Ma,F (T) + M Mo.F. (T) + Σ (Ha
SEF
(L4) For any E [K] we have
Σ LAsl log(T) (1+ (1+22)
ΣΣ E
= (I
jE,
where C₁ is constant dependent market M, such that C1 < ... Ck.
(L5) For any E [K] we have
ΣΣΣ (T) C, Σ 1411 [ log(() (1+ (1+12))
j=1 FER
1=1

---

Theorem 6 is proved using (L1)-(L5) from Lemma Note that (L1) follows from (4.1) and the definition of Ha.s; (t). From (L1) we see that to bound the regret we need consider three components: (i) expected number of matchings with suboptimal firms, (ii) expected number of collisions with any firm other than stable match, (iii) the potential collisions at the stable matel (I.2) bounds the expected number of matchings with suboptimal firms. Note that the total matchings
between agent and firm f is (T) = -Em= 1 (Ya(t)= = 1, fa(t) f). Thus, we present the following lemma which plays a key role in the proof of (1.2):
Lemma 8. The event that agent chooses the firm E F. and successfully matches at time t E [T] satisfies
(Ya(t) = - - c (Ya() = (I & UCB,,,(t) U = a. (t) = 0}
Lemma [ separates the challenge associated with uncertainty and that of competition. Note that the first event on the right hand side is the one which is standard to the analysis of UCB algorithm (Lattimore and Szepesvári (2020). Meanwhile, the other event corresponds to the case when the stable firm is pruned by agent in order to avoid potential collisions. To bound latter event use the regret bounds for the adversarial bandit subroutine (refer to Appendix).
To bound (I.3) we use the path length based regret bounds Bubeck et al. (2019): Wei and Luo (2018) for the adversarial bandit subroutine. Meanwhile to bound (L.4) we use the a- reduciblity assumption and (L2). In particular, the a aerecuciblity assumption induces a hierarchy in the market as per Remark 3 This decomposition reduces the bound in (L.4 to appropriate accounting of number of matches with suboptimal firms via an induction argument. Finally, (LS) follows again due to hierarchy induced by reduciiibylty and using (I.2)-(IA).
5 Conclusions
We consider a problem of bandit learning in two-sided matching markets comprising of agents and firms. We consider the setting where agents have unknown preferences over the firms. In this paper, we present simple design principle for decentralized, communication and coordination free algorithm for learning in two-sided matching markets. The primary challenge in learning in two-sided matching market is to balance exploration, exploitation and collision avoidance. We embed the aforementioned properties in the algorithm by a novel idea of blending a stochastic bandit subroutine with an adversarial bandit subroutine. The stochastic bandit subroutine is required for balancing the trade-off while the adversarial bandit subroutine limits the collisions. As an instance of this design principle, we present an algorithm which has the stochastic bandit subroutine based on UCB and the adversarial bandit subroutine based on Optimistic Mirror Descent algorithm. We show that if the preferences of agents satisfy certain structure known as a-reducibility (or SPC condition), then these algorithms incur a regret which is logarithmic the time horizon. However, in the worst case, the regret may grow exponentially in the size of the market. We believe that this is an artifact of proof technique and not the limitation of algorithmic design.
There are several directions in which this work can be extended in future. First, it would be an interesting avenue of future research to improve the dependence of regret bound on size of the market. We believe the worst case exponential dependence on number of agents is an artifact of the current proof technique. Second, it would be also interesting to relax the imposed structure on matching markets. Specifically. it would be interesting to extend the results to the setting when the underlying preferences satisfy a a-condition Karpov| (2019) which a necessary and sufficient condition for uniqueness of stable matching. Lastly, it would be also an interesting direction of research to develop decentralized algorithms when both sides of the market are simultaneously learning. The scenario where firms are also learning their preferences in non-trivial extension of this work as the firms may incorrectly prefer suboptimal firms which may turn lead to wrong feedback to agents.
Acknowledgments and Disclosure of Funding
Research is supported in part by NSF grant DMS 2013985 "THEORINet: Transferable, Hierarchical, Expressive, Optimal, Robust and Interpretable Networks" and C3.ai Digital Transformation Institute.
*by potential collision at stable match we mean total number of collision that would have been faced by an agent its stable firm had always requested the stable firm
10

---

References
Alcalde, J. (1994). Exchange-prooffess or sevoorc-prroffesss stability in one-sided matching markets. Review of Economic Design, 1:275-28: 287.
Aridor, G., Mansour, Y., Slivkins, A., and Wu, Z. (2020). Competing bandits: The perils of exploration under competition. arXiv preprint arXiv:2007.10144,
Auer, P. (2002). Using confidence bounds for exploitation-expplraaioo trade-offs. Journal of Machine Learning Research, 39N0v):397-422.
Basu, S., Sankararaman, K. A., and Sankararaman, A. (2021). Beyond log-squared regret for decentralized bandits in matching markets. arXiv preprint arXiv:2
Bubeck, S., Li, Y., Luo, H., and Wei, C.-Y. (2019). Improved path-length regret bounds for bandits. PMLR.
In Conference On Learning Theory, pages
Cesa-Bianchi, N. and Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.
Contributions to Theoretical Economics, Clark, S. (2006). The uniqueness of stable matchings. 6:1283-1283.
Das, S. and Kamenica, E. (2005). Two-sided bandits and the dating market. In IJCAI, volume 5, page 19. Citeseer.
Fudenberg, D., Drew, Levine, D. K., and Levine, D. K. (1998). The theory of learning in games, volume 2. MIT press.
Gale, D. and Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15.
Karpov, A. (2019). A necessary and sufficient condition for uniqueness consistency in the stable marriage matching problem. Economics Letlers, 178:63-65.
Lai, T. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in applied mathematies, 661):4-22.
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Littman, M. L. (1994). Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier.
Liu, T., Mania, H., and Jordan, M. (2020). Competing bandits matching markets. In International Conference on Artificial Intelligence and Statistics, pages 1618-1628. PMLR.
Liu, L. T., Ruan, F., Mania, H., and Jordan, M. I. (2021). Bandit learning in decentralized matching markets. Journal of Machine Learning Research, 22(211):1-34.
Mansour, Y., Slivkins, A., and Wu, Z. S. (2017). Competing bandits: Learning under competition.
arXiv preprint arXiv:1702.0855:
Sankararaman, A., Basu, S., and Sankararaman, K. A. (2021). Dominate or delete: Decentralized competing bandits in serial dictatorship. In International Conference on Artificial Intelligence and Statistics, pages 1252-1260. PMLR.
Slivkins, A. (2019). Introduction to multi-un armed bandits. arXiv preprint arXiv:1904.07272.
Wei, C.-Y. and Luo, H. (2018). More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pages 1263-1291. PMLR.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proofs of the results are included in the supplementary material. Also a sketch of the proof is provided in the main text.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "uKUWJp8_2Rw", "reviewer": "Reviewer_iWYr", "summary": "This paper presents the first framework for constructing decentralized, communication, and coordination-free algorithms for learning while matching. It blends the stochastic bandit algorithm with the adversarial bandit algorithm to solve the statistic problem of learning preference and the competitive problem with other agents respectively. Furthermore, this paper proves an O(C_\\alpha |A| |F| \\log(T) / (\\Delta^2)) regret when the matching market satisfies \\alpha-reducible condition.", "questions": "1. What’s the regret bound of each single agent? Theorem 5 only provides the regret bound for a summation over a set of agents.\n\n2. Why does this paper study markets under the \\alpha-reducible condition, as there are some more general conditions that can guarantee a unique stable matching like SPC and alpha-condition? What makes it hard to analyze the algorithm under those conditions?\n\n3. Could the author explain the constant C_\\alpha in more detail? It would be better if the author could give the explicit form of C_alpha and explain how it depends on the market.\n", "limitations": "This paper focuses on the theoretical analysis and there is no potential negative societal impact. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The contribution of this paper is important since it is the first to propose a decentralized, communication, and coordination-free algorithm for the matching while learning problem.\n\n2. The method that blends the stochastic with adversarial bandit problem is new to handle the learning while matching problem. It gives others an interesting idea to design algorithms when in the face of competition.\n\n3. The submission is technically sound. All claims are well supported by solid theoretical analysis.\n\n4. The structure of the manuscript is well-organized.\n\nWeakness:\n\n1. I think the \\alpha-reducible condition, the structure assumption of the matching market in this paper, needs more explanation. It would be better if the author could explain its rationality in more detail, and give some real-life examples that satisfy the \\alpha-reducible condition.\n\n2. The constant C_\\alpha in the regret bound may grow exponentially in the number of agents, which is a large constant.\n\n3. It would be better if the result could be extended to some weaker conditions such as SPC and \\alpha-condition.\n\n4. The experiment lacks some comparisons with existing algorithms. Moreover, it could be better if the author could list the preferences of each agent and firm in the experiment, and explain how this market satisfies \\alpha-reducible.\n\n-----\nI rechecked the result and thought the exponential term in the regret bound would be an unsatisfying issue.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "uAqzPUv5PI", "reviewer": "Reviewer_kLiZ", "summary": "This paper studies the bandit learning problem in matching markets. They propose a decentralized, communication- and coordination-free algorithm, which to the best of knowledge is the first such type algorithm in decentralized matching markets. The algorithm consists of both stochastic bandit technique to learn players’ unknown preferences and adversarial bandit technique to deal with the collision among players. They also derive O(log T/\\Delta^2) stable regret for markets satisfy \\alpha-reducible preferences. ", "questions": "Please see above weakness. \nCoordination: \nI have a question on how to understand the ‘coordination-free’? Previous works though need a common communication phase, the only assumption lies in that all agents have common timesteps and common indexes toward arms. So I am wondering that can the proposed algorithm work (or similar results be derived) when different agents come at different round? For example, agent 1 enters in the market in the first round, agent 2 enters in the 100 rounds and so on. \n", "limitations": "The work is about online learning theory and does not have negative societal impact.  ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \nThis paper study a new aspect in online matching markets: whether an algorithm can achieve sublinear stable regret without communication and coordination among players. I think such attempt in the most challenge learning environment is worthwhile. \nThe algorithm framework is novel in the literature of online matching markets. It looks at players’ learning and conflict from a new perspective different from previous works. It proposes to use stochastic algorithm to deal with the learning and adversarial algorithm to deal with the conflicts. And the proposed algorithm can work with both UCB and TS stochastic algorithms. I think the work is a novel combination of well-known techniques. \nWeakness:\nThe paper should clearly illustrate the alpha-reducible term C in the regret upper bound. During the full paper, I do not see any detailed formula about C. And since C also depends on the market size, it should not be simply regarded as an unimportant constant term. \nIn line 134, it states that players’ utilities are captured by a real value in R. However, in Line 148, it shows that players will receive 0 reward if it fails the conflict. If the utilities on arms are lower than 0, it seems that the player prefers to be single than being matched with any arm. Is there any error?\nTypo:\nAlgorithm1 line 1: a-> an\nLine 3(b) repetitive then\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "tfiniwh6BaZ", "reviewer": "Reviewer_JTGG", "summary": "The paper studies a stable matching problem where the agents have to learn their utilities for the firms. The learning process progresses in rounds. In each round the agents can each propose a firm that they want to be matched to. The firm picks their favorite agent from the set of requests they receive. Agents who are selected by the firms receive a noised measurement of their utility while all the other agents receive nothing. Moreover, the agents act independently and simultaneously in each round. The paper proposes a decentralized algorithm to learn the stable matching and shows that it gives sublinear regrete against the stable matching. ", "questions": "- How crucial is the assumption of $\\alpha$-reducibility? If it does not hold, is there any conjecture whether similar learning outcome can be achieved? \n\n- Can the algorithm be easily extended to the setting where the firms also receives noised utilities?", "limitations": "The authors didn't discuss limitations or negative societal impact specifically. However, I don't find any immediate negative societal impact of this work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The problem is a natural generalization to the stable matching problem in the full-information setting. The setting is realistic and interesting. The presentation is clear and the paper is easy to follow overall, though at times it requires some domain specific knowledge. \n\n- The results look sound. The algorithm presented is a strong one in that it requires no coordination and communication. \n\nWeakness:\n\n- The subroutine part is a bit dense and the main idea does not stand out as clear as that in the previous section. I didn't check the technical details of this part carefully as a result.\n\n- There are quite some typos. The authors may want to polish the paper a bit more. For example:\n\n    - Line 52: \"This setup serves has been...\" \n    - Line 198: \"at time any time...\"\n    - Algorithm 1, Line 1: \"a ordering\" --> \"an ordering\"\n    - Line 235: \"in the Section 3.1\", remove \"the\"", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lQR0Dv2Y25w", "reviewer": "Reviewer_wFQg", "summary": "This paper studies the problem of online learning in competitive settings in two-sided $\\alpha-$reducible matching markets. A general framework for the construction of decentralized, communication, and coordination-free algorithms is presented. It is shown that  the proposed algorithms incurs a regret which grows at most logarithmically in the time horizon under certain conditions.", "questions": "No question.", "limitations": "Not applicable.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The considered topic is relevant and the key questions that the paper aims to address are well-motivated. The theoretical claims are interesting and appear to be sound. However, I am not knowledgable about this area. Thus, to me, the significance and novelty of this paper are difficult to assess. As for presentation, the paper is well-written and generally easy to follow (even for a non-expert like me).  \n\n \n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept