Stable Matching with Ties: Approximation Ratios and Learning

We thank reviewer tEhw for the valuable comments. We provide response point by point below.

• Regret Analysis regarding the Other Side of the Market

The canonical result in two-sided matching markets without ties establishes that a worker-optimal stable matching is necessarily job-pessimal, demonstrating the fundamental impossibility of simultaneously achieving optimality for both sides of the market. Consequently, a natural approach to regret minimization in this setting involves considering both worker-optimal stable regret and job-pessimal stable regret as benchmarks. Previous work [1] has investigated this scenario, establishing an $O(K \log T / \Delta^2)$ regret bound relative to these respective benchmarks. In terms of our algorithm, if there are no ties, i.e., there is a minimal gap on both sides, our results immediately generalize to unknown job preferences and would guarantee the pessimal regret also for jobs.

The introduction of ties significantly complicates the analysis, as the set of stable matchings expands substantially and loses the lattice structure present in settings with strict preferences. In particular, no single matching simultaneously achieves the benchmark utility for all agents in the market. One potential approach would be to define a Pessimal Stable Share (PSS) for jobs, analogous to our Optimal Stable Share (OSS) for workers, and investigate corresponding regret guarantees. While our work represents the first treatment of optimal stable regret in bandit learning for matching markets with ties, we follow prevailing research conventions by focusing primarily on the worker side. We regard the extension of our analysis to the job side as an important direction for future research.

• Clarification of the Paper

We thank the reviewer for the careful reading and we would incoporate the following explanations in the final version of the paper.

Q2: ``Implementing an approximation oracle guarantees sublinear $\alpha$-approximation regret''

In our proposed ETCO algorithm, $T_0$ is a hyperparameter. By setting it to an appropriate order relative to $T$, we could achieve an $\alpha$-approximation regret that is sublinear in $T$. In particular, we provide two choices of $T_0$ and the corresponding regret bounds in Corollary 1 and 2.

Q3: Clarification for line 371-372: ``We would suffer linear regret for $\Delta_{\min} \in [\tilde{\Omega}(T^{-1/2}), \tilde{O}(T^{-1/3})]$, while keeping exploring till $\tilde{O}(T)$ we can have sublinear regret for this range.''

From a statistical learning perspective, when the minimum preference gap $\Delta_{\min}$ is known to satisfies $\Delta_{\min} = \tilde{\Omega}(T^{-1/2})$, then $\tilde{O}(T)$ rounds of exploration suffice to reliably estimate worker preferences, and achieve sublinear regret under the definition in Eq.(3). However, in our setting where $\Delta_{\min}$ is unknown, the choice of exploration length $T_0$ introduces a fundamental trade-off between the two regret objectives in Eq.(3) and Eq.(4). By setting $T_0 = T^{2/3}(K \ln T)^{1/3}$, we cannot guarantee detection of instances where $\Delta_{\min}$ falls in the intermediate regime $[\tilde{\Omega}(T^{-1/2}), \tilde{O}(T^{-1/3})]$. For these cases, we must resort to the approximation oracle during exploitation. Cruicially, since the oracle's solution differs by a constant factor from the Gale-Shapley optimal, each exploitation round incurs constant regret when measured against Eq.(3), resulting in an overall linear regret.

Q4: Clarification for line 673-675: ``Given that $U^*(w) = 1$ for any $w$, the ratio $R_{\mathcal{M}}$ is equal to $\min_D \max_w \frac{1}{U_D(w)}$ for these instances, which is no less than the ratio between the number of left nodes and the number of connected right nodes.''

By substituting $U^*(w) = 1$ into $R_{\mathcal{M}}$, we get $\min_D \max_w \frac{1}{U_D(w)}$. Then, proving a lower bound on this quantity is equivalent to establishing an upper bound on $\max_D \min_w U_D(w)$. In particular, we have $\max_D \min_w U_D(w) \leq \max_D \frac{\sum_w U_D(w)}{N}$, where $N$ is the number of left nodes. Now notice that $\sum_w U_D(w)$ is the expected size of the matching under distribution $D$ (since the utility is $1$ when a worker is matched and $0$ otherwise). Since there are $K$ jobs, the size of any matching is bounded by $K$, and we have $\sum_w U_D(w) \leq K$, which results in the claim.

• Empirical Comparison of the Methods

While empirical experiments are valuable, this paper focuses on introducing a novel metric and rigorously analyzing its theoretical properties in both offline and online settings. Notably, no existing algorithms provide theoretical guarantees for our proposed framework.

Prior work has extensively studied bandit learning in matching markets without ties, but these methods fail entirely when ties are introduced, as established by theoretical results. In contrast, our algorithm not only addresses this gap but also naturally reduces to the SOTA method [2] in tie-free settings.

That said, we fully acknowledge the reviewer's point regarding the importance of empirical validation, given the broad potential applications of our framework. To highlight this, we will include a discussion of promising directions for future experimental research in the paper's concluding section.

[1] Zhang, YiRui, and Zhixuan Fang. "Decentralized two-sided bandit learning in matching market." The 40th Conference on Uncertainty in Artificial Intelligence. 2024.

[2] Kong, Fang, and Shuai Li. "Player-optimal stable regret for bandit learning in matching markets." Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2023.

We thank reviewer SsEk for the valuable comments. We provide response point by point below.

• Set of Matchings that Interpolates the OSS-ratio from $O(\log N)$ to $O(N)$

We thank the reviewer for raising this insightful question. While this topic falls outside the scope of our current paper, we agree it represents an interesting direction for future research. Although we do not yet have a definitive answer, one promising approach would be to investigate constraints on the number of unmatched workers involved in a blocking pair: with no such workers, the OSS can scale linearly with $N$, while with $N$ potential blocking workers, we recover the $O(\log N)$ bound.

• Tightness of the Upper Bound in Theorem 7

Our upper bound in Theorem 7 matches the lower bound established by [1] in terms of both $T$ and $\Delta_{\min}$ when the minimum preference gap $\Delta_{\min}$ is sufficiently large.

For preference profiles that may contain (statistical) ties, by setting the exploration length $T_0$ as $\tilde{O}(T^{2/3})$, our upper bound achieves the same dependence on $T$ as the lower bound in Theorem 8, though with $\Delta_{rel}$ replacing $\Delta_{\min}$. We emphasize that this represents a computational limitation rather than a fundamental statistical gap. As noted in footnote 2 in page 8, given either unlimited computational resources or an oracle capable of determining whether the uncertainty set contains a unique worker-optimal stable matching, we could close this gap and provide an upper bound that depends on $\Delta_{rel}$ instead of$\Delta_{\min}$.

[1] Sankararaman, Abishek, Soumya Basu, and Karthik Abinav Sankararaman. "Dominate or delete: Decentralized competing bandits in serial dictatorship." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

We thank reviewer yExD for the valuable comments. We provide our response point by point below.

• Leaving Top-workers Unassigned with Probability $1 - 1/\log N$

In the proposed algorithm, each worker is indeed assigned a job with a probability of $1 / \log N$. This is sufficient to prove a tight upper bound in Theorem 3 which matches the lower bound derived Theorem 2. However, some matchings in the support only assign a subset of jobs. In practice, if some job $a$ is not allocated in a matching $\tilde{\mu}_j$, but is allocated to worker $w$ in $\tilde{\mu}_i$, we can give $a$ to $w$ (which are mostly top workers) in $\tilde{\mu}_j$ without breaking internal stability of $\tilde{\mu}_j$. This post-processing is a Pareto improvement of our solution, but it does not provide any improved OSS guarantee in the worst case.

• Optimize for the OSS over Internally Stable Matchings

By interpreting the distribution over matchings as a rotating schedule, where each matching in the support represents a daily assignment, we can view the restriction to internally stable matchings as imposing constraints on this schedule. Specifically, it ensures that no worker experiences justified envy toward another worker present on the same day. Theorem 1 demonstrates that no meaningful guarantees can be established when considering justified envy of the workers who are not present, which naturally motivates us to explore the set of internally stable matching.

Further, we would like to emphasize that the distribution computed by Algorithm 1 is not only "ex-post" internally stable, it is also "ex-ante" (externally) stable, in the sense that no worker has justified envy towards any other worker's (randomized) allocation. This is related to the notion of fractional stable matching discussed in Appendix A. We will add this as a comment in the final version, but we believe that formally defining ``ex-ante'' stability would distract the reader.

• Applicability of OSS in the Bandit Learning Setting

The bandit learning setting provides a natural and strong motivation for defining the OSS-ratio. Recent years have witnessed a surge of research on bandit learning in matching markets, where the goal is to minimize worker-optimal stable regret as defined in Eq.(3), using OSS as the benchmark. However, existing regret bounds universally scale as $1/\Delta^2$, where $\Delta$ represents the minimum utility preference gap across all worker-job pairs. This reveals a fundamental limitation: current methods fail completely when statistical ties exist ($\Delta = O(1/\sqrt{T})$).

To address this challenge, we must refine the regret definition and identify a tractable benchmark. Drawing inspiration from approximation regret in combinatorial bandits, we propose using an $\alpha$-approximation of the OSS as our benchmark, where $\alpha$ corresponds precisely to the reciprocal of the OSS-ratio from the offline setting. Our approach first solves the offline problem, yielding an algorithm that serves as an offline oracle for bandit learning. This innovation enables meaningful regret guarantees even with potential statistical ties. Notably, by leveraging the OSS-ratio, we establish the first problem-independent regret upper bound -- a result previously believed impossible, as demonstrated by [1].

[1] Liu, Lydia T., Horia Mania, and Michael Jordan. "Competing bandits in matching markets." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

We thank reviewer wBg1 for the valuable comments. We provide our response point by point below.

• Distributions over Matchings

In stable matching without ties, a worker-optimal stable matching -- one that simultaneously maximizes the utility for all workers -- always exists. However, when preferences admit ties, this strong property no longer holds, as different workers may favor different stable matchings. To balance competing interests, we consider distributions over matchings. In our setting, where a company allocates jobs to workers, the allocation could be done in a time-sharing scenario. For example, if workers are employed five days a week, the company could implement a rotating schedule: each day's assignment corresponds to an integral matching. This could be defined as a distribution over matchings where the support contains the daily assignments and the workers' satisfiability could be measured by the matching utility in expectation. Importantly, randomizing over matchings has been a standard approach in fair resource allocation [1-3], where previous work have shown the equivalence with fractional matchings, thanks to Birkhoff-von Neumann (BvN) theorem [4, 5].

Due to space constraints, we initially deferred the above explanations to Appendix A. We thank the reviewer for their valuable feedback -- we agree that integrating this content into the main text will enhance the clarity of our conceptual contribution, and we intend to use the extra page to give more details on it.

• Techniques Involved and Developed

The upper bound on the approximation ratio is the first key technical contribution of our paper. We establish this result via three main steps: 1) Introducing a novel component -- the duplication index -- into the algorithm design; 2) Constructing a directed forest where edges encode conflicts between workers competing for the same job copies across different matchings; 3) Leveraging the tree structure and stability constraints to derive the upper bound inductively.

In the bandit learning setting, the primary technical challenge and key contribution lie in the lower bound proof. To establish this result, we carefully construct two instances with 4 workers and 4 jobs, where the utility matrices differ in only one critical entry that determines whether meaningful ties exist. This construction reveals how ties in one worker's preferences propagate to affect other workers' regret. Furthermore, we employ an information-theoretic argument to demonstrate that the algorithm must sample this critical entry sufficiently often to avoid incurring linear regret. To our knowledge, we are the first to provably show a tradeoff between standard regret and approximation regret in bandit settings.

To clarify our technical contributions, we will add a paragraph that highlights our proof sketches to the introduction in the final version.

• Improvement in the Writing

We will incorporate the above discussions and revise the introduction section to further clarify our motivation and contributions in the final version of the paper. Additionally, we are happy to provide further clarification on any other aspects of the paper, as detailed in our response to reviewer tEhw. If there are additional clarity issues that we did not address, we would appreciate it if you could let us know so we could also incorporate these improvements into our final version.

[1] Karp, Richard M., Umesh V. Vazirani, and Vijay V. Vazirani. "An optimal algorithm for on-line bipartite matching." Proceedings of the twenty-second annual ACM symposium on Theory of computing. 1990.

[2] Halpern, Daniel, and Nisarg Shah. "Fair and efficient resource allocation with partial information." arxiv preprint arxiv:2105.10064 (2021).

[3] Benade, Gerdus, et al. "Fair and efficient online allocations." Operations Research 72.4 (2024): 1438-1452.

[4] Birkhoff, Garrett. "Three observations on linear algebra." Univ. Nac. Tacuman, Rev. Ser. A 5 (1946): 147-151.

[5] Von Neumann, John. "A CERTAIN ZERO-SUM TWO-PERSON GAME EQUIVALENT TO THE OPTIMAL ASSIGNMENT PROBLEM¹." Contributions to the Theory of Games 24 (1950): 5.