Bandit Learning in Many-to-one Matching Markets with Uniqueness Conditions
Authors: Liya Guo
Zilong Wang
Junming Yin
Shuai Li
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Multi-armed Bandits
Many-to-one Matching
Uniqueness Conditions

Abstract: An emerging line of research is dedicated to the problem of one-to-one matching markets with bandits, where the preference of one side is unknown and thus we need to match while learning the preference through multiple rounds of interaction. However, in many real-world applications such as online recruitment platform for short-term workers, one side of the market can select more than one participant from the other side, which motivates the study of the many-to-one matching problem. Moreover, the existence of a unique stable matching is crucial to the competitive equilibrium of the market. In this paper, we first introduce a more general new \textit{$\tilde{\alpha}$}-condition to guarantee the uniqueness of stable matching in many-to-one matching problems, which generalizes some established uniqueness conditions such as \textit{SPC} and \textit{Serial Dictatorship}, and recovers the known $\alpha$-condition if the problem is reduced to one-to-one matching. Under this new condition, we design an MO-UCB-D4 algorithm with $O\left(\frac{NK\log(T)}{\Delta^2}\right)$ regret bound, where $T$ is the time horizon, $N$ is the number of agents, $K$ is the number of arms, and $\Delta$ is the minimum reward gap. Extensive experiments show that our algorithm achieves uniform good performances under different uniqueness conditions.

Bandit Learning in Many-to-one Matching Markets with Uniqueness Conditions
Anonymous Author(s)
Affiliation Address email
Abstract
An emerging line of research is dedicated to the problem of one-to-one matching markets with bandits, where the preference of one side is unknown and thus we need to match while learning the preference through multiple rounds of interaction. However, in many real-world applications such as online recruitment platform for short-term workers, one side of the market select more than participant from the other side, which motivates the study of the many-to-one matching problem. Moreover, the existence of unique stable matching is crucial to the competitive equilibrium of the market. In this paper, we first introduce a more general new â- condition to guarantee the uniqueness of stable matching in many-to-one matching problems, which generalizes some established uniqueness conditions such as SPC and Serial Dictatorship, and recovers the known a-condition if the problem is reduced to one-to-one matching. Under this new condition, we design an MO- UCB-DE algorithm with O
2
6
10
11
12
NK log(T) regret bound, where T is the time horizon, A=
13
N is the number of agents, K is the number of arms, and A is the minimum reward gap. Extensive experiments show that our algorithm achieves uniform good performances under different uniqueness conditions.
15
Introduction
The rise of platforms for the online matching market has led to an emergence of opportunities for 18
companies participate in personalized decision-making [1 [8]. Companies (like Thumbtack and Taskrabbit and Upwork platforms) use online platforms to address short-term needs or seasonal spikes production demands, accommodate workers who voluntarily looking for more flexible work arrangements or probation period before permanent employment. The supply and demand sides in two-sided markets make policies on the basis of their diversified needs, which abstracted 23
19
20
21
22
24 as matching market with agent side and arm side, and each side has preference profile over the opposite side. They choose from the other side according to preference and perform matching. The stability of the matching result is key property of the market 132 27
25
26
27
The preferences in the online labor market may be unknown one side in advance, thus matching while learning the preferences is necessary. The multi-armed bandit (MAB) [36] 13
4 is an important adaptively from 30 received rewards at each round. The idea of applying MAB to one-to-one matching problems,
28
29 tool for N independent agents in matching market simultaneously selecting
31 introduced by (2I). assumes that there is central platform make decisions for all agents. Following
32 this, other works [22 34, [ consider a more general decentralized setting where there is no central
33 platform arrange matchings, and our work is also based on this setting.
34 However, it is not enough to just study the one-to-one setting. Take online short-term worker employment example, it is online platform design with iterative matching, where
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

36
employers have numerous similar short-term tasks or internships to be recruited. Workers can only choose one task according to the company's 's needs at a time while one company can accept more than one employee. Each company makes a fixed ranking for candidates according to its own requirements but workers have no knowledge of companies' preferences. The reward for workers is comprehensive consideration of salary and job environment. Since tasks are short-term, each candidate can try many times in different companies to choose the most suitable job. We abstract companies as arms and workers agents. Each arm has a capacity q which is the maximum number of agents this arm can accommodate. When an arm faces multiple choices, it accepts its most preferred agents. Agents thus compete for arms and may receive zero reward if losing the conflict. It is worth mentioning that arms with capacity q in the many-to-on matching can not just be replaced by q independent individuals with the same preference since there would be implicit competition among different replicates of this arm, not equal treatment. In addition, when multiple agents select one arm at time, there may be collision, which will hinder the communication among different agents under the decentralized assumption. They cannot distinguish who is more preferred by this arm in one round it can accept more than one agent while this can be done in one-to-one case. Communication here lets each agent learn more about the preferences of arms and other agents, so as to formulate better policies to reduce collisions and learn fast about their stable results.
37
38
39
40
41
43
45
46
47
49
50
51
52
53
This work focuses on a many- many-to-on to-one market under uniqueness conditions. Previous work [0 15 emphasize the importance of constructing unique stable matching for the equilibrium of matching problems and some existing uniqueness conditions are studied in many-to-one matching, such as Sequential Preference Condition (SPC) and Acyclicity 126 2) Our work is motivated by [7], but the unique one-to-one mapping between arms and agents in their study which gives a surrogate threshold for arm elimination does not work in the many-to-one setting. And the uniqueness conditions in many-to-one matching are not well-studied, which also brings a challenge to identify and leverage the relationship between the resulting stable matching and preferences of two sides in the design of bandit algorithms. We propose an a-condition that can guarantee a unique stable matching and recover a-condition [9) if reduced the one-to-one setting. We establish the relationships between our new â-condition and existing uniqueness conditions in many-to- one setting.
55
56
57
58
59
80
61
62
63
64
In this paper, we study the bandit algorithm for decentralized many-to matching market
65 with uniqueness conditions. Under our newly introduced â-condition, we design an MO-UCB-DD
86 algorithm with arm elimination and the regret can be upper bounded by O NN log(T) where N
67 is the number of agents, K is the number of arms, and A is the minimum reward gap. Finally,
68 we conduct a series of experiments to simulate our algorithm under various conditions of Serial dictatorship, SPC and â-condition to study the stability and regret of the algorithm.
70
The study of matching markets has long history in economics and operation allocation, and so on with real applications like school enrollment, labor employment, hospital resource 31] A salient feature of market matching is making decisions for competing players on both sides 36 12). MAB is an important tool to study matching problems under uncertainty obtain a maximum reward, and upper confidence bound algorithm (UCB) is typical algorithm, which sets a confidence interval to represent uncertainty. Matching market with MAB is studied in both centralized and decentralized setting 21 22 Following these, Abishek Sankararaman or time horizon, and reduce the probability of linear regret through non-monotonic arm elimination.
Related Work
71
research 8 6 322
72
73
74
75
76
77
et al. 34 propose a phased UCB algorithm under a uniqueness condition, Serial Dictatorship, to manage collisions. They solve the problem of the decentralized market without knowing arm-gaps
78
79
80
The introduction of the uniqueness condition plays an important role the equilibrium of matching results [1. Under a stronger and robust condition, Uniqueness Consistency [19], Soumya Basu ct. apply MAB to online matching and obtain robust results that the subset of stable matchings being separated from the system does not affect other stable matchings.
81
82
83
as prooponii- 85 the one-to-one setting has limitations in practice. Somouaoga Bonkoungo 99 runs
84 We discuss many- problems such as online short-term employment and MOOC
86
deferred acceptance algorithm (DA) [12] to study decentralized college admission. Ahmet Altinok
87
3 considers dynamic matching in many-to-one that can be solved as if it is static monee or dynamic one-to-one under certain assumptions. As the existence and uniqueness of competitive equilibrium and core are important to allocations, the unique stable results need to be considered [27]. Similar to conditions for unique stable matching in one-to-one, some uniqueness conditions of stable
88
89
90
91
results in the many-to-one setting also are studied [[6] 28 15 2 27

---

2
Setting
92
This paper considers a many-to-one matching market M (K,J, P), where K = [K], J [N] 94 are a finite arm set and a finite agent set, respectively. And each arm k has a capacity Qk 2 1. To >>> di. P is the guarantee that no agents will be unmatched, we focus on the market with N S - fixed preference order of agents and arms, which ranked by the mean reward. We assume that arm 96
93
95
97 preferences for agents are unknown and needed to be learned. If agent j prefers arm k over k', which also means that Py > j' K we denote by > k'. And the preference is strict that ji,k & Pj, if k + k. Similarly, each arm k has fixed and known preference ~ over all agents, and specially, j > j' means that arm k prefers agent j over j'. Throughout, we focus on the market where all agent-arm pairs mutually acceptable, that is, J > 9 and k > 0 for all & [K] and j E [N].
98
99
100
101
102
Let mapping m be the matching result. m²] the matched arm for agent j at time t, and (k)) is the agents set matched with arm X Every time agent j selects an arm I,(j), and we use M,( to denote whether j is successfully matched with its selected arm. M,(j) = if agent j is matched with I+) and M,(j) 0, otherwise. If multiple agents select arm k at the same time, only top q agents can successfully match. The agent j matched with arm k can observe the reward X (..m.()(()) (t), where
103
104
105
106
107
the random reward 5. E [o, 1] is independently drawn from fixed distribution with mean Pj.k- While the unmatched ones have collisions and receive zero reward. Generally, the reward obtained by
108
109
agent j is (t) Mj).).
110
An agent j and an arm & form a blocking pair for a matching m if they are not matched but prefer each other over their assignments, i.e. k } m(j) and 3j' E {k)).j > j'. We say matching satisfies individually rationality (IR), if a, p. 0 and p4 >az 9 for all i E [N] and j [K] that is, every worker prefers to find job rather than do nothing. and every company also wants to recruit workers rather than not recruit anyone. Under the IR condition, a matching in the many-to-one setting
111
112
113
114
115
stable if there does not exist a blocking pair 33 35..
116 This paper considers the matching markets under the uniqueness condition. Thus the overall goal is to find the unique stable matching between the agent side and arm side through iterations. Let m (j) be the stable matched arm for agent j under the stable matching m.. The reward obtained by agent
118
119 is compared against the reward received by matching with m m²) at each time. We aim to minimize
120
the expected stable regret for agent j over time horizon T, which is defined as
R2(T)= TT)m)))) E Σ M())x
3 Algorithm
122
In this section, we introduce our MO-UCB- DD Algorithm (Many-to-one UCB with Decentralized Dominated arms Deletion and Local Deletion Algorithm) (Algorithm [ for the decentralized many- to-one market, where there no platform to arrange actions for agents, which leads to conflicts among agents. The MO-UCB-DE algorithm for each agent j first takes agent set I and arm set K. as input and chooses a parameter 0 E (0, 1/K) (discussed in Section C.. It sets multiple phases, and each phase i mainly includes regret minimization block (line 6 12 and communication block (line
124
125
126
128
13
[6)
with duration 2 2 ; = 1,2,....
129
For each agent> j in phase i, the algorithm adds arm deletion to reduce potential conflicts, which mainly contains global deletion and local deletion. The former eliminates the arms most preferred by agents who rank higher than agent) j and obtain active set Ch,[t] (line 4), and the latter deletes the arms that still have many conflicts with agent j after global deletion (line G). We set a collision counter Cja [i] to record the number of collisions for agent j pulling arm k.
130
131
132
In regret minimization block of phase i, we use [, = (k: C3 2 [62'1] to represent the arms that collide more times than a threshold [02i] when matching with agent j. Arms in Ly[i] are first locally deleted to reduce potential collisions for agent j (line 6). After that, agent j selects an optimal action (j)) from remaining arms in Ch [+]] L,, in phase according to UCB index, which is
134
135
137
138
computed by Ar (L (((11)+ 1)+ + /
(line where Ny. (1 - 1) is the number that agent j and arm Nza(t-1]
2a log(t)
TTee mapping m is not reversible is not injective, thus do not use m. mm-1(k) (k))
3

---

Algorithm MO-UCB-D4 algorithm (for agent j)
Input:
0 E 10,1 a >
1: Set global dominated set Gy[0]
2: for phase i 1,2... do
Cj. [1] 0, vk [K] 4: Reset active arms set Chy [1] Gj - -1];
3: Reset the collision
5: i < + (i then
6:
Local deletion [
(k: Cjs(t] [02'1];
7:
Play arm Le()) arg max kEchy[s] (1)]
( 1)
2o (og(())
N5 11
8:
if k = Ie(J) is successfully matched with agent j, i.e. m²(i) = k then
9:
Update estimate (²,,(()) and matching count (t);
10:
else
C C2ali + 1;
12:
end
if
else if
2 + NK - 1) then
14:
2
most matched arm in phase i;
15:
G,
COMMUNICATIONG O,());
16:
end if
17:
end for
139
have been matched at time t -- 1. If the selected arm is successfully matched with agent j. then the algorithm updates estimated reward (م,x(()) (y, E 1(((()) = k and Ma(j) = 1} X5,
140
and (t) (line 9). Otherwise, the collision happens (line 11 and j receives zero reward. The regret minimization block identifies the most played arm O for agent j in each phase i, which is estimated as the best anm for j, thus making optimal policy to minimize expected regret.
142
Algorithm COMMUNICATION
Input:
Phase number i, and most played arms O,[1] for agent j. Vj E [N].
1: Set C = 9:
2: for 1,2 .N.
NK - do
3:
if KÍj - 5 Kj-1 then
4:
Agent j plays arm [z()) (1 mod K) +
5: if Collision Occurs then
6:
C CU (T(i)):
7:
end if
8: else
9:
Play arm 1e() O,
10: end if
11:
end for
12:
RETURN C;
In the communication block (Algorithm 2 there are N sub-blocks, each with duration K. In the th sub-block, only agent & pulls arm I, arm 2, ... arm in round-robin while the other agents select their most preferred arms estimated as the most played ones (line 4p. This block aims to detect >o, j). Under stable matching m , the globally dominated arms set for agent j is denoted as Gj. After the communication block in phase i, each agent updates its active arms set Ch,ft + 1] for phase i + 1, by globally deleting arms set
145
147
globally dominated arms for agent j: G c [[]
148
149
Gy M. and enters into the next phase (line in Algorithm l
151
Hence, multi-phases setting can guarantee that the active set different phases has no inclusion relationship so that if an agent deletes arm in certain phase, this arm can still be selected in the
153 later rounds. This ensures that each agent will not permanently eliminate its stable matched arm, and when the agent mistakenly deletes arm, it will not lead to linear regret.

---

156
4
Results
156
4.1
Uniqueness Conditions
157
4.1.1
ã-condition
158
Constructing a unique stable matching plays an important role in market equilibrium and fairness With uniqueness, there would be no dispute about adopting stable matching preferred by which side, thus it is more fair. When the preferences of agents and arms are given by some utility functions instead of random preferences, like the payments for workers in the labor markets, the stable matching is usually unique. Thus the assumption of the unique stable matching is quite common in real applications. In this section, we propose a new uniqueness condition, a-condition. First, we introduce uniqueness consistency (Unqc) [19], which guarantees robustness and uniqueness of markets.
159
10
[5].
180
182
163
184
165
186
Definition 1. A preference profile satisfies uniqueness consistency if and only if
(i) there exists a unique stable matching m";
168
(ii) for any subset of arms or agents, the restriction of the preference profile on this subset with their stable matched pair has a unique stable matching.
169
170
It guarantees that even if an arbitrary subset of agents are deleted out of the system with their respective stable matched arms, there still exists a unique stable matching among the remaining agents and arms. This condition allows any algorithm to identify at least one stable pair in unique stable matching system and guides the system to a global unique stable matching in an iterative manner. To obtain consistent stable results in the many-to-one market, we propose new ā-condition, which is a sufficient and necessary condition for Unqe (proved in Appendix B
171
172
173
174
175
We considers finite set of arms [K] 21, KK and finite set of agents [N] (1,2. .N) with preference profile P. Assume that [M], A2, ... .AN] is a permutation of {1.2. .N] and [K],=(c,, C2, , ,Ck) } is permutation of 21,
177
K). Denote [N], [K] the left order and [N],, [K], as the right order. The k-th arm in the right order set [K] has the index C& in the left
178
179
180
order set [K] and the j-th agent in the right order set [N], has the index Aj in the left order set [N].
Considering arm capacity, we denote y (c*) (right order) as the stable matched agents set for arm C₁-
181
182
Definition 2. A many-to-one matching market satisfies the â-condition if.
(i) The left order of agents and arms satisfies
Vj E [N), Vk > j.k E [K], (5.m > Uj,k
189
where m" m²() is agent j stable matched arm; (ii) The right order of agents and arms satisfies
Wk < K&= & K,ck E AK, C (N),,"" t A to,t1
184
where the set (ck) is more preferred than A A qs, +1 means that the least preferred agent in 7 (cr) ck is better than A A 9o; for Cj.
185
Under our â-condition, the left order and the right order satisfy the following rule. The left order gives rankings according to agents' preferences. The first agent in the left order set [N] prefers arm 1 in [K] most and has it the stable matched arm. Similar properties for the agent to q since arm 1 has ' capacity. Then the (q + 1)-th agent in the left order set [N] has arm in [K] as her stable matched arm and prefers arm most except arm 1. The remaining agents follow similarly. Similarly, the right order gives rankings according to arms' preferences. The first arm 1 in the right order set [ most prefers first de, agents in the right order [N], and takes them as its stable matched
187
188
189
190
191
192
193
agents. The remaining arms follow similarly.
This condition is more general than existing uniqueness conditions like SPC (8 and recover the known a-condition in one-to-one matching market [19]. The relationship between the existing uniqueness conditions and our proposed conditions will be analyzed in detail later in Section (. 1.2
195
196
197
The main idea from one-to-one to many-to-one analysis to replace individuals with sets. In general, under â-condition, the left order satisfies that when arm 1 to arm k 1 are removed, agents
5

---

[E=r 1 to (Ei=1) 4:) prefer & most, and the right order means that when A₁ to agents
199
200
Ei are removed, arm & prefers agents A = (Agt=) +1 A +2, Ei go
where As is the agent set that are most ys preferred by arm k among those who have not been matched by arm 1,2, ... 1. Te next theorem give a summary.
202
Theorem 1. If a market M = (K)J.P) satisfies â-condition, then m² (E + 1) m (E 9:) j (the left order), 72 (cx)) A₁, and m² (A₂) Cj (the
203
m [Ei=1 9: + 2)
205
right order) under stable matching.
206
Under a-condition, the stable matched arm may not be the most preferred one for each agent j. j E [NT, thus (i) we do not have m (j) be dominated only by the agent 1 to agent - 1, i.e. there may exist j' >] J. s.t. j' ()) j: (ii) the left order may not be identical to the right order, we define mapping Ir to match the index of an agent in the left order with the index in the right order,
208
209
iee A(r()) = j. From Theorem T the stable matched set for arm k is its first preferred agents 210
211
(cx) = AA. We define ir as (r()) = max(j A, E 7m (i)). E [N]], that is, in the right
order, the mapping for arm & E [K] is the least preferred
among its most qu preferred agents. Note that this mapping not an injective, i.e. Jj s.t. agent j Arr() = Ab((") An intuitive
213
representation be seen in Figure 4 Appendix A. A.I
215
4.1.2
Unique Stable Conditions in Many-to-one Matching
216
Uniqueness consistency (Unqe) leads the stable matching robust one which is desirable property in large dynamic markets with constant individual departure 77. A precondition of Unqe is to ensure global unique stability, hence finding uniqueness conditions is essential.
217
218
219
The existing unique stable conditions are well established in one-to-one setting (analysis can be found in Appendix [B. and in this section, focus uniqueness conditions in many-to-one market, such as SPC, 28 Aligned Preference, Serial Dictatorship Top-top match and Acyclicity [26] 2 28 (Definition 9
221
10 in Appendix (B.2). Takashi Akahoshi [2 proposes necessary and sufficient condition for uniqueness of stable matching in many many-to-one matching where unacceptable agents and arms may exist both sides. We denote their condition Acyclicity" Under setting, both two sides are acceptable, and we first give the proof of that Acyclicity" is a necessary and sufficient condition for uniqueness in this setting (see Section B.2.4 in Appendix B We then give relationships between our newly a-condition and other existing uniqueness conditions, intuitively expressed in
223
225
226
227
228
Figure
L and we give proof for this section in Appendix B.2
229
Lemma 1. a many-to-one matching market M = (K. P). both Serial Dictatorship and Aligned
Preference produce unique stable matching and they equivalent.
231
Theorem 2. In a many-to-one matching market M = (K., J.P,, our â-condition satisfies:
232
(i) SPC is sufficient condition to ã-condition;
(ii) ā-condition is necessary and sufficient condition to Unqe;
234
(iii) â-condition is a sufficient condition to Acyelicity".
Uniquaness Acyclicity
a-condtion
SPC
top-top
Serial Dictatorship
Aligned Preference
Figure 1: Relations of Uniqueness Conditions in Many-to-one Market.

---

235
4.2
Theoretical Results of Regret
236
We then provide theoretical results of MO-UCB-D4 algorithm under our di-condition. Recall that Gj is the globally dominated arms for agent j under stable matching m." For each arm l & Gj. we give
237
the definition of the blocking agents for arm k and agent j: Byx = -0' j > J. k & G which
238
contains agents more preferred by arm than j. The hidden arms for agent j is H, = -k: k &
239
(3) n (k: By * 0). The reward gap for agent j and arm k is defined Ayk (' (1) Mj.al
241
and the minimum reward gap across all arms and agents is A minje[N] [minke ) We
242
assume that the reward is different for each agent, thus A > O for every agent j and arm k.
Theorem 3. (Regret upper bound) Let Jmax (i) = max (j + 1, 3K Hz E B be the mux blocking agent for agent j and [a(j) j + max (j) a fixed factor depends on both the left order and the right order for agent j. Following MO-UCB-DD D4 algorithm with horizon T, the expected regret of a stable matching under a-condition (Definition) 2 for agent j E [N] is upper bounded by
244
246
E (T)
Σ
Sa Ajk
(Tg(T)
+
π a
log(T)
+
Σ Σ
(Iog(T) +
π log(T)
kg (5)
k j'EB,
N2
+ cog (T) + +0
2 +
(min().007)))) (f) + -1) + +N*Ki²)
where 1 max (8, (8,1,, (2) (then i < 8 and i1, i2 are defined in equation 33), ) and ma (J) max (::]j)::111 S j.. is the maximum right order mapping for agent j' who ranks higher than
248
the scale of the regret upper bound under â-condition is O NK log(T) and the
250
From Theorem
251
proof is in Section
Proof Sketch of Theorem Under â-condition, we only need to discuss the regret of the unique result. We construct good phase (in Appendix (A.2) and denote that the time point of agent reaching its good phase by Ty. After Tj, agent j could identify its best arm and matches with his stable pair. Thus, from phase tj on-wards, agent j + will find the set of globally dominated arms m (j) if m" (j) brings collisions in communication block according to Algorithm]] [] Global deletion here follows the left order. Then when agent j enters into regret minimization block next phase, the times plays sub-optimal arm is small which leads to a small total number of collisions experienced by agent j 1. Then the process of each agent after good phase is divided into two stages: before Tj and after Tj. After Tj. according the causes of regret, is divided into four blocks: collision, local deletion, communication, and sub- aub-optimal play. Phases before Tj can be bounded by induction. The regret decomposition is bound by the following.
253
255
G ر+ز and will eliminate
257
258
259
260
261
262
263
Lemma 2. (Regret Decomposition) For a stable matching under a-condition, the upper bound of regret for the agent) [N] under algorithm can be decomposed by:
E (T)(
E [Sras]
+ +min( 1)TE [SvoJ]
((K- - + BB ()) loga (T) + NKE [V,j)
(Regret before phose Fuz))
(Local defetion)
(Comounicaatinn)
+
Σ
Σ
804pi.mm
(Tg((T) + log(T)
π
A3
kRG J'EB,
(Collision)
8a
(1+ +NK (á(a) + +1) 80x
(log(T) (T) + V log(T)) +NK
A²
KgGJUm (1)
(Sub-optimal play)
285 where Fag. Vaj are the time points when agent j enters into â- ã-Good phase and 5-Low Collision phase respectively, mentioned as "good phase" above, are defined in Appendix A.2 A.2
7

---

267
5
Difficulties and Solutions
268
While putting forward our ã-condition in the many-to-one setting, many new problems need to be taken into account.
269
From one-to-one setting to many-to-one setting First, although we assume that arm preference is over individuals rather than combination of agents, the agents matched by one arm are not independent. Specially, arms with capacity y can not just be replaced by y independent individuals with the same preference. Since there would be implicit competition among different replicates of this arm, and can reject the previously accepted agents when it faces more preferred agent. Secondly, collisions among agents is one of main causes of regret in decentralized setting, while capacity will hinder the collision-reducinn
271
273
275
process. In communication block, when two agents select one arm at time, as an arm can accept more than one agent, these two cannot distinguish who is more preferred by this arm, while it can be done in one-to-one markets. Thus it is more difficult to identify arm preferences for each agent. The Ir in 77] is a one-to-one mapping that corresponds the agent index in the left order and the agent index in the right order, which is related regret bound (Theorem 3 in 77 and Theorem in our work). While it does not hold in our setting. To give a descriptive range of matched need to define new mapping.
277
279
280
281
282
result for each arm under a-condition,
283
In order to solve these problems. we explain as follows: First, since capacity influence the com- munication among agents, we add communication block and introduce an arm set G which will be deleted before each phase to reduce collisions, where Gj contains arms that will block agent globally under stable matching m Second, the idea from one-to-one to many-to-one is transition to set. It is natural to split sets into individuals or design a bridge to correspond sets to individuals. We construct new mapping Ir (Figure in Appendix A from agent in the left order to agents in the right order under a'-oonition. Ir maps each arm A: to the least preferred one of its stable matched agents in the right order, thus giving matching between individuals and individuals and constructing the range of the stable matched agents set (Theorem []. Except ir, capacity also influences regret mainly in communication block, mentioned in the first paragraph.
285
287
from individual
289
280
281
282
293
From a-condition to ā-condition To extend a-condition to the many-to-one setting, it needs to define preferences among sets. However, there might be exponential number of sets due to the combinatorial structure and simply constraining preferences over all possible sets will lead to high complexity. Motivated by a-condition which characterizes properties of matched pairs in one-to-one setting, we come up with a possible constraint by regarding the arm and its least preferred agent in the matched set as the matched pair and define preferences according this grouping. It turns out that
295
297
298
299
we only need to define the preferences of arms over disjoint sets of agents to complete the extension o- o-condition is defined under the stable matching, which can also fit the regret analysis well. As summary, there might be other possible ways to extend the a-condition but we present a successful
300
301
302
trial to not only give good extension with similar inclusion relationships but also guarantee good
303
regret bound.
Experiments
304
In this section, we verify the experimental results of our MO-UCB-D4 algorithm (Algorithm ! for decentralized many-to-one matching markets. For all experiments, the rankings of all agents and arms are sampled uniformly. We set the reward value towards the least preferred arm to be 1/N and the most preferred one as for each agent, then the reward gap between any adjacently ranked arms is A 1/N. The reward for agent matches with arm k at time t (t, is sampled from Ber (H),s)) The capacity is equally set as q = N/K. We investigate how the cumulative regret and cumulative market unstability depend the size of the market and the number of arms under three different unique stability conditions: Serial Dictatorship, SPC, â-condition. The former cumulative
306
308
310
311
312
313
regret is the total mean reward gap between the stable matching result and the simulated result, and the latter cumulative unstability is defined as the number of unstable matchings in round f. In our experiments, all results are averaged over 10 independent runs, hence the error bars are calculated as
314
315
standard deviations divided by V10.
316
317
Varying the market size unstability, we first varying N with fixed K with market size of N e {10, 20, 30, 40} agents
To test effects on two indicators, cumulative regret and cumulative
8

---

319
and K = 5 arms. The number of rounds is set to be 100, 000. The cumulative regret in Figure (e) show an increasing trend with convergence as the number of agents increases under these three conditions. When the number of agents increases, there is a high probability of collisions among different agents, resulting in the increase of cumulative regret. Similar results for cumulative unstability are shown in Figure (d)(())). When N is larger, the number of unstable pairs becomes
320
322
324
more. With the increase the number of rounds, both two indicators increase first and then tend to be stable. The jumping points are caused by multi-phases setting of MO-UCB-D4 algorithm.
Sertil
Sarte Demsomoo
Figure 2: Cumulative regret and cumulative unstability of MO-UCB-D4 of size with N E (10, 20, 30, 40) and the number of arms K = 5 under Serial Dictatorship, SPC, a-condition.
Figure 3: Cumulative regret and cumulative unstability of MO-UCB-D4 of size with K e {2, 5, 10, 20) under Serial Dictutorship, SPC, ä- condition.
326
Varying arm capacity The number of arms is chosen by K (2,5, 5, 10, 20), with N 20 and N/K. K. The number of rounds we set is 400, 000. With the increase of K. both the cumulative regret in (igureBla)e\CC and the cumulative unstability Figure (d)(()( increase monotonously.
327 Q
328
329
When K increases, the capacity for each arm & decreases, and then the number of collisions will increase, which leads to an increase of cumulative regret. And it also leads to more unstable pairs, which needs more communication blocks to converge to stable matching. Under these three conditions, the performances of the algorithm are similar.
330
332
Conclusion
333
We are the first to study the bandit algorithm for the many-to-one matching market under the unique stable matching. This work focuses on a decentralized market. A new ã-condition is proposed guarantee unique stable outcome in many-to-one market, which is more general than existing uniqueness conditions like SPC, Serial Dictatorship and could recover the usual a-condition in one-to-one setting. We propose phase-based algorithm of MO-UCB-D4 with arm-elimination.
335
337
338
which obtains O logggT) stable regret under ä-condition. By carefully defining a mapping from A²
340
amm to the least preferred agent in its stable matched set, we could effectively correspond arms and agents by individual-Be tiiiiaa--t--iividii individual. A series of experiments under two environments of varying the market size and varying arm capacity are conducted. The results show that our algorithm performs well under Serial Dictatorship, SPC and â-condition respectively.
342

---

References
344
345
[1] Azar Abizada. Stability and incentives for college admissions with budget constraints. Theoreti- cal Economics, 11(2):335-75,, 2016.
[2] Takashi Akahoshi. Singleton core in many-to-one matching problems. Mathematical Social Sciences, 72:7-13, 2014.
348
349
[3] Ahmet Altinok. Dynamic many-to-on matching. Available at SSRN 3526522, 2019.
350
[4] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235- 2002.
351
352
[5] Orly Avner and Shie Mannor. Concurrent bandits and cogmitive radio networks. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pages 66-81. Springer, 2014.
354
355
[6] Sophie Bade. Random serial dictatorship: the one and only. Mathematics of Operations Research, 45(1):353-368, 2020.
357
[7] Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log regret for decentralized bandits in matching markets. In International Conference on Machine Learning, pages 705-715, 2021.
358
359
360
88] Anna Bogomolnaia and Hervé Moulin. A new solution to the random assignment problem. Journal of Economic theory, 100(2):295-328. 2001.
[9]
Somouaoga Bonkoungou. Decentralized college admissions under single application. Review of Economic Design, 25(1))65-99) 91, 2021.
363
364
110]
Simon Clark. The uniqueness of stable matchings. Contributions in Theoretical Economics,
601 I), 2006.
386
[11] Jan Eeckhout. On the uniqueness of stable marriage matchings. Economics Letters, 69(1):1-8. 2000.
387
368
[12] David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1)--115, 1962.
369
370
[13] Aurelien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-comeee strategies. Advances in Neural Information Processing Systems, 29:784-792, 2016.
[14] Virginia Gunn, Bertina Kreshpaj, Nuria Matilla-Santander Emilia F Vignola, David H Weg- man, Christer Hogstedt, Emily Q Ahonen, Theo Bodin, Cecilia Orellana, Sherry Baron, et al. Initiatives addressing precarious employment and its effects on workers' health and well-being: A systematic review. International Journal of Environmental Research and Public Health, 19(4)2223,, 2022.
373
374
375
378
377
[15] Gregory Z Gutin, Philip R Neary, and Anders Yeo. Unique stable matchings. arXiv preprint arXiv:2106. /2977, 2021.
378
[16] Guillaume Haeringer and Flip Klijn. Constrained school choice. Journal of Economic theory, 144(5):1921-1947, 2009.
380
381
[17] John William Hatfield, Fuhito Kojima, and Scott Duke Kominers. Investment incentives in labor market matching. American Economic Review, 104(5):436-41 2014.
383
[18] Ramesh Johari, Vijay Kamble, and Yash Kanoria. Matching while learning. Operations Research, 69(2)6655-611, 2021.
384
385
[19] Alexander Karpov. A necessary and sufficient condition for uniqueness consistency in the stable marriage matching problem. Economics Letters, 65, 2019.
386
387
[20]
Bettina Klaus and Flip Klijn. Local and global consistency properties for student placement. Journal of Mathematical Economics, 2223):222-229, 2013.
10

---

389
[21] Lydia T Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In International Conference on Artificial Intelligence and Statistics, pages 1618-1628. PMLR. 2020.
390
382
[22] Lydia T Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. arXiv preprint arXiv:2012.07338, 2020.
393
[23] Jinpeng Ma. The singleton core in the college admissions problem and its application to the national resident matching program (nrmp). Games and Economic Behavior, 69(1):150-16) 2010.
396
397
[24] Onkar Malgonde, He Zhang, Balaji Padmanabhan, and Moez Limayem. Taming complexity in search matching: Two-sided recommender systems on digital platforms. Mis Quarterly, 44(1), 2020.
398
399
400
[25] Hai Nguyen, Thanh Nguyen, and Alexander Teytelboym. Stability in matching markets with complex constraints. Management Science, 67(12):7438-745 2021.
402
[66] Muriel Niederle and Leeat Yariv. Decentralized matching with aligned preferences. Technical report, National Bureau of Economic Research, 2009.
404
[27]
Jacok Park. Competitive equilibrium and singleton cores in generalized matching problems. International Journal of Game Theory, 46(2) 509,, 2017.
405
28
Philip Reny. A simple sufficient condition for a unique and student-efficient stable matching in the college admissions problem. Economic Theory Bulletin, 9(1):-99, 2021.
407
[29] Antonio Romero-Medina and Matteo Triossi. Acyclicity and singleton cores in matching markets. Economics Letters, 1 (18(1):237-239 2013.
409
410
[30] Jonathan Rosenski, Ohad Shamir, and Liran Szlak. Multi-player bandits-a musical chairs approach. In International Conference on Machine Learning, pages 155-163. PMLR, 2016.
411
412
[3]] Alvin Roth. On the allocation of residents to rural hospitals: a general property of two-sided matching markets. Econometrica: Journal of the Econometric Society, pages 425 025,427, 1986.
414
[32] Alvin E Roth and Marilda Sotomayor. Two-sided matching. Handbook of game theory with economic applications, 1:485-541, 1992.
415
416
[33] Hannu Salonen and Mikko AA Salonen. Mutually best matches. Mathematical Social Sciences, 91:42-50, 2018.
417
[34] Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate delete: Decentralized competing bandits in serial dictatorship. In International Conference on Artificial Intelligence and Statistics, pages 1252-1260. PMLR, 2021.
419
421
[35] Jay Sethuraman, Chung-Piav Teo, Liwen Qian, et Many-to-one stable matching: Geometry and faimess. Mathematics of Operations Research, (3)33311-5599 2006.
422
[36]
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933.
424
Checklist
425
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
428
contributions and scope? [Yes] Please see Abstract and Section [
429
(b) Did you describe the limitations of your work? [Yes] Please see Section C.4
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work mainly focuses on the online learning theory, which does not have any potential
431
negative socictal impacts.
11

---

433
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
434
435
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Please see Section 2
437
438
(b) Did you include complete proofs of all theoretical results? [Yes] Please see Appendix.
439
3. If you ran experiments..
440
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] Please see supplemental material.
441
442
443
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Please see Section [and supplemental material.
445
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Please see Section [
448
(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]
448
449
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
451
(b) Did you mention the license of the assets? [N/A]
452
(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'le 're using/curating? [N/A]
455
456
(c) Did you discuss whether the data you are using/curating contains personally identifiable
457
information or offensive content? [N/A]
458
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
460
461
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
463
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
484
12


Reviews:
[{"review_id": "rO36HAjdy5R", "reviewer": "Reviewer_HrNG", "summary": "The authors study the problem of minimizing regret in many-to-one matching markets with bandit feedback. In a many-to-one matching markets, each right-side agent (aka arms) can match upto a maximum number of left-side agents (aka agents). The authors develop \\tilde{alpha}-condition as a sufficient condition for uniqueness consistency in many-to-one matching markets. Under this condition they provide logarithmic regret for the bandit learning problem for the MO-UCB-D4 algorithm.", "questions": "- The authors' comments on increase in q_k decreases lr_{max}(j) seems a bit less rigorous. Is there a more rigorous statement -- e.g. Does partial ordering of q_k introduces partial order on lr_{max}(j)?\n\n- Please discuss the other points mentioned in the weaknesses. ", "limitations": "This work seems theoretical in nature, and negative societal impact, if any, is not immediate. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This work is an interesting addition to learning in matching markets with bandit feedback, as it studies the many-to-one matching markets for the first time.\n- It develops the \\tilde{\\alpha}-condition (adapted from one-to-one matching markets) as a sufficient and necessary condition for uniqueness consistency. \n\nWeaknesses:\n- The relationship of capacity q_k and  lr_{max}(j) is not discussed properly, elaboration needed (see questions). \n- Counterexample of Acyclicity* holding and \\tilde{\\alpha}-condition not holding is missing. This will improve the understanding in section 4.3.\n- The \\tilde{\\alpha} condition is also very closely related to Karpov et al. The difficulty in extending this to the many-to-one matching is unclear.   \n- The discussion on why deriving regret bound for many-to-one case is difficult than Basu et al. is not stated clearly. Specifically, the role of moving from ordering of individuals to ordering of sets need to be elaborated (probably in derivation of the \\tilde{\\alpha} condition as well). \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": "dcJ684SFdaU", "reviewer": "Reviewer_Q3cx", "summary": "This paper studies decentralized learning and matching in many-to-one matching markets. They introduce a model for this setting, develop a bandit learning algorithm under a uniqueness assumption about the set of stable matchings, and obtain a logarithmic instance-dependent bound on its regret.", "questions": "- I was not able to understand the definitions of “left order” and “right order”; it seems like there is a missing clause in the first sentence of the paragraph starting at line 173. Would it be possible to elaborate further on the definition?\n- In Definition 2, there appears to be a missing term in the summations. What should that term be?\n- I am also somewhat confused about the comparisons between assumptions on the preferences under “Conditions for Unique Stable matching”. For instance, the condition of Akahoshi is a property of the preference profiles of a single side (under which there exists a unique stable matching). On the other hand, uniqueness consistency is a property of the full preference profiles (for both sides). Could you clarify what the precise comparison being made is?", "limitations": "The authors describe the limitations of their results in Section C.3. It may be useful to move this discussion into the main body.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths:\n    - The problem of many-to-one matching that the authors study is well-motivated, as it is a salient aspect of many real-world matching markets (e.g., schools, employment) in which learning and adaptivity could play a useful role.\n    - It is nice to see simulations of the algorithm to validate the performance. (However, it would also be nice to see comparisons against other methods.)\n- Weaknesses:\n    - The writing was difficult to follow, with several crucial definitions and assumptions unclear (see below).\n    - The focus on unique stable matching seems like a strong limitation of the results, as in many markets where the preferences are not in a sense “acyclic” or “aligned”, multiple stable matchings exist. The proposed approach does not appear to scale gracefully to this setting.\n    - While the consideration of many-to-one matching is new, this work only considers a limited form of many-to-one matching where each “arm” has a total preference ordering agents.\n    - The regret bounds are in the minimum reward gap across all agents in arms; this assumption does not permit agents to be indifferent (or nearly indifferent), even for arms far down in their ranking list.", "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": "Q5SeB5i6E7S", "reviewer": "Reviewer_zkK9", "summary": "The paper studies many-to-one matching markets - which is a generalization of the one-to-one matching markets studied in recent years in the online learning community. The paper identifies a combinatorial condition that guarantees an unique Nash equilibrium to the underlying game if all participants knew of their preferences. This condition is a multi-way generalization of the recently used alpha condition for one-to-one matching. The paper shows that if the underlying market satisfies this unique Nash Equilibria criteria, then the decentralized learning algorithm yields logarithmic regret. The proposed algorithm is a natural variant of the UCB-D4 which was shown to be a good method for the one-to-one matching case. ", "questions": "1. What do you think are the additional challenges in extending this to markets with multiple equilibria ?\n2. Can this algorithm be generalized if both sides of the market need to perform learning ?", "limitations": "Yes. This is primarily a theory paper. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. Comprehensive treatment of the problem\n2. Builds and contributes to an emerging theory on decentralized bandit learning in matching markets \n3. Their algorithms and results recover the known results in one-to-one matching market when the system is one-to-one. In this sense the proposed algorithm is a strict generalization of prior algorithms \n\nWeakness \n\n1. The paper does not address issues such as competition mechanism while learning. \n\nHowever, I believe the weakness to be minor and can be easily addressed in the discussion sections of the revision of the paper. \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": "HSA9yhXfhAv", "reviewer": "Reviewer_36px", "summary": "This paper studies the problem of bandit learning in many-to-one matching markets. They generalize the $\\alpha$-condition in a marriage problem to a proposed $\\tilde\\alpha$-condition that is a matching guarantee for uniqueness consistency in many-to-one matching markets. Under the proposed condition the authors present a UCB-based arm elimination algorithm that obtains logarithmic regret . The authors verify their proposed algorithm by simulations under several different optimality conditions. ", "questions": "Can the authors address some of the queries from the previous section? Specifically, can they contrast their work from prior work in terms of (i) theory and regret bound, (ii) novel components in the regret analysis, (iii) specific shortcomings in prior work, (iv) baselines for experiments, (v) optimality of regret bound?", "limitations": "The authors do not discuss limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The paper presents a novel algorithm with a competitive regret bound.\n+ The new $\\tilde\\alpha$-condition proposed appears to generalize the $\\alpha$-condition from the stable marriage problem, and the discussion for the condition puts it in comparison with prior work.\n\nWeaknesses:\n- The paper has sections that are not very well-written. While the authors do a good job of explaining their new stability condition in Section 4.1, the discussion with prior conditions (deferred to 4.3) should essentially be put together. In Section 5, the authors present the technical challenges in extending bandit matching to the many-to-one setting, however it is unclear / difficult to follow how each of the steps translate into the final regret bound which is presented earlier in Section 4.2. \n- Regret Bound: It is not clear which contributions are novel and which proof techniques are reused from prior work. All the proofs are deferred to the appendix, and the proof-sketch provided in Section 4.2 is not very informative. \n- - There are no discussions on which parts of the proof reuse prior work and which parts are novel. \n- - There are no discussions on optimality and lower bounds beyond the mentioning of the logarithmic factor. \n- - There are no discussions on which aspects of the algorithm can be improved in future work, and what the authors conjecture to be the optimal rate. \n- Experiments: While the authors indeed experiment with several different criteria and different number of agents, they do not have any baseline comparisons, making it difficult to compare their experimental results in a relative sense. It would be worthwhile if the authors could come up with some meaningful albeit sub-optimal baselines to highlight the importance of each component in their algorithm design.", "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: Reject