Research map / Learning theory and algorithms / Combinatorial and search optimization
Stable Matchings in Practice: A Constraint Programming 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.
Proposes a constraint-programming (CP-SAT) clearing algorithm for Japanese daycare matching with siblings, initial enrollments and transferable quotas that minimizes blocking coalitions and then maximizes matched children, evaluated on real municipal data.
Problem
Allocating children to daycare centers in Japan under stability, fairness and non-wastefulness, with couples/siblings, initial enrollments (transfers) and transferable grade quotas; existing commercial software leaves many children unmatched and yields blocking coalitions.
Approach
Model the family-level matching with siblings, transfers and transferable quotas as a CP-SAT program whose primary objective minimizes blocking coalitions (stability violations) and secondary objective maximizes matched children subject to that minimum.
Key results
- CP algorithm matches up to 23% more children than the status quo on Koriyama-22 (1200 vs 979) with zero blocking coalitions.
- On Tama-21 and Tama-22, CP yields 560 and 470 matched children with zero blocking coalitions versus 558 and 464 for the current method (which had 26 and 2 blocking coalitions).
- Allowing indifferences in daycare priorities (CP-Ind) increases matched children further, e.g., Koriyama-22 from 1200 to 1217, though Shibuya-21 took 1000s.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the current method with CP | daycare matching · Tama-21 | matched children: 558 -> 560 | Helped |
| replace the current method with CP | daycare matching · Tama-22 | matched children: 464 -> 470 | Helped |
| replace the current method with CP | daycare matching · Shibuya-21 | matched children: 1307 -> 1307 | No clear effect |
| replace the current method with CP | daycare matching · Shibuya-22 | matched children: 1087 -> 1087 | No clear effect |
| replace the current method with CP | daycare matching · Koriyama-22 | matched children: 979 -> 1200 | Helped |
| replace the current method with CP | daycare matching · Tama-21 | blocking coalitions: 26 -> 0 | Helped |
| replace the current method with CP | daycare matching · Tama-22 | blocking coalitions: 2 -> 0 | Helped |
| replace the current method with CP | daycare matching · Shibuya-21 and Shibuya-22 | blocking coalitions: 0 -> 0 | No clear effect |
| replace the current method with CP | daycare matching · Koriyama-22 | blocking coalitions: 1059 -> 0 | Helped |
| allow indifferences in daycare priorities (ablation) | CP · Tama-21 | matched children: 560 -> 571 | Helped |
| allow indifferences in daycare priorities (ablation) | CP · Tama-22 | matched children: 470 -> 478 | Helped |
| allow indifferences in daycare priorities (ablation) | CP · Shibuya-21 | matched children: 1307 -> 1335 | Helped |
Surprising findings
- Allowing a small number of blocking coalitions (e.g., 5) did not necessarily increase matched children much, while 100 did.
- The commercial status quo software produced blocking coalitions on Tama data (26 in Tama-21, 2 in Tama-22).
Limitations
- Transferable quotas could only be tested on one small dataset, so their effect is inconclusive.
- Stable outcome not guaranteed theoretically; computation time can grow significantly with indifferences or allowed blocking coalitions.
- Real data are confidential and not released.
Experimental setup
Datasets: Tama-21 Tama-22 Shibuya-21 Shibuya-22 Koriyama-22
Benchmarks: Tama-21 Tama-22 Shibuya-21 Shibuya-22 Koriyama-22
Metrics: number of matched children number of blocking coalitions solver runtime
Baselines: commercial daycare matching software (status quo) manual allocation in Tama
Builds on: stable matching with couples matching with contracts school choice
Closest papers by meaning
- Daycare Matching in Japan: Transfers and Siblings (AAAI 2023 · similarity 0.94)
- Approximately Stable Matchings With Budget Constraints (AAAI 2018 · similarity 0.87)
- Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets (AAAI 2022 · similarity 0.86)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.85)
- MATWA: A Web Toolkit for Matching Under Preferences (AAAI 2025 · similarity 0.82)
- Stable Matching with Ties: Approximation Ratios and Learning (NeurIPS 2025 · 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.