Research map / Learning theory and algorithms / Submodular and game algorithms
Approximately Stable Matchings With Budget Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use utility-per-size greedy sequential choice in generalized DA | Budget-constrained matching with additive hospital utilities · General markets | stability approximation ratio: \frac{1}{1-\overline{s}} | Helped |
| Use transversal-matroid choice to preserve doctor strategy-proofness | Budget-constrained matching with additive hospital utilities · General markets | stability approximation ratio: \left\lceil\frac{1+\ln(|D|-1)}{1-\overline{s}}\right\rceil | Mixed |
| Use small/medium/large contract choice in proportional markets | Budget-constrained matching with proportional hospital utilities · Proportional markets | stability approximation ratio: \phi~(=\frac{1+\sqrt{5}}{2}) | Helped |
| Use increasing-size choice to preserve doctor strategy-proofness | Budget-constrained matching with proportional hospital utilities · Proportional markets | stability approximation ratio: \frac{1}{1-\overline{s}} | Mixed |
| Require strategy-proofness for doctors rather than sacrificing it | Budget-constrained matching with additive hospital utilities · General markets | stability approximation ratio: \frac{1}{1-\overline{s}} -> \left\lceil\frac{1+\ln(|D|-1)}{1-\overline{s}}\right\rceil | Hurt |
| Use proportional rather than general additive hospital utilities | Budget-constrained matching · Proportional markets | stability approximation ratio: \frac{1}{1-\overline{s}} -> \phi | Helped |
Closest papers by meaning
- Stable Matchings in Practice: A Constraint Programming Approach (AAAI 2024 · similarity 0.87)
- Stable Matching with Ties: Approximation Ratios and Learning (NeurIPS 2025 · similarity 0.86)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.85)
- Project-Fair and Truthful Mechanisms for Budget Aggregation (AAAI 2024 · similarity 0.83)
- Strategyproof Matching of Roommates and Rooms (AAAI 2025 · similarity 0.82)
- Online Budgeted Matching with General Bids (NeurIPS 2024 · similarity 0.82)
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.