Bandit Learning in Matching Markets with Indifference

-Algorithmic novelty

Although the ODA algorithm in [2] and AE arm-DA algorithm in [3] are also inspired by arm-guided DA, they differ fundamentally from our approach in exploration-exploitation design principles. Essentially, these two algorithms still adopt an "explore-then-exploit" strategy, explicitly dividing each step of the DA process. Only when the player completes an exploration step and identifies the optimal arm does the process move to the next step. Such an approach is still unable to handle indifferent preferences, which could lead to the algorithm getting stuck in one of the steps. Our key idea to address indifferences is to prevent players from facing the dilemma of determining when to stop exploration. In our approach, the available arms for players in each round are determined dynamically as the outcome of a multi-step DA process, allowing players to freely exploring. If the preferences among these arms differ, exploration will naturally conclude, and the regret can be bounded. Conversely, if preferences remain indifferent, exploration of these arms effectively becomes exploitation of the stable arm and contribute no additional regret.

This key idea also highlights a fundamental difference in the motivation behind our algorithm compared to previous approaches. The motivation of [2] to adopt the arm-proposing mechanism is to prevent exploration failure caused by players directly selecting arms and being rejected under substitutable preferences. While our motivation is to eliminate the need for players to actively distinguish between exploration and exploitation phases, allowing the process to adapt dynamically.

Our convergence results also set our algorithm apart from [2] and [3]. The algorithms in [2] and [3] converge to a fixed stable matching when players have strict preferences but fail to converge under indifferences. In contrast, our algorithm can guarantee stability under indifferences, with outcomes potentially switching between different stable matchings.

Additionally, our proof methodology diverges significantly from that in [2]. While [2] bounds regret by analyzing the length of each discrete step in the DA process (as in Lemma 10 of [2]), our algorithm does not partition the process into distinct steps. Instead, we focus on bounding the number of non-stable matchings by constraining the occurrence of blocking pairs (as shown in our Lemma B.2). We will incorporate this discussion in the revised version to better clarify these distinctions.

-Extension to Many-to-one setting

Thank you for your question. The centralized version of our approach can naturally be extended to the many-to-one setting with substitutable preferences, as studied in [2]. However, in the decentralized setting, players would first need to estimate a unique index for communication. The current estimation process cannot be directly applied because, under substitutability, an arm can accept multiple players or reject all of them. Moreover, players would need to learn the arms' preferences to locally execute the Subroutine-of-AE-AGS. This would require $O(K \cdot 2^N)$ time complexity as each subset of players needs to propose to each arm in the many-to-one setting. Addressing these challenges represents an interesting direction for future work.

We thank reviewer 2KcX for the valuable comments and suggestions. Please find our response below.

-Definition of stability

Thanks for pointing this out. Yes, under indifferences, [1] introduces different notions of stability including weak stability, strong stability, and super stability. Among these, strong and super stable matchings do not necessarily exist in general settings with ties. To ensure consistency with the established literature on bandit learning for matching markets, we focus on weak stability, which is the most commonly studied and applicable notion in this context. We will revise the manuscript to explicitly discuss these different notions of stability and justify our focus on weak stability more clearly.

-Definition of player-optimal stable matching

We would like to clarify that we follow the typical definition of player-optimal stable matching in previous bandit based works and define it as a stable matching in which every player is matched to their most preferred stable partner. In Example 3.1, such a player-optimal stable matching does not exist. We acknowledge that there are stable matchings that are Pareto-efficient, and we will add a footnote to explicitly distinguish between player-optimal stable matchings and Pareto-efficient matchings.

We agree that achieving Pareto-efficient stable matchings would be a stronger and more desirable objective. However, under indifferent preferences, the exploration-exploitation trade-off becomes significantly more complex, and whether a better objective can be achieved remains an open problem. We consider this an important direction for future research.

-Definition of stable regret

It is correct that the worst partner for all players may not appear in a single stable matching. As analyzed in Appendices B and C, we bound the regret by bounding the number of non-stable matchings \mathbb{E} \left[ \sum_{t=1}^T 1\left\\{\bar{A}(t) \text{ is unstable}\right\\} \right]. Consequently, our regret guarantee for individual players is also a guarantee on cumulative market instability, which can, in a sense, be interpreted as the collective stable regret of the market. We will revise the manuscript to incorporate a discussion of this collective objective, emphasizing its role in representing overall market stability.

We thank reviewer Ragn for the valuable comments and suggestions. Please find our response below.

-Regret definition

As illustrated by Example 3.1, all players cannot match with their most preferred arm in a single stable matching. So the sub-linear regret compared with the maximum reward cannot be simultaneously achieved by all players even if the algorithm converges to stable matchings. To better capture the algorithm's convergence rate toward a stable matching and to align our objective with prior works, we define regret for each player as the difference between their reward and the minimum reward across all stable matchings. As detailed in Appendices B and C, we establish an upper bound on this stable regret by bounding the cumulative number of non-stable matchings, which corresponds to cumulative market instability. Hence, our regret guarantee also provides a bound on cumulative market instability.

It is worth noting that our work is the first to address indifferences and to establish a polynomial upper bound on market instability under this more general setting. We agree that a stronger objective such as the pareto-efficient matching pointed out by reviewer 2KcX would be more desirable. However, under indifferent preferences, the exploration-exploitation trade-off becomes significantly more complex, and whether a better objective can be achieved remains an open problem. We consider this an important direction for future research.

-Performance of C-ETC

Yes, C-ETC performs well in some experimental settings. However, it is crucial to highlight that this algorithm relies on the value of $\Delta$ to determine the hyper-parameter $h$ (representing the exploration budget). In our experiments, we set $h = 3000$ by testing various options ({1000, 2000, 3000, 4000}) across all experimental settings, selecting the smallest value that ensures convergence. In practical applications, however, the value of $\Delta$ is unknown, and the learner cannot feasibly test multiple options to identify the best one. An inaccurate estimation of $h$ can severely impair the algorithm's performance. In contrast, our proposed algorithm does not rely on such hyper-parameters, making it more robust and practical.

-The key idea to deal with indifference

Existing works primarily rely on an explore-then-exploit strategy. However, under preference indifference, it becomes challenging for players to decide when to terminate exploration and begin exploitation, as they cannot discern whether two arms are truly tied or if the exploration budget is insufficient to identify their difference. The key idea of our approach is to prevent players from facing this dilemma by enabling an adaptive balance between exploration and exploitation.

To achieve this, we adopt an arm-propose approach. Players continuously explore arms that propose to them while systematically eliminating suboptimal ones. For the remaining arms, if a gap exists between them, sufficient exploration will eventually distinguish the optimal choice, and the stable regret incurred by selecting suboptimal arms is sub-linear. If no gap exists, continued exploration essentially becomes equivalent to exploiting a stable arm and contributes no additional regret. This design allows our algorithm to effectively handle preference indifference while guaranteeing polynomial stable regret.

We thank reviewer fp6v for the valuable comments and suggestions. Please find our response below.

-Player-optimal stable regret

We acknowledge that, in the absence of ties, our method may not converge to the player-optimal stable matching. However, our approach is designed to be more robust to general preference scenarios compared to existing methods. The existing optimal methods [Zhang et al. (2022), Kong & Li (2023)] completely fail in the presence of indifferences (ties) and suffer $O(T)$ regret, whereas our approach is the first to address and perform well in more general indifference setting. We agree that a stronger objective such as the pareto-efficient matching pointed out by reviewer 2KcX would be more desirable. However, under indifferent preferences, the exploration-exploitation trade-off becomes significantly more complex, and whether a better objective can be achieved through non-arm-propose mechanisms remains an open problem. We consider this an important direction for future research.

-Motivation to move the arm side proposal

Recall that existing explore-then-exploit strategies fail under indifference because players cannot determine when to stop exploration, as they lack knowledge about whether indifference exists or if their exploration is insufficient. Our motivation for adopting an arm-guided GS algorithm is to address this issue by preventing players from actively managing the exploration and exploitation process. Instead, players passively select from the arms proposing to them. When preference differences exist between arms, suboptimal arms are progressively eliminated over time, allowing exploration to terminate automatically. On the other hand, when indifferences persist, alternating among these arms effectively becomes an exploitation of the stable matching, without incurring additional regret. This approach provides a robust solution to the challenges posed by indifferences, simplifying the player’s decision-making process while maintaining stability guarantees.

We thank reviewer SXo9 for the valuable comments and suggestions. Please find our response below.

-Previous approaches dealing with indifference, comparison with Liu et al. (2020) and Basu et al. (2021)

We would like to clarify that all existing works assume that market participants have strict preferences. Despite these original assumptions, we carefully examined each existing approach and found that the methods proposed by Liu et al. (2020) and Basu et al. (2021) can be extended to handle indifferences with appropriate modifications to their proofs (details are provided in Appendix A). This is why we mark these two works as applicable under indifferences in Table 1. Verifying whether existing results hold under indifferences is also a contribution of our work, and we will make this clearer in the revised version.

While Liu et al. (2020) and Basu et al. (2021) can be extended to address indifferences, they come with significant limitations. Liu et al. (2020) requires knowledge of the preference gap as a hyperparameter, which is a strong assumption given that players' preferences are unknown. Basu et al. (2021), on the other hand, suffers from exponential regret growth of $O(2^{\Delta^{-2/\epsilon}})$. In contrast, our approach avoids the strong assumption of a known preference gap and achieves a polynomial regret guarantee, offering a more practical and efficient solution.

-Definition of stable regret and cumulative market instability, and their connection

As illustrated by Example 3.1, all players cannot match with their most preferred arm in a single stable matching. So the sub-linear regret defined compared with the maximum reward cannot be simultaneously achieved by all players even if the algorithm converges to stable matchings. To better reflect the algorithm's convergence rate toward a stable matching and align our objective with existing works, we define the regret for each player as the difference between their received reward and the least reward in a stable matching. As detailed in Appendices B and C, we upper bound this stable regret by bounding the cumulative number of non-stable matchings (i.e., cumulative market instability, \mathbb{E}\left[\sum_{t=1}^T 1\left\\{\bar{A}(t) \text{ is unstable}\right\\}\right] ): Reg_i(T) = \mathbb{E}\left[\sum_{t=1}^T (\mu_{i,m_i} -X_{i,A_i(t)}(t) ) \right] \le \mathbb{E}\left[ \sum_{t=1}^T 1\left\\{\bar{A}(t) \text{ is unstable}\right\\} \cdot \mu_{i,m_i} \right] \le \mathbb{E}\left[\sum_{t=1}^T 1\left\\{\bar{A}(t) \text{ is unstable}\right\\} \right] .

Thus, our regret guarantee also serves as an upper bound on cumulative market instability which is a much stronger objective that reflects the overall market stability. Existing works in this line also adopt cumulative market instability as comparison metrics (Liu et al. (2021); Kong et al. (2022)).

-Implication of the result, and comparison with previous works

Though existing works does not consider indifference, we can analyze their regret under indifference and compare our result with theirs. As analyzed in Line 81-89, the state-of-the-art works (Zhang et al., 2022; Kong & Li, 2023) do not converge and suffer $O(T)$ regret under indifference. While our algorithm converges and suffer polynomial regret. As summarized in Table 1, Liu et al. (2020) requires known $\Delta$ to achieve $O(K\log T/\Delta^2)$ regret. Our algorithm removes this strong assumption with only an additional $N$ term in regret. Basu et al. (2021) suffers exponential regret $O(2^{\Delta^{-2/\epsilon}})$ which can be huge since $\Delta$ and $\epsilon$ can be small. While our result is polynomial without this exponential dependence.

-Enumerating all stable matchings

The previous work [1] show that enumerating all stable matchings is #P-complete and therefore cannot be solved in polynomial time if P≠NP. Suppose there are $N$ players and $N$ arms, the time complexity to enumerate all stable matchings is $O(N^N)$. Even in the small market with size $10$, this time complexity is huge. So we only report the cumulative market unstability in experiments with varing market sizes. In experiments with varying preference gaps, we additionally report the maximum cumulative stable regret among all players in Figure 2 (c) in the revised version. Our algorithm shows consistent advantage in terms of stable regret. [1] Robert W. Irving and Paul Leather. The complexity of counting stable marriages. SIAM Journal on Computing (1986).

-Other suggestions

Thanks for your other suggestions on the paper presentation. We have increased the font size of the legend text in Figure 1 in the revised version.