Bandit Learning in Many-to-one Matching Markets with Uniqueness Conditions
Authors: Liya Guo
Zilong Wang
Shuai Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: matching markets
multi-armed bandit
many-to-one setting
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.

Under review as a conference paper at ICLR 2023
BANDIT LEARNING IN MANY-TO-ONE MATCHING MARKETS WITH UNIQUENESS CONDITIONS
Anonymous authors Paper under double-blind review
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 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-DA algorithm with O [K log(T)) regret bound, where T is the time horizon, A=
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.
INTRODUCTION
The data-driven matching market is faced with the problems of learning customer preference and matching the demand side with the supply side of the market to maximize the henefits of both sides. Online platforms, like Lyft, Thumbtack and Taskrabbit, make decisions for customers and service providers to match, on the basis of their diversified needs, which is abstracted as matching market with an agent side and an arm side, and each side has preference profile over the opposite side. They choose from the other side according to preference and perform a matching. Specific examples like pool riding in ride-share system that matches a driver to multiple riders, Slate ranking in recommender systems that user is matched to various content at single request le et al. (2019). The stability of the matching result is key property of the market Roth & Sotomayor (1992 Abizada (2016); Park (2017).
This work takes online short-term recruitment as the main example, combine the traditional matching problem Bade (2020); BBgoomonaiaa & Moulin (2001): Roth & Sotomayor (1992) with the online system Gunn et al. (2022); Malgonde et al. (2020); Johari et al. (2021). Companies with short-term needs accommodate workers who voluntarily looking for flexible probation periods. The worker preferences may be unknown in advance, thus matching while learning the preferences is necessary. The multi-armed bandit (MAB) Thompson [933); Garivier al. (016)); Auer al.) (2002) is an important tool for N' independent agents in matching market simultaneously selecting arms adaptively from received rewards at each round. And the upper confidence bound algorithm (UCB) Auer et al.) (2002) is typical MAB algorithm, which sets a confidence interval to represent uncertainty. The idea of applying MAB to one-to-one matching problems, introduced by Liu et al. (2020a). assumes that there is central platform to make decisions for all agents. Following this, other works Liu et al.) (2020b): Sankararaman et al. (202T): Basu et al. (2021) consider more general decentralized setting without central platform to arrange matchings, and our work is also based on this setting.
However, is not enough to just study the one-to-one setting. In online short-term worker employment problem, employers have numerous similar short-term tasks be recruited and workers only

---

Under review as a conference paper at ICLR 2023
choose one task according to the company'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. The online matching is in an iterative way that tasks are short-term, or if an agent do not get an ideal job, he will leave the platform or start a new competition to select another company. We abstract companies as arms and workers as agents. Each arm has a capacity g which is the maximum number of agents this arm can accommodate. When an arm faces multiple choices, it accepts its most q preferred agents. Agents thus competing for arms and may receive zero reward if losing the conflict. is worth mentioning that arms with capacity q in the many-to-one matching can not just be replaced by independent replicates with the same preference since there would be implicit competition. In addition, when multiple agents select one arm at time, collision is unavoidable, which 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 preferences of arms and other agents, so as to formulate better policies to reduce collisions and learn faster about their stable results.
This work focuses on a many-to- market under uniqueness conditions. Previous work Clark (2006); Gutin al. 2 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 AcyelicityNiederic Niederle & Yariv (2009); Akahoshi (2014). Our work is motivated by [Bssu et al. (2021). 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-om 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 ä-condition that can guarantee unique stable matching and recover a-condition Karpov (2019) if reduced to the one-to-one setting. We establish the relationships between our é-condition and existing uniqueness conditions in many-to-om sctting.
For clarity, in this paper, we study the bandit algorithm for decentralized many-to-one matching market with uniqueness conditions. Under our newly proposed uniqueness condition, â-condition, we design MO-UCB-DE algorithm with arm elimination to construct stable matching result. The regret of our algorithm can be upper bounded by O [NK (Tg) where N is the number of agents, A²
K is the number of arms, and A the minimum reward gap, and the regret reaches the lower bound in terms of T and A. Finally, we conduct 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.
SETTING
This paper considers a many-to-one matching market M (K,,,P), where K. = [K], is a finite arm set and J = [N] is a finite agent set. Each arm & has a fixed capacity Ok 2 1. To guarantee that no agents will be unmatched, we focus on the market with N < > q:- P is the fixed preference order of agents and arms, which is ranked by the mean reward. We assume that arm preference is over individuals Roth & Sotomayor [1992); Sethuraman et al.) (2006); Altinok (2119), and arm preferences for agents are unknown and needed to be learned. If agent j prefers arm than k', iie., Mj. > Hj we denote by A ز V. And the preference is strict that μáj, * P.j if l of k'. Similarly, each arm k has preferences > over all agents, and specially, j > means that arm l prefers agent j over j" Throughout, we focus on the market where all agent-arm pairs are mutually acceptable, that is. j > () and k > 0 for all & E [A] and E [N].
Let a mapping m be the matching result. m²(r) is the matched arm for agent ÿ at time t, and 7e (e()) is the agent set matched with arm A0 At each time agent j selects an arm Ie(5), and we use Mi( to denote whether, j is successfully matched with its selected arm. Mj)
if agent j matched with I:(j), and M,(j) O, otherwise. If multiple agents select arm k at the same time, only top qe agents can successfully match. The agent j matched with arm i can observe the reward X (..m.is)(), where
TTee mapping m is reversible it not injective, thus do not use m. mm-(k) (k)-
2

---

Under review as a conference paper at ICLR 2023
the random reward x,, E [0, 1] is independently drawn from fixed distribution with mean Mj.k- While the unmatched one has collisions and receives zero reward. Generally, the reward obtained by agent j is (t) Mz(
We say an agent j and an arm & form a blocking pair for a matching m they prefer each other over their current assignments, i.e. >-j m(j) and Ej' <k(,,, > j' We say matching satisfies individually rational (IR), if 0j 7p. & and p; >ay @ for all E [N] and j E [K] that is, every worker prefers find a job rather than do nothing, and every company also wants recruit workers rather than not recruit anyone. Under the IR condition, a matching in the many-to-one setting is stable if there does not exist a blocking pair Salonen & Salonen (2018); Sethuraman al. (2006).
This paper considers the matching markets under the uniqueness condition. Thus the overall goal is 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 compared against the reward received by matching with m m²( at each time. We aim to minimize the expected stable regret for agent j over time horizon T,, which is defined as
(T( TPj.m()) (J)
E Σ M.) M.)(()
3 ALGORITHM
In this section, we introduce our MO-UCB-D4 Algorithm (Many-to-one UCB with Decentralized Dominated arms Deletion and Local Deletion Algorithm) (Algorithm]) IT) for the decentralized many- to-one market, where there is no platform arrange actions for agents. The MO-UCB D4 algorithm sets multiple phases, and each phase mainly includes regret minimization block (line 6 (2) and
communication block (line 13
16) with duration 2'-1 1,2,....
Algorithm 1 MO-UCB-D4 D4 algorithm (for agent j)
Input:
0 E 1/K), a > 1. Set global dominated set G, 6
2: for phase i = 1, 2, do
3: Reset the collision set Cj.K [] 0, Vk E [K]
4: Reset active arms set Chy [ = G - 1]:
5:
if < 2' + N (i
then
6: Local deletion [
{k: Cjplt] 2 162'1]:
7:
Play arm Ie() arg max (م. - 1) + V (t,+(t-1)
2a log(t)
kech, [1]]
8:
if k = 44) is successfully matched with agent j, i.e. mi(i) k then
9:
Update estimate (),x(t) and matching count (t);
10:
else
11:
C = C3al1] + 1;
12:
end if
13:
else if' t = 2' + (i 1) then
1
most matched arm in phase i; COMMUNICATIONGE Oy(ā));
15:
G
end if
17:
end for
For each agent in phase i, the algorithm adds arm deletion process reduce potential conflicts, which contains global deletion and local deletion. The former eliminates the arms most preferred by agents who rank higher than agent j and obtains active set Ch (line 4b. and the latter deletes the arms that still have many conflicts with agent after global deletion (line (). We set collision counter &j [i] record the number collisions for agent j pulling arm & in phase i.
In the regret minimization block of phase use L {k: Cza > [02'1] represent the arms that collide more times than threshold [02$] when matching with agent Arms in I,5
3

---

Under review as a conference paper at ICLR 2023
After that, agent j selects optimal action [j) from remaining arms in ( in phase according to UCB index, which is log(t)
first locally deleted to reduce potential collisions for agent (line 6).
computed by A (1)+((-1)+ Nxa(tt11 (line 7. where (4 - 1) is the number that agent j and arm have been matched at time 1. If the selected arm successfully matched with agent j. then the algorithm updates estimated reward (),x(t) (,,((1) Σ. 2==1 [(1+ k and My(j) 13 X,, (t) and N (t) (line P). Otherwise, the collision happens (line [1] and agent j receives zero reward. The regret minimization block identifies the most played arm O,(d for agent j in each phase which is estimated as the best arm for agent j, thus making optimal policy to minimize expected regret.
Algorithm 2 COMMUNICATION
Input:
Phase number i, and most played arms O,[i] for agent Vj E [N]
1: Set C = 0;
2: for t = 1,
NK do
3:
if' [Í 1) < Kj then
4:
Agent j plays arm [2(j) (t mod K) +
5: if Collision Occurs then cU (I(());
6:
7:
end if
8: else
9: Play arm Iej) O,(i]:
10: end if
11:
end for
12:
RETURN C;
In the communication block (Algorithm 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 other agents select their most preferred arms estimated the most played ones (line 4). This block aims to detect globally dominated arms for each agent G, C =0,,1e [1] : j' >0, jj. Under the stable matching m" the globally dominated arm set for agent j is denoted as G After the communication block in phase i, each agent j updates its active arm set Chy (i + 1) for phase i + 1, by globally deleting arm set (i] and enters into the next phase (line in Algorithm 1.
Hence, multi-phases setting can guarantee that the active sets in different phases have no inclusion relationship so that if an agent deletes arm in certain phase, this arm can still be selected in the later rounds. This ensures that each agent will not permanently eliminate its stable matched arm, and agent j mistakenly deletes an arm, will not lead to linear regret.
RESULTS
4.1 UNIQUENESS CONDITIONS
4.1.1 İ-CONDITION
When the preferences of agents and are given by some utility functions instead of random preferences, like 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. And some uniqueness conditions have important properties like consistency, which states that any stable pair leaving the market does not affect the remaining to form stable matching. where agents and arms come and go, the consistency property is desirable to keep the matching majority static Basu et al. (021). And in this way, the market is divided into pairs with priority, which is divided into hierarchical structures, that the design of the algorithm is inductive, and the regret is constrained to the number of sub-optimal matchings (Appendix 3) Besides, when the stable matching is unique, there would be dispute about adopting stable matching preferred by which side, thus is fairer to both sides Cen Shah (202)). Note that the outcome of the GS algorithm would prefer the proposal side and would be unfair to the other side Clark (2006).
dynamic markets
4

---

Under review as a conference paper at ICLR 2023
In this section, we propose new uniqueness condition, â-condition. First, introduce uniqueness consistency (Unqe) Karpov (2019), which guarantees robustness and uniqueness of markets. Definition 1. A preference profile satisfies uniqueness consistency if and only
(i) there exists a unique stable matching m²; (ii) for any subset of arms or agents, the preference profile on this subset with their stable-matched pair can induce a unique stable matching.
guarantees that even if an arbitrary subset of stable pairs are deleted out of the system, there still exists unique stable matching among the remaining agents and arms. This condition allows the algorithm find the unique stable matching by detecting the stable matching pairs iteratively. To obtain the unique stable matching in the many-to-one market, we propose new â-condition, which a sufficient and necessary condition for Unqe (proved in Appendix C).
We considers finite set of arms [k] (1. 2.... .... K} and finite set of agents [N] = (1, ,N) with preference profile P. Assume that [N) A2, and [K],=[ct, C2, [CK) } is permutation of {1,
_AN] } is permutation of {1.2. .N
K}. Denote [N], [K] the left order and [N]r[[4] as the right order. The k-th arm in the right order set [K], has the index C₁ in the left
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 (0(ck) (right order) as the stable matched agent set for arm Ck-
Definition 2. many-to-one matching market satisfies the â-condition if. (i) The left order of agents and arms satisfies
Vj E [M], Vk j,k [K],Hsmm²()) Mjjk
where m" mj) is agent j stable matched arm; (ii) The right order of agents and arms satisfies
Vk < S K,c, E [K]r, AN C (N),,7 >o Azt's 40.+1
where the set 7"" (ck) more preferred than A A 40 means that the least preferred agent in 7" (ck) for eg better than A Ay''' 01,+1 for Gj-
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 the left order set [N] prefers arm I in [K] most and has it the stable matched arm. Similar properties for the agent to 91 since arm 1 has q1 capacity. Then the (g1 + 1)-th agent in the left order set [N] has arm in [K] as her stable matched arm and prefers arm 2 most except arm 1. The remaining agents follow similarly. Similarly, the right order gives rankings according to arms' preferences. The first arm in the right order set [K], most prefers the first Ge, agents in the right order set [N], and takes them its stable matched agents. The remaining arms follow similarly.
This condition is more general than existing SPC condition Reny (2021) and can recover the known a-condition in one-to-one matching market Karpov (2019). The relationship between existing uniqueness conditions and our proposed conditions will analyzed in detail later in Section 4.1.2
The main idea from one-to-one to many-to-one analysis is to replace individuals with sets. In general, under â-condition, the left order satisfies that when arm 1 to arm k are removed, agents (Ek-1 Q: + 1) to (E==19) 4:) prefer & most, and the right order means that when Ai to agents A are removed, arm k prefers agents A₁ = {ASt= +1 +1 A +2* A deg }. where Ag is the agent set that are most qu preferred by arm & among those who have not been matched by arm 1.2,.... k algorithm and finding stable matching, we can find two orders of arms and agents by sequential elimination higher ranked agents or arms with their matching pairs. And the ã-condition satisfied the two orders are identical. The next theorem gives summary.
The â-condition can be detected as follows: After running GS
Theorem 1. If market M (K,J,P) satisfies â-condition, then m² (Ei=) 9: + 1) m m 1== 9i + 2) = m (E' 9:) = (the left order), (cx) = As and m (A,) = cj (the
right order) under stable matching.
5

---

Under review as a conference paper at ICLR 2023
Under â-condition, the stable matched arm may not be the most preferred one for each agent j E [AT, thus (i) we do not have m (j) to be dominated only by the agent 1 to agent j 1, i.c. there may exist j' > J. s.t. j' ()) J; (ii) the left order may not be identical to the right order, define a mapping Ir to match the index of an agent the left order with the index the right order, L.e. A(r() = j. From Theorem T the stable matched set for arm & is its first Ok preferred agents ("(c)) AA-- We define Ir as Ir(i)
max(j A, E r (i)), [N]), that is, in the right order, the mapping for arm l E [K] the least preferred one among its most q preferred agents. Note that this mapping not an injective, i.e. 3j. s.t. agent j Air(s) Abrss) An intuitive
representation can be seen in Figure in Appendix B.1
4.1.2 UNIQUE STABLE CONDITIONS MANY-TO-ONE MATCHING
Uniqueness consistency (Unqe) leads the stable matching to a robust one which is desirable property in large dynamic markets with constant individual departure Basu et al. (202T). A precondition of Unqe is to ensure global unique stability, hence finding uniqueness conditions is essential.
The existing unique stable conditions are well established in one-to-one setting (analysis can be found in Appendix C.. and in this section, we focus on the uniqueness conditions many-to-one market, such as SPC, Reny (2021), Aligned Preference, Serial Dictatorship Top-top match and CovelicityNNiedeet & Yariv
Akahossi (2014); Reny (202I) (Definition 7 10 Appendix C.2 Akahoshi (2014) proposes necessary and sufficient condition for unique stable matching in many-to-one matching where unacceptable agents and arms may exist on both sides. We denote this condition Acyclicity". Under our setting, both two sides acceptable, and we first give the proof that Acyclicity" is a necessary and sufficient condition for uniqueness in this setting (Section C.2.4.. We then give relationships between intuitively expressed in Figure I and we give proof for this section in Appendix C.2
newly a-condition and other existing uniqueness conditions,
a many-to-one matching market M J,, PP),, both Serial Dictatorship and Aligned Preference can produce unique stable matching and they are equivalent.
Lemma 1.
Theorem 2. In a many-to-one matching market M = (K. J.P), our â-condition satisfies:
(i) SPC is sufficient condition ã-condition;
(ii) ā-condition is a necessury and sufficient condition to Unqe;
(ii) â-condition is sufficient but not necessary condition to Acyelicity".
Uniqueness Acyclicity
8-condition
top-top match
Distatorship
Aligned PrefemenEc
Figure 1: Relations of Uniqueness Conditions in Many-to-one Market.
4.2 THEORETICAL RESULTS OF REGRET
We then provide theoretical results of MO-UCB-D4 algorithm under our â-condition. Recall that Gj is the globally dominated arms for agent under stable matching m². For each arm & & G give the definition of the blocking agents for arm k and agent j: By₁ 5 j > j. k &f G which contains agents more preferred by arm than j. The hidden arms for agent j is H, [k: k
G3 n (k: B,x # 6). The reward gap for agent j and arm & is defined as A₁K = [)j,m² - Mj.kl
and the minimum reward gap across all arms and agents A = minje[N]
( {minse 4 We
assume that the reward is different for each agent, thus A j.k 0 for every agent j and arm k.

---

Under review as a conference paper at ICLR 2023
Theorem 3. (Regret upper bound) Let m max 1. 3k E H. Bik') be the max blocking agent for agent j and fa(3) j + max (1) is a fixed factor depends on both the left order and the right order for agent j. Following MO-UCB-DE D4 algorithm with horizon T, the expected regret of a stable matching under o-condition (Deffiition 2 for agent E [N] is upper bounded by
E (RR
Sa Ajk
(IoB(T)
π log(T)
Σ
E
(108(T)) + log(T)
A
kgG (i)
kgG J'EB
N2 + (min((1,0
+ + 1ogol122212 (T) ( + 0
(i)) + (a(1)) 1)2" + +22Ki²)
A
where i² = (8 i1 i2) (b1, i2 are defined in equation B and I (J) = max (Ir(j)):))))))))))))))))) s j}. is the maximum right order mapping for agent j' who ranks higher than j.
From Theorem the scale of the regret upper bound under â-condition is O
NK log(T)
A²
Sketch of Theorem The main proof idea is how agents settle down to their stable matched arms inductively. Agent will find its stable matched arm 1 at first since arm is the most preferred arm for agent 1. The same is true for agent to agent Q1- When they all settle down with arm 1, then agent 41 1 will find its stable arm 2 since agent Q1 + 1 has deleted arm 1 in the communication block and thus arm 2 becomes its most preferred arm. We can show by induction that agent will find its stable matched arm after agent 1 to j 1 has settled down. The regret of agent j can be decomposed into four parts: sub-optimal play, collision, communication, and local deletion. Both collisions between agent j and other agents in the blocking agent set and sub-optimal play are due to the wrong estimation of UCB index (Lemma 6). Communication regret can be bounded by the length of the communication block. Local deletion regret can be controlled by the threshold we set (line in Algorithm 1p. The regret bound is decomposed as follows, and the complete proof can be seen in Section 3
Lemma 2. (Regret Decomposition) For a stable matching under â-condition, the upper bound of regret for the agent j E [N]] under our algorithm can be decomposed by:
(T)
E [SFr..]
+ +min(0|H,)1 1)E [Sv.]]
((K 1 jB.m (1) log (T) NKE (Va))
(Regret before phase Faz))
(Local defetion)
(Communiicatinn)
Σ
Σ
8appi.m (f)
(og((T)
V log(T)
kgG; J'EBAakEGY
(Collision)
8a (log(T) + log(T)) (1+ (á(a) + +1)
AGGJUm (1) A
A²
(Sub-optimal play)
where Fag, Vaj are the time points when agent j enters into à-Good phase and LoLow Collision phase respectively, defined in Appendix
5 DIFFICULTIES AND SOLUTIONS
From one-to-one setting to many-to-one setting First, arm preference is difficult to learn in decentralized many-to-one setting. Influenced by capacity, 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 identifying arm preference for each agent encounters more challenges, and then influences total regret. In order to solve this, we introduce the dominated arm set G into communication block to identify arms who preferred by higher ranked agents than agent j. The arm set G is one of the main sources that prevent agent j from forming a stable matching, and will be deleted before each phase to reduce collisions.
7

---

Under review as a conference paper at ICLR 2023
Second, the idea from one-to-one to many-to-on is transition from individual to set. It is natural to split sets into individuals or correspond sets to individuals. Although we assume that arm preference is over individuals Roth & Sotomayor (1992); Sethuraman et al. (2006); Altinok (2019). the agents matched by one arm are not independent. Specially, arms with capacity q can not just be replaced by q independent individuals with the same preference. Since there would be implicit competition among different replicates of one arm, and he can reject previously accepted agents when he faces a more preferred agent. In addition, considering capacity, the matching result for each arm A set rather than an individual. In order to give a description of a uniqueness condition, we need to give a threshold for the range of stable matched agents set. The Ir in Basu et al. (202T) is a one-to-on mapping that corresponds the agent index in the left order and the agent index in the right order, which related to regret bound (Theorem in Basu et al. (202T) and Theorem 3 in our work). While it does not hold in our setting. We construct new mapping ir (Figure in Appendix ( which connects the index of agents in two orders in many-to-on setting. Ir maps each arm & to the least preferred one of its stable matched agents in the right order, thus giving mapping between individuals and individuals.
From a-condition to â-condition In general markets, preferences are difficult to learn when one arm can accommodate multiple agents. We consider the market with uniqueness condition. For one
thing, equilibrium plays important role in the fairness and stability of matching problems. For
another, to reduce the conflicts among agents, we adopt an arm deletion idea and Unqe (Definition I can ensure that the deletion does not affect the stable matching.
Our work extends a-condition to many-to-one setting, which needs to define preferences among sets. However, there might be an 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 one-to-one setting, we come up with a possible constraint by regarding the arm and the least preferred agent in its matched set as the matched pair and define preferences according to this grouping. It turns out that we only need to define arm preferences over disjoint agent sets to complete this extension as a-condition is defined under the stable matching, which can also fit the regret analysis well. Under this â-condition, induces a hierarchy in the matching market, which reduces the regret bound from collision block to the number of matchings with sub-optimal arms by induction, thus making the regret reach the lower bound related to time horizon T and reward gap A (Appendix D in matching problem with bandit algorithm Sankararaman et al. (202T).
In summary, there might be other possible ways to extend the a-condition but we present a successful trial to not only give a good extension with similar inclusion relationships but also guarantee a good regret bound.
6 EXPERIMENTS
In this section, we verify the experimental results of our MO-UCB-D4 algorithm (Algorithm Ip 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 1 for each agent, then the reward gap between any adjacently ranked arms is A- = I/N. The reward for agent j matches with arm time t (t) is sampled from Ber(H5,s). The capacity is equally set as g = N/K. We investigate how the cumulative regret and cumulative market unstability depend on the size of the market and the number of arms under three different unique stability conditions: Serial Dictatorship, SPC, ä-condition. The former cumulative 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 t. In our experiments, all results are averaged over 10 independent runs, hence the error bars are calculated as standard deviations divided by v10.
Varying the market size. To test effects on cumulative regret and cumulative unstability, we first vary N with fixed K with market size of N E {10, 20, 30, 40) agents and K = arms. The number of rounds is set to be 100, 000. The cumulative regrets in Figure 2 (c))) show 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 agents, resulting in an increase of
8

---

Under review as a conference paper at ICLR 2023
cumulative regret. Similar results for cumulative unstability are shown in Figure (f) When N larger. the number of unstable pairs becomes more. With the increase of the number of rounds, both two indicators increase first and then tend to be stable. The jumping points caused by multi multi-phases setting of MO-UCB-D4 algorithm.
Intea/Dcahee
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, â-condition.
Figure 3: Cumulative regret and cumulative unstability of MO-UCB-D4 of size with K {2. 5. 10, 20) under Serial Dictatorship, SPC, ä- condition.
Varying arm capacity. The number of arms K is chosen by E (2 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 Figure3b))dhy
regret in (igureBla)()Ce and the cumulative unstability 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 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.
increase monotonously.
CONCLUSIONS
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 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,
which obtains O loggg)
stable regret under ã-condition. By carefully defining mapping from
A
arms to the least preferred agent in its stable matched set, we could effectively correspond arms and agents by individual-Be to-individual. A series of experiments under 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.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Azar Abizada. Stability and incentives for college admissions with budget constraints. Theoretical Economics, 11(2):335-756, 2016.
Takashi Akahoshi. Singleton core in many-to-one matching problems. Mathematical Social Sciences, 72:7-13, 2014.
Ahmet Altinok. Dynamic many-to-one matching. Available at SSRN 3526522, 2019.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
Orly Avner and Shie Mannor. Concurrent bandits and cognitive radio networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 66-81. Springer, 2014.
Sophie Bade. Random serial dictatorship: the one and only. Mathematics of Operations Research, 45 (1):353-368, 2020.
Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log² regret for decentralized bandits in matching markets. In International Conference Machine Learning, pp. 705-715, 2021.
Anna Bogomolnaia and Hervé Moulin. A new solution to the random assignment problem. Journal of Economic theory, 100(2):295-322 2001.
Sarah H Cen and Devavrat Shah. Regret, stability & fairness in matching markets with bandit learners. In International Conference on Artificial Intelligence and Statistics, pp. 8938-8968, PMLR, 2022.
Simon Clark. The uniqueness of stable matchings. Contributions in Theoretical Economics, 6(1), 2006.
Sanmay Das and Emir Kamenica. Two-sided bandits and the dating market. In IJCAI, volume 5, pp. 19. Citeseer, 2005.
Jan Eeckhout. On the uniqueness of stable marriage matchings. Economics Letters, 69(1):1-8, 2000.
David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69)1)--11, 1962.
Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-teen-commi strategies. Ad- vances in Neural Information Processing Systems, 29:784-792, 2016.
Virginia Gunn, Bertina Kreshpaj. Nuria Matilla-Santander, Emilia F Vignola, David H Wegman, Christer Hogstedt, Emily Q Ahonen, Theo Bodin, Cecilia Orellana, Sherry Baron, et al. Initiatives addressing precarious employment and its effects workers' health and well-being: A systematic review. International Journal of Environmental Reseurch and Public Health, 19(4)2232, 2022.
Gregory Z Gutin, Philip Neary, and Anders Yeo. Unique stable matchings. arXiv preprint arXiv:2106. 12977 2021.
John William Hatfield, Fuhito Kojima, and Scott Duke Kominers. Investment incentives in labor market matching. American Economic Review, 104(5):436-41 2014.
Eugene Ie, Vihan Jain, Jing Wang, Sanmit Narvekar, Ritesh Agarwal, Rui Wu, Heng-Tze Cheng, Morgane Lustman, Vince Gatto, Paul Covington, et al. Reinforcement learning for slate- based recommender systems: A tractable decomposition and practical methodology. arXiv preprint 190. 2019.
Meena Jagadeesan, Alexander Wei, Yixin Wang, Michael Jordan, and Jacob Steinhardt. Learning equilibria in matching markets from bandit feedback. Advances in Neural Information Processing Systems, 34:3323-3333 2021.
10

---

Under review as a conference paper at ICLR 2023
Ramesh Johari, Vijay Kamble, and Yash Kanoria. Matching while learning. Operations Research, 69 (2):655 681, 2021.
Alexander Karpov. A necessary and sufficient condition for uniqueness consistency in the stable marriage matching problem. Economics Letters, 178:63-65, 2019.
Bettina Klaus and Flip Klijn. Local and global consistency properties for student placement. Journal of Mathematical Economics, 49(3):222-229, 2013.
Lydia T Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In International Conference on Artificial Intelligence and Statistics, pp. 1618-1628. PMLR, 2020a.
Lydia T Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. arXiv preprint arXiv:2012.07348, 2020b.
Jinpeng Ma. The singleton core in the college admissions problem and its application the national resident matching program (nrmp). Games and Economic Behavior, 69(1):150-164, 2010.
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.
Hai Nguyen, Thanh Nguyen, and Alexander Teytelboym. Stability in matching markets with complex constraints. Management Science, (7(12):7438-7456 2021.
Muriel Niederle and Leeat Yariv. Decentralized matching with aligned preferences. Technical report. National Bureau of Economic Research, 2009.
Erhun Özkan and Amy R Ward. Dynamic matching for real-time ride sharing. Stochastic Systems, 10(1):29-70, 2020.
Jaeok Park. Competitive equilibrium and singleton cores in generalized matching problems. Interna- tional Journal of Game T'heory, 46(2):487-509, 2017.
Philip Reny. simple sufficient condition for unique and student-efficient stable matching in the college admissions problem. Economic Theory Bulletin, 9(1):7-9, 2021.
Antonio Romero-Medina and Matteo Triossi. Acyclicity and singleton cores in matching markets. Economics Letters, 118(1):237-233) 2013.
Jonathan Rosenski, Ohad Shamir, and Liran Szlak. Multi-player bandits a musical chairs approach. In International Conference on Machine Learning, pp. 155-163. PMLR, 2016.
Alvin E Roth. On the allocation of residents rural hospitals: a general property of two-sided matching markets. Econometrica: Journal of the Econometric Society, pp. 425-427, 1986.
Alvin E Roth and Marilda Sotomayor. Two-sided matching. Handbook of game theory with economic applications, 1 1:485-541 1992.
Hannu Salonen and Mikko AA Salonen. Mutually best matches. Mathematical Social Sciences, 91: 42-50, 2018.
Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate delete: Decentralized competing bandits serial dictatorship. In International Conference on Artificial Intelligence and Statistics, pp. 1252-1260. PMLR, 2021.
Jay Sethuraman, Chung-Piin Piaw Teo, Liwen Qian, et al. Many-to-one stable matching: Geometry and fairness. Mathematics of Operations Research, (1(5):881-596 2006.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285229 2944, 1933.
11

---

Under review as a conference paper at ICLR 2023
A RELATED WORKS
The study of matching markets has long history in economics and operation research Bogomolnaia & Moulin] 200T); [ade (2020); [Roth & Sotomayor (1922) with real applications like school enrollment, labor employment, hospital resource allocation, and so on Abizada (2016); Ma (2010); Roth (1986); Hatfield et al. (2014). A salient feature of market matching is making decisions for competing players both sides Thompson (1933); Gale & Shapley (1962). MAB is an important tool to study matching problems under uncertainty to obtain a maximum reward, and upper confidence
bound algorithm (UCB) Auer al. (2002) typical algorithm, which sets confidence interval to represent uncertainty.
This paper contributes mainly to intersection of MABs and two-sided matching markets literature. We analyze recent works in this direction. After Das & Kamenica (2005) proposed to apply MAB in learning preference, the learning uncertain matching system provided inspiration for the design of online platform, and then there was series of algorithm design Liu et al. (2020a b): Sankararaman
al. (202T); Basu et al.] (202T): Gunn al. (2022): Malgonde et al. (2020); Johari et al. (2021). In general centralized market without conflicts, Liu et al. (2020a) applied the common ETC and
UCB algorithms to the matching market, and obtained the regret order of O NN log(T)) ). Following this, a more general market, decentralized one, was studied by traditional UCB algorithm, and obtain O (xx (N*) K log²(
A
regret by setting delay parameter to reduce collisions among agents. By limiting preferences, we can get algorithms that have better convergence or can learn information about unknown preferences. Under Serial Dictatorship condition, [Sankararaman et al.) (2021) proposed an phased UCB algorithm with global communication to solve decentralized market with nonlocal information. As Serial Dictatorship condition is too strong, a weaker Uniqueness Consistency condition is applied in this online data-driven market [Basu et al. (2021). Under the conditions on preferences, the regret bound in decentralized matching reduced to O However, these valuable articles focused on one-to-one matching that one arm can accept only one agent as his stable pair. Motivated by these, we extend works not only many-to-on setting, but also under weaker uniqueness condition which is first introduced by this work.
N log(T)). A
In terms of uniqueness conditions, a flurry of works proposed some descriptive conditions in one- to-one setting, like the Serial Dictatorship Sannararaman et al. (202T). the No Crossing Condition (NCC) (2006), the Sequential Preference Condition (SPC) Feckhout (2000), the a-Condition (2019). However, a few of works concentrated on the unique stable property in many-to-one market. Some exiting conditions are SPC, Reny (2021), Aligned Preference, Serial Dictatorship which are
Top-top match and Acyclicity Niederle & Yariv 2009);; Akahoshi (2014) Reny (202
strong that are not universal in algorithm design.
The research many one market is relatively meaningful work recently. Leaning preferences and form a stable matching are also key features in this setting JJgadeesan et al. (202I). Altinok (2019); Ozkan & Ward (2020): Johari et al. (2021) studied dynamic many-to-one matching. For one thing, their concerns provide motivation for our work, for another, they also provide more latent future directions for the application of MAB in matching.
B ANALYSIS FOR OUR G-CONDITION
B. MAPPING UNDER ā-CONDITION
To connect two sides of the market, we define mapping Ir as Ir(i) = max(j: A, E (1)), [N]], from agent index in the left order to agent index in the right order under â-condition since arms in the right order can select more than one agents. From Theorem [ the stable matching for arm & is its first 9k preferred agents 7 (ce) = Al. Recall that the preference is strict. Denote
A(a)). Then the rule of the mapping Ir in the right order we set is as follows: the mapping for arm l E [K] is the least preferred one
that the first qs agents are ranked as A > A(2) > ...
(oe). ...A(A
among its most preferred qu agents, that is, Arr() = ((a)) And the intuitive representation can be seen in Figure g If we assume that Ci2 = C₁. then the right order can be seen form the figure and Ir(q1 + 1)
Ir(g1 + deg) qe, holds.
12

---

Under review as a conference paper at ICLR 2023
Left Order
Right Order
Agents
Arms
Agents
A = A
(9c)) Aye = =A (
41
A +1 1
21
+1
K
CK
(aeg) AN Ag
N
Figure 4: The mapping from the left order to the right order (assume that C22 = =1)
B.2 PROOF FOR REGRET ANALYSIS UNDER ē CONDITION
The proof idea is mainly follows. We construct phases with good properties and denote that the time point of agent j reaching its good phase by Faj- From phase Faj on-wards, agent j + will find the globally dominated arm set G5+1 and will eliminate arm m (j) according to Algorithm I Then the process of each agent divided into two stages: before Foj and after F'aj. After Faj, according to the causes of regret, it is divided into four blocks: collision, local deletion, communication, and sub-optimal play. Phases before Faj can be bounded by induction.
We first give some notations and definitions:
Rank for Each Agent Recall that if arm & prefers agent j over j', we denote j > j'. And under ã-condition, the stable matched arm m mj) for agent j agent j's most preferred arm among remaining arms who still have vacant seats within its capacity. Denote the agents that match with the stable matched arm of agent j by 7 (m" (j)).
Classification of arm sets The dominated arms set D, = (m" : j' >m* j} means the stable matched arms of agents who are more preferred by these arms than agent and the globally dominated arms set under stable matching m is Gj. a subset of DD. Global deletion here follows the left order. Recall that O [1] is the best arm for agent j in phase i. Algorithm [ the estimated dominated arms set in phase is [ [O j >0,116 j} and the globally dominated arms in each phase G2 C D2 For each arm & & G we give the definition of the blocking agents for arm and agent j: By, J j > k & G J. which contains agents more preferred by arm than j. The hidden arms for agent j is Hl = {k & G3) n (k: B₁ + 0}.
Under SPC condition, the stable matched pair is also the best arm for each agent, and agents that arm matches with are its qu most preferred agents. can be easily understood by the definition of Top-top match. While under â-condition, the stable results may not be the best choices for the two sides. We then define a set NTT()), in which each arm is a stable matched arm for some other agents Ay, is sub-optimal arm for j. and is preferred by that arm than its stable matched pairs 7" (k)) The NTT()) set can be understood as "not Top-top match" stable results, and can be mathematically expressed
k: {{x=
=
NTT()) =
[K]. < (): & 2m (m))m())),m)mmmm"mmmmm")))"("))) s.t.k m (Ap) and j > k > ((6))
We obtain D2 G,(b] in the one-to-one setting
13

---

Under review as a conference paper at ICLR 2023
where > y (k) means that k prefers than any agents in (*()).
Phases with Good Properties In the decentralized market with limited information, estimating preferences of other agents is challenging. thus we set a communication block. This block for agent mainly to judge the dominated arms agents that rank higher than j. where the dominated arm is measured the arm with the most number of times matched with each agent. Under our a-condition, the most preferred arm is not necessarily the stable matched result, hence if arms in NTT()) match too many times with j, agents cannot distinguish the preference of agent During the time period with limitation of arms in the NTT(j), other agents can identify the preferences of j, which helps to reduce conflicts.
Warm-up Phase for some j [N] under a-condition if the following conditions hold for each arm k E NTT()):
Definition We say phase
(i) arm k is matched with agent at most 10ad in phase i, where is a parameter of UCB index (line A
in Algorithm T
(ii) arm k is not agent j 's most matched arm in phase i.
According it, introduce the Unlocked phase (Uz) that all phases and after it, agents A A₃
all into warm-up phase. Let min (N 1) 10cd reward gap, and
A < 02(6-1)) where A is the minimum
phase i is a warm-up phase for agent j; [w]i 0, otherwise.
(f (r(i)-1 II f'=1
(00) (
U, = max
ii, min
II
WwWW', L =
L
P2i
Definition 4. We say phase is a â-Good Phase for some j E [M] under â-condition if the following all satisfied:
(i) The globally dominated arms for agent j are globally deleted in phase Then, Gy = G3 holds.
(ii) The phase is warm-up phase for all agents in L3 = tύ' mm E NTT(")).
(ii) For each arm k & G U m" (j) (neither be globally deleted nor stable matched arm of agent j),
arm l is successfully matched with agent j phase at most A
10ai times.
(iv) The stable matched arm m" (j) selected the most number of times in phase i.
The definition â ã-Good Phase is naturally to be brought up that during this phase, agent j has collisions with low probability. When agent j selects arm competing with more preferred agent by this arm, it receives zero reward with high probability (w.h.p.), thus condition (i) in Definition is necessary for lower regret. Recall that the stable matched pair may not be the best pair for (it) aims to limit arms in other agents' NTT sets to avoid too many conflicts. And (ti)), (év) are beneficial for other agents estimate the stable matching of agent j. Similarly, define d-Low Collision Phase as Basu et al. (20TT):
Definition 5. We say phase: is ō-Low Collision Phase for agent under ā-condition if:
(i) Phase is GoGoo Phase for agent 1 to agent j;
(ūi Phase is & G-Good Phase for agent j' UKEH, Bik.
Define that
(
(II Iwli'5"1 = mnu(o0)) j"EC,
Faj = max f mimiin(i:
II
IG. I.. K.51 II ==1
(1)
221
and
Vas = max
(i. II IIc. [6 1) u
(2)
P21
14

---

Under review as a conference paper at ICLR 2023
where the definitions of IC, [i, and l.. [t, is similar to 1w [t.
Hence, all phases on and after phase Fay are ä-Good Phase and all phases after phase Vaj are LoLow Collision Phase for agent j. Hence, 1w [i, LC.. [i,5] and 1c, [ū,j] are the indicator represent whether phase is a warm-up phase, o-low deletion phase and a-good phase respectively.
propose some propositions. Proposition 1. The stable matched arm m² mi) (j) for agent can be blocked by agents in Lj, where Cj { () E NTTG")
Before we give the complete proof of the regret bound in Theorem 3
Proof. Assume that we have stable matching m By contradiction, if >m (f)) j' but Hj.m (i) < (j)) then (j, mmmmm" (j')) forms a blocking pair since they prefer each other than matched one but they are unmatched, this leads to the instability of m So, if j mm) j', then Pj.= > (jm))))) under the stable matching. Thus, if j' > mm (1) J. then Py (i) > Pim (1) then (j) NTT(J))
Proposition I tells us that m (() can be blocked only by agents in Lj, and the next proposition gives the range L.
Proposition For each agent j E [M] L, S - A₂
Proof. Under ä-condition, for Ak: < j S K, Co E [K]r. A, E [N],, (cEe) Fox Aj. And by Theorem I (cx) Ag. Therefore, for Vj,j' E [M], and j < < A, (m,) Ay- In particular, for any J > Ir(i), we have = Aira) m Ag. This implies that for Vj 2 Ir(j), we not obtain j' m j. hence mf( $ NTT(J"), that is, for Vjy 2 1r(t). j' & Cj. Then (r()-1 Ag. Lj C c
Proposition 3. For each agent j E [M] Fay I max happens with probability 1.
max{Ueee (Ua-G)-1) max(Fay : j S 1)}
Proof. By the definition of Uj. we know that on and after phase U(r()))) all agents {Ay
1,2..... (r(j)- 1} are in warm-up phase. By proposition 2 the set of deadlock agents as 4, 5 - -r()) Agr Hence, all agents in L5 are also in warm-up phase on and after Uir()-1- Further, the agents 1 to (j 1) are in ä-good phase from phase max (Fay S j و 13 onwards. Then the proposition holds w.p.1.
m²()) (j) always As the events decomposition for regret minimization block in Lemma 6 requires that m²
exit and will not be deleted, is important to find conditions or a certain phase with good properties to guarantee that m (j) will not be globally deleted or locally deleted. The next lemma give us theoretical guarantee.
Lemma 3. Let i = min : (N 10e < 022-11 }. for any phase i (i 2 ii) and any agent
j E [N], the following properties holds.
(a) If phase i and (i -1-1 1) are warm-up phases for all jr E Cy then m²( will not be globally deleted or locally deleted almost surely, i.e. m² (j) $ L,00
(b) If phuse: i 2 min (U(r)()11); Fay} +1, then m² (J) 25(1] U Gyli] a.s.
(c) If phase i 2 Va, + 1 is a low collision phase for agent j then C = a.s.
Proof. (i) All agents j' can block arm m² m="() (j) are in C, by Proposition 1 And m² E NTT(')) for any agent j' E Lj due to the definition of E, Therefore, if all agents In C, are in warm-up phase in phase 1), then m" m²()) (j) & Gý(i) because by the definition of warm-up phase for agent and
15

---

Under review as a conference paper at ICLR 2023
m²() NTT(")), (j) is not agent j' 's most matched arm. Hence, m m²()) $ Gyli]. further- more, the total number of times the arm m m²()) (j) can be deleted is at most (EE 4: ---1 10st for
any 2 i1 which is less than the local deletion threshold. So m m²(i) & L, U Gylb] after phase in
(ii) (a) L, S - - 'A holds by Proposition this implies that for phase 2 Ul + 1 (i.e.
i 1 2 U+ 1) is warm-up phase for all agents in L = (i' m² E NTT()).
(b) By the definition of Fag. all agents Cj = - m² E NNT())) are warm-up phase for phase i 2 Fajt1.
By (a), (b) and (i) we know that (ii) holds.
(iii) It can easily check by the definition of Vaj.
B.3 PROOF FOR THEOREM 3
After defining Faj and phase Faj and after Faj- We denote S, by the beginning time point of phase i. The regret during time period [Sr,,, T] can be decomposed by four blocks: Local Deletion Block, Communication Block, Collision Block and Sub-optimal Block. The regret during time period [0, Sr.j] can be bounded by induction with j (I (Lemma
we divide the whole process into two main modules: the process before
Local Deletion Block. Lemma 3 implies that there is no collision after phase Vaj. so we only need to consider the regret from Faj + to Vaj- Following our algorithm, there is at most 02 collisions when pulling an arm from the set H, in each round. This amounts
Vas
Vas
Σ
0 0-22-1
0 M 2'-1
Fag
KEH,
im 11
1 - 2Va
1-2 0|Hly = (2 1)0
Sva; 0114y1 S min(Sv...))) 1) 01,11
Communication Block. In the communication block, there are N sub-blocks, and the duration of each sub-block is K. Agent pulls arm 1, arm 2, ..., arm K in order in the j-th block and pulls (111] in other blocks, where O, i] is the arm that matched the most times in the regret minimization block in phase i. The best arm for agent j is not played in all but (K 1) number of steps for each communication phase after phase Faj + 1, and other agents j' collide at most once after phase Voj (since each of them enters good phase). Hence, the regret comes from communication block is ((K - 1 + |B ())) (7)) NKE [V.j]).
Collision Block. The regret caused by collision from phase Faj to Vaj has been included in the previous communication block (the regret of the period during Faj + 1 and Vas is rel- atively loose). so we only consider the regret after phase Vaj. After phase Vaj + 1, regret comes from the collision between agent j and the agents in the set BjAk- And by the definition of Vaj, agent j and agent j' Byx have deleted dominated arms for themselves, this leads to
Enec; EyeB, ()) (Ny&(T)) Ny And by lemma the number of the matchings with suboptimal arms can be bounded, and the main resource of regret is bounded as scale of O NNNKN log(T)
Undde ā-condition is no longer the case as agent is not the most preferred agent for arm 1. For agent A and its stable match arm C1, Ci may be the best arm for agent A, but for ei have A₁ its best agent. Therefore, agent A₁ will not delete it's stable match pair arm 01, but unless global deletion eliminates better arms will not converge to this arm.
'It is ã-condition that induces hierarchy in the matching market, which reduces the regret bound from collision block the number of matchings with sub-optimal arms by induction.
16

---

Under review as a conference paper at ICLR 2023
Sub-optimal Play Block. From phase Faj + 1 on-wards, regret happens for agent j when agent j selects arm & Gj m)) and successfully be matched. This amounts to Exegzum ()) ( -Nr((rr,)) regret, and it can be upper bounded by Lemma
Then illustrate the relationship among those phases with good properties and indicators. We first show that for phases 2 Uag-1 + I, the probability that phase is not a Warm-up phase for agent A, is low. Let
10ai
41 min (N 1)
A < 002
(3)
d2 min(i: C(i 1) - v 2
(4)
then we have the following lemma.
Lemma 4, For phase i 2 i* max(8, (1, i2), for Vj E [N], a > 1, then the following holds:
(1+
64
P ((1 (i, A,] = 0) n (i Un + 1)) S (K (K-j)2--00 j)2-
2
Similarly, we give the relationship between Faj and a-Good phase. Lemma 5. For any agent j and phase 2 i', and for > 1, then
PP ((1G, [ = 0) n (i 2 Faj + +)) - (K - ((--)
1+
64
A2
We only give the proof of Lemma 4 and another one can similarly be verified.
Proof.
P [[)
Uaj-1
10ad
vIa
P
UKENTTIA, - NAj 11)
} ni 2 (Uag-1+11)
A A
Σ
(UiES
(A,,M()))
(t),((t=
10ai
n (4((A) = ni (Uos-1
A Ag
KENTT(AA)
(S:1-1)
10ad
Σ P
(Na,,
) (t uAyo, (t 1))
(166 (ENTT(A,) KES:
64
= [NT((A))) -((a-1)
(1+
A
64
< (K - 1)2-
A
The inequality (1) is because that if phase is not a Warm-up phase for agent Aj, there exists an arm E (NT((A)), which is played more than 10ni. times in phase i. Next, (ii) holds since
the probability of union is less than equal the
of probability. By Lemma m" (A,) g
G U LA. [1]. Hence, the inequality (dii) holds since (AA, = k is equivalent to that the UCB index (line Algorithm I of arm m "j) a, can not be less than arm k.
We now give the upper bound of E N (SP,SP.))) )} which is helpful to bound the regret resulting from collision block and sub- sub-optimal block.
Lemma 6. For Vjj E [N], k & Gj m for 1
8
8
E ( < ((x))
+
(alog(T)) + Va (og(T))+)
AZ
A
j.k
j.b.
17

---

Under review as a conference paper at ICLR 2023
Proof. Due to Lemma m² (j) will not be globally deleted locally deleted after phase i 2 (Fas + 1). Denote (t] as the arm that agent pulls at time t. After phase Faj, the reason for agent J pulling arm k rather than m² (j) are as follows: (1) the UCB index of the optimal arm m (j) is less than ()) 6 (2) [t)) = and its UCB index is larger than pj. (1) - 6. For any & G3 (i) and O.
T Σ SFa
(T) - (SF =
((+(i) k}}
H((s,,(t)= 2 () - e) A ( = k)} + Huz.m=(1 (1) S My (1) E}
S=FFaj
(4)
(6)
First, we bound (a)-
T
Σ
(((2)(()22 (im--() c) -)) = -)
E
t= (
of ((issa((-1++ 1)+ V
Nt - 2 2) -)) (((())))()) =n0
2a log()())
<R
1= (=ara; -1
T
20 ITg(T)
2 (1) -)) (4(G) = f0o}
<B
(Rgall 111/ 1/1/
(1 - 1)
T
(Rgh(()) + log(T)
2 14. + D - e) }
<B
(olog(T) + v aa (Tg +1)
<1 +
j c)2
Then we turn to bound (b)
E
Σ
(j)m S ())m(())
SFaF
T
<E
()) I ()) -
N1 -1) S ().mm()) -0)
2a log(t)
<R.
-1)+
V
[=1
s=1
2a log(t)
=)
exp
2
8
T
SEa
exp(
2
1=1
8=1
2
<v(aa=
z
By choosing e == Aut, we have
E (T) Nea(Srr,)] 1 (0))
8
+1
+
8
(olog(T) + (og + 1)
A2
A2 j.k
j.k
18

---

Under review as a conference paper at ICLR 2023
We define (i)ax(() max(Ir(f)) : S J s. and F3 = max (Urmmx(0)11, max(( S
d') and F, Foj. Then we introduce a lemma to bound the probability that a phase i is
not an â-Good phase when i 2 Faj + 1. Lemma 7. For any j E [N] and m 2 1, the the following hold with 1 (ir max (8,
64
2 2- (a-1)(x 2)
Fmm
S 2il + (Irmax (f) + -+j-j)
2) 2) (1))T + +K[1+ +
A
(2(a-1) - 1)2
E
2
s 261 + (Ir (j) + - 2)
2 + K(1 +
A²
64
2-(a-1)(ff-2
(2(a-1) 1)²
The proof is the same as Basu et al (001I)
Hence, the upper bound of IE [F is
E [Fal E C(FFs 1) 2Pas SE C(F) - 1) 1) 2F3
$ C(2i 1) + C( (j) + - 2) + (I (f) + 2
64 2 (a(--11(6--1
+ (c+ (c+1) (Ir ((m+))(()mx)))) ()) - 22) K + A (2(a-1) 1)2
where C' a constant term.
Then for formula with term E [Sv,]], transform its upper bound another term related to E S F F)mm
since
PO.D) Vaj = max (Farsti), UsE UkeH, Fus) S max (Ro4t) Poo)) = Fmmax(()
Hence, E. [Svaj] S E S [
Lastly, the regret can be bounded by the decomposition of E [Sp..] and phases after SF., with properties above, where phases on and after SF., contain local deletion, collision, communication, sub-optimal play blocks.
[T)] E [Sr..]
() ((K - 1 1Bmm (n)) log2(T) NNE (V..])
Σ
Σ
8amplaj"
log(T) + +. log(T)
+
Σ
(log(T) 8a
+ a
log(T))
P'k
kgGz j'EBy.ikk0Gy
kgGjUm
+ NK
[+
+ 1)
80
I Σ
Σ
8apkyy
[og((T) + log(T)
A
A
kRG j "EB
Σ
8a
(og(T) + V
log(T) + cg (T)
Aju
k4GjUm (i)
N2
fa(i) (166)))1))+1 N22KF)
+0
A2
min
C PROOF FOR UNIQUE STABLE CONDITIONS
C.I UNIQUENESS CONDITIONS IN ONE-TO-ONE MATCHING.
There are many existing conditions that guarantee the unique stable matching in one-to-one setting. like the Serial Dictatorship Saakararamann al. (2021), the No Crossing Condition (NCC) Clark
19

---

Under review as a conference paper at ICLR 2023
(2006), the Sequential Preference Condition (SPC) Eeckhout (2000), the e-Conditiin Karpov (2019). Previous works tell us that top-top match and SPC condition can lead to a unique stable matching in both one-to-one Niederle & Yariv (2009): Clark (006) and many-to-one setting Reny (2021).
Niederle & Yariv (009)) use the Top-top match property instead of a-reducibility for the same meaning in the one-to-one setting. Serial Dictatorship in one-to-one setting means that for each agent, the arms are ranked heterogeneously, in an increasing order of arm-means which is different for each agent-arm pair while the agents are ranked homogeneously across all arms, and vice versa. Followed by Romero- Romero-Medina & Triossi (2013); Niederle & Yariv (2009), we know that Aligned preference is equal Serial dictatorship marriage problem as they are both equivalent no cycle property. And NCC and Serial Dictatorship are not mutually inclusive, which can be seen in Clark (2006). Hence, the relationship can be represented intuitively in figure
Uniqueness Acyelicity*
a-condition
ficondiiion
SPC
SPC
a-meducible co top-top match
top-top match
Serial Dictatorship & Aligned Preference
Serial Dictatorship
NOC
Aligned Preference
Figure 5: Relations of Unique Stable Conditions in One-to-one (left) and Many-to-one (right) Setting.
C.2 UNIQUENESS CONDITIONS IN MANY-TO-ONE SETTING.
In this section, we focus conditions that guarantee the unique stable matching in the many-to- one setting, such as SPC, Reny (202T). Aligned Preference, Serial Dictatorship Top-top match
and Acyclicity Niederle Yariv (2009) Akahoshi (2014): Reny (202I) and give the proof of the
relationships among uniqueness conditions
Definition 6. (Aligned Preference.) many-to-one market M = (K, K (K)) J ())eM,, the preference profile satisfies
Vk: VKEK, < (1.a)
vj VjENKK>, K. <' (1.b)
then the market has aligned preference. The one-to-one setting has the same definition. Definition 7. (Serial Dictatorship) We say that if all arms (school) have the same preference for agents (students), while agents' preferences are heterogeneous (vice versa), then the system satisfies serial dictatorship.
Definition 8. (Top-top Match) A stable pair (k.j) is a Top-top match for sub-market M' E EME if. for arm k, agent j the favorite candidate in M', and vice versa.
Definition 9. (SPC) SPC condition in the many-to-one setting Reny (2021) 1) is to require the existence of a sequence of agents 1,2,....
which each agent appears once, and a sequence of arms 1. 1.2.... ... .K in which each arm appears once for each seat in its capacity, such that & > k for every > and E [N]; in addition, such that >k j' for every j' > and E [K].
C.2.1
PROOF FOR LEMMA
Proof. +):
Park 2011 or pair for every sub- problem. TThe remark in Niederle & Yariv 20099 tells that Aligned Preference is stronger than Top-top match and
Clark 2006) introduce that matching problem is a-reducible if there top trading single
SPC condition.
20

---

Under review as a conference paper at ICLR 2023
Table I: Preference Profiles
(a) Exml: Companies
(b) Exml: Workers
C1 81 52 > 83 > 81 > 85
51 C > 02 > 43
02 82 83 81 >
52 0 > 0 >
C3 83 > 84 85 81 > 82
83: 63 02 C1
84: 6> 02202 02
55 02 >
(c) Exm2: Companies
(d) Exm2: Workers
G1 81 > 82 83 > 84
81: q > 0g C
(2 83 > 82 81
85
82: 6
02 03
C3 85
82 84
83
0 > C1 03
84 6 02 03
C3 Cg
Serial Dictatorship = Aligned Preference. order to distinguish the symbols of agents and arms, we consider arms set {cx, k = 1,2..... K} and agents set {sy : = 1,2, .N.. If arms have the same preference for individual agent, then there no cycle in the preference of the arm, i.e. there is no case that
37, 80 > 8T Ser 8T-1" 1..1... Fe 80
for 8o, $1,-.. ST and Co, -.. Otherwise, assume that there exists the cycle above, then by the same preference of arms, know that -> And then so > 81 and $ > 80, hence So > and $1 > co sp. which yields contradiction.
Now we prove that no cycle property implies Aligned preference. By contradiction, if there exists such that 8y 7 Sy. for l j. then we can construct cycle:
8k >a xe, $--1" ... 9k-2 7 cx-s 8 bc Sk.
<):
Aligned Preference + Serial Dictatorship. We first illustrate that aligned preference leads to no cycle property. By contradiction, if there cycle
S1 > cq 8T > or 8T-1 82 >z
for some 81, 82, ST, C1 C2. contradicts the aligned principle. Then, if there is no cycle of length two, which implies that all college have the same preferences because all students are acceptable to every college, which induces group serial dictatorship property.
and T. It is obvious that it yields 81 > 8T, Tr,T3 1, which
C.2.2 PROOF FOR THEOREM
(i) Proof for the relationship between SPC and ã-condition
SPC states that after eliminating all Top-top match, there is at least one new Top-top match in the remaining system under restricted preference profile. Then satisfies ā-condition naturally. However, examples below tell us that SPC can not imply â-condition. We give two examples to illustrate this relationship where the order that an agent successfully matches with its stable pair corresponds to the left order and right order.
Example Consider market with three companies and five workers. Assume that the preference profile of companies C1, 02, C3 and workers $1, 82, 83, 84, 85 is follows and the capacities are 2, 1, respectively for c1, 022 C3-
The preference in Table (aa [(b) satisfies both SPC and â-condition with valid or-
der ((22, $2). (Cz, S3, 84), (c,, $5 J. While preference in Table [ (I(c) I(d) only sat- isfies á-condition with valid left order {(1,,81, 82), (c2, 83), (43,84, 85)] and right order
21

---

+) Necessity: We first prove for K = 2, N = ạ + Q2 case. Assume that there are two arms ç1 C2. each has capacity q (A= 2) and the agents set S 81, 82, 861 t- By contradiction, assume that Unge is satisfied while ã-condition is not. Then we know that not all matching pairs are Top-top Under review as a conference paper at ICLR 2023
(1,, s2), (cs, $4, 85)), and SPC does not hold.
(ii) Proof for the relationship between Unqe and é-condition
) Sufficiency: If ---condiiion holds, then the agent-proposing Gale-Shaple Gale-Shapley algorithm and the arm-prop arm-proposing Gale-Shapley algorithm leads to matching m in all consistent restrictions.
match, so there exists an agent 8k, C1 Fop C22 but Sy is not in the agents set that first qi preferred by
c1. The matched result may have two cases:
4 and (8k.
02)
(i)
91
42
(sky c1) and
02) (ii)
We first consider matching (it). If sy matches C1, then there must be an agent in A matches with Cg. Let's assume that there is agent Se E Ai that matches with cz. There are two situations to discuss at this time. If e >5 C22 then (ii) is an unstable matching, which recorded as case (A); If se prefers 02 more than c1, then (fi) is stable matching and is recorded event (B).
Apply the above two cases (A), (B) to matching (t). In (A), C1 and 8t prefer each other, so there is a Top-top match and then â-condition is satisfied, and conclusion contradictory to the hypothesis is derived. In (B), this case will produce two stable matchings, which contradicts Unqe.
We use induction to prove it. Suppose, that for all (Ñ, K), Ñ s N, s K, N 2 41 + 92 + qK the â-condition a necessary condition for the uniqueness consistency. Then we prove for (N + 1, + Q2 + ... + Qk) (similarly, we would have for (N, qı + Q2 +...... + 9K + 1) and Q1 + 92 + .......... + 9к 2 N ). Assume that the newly added agent X, select an agent from the original N agents and record it as Y. Let k2x and ky. be the arms rank first for X and Y respectively. By the K N Qi + F2 case proved above, we know that X and Y satisfy ã-condition, hence either X or Y matches with its first ranked arm. The agent matches with its first ranked arm is denoted by 81, and the remaining N agents are 82, ... 88. Except k; and stable matched agents for ky, : there are N agents and K 1 arms, and N 2 91 + Q2 + qK qk;, From the inductive hypothesis, can know that â-condition is satisfied.
The relationship between â-condition and Acyclicity" is illustrated in Section C.2.4
C.2.3 DIFFICULTIES FROM SPC TO İ-CONDITION IN REGRET ANALYSIS
When we use the events decomposition for regret minimization block to prove the bound inequality of the number of times agent j is pulled (Lemma 6. it requires that m m²(i) always exit and will not be deleted. Under SPC' condition, m (j) always exits as the stable matched partner is the most preferred one among the remaining market for the certain agent while â-condition cannot guarantee this property. Hence, it is important to find conditions or certain phase with good properties to guarantee that m (j) will not be globally deleted or locally deleted. And we consider Fa, and Va, in Lemma 3 (in Appendix B.2) to solve this problem. And since the stable matched pair is not top-top match in the remaining system under ã-condition while the answer is true under SPC, we introduce new mapping (Figure 4 to describe the corresponding relationships of stable pairs. In addition, as shown in Figure Acyclicity" is the weakest condition to ensure uniqueness up to now, and Bettina Klaus and Flip Klijn Klaus & Klijn (2013) point that acyclicity has tight connection with consistency. Hence, whether we can further weaken â-condition and propose a new algorithm remains to study.
22

---

Under review as a conference paper at ICLR 2023
C.2.4 Acyclicity" GUARANTEES A UNIQUE STABLE MATCHING
Definition 10. The preference profile of the arm side Pe has a cycle with length E if there exists
integer 2 2, C1, 21,02.'.. :.. ,e are l distinct arms and 81, 82," S8 are i distinct agents, subset T2,T,,... c((ss, st} and for any i E f1.2, ,l], the following two conditions are satisfied.
(P) (5(+1) >e {5t Se, where 8141 = $1, and
(2) [Z qe, - and Ti S Ue, (8i), where Uo, (si) = {s: sc st}.
Pf has no cycle, it satisfies Acyclicity'.
Akahoshi 2014) pointed that Acyclicity" is a necessary and sufficient condition for unique stable matching in many-to-one matching. They study the problem with responsive preference" and unacceptable agents and arms may exist on both sides of the market. Under our setting, both two sides are acceptable, and we will prove that Acyelicity" is also necessary and sufficient condition for uniqueness in our problem.
Theorem In our setting, our new ā-condition a sufficient condition to Acgelicity" (Theorem (iii)..
We first see the example above to explain hoe to check whether the Acyclicity" is satisfied. As mentioned above, the preference profile in Table I ((a))((T) satisfies both SPC and â-condition with valid order {(c2, $2), (Ca, $3, $1), (C1, $1, $s) J. We now check that also satisfies Acyclicity".
From preference profile ((a).
find four cycle:
81 F 82 02 02 81;
(ii) 82 02 83 og 82:
(iii) 83 e
cx $3:
(iv) 83 Pea 81 bo 82 oo 83:
Condition (P) in Definition 10 is satisfied, and we then illustrate that condition (Q) is not satisfied, [(31,,3), s2 |Til = 9c, 1 1. However, it violates Ti C Uc, (s1) = 0. Similarly, (ii), (iii), (iv) all imply that Acyclicity" is satisfied. For eycle (iv), Ti, T.,T,TT, C S1111, $2), [T = gz. 1 1 while T₃ c U2, (s1) Ó. Then, this example also satisfies Acyclicity".
thus Acyclicity" holds. For cycle (i), Ti, T2 C Si,(,,
In fact, we can see from the definitions of these two conditions that Acyclicity" only limits the preferences of the side, while â-condition limits the preferences of both sides of the market. Intuitively, Acyclicity" is more general condition. We now give the theoretical proof.
If â-condition holds, then Acyclicity" also holds. By contradiction, if Acyclicity" is violated, then there is a cycle (Definition 10). For preference sequences that can produce stable matchings, as long there cycle or a ring structure, we can always construct least two stable matchings Romero-Meding & Triossi 2013)). 3). For example. for fixed agents set S = {s1. $2, ,N) and arms set [C1, C2 ... CK with preference profile P and this matching market has stable matching m=. If there is a cycle >e 82 > 81, for this stable matching m. containing (81, e1), (82, 02). when other matching pairs remain unchanged, (#2, 01), (81, with other pairs can lead new stable matching. Thus the uniqueness is violated, and then â-condition is also violated.
Conversely, we consider a counterexample that Acyelicity" holds while a-condition may not hold.
From Table we now explain that market with arms C1 C22 C3, agents 81, 82, 83, 84, 85, and capacity q 1,2) with preference ((a)) and (bb) satisfies Acyclicity" and can lead to unique stable matching but does not satisfy a-condition. We run GS Algorithm in many-to-one market and obtain stable matching {(11; 82, st), (02; $1), (Ca) $3, s.)). And Acyclicity" is easily verified. After eliminating (C3; $3, 84), only 81, 82, 85, C1, C2 remain in the system, and then the preference profile is represented as (2(c)) and (2d)) in Table 2 Apparently, this preference can produce two stable matching. Thus, d-condition violated.
"The responsive preference here means that if only one student in the two matchings is different, the college prefers the matching containing the preferred student.
23

---

Under review as a conference paper at ICLR 2023
Table 2: Preference Profiles
(a) Exm3: Arms
(b) Exm3: Agents
C1 $1 > 82 > 85 > 83 > 84
81
22 > C3 > C1
0 82 81 83
85
82
C1 02 C3
C3 81 >
83
> 82 84 85
83
C3 > 01 > 02
a > 02 03
86
02 03
(c) Exm3: Arms
(d) Exm3: Agents
01 : 81 > 82 85
81
22 > C1
02 82 81 85
82 6 > 02
85 > 02
Theorem's 5. Suppose that (K. P) are arbitrarily fixed. Pe and Pe are the preference profiles of arms and agents respectively. Then, Pe satisfies Acyclicity' and only there is unique stable matching in many-to-one setting for each P.-
Proof. In order to prove this theorem, we first introduce a lemma.
Lemma 8. For a given P, suppose that there are two stable matchings under P: Ph p,, then Akahoshi 2014
[(s)|= = (s)) for each I and lu(c)] | for each e K.
Moreover, for each c with (c) + p(c).
qc:
m(d))/((c) # 9 and p (e))/v(()) + 0; (f) re p(e), then for each E (c(c) and E p(c))((c)) {8) xe {s}.
+) Necessity: We complete this proof by contradiction. Suppose there are at least two distinct stable matchings under P. From GS algorithm Gale Shapley (1962), there exists optimal matchings u² and μ², s.t. 4º Se 4² and p² > ja. Under the mnulti-stabllig assumption, f² * μ², Then, Eeg K, s.t. (c(c)) # (C(c)) and by the optimality of μ², (C())) > p² (co). Consider the following algorithm:
Step 1: Choose eq K, such that (()))) # (c2) and choose 82 J. such that Choose es E (K(cc {c2] = 1 (82). Go to step 2;
E n
Step & (k 2 2): Choose 8841 J, such that 8841 E μf (cx)) and cR+1 E [CMc s.t. {c++1} = =:::==0(sp (s8+1)) If (fck+1 E fci.02, ... ,cc, then the algorithm terminates. If not, go to the next step.
Result: the algorithm terminates at Step (E 2) with c++1 = cG 2 1), then result is:
Given the students (8j+1,8842, 88+1) and the college {ez, 1j+1, ,c), there is cycle: 8241 Foi .g.............................. og......8j42 Je 8j+1 de, 3j. then condition (P) is satisfied. Let Te = (cx))) (sxx,, E {j.]+ 1,... ...,,,), since each agent ultimately matches only one arm, (cy)) (f (c)+1),
(cx) are mutually disjoint, then T,, T Te are disjoint. And by the definition of Tr, k E {j.j 1, 1,... ,{). Tş does not contain any agent in {sj+1s 8542, .841). By the second property in Lemma Ta qs 1 and by the last property, Te C Un (8a).
Hence, there is cycle (Definition T0 which induces contradiction.
24

---

Under review as a conference paper at ICLR 2023
-) Sufficiency: Assume that there exists cycle 81+1 > St-... cz 82 c1 81, st+1 51
and [i = 9c. 1. To S Uc, (s;), then we construct preference profiles for both arms (Figure C.2.4
and agents (Figure C.2.4
Table 3: Preference Profile of IC.
note
C1
C2
Ct-1
C2
C++1
Ck
82
83
81
$6+2
8E+22
8242
88+2
SE+1+91
S8+1-
g:
96-1-91
se+1+g1
8E42+Q:
81-2-42
8842-qe-1
18:+2+9
SE+3+qu
8-+3-q4
$243-90-1
186+3+9
SN
SNN
SN
SN
The remaining of {st}
81
81
81
83
$2
$2
53
ranked
84
at last
8t
St
8t-1
St
Table 4: Preference Profile of J.
$2
S
SN
C1
C2
St-1
$1
C1
CC-2
C--1
*
c [KM
Then can find two distinct matchings μt and n² (Figure C.2.4 and Figure C.2.4). which induce contradiction.
Table 5: μ.
C--1
C1+1
CK
$2
$3
8t
81
Table 6: n¹a
C1
Ct-1
Ct
C++1
CK
8
Sp
St
25

---

Under review as a conference paper at ICLR 2023
D MORE DISCUSSIONS ABOUT OUR WORK
D.1 STABILITY IN MANY-TO-ONE SETTING
Stable matchings are always exist in one-to-one market Gale & Shapley (1962) while the answer is not necessarily correct under many-to onne-to-one setting Roth & Sotomayor (1992). Roth & Sotomayor (1992) points out that responsive preference (RP) that can refrain from this unexpectation. Our work assume that preference profiles are over individuals rather than agents sets, which naturally satisfies RP Sethuraman et al. 2006
D.2 SOME DETAILS ABOUT ALGORITHM
Multi-phases to Reduce Collisions In previous work, the CA-UCB algorithm Liu et al. (2020b) was proposed manage conflicts in the decentralized market combined with the bandit algorithm, but it has limitations for more general preference structures. In CA-UCB, we set the delay probability for all agents zero, then agents may fall into infinite loops and cause high regret. To avoid linear regret, the paper of SSanaarrraman et al. (2011) applies a phased UCB algorithm with arm elimination in the one-to-one setting. Our MO-UCB DD algorithm in many-to-on multi-phases for conflict management. The multi-phases is to guarantee that the active set in different phases has no inclusion relationship so that if an agent deletes an arm in phase, this arm can still be selected in the later phases. This ensures when the agent wrongly deletes an arm, it will not lead to linear regret.
matching is also carried out in
Parameter Selection and Scale The parameter 0 E (0, in our MO-UCB-D4 algorithm is chosen for the local deletion threshold. Increasing the threshold leads to higher regret until local deletion vanishes. This happens as more collisions are allowed until an arm deleted. But higher threshold allows for quick detection of the stable matched arms. However, decreasing the threshold results in a more aggressive deletion and then lower regret from collision each phase, at a cost of longer detection time for the stable matched arms. Therefore, there is trade-off when choosing 0 and we can design an algorithm iteratively update based on the previous information.
Baseline experimental design Although our work mainly focuses on theory and therefore we did not put much emphasis on the experimental evaluation, we still carefully design our experiments to test the robustness of our algorithm across different environments. Since our work is the first one to study the many-to-one setting with uniqueness conditions, there are indeed no comparable baselines. possible to design some sub-optimal algorithms in which each agent runs MAB algorithm independently and there is no communication block among agents. However, such algorithm may not find the stable matching and thus suffers a linear regret.
Optimality of our bound and the lower bound Recall that our bound is O(NK A=)) There
under the setting where arms have the same and known preferences Sankararaman et al. (2021), which is special case our setting. Our bound is optimal in terms of
exists a lower bound of O log(T)
A
T T'add A. For N. since each agent needs to face collisions from non-dominated arms and other agents, regret is bounded over the summation of agents and thus leads the term O(N). Usually in multi-player decentralized setting Avner & Mannor (2014); Rosenski et al. (016)). each agent will suffer regret of term N since will be collided with other agents. Thus we conjecture such N unavoidable. For K, since in the decentralized setting, agents have no knowledge of arm preference, each agent needs to try each (log(T)) /A?) times to identify the stable matched arm. And it may get collided when pulling the other agent's stable matched arm, thus leading the term K. K might be removed for those agents who may never get collisions due to the special market structure.
'This assumption Roth & Sotomayor (1992): Akahoshi 22014; Altinok (019 in our setting states that the addition of another agent P." will not influence the preference ranking for arm to agent ps and par, i.c. Per U ps May Per pe equivalent to pv >ay
26

---

Under review as a conference paper at ICLR 2023
D.3 STRICT PREFERENCE AND "INDIFFERENT AGENTS"
Our work focuses on strict preference rather than the more general case that considering indifferent agents, As far we know, lot of works studying the traditional (offline) matching markets would assume preferences to be striet Gale & Shapley (162); Karpoy (2019); Gutin et al. (2021); Nguyen ct (202T); ): |Akahoshi| (2014), perhaps due to the reason simplicity. Our work mainly follows these existing settings of the offline matching markets Gale & Shapley (162);; Karpov (2019); Gutin et al.
(202T); Nguyen et al. (2021) ) Akahoshi (2014) and the bandit learning on the one-to-one matching
markets Basu et al. (2021): Liu et al. (2020a); Sankararaman et al. (2021) Liu et al. (2020b) that
assume strict preferences.
Note that if the agents are indifferent (or nearly indifferent) over the arms that are far down the ranking lists and not affect the stable matching, our algorithm and analysis can actually go through. The gap appeared in the regret bound actually depends only on the those "(nearly) optimal" arms that appear in the stable matching or are the best among those not appeared in the stable matching.
Recall that our setting is to learn particular stable matching, like previous works Basu al. (2021 Liu et al. (2020a); Sankararaman et al. (2021); Liu et al. (2020b) learning the unique, or agent- pessimal/optimal stable matching the one-to-one setting. Under this objective, if the agents nearly indifferent, not exactly indifferent, over "(nearly) optimal" arms, no matter how small the gap is, the agents will need figure out the which arm is better and the gap appears as the learning hardness. This phenomenon is common in multi-armed bandits where differentiating the optimal arm and the second optimal arm the most difficult part of the learning. Then one might be curious about the objective to learn a "nearly stable matching". This would be more general and would prefer to leave it as interesting future work.
For the case when agents are exactly indifferent on "(nearly) optimal" arms, the stable matchings would not be unique. In this case, the communication block and the global deletion set of our algorithm need to be revised to allow each agent to keep more than one stable matched arm. Note that after this revision, the selected matching will not become fixed during interactions and will switch between all optimal stable matchings since the learning algorithm needs to continue exploring these arms to take precautions against the case of small gap. This will result in a phenomenon of fast-changing matching-se matching-selections. selections, compared with our setting and most previous works Basu et al. (202T); Liu et al. (2020a); Sankararaman et al. (202T) y Liu et al. (2020b) where the learning algorithm tends to stick a specific matching in the latter learning period.
D.4 FUTURE DIRECTIONS FOR MANY-TO-ONE SETTING
First, we propose some interesting directions about the setting. This paper considers preference over individuals rather than agent sets. For example, when the first and fourth employees have cooperation experience and the second and third employees have no cooperation experience before, the company may prefer to recruit 1-st and 4-th together rather than 1-st, 2-nd or 2-nd, 3-rd. That is, 1, 4 > 2, may occur for arm & and 1, 3, 4 [N] Further research can also take this combination effect as the starting point. We assume that the preferences over agents for arms are known in our setting") When multiple agents are accepted by one arm simultancously, the ranking of these agents cannot be judged if under the assumption of unknown preference ranking. Therefore, the algorithm for rank estimation still needs further design. And our work is based on fixed finite agents set and arms set, thus how to generalize this setting to a dynamic one?
TThe preference profile over arms for agents unknown in our setting, and needed be leameed
27


Reviews:
[{"review_id": "mZ0gWHHe9-5", "reviewer": "Reviewer_dQX3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies an allocation problem where multiple \"agents\" can be assigned to the same \"arm\" in each round. Each arm has some capacity, and the combined capacity of the $K$ arms is large enough to accommodate all $N$ agents. Both sides of the market (agents and arms) have preferences over each other. Agent preferences over arms are unknown a priori, but can be learnt though sequential interactions with arms. If the number of agents bidding for the same arm (say, arm $k$) exceeds the arm's capacity, only the top $q_k$ (capacity of arm $k$) agents preferred by the arm are assigned to it; rest remain unmatched during that round. For each matched pair, a stochastic $[0,1]$-valued reward is realized that the concerned agent can learn from. The authors provide conditions for a unique stable \"many-to-one\" matching, and propose a decentralized algorithm (each agent independently runs its own thread of said algorithm) that guarantees a regret of $\\mathcal{O}\\left( \\log T \\right)$ for each agent relative to its match in the unique stable matching; $T$ being the number of matching rounds.", "summary_of_the_review": "The overall quality of writing definitely warrants a minor revision. However, the biggest concern for me is the similarity with (https://dl.acm.org/doi/pdf/10.1145/3511808.3557248); the authors must appropriately address their contributions relative to this paper. Until that has been done, I will have my reservations about the merit/contribution of this submission. ", "strength_and_weaknesses": "While certainly a very interesting model to study, this paper seems very similar in style (including the model and even the title) to (https://dl.acm.org/doi/pdf/10.1145/3511808.3557248). In light of cited reference, the originality of this submission appears somewhat questionable. The only significance I see is the authors improving the $\\mathcal{O}\\left( \\log^2 T \\right)$ upper bound in the decentralized case (established in cited paper) to $\\mathcal{O}\\left( \\log T \\right)$; it is unclear whether the improvement is attributable to the new algorithm, communication block, or its analysis. While I do believe there is some technical merit to this submission, it would undoubtedly help the readers if the authors can compare their model, approach, and results with the cited reference. It would also help highlight their innovations and contributions (if any) vis-\\`a-vis the cited paper.\n\nI do understand the cited reference might not have been publicly available at the time of submission, however, I think it is imperative at this point that the authors address aforementioned concerns given the apparent non-trivial overlap between the two works.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "atFNcPZoZC", "reviewer": "Reviewer_mBKs", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\nThe paper investigates learning stable matchings in many-to-one matching markets where agents (“arms”) on one side can be matched to sets of agents on the other side. Building on an emerging line of work, the paper views the problem of learning stable matchings within the multi-armed bandits framework. The paper considers and analyzes a condition that guarantees uniqueness of stable matchings. Under this uniqueness condition, the paper designs a bandit algorithm that achieves O(log T / delta^2) \"stable regret\". The algorithm proceeds in phases, where each phase includes a regret minimization block and a communication block. The paper validates the performance of the algorithm through simulations. ", "summary_of_the_review": "The paper studies the timely problem of learning stable matchings in many-to-one matching markets. However, the preference assumptions are very strong and, as a result, the technical contribution is somewhat limited. ", "strength_and_weaknesses": "Strengths:\n- The problem of studying learning stable matchings in the many-to-one setting is well-motivated and timely, given that the emerging line on work learning stable matchings focuses on the one-to-one setting. \n- The paper leverages uniqueness of stable matchings to achieve O(log T) regret. \n\nWeaknesses:\n- The implicit assumption on the preferences of the arms—that arm preferences decompose into a preference ranking over individual agents—is very strong. Much of the interesting structure in many-to-many matching markets comes from arm preferences being over sets of agents. In particular, preferences might depend on the interactions between the agents within the set (e.g. the arms might prefer “balanced” sets of agents). The assumption made in this paper disallows these types of interactive structures. The model thus only applies to matching markets with capacity constraints, and does not apply to general many-to-one matching markets. \n- While the regret bound is shown to be have optimal dependence on T and Delta (see Section C.2), the paper does not show optimality of the dependence on N and K. \n- One weakness of the regret notion studied in this paper—stable regret—is that it is discontinuous in the utilities of agents: this makes it impossible to achieve instance-independent regret bounds. As a result, the paper only provides an instance-dependent regret bound and likely cannot achieve instance-independent regret bounds (similar to prior work on decentralized learning in one-to-one matching markets). It would be helpful to discuss this limitation of the model and regret definition. \n- Some references to related work are missing, e.g. Das and Kamenica (IJCAI 2005), Jagadeesan, Wei, Wang, Jordan, and Steinhardt (NeurIPS 2021), Cen and Shah (AISTATS 2022), Min, Wang, Xu, Wang, Jordan, Wang (NeurIPS 2022).  \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WPM07ckcet0", "reviewer": "Reviewer_xyU7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work focuses on the many-to-one matching problem in the bandits, and the uniqueness condition is fundamental in their problem setup. The author(s) designs the MO-UCB-D4 algorithm and derives an upper bound. The paper also presents experimental results to convince the efficacy of the proposed algorithm. ", "summary_of_the_review": "This work focuses on the many-to-one matching problem in the bandits with the uniqueness condition is fundamental in their problem setup. The author(s) designs the MO-UCB-D4 algorithm and derives an upper bound. The paper also presents experimental results to convince the efficacy of the proposed algorithm. \n\n==================\n\nThanks for the response. The gap between the upper and lower bounds is $NK$ as you explained, which indicates that the bounds are not sufficiently tight but I see your efforts. I would keep my score.", "strength_and_weaknesses": "Strength:\n1. The paper generally looks fine and easy to follow.    \n1. To explain the motivation of its formulation, this work describes a vivid scene with the companies and workers.\n\nWeaknesses:\n1. Is there a matching lower bound on the regret?\n2. Although the assumption of the unique stable matching ensures the consistency, the author(s) may also mention what will be the challenge in a setting without unique stable matching.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-Yx_LZGO-n", "reviewer": "Reviewer_XTzP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper extends the problem of bandit in matching markets from a 1-to-1 matching to many to one matching. Many to one matching are an important family with rich applications in domains like crowd-sourcing and pool ride-share. They extend the setting of optimal regret in the case of unique stable matching for the 1-to-1 matching to many-to-one. To achieve this extension, they need to identify a number of key components. First, they need to identify the analogue of alpha-condition in the many-to-one matching world. Next, they need to learn to deal with collisions. And finally, they need to put these pieces together to prove the optimal regret bound. They design an algorithm that is similar in template to the prior work on 1-to-1 matching where there is a notion of global deletion and local deletion and priove theoretical guarantees for this problem. They also corroborate this with empirical simulations.", "summary_of_the_review": "Overall, I believe that the pros outwieighs the cons. The considered paper is practical and the algorithm is a natural extension of UCBD4. Among the couple of follow-ups I suggested above, I would like to see the paper engage with the application bit more deeply. A section dedicated to a few applications and how the model in the current paper can be modelled for those applications will make the impact much more stronger. Additionally/aspirationally, I also wonder if the authors can find real-world datasets to run their algorithm on the above said applications which would definitely make this a stronger paper. From theory pov, I think this paper does a good job of straddling prior work contributions while also mentioning the novel aspects. Overall, I am leaning towards an accept.", "strength_and_weaknesses": "Strengths\n\n+ The studied setting is important and practical for a wide range of applications. Many-to-one matching markets are very common in internet age companies and bandit learning these markets presents an interesting challenge that this paper considers\n\n+ Overall the paper is well-written, places prior work in context and is careful in claiming contributions while also acknowledging which parts of prior work they build on. The algorithm is natural and they also address common questions one may have such as reducing this to 1-to-1 matching by making many copies.\n\n+ The results are optimal, and they consider a very general setting of unique stable matching.\n\nWeakness\n\n+ The primary weakness I find in the paper is not going deeper on applications. Right now, they only briefly mention an application that seems contrived. I would like the authors to consider multiple applications and expand on them, even in the appendix. As written, the paper may come across as contrived. But in my opinion, many-to-one matching has many stronger applications; I list a couple here.\n\n  - Pool riding in ride-share. This is an important application where we can match a driver to multiple riders. And the goal is to maximize the long-term platform utility.\n- Slate ranking in recommender systems. Here a user can be matched to multiple content at a single request. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject