# Stable Matching with Ties: Approximation Ratios and Learning

arXiv: https://arxiv.org/abs/2411.03270 · HTML: https://mlsanity.com/paper/2411.03270/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 61 references that are in the map.
- First posted on arXiv 5 Nov 2024.

## Builds on (most cited first, 18 of 18)

- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [Preference-Informed Fairness](https://mlsanity.com/paper/1904.01793/) (2019)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation](https://mlsanity.com/paper/2005.14122/) (2020)
- [Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem](https://mlsanity.com/paper/1905.03125/) (2019)
- [Best-of-Both-Worlds Fair-Share Allocations](https://mlsanity.com/paper/2102.04909/) (2021)
- [When Combinatorial Thompson Sampling meets Approximation Regret](https://mlsanity.com/paper/2302.11182/) (2023)
- [Two-Sided Matching Meets Fair Division](https://mlsanity.com/paper/2107.07404/) (2021)
- [On Fairness and Stability in Two-Sided Matchings](https://mlsanity.com/paper/2111.10885/) (2021)
- [Fair Division with Two-Sided Preferences](https://mlsanity.com/paper/2206.05879/) (2022)
- [Fair and Efficient Resource Allocation with Partial Information](https://mlsanity.com/paper/2105.10064/) (2021)
- [Breaking the Envy Cycle: Best-of-Both-Worlds Guarantees for Subadditive Valuations](https://mlsanity.com/paper/2304.03706/) (2023)
- [Stable Fractional Matchings](https://mlsanity.com/paper/1902.06698/) (2019)

## Built on by (most cited first, 2 of 2)

- [Competing Bandits in Matching Markets via Super Stability](https://mlsanity.com/paper/2506.15926/) (2025)
- [Adaptive Bandit Algorithms for Contextual Matching Markets](https://mlsanity.com/paper/2605.28290/) (2026)

## Abstract (arXiv)

We study matching markets with ties, where workers on one side of the market may have tied preferences over jobs, determined by their matching utilities. Unlike classical two-sided markets with strict preferences, no single stable matching exists that is utility-maximizing for all workers. To address this challenge, we introduce the Optimal Stable Share (OSS)-ratio, which measures the ratio of a worker's maximum achievable utility in any stable matching to their utility in a given matching. We prove that distributions over only stable matchings can incur linear utility losses, i.e., an Omega (N) OSS-ratio, where N is the number of workers. To overcome this, we design an algorithm that efficiently computes a distribution over (possibly non-stable) matchings, achieving an asymptotically tight O (log N) OSS-ratio. When exact utilities are unknown, our second algorithm guarantees workers a logarithmic approximation of their optimal utility under bounded instability. Finally, we extend our offline approximation results to a bandit learning setting where utilities are only observed for matched pairs. In this setting, we consider worker-optimal stable regret, design an adaptive algorithm that smoothly interpolates between markets with strict preferences and those with statistical ties, and establish a lower bound revealing the fundamental trade-off between strict and tied preference regimes.