Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning

We thank the reviewer for the comments. Please see our responses and clarifications below.

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.

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

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.

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

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.

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

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

Our 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: $\underline{R}(ODA) > \underline{R}(uni \ arm-DA) > \underline{R}(AE \ arm-DA)$.

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

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

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.

Thank you for your constructive comments. Please see the following responses to your questions.

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.

Response: 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$.

One 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})|$.

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.

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

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

Response: 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})|$. Then 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})|$?

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.

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

We thank the reviewer for the comments and suggestions. We first clarify some of the comments.

The algorithmic improvement seem marginal, as Theorem 5…

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

Line 359-360: … the vanilla DA should work fine with ties and is efficient.

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

When the problem is formulated as agents pulling arms, I find it hard to reasonable arms proposing.

Please 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. An 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.

Please find responses to specific questions below:

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

2. 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. Allowing $\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.

Other 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$).

SPC 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. Ref: Wang and Li. Optimal analysis for bandit learning in matching markets with serial dictatorship. TCS 2024

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

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

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

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.

We thank the reviewer for the interesting questions. Please find responses to specific questions below.

What is benefit of the proposed methods over one that pays the cost to elicit all preferences?

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

No consideration of fairness aspects of the ensuing matching.

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

Kato, Akiko. "Complexity of the sex-equal stable marriage problem." Japan Journal of Industrial and Applied Mathematics 10 (1993): 1-19.

Tomás Feder. "Stable networks and product graphs", PhD thesis, Stanford University, 1990.