Research map / Bandits and online learning / Online convex optimization and games
Stable Matching with Ties: Approximation Ratios and Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies stable matching with worker-side ties and introduces the OSS-ratio, showing a tight O(log N) approximation via distributions over internally stable matchings and an adaptive bandit algorithm (ETCO) that interpolates between strict and tied regimes.
Problem
Matching markets where workers have tied utilities over jobs, so no single stable matching maximizes every worker's utility; also learning these preferences via bandit feedback with stable regret that breaks down under ties.
Approach
Defines the OSS-ratio (worker's best stable utility over utility achieved by a random matching) and shows that duplicating each job m=O(log N) times, running worker-proposing Gale-Shapley, and taking the m induced matchings uniformly yields an internally stable distribution achieving an O(log N) OSS-ratio; combined with an explore-then-choose-oracle bandit algorithm.
Key results
- Distributions over stable matchings can incur an Omega(N) OSS-ratio (R_S >= N/2).
- A distribution over internally stable matchings achieves an O(log N) OSS-ratio, matched by an Omega(log N) lower bound over all matchings.
- ETCO matches the known Omega(N ln T / Delta^2) lower bound regime for large gaps and a trade-off lower bound of Omega(T^{1-2delta}) approximation regret shows strict vs tied regimes cannot both be optimal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow distributions over general matchings instead of restricting support to stable matchings | OSS-ratio guarantees for matching markets with ties · Matching markets with ties | OSS-ratio: R_S ≥ N/2 = Ω(N); R_M = Ω(log N); R_I = O(log N) | Helped |
| Use the offline approximation oracle to distribute over internally stable matchings | Matching markets with ties · Matching markets with ties | OSS-ratio: R_I = O(log N) | Helped |
| Set ETCO exploration length to T^(2/3)(K ln T)^(1/3) (ablation) | ETCO · Bandit matching, small gaps | α-approximation stable regret: O((K ln T)^(1/3) T^(2/3)) | Helped |
| Set ETCO exploration length to T/(2 ln T) (ablation) | ETCO · Bandit matching, gaps Δ_min = Õ(T^(-1/2)) | Approximation stable regret: Reg_i^(α − 1/ln T)(T) = O(√(KT) ln T) | Mixed |
| Require sublinear stable regret on large-gap instances | Any bandit matching algorithm · Bandit matching with ties | Approximation stable regret: Ω(T^(1 − 2δ)) | Hurt |
Surprising findings
- Stable distributions can be linearly bad for workers in the tied case, while non-stable matchings achieve logarithmic guarantees.
- Even with unlimited computation, the approximation factor in the tied bandit regime persists, a fundamental statistical limit.
Limitations
- Centralized job allocation; decentralized bandit learning left open.
- No experiments on real-world datasets.
- Approximation ratio is only logarithmic and the bandit results hold only in certain regimes (e.g., trade-off lower bound stated for N=K=4 instances).
Experimental setup
Metrics: OSS-ratio stable regret alpha-approximation regret
Baselines: Gale-Shapley with tie-breaking ETGS
Builds on: Gale-Shapley deferred acceptance weak stability stable regret in multi-player bandits (ETGS) Birkhoff-von Neumann theorem
Closest papers by meaning
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.91)
- Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.90)
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.89)
- Competing Bandits in Matching Markets via Super Stability (ICML 2025 · similarity 0.89)
- Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach (AAAI 2025 · similarity 0.89)
- Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.