# Daycare Matching in Japan: Transfers and Siblings

Zhaohong Sun1, Yoshihiro Takenami1, Daisuke Moriwaki1, Yoji Tomita1, Makoto
Yokoo 2

###### Abstract

In this paper, we study a daycare matching problem in Japan and report the
design and implementation of a new centralized algorithm, which is going to be
deployed in one municipality in the Tokyo metropolis. There are two features
that make this market different from the classical hospital-doctor matching
problem: i) some children are initially enrolled and prefer to be transferred
to other daycare centers; ii) one family may be associated with two or more
children and is allowed to submit preferences over combinations of daycare
centers. We revisit some well-studied properties including individual
rationality, non-wastefulness, as well as stability, and generalize them to
this new setting. We design an algorithm based on integer programming (IP)
that captures these properties and conduct experiments on five real-life data
sets provided by three municipalities. Experimental results show that i) our
algorithm performs at least as well as currently used methods in terms of
numbers of matched children and blocking coalition; ii) we can find a stable
outcome for all instances, although the existence of such an outcome is not
guaranteed in theory.

## Introduction

Due to a high demand for daycare services and an increasing number of mothers
in the workforce, a large number of children are placed on a waiting list each
year in Japan, especially in the metropolitan area. The shortage of daycare
facilities has become one of the most serious social issues. The Japanese
Government provides daycare centers with subsidies to relieve the financial
burden of early childhood education. Currently, kindergartens and daycare
centers are free of charge for children of age from $3$ to $5$ and fees are
deducted for children younger than $3$ years old. Although the national number
of children on the waiting list dropped dramatically to $5634$ in April $2021$
from the peak over $26000$ a few years ago, the government is still concerned
about the situation after the COVID-19 pandemic.

The allocation of children to daycare centers in Japan is not based on a
first-come, first-served basis. Families with several children first report to
their local municipality their preferences over combinations of daycare
centers and the municipality then generates a priority ordering over children
based on its own scoring system. Children from low-income households and
single-parent families, as well as those whose guardians are suffering from
diseases or disabilities, usually take precedence over others. Nearly all
slots are assigned at the beginning of April each year via a centralized
algorithm that takes into consideration of both families’ preferences and
priorities over children.

The existence of siblings makes this problem resemble _hospital-doctor
matching with couples_ in which a couple of doctors participates in the job
market and submits a joint preference over pairs of hospitals (Roth 1984). Two
obvious distinctions are that some children may be initially enrolled and one
family may have more than two children. A recent work studies school choice in
Chile where both transfers and siblings are considered (Correa et al. 2022).
However, they assume families have restrictive _higher-first_ preferences
(i.e. families prioritize the assignment of their children in higher grades),
while in the Japanese daycare matching problem families can submit their
preferences over any possible combination of daycare centers.

We are actively collaborating with several municipalities and our objective is
to design transparent matching algorithms that compute desirable outcomes
efficiently. _A fundamental question is which properties are deemed suitable
and appropriate for this setting._ Stability is a standard solution concept
for two-sided matching problems and has been widely applied in practice (Roth
2008). It is often decomposed into individual rationality, non-wastefulness,
and fairness in the literature on school choice (Abdulkadiroğlu and Sönmez
2003). We carefully generalize these properties to meet the expectations of
municipalities and design a centralized algorithm to achieve them.

We summarize our contributions below:

  * •

Our first contribution is to formalize a realistic model of the daycare
matching market in Japan based on real-life data sets. To our best knowledge,
we are the first to study a two-sided matching problem in which i) children
may have their initial enrollment and ii) two or more siblings can submit a
joint preference over any possible combination of daycare centers. We compare
our model with several representative papers in Table 1 and discuss more
papers in the section on related work.

  * •

We generalize some well-studied concepts including individual rationality,
non-wastefulness, and stability by taking the initial enrollment and siblings’
joint preferences into account. We adapt these concepts based on the
requirements of municipalities; children’s welfare is considered more
important than daycares’. One subtle difference from previous definitions is
that children can make use of other siblings’ assignments when forming a
blocking coalition.

  * •

We develop and implement an algorithm based on integer programming (IP) to
capture these new properties, which will be deployed in one city in the Tokyo
metropolis111Our trial matching system is currently being tested and verified
by one municipality which is satisfied with our new algorithm.. We evaluate
the performance of our new algorithm through experiments on several real-life
data sets. Experimental results show that the outcomes returned by our
algorithm are at least as good as the ones yielded by the currently applied
methods (some of which are computed by an undisclosed and commercial software
package222https://www.fujitsu.com/global/about/resources/news/press-
releases/2018/1112-01.html). Another surprising result is that we can find a
stable outcome for all instances, although the existence of such an outcome is
not guaranteed in theory.

| transfer | siblings | general
---|---|---|---
|  | $2$ | $\geq 2$ | preferences
(Biró, Manlove, and McBride 2014) | ✗ | ✓ |  | ✓
(Manlove, McBride, and Trimble 2017) | ✗ | ✓ |  | ✓
(Hamada et al. 2017) | ✓ | ✗ |  | –
(Okumura 2019) | ✗ | ✗ |  | –
(Kamada and Kojima 2019) | ✗ | ✗ |  | –
(Dur, Morrill, and Phan 2022) | ✗ | ✓ |  | ✗
(Correa et al. 2022) | ✓ |  | ✓ | ✗
Our work | ✓ |  | ✓ | ✓

Table 1: Comparison with some existing models.

## Related Work

There exist two existing works on the Japanese daycare matching problem, one
of which focused on non-wasteful outcomes and the other one considered fair
outcomes. Okumura (2019) assumes that schools establish soft quotas for each
grade rather than hard bounds. If the soft target for some grade is not
fulfilled, then resources (e.g. room space, teachers) assigned to that grade
can be utilized by other grades. Okumura (2019) proposed a mechanism based on
the deferred acceptance that satisfies non-wastefulness, fairness with respect
to initial quotas, and fairness for children of the same grade. Kamada and
Kojima (2019) studied a matching model under general upper-bounds (i.e., any
subset of a feasible set of students remains feasible) that includes the
Japanese daycare matching market. They proposed a student-optimal fair
matching (SOFM) algorithm which is the most preferred outcome by every student
among all feasible, individually rational, and fair matching. Although
(Okumura 2019) and (Kamada and Kojima 2019) considered the same research
problem, they focus on flexible quotas and do not allow for families’
preferences and initial enrollment. (Dur, Morrill, and Phan 2022) consider a
school choice model with families where each family has at most two children.
They assume that siblings must have the same preferences over daycare centers
and siblings are not separable (otherwise they are treated as different
families). (Correa et al. 2022) studies school choice in Chile and their
setting is the most similar to ours. However, they assume that families have
restrictive _higher-first_ preferences instead of general preferences over
tuples of daycare centers.

There exists some works on daycare matching which are different from our
focus. (Kennes, Monte, and Tumennasan 2014) study a dynamic daycare matching
problem and children have individual preferences. (Veski et al. 2017) study a
daycare matching problem in Estonia and they define fairness (or equal access)
as the chance for families to be matched to their first choice daycares.
(Geitle et al. 2021) propose an integer programming approach for kindergarten
allocation in Norway and the objective of their IP models is to minimize the
sum of penalties for not assigning children to their prioritized
kindergartens. (Reischmann, Klein, and Giegerich 2021) propose and implement a
decentralized algorithm based on deferred acceptance for childcare allocation
in two German cities.

There exists a rich literature on hospital-doctor matching with couples which
bears similarities to the daycare matching problem. Even though a stable
outcome is not guaranteed to exist in theory, Kojima, Pathak, and Roth (2013)
showed that there is a high probability that a stable matching may exist in a
large market if the proportion of couples is relatively small. Biró, Manlove,
and McBride (2014); Manlove, McBride, and Trimble (2017) focused on the
computational complexity of computing a stable outcome in the setting of
couples (which is NP-hard to decide whether one exists) and proposed
algorithms based on Integer Programming and Constraint Programming. Nguyen and
Vohra (2018) discussed near-feasible stable matchings for couples under the
assumption that hospital capacity is soft.

Hamada et al. (2017) considered a school choice problem in which each school
is subject to a minimum quota and each student has an initial school and
prefers to transfer. They showed that no strategy-proof mechanism exists that
is both efficient and fair when minimum quotas exist. They proposed one
mechanism called Top Trading Cycles among Representatives with Supplementary
Seats (TTCR-SS) which is Pareto efficient and another mechanism called
Priority List-based Deferred Acceptance with Minimum Quotas (PLDA-MQ) which is
priority list-based stable. Suzuki, Tamura, and Yokoo (2018) also considered
the school choice problem with initial schools where distributional
constraints can be represented as an M-convex set. They proposed a mechanism
based on the Top Trading Cycles mechanism, which satisfies strategy-proofness,
feasibility, Pareto efficiency, and individual rationality. However, both
works did not consider siblings’ joint preferences over schools.

The problem of refugee reallocation also deals with families instead of
individuals. In the model of refugee reallocation, each refugee family
consists of several members and imposes a multi-dimensional requirement of
services including housing, medical services, education, employment, and so on
(Delacrétaz, Kominers, and Teytelboym 2016; Aziz et al. 2018). A host locality
can accommodate a refugee family only if it meets the multi-dimensional
requirement. Each refugee family has a strict preference ordering over host
localities and each host locality has a strict preference ordering over
refugee families. Thus members from the same refugee family are inseparable
and they have an identical preference ordering. However, this is different
from our model in which siblings from the same family can be matched in
separable daycares and they submit a joint family preference ordering over a
tuple of daycares.

## Model

In this section, we introduce the model of daycare matching in Japan based on
real-life data sets. An instance $I$ consists of a tuple
$I=(C,F,D,G,\omega,\succ_{C},\succ_{F},\succ_{D},q)$. There are a set of
children $C$, a set of families $F$, and a set of daycares $D$. Each child $c$
pertains to one family $f\in F$ and each family $f$ is associated with a set
of children $C_{f}\subseteq C$.

The set of children $C$ is partitioned into disjoint families s.t. i)
$\bigcup_{f\in F}C_{f}=C$; ii) for any two different families $f$ and
$f^{\prime}$, $C_{f}\cap C_{f^{\prime}}=\emptyset$. When $C_{f}$ consists of
one child, i.e. $C_{f}=\\{c\\}$, we say child $c$ is an _only child_ of family
$f$. When $C_{f}$ consists of several children, i.e.
$C_{f}=\\{c_{1},\ldots,c_{k}\\}$ with $k\geq 2$, we say children
$c_{1},\ldots,c_{k}$ are _siblings_ of family $f$. Each child $c$ belongs to
one of the grades $G$ and let $G(c)$ denote the grade of child $c$. Note that
siblings from the same family may belong to the same grade, e.g., twins.

The set of daycares is denoted as $D$. Let $d_{0}\in D$ denote a dummy daycare
representing the option of being unmatched for children. Some children are
initially enrolled at some daycare $d\in D\setminus\\{d_{0}\\}$ and prefer to
be transferred to a new one. Let $\omega(c)\in D$ denote the initial daycare
of child $c$. If $\omega(c)=d_{0}$, then child $c$ is not initially enrolled
(i.e. a new applicant). We generalize the notion of $\omega(c)$ to $\omega(f)$
as follows: given a family $f$ with children $C_{f}=\\{c_{1},\ldots,c_{k}\\}$,
let $\omega(f)=(\omega(c_{1}),\ldots,\omega(c_{k}))$ denote the initial
enrollment of each child from $C_{f}$.

There are two types of preference orderings collected in the centralized
matching system. Each child $c$ has a strict _individual preference ordering_
$\succ_{c}$ over daycares $D$. We say daycare $d$ is _acceptable_ to child $c$
if either it is strictly better than child $c$’s initial enrollment, i.e., $d$
$\succ_{c}$ $\omega(c)$ or it is the same as child $c$’s initial enrollment,
i.e., $d$ $=$ $\omega(c)$. Only acceptable daycares are listed in $\succ_{c}$
and the dummy daycare $d_{0}$ is omitted if child $c$ does not have initial
enrollment.

Each family $f$ with $k$ children $C_{f}=\\{c_{1},\ldots,c_{k}\\}$ where
$k\geq 2$ also has a strict _family preference ordering_ $\succ_{f}$ over a
tuple of $k$ daycare centers $D^{k}$, i.e., a joint preference ordering of
children $C_{f}$. Here a tuple of daycares $(d_{1},\ldots,d_{k})\in D^{k}$
means that for each integer $i\in\\{1,\ldots,k\\}$, the $i$-th child $c_{i}\in
C_{f}$ attends the $i$-th daycare in the tuple.

During the application phase, if one family’s preference type falls into one
of predefined categories (e.g., all children must be assigned to the same
daycare), then the family just submits its children’s individual preference
orderings and specifies its preference type. Then the system automatically
generates a family preference ordering. Otherwise, the family needs to fill
out its complete preference ordering on its own, which is common in practice.

In Japan, each municipality has its own scoring system to calculate children’s
_priority scores_. Factors depend on families’ circumstances, such as parents’
employment and health status. Siblings from the same family usually have an
identical priority score, although in some cases one sibling may be given
additional scores due to some characteristics, e.g., disability. In order to
derive a strict priority ordering over all children, some small fractions are
added for tie-breaking (based on some complex rules).

Each daycare also derives a strict priority ordering from children’s priority
scores. However, daycares may give additional points to some children. For
example, if a child has a sibling who is currently enrolled at some daycare,
then the child receives extra points for that daycare. Note that this is
different from the case in other countries where a child is given the highest
daycare priority if the child has an enrolled sibling at that daycare (Correa
et al. 2022; Dur, Morrill, and Phan 2022). Another important feature is that
if some child $c$ is initially enrolled at daycare $d$, then child $c$ has
higher daycare priority at daycare $d$ than those who are not. Each daycare
$d$ has a strict preference ordering $\succ_{d}$ over $C\cup\\{\emptyset\\}$,
where $\emptyset$ represents the option of leaving some seats vacant.

The Japanese government imposes two types of feasibility regulations: grade-
specific minimum room space for each child and grade-specific maximum teacher-
child ratios for each teacher. In the current matching system, each daycare
$d$ sets a _hard quota_ $q_{d}^{g}$ for each grade $g$ that conforms to the
two feasibility regulations in advance. Note that the target quotas are
designed for new applicants only. If some initially enrolled child transfers
to a new daycare, then one additional seat becomes available.

For the rest of this paper, we just treat each grade $g$ at each daycare $d$
as an independent daycare that only admits children of grade $g$. This
simplifies our description of notation and terminology. We assume each daycare
$d\in D$ has its capacity limit $q_{d}$. We will discuss _flexible quotas_
that comply with these two regulations at the end of this paper.

An outcome $\mu$ is a matching between $C$ and $D$ s.t. i) each child $c$ is
matched to exactly one daycare $d$ (which can be $d_{0}$), i.e., $|\mu(c)|=1$,
where $\mu(c)$ denotes the daycare to which $c$ is matched, and ii) $\mu(c)=d$
if and only if $c\in\mu(d)$, where $\mu(d)$ denotes the set of children
matched to $d$. An outcome is feasible if for each daycare $d$, $|\mu(d)|\leq
q_{d}$ holds. Given outcome $\mu$ and family $f$ with children
$C_{f}=\\{c_{1},\ldots,c_{k}\\}$, let $\mu(f)=(\mu(c_{1}),\ldots,\mu(c_{k}))$
denote the assignment of family $f$ in the outcome $\mu$.

## Fundamental Properties

We next introduce two fundamental properties by generalizing individual
rationality and non-wastefulness. Two municipalities confirmed that they
consider that any desirable outcome should satisfy these two new properties.
We discuss how to properly define stability in the next section.

_Individual rationality_ requires that each child $c$ is matched to some
daycare that is weakly better than child $c$’s initial enrollment. Family
rationality captures the same idea except that we consider families’
preferences instead of children’s individual preferences.

######  Definition 1 (Family Rationality).

A feasible outcome $\mu$ satisfies family rationality if for each family $f$,
either $\mu(f)$ $\succ_{f}$ $\omega(f)$ or $\mu(f)$ $=$ $\omega(f)$ holds.

For the classical matching problem without siblings, non-wastefulness requires
that if a child is not matched to a more preferred daycare, then the daycare
does not have any vacant seats. Correa et al. (2022) generalize this idea to
the setting with multiple siblings; if there exists a pair of daycare $d$ and
child $c$ from family $f$ s.t. family $f$ prefers child $c$ to be matched with
$d$, then daycare $d$ must be full. The same idea is also included in the
stability concepts for matching models with couples or siblings (Klaus and
Klijn 2005, 2007; McDermid and Manlove 2010; Dur, Morrill, and Phan 2022).

However, we argue that this generalization may not be adequate. In principle,
we believe non-wastefulness should imply that improving the assignment of a
family is not possible without hurting other children/families, i.e., the
welfare of families must be the first priority. We illustrate our concern
through Example 1.

######  Example 1.

Consider one family $f$ with two children $c_{1}$ and $c_{2}$ and two daycares
$d_{1}$ and $d_{2}$ with one seat each. Both children are acceptable to both
daycares. Family $f$ have preferences $(d_{1},d_{2})$ $\succ_{f}$
$(d_{2},d_{1})$. Outcome $\mu$ $=$ $\\{(c_{1},d_{2})$, $(c_{2},d_{1})\\}$ is
considered non-wasteful by Correa et al. (2022), but we can obtain another
outcome $\mu^{\prime}$ $=$ $\\{(c_{1},d_{1})$, $(c_{2},d_{2})\\}$ without
making any child or family worse off, and it is more preferred by family $f$.

Instead, we propose a new family non-wastefulness concept in Definition 2 that
captures the above mentioned idea.

######  Definition 2 (Family Non-wastefulness).

A feasible outcome $\mu$ satisfies family non-wastefulness, if there does not
exist another feasible outcome $\mu^{\prime}$ and one family $f$ such that i)
$\mu^{\prime}(f)\succ_{f}\mu(f)$ and ii) for each family $f^{\prime}\in
F\setminus\\{f\\}$, we have $\mu^{\prime}(f^{\prime})=\mu(f^{\prime})$.

Definition 2 states that a feasible outcome $\mu$ is family non-wasteful if we
cannot find another feasible outcome $\mu^{\prime}$ and family $f$ such that
i) children $C_{f}$ from family $f$ can be matched to a more preferred tuple
of daycares in outcome $\mu^{\prime}$ and ii) all other families
$F\setminus\\{f\\}$ are matched to the same tuple of daycares in
$\mu^{\prime}$ as in the outcome $\mu$. When each family $f$ has an only
child, Definition 2 becomes equivalent to the original concept of non-
wastefulness.

## Stability

In this section, we generalize the original concept of stability to the
setting of daycare matching with siblings and initial enrollment. Our new
stability concept implies family non-wastefulness in Definition 2 and it is
different from the ones considered in the literature on matching with couples,
as our concept allows a child to make use of her siblings’ assignment when
forming a blocking coalition.

Recall that in the classical hospital-doctor matching problem, a doctor and a
hospital form _a blocking pair_ if they are unmatched and prefer to be matched
with each other. A feasible outcome is _stable_ if it is individually rational
and there does not exist a blocking pair (Roth 1986). In our setting, a family
expresses preferences over a tuple of daycares. Thus we consider a _blocking
coalition_ between one family and a set of daycares. Briefly speaking, we say
a feasible outcome is _stable_ if there does not exist any blocking coalition.
Note that we treat family rationality as a different property. As explained in
the section on Integer Programming, we capture these properties by different
constraints separately.

We next introduce a notation $\lambda(\cdot)$ to simplify the definition of
blocking coalition and stability.

######  Definition 3 (Function $\lambda$).

Given a feasible outcome $\mu$, a daycare $d$, and two subsets of children
$C_{1},C_{2}\subseteq C$, let $\lambda(\mu,d,C_{1},C_{2})$ denote the number
of children who satisfy the following three conditions: i) they are matched to
daycare $d$ in $\mu$, ii) they are not included in $C_{1}$ and iii) they have
higher daycare priority than at least one child $c\in C_{2}$.

We use notation $\lambda(\cdot)$ in the following way: given outcome $\mu$,
daycare $d$, family $f$ and a subset of children $C^{*}\subseteq C_{f}$ who
prefer to be matched to daycare $d$, let $\lambda(\mu,d,C_{f},C^{*})$ denote
the number of children matched to daycare $d$ in $\mu$ excluding $C_{f}$ who
have higher daycare priority than at least one child $c\in C^{*}$.

######  Example 2.

Consider one daycare $d$ and a set of children
$C=\\{c_{1},c_{2},c_{3},c_{4},c_{5}\\}$ in which children $c_{2}$ and $c_{4}$
are siblings while others are only children. Suppose daycare $d$ has three
seats and a priority ordering $\succ_{d}:c_{1},c_{2},c_{3},c_{4},c_{5}$. For
matching $\mu=\\{(c_{1},d),(c_{3},d),(c_{5},d)\\}$, $C_{1}=\\{c_{2},c_{4}\\}$
and $C_{2}=\\{c_{4}\\}$, we have
$\lambda(\mu,d,C_{1},C_{2})=|\\{c_{1},c_{3}\\}|=2$. In other words, only two
children excluding $C_{1}$ are matched to daycare $d$ who have higher daycare
priority than any child in $C_{2}$ (i.e., child $c_{4}$) in the outcome $\mu$.

In order to develop a good intuition, we first confine our attention to the
real-life data sets used in our experiments which deal with a setting where
each family has at most one pair of twins and no more than three children. We
then present a general concept of stability in Definition 9.

We next illustrate four types of blocking coalition for this restrictive
setting. Here are three reasons why we break down Definition 9. Firstly, it is
easier to describe each concept and to capture each type of blocking coalition
with a corresponding IP constraint. Secondly, if we could not find an outcome
that fulfills all constraints, then we can relax them gradually until one
exists. Thirdly, the choice of constraints involves a trade-off between the
number of matched children and blocking coalitions, i.e., tolerating some form
of blocking coalitions may lead to an increase in the number of matched
children, as shown in our experimental results.

######  Definition 4 (Blocking Coalition I).

Given a feasible outcome $\mu$, family $f$ with an only child $c$ and daycare
$d$ form a blocking coalition if

  * •

i) $(d)\succ_{f}\mu(f)$;

  * •

ii) $\lambda(\mu,d,\\{c\\},\\{c\\})\leq q_{d}-1$.

Definition 4 involves a family with an only child and a daycare, corresponding
to the blocking pair in the original stability concept. Condition i) of
Definition 4 states that family $f$ prefers daycare $d$ to its assignment
$\mu(f)$. Condition ii) of Definition 4 states that child $c$ can be matched
to daycare $d$ along with all matched children who have higher priority than
child $c$, which contains two cases: either daycare $d$ has at least one
vacant seat or child $c$ can replace some matched child $c^{\prime}$ with
lower daycare priority at daycare $d$.

######  Definition 5 (Blocking Coalition II).

Given a feasible outcome $\mu$, family $f$ with two children
$C_{f}=\\{c_{1},c_{2}\\}$ of the same age (i.e., twins) and daycare $d$ form a
blocking coalition if

  * •

i) $(d,d)\succ_{f}\mu(f)$;

  * •

ii) $\lambda(\mu,d,C_{f},C_{f})\leq q_{d}-2$.

Definition 5 involves a family $f$ with a pair of twins $c_{1}$ and $c_{2}$
who apply to the same daycare $d$. Condition ii) of Definition 5 states that
daycare $d$ can admit children $C_{f}$ as well as all matched children who
have higher priority than either child $c_{1}$ or $c_{2}$.

######  Definition 6 (Blocking Coalition III).

Given a feasible outcome $\mu$, family $f$ with children
$C_{f}=\\{c_{1},\ldots,c_{k}\\}$, and a tuple of daycares
$(d_{1},\ldots,d_{k})$ with $k$ distinct daycares, family $f$ and daycares
$d_{1},\ldots,d_{k}$ form a blocking coalition if

  * •

i) $(d_{1},\ldots,d_{k})$ $\succ_{f}$ $\mu(f)$;

  * •

ii) $\forall d_{i}\in(d_{1},\ldots,d_{k})$,
$\lambda(\mu,d_{i},C_{f},\\{c_{i}\\})\leq q_{d_{i}}-1$.

Definition 6 involves a family $f$ with $k$ children $\\{c_{1}$, $\ldots$,
$c_{k}\\}$ who apply to $k$ distinct daycares $(d_{1}$, $\ldots$, $d_{k})$.
Condition ii) of Definition 6 states that for each daycare $d_{i}$ from the
tuple of daycares $(d_{1}$, $\ldots$, $d_{k})$, daycare $d_{i}$ can admit the
corresponding child $c_{i}$ from $C_{f}$ and all matched children (excluding
other siblings from $C_{f}$) who have higher priority than child $c_{i}$.

######  Definition 7 (Blocking Coalition IV).

Given a feasible outcome $\mu$, family $f$ with children
$C_{f}=\\{c_{1},c_{2},c_{3}\\}$ and a tuple of daycares $(d_{1},d_{1},d_{2})$
with $d_{1}\neq d_{2}$333Here we assume if a family has three children
including one pair of twins, $c_{1}$ and $c_{2}$ are twins and $c_{3}$ is
another child. , family $f$ and daycares $d_{1}$ and $d_{2}$ form a blocking
coalition if

  * •

i) $(d_{1},d_{1},d_{2})$ $\succ_{f}$ $\mu(f)$;

  * •

ii) For daycare $d_{1}$, $\lambda(\mu,d_{1},C_{f},\\{c_{1},c_{2}\\})\leq
q_{d_{1}}-2$ and for daycare $d_{2}$, $\lambda$$(\mu$, $d_{2}$, $C_{f}$,
$\\{c_{3}\\})$ $\leq$ $q_{d_{2}}$ $-$ $1$.

Definition 7 involves family $f$ with a pair of twins applying to the same
daycare $d_{1}$ and another sibling applying to a different daycare $d_{2}$.
Condition ii) of Definition 7 states that daycare $d_{1}$ can admit children
$c_{1}$ and $c_{2}$ as well as all matched children (excluding $C_{f}$) who
have higher priority than either $c_{1}$ or $c_{2}$, and daycare $d_{2}$ can
admit child $c_{3}$ along with all matched children (excluding $C_{f}$) who
have higher priority than child $c_{3}$.

We next present the general concept of stability without imposing any
limitation on the number of siblings or twins. Prior to that, we first
introduce a new concept called demand table in Definition 8.

######  Definition 8 (Demand Table).

Given a family $f$ and a tuple of daycares $(d_{1},\ldots,d_{k})$ in family
preference $\succ_{f}$, _demand table_ $T$ $=$ $\\{(d_{1}:C_{1})$, $\ldots$,
$(d_{k^{\prime}}:C_{k^{\prime}})\\}$ is given as follows: for each distinct
daycare $d$ in $(d_{1},\ldots,d_{k})$, add an entry in the form of
$(d:\\{c^{\prime}_{1},c^{\prime}_{2},\ldots\\})$ where
$c^{\prime}_{1},c^{\prime}_{2},\ldots$ are a subset of children from $C_{f}$
who apply to daycare $d$ w.r.t. the tuple $(d_{1},\ldots,d_{k})$.

######  Example 3 (Instance of Demand Table).

Consider one family $f$ with children $C_{f}=\\{c_{1},c_{2},c_{3}\\}$ and a
tuple of daycares $(d_{1},d_{1},d_{2})$ in the family preference ordering
$\succ_{f}$. The corresponding demand table $T$ is
$\\{(d_{1}:\\{c_{1},c_{2}\\}),(d_{2}:\\{c_{3}\\})\\}$.

######  Definition 9 (Stability).

Given a feasible outcome $\mu$, family $f$ with children
$C_{f}=\\{c_{1},\ldots,c_{k}\\}$ and a tuple of daycares
$(d_{1},\ldots,d_{k})$, family $f$ and all distinct daycares in the tuple
$(d_{1},\ldots,d_{k})$ form a blocking coalition if

  * •

i) $(d_{1},\ldots,d_{k})$ $\succ_{f}$ $\mu(f)$ and

  * •

ii) let $T=\\{(d_{1}:C_{1}),\ldots,(d_{k^{\prime}}:C_{k^{\prime}})\\}$ denote
the demand table w.r.t. $(d_{1},\ldots,d_{k})$, then for each pair of daycare
$d$ and $C_{d}$ in $T$, we have

$\lambda(\mu,d,C_{f},C_{d})\leq q_{d}-|C_{d}|.$

A feasible outcome $\mu$ is stable if there does not exist any blocking
coalition.

We next prove that there may not exist any stable outcome in general. However,
in our experiments using real-life data sets, we found that a stable outcome
exists for all instances.

######  Theorem 1.

The set of stable outcomes may be empty even if there are only four children
and two daycares.

###### Proof.

We prove Theorem 1 through the following counter-example. Consider three
families $f_{1}$ with two children $C_{f_{1}}=\\{c_{1},c_{2}\\}$, $f_{2}$ with
one child $C_{f_{2}}=\\{c_{3}\\}$, $f_{3}$ with one child
$C_{f_{3}}=\\{c_{4}\\}$, and two daycares $d_{1}$ with $2$ seats and $d_{2}$
with $1$ seat. The preference and priority profiles are as follows:

$\displaystyle\succ_{f_{1}}:(d_{1},d_{1}),\quad\succ_{f_{2}}:(d_{2}),(d_{1})\quad\succ_{f_{3}}:(d_{1}),(d_{2})$
$\displaystyle\succ_{d_{1}}:c_{1},c_{3},c_{2},c_{4}\qquad\succ_{d_{2}}:c_{4},c_{3}$

There are five feasible and family rational outcomes to which we cannot add
any more children without violating feasibility. We next show that none of
them satisfies stability.

  * •

For outcome $\mu_{1}=\\{(c_{1},d_{1}),(c_{2},d_{1}),(c_{3},d_{2})\\}$, family
$f_{3}$ can form a blocking coalition with daycare $d_{2}$, as
$\lambda(\mu_{1},d_{2},\\{c_{4}\\},\\{c_{4}\\})=0\leq q_{d_{2}}-1$. In other
words, no child matched to daycare $d_{2}$ in $\mu_{1}$ has a higher daycare
priority than child $c_{4}$.

  * •

For outcome $\mu_{2}=\\{(c_{1},d_{1}),(c_{2},d_{1}),(c_{4},d_{2})\\}$, family
$f_{2}$ can form a blocking coalition with daycare $d_{1}$, as
$\lambda(\mu_{2},d_{1},\\{c_{3}\\},\\{c_{3}\\})=1\leq q_{d_{1}}-1$. In other
words, only one child, i.e., $c_{1}$, who is matched to daycare $d_{1}$ in
$\mu_{2}$, has a higher daycare priority than child $c_{3}$.

  * •

For outcome $\mu_{3}=\\{(c_{4},d_{1}),(c_{3},d_{2})\\}$, family $f_{1}$ can
form a blocking coalition with daycare $d_{1}$, as
$\lambda(\mu_{3},d_{1},C_{f_{1}},C_{f_{1}})=0\leq q_{d_{1}}-2$. In other
words, no child matched to daycare $d_{1}$ in $\mu_{3}$ has a higher daycare
priority than either child $c_{1}$ or $c_{2}$.

  * •

For outcome $\mu_{4}=\\{(c_{4},d_{1}),(c_{3},d_{1})\\}$, family $f_{2}$ can
form a blocking coalition with daycare $d_{2}$, as
$\lambda(\mu_{4},d_{2},\\{c_{3}\\},\\{c_{3}\\})=0\leq q_{d_{2}}-1$. In other
words, no child matched to daycare $d_{2}$ in $\mu_{4}$ has a higher daycare
priority than child $c_{3}$.

  * •

For outcome $\mu_{5}=\\{(c_{3},d_{1}),(c_{4},d_{2})\\}$, family $f_{3}$ can
form a blocking coalition with daycare $d_{1}$, as
$\lambda(\mu_{5},d_{1},\\{c_{4}\\},\\{c_{4}\\})=1\leq q_{d_{1}}-1$. In other
words, only one child, i.e., $c_{3}$, who is matched to daycare $d_{1}$ in
$\mu_{5}$, has a higher daycare priority than child $c_{4}$.

This completes the proof of Theorem 1. ∎

## Integer Programming

In this section, we present a practical algorithm based on Integer Programming
(IP) for the real-life data sets provided by three municipalities where each
family has no more than three children and at most one pair of twins.

We first introduce another representation of preference orderings derived from
family preferences used in the IP algorithm. Given family $f$ with $k$
children $C_{f}=\\{c_{1},\ldots,c_{k}\\}$ and family preference ordering
$\succ_{f}$, a _projected preference ordering_ $\succ_{f,c_{i}}$ of child
$c_{i}\in C_{f}$ consists of the $i$-th daycare in each tuple of daycares in
$\succ_{f}$. For an only child $c$, there is no difference among $\succ_{c}$,
$\succ_{f}$ and $\succ_{f,c}$. We next illustrate the relationship of
$\succ_{c},\succ_{f},\succ_{f,c}$ for child $c$ who has a sibling through
Example 4.

######  Example 4.

Consider one family $f$ with two children $C_{f}=\\{c_{1},c_{2}\\}$ and three
daycares $D=\\{d_{0},d_{1},d_{2}\\}$ (including a dummy daycare $d_{0}$).
Suppose both children $c_{1}$ and $c_{2}$ have the same individual preference
ordering $d_{1}\succ_{c}d_{2}$.

Family $f$ requires that either both children are enrolled at the same daycare
or if only one child can be matched, then higher precedence is given to child
$c_{1}$. This rules out the possibility that two children are enrolled at
different daycares. The family preference ordering $\succ_{f}$ and the
projected preference ordering $\succ_{f,c}$ of each child $c$ are as follows:

$\displaystyle\succ_{f}:(d_{1},d_{1}),(d_{2},d_{2}),(d_{1},d_{0}),(d_{2},d_{0}),(d_{0},d_{1}),(d_{0},d_{2})$
$\displaystyle\succ_{f,c_{1}}:d_{1},d_{2},d_{1},d_{2},d_{0},d_{0}$
$\displaystyle\succ_{f,c_{2}}:d_{1},d_{2},d_{0},d_{0},d_{1},d_{2}$

As shown in Example 4, a given daycare $d$ may appear multiple times in the
projected preference ordering $\succ_{f,c}$ and the dummy daycare $d_{0}$
cannot be omitted in $\succ_{f,c}$ if child $c$ has another sibling.

Given a projected preference ordering $\succ_{f,c}$ of child $c$ and a
position $p\in[1,\mid\succ_{f,c}\mid]$ in the range from $1$ to the length of
child $c$’s projected preference ordering $\succ_{f,c}$, let $d(c,p)$ denote
the daycare at position $p$ in $\succ_{f,c}$ and let $P(c,d)=\\{p:d(c,p)=d\\}$
denote the set of positions corresponding to daycare $d$ in $\succ_{f,c}$.

We next introduce four types of binary variables used in the IP algorithm. For
each child $c\in C$ and each position $p\in[1,\mid\succ_{f,c}\mid]$, create a
variable $y_{c,p}$ indicating whether child $c$ is matched to the $p$-th
element in $\succ_{f,c}$ 444It is inaccurate to state that “child $c$ is
matched to the $p$-th ‘daycare’ in $\succ_{f,c}$”, as the same daycare at
position $p$ may appear multiple times in $\succ_{f,c}$..

$y_{c,p}=\begin{cases}1\quad\text{{if $c$ is matched to the $p$-th element in
$\succ_{f,c}$}}\\\ 0\quad\text{{otherwise.}}\end{cases}$ (1)

For each child $c\in C$ and each position $p\in[1,\mid\succ_{f,c}\mid]$,
create a variable $\alpha_{c,p}$ indicating whether child $c$ is matched to
the $r$-th element in $\succ_{f,c}$ with $r\leq p$ as follows:

$\alpha_{c,p}=\sum_{r=1}^{p}y_{c,r}.$ (2)

For each child $c\in C$ who has a sibling and each position
$p\in[1,\mid\succ_{f,c}\mid]$, create a variable $\beta_{c,p}$ indicating
whether child $c$ can be matched to the $p$-th element without modifying other
families’ assignment. Please note that $\beta_{c,p}=1$ if child $c$ cannot be
matched to the $p$-th element without changing other families’ assignment, and
$\beta_{c,p}=0$ otherwise. There are two cases when determining the value of
$\beta_{c,p}$. The first case is that child $c$ from family $f$ has a twin
$c_{t}$ and both children apply to the same daycare at position $p$, i.e.,
$d(c,p)=d(c_{t},p)$.

$\beta_{c,p}=\begin{cases}1\quad\text{{if $d(c,p)$ admits at least}}\\\ \ \
\quad\text{{$q_{d}-1$ children except for $C_{f}$}}\\\
0\quad\text{{otherwise.}}\end{cases}$ (3)

The second case is that child $c$ and all of her siblings apply to different
daycares at position $p$:

$\beta_{c,p}=\begin{cases}1\quad\text{{if $d(c,p)$ admits $q_{d}$ children
except for $C_{f}$}}\\\ 0\quad\text{{otherwise.}}\end{cases}$ (4)

For each child $c\in C$ who has a sibling and each position
$p\in[1,\mid\succ_{f,c}\mid]$, create a variable $\gamma_{c,p}$ indicating
whether child $c$ can coexist with all matched children who have higher
priority than either $c$ or his twin $c_{t}$ (if any). Similar to variables
$\beta$, variable $\gamma_{c,p}=1$ means that child $c$ cannot coexist with
all matched children with higher priority than either $c$ or her twin $c_{t}$
(if any), and $\gamma_{c,p}=0$ otherwise. We also consider two cases depending
on whether child $c$ has a twin $c_{t}$ who applies to the same daycare at
position $p$. The first case is that child $c$ from family $f$ has a twin
$c_{t}$ who applies to the same daycare at position $p$, i.e.
$d(c,p)=d(c_{t},p)$:

$\gamma_{c,p}=\begin{cases}1\ \ \text{{if $d(c,p)$ admits at least $q_{d}-1$
children}}\\\ \ \ \ \ \text{{with higher priority than $c$ or $c_{t}$} except
for $C_{f}$ }\\\ 0\ \ \text{{otherwise.}}\end{cases}$ (5)

The second case is that child $c$ and all of her siblings apply to different
daycares:

$\gamma_{c,p}=\begin{cases}1\ \ \text{{if $d(c,p)$ admits exactly $q_{d}$
children}}\\\ \ \ \ \ \text{{with higher priority than $c$} except for
$C_{f}$}\\\ 0\ \ \text{{otherwise.}}\end{cases}$ (6)

Recall that an outcome is feasible if i) each child $c\in C$ is matched to at
most one daycare; and ii) each daycare $d\in D$ can accommodate at most
$q_{d}$ children. We capture these two requirements through Constraints 7 and
8, respectively.

$\sum_{p=1}^{\mid\succ_{f,c}\mid}y_{c,p}\leq 1\qquad\forall c\in C$ (7)
$\sum_{c\in C}\sum_{p\in P(c,d)}y_{c,p}\leq q_{d}\qquad\forall d\in D$ (8)

As we use children’s projected preferences, we need to ensure that siblings
must be matched to a tuple of daycares that are located at the same position
of each child’s projected preference ordering. That is, for each family $f$
with children $C_{f}=\\{c_{1},...,c_{k}\\}$, for each position
$p\in[1,\mid\succ_{f,c}\mid]$,

$y_{c_{1},p}=...=y_{c_{k},p}.$ (9)

Family rationality is guaranteed by Constraint 10 combined with Constraints 9.
For each child $c\in C$ with $\omega(c)=d\neq d_{0}$, we have

$\sum_{p=1}^{\mid\succ_{f,c}\mid}y_{c,p}=1.$ (10)

### Non-wastefulness

We capture non-wastefulness with the following four constraints.

Constraint 11 corresponds to the blocking coalition concept in Definition 4
which involves families with an only child. For each family $f$ with an only
child $c$ and each position $p\in[1,|\succ_{f,c}|]$, let $d$ denote the
daycare at position $p$,

$(1-\alpha_{c,p})*q_{d}\leq\sum_{c^{\prime}\in C}\sum_{p\in
P(c^{\prime},d)}y_{c^{\prime},p}$ (11)

Constraint 12 corresponds to the blocking coalition concept in Definition 5
which involves families with a pair of twins who apply to the same daycare.
For each family $f$ with twins denoted by $c_{1}$ and $c_{2}$, as well as each
position $p$ such that twins $c_{1}$ and $c_{2}$ apply to the same daycare at
position $p$, let $c^{*}$ denote either $c_{1}$ or $c_{2}$, then we have

$(1-\alpha_{c^{*},p})\leq\beta_{c^{*},p}.$ (12)

Constraint 13 corresponds to the blocking coalition concept in Definition 6
which involves families with siblings applying to all different daycares. For
each family $f$ with children $C_{f}$ and each position $p$ such that siblings
$C_{f}$ apply to all different daycares at position $p$, the following holds
for any child $c\in C_{f}$,

$(1-\alpha_{c,p})\leq\sum_{c^{\prime}\in C_{f}}\beta_{c^{\prime},p}.$ (13)

Constraint 14 corresponds to the blocking coalition concept in Definition 7
which involves families with a pair of twins applying to the same daycare and
a third sibling applying to a different daycare. For each family $f$ with
children $C_{f}=\\{c_{1},c_{2},c_{3}\\}$ and a tuple of daycares
$(d_{1},d_{1},d_{2})$ with $d_{1}\neq d_{2}$ at position $p$ in $\succ_{f}$,
let $c^{*}$ denote either $c_{1}$ or $c_{2}$, then the following holds,

$(1-\alpha_{c^{*},p})\leq\beta_{c^{*},p}+\beta_{c_{3},p}.$ (14)

### Stability

We next explain how to capture stability with the following four constraints
corresponding to four types of blocking coalitions. Constraint 15 corresponds
to the blocking coalition concept in Definition 4 which involves families with
an only child. For each family $f$ with an only child $c$ and each position
$p\in[1,\mid\succ_{f,c}\mid]$, let $d$ denote the daycare at position $p$ and
let $C^{*}\subseteq C$ denote a set of children who have higher priority than
child $c$ at daycare $d$,

$(1-\alpha_{c,p})*q_{d}\leq\sum_{c^{\prime}\in C^{*}}\sum_{p^{\prime}\in
P(c^{\prime},d)}y_{c^{\prime},p^{\prime}}.$ (15)

###### Proof.

Consider any family $f$ with an only child $c$ and any position
$p\in[1,\mid\succ_{f,c}\mid]$.

If child $c$ is matched to the $r$-th element in her projected preference
ordering $\succ_{f,c}$ with $r\leq p$, i.e., $\alpha_{c,p}=1$, then Constraint
15 is trivially satisfied and child $c$ will not form a blocking coalition
with the daycare at position $p$ as child $c$ is matched to a weakly better
element at position $r$ (violating condition i) of Definition 4).

If child $c$ is not matched to the $r$-th element in $\succ_{f,c}$ with $r\leq
p$, i.e., $\alpha_{c,p}=0$, then Constraint 15 requires that the number of
matched children with higher priorities than child $c$ at daycare $d$ reaches
daycare $d$’s capacity $q_{d}$. In that case, daycare $d$ will not form a
blocking coalition with child $c$, as daycare $d$ is full and all matched
children have higher daycare priorities than child $c$ (violating condition
ii) of Definition 4).

Thus family $f$ and daycare $d$ at position $p$ will not form a blocking
coalition. ∎

Constraint 16 corresponds to the blocking coalition concept in Definition 5
which involves families with a pair of twins who apply to the same daycare.
For each family $f$ with twins denoted by $c_{1}$ and $c_{2}$, as well as each
position $p$ such that twins $c_{1}$ and $c_{2}$ apply to the same daycare at
position $p$, let $c^{*}$ denote the child who has lower priority at daycare
$d(c^{*},p)$ between $c_{1}$ and $c_{2}$, then we have

$(1-\alpha_{c^{*},p})\leq\gamma_{c^{*},p}.$ (16)

###### Proof.

Consider any family $f$ with a pair of twins denoted by $c_{1}$ and $c_{2}$ as
well as any position $p$ such that children $c_{1}$ and $c_{2}$ apply to the
same daycare at position $p$. Let $c^{*}$ denote the child who has a lower
priority at daycare $d(c^{*},p)$ between $c_{1}$ and $c_{2}$.

If child $c^{*}$ is matched to the $r$-th element in her projected preference
ordering $\succ_{f,c^{*}}$ with $r\leq p$, i.e., $\alpha_{c^{*},p}=1$, then
Constraint 16 is trivially satisfied as $\gamma_{c^{*},p}$ could be either $0$
or $1$. Family $f$ will not form a blocking coalition with the daycare at
position $p$ as family $f$ is matched to a weakly better tuple of daycares at
position $r$ (violating condition i) of Definition 5).

If child $c^{*}$ is not matched to the $r$-th element in $\succ_{f,c^{*}}$
with $r\leq p$, i.e., $\alpha_{c^{*},p}=0$, then Constraint 16 requires that
$\gamma_{c^{*},p}=1$. By Constraint 5, $\gamma_{c^{*},p}=1$ implies that
daycare $d(c,p)$ admits at least $q_{d}-1$ children excluding $C_{f}$ who have
a higher priority than child $c^{*}$. Thus daycare $d$ will not form a
blocking coalition with family $f$, as children $C_{f}$ cannot coexist with
all matched children who have a higher daycare priority than child $c^{*}$
(violating condition ii) of Definition 5).

Thus family $f$ and daycare $d$ at position $p$ will not form a blocking
coalition. ∎

Constraint 17 corresponds to the blocking coalition concept in Definition 6
which involves families with siblings applying to all different daycares. For
each family $f$ with children $C_{f}$ and each position $p$ such that siblings
$C_{f}$ apply to all different daycares at position $p$, the following holds
for any child $c\in C_{f}$,

$(1-\alpha_{c,p})\leq\sum_{c^{\prime}\in C_{f}}\gamma_{c^{\prime},p}.$ (17)

###### Proof.

Consider any family $f$ with $k(\leq 3)$ children
$C_{f}=\\{c_{1},\ldots,c_{k}\\}$ and any position $p$ such that children
$C_{f}$ apply to $k$ distinct daycares $(d_{1},\ldots,d_{k})$ at $p$ in
$\succ_{f}$. Let $c$ denote any child from family $f$, i.e., $c\in C_{f}$.

If child $c$ is matched to the $r$-th element in $\succ_{f,c}$ with $r\leq p$,
i.e., $\alpha_{c,p}=1$, then Constraint 17 is trivially satisfied as
$\gamma_{c^{\prime},p}$ could be either $0$ or $1$ for any child
$c^{\prime}\in C_{f}$. In this case, family $f$ will not form a blocking
coalition with daycares $(d_{1},\ldots,d_{k})$ at position $p$, as family $f$
is matched to a weakly better tuple of daycares at position $r$ (violating
condition i) of Definition 5).

If child $c$ is not matched to the $r$-th element in $\succ_{f,c}$ with $r\leq
p$, i.e., $\alpha_{c,p}=0$, then Constraint 17 requires that
$\sum_{c^{\prime}\in C_{f}}\gamma_{c^{\prime},p}\geq 1$. In other words, there
exists at least one child $c^{\prime}\in C_{f}$ with
$\gamma_{c^{\prime},p}=1$. By Constraint 6, $\gamma_{c^{\prime},p}=1$ implies
that daycare $d=d(c^{\prime},p)$ admits at least $q_{d}$ children excluding
$C_{f}$ who have a higher priority than child $c^{\prime}$. Thus daycare
$d(c^{\prime},p)$ will not form a blocking coalition with family $f$, as child
$c^{\prime}$ cannot coexist with all matched children who have higher daycare
priorities than child $c^{\prime}$ (violating condition ii) of Definition 5).

Thus family $f$ and a tuple of daycares $(d_{1},\ldots,d_{k})$ at position $p$
in $\succ_{f}$ will not form a blocking coalition. ∎

Constraint 18 corresponds to the blocking coalition concept in Definition 7
which involves families with a pair of twins applying to the same daycare and
a third sibling applying to a different daycare. For each family $f$ with
children $C_{f}=\\{c_{1},c_{2},c_{3}\\}$ and a tuple of daycares
$(d_{1},d_{1},d_{2})$ with $d_{1}\neq d_{2}$ at position $p$ in $\succ_{f}$,
let $c^{*}$ denote the child who has lower priority at daycare $d_{1}$ between
$c_{1}$ and $c_{2}$, then the following holds,

$(1-\alpha_{c^{*},p})\leq\gamma_{c^{*},p}+\gamma_{c_{3},p}.$ (18)

###### Proof.

Consider any family $f$ with three children $C_{f}=\\{c_{1},c_{2},c_{3}\\}$
who apply to a tuple of daycares $(d_{1},d_{1},d_{2})$ with $d_{1}\neq d_{2}$
at any position $p$ in $\succ_{f}$. Let $c^{*}$ denote the child who has a
lower priority at daycare $d_{1}$ between $c_{1}$ and $c_{2}$.

If child $c^{*}$ is matched to the $r$-th element in her projected preference
ordering $\succ_{f,c^{*}}$ with $r\leq p$, i.e., $\alpha_{c^{*},p}=1$, then
Constraint 18 is trivially satisfied as $\gamma_{c^{*},p}$ and
$\gamma_{c_{3},p}$ could be either $0$ or $1$. Family $f$ will not form a
blocking coalition with the daycare at position $p$ as family $f$ is matched
to a weakly better tuple of daycares at position $r$ (violating condition i)
of Definition 5).

If child $c^{*}$ is not matched to the $r$-th element in $\succ_{f,c^{*}}$
with $r\leq p$, i.e., $\alpha_{c^{*},p}=0$, then Constraint 18 requires that
$\gamma_{c^{*},p}+\gamma_{c_{3},p}\geq 1$. Then either $\gamma_{c^{*},p}=1$ or
$\gamma_{c_{3},p}=1$ holds. By Constraint 5, $\gamma_{c^{*},p}=1$ implies that
daycare $d_{1}$ admits at least $q_{d_{1}}-1$ children excluding $C_{f}$ who
have a higher priority than child $c^{*}$. By Constraint 6,
$\gamma_{c_{3},p}=1$ implies that daycare $d_{2}$ admits at least $q_{d_{2}}$
children excluding $C_{f}$ who have higher priorities than child $c_{3}$. For
both cases, either daycare $d_{1}$ or daycare $d_{2}$ will not form a blocking
coalition with family $f$, as children $C_{f}$ cannot coexist with all matched
children who have higher daycare priorities than child $c^{*}$ or child
$c_{3}$ (violating condition ii) of Definition 5).

Thus family $f$ and daycares $d_{1}$ and $d_{2}$ will not form a blocking
coalition. ∎

The objective of the IP algorithm is to maximize the total number of matched
children as described in Constraint 19. Recall that a dummy daycare $d_{0}$
can be included in children’s projected preferences, so we must remove the
number of children who are matched to daycare $d_{0}$.

$\max\sum_{c\in C}\sum_{p=1}^{\mid\succ_{f,c}\mid}y_{c,p}-\sum_{c\in
C}\sum_{p^{\prime}\in P(c,d_{0})}y_{c,p^{\prime}}$ (19)

## Experiments

In this section, we evaluate the performance of our new algorithm by running
experiments on five real-life data sets provided by the following three
municipalities. Shibuya ward is one of the major commercial centers in Tokyo
with a population of more than $220,000$. Tama is a rural city located in the
west of the Tokyo Metropolis with a population of less than $150,000$.
Moriguchi is one of the satellite cities of the Osaka Metropolis with a
population of around $140,000$.

All experiments were conducted on a laptop with an Apple M1-Max processor and
32Gb of memory. Our IP model was implemented via Google OR-Tools using the
default CP-SAT solver 555https://developers.google.com/optimization. For all
five data sets, stable outcomes were computed in no more than 2 seconds. We
also run more experiments, where we restrict IP constraints; the running times
vary from a few seconds to around 40 minutes. The details of these experiments
are presented in Appendix.

We summarize the basic information of the five data sets in Table 2. We found
three common features in these data sets. Firstly, each family contains no
more than three children and at most one pair of twins. Secondly, around
$15\%$ of children have siblings and more than $7\%$ of children prefer to
transfer. Thirdly, daycares are suffering from a shortage of seats for ages
$0$ and $1$, but there is an excess of seats for ages $3$ and above. We give
more details about the imbalance of demand and supply by age in Appendix.

For Shibuya ward, the status quo outcome is calculated by the commercial
software package mentioned in Introduction. We have no access to the detailed
implementation of that algorithm and it is not clear whether it satisfies the
desirable theoretical properties discussed in this paper. For Tama city and
Moriguchi city, the status quo outcome is calculated manually and it takes
several government officials one or two weeks to determine and verify the
outcome.

We compare the outcomes yielded by IP and the status quo in Table 3 and we can
draw two conclusions from these experiments: i) our IP algorithm outperforms
the currently applied methods used by Tama and Moriguchi city and performs the
same as the commercial algorithm for Shibuya ward 666Although our IP algorithm
returned exactly the same outcome as the status quo (i.e., the commercial
software) for both Shibuya data sets, the results can be different for other
cases. For instance, Tama also purchased the same software, but the
performance was not as good as the status quo (i.e., the manual method) and
they decided not to deploy it and chose our new algorithm instead., ii) there
always exists a stable outcome for five real-life data sets. Our new algorithm
is accepted by Tama city and will be deployed in its matching system shortly.

Due to the confidentiality agreement with local municipalities, we do not have
the authorization to disclose these data sets and our codes, but we have given
full description of our IP algorithm for reproducibility purpose.

| # children in | Tama | Shibuya | Moriguchi
---|---|---|---|---
the family | 2021 | 2022 | 2021 | 2022 | 2021
# children | – | 635 | 550 | 1589 | 1372 | 915
# daycares | – | 33 | 33 | 72 | 72 | 54
# families | $1$ | 542 | 462 | 1331 | 1161 | 777
$2$ | 42 | 44 | 120 | 101 | 66
$3$ | 3 | 0 | 6 | 3 | 2
# families | 2 | 3 | 8 | 14 | 25 | 9
with twins | 3 | 3 | 0 | 4 | 3 | 1
# children | 1 | 41 | 24 | 92 | 66 | 85
who prefer | 2 | 20 | 16 | 41 | 27 | 10
to transfer | 3 | 0 | 0 | 2 | 2 | 0

Table 2: Numbers of children, daycares, and families in five data sets. The
second column corresponds to families with 1,2 or 3 children. For instance,
the bottom row calculates the number of children who prefer to transfer from
families with 1, 2, or 3 children.

| Tama-21 | Tama-22 | Shibuya-21 | Shibuya-22 | Moriguchi-21
---|---|---|---|---|---
| status quo | IP | status quo | IP | status quo | IP | status quo | IP | status quo | IP
# matched children | 558 | 560 | 464 | 464 | 1307 | 1307 | 1087 | 1087 | 669 | 680
# blocking coalition | 42 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 116 | 0
family rationality | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✗ | ✓
family non-wastefulness | ✗ | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✗ | ✓

Table 3: Comparison of outcomes for five data sets

## Future Work

We elaborate on several research questions that would be beneficial for other
theoretical models or applications.

#### Flexible Quotas

One of the main objectives of Japanese daycare matching market is to reduce
(or ideally eliminate) the number of unmatched children. A possible approach
is to establish flexible quotas instead of hard targets that comply with two
feasibility regulations imposed by the government. As shown in two recent work
(Okumura 2019; Kamada and Kojima 2019), flexible quotas could significantly
increase the number of matched children.

However, based on the feedback from the municipalities, there are two main
reasons that flexible quotas are not employed in the current system. Firstly,
daycare centers are operated independently and municipalities do not have the
authority to interfere in their management. Secondly, children of certain ages
require specialized facilities (e.g. crawl space for babies) and thus
superfluous room for higher grades cannot be utilized by children of age $0$
or $1$.

We are still interested in designing algorithms under flexible quotas, as it
may be possible to reallocate unused room space among children of certain
ages. For example, suppose age $0$ and $1$ form group $1$, age from $2$ to $5$
form group $2$ and room space is shared between each age group.

#### Fairness

Although experimental results on several real-life data sets show existence of
stable outcomes in practice, there is no theoretical guarantee that there
always exists a stable outcome in general. Thus it is worth studying how to
properly define fairness concepts that are compatible with family rationality
and family non-wastefulness (or possibly weaker concepts of non-wastefulness).

Here are several factors that need to be considered when defining fairness: i)
should a child or a family has envy towards a child, a family or a set of
families? ii) which priority ordering should we consider when giving
precedence to some children or families (daycares’ priorities, a common
ordering over children, a common ordering over families, or combinations of
these priority orderings)? iii) should we confine envy to the set of children
who have the same grade only or should we allow envy across grades? iv) when
some agent $a$ (a child or a family) has envy towards another agent $b$,
should the envy be deemed as justified only if there exists a feasible outcome
after agent $a$ replaces agent $b$? v) can we compute a fair outcome
efficiently, e.g., in polynomial-time?

#### Indifferences

Families are requested to submit strict preferences over tuples of daycare
centers. Here are two aspects in which indifferences may be superior. Firstly,
it is natural and reasonable to assume that a family is indifferent between
some options. Secondly, allowing indifferences can increase the number of
matched children in theory. The extreme case is that each family submits a
binary preference ordering over tuples of daycares (i.e. only acceptable
tuples).

The common ordering over children and daycare priorities over children are
derived from priority scores and ties occur often in the data sets. As
priorities are important in determining which children take precedence over
others, it is unclear how different choices of tie-breaking for priority
orderings affect the outcome.

#### Other Properties

Pareto optimality is a stronger concept than non-wastefulness, which requires
that there is no other outcome in which all agents are weakly better off and
at least one agent is strictly better off. As stability and Pareto optimality
are generally incompatible for two-sided matching problems (Roth 1984), we
have to give up one of them when designing algorithms. Although it is not the
main concern of this work, it is interesting to consider i) whether there
exists a Pareto optimal outcome that also satisfies some other properties; ii)
whether it promotes the welfare of children.

Strategy-proofness is an important property in mechanism design and has been
extensively studied in matching markets. Although it may be impossible to
design algorithms that achieve strategy-proofness and other desirable
properties for the daycare matching problem, we want to figure out to what
extent families are willing to manipulate their strategies (i.e. misreporting
their true preferences) in practice.

## Acknowledgement

This work is partially supported by JSPS KAKENHI Grant Number JP20H00609 and
JP21H04979.

## References

  * Abdulkadiroğlu and Sönmez (2003) Abdulkadiroğlu, A.; and Sönmez, T. 2003.  School Choice: A Mechanism Design Approach.  _American Economic Review_ , 93(3): 729–747.
  * Aziz et al. (2018) Aziz, H.; Chen, J.; Gaspers, S.; and Sun, Z. 2018.  Stability and Pareto Optimality in Refugee Allocation Matchings.  In _International Conference on Autonomous Agents and Multiagent Systems_ , 964–972.
  * Biró, Manlove, and McBride (2014) Biró, P.; Manlove, D. F.; and McBride, I. 2014.  The hospitals/residents problem with couples: Complexity and integer programming models.  In _International Symposium on Experimental Algorithms_ , 10–21. Springer.
  * Correa et al. (2022) Correa, J.; Epstein, N.; Epstein, R.; Escobar, J.; Rios, I.; Aramayo, N.; Bahamondes, B.; Bonet, C.; Castillo, M.; Cristi, A.; Epstein, B.; and Subiabre, F. 2022.  School choice in Chile.  _Operations Research_ , 70(2): 1066–1087.
  * Delacrétaz, Kominers, and Teytelboym (2016) Delacrétaz, D.; Kominers, S. D.; and Teytelboym, A. 2016.  Refugee Resettlement.
  * Dur, Morrill, and Phan (2022) Dur, U.; Morrill, T.; and Phan, W. 2022.  Family Ties: School Assignment with Siblings.  _Theoretical Economics_ , 17(1): 89–120.
  * Geitle et al. (2021) Geitle, A. H.; Johnsen, Ø. K.; Ruud, H. F. E.; Fagerholt, K.; and Julsvoll, C. A. 2021.  Kindergarten allocation in Norway: An integer programming approach.  _Journal of the Operational Research Society_ , 72(7): 1664–1673.
  * Hamada et al. (2017) Hamada, N.; Hsu, C.; Kurata, R.; Suzuki, T.; Ueda, S.; and Yokoo, M. 2017.  Strategy-proof school choice mechanisms with minimum quotas and initial endowments.  _Artificial Intelligence_ , 249: 47–71.
  * Kamada and Kojima (2019) Kamada, Y.; and Kojima, F. 2019.  Fair matching under constraints: Theory and applications.  _Review of Economic Studies_.
  * Kennes, Monte, and Tumennasan (2014) Kennes, J.; Monte, D.; and Tumennasan, N. 2014.  The day care assignment: A dynamic matching problem.  _American Economic Journal: Microeconomics_ , 6(4): 362–406.
  * Klaus and Klijn (2005) Klaus, B.; and Klijn, F. 2005.  Stable matchings and preferences of couples.  _Journal of Economic Theory_ , 121(1): 75–106.
  * Klaus and Klijn (2007) Klaus, B.; and Klijn, F. 2007.  Paths to stability for matching markets with couples.  _Games and Economic Behavior_ , 58(1): 154–171.
  * Kojima, Pathak, and Roth (2013) Kojima, F.; Pathak, P. A.; and Roth, A. E. 2013.  Matching with couples: Stability and incentives in large markets.  _The Quarterly Journal of Economics_ , 128(4): 1585–1632.
  * Manlove, McBride, and Trimble (2017) Manlove, D. F.; McBride, I.; and Trimble, J. 2017.  “Almost-stable” matchings in the Hospitals/Residents problem with Couples.  _Constraints_ , 22(1): 50–72.
  * McDermid and Manlove (2010) McDermid, E. J.; and Manlove, D. F. 2010.  Keeping partners together: algorithmic results for the hospitals/residents problem with couples.  _Journal of Combinatorial Optimization_ , 19(3): 279–303.
  * Nguyen and Vohra (2018) Nguyen, T.; and Vohra, R. 2018.  Near-feasible stable matchings with couples.  _American Economic Review_ , 108(11): 3154–69.
  * Okumura (2019) Okumura, Y. 2019.  School choice with general constraints: a market design approach for the nursery school waiting list problem in Japan.  _The Japanese Economic Review_ , 70(4): 497–516.
  * Reischmann, Klein, and Giegerich (2021) Reischmann, T.; Klein, T.; and Giegerich, S. 2021.  An iterative deferred acceptance mechanism for decentralized, fast and fair childcare assignment.  _ZEW-Centre for European Economic Research Discussion Paper_ , (21-095).
  * Roth (1984) Roth, A. E. 1984.  The evolution of the labor market for medical interns and residents: a case study in game theory.  _Journal of Political Economy_ , 92(6): 991–1016.
  * Roth (1986) Roth, A. E. 1986.  On the allocation of residents to rural hospitals: a general property of two-sided matching markets.  _Econometrica: Journal of the Econometric Society_ , 425–427.
  * Roth (2008) Roth, A. E. 2008.  Deferred acceptance algorithms: History, theory, practice, and open questions.  _International Journal of Game Theory_ , 36(3): 537–569.
  * Suzuki, Tamura, and Yokoo (2018) Suzuki, T.; Tamura, A.; and Yokoo, M. 2018.  Efficient allocation mechanism with endowments and distributional constraints.  In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_ , 50–58.
  * Veski et al. (2017) Veski, A.; Biró, P.; Pöder, K.; and Lauri, T. 2017.  Efficiency and fair access in kindergarten allocation policy design.  _The Journal of Mechanism and Institution Design_ , 2(1): 57–104.

##  Appendix A More on Experiments

We next give a detailed description of five data sets and summarize the
imbalance of demand and supply by age in Table 4.

#### Tama 2021

Tama’s data set for the year $2021$ involves $635$ children, $587$ families
and $33$ daycares. There are $42$ families with two children and $3$ out of
them have a pair of twins. Only $3$ families have three children and all of
them contain a pair of twins. There are $61$ children are initially enrolled
and $20$ out of them have siblings. The age distribution of the children is
$28.50\%$, $40.47\%$, $15.43\%$, $11.81\%$, $2.68\%$ and $1.10\%$
corresponding to ages from $0$ to $5$. For families with an only child, the
average length of family preferences is $3.3$ and the maximum length is $15$.
For families with siblings, the average length of family preferences is
$38.37$ and the maximum length is $1088$.

| age | $0$ | $1$ | $2$ | $3$ | $4$ | $5$
---|---|---|---|---|---|---|---
Tama-21 | # applicants | $181$ | $257$ | $98$ | $75$ | $17$ | $7$
# capacity | $241$ | $222$ | $123$ | $106$ | $57$ | $68$
Tama-22 | # applicants | $181$ | $219$ | $91$ | $43$ | $8$ | $8$
# capacity | $230$ | $212$ | $88$ | $83$ | $41$ | $58$
Shibuya-21 | # applicants | $569$ | $656$ | $171$ | $136$ | $37$ | $20$
# capacity | $509$ | $613$ | $239$ | $265$ | $268$ | $275$
Shibuya-22 | # applicants | $540$ | $582$ | $134$ | $67$ | $33$ | $16$
# capacity | $497$ | $586$ | $186$ | $233$ | $255$ | $306$
Moriguchi-21 | # applicants | $257$ | $354$ | $184$ | $89$ | $17$ | $14$
# capacity | $369$ | $294$ | $156$ | $66$ | $38$ | $38$

Table 4: Demand and supply by age

#### Tama 2022

Tama’s data set for the year $2022$ involves $550$ children, $506$ families
and $33$ daycares. No family is endowed with three children and $462$ families
has an only child. The remaining $44$ families have two children and contain
$8$ pairs of twins. Only $40$ children are initially enrolled and $16$ out of
them have siblings. The age distribution of the children is $32.91\%$,
$39.82\%$, $16.55\%$, $7.82\%$, $1.45\%$ and $1.45\%$ corresponding to ages
from $0$ to $5$. For families with an only child, the average length of family
preferences is $3.0$ and the maximum length is $8$. For families with
siblings, the average length of family preferences is $8.4$ and the maximum
length is $64$.

#### Shibuya 2021

Shibuya’s dataset of the year $2021$ involves $1589$ children, $1457$ families
and $72$ daycares. The number of families with two children is $120$ and $14$
of them have twins. There are $6$ families with three children and $4$ of them
contain a pair of twins. The number of children with initial enrollment is
$135$ and $43$ of them have siblings. The age distribution of the children is
$35.81\%$, $41.28\%$, $10.76\%$, $8.56\%$, $2.33\%$, $1.26\%$ corresponding to
ages from $0$ to $5$. For families with an only child, the average length of
family preferences is $4.45$ and the maximum length is $11$. For families with
siblings, the average length of family preferences is $14.95$ and the maximum
length is $120$.

#### Shibuya 2022

Shibuya’s dataset of the year $2022$ involves $1372$ children, $1265$ families
and $72$ daycares. The number of families with two children is $101$ and $25$
of them are twins. There are $3$ families with three children and all of them
contain a pair of twins. The number of children with initial enrollment is
$95$ and $29$ out of them have siblings. The age distribution of the children
is $39.36\%$, $42.42\%$, $9.77\%$, $4.88\%$, $2.40\%$, $1.17\%$ corresponding
to ages from $0$ to $5$. For families with an only child, the average length
of family preferences is $3.78$ and the maximum length is $10$. For families
with siblings, the average length of family preferences is $6.58$ and the
maximum length is $64$.

#### Moriguchi 2021

Moriguchi’s dataset of the year $2021$ involves $915$ children, $845$ families
and $54$ daycares. The number of families with two children is $66$ and $9$ of
them are twins. There are $2$ families with three children and one of them
contains a pair of twins. The number of children with initial enrollment is
$95$ and $10$ out of them have siblings. The age distribution of the children
is $28.09\%$, $38.69\%$, $20.11\%$, $9.72\%$, $1.86\%$, $1.53\%$ corresponding
to ages from $0$ to $5$. For families with an only child, the average length
of family preferences is $2.56$ and the maximum length is $5$. For families
with siblings, the average length of family preferences is $5.20$ and the
maximum length is $24$.

### Other Experimental Results

We next present more experimental results where only some of the IP
constraints are satisfied. We refer to these new algorithms as IP-X where the
difference is whether we allow blocking coalition for certain families. The
fundamental constraints include feasibility, family rationality, and family
non-wastefulness, which are captured by the IP-0 algorithm. IP-1 indicates
that there is no blocking coalition for families with one child. IP-2
indicates that there is no blocking coalition for families with one and two
children. IP-3 indicates that there is no blocking coalition for families with
one, two and three children. Note that the number of blocking coalitions may
be different, as we do not consider it in the objective function.

| status quo | IP-3 | IP-2 | IP-1 | IP-0
---|---|---|---|---|---
family rationality | ✓ | ✓ | ✓ | ✓ | ✓
family non-wastefulness | ✗ | ✓ | ✓ | ✓ | ✓
# matched children | 558 | 560 | 560 | 569 | 595
# blocking coalition | 42 | 0 | 0 | 31 | 373
# running time (s) | – | 1.86 | 1.87 | 2.78 | 49

Table 5: Outcomes for Tama 2021

| status quo | IP-3 | IP-2 | IP-1 | IP-0
---|---|---|---|---|---
family rationality | ✓ | ✓ | ✓ | ✓ | ✓
family non-wastefulness | ✗ | ✓ | ✓ | ✓ | ✓
# matched children | 464 | 464 | 464 | 469 | 509
# blocking coalition | 2 | 0 | 0 | 30 | 336
# running time (s) | – | 0.16 | 0.15 | 0.62 | 1.5

Table 6: Outcomes for Tama 2022

| status quo | IP-3 | IP-2 | IP-1 | IP-0
---|---|---|---|---|---
family rationality | ✓ | ✓ | ✓ | ✓ | ✓
family non-wastefulness | ✓ | ✓ | ✓ | ✓ | ✓
# matched children | 1307 | 1307 | 1312 | 1339 | 1464
# blocking coalition | 0 | 0 | 7 | 311 | 2481
# running time (s) | – | 1.85 | 3.43 | 2526 | 480

Table 7: Outcomes for Shibuya 2021

| status quo | IP-3 | IP-2 | IP-1 | IP-0
---|---|---|---|---|---
family rationality | ✓ | ✓ | ✓ | ✓ | ✓
family non-wastefulness | ✓ | ✓ | ✓ | ✓ | ✓
# matched children | 1087 | 1087 | 1087 | 1111 | 1206
# blocking coalition | 0 | 0 | 0 | 86 | 1530
# running time (s) | – | 0.57 | 0.58 | 58.7 | 23.8

Table 8: Outcomes for Shibuya 2022

| status quo | IP-3 | IP-2 | IP-1 | IP-0
---|---|---|---|---|---
family rationality | ✗ | ✓ | ✓ | ✓ | ✓
family non-wastefulness | ✗ | ✓ | ✓ | ✓ | ✓
# matched children | 669 | 680 | 680 | 693 | 746
# blocking coalition | 116 | 0 | 0 | 46 | 599
# running time (s) | – | 0.19 | 0.18 | 0.42 | 2.64

Table 9: Outcomes for Moriguchi 2021