Probabilistic Analysis of Stable Matching in Large Markets with Siblings

1 Introduction

Stability is a foundational concept in preference-based matching theory [Roth and Sotomayor, 1990], with significant implications for both theoretical frameworks and practical applications [Roth, 2008]. Its importance was underscored by the awarding of the 2012 Nobel Prize in Economics. This fundamental concept is crucial for the success of various markets, including the National Resident Matching Program [Roth, 1984] and public school choice programs [Abdulkadiro˘glu and S¨onmez, 2003; Abdulkadiro˘glu et al., 2005].

Despite its significance, the challenge posed by complementarities in preferences often leads to the absence of a stable matching. A persistent issue in this context is the incorporation of couples into centralized clearing algorithms for professionals like doctors and psychologists [Roth and Peranson, 1999]. Couples typically view pairs of jobs as Nevertheless, real-life markets of substantial scale do exhibit stable matchings even in the presence of couples. For example, in the psychologists' markets, couples constituted only about 1% of all participants from 1999 to 2007 [Kojima et al., 2013]. It was demonstrated that if the proportion of couples grows sufficiently slowly compared to the number of single doctors (at a near-linear rate of nϵ with 0 < ϵ < 1 where n is the number of single doctors), then a stable matching is very likely to exist in a large market [Ashlagi et al., 2014].

In this paper, we shift our attention to daycare matching markets in Japan, where the issue of waiting children has become one of the most urgent social challenges due to the scarcity of daycare facilities [Kamada and Kojima, 2023]. The daycare matching problem is a natural extension of matching with couples, with the notable distinction that the number of siblings in each family can exceed two.

The objective of this research is to gain a more nuanced understanding of why stable matchings exist in practical daycare markets. Recently, stable matchings have been reported in these markets where optimization approaches are utilized [Sun et al., 2023; Sun et al., 2024], but the underlying reasons have not been thoroughly examined. Furthermore, theoretical guarantees established in prior research on matching with couples may not readily extend to the daycare market [Ashlagi et al., 2014], primarily due to two key factors. Firstly, a distinctive characteristic of Japanese daycare markets is the substantial proportion, approximately 20%, of children with siblings. This stands in contrast to the assumption of nearlinear growth of couples in previous research. Secondly, we consider a stronger stability concept than the previous one, tailored for daycare markets.

Our contributions can be summarized as follows:

Firstly, we propose an Extended Sorted Deferred Acceptance (ESDA) algorithm, which builds upon the existing heuristic Sorted Deferred Acceptance (SDA) algorithm [Ashlagi et al., 2014]. The modification is necessary because the original algorithm may fail to produce a matching that satisfies our stricter stability concept (Theorem 1). We further demonstrate that the ESDA algorithm yields a stable matching when it terminates successfully (Theorem 2).

Second, we conduct a probabilistic analysis to investigate the existence of stable matchings in large random daycare markets, modeled using probability distributions. A key observation is that, in practice, daycares often share similar priority structures over children. Our main result demonstrates that in such randommarkets, the probability of a stable matching existing approaches 1 as the market size becomes infinitely large (Theorem 3). To the best of our knowledge, this is the first study to provide a theoretical framework that explains the consistent presence of stable matchings in realworld daycare markets.

Third, we conduct comprehensive experiments on both real-world datasets and a diverse range of synthetic datasets. Our results demonstrate that a stable matching is highly likely to exist, and the ESDA algorithm remains highly effective, particularly in scenarios where daycare priorities exhibit significant similarity.

Due to space limit, we provide a detailed literature review in the Appendix.

2 Preliminaries

In this section, we present the framework of a daycare market, expanding upon the classical problem of hospital-doctor matching with couples. We also generalize three fundamental properties that have been extensively examined in the literature of two-sided matching markets.

2.1 Model

The daycare matching problem is represented by the tuple I = (C, F,D,Q,≻F ,≻D), where C, F and D denote sets of children, families, and daycare centers, respectively.

Each child c ∈ C belongs to a family denoted as fc ∈ F. Each family f ∈ F is associated with a subset of children, denoted as Cf ⊆ C. In cases where a family contains more than one child, e.g., Cf = (c1, c2, . . . , ck) with k > 1, these siblings are arranged in a predefined order, such as by age.

Let D represent a set of daycare centers, referred to as "daycares" for brevity. A dummy daycare denoted as d0 is included in D, signifying the possibility of a child being unmatched. Each individual daycare d establishes a quota, denoted as Qd, where the symbol Q represents all quotas.

Each family f reports a strict preference ordering ≻f , defined over tuples of daycare centers, reflecting the collective preferences of the children within Cf . The notation D(≻f , j) is used to represent the j-th tuple of daycares in ≻f , and the overall preference profile of all families is denoted as ≻F .

Each daycare d ∈ D maintains a strict priority ordering ≻d over C ∪ {∅}, encompassing both the set of children C and an empty option. A child c ∈ C is considered acceptable to daycare d if c ≻d ∅, and deemed unacceptable if ∅ ≻d c. The priority profile of all daycares is denoted as ≻D.

A matching is defined as a function µ : C ∪ D → C ∪ D such that i) ∀c ∈ C, µ(c) ∈ D, ii) ∀d ∈ D, µ(d) ⊆ C and iii) µ(c) = d if and only if c ∈ µ(d). For a given matching µ, the assignment of a child c is denoted by µ(c), and the set of children assigned to a daycare d is denoted by µ(d). For a family f with children Cf = (c1, c2, . . . , ck), the family's assignment is represented as µ(f) = (µ(c1), µ(c2), . . . , µ(ck)).

2.2 Fundamental Properties

The first property, individual rationality, stipulates that each family is matched to some tuple of daycares that are weakly better than being unmatched, and no daycare is matched with an unacceptable child. It is noteworthy that each family is considered an agent, rather than individual children.

Definition 1 (Individual Rationality). A matching µ satisfies individual rationality if two conditions hold: i) ∀f ∈ F, µ(f) ≻f (d0, d0, . . . , d0) or µ(f) = (d0, d0, . . . , d0), and ii) ∀d ∈ D, ∀c ∈ µ(d), c ≻d ∅.

Feasibility in Definition 2 necessitates that i) each child is assigned to one daycare including the dummy daycare d0, and ii) the number of children matched to each daycare d does not exceed its specific quota Qd.

Definition 2 (Feasibility). A matching µ is feasible if it satisfies the following conditions: i) ∀c ∈ C, |µ(c)| = 1, and ii) ∀d ∈ D, |µ(d)| ≤ Qd.

Stability is a well-explored solution concept within the domain of two-sided matching theory. Before delving into its definition, we introduce the concept of a choice function as outlined in Definition 3. It captures the intricate process by which daycares select children, capable of incorporating various considerations such as priority, diversity goals, and distributional constraints (see, e.g., [Hatfield and Milgrom, 2005; Aziz and Sun, 2021; Suzuki et al., 2023; Kamada and Kojima, 2023]). Following the work in [Ashlagi et al., 2014], our choice function operates through a greedy selection of children based on priority only, simplifying the representation of stability.

Definition 3 (Choice Function of a Daycare). For a given set of children C ′ ⊆ C, the choice function of daycare d, denoted as Chd : C ′ → 2C′ , selects children one by one in descending order of ≻d without exceeding quota Qd.

In this paper, we explore a slightly stronger stability concept than the original one studied in [Ashlagi et al., 2014]. It extends the idea of eliminating blocking pairs [Gale and Shapley, 1962] to address the removal of blocking coalitions between families and a selected subset of daycares.

Definition 4 (Stability). Given a feasible and individually rational matching µ, family f with children Cf = (c1, c2, . . ., ck) and the j-th tuple of daycares D(≻f , j) = (d∗1 , d∗2 , . . ., d∗k ) in ≻f , form a blocking coalition if the following two conditions hold,

1. family f prefers (d∗1 , d∗2 , . . ., d∗k ) to its current assignment µ(f), i.e., D(≻f , j) ≻f µ(f), and
2. for each distinct daycare d from (d∗1 , d∗2 , . . . , d∗k ), we have C(≻f , j, d) ⊆ Chd((µ(d) \ Cf ) ∪ C(≻f , j, d)), where C(≻f , j, d) ⊆ Cf denotes a subset of children from family f who apply to daycare d with respect to D(≻f , j).

A feasible and individually rational matching satisfies stability if no blocking coalition exists.

Consider the input to Chd(·) in Condition 2 in Definition 4. First, we calculate µ(d) \ Cf , representing the children matched to d in matching µ but not from family f . Then, we consider C(≻f , j, d). This process accounts for situations where a child c is paired with d in µ but is not included in C(≻f , j, d), indicating that c is applying to a different daycare d′ ̸= d according to D(≻f , j). Consequently, child c has the flexibility to pass his assigned seat from d to his siblings in need. Otherwise, child c would compete with his siblings for seats at d despite his intent to apply elsewhere.

2.3 Motivation of New Stability Concept

The primary reason for modifying the stability concept lies in the differing selection criteria between hospital-doctor matching and daycare allocation. In the former problem, hospitals have preferences over doctors. In contrast, daycare centers utilize priority scores to determine which child should be given higher precedence. The priority scoring system is designed to eliminate justified envy and achieve a fair outcome, treating daycare slots as resources to be allocated equitably. Additionally, it is crucial that siblings do not envy each other, especially when they are not enrolled in the same daycare. Allowing children to transfer their seats to other siblings can potentially reduce waste and increase overall welfare. We presented this new stability concept to multiple government officials from different municipalities and several renowned economists. They all agreed that the modification is more appropriate for the daycare matching setting.

On the other hand, the stability concept in [Ashlagi et al., 2014] does not take siblings' assignments into account. To distinguish it from our concept, we refer to their stability as ABH-stability, named after the authors' initials. The formal definition of ABH-stability is presented in the Appendix.

Proposition 1. Stability implies ABH-stability, but not vice versa.

We next illustrate the differences between stability in Definition 4 and ABH-stability through Example 1.

Example 1 (Comparison of Two Stability Concepts). Consider a family f with two children Cf = (c1, c2) and three daycare centers D = {d0, d1, d2}. The daycares d1 and d2 each have one available slot, while the dummy daycare d0 has unlimited capacity. The preferences of family f are (d1, d2) ≻f (d2, d0). Each daycare ranks c1 higher than c2.

The matching (d2, d0), which assigns c1 to d2 and c2 to d0, is considered ABH-stable. However, it does not satisfy our stricter stability criteria defined in Definition 4. This is because it is blocked by family f and the pair (d1, d2): child c1 could transfer their seat at d2 to c2, allowing both children to achieve a more preferred assignment.

We consider the matching (d1, d2) superior, as it assigns family f to their top choice without negatively impacting any other family. In contrast, the matching (d2, d0) results in a wasted seat at daycare d1 and leaves family f unsatisfied.

3 Extended Sorted Deferred Acceptance (ESDA)

In this section, we introduce the Extended Sorted Deferred Acceptance (ESDA) algorithm, a heuristic method demonstrated to be effective in computing stable matchings across diverse real-world and synthetic datasets. Importantly, the ESDA algorithm serves as a foundational component in our probability analysis for large randommarkets.

The ESDA algorithm extends the Sorted Deferred Acceptance (SDA) algorithm. In the following theorem, we demonstrate that the original SDA algorithm may not produce a stable matching with respect to Definition 4 when it terminates successfully. More details about the previous algorithms, including SDA and Sequential Couples (a simplified version of SDA), are provided in the Appendix.

Theorem 1. The matching returned by the original SDA algorithm may not be stable.

3.1 Description of ESDA

We next provide an informal description of ESDA, while the full description is presented in the Appendix.

The algorithm begins by computing a stable matching among families with an only child, denoted as F O , using the Deferred Acceptance algorithm. Subsequently, the algorithm sequentially processes each family from the set of families with multiple children, denoted as f ∈ F S , following a predefined order π over F S .

When a family f ∈ F S is added to the matching process, the algorithm executes the following procedures within a single iteration. First, in the Proposal step, family f proposes to a tuple of daycare centers from its preference order that has not yet been considered. Next, in the Selection step, each daycare evaluates these proposals using the choice function defined in Definition 3. If any sibling from family f is rejected, the algorithm returns to the Proposal step with the next tuple in the family's preference order. Conversely, if all siblings are accepted, family f is tentatively matched to the current tuple. This tentative assignment may displace some children from other families due to capacity constraints. Let RF denote the set of families whose children are rejected as a result of this reallocation. In the Check Restart step, if any family f ′ ∈ F S with siblings has a child rejected during this process, the algorithm attempts a new order π′ by placing f before f ′ in the sequence. If this new permutation π′ has already been attempted, the algorithm terminates and returns Unsuccess. Otherwise, the algorithm restarts the process with π′ . Subsequently, in the Stabilization step, each evicted family f ′ ∈ RF repeats the procedures starting from the Proposal step, proposing to the next feasible tuple in its preference order. Family f ′ is removed from RF once its assignment is determined, while any new families displaced during this process are added to RF. This iterative stabilization continues until RF becomes empty. Finally, in the Check Improvement step, the algorithm evaluates whether family f can improve its current assignment by allowing siblings to transfer their seats. If such an improvement is possible, the algorithm terminates and returns Unsuccess. Otherwise, it proceeds to process the next family in F S according to the predefined order π.

We provide a concise explanation of the differences between our ESDA algorithm and the original SDA algorithm. First, the choice function used by daycares to select children differs significantly. In ESDA, children can transfer their allocated seats to their siblings, a feature absent in the original SDA. Second, the ESDA algorithm rigorously examines whether any family can form a blocking coalition with a tuple of daycares that previously rejected it, particularly when the assignment of any child without siblings is modified. In contrast, the original SDA processes each tuple of daycares only once, without performing this additional check.

Example 2. Consider three families f1 with Cf1 = (c1, c2), f2 with Cf2 = (c3, c4) and f3 with Cf3 = (c5, c6). There are five daycares denoted as D = {d1, d2, d3, d4, d5}, each with one available slot. The order π is initialized as {1, 2, 3}. The preference profile of the families and the priority profile of the daycares are outlined as follows:

Iteration 1: With order π1 = {1, 2, 3}, family f1 secured a match by applying to daycares (d1, d2), followed by family f2 obtaining a match with applications to (d3, d4). However, family f3 faced rejections at (d1, d4) and (d3, d4) before successfully securing acceptance at (d5, d2), leading to the displacement of family f1. Thus we generate a new order π2 = {3, 1, 2} by inserting 3 before 1.

Iteration 2: With order π2 = {3, 1, 2}, family f3 secures a match at (d1, d4). Then family f1 applies to (d1, d2) and also secures a match, resulting in the eviction of family f3. This leads to the generation of a modified order π3 = {1, 3, 2} with 1 preceding 3.

Iteration 3: With order π3 = {1, 3, 2}, family f1 secures a match at (d1, d2). Subsequent applications by f3 result in a match at (d3, d4), but f2 remains unmatched due to rejections at (d3, d4) and (d5, d4). The algorithm terminates, returning a stable matching µ with f1 matched to (d1, d2) and f3 matched to (d3, d4), while f2 remains unmatched.

3.2 Two Types of Unsuccessful Termination

The ESDA algorithm terminates unsuccessfully in two scenarios suggesting that a stable matching may not exist, even if one indeed exists.

A Type-1 Unsuccessful Termination happens when, during the insertion of a family f ∈ F S , a child c ∈ Cf initiates a rejection chain that ends with another child c′ ∈ Cf from the same family, where all other children in the chain do not have siblings. This unsuccessful termination is further divided into two cases based on whether c = c′ holds: Type-1-a Unsuccessful Termination when c = c′ and Type-1-b Unsuccessful Termination when c ̸= c′ ∈ fc.

A Type-2 Unsuccessful Termination occurs when two families, f1 and f2 ∈ F S , satisfy the following conditions: i) f1 precedes f2 in the current order π, ii) There exists a rejection chain starting from f2 and ending with f1, where all other families in the chain have only one child, and iii) A new order π′ is generated by placing f2 before f1, and this order has been attempted and stored in the set Π, which keeps track of permutations explored during the ESDA process.

We provide examples to illustrate these two types of unsuccessful terminations in the Appendix, which are crucial when analyzing the probability of the existence of stable matchings in a large random market.

3.3 Successful Termination

We next demonstrate that ESDA always generates a stable matching if it terminates successfully.

Theorem 2. Given an instance of I, if ESDA returns a matching, then the yielded matching is stable. In addition, ESDA always terminates in a finite time.

Our proof that ESDA always generates a stable matching if it terminates successfully, relies on the following two lemmas. First, we establish that the number of matched children at each daycare does not decrease as long as no family in F S is rejected and no child passes their seat to other siblings during the execution of ESDA. Then, we prove that for a given order π over F S , if the rank of the matched child at any daycare increases, then ESDA cannot produce a matching with respect to π.

Lemma 1. For a given order π over families F S , let µi (π) denote the matching obtained during the ESDA procedure before processing the i-th family denoted as F S π(i) ∈ F S . The number of matched children at any daycare d does not decrease under matching µi+1 (π) if the following three conditions hold: i) The algorithm does not encounter any type of Unsuccessful Termination. ii) The order π remains unchanged. iii) No child from family F S π(i+1) transfers their seat to other siblings during the ESDA process.

For a given matching µ and a daycare d, let Rank(µ, d) represent the rank of the matched child with the lowest priority at daycare d, where 1 denotes the highest priority. Imagine that all vacant slots at each daycare are initially occupied by dummy children assigned the rank |C| + 1. As the ESDA algorithm progresses, these dummy children are gradually rejected and replaced by children with higher priorities, resulting in a decrease in Rank(·).

Lemma 2. Given an order π over families F S , if, during the ESDA process, Rank(µ, d) increases for any daycare d, then ESDA fails to generate a matching under the current order π over families F S .

4 RandomDaycare Market

To analyze the likelihood of a stable matching in practice, we proceed to introduce a random market where preferences and priorities are generated from probability distributions. Formally, we represent a random daycare market as ˜

Let |C| = n and |D| = m denote the number of children and daycares, respectively. Throughout this paper, we assume that m = Ω(n). To facilitate analysis, we partition the set F into two distinct groups labeled F S and F O , signifying the sets of families with and without multiple children, respectively. Correspondingly, C S and C O represent the sets of children with and without siblings, respectively. The parameter α signifies the percentage of children with siblings. Then we have |C O | = (1 - α)n and |C S | = αn. For each family f, the size of Cf is constrained by a constant K, expressed as maxf∈F |Cf | ≤K.

4.1 Preferences of Families

We adopt the approach described in [Kojima et al., 2013] to generate family preferences using a two-step process. In the first step, we independently generate preference orderings for each child based on a probability distribution P over the set of daycares D. Let P = (pd)d∈D denote a probability distribution, where pd represents the probability of selecting daycare d. For each child c, we initialize an empty list, then independently select a daycare d from P and add it to the list if it is not already included. This process is repeated until the list reaches a maximum length L, which is typically a small constant in practice [Sun et al., 2023].

We adhere to the assumption that the distribution P satisfies a uniformly bounded condition, as assumed in the random market in [Kojima et al., 2013] and [Ashlagi et al., 2014].

Definition 5 (Uniformly Bounded). For all d, d′ ∈ D, the ratio of probabilities pd/pd′ falls within the interval [1/σ, σ] with a constant σ ≥ 1.

Lemma 3. Under the uniformly bounded condition, the probability pd of selecting any daycare d is limited by σ/m where m denotes the total number of daycares.

In the second step, we generate all possible combinations of the individual preferences of the children within each family. From these combinations, we uniformly at random select a subset with a specified length limit, without imposing additional restrictions.

4.2 Priorities of Daycares

A notable departure from previous work [Kojima et al., 2013; Ashlagi et al., 2014] is our adoption of the Mallows model [Mallows, 1957] to generate daycare priority orderings over children. The Mallows model, denoted as D≻0,ϕ, begins with a reference ordering ≻0. New orderings are then probabilistically generated based on this reference, with the degree of deviation controlled by a dispersion parameter ϕ.

Through active collaborations with multiple Japanese municipalities, we have observed that daycare centers often share similar priority structures for children. In practice, municipalities typically use a complex scoring system to assign a unique priority score to each child, establishing a strict priority order. This order is then applied and slightly adjusted by each daycare based on their individual policies (e.g., prioritizing siblings who are already enrolled). The Mallows model is particularly well-suited for replicating these priority orderings, as it allows for controlled variations around a reference ranking. Additionally, this model is widely recognized for its flexibility and has been extensively used for preference generation across various domains [Lu and Boutilier, 2011; Brilliantova and Hosseini, 2022].

Let S denote the set of all orderings over C.

Definition 6 (Kendall-tau Distance). For a pair of orderings ≻ and ≻′ in S, the Kendall-tau distance, denoted by inv(≻,≻′ ), is a metric that counts the number of pairwise inversions between these two orderings. Formally, inv(≻,≻′ ) = |{c, c′ ∈ C | c ≻′ c′ and c′ ≻ c}|.

Definition 7 (Mallows Model). Let ϕ ∈ (0, 1] be a dispersion parameter and Z = ∑≻∈S ϕinv(≻,≻0) . The Mallows distribution is a probability distribution over S. The probability that an ordering ≻ in S is drawn from the Mallows distribution is given by

The dispersion parameter ϕ characterizes the correlation between the sampled ordering and the reference ordering ≻0. Specifically, when ϕ is close to 0, the ordering drawn from D≻0,ϕ is almost the same as the reference ordering ≻0. On the other hand, when ϕ = 1, D≻0,ϕ corresponds to the uniform distribution over all permutations of C.

Siblings within the same family typically share identical priority scores, with ties resolved arbitrarily [Sun et al., 2023; Sun et al., 2024]. Motivated by this observation, we construct a reference ordering ≻0 through the following steps. Starting with an empty list, we first include all singleton children C O , who do not have siblings. For each family f ∈ F S (families with siblings), we decide probabilistically whether to add its children individually or as a grouped entity: with a probability of 1/n1+ε , all children Cf of the family are added as separate entries, and with a probability of 1 - 1/n1+ε , the family is added as a single entity to keep its children grouped together, where n is the total number of children and ε > 0 is a constant. Once all children and families are added, the list is shuffled to introduce randomness. Finally, the reference ordering ≻0 is drawn from a uniform distribution over all permutations of the shuffled list.

Definition 8 (Diameter). Given a reference ordering ≻0 over children C, we define the diameter of family f, denoted by diamf , as the greatest difference of positions in ≻0 among Cf plus 1. Formally,

where maxc∈Cf c (resp. minc∈Cf c) refers to the child in Cf with the highest (resp. lowest) priority in ≻0.

The methodology employed to generate the reference ordering ≻0 above adheres to the following condition. For each family f with siblings, we have Pr[diamf ≥ |Cf |] ≤ 1 n1+ε from the construction.

4.3 Main Theorem

We focus on a randommarket ˜ I where all parameters are set as described above. Although a stable matching may not exist even when all daycares have the same priority ordering over children (see the Appendix), our main result, encapsulated in the following theorem, shows that for a large randommarket, the existence of a stable matching is highly likely.

Theorem3. Given a randommarket ˜ I with ϕ = O(log n/n), the probability of the existence of a stable matching converges to 1 as n approaches infinity.

5 Sketched Proof of Theorem 3

We prove Theorem 3 by showing that the ESDA algorithm produces a stable matching with a probability that converges to 1 in the random market. Our primary approach to proving Theorem 3 involves setting an upper bound on the likelihood of encountering the two types of unsuccessful termination in the ESDA algorithm.

The following two lemmas establish that as n approaches infinity, Type-1-a and Type-1-b unsuccessful terminations are highly unlikely to occur when the dispersion parameter ϕ is on the order of O(logn/n). We defer the proofs for these results to the Appendix.

Lemma 4. Given a random market ˜ I with ϕ = O(log n/n), the probability of Type-1-a unsuccessful termination in the ESDA algorithm is bounded by O((log n)2 /n).

Lemma 5. Given a random market ˜ I with ϕ = O(log n/n), the probability of Type-1-b unsuccessful termination in the ESDA algorithm is bounded by O((log n)2 /n) + O(n-ε ).

As illustrated in the Appendix Type-2 unsuccessful termination can occur even when the priorities of daycares over children are identical.

We introduce concepts of domination and nesting to analyze the case of Type-2 unsuccessful termination.

Definition 9 (Domination). Given a priority ordering ≻, we say that family f dominates f ′ w.r.t. ≻ if maxc∈Cf c ≻ minc′∈C(f ′ ) c′ where maxc∈Cf c (resp. minc∈Cf c) represents the child in Cf with the highest (resp. lowest) priority under the priority ordering ≻.

In simple terms, if f dominates f ′ , then there is a possibility that f ′ will be rejected by daycares with a certain order ≻ due to an application of f.

Definition 10 (Top Domination). Given a priority ordering ≻, we say that family f top-dominates f ′ w.r.t. ≻ if

Intuitively, a Type-2 unsuccessful termination can arise from a cycle in which two families with siblings reject each other. We introduce the concept of nesting as follows.

Definition 11 (Nesting). Given a priority ordering ≻, two families f and f ′ are said to be nesting if they mutually dominate each other under ≻.

We next show that if any two families do not nest with each other with respect to ≻0, then Type-2 unsuccessful termination is unlikely to occur as n tends to infinity in Lemma 6. We defer the proof to the Appendix.

Lemma 6. Given a random market ˜ I with ϕ = O(log n/n), and for any two families f, f ′ ∈ F S that are not nesting with each other with respect to ≻0, then Type-2 unsuccessful termination occurs with a probability of at most O(log n/n).

Following an analysis of the probability that any two pairs of families from F S nest with each other with respect to the reference ordering ≻0, we establish the probability of Type-2 unsuccessful termination in Lemma 7.

Lemma 7. Given a random market ˜ I with ϕ = O(log n/n), the probability of Type-2 unsuccessful termination occurring is bounded by O(log n/n) + O(n-2ε ).

Lemma 4, Lemma 5, and Lemma 7 imply the existence of a stable matching with high probability for the large random market, thus concluding the proof of Theorem 3.

6 Experiments

In this section, we conduct comprehensive experiments to address three key questions: (1) How often does a stable matching exist in a large random market? (2) How effective is our proposed ESDA algorithm in identifying stable matchings? (3) How does our stronger stability concept affect the existence of stable matchings compared to ABH-stability?

Given the limitations of the ESDA algorithm in computing stable matchings in certain scenarios, we adopt a constraint programming (CP) approach as an alternative. This method reliably produces a stable matching whenever one exists [Sun et al., 2024]. We compare our algorithm against the sequential couples (SC) algorithm, the original SDA, CP with ABH stability, and CP with our proposed stability concept.

To evaluate these algorithms, we use both real-world and synthetic datasets, focusing on two key aspects: the frequency with which each algorithm identifies a stable matching and their running time. All algorithms are implemented in Python and executed on a standard laptop with an M4 Pro chip, without additional computational resources. To generate priorities from the Mallows distributions, we follow the approach outlined in the PrefLib library [Mattei and Walsh, 2013].

The experimental findings are summarized as follows: (1) As established in Theorem 3, a stable matching is highly likely to exist when daycares share similar priority orderings over children. (2) The ESDA algorithm achieves performance close to the optimal solution, without experiencing a significant performance decline compared to SDA, while satisfying a stronger stability concept. (3) In general, our proposed stability concept does not reduce the probability of stable matchings existing compared to the ABH stability concept.

6.1 Experiments on Real-life Datasets

We first evaluate our algorithm on six real-world datasets obtained from three municipalities. All algorithms, including SDA, ESDA, CP-ABH, and CP-ours, successfully identify a stable matching in these cases, whereas only SC fails.

We are collaborating with several municipalities in Japan, and as part of our collaboration, we provide a detailed description of the practical daycare matching markets based on data sets provided by three representative municipalities.

The proportion of children with siblings ranges from 15% to 20%. The preference list of an only child is relatively concise compared to the available facilities, averaging between 3 and 4.5 choices. All daycares demonstrate a tendency to have similar priority orderings over the children. Detailed information is available in the Appendix.

6.2 Experiments on Synthetic Datasets

We outline the steps to generate synthetic datasets.

We define the total number of children, denoted by |C|, drawn from the set {500, 1000, 3000, 5000, 10000}. We assume that the proportion of children with siblings is bounded by α = 0.2. For families with siblings, we consider only twosibling families and three-sibling families, where the children account for 80% and 20%, respectively.

The number of two-sibling families is calculated as

and the number of three-sibling families is calculated as

The total number of children with siblings is calculated as

while the number of children without siblings is

Correspondingly, the total number of families is

where |F O | and |F S | represent the numbers of families without and with siblings, respectively.

The number of daycares is determined as

and the capacity of each daycare is fixed using the list [5, 5, 1, 1, 1, 1], where each element corresponds to a specific age group in the range from 0 to 5.

For each child without siblings (C O ), we randomly assign preferences for 5 daycares from the set D. For families with siblings (F S ), we generate an individual preference ordering of length 10 for each child c ∈ Cf by uniformly sampling fromD. Subsequently, we consider all possible combinations of preferences within the family and uniformly select a joint preference ordering of length 10.

We vary the dispersion parameter ϕ within the range {0.0, 0.3, 0.5, 0.7, 0.9, 1.0} while keeping the parameter ε, which is used to generate a reference ordering ≻0, fixed at 1. For each specified setting, we generate 100 instances.

In addition to the stability analysis, we conducted a comparison of the running times between these algorithms. Although SDA and ESDA may need to check all permutations of F S in the worst-case scenario, it consistently demonstrated significantly faster performance than the CP algorithm across all cases.

Regarding the experimental findings: (i) A stable matching is very likely to exist for ϕ ≤ 0.9 and with high probability for ϕ = 1.0. (ii) For ϕ ≤ 0.9, the ESDA algorithm consistently identified a stable matching, while the SDA algorithm consistently identified an ABH-stable matching. (iii) Although our stability concept is stronger than ABH-stability, there is no significant decrease in the existence of stable matchings for most of the settings, except for the case where |C| = 10000 and ϕ = 1.0, which is unlikely to occur in practice.

Table 1 presents the results for 3000 children, while the detailed experimental findings for different children sizes are summarized in the Appendix.

7 Conclusion

In this study, we investigate the reasons behind the existence of stable matchings in practical daycare markets, identifying the shared priority ordering among daycares as a primary factor. Our contributions include a probabilistic analysis of such large random markets and the introduction of the ESDA algorithm to identify stable matchings. Experimental results demonstrate the efficiency of the ESDA algorithm under various conditions. We plan to continue this study by investigating additional factors that contribute to the existence of stable matchings in more general settings, beyond the case of similar priority orderings over children.

Acknowledgments

This work was partially supported by the Japan Science and Technology Agency under the ERATO Grant Number JPMJER2301, and by the Japan Society for the Promotion of Science under Grant Numbers 21H04979 and 25K21277. We thank the anonymous reviewers of NeurIPS 2024, AAMAS 2025, and IJCAI 2025 for their valuable feedback.