Research map / Bandits and online learning / Online convex optimization and games
Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility
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 bandit learning in many-to-one matching markets, proposing AETDA (incentive-compatible, player-optimal stable regret under responsiveness) and ODA (player-pessimal stable regret under substitutability).
Problem
Learning stable matchings with unknown player preferences in many-to-one markets: prior work gives only player-pessimal regret and lacks incentive compatibility.
Approach
Integrates round-robin exploration into each step of deferred acceptance: players explore arms, and once they identify their most preferred available arm they follow it, with a detection procedure removing arms that reject them; AETDA is shown incentive compatible, and ODA runs an arm-proposing DA-style online procedure under substitutable preferences.
Key results
- AETDA achieves player-optimal stable regret O(N·min{N,K}·C·log T/Δ^2) under responsiveness and is incentive compatible.
- ODA achieves player-pessimal stable regret O(NK log T/Δ^2) under substitutable preferences, improving on the prior O(N^5K^2 log^2 T/(ε^{N^4}Δ^2)) bound in the responsiveness case.
- The paper claims AETDA is the first polynomial player-optimal guarantee in matching markets without known Δ that is also robust to deviations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ODA for the recovered responsiveness setting instead of the prior many-to-one algorithm | Many-to-one bandit matching · Responsiveness, player-pessimal stable regret | regret upper bound: O(N^5K^2 \log^2 T/(\varepsilon^{N^4}\Delta^2)) to O(NK\log T/\Delta^2) | Helped |
Surprising findings
- Without incentive compatibility, a single player that misreports can gain O(T) reward while causing linear regret for all others in the ETDA variant.
Limitations
- Requires N ≤ C (each player can be matched) and assumes players know whether p_i ∈ Ch_j(P) for ODA (later relaxed only via extra rounds).
- Player-optimal regret under general substitutable preferences remains open.
- AETDA carries an O(NC) worse regret bound than the best one-to-one result, the cost of robustness.
Experimental setup
Metrics: player-optimal stable regret player-pessimal stable regret
Baselines: ETDA prior many-to-one responsive bandit algorithm (player-pessimal) one-to-one player-optimal algorithms
Builds on: ETDA (one-to-one explore-then-DA) deferred acceptance UCB
Closest papers by meaning
- Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.93)
- Competing Bandits in Matching Markets via Super Stability (ICML 2025 · similarity 0.92)
- Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach (AAAI 2025 · similarity 0.91)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.90)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.90)
- Stable Matching with Ties: Approximation Ratios and Learning (NeurIPS 2025 · similarity 0.89)
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.