Abstract
In many Japanese municipalities, the demand for daycare services significantly exceeds supply, creating a social crisis known as the "waiting child" problem. Allocating these slots is a complex two-sided matching problem involving unique real-world constraints such as sibling joint preferences, existing enrollment transfers, and transferable quotas between age groups. This paper proposes a novel Constraint Programming (CP) approach to solve this NP-complete problem. By modeling these constraints comprehensively and utilizing the Google OR-Tools CP-SAT solver, our method significantly outperforms existing commercial systems, increasing the number of matched children by up to 23% while ensuring mathematical stability.
Introduction: The "Waiting Child" Crisis
Daycare allocation in Japan is not a simple lottery; it is a high-stakes administrative process where families submit preferences and centers prioritize children based on state-mandated scoring systems. Traditional matching algorithms, like the standard Gale-Shapley mechanism, are insufficient for this market due to three non-standard features:
- Transfers: Children already in a center may seek to move to a more preferred location.
- Siblings: Families often have joint preferences, such as requiring both children to be admitted to the same center or neither.
- Transferable Quotas: Centers can often reallocate capacity between age groups (e.g., using an empty 2-year-old slot for a 1-year-old).
The inclusion of sibling groups makes finding a stable matching NP-complete, presenting a significant computational challenge for local governments.
A Comprehensive Constraint Programming Model
To address these complexities, we developed a model that integrates all three non-standard features—transfers, siblings, and transferable quotas—into a single framework. Previous literature typically addressed these features in isolation, as shown in the comparison below.
We chose Constraint Programming (CP) as our primary tool. Unlike Mixed-Integer Linear Programming (MILP), CP allows for the flexible definition of logical "if-then" rules as constraints. Our algorithm follows a two-stage optimization process:
- Minimize Stability Violations: The solver first identifies the minimum number of "blocking coalitions" (instances where a family and a daycare would both prefer each other over their assigned match).
- Maximize Matches: Within the bounds of that minimum violation threshold, the solver then maximizes the total number of children assigned to daycare centers.
Experimental Results
We evaluated our CP approach using real-life datasets from three Japanese municipalities: Shibuya, Tama, and Koriyama. These datasets included between 550 and 1,589 children and 33 to 86 daycare centers.
Our results demonstrate that the CP algorithm significantly outperforms the commercial software currently used by these municipalities. In Koriyama City, the CP approach increased the number of matched children from 979 to 1,200—a 22.6% improvement. Crucially, it also reduced the number of blocking coalitions from 1,059 to zero, ensuring a stable and fair outcome.
The Impact of Indifferences
One key insight from our study is the flaw in "strict" priorities. Many municipalities use tiny fractional tie-breakers to ensure every child has a unique rank. We discovered that these artificial rankings restrict the matching process. By removing these tie-breakers and allowing "indifferences" (ties), the CP algorithm gains the flexibility to match even more children without violating fairness. While this increases the search space and running time, the solutions remain computationally feasible for practical use.
Conclusion
This work demonstrates that Constraint Programming is a powerful and accessible tool for solving complex, real-world matching problems. By moving beyond simplified theoretical models to account for siblings and transferable quotas, we can provide local governments with tools that are not only mathematically stable but also significantly more effective at placing children in daycare. Future work will focus on scaling these models for even larger metropolitan areas and exploring the full potential of transferable quota data.
Summary updated