Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning
Authors: Hadi Hosseini
Sanjukta Roy
Duohan Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Online learning
Multi-armed bandits
Stable matching
Matching markets.
Primary area: bandits

Abstract: Two-sided matching markets describe a large class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences. In many real-world applications (e.g. content matching or online labor markets), the knowledge about preferences may not be readily available and must be learned, i.e., one side of the market (aka agents) may not know their preferences over the other side (aka arms). Recent research on online settings has focused primarily on welfare optimization aspects (i.e. minimizing the overall regret) while paying little attention to the game-theoretic properties such as the stability of the final matching. In this paper, we exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions. We initiate the study of the sample complexity of finding a stable matching, and provide theoretical bounds on the number of samples needed to reach a stable matching with high probability. Finally, our empirical results demonstrate intriguing tradeoffs between stability and optimality of the proposed algorithms, further complementing our theoretical findings.

Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning
Hadi Hosseini Penn State University, USA hadi redi@psu.ede edu
Sanjukta Roy University of Leeds, UK s roy@leeds ac uk
Duohan Zhang Penn State University, USA dqz52350psu. edu
Abstract
Two-sided matching markets describe a large class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences. In many real-world applications (e.g. content matching or online labor markets), the knowledge about preferences may not be readily available and must be learned, i.e., one side of the market (aka agents) may not know their preferences over the other side (aka arms). Recent research on online settings has focused primarily on welfare optimization aspects (i.e. minimizing the overall regret) while paying little attention to the game-theoretic properties such the stability of the final matching. In this paper, we exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions. We initiate the study of the sample complexity of finding stable matching, and provide theoretical bounds on the number of samples needed to reach stable matching with high probability. Finally, our empirical results demonstrate intriguing tradcoff's between stability and optimality of the proposed algorithms, further complementing our theoretical findings.
Introduction
Two-sided markets provide framework for large class of problems that deal with matching two disjoint sets (colloquially agents and arms) according to their preferences. These markets have been extensively studied in the past decades and formed the foundation of matching theory-a prominent subfield of economics that deals with designing markets without money, They have had profound impact numerous practical applications such school choice [Abdulkadiroglu al. 2005a b). entry-level labor markets [Roth and Peranson, [999], and medical residency [Roth] 1984]. The primary objective is to find stable matching between the two sets such that no pair prefers each other to their matched partners.
The advent of digital marketplaces and online systems has given rise to novel applications of two- sided markets such as matching riders and drivers [Banerjee and Johari 2019], electric vehicle to charging stations [Gerding et al. 2013), and matching freelancers (or flexworkers) to job requester in a gig economy. In contrast to traditional markets that consider preferences to be readily available (e.g. by direct reporting or elicitation), in these new applications preferences may be uncertain or unavailable due to limited access or simply eliciting may not be feasible. Thus, a recent line of work has utilized bandit learning to learn preferences by modeling matching problems multi-arm bandit problems where the preferences of agents are unknown while the preferences of arms are known. The goal is to devise learning algorithms such that matching based the learned preferences minimize
the regret for each agent (see, for example, Liu et al. (020) 2021]. (Sankararaman et al.) [202]] Basu
al. 2021] Maheshwari al. 2022 Kong al. 2022 Zhang al. (022 Kong and Li 2023
Wang et al. 2022
"Conesponniig author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Unitorm agent-DA
Unitorm arm-DA
AE arm-DA
Prob. instability
((E(())))) 7) (Thm.
((ES(m))) (Thm.
(((ES(y)) exp Am
(Thm.
Sample complexity
Ō NK log(o ")) (Thm.
NK log(a 1)) (Thm..
Ō O [F5(m)) log(a () (Thm.
Table 1:
Comparison of bounds on probability of unstable matchings and the sample complexity to find a stable matching. ? = exp
A
SK
Despite tremendous success in improving the regret bound in this setting, the study of stability of the final matching has not received sufficient attention. The following stylized example illustrates how an optimal matching (with zero regret) across all agents may remain unstable.
Example 1. Consider three agents {ai, 02, 0a) and three arms {bi, b2, ba}- Let us assume true preferences are given as strict linear orderings as follows:
ill
01 : bi by bz
bj : 02
03 dj
02 bj
b1 by
b2 01
a3
02
03 bi b2 bg
b3 02
d3
The underlined matching is the only stable solution in this instance. The matching denoted by a regret minimizing matching: agents a₁ and ag have a negative regret (compared the stable matching), and 03 has zero regret. However, this matching is not stable because 03 and by form blocking pair. Thus, 03 would deviate from the matching.
Note that stability is desirable property that eliminates the incentives for agents to participate in secondary markets, and is the essential predictor of the long-term reliability of many real-world matching markets (Roth| 2002]. Though some work (e.g. Liu et al. [021]. Pokharel and Das (2023)
did stability analysis, it is insufficient as we discuss later in Section and Section
Our contributions. We propose bandit-learning algorithms that utilize structural properties of the Deferred Acceptance algorithm (DA)-a seminal algorithm proposed by Gaaee and Shapley [1962] that has played essential role in designing stable matching markets. Contrary previous works [Liu et al. 2020 Kong and Li 2023). we show that by exploiting an arm-proposing variant of the DA algorithm, the probability of finding stable matching improves compared to those used in many previous work (an agent-proposing variant, such as Liu et al. (220). [Bsu et al. [2021] Kong and Li (2023). ). We demonstrate that for a class of profiles (i.e. profiles satisfying a-condition or those with a masterlist), the arm- -on-pooooi DA is more likely to produce a stable matching compared to the agenn-proposing DA for any sampling method (Corollary [T] For the commonly studied uniform sampling strategy, we show the probability bounds for two variants of DA for general preference profiles (Theorem D We initiate the study of sample complexity in the Probably Approximately Correct (PAC) framework. We propose non-uniform sampling strategy which is based on arm- proposing DA and Action Elimination algorithm (AE) (Even- -ar al. (2066). and show that has a lower sample complexity as compared to uniform sampling (Theorem 3aand Theorem
5 Lastly, we
validate our theoretical findings using empirical simulations (Section
Table D shows the main theoretical results for uniform agent-DA -A algorithm, uniform arm-DA -A algo- rithm, and AE arm-DA algorithm. We note that the novel AE arm-DA algorithm achieves smaller sample complexity for finding stable matching. Our bounds depend on structure of the stable solution m, parameterized by the 'amount' of justified envy (m5mm)) (see Definition 4.
1.1 Related Works
The two-sided matching problem is one of the most prominent success story of the field of game theory, and particular, mechanism design, with a profound practical impact applications ranging from organ exchange and labor market to modern markets involving allocation of compute, server, or content. The framework was formalized by Gale and Shapley [1962] seminal work, where
'ee consider general case where preferences are given as cardinal values; note that cardinal preferences induce (possibly weak) ordinal linear orders.
2

---

they, along with long list of subsequent works focused primarily on theoretta aspects such as stability and incentives [Roth and Sotomayor 1992 Roth 1986 Dubins and Freedman, [98T].
While the DA algorithm is strategyproof for the proposing side [Gale and Shapley 1962]. J. no stable mechanism can guarantee that agents from both sides have incentives to report preferences truthfully
in dominant strategy Nash equilibrium (Roth 1982]. A series of works focused on strategic aspects
of stable matchings [Huang 2006 Teo et al. 2001 Vaish and Garg 2017 Hosseini et al. [021].
Stable matchings under uncertain linear or pairwise preferences were studied by Aziz et al. 2020
2022]. When preferences are unknown, the problem of learning preferences can be modeled as multi-agent multi-arm bandit problem. Recent work has shown a variety of learning approaches using Saplore-Then--e Comn-C (ETC), Thompson sampling [Kong et al., [202]] in centralized [Liu al.
2020: Pokkhare and Das 2023] or decentralized (Sankararaman et al., [022] Kong and Li] 2023
matching markets. Subsequent works focused on domains with restricted preferences (as we also study in this paper) wherein a unique stable matching exists under true preferences [Sankararaman jt al. [202T] Basu et al.] [022 Maheshwari et al. [022 Wang and Lij 2024 or those that generalize to many-to-on markets [Wang et al., [022 Kong and Li 2024 Li et al. 2024 An extensive related
work with details on upper bounds is provided in Appendix
2 Preliminary
1 denotes the Riemann Zeta function, and 2 ((B) > 1 Let [k] = (1.2..... .). and ((3) ((8)= E d² if 3 1 2.
Problem setup. An instance of a two-sided matching market is specified by set of N agents, N = {01, a2,...,,.y' a on one side, and a set of K arms, K. = {b), b2, bk J. on the other side. The preference of an agent a, denoted by > is strict total ordering over the arms. Each agent a; is additionally endowed with a utility Mi.j over arm by. Thus, we say an agent a; prefers arm by to 6g, i.c. by >a, by. if and only if μt.j > P..k 2 The preferences of arms are denoted by a strict total
We use je to indicate the utility profile
of all agents, where μ = ordering over the agents, i.c. an arm 6 has preference bb. The minimum preference gap is defined as min minj, [ [M4, pi,kel It captures the difficulty of learning problem in matching markets, i.e., the mechanism needs more samples to estimate the preference profile if A is small.
Stable matching, A matching is mapping m : -UK - NUKU {0} such that m(a:) E K. for all i E [N], and m(b;) . (0) for all j E [K], m(a:) = by if and only if m(6;) = ag- Additionally, m(b;) = @ if by is not matched. Sometimes we abuse the notation and use to denote i if agent is clear from context, and similarly use by to denote j if arm clear from context. Given a matching m. an agent-am pair (a;, by) is called a blocking pair if they prefer each other than their assigned partners, i.e., by >a, (n;))) and o; b, m(b,). Note that for any arm bj. getting matched is always better than being not matched, i.e., 0 >b, 0. A matching stable if there no blocking pair.
The Deferred Acceptance (DA) algorithm [Gale and Shapley 1962 finds a stable matching in two sided market follows: the participants from the proposing side make proposals to the other side according to their preferences. The other side tentatively accepts the most favorable proposals and rejects the rest. The process continues until everyone from the proposing side either holds an accepted proposal (i.e., matched to the one who has accepted its proposal), or has already proposed to everyone on its preference list (i.e., remains unmatched). We consider two variants of the DA algorithm, namely, agent-proposing and arm-proposing. The matching computed by the DA algorithm is optimal for the proposing side [Gale and Shapley 1962). i.e. proposing side receives their best match among all stable matchings. It simultancously pessimal for the receiving side Vitie and Wilson 197I). We denote the agent-optimal carm-pessimal) stable matching by in and the aegent-pessimal (arm-optimal) stable matching by m.
Rewards and preferences. Agents receive stochastic rewards by pulling arms. If an agent o; pulls an arm by. she gets a stochastic reward drawn from a 1 I-subgaussian distribution with mean
We assume preferences do not contain ties for simplicity as previous works [Luu et al. 2020 Kong and 2023 When preferences are ordinal and contain ties, stable solutions may not exist in their strong sense (sec, c.g. Irving 1994]. Manlove 22022).
AA random variable X is d-subgaussian if its tail probability satisfies P([X) > t) S 2 eexp 22z for all
t 0.
3

---

value At.j- We denote the sample average of agent over arm by as Pr.j. The agent-optings stable regrer is defined as the difference between the expected reward from the agent's most preferred stable match and the expected reward from the arm that the agent is matched to. Formally, we have R2 (m) = (a.) Hi,m)as) for agent 0; and matching m. Similarly, the arm-optimal stable regret as (m) = (a.) (a.))
Restriction on preferences has been heavily studied by previous papers (see Sankararaman et al. [2021]. Basu et al. [2021], Maheshwari et al. [2022]) as they capture natural structures where, for example, riders all rank drivers according to a common masterlist, but drivers may have different preferences according to, e.g., distance to riders. If the true preference profiles are known and there exists a unique stable matching, then the agent-proposing DA algorithm and the arm-proposing DA algorithm lead the same matching, namely 77 m. A natural property of the preference profile that leads to unique stable matching is called uniqueness consistency where not only there exists a unique stable matching, but also any subset of the preference profile that contains the stable partner of each agent/arm in the subset, there exists a unique stable matching. Karpoy 2019) provided necessary and sufficient condition (a-condition) to characterize preference profiles that satisfy uniqueness consistency. A preference profile satisfies the a-condition if and only if there stable matching m and an order of agents and arms such that Vi E [M] Vj > i, mm(aa) >e. by. and possibly different order of agents and arms such that Vj E [K], Vi > j, m(bb) bb, ag.
Preference profiles.
3 Unique Stable Matching: Agents vs. Arms
To warm up, we start by analyzing instances of a matching market where a unique stable solution exists. As we discussed in the preliminaries, these markets are common and can be characterized by property called uniqueness consistency. We show that for any sampling algorithm, the arm- -mn-prooi DA algorithm is more likely to generate stable matching compared to the agent- preen--poposing DA algorithm. All missing proofs and additional results are relegated to the full version Hosseini et al. 2024
Theorem 1. Assume that the true preferences satisfy uniqueness consistency condition. For any estimated utility S. if the agent-preposing DA algorithm produces a stable matching, then the arm-proposing DA algorithm produces a stable matching.
Theorem I states that when preferences satisfy the uniqueness consistency condition, for any estimated utility, the stability of agent-proposing DA matching implies the stability of arm-proposing DA matching. For any fixed sampling algorithm, each estimation occurs with some probability, so immediately have the following corollary.
Corollary 1. For any sampling algorithm, the arm-proposing DA algorithm has a higher probability of being stable than the agent-pronn egent-proppsing DA algorithm the true preferences satisfy uniqueness consistency condition.
The following example further shows that the arm- com-propsinng DA could generate a stable matching even if the estimation is incorrect, while the Section 6) we provide empirical evaluations on stability and regret of variants of the DA algorithm.
DA generates unstable matching. In
Example 2 (The stability of arm vs. agent proposing DA when estimation is wrong.). Con- sider two agents (a1,02) and two arms (bi,b)) Assume the true preferences are as follows:
a1 6
b
a
a2
02 b by
by
0
a1
The matching denoted by the only stable solution in this instance. Assume that after sampling data, agent a1 has wrong estimation: b2 > by and agent 02 has the correct estimation. Under the wrong estimation, arm-proposing DA algorithm returns the matching while agent-proposing DA algorithm returns the underlined matching, which is unstable with respect to true preferences. Note that algorithms that rely on agent-proposs proposing DA (e.g. Liu et al. (2027), Kong and Li (2023)) may similarly fail to find stable matching as they do not exploit the known arms preferences effectively.

---

Algorithm 1: Uniform sampling algorithm
Input: :arameter (3, sample budget T.
for -,,,...., for 1, 1,2...., do
Agent a; pulls (1) = bj. where j= ((+i- mod K + 1; Agent observes a return X1(1) and updates pi,j;
Compute UCB.,, and LCB,3 using B;
if 3 a permutaaiion for all E [M] such that (C > UCB Va [K then
Break:
return (ās.) i [M].E [K]}
4 Uniform Sampling DA Algorithms
In this section, we compare the stability performance for two types of DA combined with uniform sampling algorithm when the preferences could be arbitrary. Compared with Section 3 we note that the theory in this section does not constrain preferences. We provide probability bounds for finding an unstable matching in Section 4.1 and analyze sample complexity for reaching a stable matching in
Section 4.2
Uniform sampling is technique in bandit literature Garivier et al. 2016 (usually termed as exploration werooon-ttee-eoeee then-commit algorithm, ETC). and Li [2023] utilized UCB to construct confidence interval (CI) for each agent-arm pair, where each agent samples arms uniformly. The exploration phase stops when every agent's CIs for each pair of arms have no overlap. i.c. agents are confident that arms are ordered by the estimation correctly. Then, in the commit phase agents form a matching through agent-proposiee
DA, and keep pulling the same arms.
Agents construct CIs based the collected data by utilizing the upper confidence bound (UCB) and lower confidence bound (LCB). Given a parameter 3, if arm b, is sampled t times by agent a, we define the UCB and LCB as follows:
UCB (t) + (23 LCB., = (t) log Ktt)tt,
(I)
where (t) the average of the collected samples.
Uniform sampling algorithm (Algorithm I Agents explore the arms uniformly. Suppose that agent ag has disjoint confidence intervals over all arms, i.c.. there exists permutation o, := (2), (2)...... (K)) over arms such that LC' (C'B,,,,(k) > UC (CC for each k [K 1]. Then, agent a; can reasonably infer the accuracy of the estimated preference profile. The parameter is used to control the confidence length, where larger / implies that the agent needs more samples differentiate the utility for pair of arms.
After the sampling stage, agents can consider to form a matching either through agent-pros prent-proposing DA or arm-proposing DA, is discussed in Section 3 For simplicity, we refer uniform sampling Algorithm I with agent-proposing DA as uniform agent-DA algorithm, and uniform sampling with arm-proposing DA as uniform arm-DA algorithm.
4.1 Probability Bounds for Stability
We provide theoretical analysis on probability bounds for stability for the uniform agent-DA algorithm and the uniform arm-DA algorithm. We show probability bounds of learning stable matching using the properties of stable solutions and the structure the profile. first define the following notions of local and global emvy-sets.
Definition 4.1. The local envy-set for agent aj for a matching m is defined as
if (b; : at >b, m(b;)} is emply otherwise.
(. (b, a, >b, m(b;)) ((m(a))
The global envy-set of matching m is defined as the union of local envy-sets over all agents:
F.S(m)= = U ((a by): : by (m)))
[E|N]
5

---

By the defimition of stability, a matching m is stable if and only if the global envy-set is justified, ie., agents truly prefer their current matched arm the arms in the envy-set ES(m). Formally, Ni,m(a.) 2 Mi.j: for all (a.,b) b2) E (.)(m) if and only if m is stable matching. This observation is key in establishing theoretical results.
The following lemma provides condition for finding a stable matching using the envy-set of the estimated matching. The detailed proof of all the results can be found in the full version Hosseini
et al. [2224].
Lemma Assume ja is the sample average, and matching in is stable with respect to p. Define 'good' event for agent ag and arm by as Fi,j = {lui, - رريl I A/2), and define the intersection of the good events over envy-set as F(ES(m) = Es( Fs.j. Then if the event ((E)(())) occurs, matching m is guaranteed to be stable (with respect to jo).
Now prove the following bounds for two types of uniform sampling algorithms. The probability bound depends on the size of the envy-set.
Theorem 2. By uniform sampling (Algorithm 1. each agent samples each arm T/K times, and my and f2 are matchings generated by agget-proposing DA and arm-proposing DA, respectively. Then,
(i) P(m1 is unstable) ((
A-T )),
8K
(ii) P(mz is unstable) O((ES(m)) exp(
A )),
where m is the agent-pessimal stable matching and mा is the agent-optimal stable matching.
Proof sketch. Since m. and m2 are produced by DA based on j., both matchings are stable with respect jr. By Lemma [ both matchings are guaranteed to be stable with respect μ conditioned on F(E)((11)) (or F (M)))))) Thus, it follows
P(m is unstable) S 1 - P(F(ES(m))))
Bl P(IULs - Ar. 2 A/2]]
[definition of FF
E
Σ
P(IEEs - -i.i 2 A/2)]
[union bound]
A&T
S 2B[ exp(
Iv T su subgaussian with 0 mean].
8K
To complete the proof for m1, we demonstrate an upper bound of E| (M)) We show that [E[ESS(m]]] )]] [TE)l I 2 exp(p AT,) ). The difference is negligible when is sufficiently
large. Thus the first statement follows. The complete proof is deferred to Appendix C
In the next lemma, we show the relation between the size of the envy-sets for the agent-optimal and aggettppessing matchings. Then, combining Theorem 2 and Lemma 2 we prove the next corollary.
Lemma 2. Given any instance of matching problem, we have the following relationship between the size of the two envy sets: [m)(m)) < [m)m
Proof. Agent-pessinet stable matching is the arm-optimal stable matching, and agent-optimal stable matching m is the arm-pessimal stable matching, so we have that m (by) >b, m(b,) or m(b))) m(b;) for each arm by. From the definition of the envy-set, we have (ES(m) < (ES(T)).
Corollary 2. The uniform arm-DA algorithm has a smaller probability bound of being unstable than the uniform agent-DA algorithm.
Liu et al. (2020) showed the probability bound of exp( A-T for finding an invalid ranking by the ETC algorüthm, where a valid ranking is defined as the estimated ranking such that the estimated pairwise comparison is correct for a subset of agent-arm pairs. However, their result did
Remark 1.
not relate the probability bound with the structure of the instance, whereas the bound in Theorem 2 crucially uses the envy set improve the probability of finding a stable solution. Liu et al. (2027] provided an upper bound on the sum of the probabilities of being unstable for the Conflict-Avoiding Avoiding UCB algorithm (CA-UCB). Under CA-UCB algorithm, Ollog (T)) out Tf matchings are unstable in expectation.

---

Algorithm 2: Arm elimination algorithm
Input:
Imput:agent aagett arms b1, b2, sample sizes mı, m2, and sample mean üs P2.
Calculate LCB1, LCB22, UCB,, UCB2;
winmer + empty;
while max(LCB,, LCBb) < Min(UCC,, do
inder <- wwhich.min(11.. 112);
Agent a pulls bindex:
Agent o observes a return and updates Pinden Dindezi
Update all UCB and LCB;
winner index of maximum (f1, p2):
return winner.
4.2 Sample Complexity
We turn to analyze the sample complexity learn stable matching under the probably approximately correct (PAC) framework. In particular we ask: given a probability budget a, how many samples T' are needed find stable matching? Formally, an algorithm has sample complexity T with probability budget a if with probability at least 1 a. the algorithm guarantees that it would find stable matching with the total number of samples over all agent-arm arm pairs upper bounded by T.
Theorem 3. [Sample complexity for uniform sampling algorithm] With probability least both the uniform agent- DA and the uniform arm-DA algorithms find a stable matching with the same sample complexity ( NK
log(a-))
Note that uniform agent-DA DA algorithm finds the stable matching m, and uniform arm-DA algorithm finds the stable matching m. Uniform sampling (Algorithm [ suffers from sub-optimal sample complexity for finding stable matchings since agents sample each arm uniformly. Thus, in the next section we devise an exploration algorithm that exploits the structure of stable matchings by utilizing arms' known preferences.
5 An Arm Elimination DA Algorithm
The proposed algorithm (Algorithm 3 combines the arm- pron-pooopsingggg DA and Action Elimination (AE) algorithm [Audibert and Bubeck 2010 Even-Dar al. 2006 Jamieson and Nowak 2014). The AE algorithm eliminates an arm (i.e. no longer sampling the arm) when confidence bound indicates that the arm is sub-optimal (i.c. the upper confidence bound is smaller than another arm't 'ss that hasn't 't been climinated. Note that Algorithm 3 differs from the vanilla arm- proppsssi DA in Line 8, when an agent has been proposed by arms. Agents utilize the arm elimination algorithm (see Algorithm 2) until the agent eliminates the sub-optimal arm. Note that at every round, each agent chooses an arm with fewer samples thus far (see Line 4 in Algorithm 2 One significant observation is that if Algorithm 2 outputs winners correctly whenever an agent is proposed, Algorithm terminates with the arm-optimal matching m.
lower confidence bound), and outputs the best arm when there is only
5.1 Probability Bounds for Stability
We compute the probability bound for learning an unstable matching for Algorithm Contrary to uniform sampling, here compute the bound on given sample size.
Theorem 4. By Algorithm 3 assume that agent samples arm b; for Ti,j and vi is returned by the algorithm. We define Tmin min EE Th, as the minimum sample size for agent-arm pairs. Then, we have
A 2
P(m unstable) < ((ES(mm) exp(
Remark 2. Theorem provides stability bound for Algorithm 3 that depends on Tú,5, which is NT
unknown apriori. If the total sample budget is NT and we set Tij [m]
the stability bound
'Ô denotes the upper bound that omits terms logarithmic in the input.
7

---

Algorithm 3: AE arm-DA algorithm
Input: :arms' preference lists, sample budget T.
m empty matching;
while unmatched arm who has not propused to every agent and sample number S do
a 4- highest-ranked agent to whom b has not yet proposed;
if is unmatched then Add (a, b) S:
+- arm currenlyy matched to a: finds the preferred arm from (b, 3/) using elimination, Algorithm 2 if prefers b to 6' then
Replace (a, 6') in with (a, b);
11
Mark as unmatched;
12 Arbitrarily match remaining agents and arms if m is incomplete;
13 return
becomes O(ESS()) exp(
NT FS(m)) mm)
)), which is smaller than uniform arm-DA's stability bound
OQES(() (m) eepp( (eeeppppppppp SK
), as stated in Theorem 2 Even though the upper bound could be larger
than that of Algorithm
7 simulated experiments show that AE arm- mnnDAA significantly improves stability guarantees compared to the uniform sampling variants [Algorithm!] 77.
5.2 Sample Complexity
We compute the sample complexity learn stable matching for Algorithm 3 Note that agents only sample pairs in the envy-set, while in Algorithm [ Jagents explore all arms uniformly. The following analysis shows that Algorithm 3 has smaller sample complexity compared to Algorithm [I]
Theorem S. /Sample complexity for AE arm-DA algorithm] With probability least a, Algo- rithm 3 terminates and returns stable matching, m. with sample complexity of
Ō (m(m)
log(a-11)
Proof sketch. We begin by defining a good event (t) -4. S 2B (og(Kt)/K only for agent- arm pairs in the envy-set [ES(m). Conditioned such events for all time, we demonstrate that the algorithm terminates with true preferences on the envy-set (mmm), ) and thus, the algorithm executes the arm-propa com-propsingg DA when agents have known preferences and produces
Then we show the upper bound of sample complexity for each agent-arm pair: T 0 log( 8K x² )).
We prove it by induction on the number of proposals. The base case when arms by and by propose to agent a, for the first time. Then, we show the number of samples for each pair is bounded by T. In the inductive step, say by is the winner in the last round and has sampled t,,; S times, and by proposes to in this round. Then if a; samples b, for T - 4.jj more times and a, samples by for T times, by the same computation as the base case, we have that the number of samples for each pair is bounded by T. Since Algorithm 3 only samples the agent-ama pairs in the envy set ES(m). get that the total sample complexity is [ES(m) O ((())())) log( (KK )). By setting the probability A
budget (ES(() have that with probability least a, the AE arm-DA algorithm has
sample complexity Ō [ES(m)) log(a-1) The complete proof appears in Appendix D
is worth noting that a large 3 implies a small a, which implies that the algorithm needs more samples guarantee finding a stable matching. We show bounds the envy-sets in the next lemma.
Lemma 3. Considering any preference μ. have the following bounds for envy-set
(i) Size of the envy-sel for m. (mox) N, K} - N)N < [E(mm < NK.
(ii) Size of the envy-set for me (mox N, K) - N)N < [m)mm S NK 1.

---

resman CHUC)
Average Stablity
Average Regrets
Regrets
12
Samples
Samples
Samples
Figure 95% confidence interval of stability and regret for 200 randomized general preference profiles.
Remark 3. By comparing Theorem 5 to Theorem 3 the sample complexity ratio between the AE
arm-DA (Algorithm 3) and uniform arm selection (Algorithm 1) is [ES(m]] which further shows that fewer arms from the envy-set (m) need to be sampled. Lemma states the best-case and worse-case ratios as Man(N.K3-N and N-1 NK
< 1. Thus, Algorithm strictly improves the sample
K
complexity of finding a stable matching.
Remark 4. One can illustrate the magnitude of [ES(m) through the lens of arm-proposing DA algorithm. Observe that [mS( is the number of proposals made by arms and rejections made by agents in the arm-proposing DA algorithm. In highly competitive environment for arms, e.g. when there are much more arms than agents so that many arms are not matched, the magnitude of (E)(m)) is large. In less competitive environment, e.g. when arms put different agents their top choices, [S(m)) has much smaller magnitude.
Experimental Results
In this section, experimentally validate our theoretical results. For this, we consider N K 20 and randomly generate preferences. In particular, we follow a similar experiment setting in Liu al. [2021]: for each i, the true utilities {pr,1, (r,2.. . Me,20) are randomized permutations of the sequence .1. so that the minimum preference gap is fixed (A 1) and algorithm performance exhibits relatively low variability, Arms' preferences are generated the same way. We conduct 200 independent simulations, with each simulation featuring randomized true preference profile. We compare average stability, i.e., the proportion of stable matchings over 200 experiments, average regrets, and maximum regrets over agents between four algorithms: uniform agent-DAf) uniform arm-DA DA, AE arm-DA, and CA-UCB Liu et al. 2021].
In terms of stability, our experiments show that the AE arm-DA algorithm significantly enhances the likelihood of achieving stability compared both types of uniform sampling algorithm and CA-UCB algorithm (Figure D]. On the other hand, the regret gap between uniform agent-DA and other two ponppprposing types of algorithms illustrates the utility difference of agent-optimal matching m and arm-optimal matching m. We note that when preferences are restricted to have unique stable matching, AE arm-DA algorithm's 's regret converges faster compared to uniform algorithms, while still keeping faster stability convergence (Figure 2). Additional experiments with other preference domains (e.g. masterlist) provided in Appendix
At the first glance, Figure (the center and the right plots) seems to suggest that the the uniform arm-DA is outperforming the AE arm-DA algorithm. However, note that the regret here with respect to the agent-optimal solution (i.c. R); and thus, the AE arm-Da DD algorithm by design is not optimized to reach that solution. Upon further investigation, however, we see that when comparing the algorithms using the ppent-pssimmal regret ( then the AE arm-DA converges with fewer samples both in terms of average and maximum regrets, as illustrated in Figure
7 Conclusion and Future Work
The game-theoretical properties such stability two-sided matching problems are critical indicators of success and sustenance of matching markets; without stability agents may 'scramble' to participate
'The uniform agent-DA Deent-DA algorithm is ETGS algorithm in Kong and Li 2023 with minor differences.

---

Average Stablity
Average Regrets
Regrets
relmmaa- CHUCZ
Samples
Samples
Samples
Figure 95% confidence interval of stability and regrets for 200 randomized SPC preference profiles. Please see the definition of SPC in Appendix E matching.
An SPC preference profile has a unique stable
unitim am AE
Average Regrets
Pi Am.
AS am-c
Samples
Samples
Figure 3: 95% confidence interval of agent-pessimal stable regrets for 200 randomized general preference profiles.
in secondary markets even when all preferences are known [Kojmma et al. 2013]. We demonstrated key techniques in learning preferences that rely the structure of stable solutions. In particular, exploiting the 'known' preferences of arms in the arm-proposing variant of DA and eliminating arms early on, provably reduces the sample complexity of finding stable matchings while experimentally having little impact on optimality (measured by regret). Findings of this paper can have substantial impact in designing new labor markets, school admissions, or healthcare where decisions must be made preferences are revealed Rastegarii et al. 2014
We conclude by discussing settings with incomplete preferences, ties, or those that go beyond subgaussian utility assumptions are interesting directions for future research. We opted to avoid these nuances, for example ties, such variations often introduce computational complexity with known preferences. In addition, given that the number of stable solutions could raise exponentially (Knuth] 1976), designing learning algorithms that could converge to stable solutions while satisfying some fairness notions (e.g. egalitarian or regret-minimizing) is an intriguing future direction.
limitations and open questions. First, extending this framework to
Acknowledgments and Disclosure of Funding
Hadi Hosseini acknowledges support from National Science Foundation (NSF) IIS grants #2144413 and #2107173. We thank Shraddha Pathak for her feedback. We also thank the anonymous reviewers for their comments and constructive criticisms.
References
Atila Abdulkadiroglu, Parag Pathak, and Alvin Roth. The New York City High School Match. American Economic Review, 95(2):364-367, 2005a.
Atila Abdulkadiroğlu, Parag A Pathak, Alvin E Roth, and Tayfun Sönmez. The Boston Public School Match. American Economic Review, 95(2):368-37,, 2005b.
Jean- Audibert and Sébastien Bubeck. Best arm identification multi-armed bandits. In COLT-23th Conference on learning theory-2010, pages 13-p, 2010.
10

---

Haris Aziz, Péter Biró, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari. Stable matching with uncertain linear preferences. Algorithmica, 82:1410-1433, 2020.
Haris Aziz, Péter Biró, Tamás Fleiner, Serge Gaspers, Ronald De Haan, Nicholas Mattei, and Baharak Rastegari. Stable matching with uncertain pairwise preferences. Theoretical Computer Science, 109: 2022.
Siddhartha Banerjee and Ramesh Johari. Ride Sharing. In Sharing Economy, pages 73-97. Springer, 2019.
Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log" regret for decentralized bandits in matching markets. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 705-715. PMLR, 18-24 Jul 2021.
Sanmay Das and Emir Kamenica. Two-sided bandits and the dating market. In IJCAI, volume 5, page 19. Citeseer, 2005.
Lester E Dubins and David A Freedman. Machiavelli and the gale-shapley algorithm. The American Mathematical Monthly, 88(7):85-499, 1981.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9 15, 1962.
Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-commit strategies. Ad- vances Neural Information Processing Systems, 29, 2016
Enrico H. Gerding, Sebastian Stein, Valentin Robu, Dengji Zhao, and Nicholas R. Jennings. Two-sided online markets for electric vehicle charging. In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS 133 page 189-996. International Foundation for Autonomous Agents and Multiagent Systems, 2013. ISBN 978 9781450319935.
Hadi Hosseini, Fatima Umar, and Rohit Vaish. Accomplice manipulation of the deferred acceptance algorithm. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 231-237, 2021. doi: 10.24996//iccai22221/3.. URL Main Track.
https://doi. org/10. 10. 24963 /i//://jjai... 2021/33
Hadi Hosseini, Sanjukta Roy, and Duohan Zhang. Putting gale shapley to work: Guaranteeing stability through learning. arXiv preprint 1rXiv:2410.04376 2024.
Chien-Chung Huang. Cheating by men in the gale-shapley stable matching algorithm. In European Symposium on Algorithms, pages 418-431. Springer, 2006.
Robert W Irving. Stable marriage and indifference. Discrete Applied Mathematics, 48(3):261-272. 1994.
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-23 -3335, 2021.
Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE, 2014.
Alexander Karpov. A necessary and sufficient condition for uniqueness consistency the stable marriage matching problem. Economics Letters, 178:63-65. 2019.
Donald Ervin Knuth. Mariages stables leurs relations avec d' d'autres problèmes combinatoires: introduction l a'aaalyse mathématique des algorithmes. (No Title), 1976.

---

Fuhito Kojima, Parag A Pathak, and Alvin E Roth. Matching with couples: Stability and incentives in large markets. The Quarterly Journal of Economics, 128(4):1585-163) 2013.
Fang Kong and Shuai Li. Player-optimal stable regret for bandit learning in matching markets. In Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 1512-1522. SIAM, 2023.
Fang Kong and Shuai Li. Improved bandits in many-to-one matching markets with incentive compatibility. Proceedings of the AAAI Conference on Artificial Intelligence, 38(12) Mar. 2024, doi: 10. 1609/aaai wit.aai.33812...9222.. URL https: aaai. org/index. index.ndexx.. php/ AAAI/
article/view 292226
Fang Kong. Junming Yin, and Shuai Li. Thompson sampling for bandit learning in matching markets. In Lud De Raedt, editor, Proceedings of the Thirty-FFrsst International Joint Conference on Artificial Intelligence, IJCAI-22, pages 3164-3170. International Joint Conferences on Artificial Intelligence Organization, 7 2022. doi: 10.24963/ijcai.2022433 2022/439 Main Track.
htw.btttts://doooor////// 2496/ jcai
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Yuantong Li, Guang Cheng, and Xiaowu Dai. Two-sided competing matching recommendation markets with quota and complementary preferences constraints. In Forty-first International Conference on Machine Learning, 2024.
Lydia T. Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1618-1628. PMLR, 26-28 Aug 2020.
Lydia T Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. The Journal of Machine Learning Research, 22(1):9112-9645, 2021.
Chinmay Maheshwari, Shankar Sastry, and Eric Mazumdar. Decentralized, communication- and coordination-free learning in structured matching markets. In Advances in Neural Information Processing Systems, volume 35, pages 15081-15092. Curran Associates, Inc., 2022.
David F Manlove, The structure of stable marriage with indifference. Discrete Applied Mathematics, 122(1-3):167-81,, 2002.
David G Vitie and Leslie B Wilson. The stable marriage problem. Communications of the ACM, 14(7):486-99,, 1971.
Yifei Min, Tianhao Wang, Ruitu Xu, Zhaoran Wang, Michael Jordan, and Zhuoran Yang. Learn to match with regret: Reinforcement learning in markov matching markets. Advances in Neural Information Processing Systems, 35: 35:19956-1999 19970, 2022.
Gaurab Pokharel and Sanmay Das. Converging to stability in two-sided bandits: The case of unknown preferences on both sides matching market. arXiv preprint 27X1v:2302.06116. 2023.
Baharak Rastegari, Anne Condon, Nicole Immorlica, Robert Irving, and Kevin Leyton-Brown. Reasoning about optimal stable matchings under partial information. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 431-448, 2014.
Brown.
Alvin E Roth. The economics of matching: Stability and incentives. research, 7(4):617-625 1982.
Mathematics of operations
Alvin E Roth. The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory. Journal of Political Economy, 92(6):911-0166 1984.
Alvin E Roth. On the allocation of residents to rural hospitals: a general property of two-sided matching markets. Econometrica: Journal of the Econometric Society, pages 425-427, 1986.
Alvin Roth. The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica, 1044):134,-1378, 2002.
12

---

Alvin E Roth and Elliott Peranson. The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design. American Economic Review, 89(4):748-780 1999.
Alvin E Roth and Marilda Sotomayor. Two-sided matching. Handbook of game theory with economic applications, 1:485-544 541,,,,,1111 1992.
Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate or delete: Decentralized competing bandits in serial dictatorship. In Proceedings The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1252-1260. PMLR, 13-15 Apr 2021.
Chung-Piaw Teo, Jay Sethuraman, and Wee-Peng Tan. Gale-shapley stable marriage problem revisited: Strategic issues and applications. Management Science, 47(9):1252-1267, 2001.
Rohit Vaish and Dinesh Garg. Manipulating gale-shapley algorithm: Preserving stability and remaining inconspicuous. In IJCAI, pages 437-443, 2017.
Zilong Wang and Shuai Li. Optimal analysis for bandit learning in matching markets with serial dictatorship. Theoretical Computer Science, page 14703, 2024.
Zilong Wang, Liya Guo, Junming Yin, and Shuai Li. Bandit learning in many-to-one matching markets. In Proceedings of the s1 ACM International Conference on Information & Knowledge Management, pages 2088-2097, 2022.
YiRui Zhang and Zhixuan Fang. Decentralized two-sided bandit learning in matching market. The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
YiRui Zhang, Siwei Wang, and Zhixuan Fang. Matching in multi-arm bandit with collision. In Ad-
vances in Neural Information Processing Systems, volume 35, pages 9552-9563, Curran Associates,
Inc., 2022.
13

---

Appendix
A
Related work (Extended)
Stable matching markets. The two-sided matching market problem has been used to analyze many markets, such the residency assignment problem [Gale and Shapley 1962 Roth and Sotomayor 1992]. The deferred-accepe -ecerred-acceptancee (DA) algorithm an elegant procedure that guarantees a stable solution and can be computed in polynomial time [Gale and Shapley 1962]. The DA algorithm is strategy proof for proposers Roth [1982), i.e., no single proposer can be matched to a better partner by misrepresenting the preference. However, proposers can form coalition misrepresent their preferences and some proposers are better off [Huang| [2006), Dubins and Freedman [198]. Research on stable matching with uncertain preferences [Aziz et al., 2020 2020]2022] investigated find stable matching with the highest probability when both sides are unsure about their preferences.
[220 formalized the centralized and decentral- ized bandit learning problem in matching markets. In this problem, one side of participants (agents) have unknown preferences over the other side (arms), while arms have known preferences over agents. They introduced a centralized uniform sampling algorithm that achieves O log(T) agent- optimal stable regret for each agent, considering the time horizon T and the minimum preference gap A. For decentralized matching markets, Sankararaman et al. [022] showed that there exists an instance such that the regret for agent a; is lower bounded as Q max (3-1] log((T)
Bandit learning in matching markets. Liu
Klogl() }). Some
A2
research (Sankararaman al. 2021 Basu et al., 2021 Maheshwari al., 2022 focused on special
preference profiles where a unique stable matching exists. Recently, Kong and Li [2023). [Zhang et al.
[222]] both unveiled decentralized algorithms to achieve near-optimal regret bound O (X )
embodying the exploration-exploitaiie trade-off central to reinforcement learning and multi-armed bandit problems.
Other works focused on different variants of the bandit matching market problem. Das and Kamenica (2055) Zhang and Fang [2024) studied the bandit problem in matching markets, where both sides
of participants have unknown preferences. WWan et al. 2022] Kong and Li (2024) generalized the
one-to-one setting to many-to-one matching markets under the bandit framework. Kong and Li| [004]]
proposed an ODA algorithm that utilized a similar idea of arm- arm-proposing DA variant compared
to the AE arm-DA algorithm in this paper, however, the ODA algorithm achieved O NK
(T))
regret bound in the one-to-one setting, which is ONN) worse than the sfateoffthhe-at art algorithms in one-to-one matching (e.g. Kong and Li [2023 Zhang et al. (2022) ). The performance of the ODA algorithm hindered by unnecessary agent pulls. [Jagadeesan et 2021] studied stability of bandit
problem in matching markets with monetary transfer. [Min et al. 2022 studied Markov matching
markets by considering unknown transition functions.
B Omitted proofs from Section 3
Theorem 1. Assume that the true preferences satisfy uniqueness consistency condition. For any estimated utility P. if the agent-proposing DA algorithm produces a stable matching, then the arm-proposing DA algorithm produces a stable matching.
Proof. We denote the matching generated based on the estimated utility ja by the agent-proposiin DA and arm- proposiop DA M2 and m2, respectively. By the definition of uniqueness consistency there is only one stable matching, denote by m." Since my is assumed to be stable, my = m,, we show that the arm- cnn-propoinng DA algorithm also returns the same matching, i.c., m2 m
By using the Rural-Hospinn theorem Rothh 1986 on the estimated preferences ju, we have that the same subset of agents and arms are matched in both my and m2, so we can reduce the case to N = K by only considering the subset of matched agents and arms.
Since the true preferences satisfy uniqueness consistency, then it must satisfy the a-condition. Using the definition of a-condition, have ordering of agents and arms such that
aj >b. aj. Vj i,
(2)
where a; (b.).
14

---

Suppose for contradiction that my # m²" Then there must exist some k > 1, such that m ag- However, since both m and my are stable with respect to fi and my is arm optimal, the partner of arm by in m2 is at least as good as its partner in mi. Thus,
Gk (bi >b, mi (bi) =
which is a contradiction to equation utility).
Thus, we prove that m2 is also stable (with respect to true
C Omitted proofs from Section 4
The following lemmas are useful to prove the stability bounds.
Lemma 4 (Property of independent subgaussian, Lemma 5.4 in Lattimore and Szepesvári (2020)).
Suppose that X is d-subgaussian and X1 and X2 are independent and di and d2 subgaussion, respectively, then we have the following property:
(I) Var[X] d².
(2) cX is leld-subgaussian for all e E IR.
(3) X1 + X2 is v + dE-subgaussian.
By the property of independent subgaussian random variables, we have the following lemma that bounds the probability of ranking two arms wrongly.
Lemma 5. Sample hi data (X1, . X i..dd from I-subgaussian with mean μt, and hz data (Y1, Y2,.Y..... .2..... Ybg} i...d. from I-subgaussian with mean p2, where μr < p2. Two datasets are independent. Define üi and üo2 the sample mean for two datasets. Then have
(12 m1)² ( + L
P(ñz im) S expp
Proof. By Lemma 4 P22 iin is v hi + hi
-subgaussian with mean μ22 f1. Thus by the definition
of subgaussian
(N2 11)²
P(ña (n) P((02 --n) (122 m1) -(12 m)) S exp(
2( I 1
h1 To2
and the proof is complete.
Lemma 1. Assume ja is the sample average, and matching m is stable with respect to p.. Define
"good' event for agent ag and arm by as Fi, = {1ucs - Purl S A/2], and define the intersection Then if the event F(FS((m))
of the good events over envy-set as F F(F.((m) = (E))))))) occurs, matching in is guaranteed be stable (with respect to pt).
Proof. We show that no agent- arm pair forms a blocking pair m. We prove it by contradiction.
Assume that there exists an agent a; and an arm by in the local envy-set ES; (m that blocks m which means ((,,((o)) < Me.js and more concretely, j4ij (i,))(s) 2 A. From stability of in with respect to the preference je we have that üú Ri,n((s)) > Pu.j otherwise, (a;, b,) blocks vi according to j. Thus, under the event F(ES(m)), it holds that
A 2 Mi.j
2 (a,m(a.)
+ 2 (i,m(ai)
2
which is contradiction. Therefore, mn is stable with respect to μ..
Theorem 2. By uniform sampling (Algorithm 7. each agent samples each arm T/K times, and mi and fh are matchings generated by agent- agent-propostee proposing DA and arm-proposing DA, respectively. Then,
(i) P(m is unstable) O(EES(m)) exp(
ATT ))
8K
(ii) P(m is unstable) O(ESS()) exp(
ATT
))
8K
15

---

where m. is the agent- peent-pessimal stable matching and m. is the agent-optimal stable matching.
Proof. Since ri and myz are produced by DA based on ü. both matchings are stable with respect to j. By Lemma T. both matchings are guaranteed to be stable with respect to conditioned on F(E)( (or F(ES(mn))). Thus, it follows
P(m unstable)
- P(F(ES((i)))
(, P((Na. Pasl 2 A/2)]
B
Σ
P(Ina Payl 2 A/2)]
(ES(R)))))
ATT 8K ):
2B exp(
where the second line follows from the definition of the event F, the third line is by union bound, and
the last line follows from Lemma 4 that ji. ji.j is v 7 -ssubaaussinn with 0 mean.
To complete the proof for 1i, we demonstrate an upper bound of (m)))( Then we have that [B( )|] |ES(m) s NK P(m m))
< NK: j.3' such that Pa. > paig's Pass < (s.
< N2 P(us.j >> p Dig < (
AT
S K
4K
where the second line comes from the fact that if vin * m, then there exists agent a; and two arms by and by: that are learned incorrectly since a correct estimated profile produces 77 by agent-proposing DA. The last incquality follows from Lemma 5 since (mis -...') A and number of samples is T/K.
Note that the difference is negligible when 7' is sufficiently large compared with N and K. The same computation applies to my and m. Thus the second statement follows.
A useful technical lemma for bounding the number of samples agents need to find stable matching as follows.
Lemma 6. For variables K N and d >> min(t N log (og(Kt)/tt d) O log( log(
Proof. Define Tiiu := min(t E N log(Kt)) S d} and Tmax == max(t E N log (ot(Kt)/t 2 d}. We observe that Tiin < T max and thus, compute the upper bound of Tiin through Tmax- By the definition of T max, we have
log KT max) S log( K log( (g[[KTaax))
Tmax
S
(3)
Again by the definition of Tmax and the fact that 2 (og²(()) for any O, have
T Tmax & <
log" log2((K) OKgT(aaaxx) <1.
(4)
K
KT
Equation 3 and Equation (4
give
2K logí
K
2K
K 2 2K log( log( 7) s d log(
T Iaxx
< 7
log(
{) - log(
d
On the other hand, we compute the lower bound of Tmin by the definition of Tmin:
K
Tmin lo (log(KTmmn)) 2 à log(
J
log (Tmm)))
Since Tiin is a positive integer, we have that
K log
Tmin 2 ā log( a log(K)) >
d
when K > 2. Thus the proof is complete.
16

---

Theorem 3. [Sample complexity for uniform sampling algorithm] With probability at least - both the uniform agent-DA DA and the uniform arm-DA algorithms find stable matching with the same sample complexity Ō NK log(a 1og(a-1) )
Proof. We first show that Algorithm I finds the stable matching m with a high probability. Then we analyze the total number of samples. agent a, samples arm by for times, by Lemma and the definition of subgaussian, with probability at least 1 (Keja such that (Aa,(()) - Ms.l S
where (t) is the sample average of agent a; over arm by when a, samples by for times. Taking union bound for all j, gives that with probability at least KR ((8).
(t) - - S /23 log(Kt)/tt E N, Vi [M], Vj E [K].
(5)
Conditioned this, we first show that Algorithm Algorithm[lerminatee terminates with true preference profiles. Assume that the mechanism stops with sample size T' for each agent-arm pair. For any and j + h, ja.j Pi,.. have stopping condition
Pr. PL 2 28lo KT)/T,
(6)
since by Equation ①T and line of Algorithm
1
LC = P4.5 22 log /T/TT2 2 Pi + /28
Then by Equation
Mij 2 LCB,, UCB p4,b
Hence, uniform agent-DA DA algorithm produces the stable matching m..
Then compute the sample complexity. By Equation 55)
Pi.j - Pu. 2 -2 log KT) + pag - 1i,k-
(7)
Therefore if set
T= =mmnn! N: 28 (Kt)t S A/4).
we have that
Pij Pi, 2 23 log KT)/T pi.j Pi.
2 2 log KT)/T +
2 2//22/322 2 (TT)/T
and thus the stopping condition is satisfied. By Lemma 6 we have T minfl E N 1233 < A/4] 0 2z log( X+ )). Note that T is the sample complexity for each agent-arm pair. Thus, the total number of samples are bounded by NKT 0 ANK
log( 8K x ))-
A
By setting a probability budget a = kーーT, we have that with probability at least 1 - a, the uniform (8NK A2
4N
sampling algorithm terminates with sample complexity O log( 9K )), where 1+ A=
log(ANa 1 lng(K)
Therefore, the sample complexity for uniform agent-DA algorithm is Ō NK log(a
For uniform arm-DA, the only difference is that it produces matching by arm cum-proposing DA algorithm. Therefore, uniform arm-DA finds the stable matching m with the same sample complexity.
D Omitted proofs from Section 5
Theorem 4. By Algorithm assume that agent a; samples arm by for Tei and in is returned by the algorithm. We define Tmin Then, we have
(S) Te,5 as the minimum sample size for agent-arm pairs.
22Tmin ))
P(m is unstable) s O(IES(m) exp(
' denotes the upper bound that omits terms logarithmic in the input.
17

---

Proof. When the sampling phase of Algorithm Bends, there is no unmatched agent and the matching in is the same matching proposed by arm propooiii DA according estimated utility f. Thus, n stable with respect to ji. By Lemma]
|
we know that vn is stable under the event F (m)). Then
Pmm is unstable)
- P(F(ES(())) Bl Festmm) P(( Paul 2 A/2)]
E
Σ
P(Iet - PaJl 2 A/2)
(o..)))EES()))))
A T i.j
$ 2E (E.
exp(
A min )]
S ES( exp(-
8
The third line comes from union bound, and the fourth line comes from Lemma 4 and that ji. i is V Ti, subgaussian. Observe that correct estimated profile on (S(m) outputs m by Algorithm since the algorithm follows arm-DA algorithm. Then we have the computation
P(m + m) S P(3(at, by) ES(m), by: E ES(m), and pig > Ma,t's Mas Ps.g') P(ui > Pag Pas < (43')
E
(o.b))).rby)EES(N))
A 2
Σ
exp(
2( T
(EES(())
A min
< NNK exp(
where the third line follows from Lemma 5 Therefore, we have that m converges to m and so the probability of not being is negligible when Tmin is sufficiently large. Thus, we complete the proof.
Theorem 5. [Sample complexity for AE arm-DA algorithm] With probability at least 1 - a, Algo- rithm 3 terminates and returns stable matching, m, with sample complexity of
(mmm)
log(a 11)-
A
Proof. The proof has similar structure to the proof of Theorem 3 however, the proof is different because Algorithm Jonly sample the pairs in the envy set ES(m) while Algorithm samples all arms uniformly.
We first show that with high probability, the algorithm terminates with m. If agent a; samples arm by for t times, by Lemma 4 and the definition of subgaussian, we have that [Pr,( - uر s TKtjo. here (t, is the sample average of agent o; over arm by when a; samples b; for i times. Taking a union bound over all f and all pairs a;, by the envy set (m)) we have that
223 225 log(Kt)/ Kt)/l with probability at least 1 2
(t) pr, (otg) Vt 2 1, V(a, e ES(m)
(8)
with probability at least 21ES(m)) ((B). Conditioned on Equation (8) we have that Algorithm
K2
terminates with correct estimated profile on pairs of the envy-set (m5 as the same logic in the first part of the proof in Theorem 3 Thus, since Algorithm 3 follows arm-propasing DA algorithm, the algorithm outputs m.
Next, we claim that for every agent-arm pair in the envy-set ES(m), the sample complexity is [K
T = minft E N /25 (otK))/t < A/4] 0 A= log( A )). We prove this for each agent-arm pair by induction on the number of iterations of while loop Algorithm 3 We will show that each invocation of Algorithm [ the number of samples for any agent-arm pair the envy-set (m)( is at most T. Thus, since the while loop in Algorithm checks whether the sample number is bounded by T. we get the desired bound.
18

---

Base case. Let arms by and byr are the first to propose to agent a, Let Ti, and Tú,y be the number Without loss of generality, we assume
of samples for agent a, over arm b, and by. by Algorithm 2 that Mú > Migs Since both arms have not been sampled before, by Algorithm 2 the stopping condition Equation (6) satisfied when Tig = Tig since
PL. - PG,5" 2 2/3 log KT)/T + ps.j - Pa.s'
2/
2 22 23 log /T +A
2 2 2/228og (
where the first line comes from Equation 8 and the third line comes from the definition of T.
Inductive steps. By induction hypothesis, in Algorithm E agent 0, has already sampled by for 4. S T times. Let by be the winner in the last round and by proposes to ag in this round. In Line of Algorithm 2 agent a; samples ti, times of arm by before sampling by. Then if a, samples by for T- T more times and ag samples byr I" times, by the same computation as the base case, we have that the stopping condition Equation (6) is satisfied when Ti, Ti.y' T. Thus, we show that the number of samples for any agent-arm pair is bounded by T.
Since Algorithm only samples the agent-arm pairs in the envy set ES(m). we get that the total sample complexity is (m) [ = O (((())(m)]
log
3K )).
A
By setting the probability budget (E)(m) KP
we have that with probability at least 1 a, the
AE arm-DA algorithm has sample complexity complexity of the order ([ES(m)]
log( A
RK where
A
8 [gg(4)]S(m]aa=]) Therefore, it is of the order Ó( [[S(m]] A
log((=")))-
log(K)
Lemma 3. Considering any true preference μ., have the following bounds for envy-set:
(i) Size of the envy-set for m. (max N, K} - N)N S [E5(m)) S NK.
(ii) Size of the envy-set for me (max) N, K} N)N < (m)( NK 1
Proof. First we consider the best case and N 2 K. Suppose that for any i E [K] agent a, prefers arm b; the most; also for any j E [K] arm by prefers agent a, the most. Under this preference profile, we immediately have m yn {(11 by), (a2, ba),..., (ak, bx)} and, since all arms match their first choice, we have [m]] = [F.((m) = K N, we construct the preference profile similarly for the first N agents and N arms, then the remaining K - N arms are not matched, and so (m) = (mmm = (K- - NV..
Now consider the worst case for m. We keep agents' preferences the same as stated above; however, agent a; is the worst agent according to by for each j E [min(N, K}]. Then mा {(a1, b1), (a2, be),.., (Cmin(N,K") (N.)(N, Thus, for each j E [K], arm by is in the envy-set (m) of agent a; for all i E [N]. Then, envy-set (m( contains all agent-arm pairs and so in the worst case [E(((T))= NN.
Lastly, we show the worst case for m. We claim that for all matched arms, at most one arm can get matched to the worst choice. In their seminal work. Gale and Shapley [1622] observed that when one arm gets matched to the worst agent, it proposes to all other agents and get rejected by them. This observation implies all other agents are tentatively matched and thus agent is available. Therefore, we have that the worst case is (m(m)) = NK- N +1.
E Omitted details from Section
We define the sequence preference condition (SPC) that we use for our experiments. A preference profile satisfies SPC if and only if there is an order agents and arms such that Vi E [N], > 2,14, > Mi.j and Vi E [K], Vj > i, a, >6, az. If each participant of one side (agents arms) has the same preference (also known as masterlist ) over the other, the preference profile satisfies SPC. Clearly, a preference profile that is SPC satisfies a-condition.
Figure 4 shows the stability and regrets for all four algorithms under the constraint of the agent masterlist preference profiles. When agents share identical utilities for each arm, the average rewards
19

---

Average Stablity
Average Rogrots
Regrets
CbuCa
Samples
Samples
Samples
Figure 95% confidence interval of stability and regrets for 200 randomized agent masterlist preference profiles.
remain the same regardless of the matching. Consequently, the average regrets (showed in the middle figure) are always zero.
We also explain why the uniform arm-DA algorithm surpasses the AE arm-DA algorithm in terms of R. but underperforms compared the AE-arm DA algorithm in terms of R under general preference profiles. Note that the uniform arm-DA algorithm samples arms uniformly, and thus may end up matching agents arms that between the agent-optimal stable match and the agent-pessimal stable match. Thus, when compared with the agent-pessimal regret, it may seem better. However, in comparison, agents are incrementally matched to increasingly preferable arms throughout the procedure of Algorithm 3 and therefore agents are matched to arms that are no better than agent- pessimal stable match as shown in Figure and Figure
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims in the abstract and introduction match the theoretical analysis in Section 3 Section 4 and Section 5 and the simulated experiments in Section 6
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We mentioned several limitations and future work in Section 7
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
21

---

Justification:
We provide detailed proofs in appendix. Assumptions are clearly stated in the statement of theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We clearly state the experimental details in Section 6
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
22

---

Answer:[Yes
Justification:
We provide codes in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
wwt.Suubmisioooooiiooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We present the experimental setting in Section Additional details are provided Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We show eтror bars for figures in Section al Appendix The error bars are calculated as average 1.96 standard error.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
23

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Experiments use bandit domain and algorithms can be run on a typical personal computer. Minimal compute resources required to reproduce experiments the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp///euurpp...cca/a//////tte
Answer: [Yes]
Justification: Yes, we follow the code ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Yes, we discussed societal impacts of our work in Section 7
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper has no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We don't 't use any existing codes or data.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "lZezqfaquW", "reviewer": "Reviewer_Uabi", "summary": "This paper studies the unexplored question of stability in the study of two-sided market matching problems where preferences of one side are unknown and have to be progressively learned through a bandit learning mechanism. The paper makes a significant contribution in this area, which has hitherto only considered the regret cost aspect. Yet it still neglects the fairness aspect of the ensuing matching, which is a weakness in most solution ignoring balance cost and sex equality cost.\n\nIt would be interesting to consider the cost of eliciting preferences and solving the problem in the classic manner, and illustrate the benefit of the proposed solution over that approach.", "questions": "What is benefit of the proposed methods over one that pays the cost to elicit all preferences?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. Solid improvement in terms of probability to yield stable solutions leading to Arm Elimination arm-DA algorithm.\nS2. Derivation of bounds on samples needed to reach stable matching w.h.p.\nS3. Experimental study among proposed variants.", "weaknesses": "W1. No consideration of fairness aspects of the ensuing matching. \nW2. No illustration of benefit vs. solution that elicits all preferences.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the interesting questions. Please find responses to specific questions below.\n\n>What is benefit of the proposed methods over one that pays the cost to elicit all preferences?\n\nResponse: In the classical preference elicitation framework, each query (either it is based on interview or comparing two options) is deterministic. However, our model enables us to consider stochastic rewards where agents receive a stochastic signal when pulling arms. \nIn addition, in a variety of applications (e.g. job interviews), the information is noisy as a candidate’s performance may not be the same in each iteration. Our model enables us to encode such practical scenarios (please also see Line 28-30 in our paper).\n\n> No consideration of fairness aspects of the ensuing matching. \n\nResponse: We agree with the reviewer that the fairness aspect of the matching is important. Our algorithms, either aiming to reach an agent-optimal stable solution or arm-optimal stable solution, are good for only one side of the market. Within the matching literature, achieving fairness based on criteria such as sex-equality or maximin fairness either are computationally intractable or are solely defined based on ordinal preferences. In particular, computing a sex-equal stable matching [Kato 1993] or a balance stable matching [Feder 1990] is NP-hard even when all preferences are known and deterministic. \n\nKato, Akiko. \"Complexity of the sex-equal stable marriage problem.\" Japan Journal of Industrial and Applied Mathematics 10 (1993): 1-19. \n\nTomás Feder. \"Stable networks and product graphs\", PhD thesis, Stanford University, 1990.", "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": "", "extra_scores": {}}, {"review_id": "zQaiX8qI7k", "reviewer": "Reviewer_wAZr", "summary": "The paper studies the sample complexity of finding a stable matching under the probably approximately (PAC) framework.\n\nIn the model, $N$ agents are to be matched with $K \\ge N$ arms. Each arm has an (a priori unknown) utility to each agent, inducing the agents’ preferences; Arms also has strict preferences over the agents. Agents learn about their rewards by pulling the arms and observing stochastic rewards with means equal to the utilities. The objective is to find a matching that is stable with the desired probability with least possible samples (pullings of arms).\n\nThe paper proposes an arm-proposing deferred acceptance (DA) algorithm with action elimination (AE). The algorithm implements the arm-proposing DA, with the modification where, in face of uncertain preferences over a new proposal and the current match, the agent uses AE to reach a decision of rejection. The sample complexity of the algorithm is analyzed and simulations are used to evaluate the algorithm empirically.", "questions": "- Can the authors elaborate on the assumption that $N \\le K$? Note that, since the main algorithm is an arm-proposing DA variant, the two sides are not symmetric and such an assumption requires justification. When $N > K$ we know that the entire set of stable matchings can exhibit strikingly different behaviors than when $N\\le K$ [1].\n- Is there any reason why the experiment is only carried out on the specific utility model with utilities 1 through 20? What if they come from other distributions, e.g., exponentially or polynomially growing? The additional SPC setting is also quite restrictive in my understanding.\n- Have the authors considered relaxing the notion of stability in such stochastic settings (e.g., [2,3])? Ultimately, strict stability is a rather restricted solution concept and often beyond hope, and an approximate notion may be both more realistic and also more tractable.\n- How should one reason about the minimum preference gap? In general, I would expect this quantity to scale down as the market size increases; realistically speaking, at most $1/n$.\n- Further, indifference can be common in real world applications, and I would hope that the model and the algorithm should allow for such scenarios - pressing a student to form a precise preference over schools that are otherwise entirely comparable seems unnecessary. Maybe approximate stability could be one way to resolve this? E.g., maybe there is a better measure of “average stability” that accounts for utility gap rather than just the probability of stability (Line 324, in my understanding).\n\n[1] Itai Ashlagi, Yash Kanoria, and Jacob D. Leshno. 2017. Unbalanced Random Matching Markets: The Stark Effect of Competition.\" Journal of Political Economy.\n[2] Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum. 2015. A Stable Marriage Requires Communication. In Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).\n[3] Itai Ashlagi, Mark Braverman, and Geng Zhao. 2023. Welfare Distribution in Two-sided Random Matching Markets. In Proceedings of the 24th ACM Conference on Economics and Computation (EC '23).\n\nMinor comments:\n- Line 135: typo. “… leads to unique …” => “… leads to a unique …”\n- Line 359-360: “such variations often introduce computational complexity with known preferences” - I might be missing something obvious, but in the hope to understand this claim better, I hope the authors could clarify what “computational complexity with known preferences” they are referring to here. In my understanding, with known preferences, the vanilla DA should work fine with ties and is efficient.\n- When the problem is formulated as agents pulling arms, I find it hard to reasonable arms proposing. To me, this means that the side that bears the burden of exploration in fact does not control their very own action? Is there a better setup or application that motivates the study?", "limitations": "Limitations are discussed in Section 7: Conclusion and Future Work. The paper is mostly of a theoretical nature.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "The paper combines the online learning from stochastic observations with the classic literature on stability of matchings, a novel and important direction. While intuitive, the algorithmic combination of arm-proposing DA with AE is novel to my understanding.\n\nThe paper is overall clearly written, with consistent notations and clear definitions. I find it easy to follow. The claims seem reasonable, although I did not go over all the proofs.", "weaknesses": "While the results may be new and interesting, I do not find them sufficiently significant. From the theoretical perspective, the algorithm proposed and its analysis both seem fairly standard. The algorithmic improvement also seem marginal, as Theorem 5 only seem to provide a weak improvement on existing results, and nor do the simulations (which are run in a very restrictive setting with a specific form of preferences) seem conclusive on the superiority of the main algorithm. [Edit: From the discussion, I understand that there is some valid rationales behind the simulations (the choice of utility distribution in particular). I think it is worth more discussion and justification.]\n\nOn the empirical front, the paper would benefit from additional motivating examples on why the results can be impactful in real world applications. As will be mentioned in one of my questions, I am not sure how the proposed algorithm can be applied to settings such as school admission, ride share, etc. - in particular, the assumption that rewards are iid and that an arm can be pulled (sampled) repeatedly in an arm-proposing fashion seems hard to interpret in these settings. Without sufficient practical motivation, the results seem only a nice yet marginal theoretical exercise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and suggestions. We first clarify some of the comments. \n> The algorithmic improvement seem marginal, as Theorem 5…\n\nPlease note that sample complexity of the AE arm-DA ($\\frac{|ES(\\underline{m})|}{\\Delta^2}log(\\alpha^{-1})$) has an improvement on that of uniform agent-DA ($\\frac{NK}{\\Delta^2}log(\\alpha^{-1})$). The improvement ratio is $\\frac{NK}{|ES(\\underline{m})|}$. In the best case, the envyset $ES(\\underline{m})$ has size $0$ when $N=K$ (see Remark 3) giving an infinitely better solution. This is the reason why we stress the role of arm-proposing DA in terms of stability. Moreover, the AE algorithm uses the envyset effectively (which has never been done before), unlike the uniform algorithms, as explained, leading to a significant improvement in the sample complexity. \n> Line 359-360: … the vanilla DA should work fine with ties and is efficient.\n\nWhen preferences are ordinal and contain ties, stable solutions may not exist in their strong sense (see, e.g. Irving et al. [1994], Manlove [2002]). We need to consider new stability notions (strict, strong, and weak stability). Moreover, in the presence of ties and incomplete lists, not all agents are matched in every weakly stable matching. In fact, finding a stable solution that is efficient (i.e., matches maximum number of agents) is NP-hard as shown in “Hard variants of stable matchings”, Manlove et al, TCS 2002. \n>When the problem is formulated as agents pulling arms, I find it hard to reasonable arms proposing.\n\nPlease note the difference between “agents pulling arms” and “arms proposing to agents”. The former is our model setup, while the latter is a step in our algorithm. The goal of the problem is to minimize the exploration agents spend in finding a stable matching. Either side of the matching market can propose depending on the algorithm we use. \nAn example in labor markets: Companies are agents and job seekers are arms. When a company organizes an interview with a potential employee, it incurs cost. A company usually does not have prior information about a job seeker in advance. Thus, from the view of the company side, the objective is to find a stable matching using the least number of interviews. Our AE arm-proposing DA algorithm is the case that job seekers propose to companies, and companies organize interviews to filter out the best candidates.\n\nPlease find responses to specific questions below:\n1. We use this assumption to stay consistent with previous papers where they assumed $N \\leq K$ so that each agent at least can be matched to an arm. They had this assumption so that the regret would not be $\\Omega(T)$ for the unmatched agent. Since we do not consider regrets, we agree with the reviewer that such assumption is not required. In fact, removing this assumption does not change our theoretical results, Thm 1 to Thm 5. \n\n2. Please note that the sample complexity depends on minimum preference gap $\\Delta$. In experiments, we keep $\\Delta=1$ to focus on comparing algorithm performance rather than the impact of $\\Delta$. Thus, each agent’s utilities are permuted from $\\{1, 2, \\ldots, 20 \\}$ following a similar experimental setup in Liu et al. [2021], though with slight differences in permutation.\nAllowing $\\Delta$ to vary randomly would obscure algorithm comparisons, as their performance would fluctuate with $\\Delta$. For example, uniformly sampling utilities in (0, 20] would result in $\\Delta$ ranging from 0 to 20, causing high performance variance. \n\nOther distributions, such as exponentially or polynomially growing, are some potential settings but have flaws especially when the number of agents/arms is large. If utilities are permuted from $1^2, 2^2, 3^2, \\ldots, 20^2$, the total number of samples to find a stable matching should decrease, since it should be easier to rank through sampling. E.g. it takes much less effort to differentiate $19^2 = 361$ with $20^2 = 400$ (as compared to differentiate $19$ with $20$). \n\nSPC setting: Preferences where one side has a masterlist capture natural structures, such as riders ranking drivers by ratings or colleges ranking students by exam scores. Previously studies by Sankararaman et al. [2021], Basu et al. [2021], and Wang and Li [2024] have studied this setting. Masterlist is a special case of SPC, both of which ensure a unique stable matching. Thus, we also provide results for SPC to capture this class in our experiments. \nRef: Wang and Li. Optimal analysis for bandit learning in matching markets with serial dictatorship. TCS 2024\n \n3. We thank the reviewer for pointing us to the references. Studying approximate stability could be a future research question. Also, it is not clear if the sample complexity would improve asymptotically if we consider approximate stability [2] or [3]. Thus, we first study the sample complexity for stable matchings in our model before exploring approximate stability.\n\n4. Please note that we do not restrict the value of the utility in our theoretical analysis. Since we consider scenarios (school choice, ridesharing, etc) where we have a finite number of agents and arms, we can assume that the utility values can be scaled as long as it can be stored and accessed using one machine query. In some previous papers that emphasized on regret, e.g. Kong and Li [2024], they consider the case that the utility is a real value in $(0,1]$. Hence, in such an assumption you could expect the minimum preference gap to scale down as the market size increases.\n\n5. Yes, we agree with the reviewer that studying indifference is an interesting future direction. However, this line of results fails to capture indifference, as the regret bound and sample complexity is proportional to $1/\\Delta^2$. One of our initial ideas to overcome the difficulty is to take a different sampling distribution when agents pull an arm, as compared to sub-Gaussian distribution. Indifferences pose several computational challenges (see response to comments).", "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": "", "extra_scores": {}}, {"review_id": "jiYZmZjXBW", "reviewer": "Reviewer_ormW", "summary": "The paper studies stability in matching problems with learned preferences on one side. The two sides are agents and arms. The agents learn their preferences over the arms through sampling while the arms know their preferences over agents. Then a DA algorithm is run with either arms or agents proposing. The paper gives bounds on the probability that the matching found is unstable, as well as sample complexity results, with uniform sampling and for a more refined arm-elimination algorithm. The paper is complemented by numerical simulations.", "questions": "See above, in particular 1. and 3.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem studied, the stability of the matching found by learning, is interesting and novel. Indeed, much of the literature rather focused on the regret achieved but I have not seen many works on looking at the probability of blocking pairs. \n\nThe bounds proved are relevant and well behaved, and relatively intuitive. \n\nThe comparison of uniform sampling and arm elimination (which basically removes a factor K) is nice. \n\nThe paper is easy to follow.", "weaknesses": "1. The bounds proved contain a term in |ES(m)|. This term is natural but may be quite large. It would be good to give an order of magnitude for some reasonable preferences. \n\n2. The theoretical tools to prove the main results are relatively standard from bandits. This is not a weakness in itself, I am mentioning it to justify that I do not see the contribution as a particularly intricate theoretical analysis. \n\n3. Is it possible to provide lower bounds to know whether the analysis is tight? And to do better than arm elimination?\n\n4. The motivation for the problem studied could be further developed to justify the setting introduced (sampling, then DA). For instance, a reasonable alternative would be to have a more dynamic setting where different agents get matched at different times, e.g., when they are confident that they are done exploring (and then the pair leaves the system). Of course, this would be a different problem and I am not suggesting the authors should have studied this one instead, but it would be nice to strengthen the motivation for the given problem studied.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments. Please see the following responses to your questions.\n\n> The bounds proved contain a term in |ES(m)|. This term is natural but may be quite large. It would be good to give an order of magnitude for some reasonable preferences. \n\nResponse: Please note that in the proof of Lemma 3, we constructed preference profiles that have the smallest envy-set size $|ES(\\underline{m})| = (K-N)N$ (which would be reduced to $0$ if $N = K$) and the largest envy-set size $|ES(\\underline{m})| = NK - N + 1$.  \n\nOne way to illustrate the magnitude of $|ES(\\underline{m})|$ is through the lens of arm-proposing DA algorithm. Usually in a highly competitive environment for arms, e.g. there are much more arms than agents so that a lot of arms are not matched, the magnitude of $|ES(\\underline{m})|$ is large since we need a large number of proposals and rejections in the process of arm-proposing DA. A less competitive environment, e.g. arms put different agents as their top choices, has much smaller magnitude of $|ES(\\underline{m})|$. \n\n\n> The theoretical tools to prove the main results are relatively standard from bandits. This is not a weakness in itself, I am mentioning it to justify that I do not see the contribution as a particularly intricate theoretical analysis.\n\nResponse: We agree with the reviewer that some of the theoretical techniques are borrowed from bandit literature. Please note that the notion of envy-set itself is novel, and we are able to construct our sample complexity based on it. Focusing on $N$ and $K$, as done in previous work, to achieve such bounds does not provide any insight about the preference structure or the structure of the stable matchings.\n\n> Is it possible to provide lower bounds to know whether the analysis is tight? And to do better than arm elimination?\n\nResponse: This is an interesting question that we are also considering. We do not know of any lower bounds. We have an initial idea on whether it is possible to do better than arm elimination arm-proposing DA. Remember that uniform sampling algorithm has sample complexity $\\frac{NK}{\\Delta^2}log(\\alpha^{-1})$ (see Theorem 3). Intuitively, $NK$ comes from the observation that agents uniformly pull all arms so that the number of agent-arm pairs that interact are $NK$. In Arm Elimination arm-proposing algorithm, there is a high probability that the number of agent-arm pairs that interact are $|ES(\\underline{m})|$. \nThen we might ask this question: can we design a new algorithm that with high probability, the number of agent-arm pairs that interact are smaller than $|ES(\\underline{m})|$?  \n\n\n> The motivation for the problem studied could be further developed to justify the setting introduced (sampling, then DA). For instance, a reasonable alternative would be to have a more dynamic setting where different agents get matched at different times, e.g., when they are confident that they are done exploring (and then the pair leaves the system). Of course, this would be a different problem and I am not suggesting the authors should have studied this one instead, but it would be nice to strengthen the motivation for the given problem studied.\n\n\nResponse: Thank you for your suggestion. Yes, one advantage of our solution as compared to the agent-proposing DA, such as Kong et al. 2023, is that agents do not need to explore arms concurrently.  I have a question about your dynamic model. Are you suggesting that agents and arms can come and leave the system? If they leave the system, I'm concerned that the matching might not be stable.", "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": "", "extra_scores": {}}, {"review_id": "rpOvSxbo7w", "reviewer": "Reviewer_ct3v", "summary": "This paper investigates the bandit learning problem in matching markets. It introduces a critical perspective that the objective of regret minimization does not align with achieving market stability. The study explores the sample complexity required to find a stable matching. To address this issue, the authors propose two algorithms: the Uniform Sampling DA algorithm and the Arm Elimination DA algorithm, and provide guarantees based on the corresponding envy-set size.", "questions": "Please see the last part.", "limitations": "The authors adequately addressed the limitations.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper raises a significant issue in the literature of bandit learning in matching markets, highlighting that the objective of regret minimization may not align well with the goal of finding a stable matching.\n\n2. The investigation of sample complexity in this paper delves into the detailed structure, specifically examining the envy-set size with respect to a particular stable matching, thereby deepening the understanding of the learning task's difficulty.", "weaknesses": "1.Although some existing works consider stable regret, their theoretical guarantees also imply guarantees for the sample complexity of reaching (player-optimal/pessimal) stable matchings, as demonstrated by Liu et al. [2020], Kong and Li [2023], and Zhang et al. [2022]. However, this paper does not compare its results with the induced sample complexity of these existing works. Consequently, it is difficult to determine how this work improves upon existing studies in terms of sample complexity and the objective of achieving stable matchings, specifically player-optimal and player-pessimal stable matchings.\n\n2.The technical novelty is limited. The uniform-sampling DA algorithm is standard in the literature, and the arm elimination DA algorithm appears similar to the ODA algorithm in Kong and Li [2024], although they consider a more general many-to-one setting. Please verify this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments. Please see our responses and clarifications below.\n\n> Although some existing works consider stable regret, their theoretical guarantees also imply guarantees for the sample complexity of reaching (player-optimal/pessimal) stable matchings, as demonstrated by Liu et al. [2020], Kong and Li [2023], and Zhang et al. [2022]. However, this paper does not compare its results with the induced sample complexity of these existing works. \n\n\nResponse: We do compare our approach with those of Liu et al. [2021] and  Kong and Li [2023]. These are shown in plots as CA-UCB (in Line 326) and uniform agent-DA, respectively. We will mention it explicitly.  Please note that  Kong and Li [2023] provided an ETGS algorithm, which is essentially the same as the uniform agent-DA algorithm in this paper with minor differences. Both algorithms take UCB/LCB bounds to indicate when to stop sampling. ETGS algorithm has an extra phase of index estimation that only takes $N^2$ samples so the sample complexity in this phase can be ignored, and therefore, the sample complexity of ETGS algorithm would have the same order as uniform agent-DA in our paper. \n\n>Consequently, it is difficult to determine how this work improves upon existing studies in terms of sample complexity and the objective of achieving stable matchings, specifically player-optimal and player-pessimal stable matchings.\n\nResponse: One of the main advantages of this paper is to emphasize the role of arm-proposing DA, while many previous papers including Liu et al. [2020], Kong and Li [2023], take the agent-proposing DA. Action Elimination Arm-proposing DA algorithm takes the advantage of fewer sample complexity for a stable matching, as compared to solutions that take uniform agent-DA.\n\n> The technical novelty is limited. The uniform-sampling DA algorithm is standard in the literature, and the arm elimination DA algorithm appears similar to the ODA algorithm in Kong and Li [2024], although they consider a more general many-to-one setting. Please verify this.   \n\nResponse: The arm elimination DA algorithm is not the same as ODA. After careful comparison of the ODA algorithm, uniform sampling algorithms, and our AE arm-DA algorithm, we explain the significant differences below.  \n\n(i) Firstly we would like to compare regret performance. As the reviewer also mentioned, the ODA algorithm was designed for many-to-one matching markets. Since one-to-one setting is a special case of many-to-one matching markets, we could recover the player-pessimal stable regret for the ODA algorithm as $\\frac{NK}{\\Delta^2}logT$ in the one-to-one setting. On the other hand, ETGS algorithm in Kong and Li [2023] (or uniform agent-DA algorithm in this paper) has player-optimal stable regret $\\frac{K}{\\Delta^2}logT$. Since the uniform arm-DA algorithm aims to reach the player-pessimal stable matching, we can show that its player-pessimal stable regret is also $\\frac{K}{\\Delta^2}logT$ without much difficulty. Therefore, the ODA algorithm has $N$ times the regret bound of the uniform arm-DA algorithm.    \n\nOur simulated experiments show that the AE arm-DA algorithm converges with fewer samples in terms of player-pessimal stable regrets compared with uniform arm-DA algorithm, as shown in Figure 3. By fixing sample size $T$, we also compare regrets. Therefore, our AE arm-DA algorithm has lower regrets than that of the uniform arm-DA algorithm. Therefore, we get the following ordering of player-pessimal stable regret in one to one setting: \n$\\underline{R}(ODA) > \\underline{R}(uni \\ arm-DA) > \\underline{R}(AE \\ arm-DA)$.    \n\n(ii) More importantly, we would like to emphasize that the technical novelty of this paper is the notion of envy-set. While many previous papers including Liu et al. [2020, 2021], Kong and Li [2023, 2024] constructed their theory based on the number of agents $N$ and the number of arms $K$, we discover that the difficulty of the learning problem could depend on a new notion, i.e. envy-set. The ODA algorithm along with many others failed to capture this important observation.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The review team is relatively positive about the authors' work. On the plus side, reviewers found that the studied problem is novel, considering "two-sided market matching problems where preferences of one side are unknown and have to be progressively learned". The reviewers generally also found the results of the paper interesting and relatively intuitive, but with two caveats: 
- One reviewer notes that the analysis is relatively standard and the improvements compared to previous work seem to be a bit weak 
- Several reviewers point out issues with the motivation, noting that the problem could be a better-motivated and that there may be a disconnect between the theory/model/setting and the actual intended applications, which is a potential worry. 

For this reason, I am recommending acceptance as a poster. My understanding is that the paper is above the bar for NeurIPS if there is space for it, however it still suffers from weaknesses that could be addressed in a re-submission/revision. I set my confidence as "less certain" due to the balance of strengths and weaknesses and I do not feel that I have sufficient information about competing papers to make an informed decision, and further recommend that this paper is discussed with the SAC.
Decision: Accept (poster)