Research map / Learning theory and algorithms / Submodular and game algorithms
Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach
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.
Formulates learning stable matchings with unknown preferences as learning Nash equilibria in a continuous-action stable matching game, and proposes an uncoordinated EXP algorithm achieving logarithmic regret in hierarchical markets, local exponential convergence in general markets, and a weakly-acyclic-based global learner.
Problem
Learning stable matchings in two-sided matching markets with unknown men's preferences, where men receive feedback only when matched, under decentralized and uncoordinated decision-making with collisions.
Approach
Casts the stable matching problem as a complete-information continuous-action game (stable matching game) whose pure NE are exactly stable matchings, then adapts exponential-weight (EXP3-style) online mirror descent with logit updates and importance-weighted feedback so each man learns without coordination.
Key results
- In hierarchical markets, EXP with eta_t=1/sqrt(t) and gamma_t=M log t / t achieves expected regret R(T)=Õ(n^3/c^{n+2} log T + n^2/c log^3 T).
- EXP converges locally and exponentially fast to a stable matching in general markets under suitable stepsize/mixing conditions (rate exp(-c t^{1/4}) for example choices).
- Proposed uncoordinated global learner converges to a stable matching with arbitrarily high probability by exploiting weak acyclicity of the stable matching game.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EXP without phase-dependent coordination | Learning stable matchings in hierarchical markets · Hierarchical matching markets | expected regret: \tilde{O}\Big(\frac{n^3}{c^{n+2}}\log T+\frac{n^2}{c}\log^3 T\Big) | Helped |
| Use EXP when the strategy profile is sufficiently close to a stable matching | EXP in general matching markets · General matching markets | distance to pure NE: 41 n\exp(-ct\eta^{t+1}) | Helped |
| Use the alternative algorithm based on the weakly acyclic property | Learning stable matchings in general markets · General matching markets | probability of global convergence to a stable matching: arbitrarily high probability | Helped |
| Apply EXP with the stated stepsize and mixing conditions | EXP in general matching markets · General matching markets | convergence to Nash equilibrium: 1-\delta | Helped |
| Round each man's mixed strategy to his least-preferred fractionally proposed woman | Mixed NE of the stable matching game · Markets where each woman receives at least one fractional proposal | stable matching validity | Helped |
Surprising findings
- Exponential lower bounds exist for better-response dynamics in general markets without structure, motivating restriction to hierarchical markets for regret guarantees.
Limitations
- Regret bound is exponential in the number of men n (n^{n+2} dependence on the gap constant c).
- Global convergence result for general markets is slower and relies on weak acyclicity; EXP only has local guarantees in general markets.
- Hierarchical analysis requires a known lower bound on the preference gap (addressed only partially by a UCB oracle).
Experimental setup
Metrics: expected regret convergence rate
Baselines: Deferred-Acceptance phase-coordinated decentralized algorithm for hierarchical markets
Builds on: EXP3 Deferred Acceptance Gale-Shapley stable matching UCB
Closest papers by meaning
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.91)
- Competing Bandits in Matching Markets via Super Stability (ICML 2025 · similarity 0.90)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.90)
- Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.89)
- Stable Matching with Ties: Approximation Ratios and Learning (NeurIPS 2025 · similarity 0.89)
- Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (AAAI 2025 · similarity 0.88)
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.