Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning

Authors: hadi  hosseini
sanjukta  roy
duohan  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-02 23:14:28

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.

Main paper: 
 introduction: 
 Two-sided markets provide a framework for a 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 on numerous practical applications such as school choice [Abdulkadiroglu et al., 2005a,b] , entry-level labor markets [Roth and Peranson, 1999] , and medical residency [Roth, 1984] . The primary objective is to find a 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 twosided 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 as 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 a matching based on the learned preferences minimize the regret for each agent (see, for example, Liu et al. [2020 Liu et al. [ , 2021]] , Sankararaman et al. [2021] , Basu et al. [2021] , Maheshwari et al. [2022] , Kong et al. [2022] , Zhang et al. [2022] , Kong and Li [2023] , Wang et al. [2022] ).Table 1 : Comparison of bounds on probability of unstable matchings and the sample complexity to find a stable matching. γ = exp -∆ 2 T 8K .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 {a 1 , a 2 , a 3 } and three arms {b 1 , b 2 , b 3 }. Let us assume true preferences are given as strict linear orderings1 as follows:a 1 : b * 1 ≻ b 2 ≻ b 3 a 2 : b * 2 ≻ b 1 ≻ b 3 a 3 : b 1 ≻ b 2 ≻ b * 3 b 1 : a 2 ≻ a 3 ≻ a * 1 b 2 : a 1 ≻ a 3 ≻ a * 2 b 3 : a 1 ≻ a 2 ≻ a * 3The underlined matching is the only stable solution in this instance. The matching denoted by * is a regret minimizing matching: agents a 1 and a 2 have a negative regret (compared to the stable matching), and a 3 has zero regret. However, this matching is not stable because a 3 and b 1 form a blocking pair. Thus, a 3 would deviate from the matching.Note that stability is a 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. [2021] , Pokharel and Das [2023] ) did stability analysis, it is insufficient as we discuss later in Section 3 and Section 4.Our contributions. We propose bandit-learning algorithms that utilize structural properties of the Deferred Acceptance algorithm (DA)-a seminal algorithm proposed by Gale and Shapley [1962] that has played an essential role in designing stable matching markets. Contrary to 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 a stable matching improves compared to those used in many previous work (an agent-proposing variant, such as Liu et al. [2020] , Basu et al. [2021] , Kong and Li [2023] ). We demonstrate that for a class of profiles (i.e. profiles satisfying α-condition or those with a masterlist), the arm-proposing DA is more likely to produce a stable matching compared to the agent-proposing DA for any sampling method (Corollary 1). For the commonly studied uniform sampling strategy, we show the probability bounds for two variants of DA for general preference profiles (Theorem 2). We initiate the study of sample complexity in the Probably Approximately Correct (PAC) framework. We propose a non-uniform sampling strategy which is based on armproposing DA and Action Elimination algorithm (AE) [Even-Dar et al., 2006] , and show that it has a lower sample complexity as compared to uniform sampling (Theorem 3 and Theorem 5). Lastly, we validate our theoretical findings using empirical simulations (Section 6).Table 1 shows the main theoretical results for uniform agent-DA algorithm, uniform arm-DA algorithm, and AE arm-DA algorithm. We note that the novel AE arm-DA algorithm achieves smaller sample complexity for finding a stable matching. Our bounds depend on structure of the stable solution m, parameterized by the 'amount' of justified envy ES(m) (see Definition 4.1).The two-sided matching problem is one of the most prominent success story of the field of game theory, and in particular, mechanism design, with a profound practical impact in 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] 's seminal work, where they, along with a long list of subsequent works focused primarily on game-theoretical aspects such as stability and incentives [Roth and Sotomayor, 1992 , Roth, 1986 , Dubins and Freedman, 1981] . While the DA algorithm is strategyproof for the proposing side [Gale and Shapley, 1962] , no stable mechanism can guarantee that agents from both sides have incentives to report preferences truthfully in a 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., 2021] .Stable matchings under uncertain linear or pairwise preferences were studied by Aziz et al. [2020 Aziz et al. [ , 2022]] . When preferences are unknown, the problem of learning preferences can be modeled as a multi-agent multi-arm bandit problem. Recent work has shown a variety of learning approaches using Explore-Then-Commit (ETC), Thompson sampling [Kong et al., 2022] , in centralized [Liu et al., 2020, Pokharel and Das, 2023] or decentralized [Sankararaman et al., 2021, 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 et al., 2021 , Basu et al., 2021 , Maheshwari et al., 2022 , Wang and Li, 2024] or those that generalize to many-to-one markets [Wang et al., 2022 , Kong and Li, 2024 , Li et al., 2024 ]. An extensive related work with details on upper bounds is provided in Appendix A. 
preliminary: 
 Let [k] = {1, 2, . . . , k}, and ζ(β) = ∞ n=1 1 n β denotes the Riemann Zeta function, and 2 > ζ(β) > 1 if β ≥ 2.Problem setup. An instance of a two-sided matching market is specified by a set of N agents, N = {a 1 , a 2 , . . . , a N } on one side, and a set of K arms, K = {b 1 , b 2 , . . . , b K }, on the other side. The preference of an agent a i , denoted by ≻ ai , is a strict total ordering over the arms. Each agent a i is additionally endowed with a utility µ i,j over arm b j . Thus, we say an agent a i prefers arm b j to b k , i.e. b j ≻ ai b k , if and only if µ i,j > µ i,k . 2 We use µ to indicate the utility profile of all agents, where µ = (µ i,j ) i∈[N ],j∈ [K] . The preferences of arms are denoted by a strict total ordering over the agents, i.e. an arm b i has preference ≻ bi . The minimum preference gap is defined as ∆ = min i∈[N ] min j,k∈[K],j̸ =k |µ i,j -µ i,k |. It captures the difficulty of a learning problem in matching markets, i.e., the mechanism needs more samples to estimate the preference profile if ∆ is small. Stable matching. A matching is a mapping m :N ∪ K → N ∪ K ∪ {∅} such that m(a i ) ∈ K for all i ∈ [N ], and m(b j ) ∈ N ∪ {∅} for all j ∈ [K], m(a i ) = b j if and only if m(b j ) = a i .Additionally, m(b j ) = ∅ if b j is not matched. Sometimes we abuse the notation and use a i to denote i if agent is clear from context, and similarly use b j to denote j if arm is clear from context. Given a matching m, an agent-arm pair (a i , b j ) is called a blocking pair if they prefer each other than their assigned partners, i.e., b j ≻ ai m(a i ) and a i ≻ bj m(b j ). Note that for any arm b j , getting matched is always better than being not matched, i.e., a i ≻ bj ∅. A matching is stable if there is no blocking pair.The Deferred Acceptance (DA) algorithm [Gale and Shapley, 1962 ] finds a stable matching in two sided market as 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 is simultaneously pessimal for the receiving side [McVitie and Wilson, 1971] . We denote the agent-optimal (arm-pessimal) stable matching by m and the agent-pessimal (arm-optimal) stable matching by m. Rewards and preferences. Agents receive stochastic rewards by pulling arms. If an agent a i pulls an arm b j , she gets a stochastic reward drawn from a 1-subgaussian distribution 3 with mean value µ i,j . We denote the sample average of agent a i over arm b j as μi,j . The agent-optimal stable regret 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 R i (m) = µ i,m(ai) -µ i,m(ai) for agent a i and matching m. Similarly, the arm-optimal stable regret as R i (m) = µ i,m(ai) -µ i,m(ai) .Preference profiles. 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 to the same matching, namely m = 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. Karpov [2019] provided a necessary and sufficient condition (α-condition) to characterize preference profiles that satisfy uniqueness consistency. A preference profile satisfies the α-condition if and only if there is a stable matching m and an order of agents and arms such that ∀i ∈ [N ], ∀j > i, m(a i ) ≻ ai b j , and a possibly different order of agents and arms such that ∀j ∈ [K], ∀i > j, m(b j ) ≻ bj a i . 
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 a property called uniqueness consistency. We show that for any sampling algorithm, the arm-proposing DA algorithm is more likely to generate a stable matching compared to the agent-proposing 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 μ, if the agent-proposing DA algorithm produces a stable matching, then the arm-proposing DA algorithm produces a stable matching.Theorem 1 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 we 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-proposing DA algorithm if the true preferences satisfy uniqueness consistency condition.The following example further shows that the arm-proposing DA could generate a stable matching even if the estimation is incorrect, while the agent-proposing DA generates an unstable matching. In Section 6, we provide empirical evaluations on stability and regret of variants of the DA algorithm.Example 2 (The stability of arm vs. agent proposing DA when estimation is wrong.). Consider two agents {a 1 , a 2 } and two arms {b 1 , b 2 }. Assume the true preferences are as follows:a 1 : b * 1 ≻ b 2 a 2 : b 1 ≻ b * 2 b 1 : a * 1 ≻ a 2 b 2 : a * 2 ≻ a 1The matching denoted by * is the only stable solution in this instance. Assume that after sampling data, agent a 1 has a wrong estimation: b 2 ≻ b 1 and agent a 2 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-proposing DA (e.g. Liu et al. [2021] , Kong and Li [2023] ) may similarly fail to find a stable matching as they do not exploit the known arms preferences effectively.Algorithm 1: Uniform sampling algorithm Input :Parameter β, sample budget T. for t = 1, 2, . . . , T do for i = 1, 2, . . . , N do Agent ai pulls mi(t) = bj, where j = (t + i -1) mod K + 1;Agent ai observes a return Xi(t) and updates μi,j ; Compute U CBi,j and LCBi,j using β;if ∃ a permutation σi for all i ∈ [N ] such that LCB i,σ i (k) > U CB i,σ i (k+1) , ∀k ∈ [K -1] then Break; return {μi,j | i ∈ [N ], j ∈ [K]}. 
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 a technique in bandit literature [Garivier et al., 2016] (usually termed as exploration-then-commit algorithm, ETC). Kong and Li [2023] utilized UCB to construct a 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.e. agents are confident that arms are ordered by the estimation correctly. Then, in the commit phase agents form a matching through agent-proposing DA, and keep pulling the same arms.Agents construct CIs based on the collected data by utilizing the upper confidence bound (UCB) and lower confidence bound (LCB). Given a parameter β, if arm b j is sampled t times by agent a i , we define the UCB and LCB as follows:EQUATIONwhere μi,j (t) is the average of the collected samples.Uniform sampling algorithm (Algorithm 1) Agents explore the arms uniformly. Suppose that agent a i has disjoint confidence intervals over all arms, i.e., there exists a permutationσ i := (σ i (1), σ i (2), . . . , σ i (K)) over arms such that LCB i,σi(k) > U CB i,σi(k+1) for each k ∈ [K -1].Then, agent a i can reasonably infer the accuracy of the estimated preference profile. The parameter β is used to control the confidence length, where a larger β implies that the agent needs more samples to differentiate the utility for a pair of arms.After the sampling stage, agents can consider to form a matching either through agent-proposing DA or arm-proposing DA, as is discussed in Section 3. For simplicity, we refer uniform sampling ( Algorithm 1) with agent-proposing DA as uniform agent-DA algorithm, and uniform sampling with arm-proposing DA as uniform arm-DA algorithm.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 a stable matching using the properties of stable solutions and the structure of the profile. We first define the following notions of local and global envy-sets. Definition 4.1. The local envy-set for agent a i for a matching m is defined asES i (m) = ∅ if {b j : a i ≻ bj m(b j )} is empty {b j : a i ≻ bj m(b j )} {m(a i )} otherwise.The global envy-set of a matching m is defined as the union of local envy-sets over all agents:ES(m) = i∈[N ] {(a i , b j ) : b j ∈ ES i (m))}.By the definition of stability, a matching m is stable if and only if the global envy-set is justified, i.e., agents truly prefer their current matched arm to the arms in the envy-set ES(m). Formally, µ i,m(ai) ≥ µ i,j , for all (a i , b j ) ∈ ES(m) if and only if m is a stable matching. This observation is key in establishing theoretical results.The following lemma provides a 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. [2024] . Lemma 1. Assume μ is the sample average, and matching m is stable with respect to μ. Define a 'good' event for agent a i and arm b j as F i,j = {|µ i,j -μi,j | ≤ ∆/2}, and define the intersection of the good events over envy-set as F(ES( m)) = ∩ (ai,bj )∈ES( m) F i,j . Then if the event F(ES( m)) occurs, matching m is guaranteed to be stable (with respect to µ). Now we 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 m1 and m2 are matchings generated by agent-proposing DA and arm-proposing DA, respectively. Then,(i) P ( m1 is unstable) = O(|ES(m)| exp(-∆ 2 T 8K )), (ii) P ( m2 is unstable) = O(|ES(m)| exp(-∆ 2 T 8K )), where m is the agent-pessimal stable matching and m is the agent-optimal stable matching.Proof sketch. Since m1 and m2 are produced by DA based on μ, both matchings are stable with respect to μ. By Lemma 1, both matchings are guaranteed to be stable with respect to µ conditioned on F(ES( m1 )) (or F(ES( m2 ))). Thus, it followsP ( m1 is unstable) ≤ 1 -P (F(ES( m1 ))) = E[∪ (ai,bj )∈ES( m1) P (|µ i,j -μi,j | ≥ ∆/2)] [definition of F] ≤ E[ (ai,bj )∈ES( m1) P (|µ i,j -μi,j | ≥ ∆/2)] [union bound] ≤ 2E[|ES( m1 )|] exp(- ∆ 2 T 8K ) [ K T -subgaussian with 0 mean].To complete the proof for m1 , we demonstrate an upper bound ofE[|ES( m1 )|]. We show that |E[|ES( m1 )|] -|ES(m)|| ≤ N 2 K 3 exp(-∆ 2 T 4K). The difference is negligible when T 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 agent-pessimal matchings. Then, combining Theorem 2 and Lemma 2, we prove the next corollary. Lemma 2. Given any instance of a matching problem, we have the following relationship between the size of the two envy sets:|ES(m)| ≤ |ES(m)|.Proof. Agent-pessimal stable matching m is the arm-optimal stable matching, and agent-optimal stable matching m is the arm-pessimal stable matching, so we have that m(b j ) ≻ bj m(b j ) or m(b j ) = m(b j ) for each arm b j . From the definition of the envy-set, we have|ES(m)| ≤ |ES(m)|.Corollary 2. The uniform arm-DA algorithm has a smaller probability bound of being unstable than the uniform agent-DA algorithm.Remark 1. Liu et al. [2020] showed the probability bound of exp(-∆ 2 T 2K ) for finding an invalid ranking by the ETC algorithm, 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 not relate the probability bound with the structure of the instance, whereas the bound in Theorem 2 crucially uses the envy set to improve the probability of finding a stable solution. Liu et al. [2021] provided an upper bound on the sum of the probabilities of being unstable for the Conflict-Avoiding UCB algorithm (CA-UCB). Under CA-UCB algorithm, O(log 2 (T )) out of T matchings are unstable in expectation. We turn to analyze the sample complexity to learn a stable matching under the probably approximately correct (PAC) framework. In particular we ask: given a probability budget α, how many samples T are needed to find a stable matching? Formally, an algorithm has sample complexity T with probability budget α if with probability at least 1 -α, the algorithm guarantees that it would find a stable matching with the total number of samples over all agent-arm pairs upper bounded by T . Theorem 3. [Sample complexity for uniform sampling algorithm] With probability at least 1 -α, both the uniform agent-DA and the uniform arm-DA algorithms find a stable matching with the same sample complexity Õ( N K ∆ 2 log(α -1 ))4 .Note that uniform agent-DA algorithm finds the stable matching m, and uniform arm-DA algorithm finds the stable matching m. Uniform sampling (Algorithm 1) 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. 
an arm elimination da algorithm: 
 The proposed algorithm (Algorithm 3) combines the arm-proposing DA and Action Elimination (AE) algorithm [Audibert and Bubeck, 2010 , Even-Dar et 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.e. the upper confidence bound is smaller than another arm's lower confidence bound), and outputs the best arm when there is only one arm that hasn't been eliminated. Note that Algorithm 3 differs from the vanilla arm-proposing DA in Line 8, when an agent has been proposed by two 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 3 terminates with the arm-optimal matching m.We compute the probability bound for learning an unstable matching for Algorithm 3. Contrary to uniform sampling, here we compute the bound on given sample size.Theorem 4. By Algorithm 3, assume that agent a i samples arm b j for T i,j and m is returned by the algorithm. We define T min = min (ai,bj )∈ES( m) T i,j as the minimum sample size for agent-arm pairs. Then, we haveEQUATION)).Remark 2. Theorem 4 provides stability bound for Algorithm 3 that depends on T i,j , which is unknown apriori. If the total sample budget is N T and we set T i,j = N T |ES(m)| , the stability bound )), as stated in Theorem 2. Even though the upper bound could be larger than that of Algorithm 1, simulated experiments show that AE arm-DA significantly improves stability guarantees compared to the uniform sampling variants (Algorithm 1).We compute the sample complexity to learn a stable matching for Algorithm 3. Note that agents only sample pairs in the envy-set, while in Algorithm 1 agents explore all arms uniformly. The following analysis shows that Algorithm 3 has smaller sample complexity compared to Algorithm 1. Theorem 5. [Sample complexity for AE arm-DA algorithm] With probability at least 1 -α, Algorithm 3 terminates and returns a stable matching, m, with sample complexity ofES(m) ∆ 2 log(α -1 )).Proof sketch. We begin by defining a good event |μ i,j (t) -µ i,j | ≤ 2β log(Kt)/t only for agentarm pairs in the envy-set |ES(m)|. Conditioned on such events for all time, we demonstrate that the algorithm terminates with true preferences on the envy-set ES(m), and thus, the algorithm executes the arm-proposing DA when agents have known preferences and produces m.Then we show the upper bound of sample complexity for each agent-arm pair:T = O( β ∆ 2 log( βK ∆ 2 )). We prove it by induction on the number of proposals. The base case is when arms b j and b j ′ propose to agent a i for the first time. Then, we show the number of samples for each pair is bounded by T . In the inductive step, say b j is the winner in the last round and has sampled t i,j ≤ T times, and b j ′ proposes to a i in this round. Then if a i samples b j for T -t i,j more times and a i samples b j ′ 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-arm pairs in the envy set ES(m), we get that the total sample complexity is|ES(m)|T = O( β(|ES(m)|) ∆ 2 log( βK ∆ 2 )). By setting the probability budget α = 4|ES(m)| K β, we have that with probability at least 1 -α, the AE arm-DA algorithm has sample complexity Õ( |ES(m)| ∆ 2 log(α -1 )). The complete proof appears in Appendix D.It is worth noting that a large β implies a small α, which implies that the algorithm needs more samples to guarantee finding a stable matching. We show bounds on the envy-sets in the next lemma. Lemma 3. Considering any true preference µ, we have the following bounds for envy-set: 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)| N K , which further shows that fewer arms from the envy-set ES(m) need to be sampled. Lemma 3 states the best-case and worse-case ratios as max{N,K}-N K and 1 -N -1 N K < 1. Thus, Algorithm 3 strictly improves the sample 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 |ES(m)| is the number of proposals made by arms and rejections made by agents in the arm-proposing DA algorithm. In a 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 |ES(m)| is large. In a less competitive environment, e.g. when arms put different agents as their top choices, |ES(m)| has much smaller magnitude. 
experimental results: 
 In this section, we 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 et al. [2021] : for each i, the true utilities {µ i,1 , µ i,2 , . . . , µ i,20 } are randomized permutations of the sequence {1, 2, . . . , 20} so that the minimum preference gap is fixed (∆ = 1) and algorithm performance exhibits relatively low variability. Arms' preferences are generated the same way. We conduct 200 independent simulations, with each simulation featuring a 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-DA5 , uniform arm-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 to both types of uniform sampling algorithm and CA-UCB algorithm (Figure 1 ). On the other hand, the regret gap between uniform agent-DA and other two arm-proposing 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 regret converges faster to 0, compared to uniform algorithms, while still keeping faster stability convergence (Figure 2 ). Additional experiments with other preference domains (e.g. masterlist) in provided in Appendix E.At the first glance, Figure 1 (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 is with respect to the agent-optimal solution (i.e. R); and thus, the AE arm-DA algorithm by design is not optimized to reach that solution. Upon further investigation, however, we see that when comparing the two algorithms using the agent-pessimal regret (R) then the AE arm-DA converges with fewer samples both in terms of average and maximum regrets, as illustrated in Figure 3 . 
conclusion and future work: 
 The game-theoretical properties such as stability in two-sided matching problems are critical indicators of success and sustenance of matching markets; without stability agents may 'scramble' to participate in secondary markets even when all preferences are known [Kojima et al., 2013] . We demonstrated key techniques in learning preferences that rely on 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 as preferences are revealed [Rastegari et al., 2014] .We conclude by discussing some limitations and open questions. First, extending this framework to 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, as 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.Suppose for contradiction that m2 ̸ = m * . Then there must exist some k > l, such that m2 (b l ) = a k . However, since both m1 and m2 are stable with respect to μ and m2 is arm optimal, the partner of arm b l in m2 is at least as good as its partner in m1 . Thus,a k = m2 (b l ) ≻ b l m1 (b l ) = a l ,which is a contradiction to equation ( 2). Thus, we prove that m2 is also stable (with respect to true utility). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: Yes, we follow the code of 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 the societal impacts of our work in Section 7.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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 to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper has no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 use any existing codes or data.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: 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 X 1 and X 2 are independent and d 1 and d 2 subgaussian, respectively, then we have the following property:(1) V ar[X] ≤ d 2 .(2) cX is |c|d-subgaussian for all c ∈ R.(EQUATIONBy the property of independent subgaussian random variables, we have the following lemma that bounds the probability of ranking two arms wrongly. Lemma 5. Sample h 1 data {X 1 , X 2 , . . . , X h1 } i.i.d. from 1-subgaussian with mean µ 1 , and h 2 data {Y 1 , Y 2 , . . . , Y h2 } i.i.d. from 1-subgaussian with mean µ 2 , where µ 1 < µ 2 . Two datasets are independent. Define μ1 and μ2 as the sample mean for two datasets. Then we haveP (μ 2 < μ1 ) ≤ exp(- (µ 2 -µ 1 ) 2 2( 1 h1 + 1 h2 )).Proof. By Lemma 4, μ2 -μ1 is1 h1 + 1 h2 -subgaussian with mean µ 2 -µ 1 .Thus by the definition of subgaussianP (μ 2 < μ1 ) = P ((μ 2 -μ1 ) -(µ 2 -µ 1 ) < -(µ 2 -µ 1 )) ≤ exp(- (µ 2 -µ 1 ) 2 2( 1 h1 + 1 h2 ) ),and the proof is complete.Lemma 1. Assume μ is the sample average, and matching m is stable with respect to μ. Define a 'good' event for agent a i and arm b j as F i,j = {|µ i,j -μi,j | ≤ ∆/2}, and define the intersection of the good events over envy-set as F(ES( m)) = ∩ (ai,bj )∈ES( m) F i,j . Then if the event F(ES( m)) occurs, matching m is guaranteed to be stable (with respect to µ).Proof. We show that no agent-arm pair forms a blocking pair in m. We prove it by contradiction.Assume that there exists an agent a i and an arm b j in the local envy-set ES i ( m) that blocks m, which means µ i, m(ai) < µ i,j , and more concretely, µ i,j -µ i, m(ai) ≥ ∆. From stability of m with respect to the preference μ we have that μi, m(ai) > μi,j , otherwise, (a i , b j ) blocks m according to μ. Thus, under the eventF(ES( m)), it holds that μi,j ≥ µ i,j - ∆ 2 ≥ µ i, m(ai) + ∆ 2 ≥ μi, m(ai) ,which is a contradiction. Therefore, m is stable with respect to µ.Theorem 2. By uniform sampling (Algorithm 1), each agent samples each arm T /K times, and m1 and m2 are matchings generated by agent-proposing DA and arm-proposing DA, respectively. Then,(i) P ( m1 is unstable) = O(|ES(m)| exp(-∆ 2 T 8K )), (ii) P ( m2 is unstable) = O(|ES(m)| exp(-∆ 2 T 8K )),where m is the agent-pessimal stable matching and m is the agent-optimal stable matching.Proof. Since m1 and m2 are produced by DA based on μ, both matchings are stable with respect to μ. By Lemma 1, both matchings are guaranteed to be stable with respect to µ conditioned on F(ES( m1 )) (or F(ES( m2 ))). Thus, it followsP ( m1 is unstable) ≤ 1 -P (F(ES( m1 ))) = E[∪ (ai,bj )∈ES( m1) P (|µ i,j -μi,j | ≥ ∆/2)] ≤ E[ (ai,bj )∈ES( m1) P (|µ i,j -μi,j | ≥ ∆/2)] ≤ 2E[|ES( m1 )|] exp(- ∆ 2 T 8K ),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 µ i,j -μi,j is K T -subgaussian with 0 mean. To complete the proof for m1 , we demonstrate an upper bound of E[|ES( m1 )|]. Then we have that|E[|ES( m1 )|] -|ES(m)|| ≤ N K • P ( m1 ̸ = m) ≤ N K • P (∃i, j, j ′ such that µ i,j > µ i,j ′ , μi,j < μi,j ′ ) ≤ N 2 K 3 P (µ i,j > µ i,j ′ , μi,j < μi,j ′ ) ≤ N 2 K 3 exp(- ∆ 2 T 4K ),where the second line comes from the fact that if m1 ̸ = m, then there exists an agent a i and two arms b j and b j ′ that are learned incorrectly since a correct estimated profile produces m by agent-proposing DA. The last inequality follows from Lemma 5 since (µ i,j -µ i,j ′ ) ≥ ∆ and number of samples is T /K.Note that the difference is negligible when T is sufficiently large compared with N and K. The same computation applies to m2 and m. Thus the second statement follows.A useful technical lemma for bounding the number of samples agents need to find a stable matching is as follows. Lemma 6. For variables K ∈ N and d > 0, min{t∈ N : log(Kt)/t ≤ d} = Θ( 1 d log( K d )).Proof. Define T min := min{t ∈ N : log(Kt)/t ≤ d} and T max := max{t ∈ N : log(Kt)/t ≥ d}.We observe that T min ≤ T max + 1 and thus, we compute the upper bound of T min through T max . By the definition of T max , we haveEQUATIONAgain by the definition of T max and the fact that x ≥ log 2 (x) for any x > 0, we haveEQUATIONEquation ( 3) and Equation (4) giveT max ≤ 1 d log( 2K d log( K d )) = 1 d log( 2K d ) + 1 d log(log( K d )) ≤ 2 d log( 2K d ).On the other hand, we compute the lower bound of T min by the definition of T min :T min ≥ 1 d log(KT min ) ≥ 1 d log( K d log(KT min )).Since T min is a positive integer, we have thatT min ≥ 1 d log( K d log(K)) ≥ 1 d log( K d )when K > 2. Thus the proof is complete.Proof. When the sampling phase of Algorithm 3 ends, there is no unmatched agent and the matching m is the same matching proposed by arm-proposing DA according to estimated utility μ. Thus, m is stable with respect to μ. By Lemma 1, we know that m is stable under the event F(ES( m)). ThenP ( m is unstable) ≤ 1 -P (F(ES( m))) = E[∪ (ai,bj )∈ES( m) P (|µ i,j -μi,j | ≥ ∆/2)] ≤ E[ (ai,bj )∈ES( m) P (|µ i,j -μi,j | ≥ ∆/2)] ≤ 2E[ (ai,bj )∈ES( m) exp(- ∆ 2 T i,j 8 )] ≤ 2E[|ES( m)| exp(- ∆ 2 T min 8 )].The third line comes from union bound, and the fourth line comes from Lemma 4 and that µ i,j -μi,j is 1 Ti,j -subgaussian. Observe that correct estimated profile on ES( m) outputs m by Algorithm 3 since the algorithm follows arm-DA algorithm. Then we have the computationP ( m ̸ = m) ≤ P (∃(a i , b j ) ∈ ES( m), (a i , b j ′ ) ∈ ES( m), and µ i,j > µ i,j ′ , μi,j < μi,j ′ ) ≤ (ai,bj ),(ai,b j ′ )∈ES( m) P (µ i,j > µ i,j ′ , μi,j < μi,j ′ ) ≤ (ai,bj ),(ai,b j ′ )∈ES( m) exp(- ∆ 2 2( 1 Ti,j + 1 T i,j ′ ) ) ≤ N K 2 exp(- ∆ 2 T min 4 ),where the third line follows from Lemma 5. Therefore, we have that m converges to m and so the probability of not being m is negligible when T min is sufficiently large. Thus, we complete the proof.Theorem 5. [Sample complexity for AE arm-DA algorithm] With probability at least 1 -α, Algorithm 3 terminates and returns a stable matching, m, with sample complexity ofÕ( ES(m) ∆ 2 log(α -1 )).Proof. The proof has similar structure to the proof of Theorem 3; however, the proof is different because Algorithm 3 only sample the pairs in the envy set ES(m) while Algorithm 1 samples all arms uniformly.We first show that with a high probability, the algorithm terminates with m. If agent a i samples arm b j for t times, by Lemma 4 and the definition of subgaussian, we have that |μ i,j (t) -µ i,j | ≤ 2β log(Kt)/t with probability at least 1 -2 (Kt) β , here µ i,j (t) is the sample average of agent a i over arm b j when a i samples b j for t times. Taking a union bound over all t and all pairs a i , b j in the envy set ES(m), we have that|μ i,j (t) -µ i,j | ≤ 2β log(Kt)/t, ∀t ≥ 1, ∀(a i , b j ) ∈ ES(m) (8) with probability at least 1 -2|ES(m)| K β ζ(β).Conditioned on Equation (8), we have that Algorithm 3 terminates with correct estimated profile on pairs of the envy-set ES(m) as the same logic in the first part of the proof in Theorem 3. Thus, since Algorithm 3 follows arm-proposing DA algorithm, the algorithm outputs m.Next, we claim that for every agent-arm pair in the envy-set ES(m), the sample complexity isT = min{t ∈ N : 2β log(Kt)/t ≤ ∆/4} = O( β ∆ 2 log( βK ∆ 2 )).We prove this for each agent-arm pair by induction on the number of iterations of while loop of Algorithm 3. We will show that in each invocation of Algorithm 2, the number of samples for any agent-arm pair in the envy-set ES(m) is at most T . Thus, since the while loop in Algorithm 3 checks whether the sample number is bounded by T , we get the desired bound.Base case. Let arms b j and b j ′ are the first to propose to agent a i . Let T i,j and T i,j ′ be the number of samples for agent a i over arm b j and b j ′ by Algorithm 2. Without loss of generality, we assume that µ i,j > µ i,j ′ . Since both arms have not been sampled before, by Algorithm 2 the stopping condition Equation ( 6) is satisfied whenT i,j = T i,j ′ = T since μi,j -μi,j ′ ≥ -2 2β log(KT )/T + µ i,j -µ i,j ′ ≥ -2 2β log(KT )/T + ∆ ≥ 2 2β log(KT )/T ,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 3, agent a i has already sampled b j for t i,j ≤ T times. Let b j be the winner in the last round and b j ′ proposes to a i in this round. In Line 4 of Algorithm 2, agent a i samples t i,j times of arm b j ′ before sampling b j . Then if a i samples b j for T -t i,j more times and a i samples b j ′ T times, by the same computation as the base case, we have that the stopping condition Equation ( 6) is satisfied when T i,j = T i,j ′ = T . Thus, we show that the number of samples for any agent-arm pair is bounded by T .Since Algorithm 3 only samples the agent-arm pairs in the envy set ES(m), we get that the total sample complexity is|ES(m)|T = O( β(|ES(m)|) ∆ 2 log( βK ∆ 2 )). By setting the probability budget α = 4|ES(m)| K β, we have that with probability at least 1 -α, the AE arm-DA algorithm has sample complexity complexity of the order β|ES(m)|∆ 2 log( βK ∆ 2 ), where β = log(4|ES(m)|α -1 ) log(K). Therefore, it is of the order Õ( |ES(m)| ∆ 2 log(α -1 )). 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 [1962] 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 no agent is available. Therefore, we have that the worst case is |ES(m)| = N K -N + 1.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 of agents and arms such that ∀i ∈ [N ], ∀j > i, µ i,i > µ i,j , and ∀i ∈ [K], ∀j > i, a i > bi a j . If each participant of one side (agents or arms) has the same preference (also known as a masterlist ) over the other, the preference profile satisfies SPC. Clearly, a preference profile that is SPC satisfies α-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 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 to 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 it may end up matching agents to arms that are 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 agentpessimal stable match as shown in Figure 1 and Figure 3 .Answer:[Yes] Justification: We provide codes in the supplemental material. Guidelines:• The answer NA means that paper does not include experiments requiring code. 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 (e.g., preliminary or failed experiments that didn't make it into the paper).We consider a general case where preferences are given as cardinal values; note that cardinal preferences can induce (possibly weak) ordinal linear orders.We assume preferences do not contain ties for simplicity as in previous works[Liu et al., 2020, Kong andLi, 2023]. When preferences are ordinal and contain ties, stable solutions may not exist in their strong sense (see, e.g.Irving [1994],Manlove [2002]).A random variable X is d-subgaussian if its tail probability satisfies P (|X| > t) ≤ 2 exp(-t 2 2d 2 ) for all t ≥ 0.Õ denotes the upper bound that omits terms logarithmic in the input.The uniform agent-DA algorithm is ETGS algorithm inKong and Li [2023] with minor differences.Õ denotes the upper bound that omits terms logarithmic in the input. 


Decision: 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.

Reviews: review: paper_summary: paper_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.

It 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.
strength_weakness: strength_weakness: W1. No consideration of fairness aspects of the ensuing matching. 
W2. No illustration of benefit vs. solution that elicits all preferences.
questions: questions: What is benefit of the proposed methods over one that pays the cost to elicit all preferences?
limitations: limitations: Yes.
paper_summary: paper_summary: The paper studies the sample complexity of finding a stable matching under the probably approximately (PAC) framework.

In 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).

The 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.
strength_weakness: strength_weakness: 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.]

On 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.
questions: 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].
- 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.
- 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.
- 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$.
- 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).

[1] Itai Ashlagi, Yash Kanoria, and Jacob D. Leshno. 2017. Unbalanced Random Matching Markets: The Stark Effect of Competition." Journal of Political Economy.
[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).
[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).

Minor comments:
- Line 135: typo. “… leads to unique …” => “… leads to a unique …”
- 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.
- 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: Limitations are discussed in Section 7: Conclusion and Future Work. The paper is mostly of a theoretical nature.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

2. 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. 

3. Is it possible to provide lower bounds to know whether the analysis is tight? And to do better than arm elimination?

4. 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.
questions: questions: See above, in particular 1. and 3.
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2.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.
questions: questions: Please see the last part.
limitations: limitations: The authors adequately addressed the limitations.

Comments: comment: Thank you for your responses, increasing the score, and taking the time to read our responses.

1.⁠ ⁠We discuss about ties in limitation.

2.⁠ ⁠⁠As we mentioned, since our choice of utilities are similar to experiments in previous papers [Liu 2021], we did not discuss this. We can add it briefly in revision.

3.⁠ Please note in this line of bandit learning in matching markets, the true utility is given and we do not have any assumption about the utility distribution. Thus our use of envy-set (Theorem 5) exploits the structure of the input preference. Since the utilities are part of the input, we cannot discuss about the average case but we provided the best case and the worst case improvements over the uniform DA algorithms in Lemma 3. For an example of practical scenario, please see our labor market example in rebuttal.
I appreciate the very detailed response from the authors. I have taken the discussion into consideration and adjusted my evaluation accordingly to reflect my current judgment:
1. I agree that the incompatibility with indifference in preferences is, unfortunately, common to prior works in this line of literature. I invite the authors to discuss such limitation in the paper and the ideas to overcome it.
2. It seems that the authors are thoughtful with the choice of utility distribution in the evaluation. While I still don't think it is necessarily the most convincing one, the additional argument now makes it more appealing to me. I might suggest including additional discussion on the rational of such a choice, as summarized in the rebuttal comment.
3. Overall, I see the contribution from this work but personally I still think it falls short of the bar for NeurIPS. In a very short summary, I did not find the "at best infinite" argument along with the simulation convincing enough (maybe some average case notion of improvement can be more helpful?), and I still have reservations over the practical significance of the results.
Overall, I appreciate the contribution of studying the pure exploration problem in matching markets and the use of the envy-set notion to measure its complexity. However, since both the uniform sampling and arm elimination algorithms are similar to existing approaches, I am adjusting my score to 5. I encourage the authors to discuss the relationship between their sample complexity and the standard regret, as well as their algorithmic difference between arm elimination and ODA in the next version.
Yes, We agree with the reviewer that our setting is a little different from the traditional setting and we do not consider regrets in our theory. Instead, we consider sample complexity, which focuses on minimizing the amount of samples to reach a stable matching.
I think it is not the traditional stable regret definition as it does not consider the collision scenario in the multi-agent problem. When a player samples nothing, it receives 0 rewards. So the regret is the mean of the (optimal or pessimal) stable arm, instead of 0. This is the definition in all of the existing works [Liu et al. 20; Kong and Li. 2023, 2024].
Right, it is not true that sample complexity/N is regret. In fact, as we saw, sample complexity is a function of probability budget $\alpha$, and regret is a function of $T$. 
Observe that we define regrets based on the difference between the sampled arm with the player-optimal (or pessimal) stable arm. When an agent does not sample an arm, it does not incur extra regret. In your example, by our AE arm-DA algorithm, when agent $a_1$ samples all arms, other agents are not sampling so they should have 0 regret.
Thanks for your response. I wonder whether there is some misalignment between the stable regret and sample complexity. Consider the global preference example where all agents' preference rankings are $b_1>b_2>...>b_K$, and all arms' preference rankings are $a_1> a_2> ... >a_N$. In this case, the agent $a_1$ will sample all arms until it identifies $b_1$ is optimal. Then the agent $a_2$ will sample arms except for $b_1$ until it identifies $b_2$ to be optimal. The agent $a_N$ needs to wait for all of the other agents to sample arms. This part of the samples contributes not only to the regret of the agents with higher priority but also $a_N$'s own regret. However it does not contribute to the sample complexity repeatedly. So the sample complexity/N is not equal to a single agent's stable regret. Is this right?
Thank you for taking the time to read our response and seek clarification. We are glad to clarify your question.

Please note that the definition of player-pessimal stable regret is the regret for only ONE agent, while the definition of sample complexity in our paper is how many samples ALL agents need collectively to reach a stable matching. Therefore, uniform arm-DA algorithm has player pessimal stable regret depending on $K$ and sample complexity depending on $NK$; AE arm-DA algorithm has sample complexity depending on $|ES(\underline{m})|$.

We didn't do regret analysis for AE arm-DA in this paper. Note that the ordering we wrote for player-pessimal stable regret is based on the empirical observations.
Thanks for your detailed response. I am happy to increase my score. I also want to further ask how to derive an $O(K\log T/\Delta^2) $ regret for the AE-arm-DA? As its current result depends on $|ES(\underline{m})|$ which is of order $O(NK)$.
Thank you for the responses, I am happy to keep my score as is.