Probabilistic Analysis of Stable Matching in Large Markets with Siblings

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 07:54:53

Abstract: We study a practical matching problem that involves assigning children to daycare centers. The collective preferences of siblings from the same family introduce complementarities, which can lead to the non-existence of stable matchings, as observed in the well-studied hospital-doctor matching problems involving couples. Intriguingly,  stable matchings have been observed in real-world daycare markets, even with a substantial number of sibling applicants.

Our research systematically explores the presence of stable matchings in these markets. We conduct a probabilistic analysis of large random matching markets that incorporate sibling preferences. Specifically, we examine scenarios where daycares have similar priorities over children, a common characteristic in practical markets. Our analysis reveals that as the market size approaches infinity, the likelihood of stable matchings existing converges to 1.

To facilitate our investigation, we introduce significant modifications to the Sorted Deferred Acceptance algorithm proposed by ed by Ashlagi et al. [2014]. These adaptations are essential to accommodate a more stringent stability concept, as the original algorithm may yield matchings that fail to meet this criterion. By leveraging our revised algorithm, we successfully identify stable matchings in all real-life datasets examined. Additionally, we conduct comprehensive empirical investigations using synthetic datasets to validate the efficacy of our algorithm in identifying stable matchings.

Main paper: 
 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 [Abdulkadiroglu and Sönmez, 2003, Abdulkadiroglu 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 complements, which can result in the non-existence of a stable matching [Roth, 1984, Klaus and Klijn, 2005] . Moreover, verifying the existence of a stable matching is known to be NP-hard, even in restrictive settings [Ronn, 1990 , McDermid and Manlove, 2010 , Biró et al., 2014] .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 Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.participants from 1999 to 2007. Kojima et al. [2013] and Ashlagi et al. [2014] demonstrate that if the proportion of couples grows sufficiently slowly compared to the number of single doctors, then a stable matching is very likely to exist in a large market.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, analogous to hospitals and doctors, with the notable distinction that the number of siblings in each family can exceed two. We are actively collaborating with multiple municipalities, providing advice to design and implement new centralized algorithms tailored to their specific needs.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, but the underlying reasons have not been thoroughly examined [Sun et al., 2023 [Sun et al., , 2024]] . Furthermore, theoretical guarantees established in prior research on matching with couples may not readily extend to the daycare market, 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 near-linear growth of couples in previous research [Ashlagi et al., 2014] . Secondly, we consider a stronger stability concept tailored for daycare markets. Our proposal has been presented to government officials and esteemed economists, who concur that this modification better suits the daycare markets1 .Our contributions can be summarized as follows:Firstly, we formalize a large random market that mirrors the characteristics of realistic daycare markets, incorporating family preferences and daycare priorities generated through probability distributions. A significant trait observed in practical markets is the tendency for daycares to exhibit similar priorities over children. Our central result demonstrates that, in such random markets, the probability of a stable matching existing approaches 1 as the market size tends to infinity (Theorem 1).To the best of our knowledge, this is the first work to explain the existence of stable matchings in these practical daycare markets.Secondly, we modify the Sorted Deferred Acceptance algorithm [Ashlagi et al., 2014] to address our stronger stability concept, as the original algorithm may not produce a matching that satisfies this criterion (Theorem 2). We carefully rectify and extend the algorithm to meet the stronger stability requirement (Theorem 3). Notably, we employ our modified algorithm to successfully identify stable matchings in all encountered real-life datasets. Additionally, we generate a large number of synthetic datasets that closely resemble real-life markets to assess the algorithm's effectiveness across diverse scenarios. 
related work: 
 We next provide a brief summary of some papers that are closely related to our work. A more detailed literature review is presented in Appendix A. A classical work on matching with couples, conducted by Kojima et al. [2013] , illustrates that as the market size approaches infinity, the probability of a stable matching existing converges to 1, given the growth rate of couples is suitably slow in relation to the market size, e.g., when the number of couples is √ n where n represents the number of singles. Ashlagi et al. [2014] propose an improved matching algorithm, building on the foundation laid by Kojima et al. [2013] . This refined algorithm demonstrates that, even if the number of couples grows at a near-linear rate of n ϵ with 0 < ϵ < 1, a stable matching can still be found with high probability.In contrast, Ashlagi et al. [2014] highlight that as the number of couples increases at a linear rate, the probability of a stable matching existing diminishes significantly. In practical applications, the National Resident Matching Program employed a heuristic based on the incremental algorithm proposed by Roth and Vate [1990] . Biró et al. [2016] proposed a different approach involves the utilization of the Scarf algorithm [Scarf, 1967] to identify a fractional matching. If the outcome proves to be integral, it is then considered a stable matching. Moreover, researchers have explored the application of both integer programming and constraint programming to address the complexities of matching with couples [Manlove et al., 2007 , Biró et al., 2014 , Manlove et al., 2017] . Notably, these methodologies have recently been adapted in the daycare matching market as well [Sun et al., 2023 [Sun et al., , 2024]] .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Our theoretical contribution are made under assumptions which are motivated by real-world datasets and we give full description of these assumptions in the paper.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
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.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 f (c) ∈ F . Each family f ∈ F is associated with a subset of children, denoted as C(f ) ⊆ C. In cases where a family contains more than one child, e.g.,C(f ) = {c 1 , • • • , c k } 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 d 0 is included in D, signifying the possibility of a child being unmatched. Each individual daycare d establishes a quota, denoted as Q(d), 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 C(f ). The notation ≻ 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 .Example 1. Consider family f with C(f ) = {c 1 , c 2 , . . . , c k } where the children are arranged in a predetermined order. A tuple of daycares in ≻ f , denoted as (d * 1 , d * 2 , . . . , d * k ), indicates that for each i ∈ {1, 2, . . . , k}, child c i is matched to some daycare d * i ∈ D. It's possible that d * i = d * j ,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 i) ∀f ∈ F, µ(f ) ≻ (d 0 , • • • , d 0 ) or µ(f ) = (d 0 , • • • , d 0 ), 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 d 0 , and ii) the number of children matched to each daycare d does not exceed its specific quota Q(d).Definition 2 (Feasibility). A matching µ is feasible if it satisfies the following conditions: i) ∀c ∈ C,|µ(c)| = 1, and ii) ∀d ∈ D, |µ(d)| ≤ Q(d).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 by Ashlagi et al. [2014] , our choice function operates through a greedy selection of children based on priority only, simplifying the representation of stability. 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 C(f ) = {c 1 , ..., c k } and the j-th tuple of daycares≻ f,j = (d * 1 , ..., d * k ) in ≻ f , form ablocking coalition if the following two conditions hold,(1) family f prefers ≻ f,j to its current assignment µ(f ), i.e., (d * 1 , ..., d * k ) ≻ f µ(f ), and(2) for each distinct daycare d in(d * 1 , ..., d * k ), C(f, j, d) ⊆ Ch d ((µ(d) \ C(f )) ∪ C(f, j, d)) holds,where C(f, j, d) ⊆ C(f ) denotes a subset of children who apply to daycare d with respect to ≻ f,j .A feasible and individually rational matching satisfies stability if no blocking coalition exists.Consider the input to Ch d (•) in Condition 2. First, we calculate µ(d)\C(f ), representing the children matched to d in matching µ but not from family f . Then, we consider C(f, j, d), which denotes the subset of children from family f who apply to d according to the tuple of daycares ≻ f,j .This process accounts for situations where a child c is paired with d in µ but is not included inC(f, j, d), indicating that c is applying to a different daycare d ′ ̸ = d according to ≻ 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 he intends to apply elsewhere.In contrast, the original concept by Ashlagi et al. [2014] does not take siblings' assignments into account. We illustrate the differences between the two concepts in (d 1 , d 2 ) ≻ f (d 2 , d 0 ). Each daycare prefers c 1 over c 2 .The matching (d 2 , d 0 ) is deemed stable by Ashlagi et al. [2014] , but it is not considered stable by Definition 4. This is because it is blocked by family f and the pair (d 1 , d 2 ). Here, child c 1 passes his seat at d 2 to c 2 , allowing both children to potentially be matched to a more preferred assignment.It is well-known that a stable matching is not guaranteed when couples exist [Roth, 1984] . We provide an example to illustrate that even when each family has at most two children, and all daycares have the same priority ordering over children, a stable matching may not exist. Please refer to Appendix B.3 for details. 
random daycare 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 Ĩ = (C, F, D, Q, α, β, L, P, ρ, σ, D ≻0,ϕ , ε).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 siblings, 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 -α)nand |C S | = αn. For each family f , the size of C(f ) is constrained by a constant β, expressed asmax f ∈F |C(f )| ≤ β.We adopt the approach outlined in Kojima et al. [2013] to generate family preferences through a two-step process. In the first step, we independently generate preference orderings for each child from a probability distribution P on daycares D. Subsequently, we employ a function ρ to aggregate the individual preferences of children within each family into a collective preference ordering.The procedure for generating preference orderings for each child operates as follows. Let P = (p d ) d∈D be a probability distribution, where p d represents the probability of selecting daycare d. For each child c, start with an empty list, independently choose a daycare d from P, and add it to the list if it is not already included. Repeat this process until the length of the list reaches the maximum length L, a relatively small constant in practice.We adhere to the assumption that the distribution P satisfies a uniformly bounded condition, as assumed in the random market by Kojima et al. [2013] and Ashlagi et al. [2014] .Definition 5 (Uniformly Bounded). For all d, d ′ ∈ D, the ratio of probabilities p d /p d ′ falls within the interval [1/σ, σ] with a constant σ ≥ 1.Lemma 1. Under the uniformly bounded condition, the probability p d of selecting any daycare d is limited by σ/m where m denotes the total number of daycares.For families with multiple siblings, we do not impose additional constraints on the function ρ that aggregates individual preferences into collective preferences.A notable departure from previous work [Kojima et al., 2013] and [Ashlagi et al., 2014] , is our adoption of the Mallows model [Mallows, 1957] to generate daycare priority orderings over children.In the Mallows model, represented as D ≻0,ϕ , a reference ordering ≻ 0 is first determined. New orderings are then probabilistically generated based on this reference, controlled by a dispersion parameter ϕ. This model is widely used for preference generation in diverse contexts [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 ≻0) .Pr[≻] = 1 Z ϕ inv(≻,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.In the practical daycare matching market, every municipality assigns a unique priority score to each child, establishing a strict priority order utilized and slightly adjusted by all daycares. Siblings within the same family usually share identical priority scores, with ties being resolved arbitrarily.Motivated by this observation, we construct a reference ordering ≻ 0 as follows: Begin with an empty list and include all children C O in the list. For each family f ∈ F S , add children C(f ) to the list with a probability of 1/n 1+ε , and include f in the list with a probability of 1 -1/n 1+ε for a constant ε > 0. Subsequently, shuffle all permutations of the elements in the list. Finally, ≻ 0 is drawn from a uniform distribution over all permutations of the shuffled elements in the list. In other words, with a probability of 1/n 1+ε , we treat siblings from the same family separately, and with a probability of 1 -1/n 1+ε , we treat them as a whole, or more precisely, as a continuous block in ≻ 0 .Definition 8 (Diameter). Given a reference ordering ≻ 0 over children C, we define the diameter of family f , denoted by diam f , as the greatest difference in ≻ 0 among C(f ). For-mally, diam f = c ∈ C max c ′ ∈C(f ) c ′ ≻ 0 c ≻ 0 min c ′′ ∈C(f ) c ′′ + 2 where max c∈C(f ) c (resp.min c∈C(f ) c) refers to the child in C(f ) 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 havePr diam f ≥ |C(f )| ≤ 1 n 1+ε from the construction.We concentrate on a random market Ĩ where all parameters are set as mentioned above. Our main result is encapsulated in the following theorem.Theorem 1. Given a random market Ĩ with ϕ = O(log n/n), the probability of the existence of a stable matching converges to 1 as n approaches infinity.We will prove Theorem 1 by demonstrating that an algorithm, namely the Extended Sorted DeferredAcceptance algorithm (to be defined in the next section), produces a stable matching with a probability that converges to 1 in the random market. 
extended sorted deferred acceptance: 
 In this section, we propose the Extended Sorted Deferred Acceptance (ESDA) algorithm, a heuristic approach that has proven effective in computing stable matchings across a variety of real-life daycare datasets. Importantly, the ESDA algorithm serves as a foundational component in our probability analysis for large random markets.The ESDA algorithm is an extension of the Sorted Deferred Acceptance (SDA) algorithm [Ashlagi et al., 2014] , originally designed for matching with couples. More details of the SDA algorithm are presented in Appendix C.3. In the following theorem, we demonstrate that the SDA algorithm may not produce a stable matching with respect to Definition 4 when it terminates without failure. The proof of Theorem 2 is presented in Appendix C.4.Theorem 2. The matching returned by the original SDA algorithm may not be stable.We next give an informal description of ESDA. The algorithm begins by computing a stable matching without considering families with siblings, denoted as F S , using the Deferred Acceptance algorithm (see Appendix C.1). Subsequently, it sequentially processes each family, denoted as f , based on a predefined order denoted as π. Children without siblings who are displaced by family f are processed individually, enabling them to apply to daycare centers from their top choices in their preference orderings. If any child from family f ′ ∈ F S with siblings is rejected during this process, a new order π ′ is attempted, with f being inserted before f ′ . If the outcome before inserting family f becomes different after processing family f , then we check whether family f can be matched to a better tuple of daycares from their top choices. The algorithm terminates and returns a failure if any child from family f is rejected or if the same permutation has been attempted twice.We offer a brief elucidation on the differences between our ESDA algorithm and the original SDA.Firstly, the input to the choice function of daycares differs. In our algorithm, children have the option to transfer their allocated seats to other siblings, a feature not present in the original SDA. Secondly, we meticulously examine whether any family could establish a blocking coalition with a tuple of daycares that previously rejected it whenever the assignment of any child without siblings is changed.In contrast, SDA goes through each tuple of daycares once without performing this check.We illustrate how ESDA works through Example 3. A formal description of ESDA is presented in Algorithm 1 in Appendix D, along with all technical details.Example 3. Consider three familiesf 1 with C(f 1 ) = {c 1 , c 2 }, f 2 with C(f 2 ) = {c 3 , c 4 } and f 3 with C(f 3 ) = {c 5 , c 6 }.There are five daycares denoted as D = {d 1 , d 2 , d 3 , d 4 , d 5 }, 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:≻ f1 : (d 1 , d 2 ), (d 1 , d 4 ) ≻ d1 : c 1 , c 5 ≻ d2 : c 6 , c 2 ≻ f2 : (d 3 , d 4 ), (d 5 , d 4 ) ≻ d3 : c 3 , c 5 ≻ d4 : c 6 , c 4 , c 2 ≻ f3 : (d 1 , d 4 ), (d 3 , d 4 ), (d 5 , d 2 ) ≻ d5 : c 3 , c 5Iteration 1: With order π 1 = {1, 2, 3}, family f 1 secured a match by applying to daycares (d 1 , d 2 ), followed by family f 2 obtaining a match with applications to (d 3 , d 4 ). However, family f The algorithm terminates, returning a stable matching µ with f 1 matched to (d 1 , d 2 ) and f 3 matched to (d 3 , d 4 ), while f 2 remains unmatched.We demonstrate that ESDA always generates a stable matching if it does not terminate with failures.Our proof relies on the following two facts, which are formally presented in Appendix D.1. 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.Second, 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 π. The detailed proof for Theorem 3 is presented in Appendixes D.1 and D.2.Theorem 3. Given an instance of I, if ESDA returns a matching without failure, then the yielded matching is stable. In addition, ESDA always terminates in a finite time, either returning a matching or a failure.Theorem 3 states that if the algorithm successfully concludes, it results in a stable matching. Conversely, the algorithm returns failures in two scenarios, suggesting that a stable matching may not exist, even if one indeed exists. A Type-2 Failure occurs if there exist two families f 1 , f 2 ∈ F S satisfying the following conditions: i) f 1 appears before f 2 in the current order π, ii) There exists a rejection chain starting from f 2 and ending with f 1 where all other families in the chain have an only child, and iii) A new order π ′ , obtained by placing f 2 in front of f 1 , has been attempted and stored in the set of Π, which keeps track of permutations tried during the ESDA process.These two types of failures are crucial when analyzing the probability of the existence of stable matchings in a large random market. Detailed examples illustrating these two types of failures can be found in Appendix D.3.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: All codes are included in the supplemental material along with instructions.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
skecthed proof of theorem 1: 
 Our main approach to proving Theorem 1 is to set an upper limit on the likelihood of encountering the two types of failure in the ESDA algorithm.The following two lemmas establish that as n approaches infinity, Type-1-a and Type-1-b Failures are highly unlikely to occur when the dispersion parameter ϕ is on the order of O(log n/n). We defer the proofs for these results to Appendices E.2 and E.3, respectively.Lemma 2. Given a random marketĨ with ϕ = O(log n/n), the probability of Type-1-a Failure in the SDA algorithm is bounded by O (log n) 2 /n . Lemma 3. Given a random market Ĩ with ϕ = O(log n/n), the probability of Type-1-b Failure in the SDA algorithm is bounded by O (log n) 2 /n + O(n -ε ).We introduce concepts of domination and nesting to analyze the case of Type-2 Failure.Definition 9 (Domination). Given a priority ordering ≻, we say that family f dominates f ′ w.r.t.≻ if max c∈C(f ) c ≻ min c ′ ∈C(f ′ ) c ′ where max c∈C(f ) c (resp. min c∈C(f ) c) represents the child in C(f )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 .Intuitively, a Type-2 Failure can arise from a cycle in which two families with siblings reject each other. We introduce the concept of nesting as follows.Definition 10 (Nesting). Given a priority ordering ≻, two families f and f ′ are said to be nesting if they mutually dominate each other under ≻.Example 4. Consider three familiesF = {f 1 , f 2 , f 3 }, each with two children: C(f 1 ) = {c 1 , c 2 }, C(f 2 ) = {c 3 , c 4 }, and C(f 3 ) = {c 5 , c 6 }.Suppose there is a priority ordering ≻: c 1 , c 3 , c 5 , c 2 , c 4 , c 6 . In this case, all pairs in F nest with each other with respect to ≻.We next show that if any two families do not nest with each other with respect to ≻ 0 , then Type-2Failure is unlikely to occur as n tends to infinity in Lemma 4. We defer the proof to Appendix E.4.Lemma 4. Given a random market Ĩ 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 Failure 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 Failure in Lemma 5.Lemma 5. Given a random market Ĩ with ϕ = O(log n/n), the probability of Type-2 Failureoccurring is bounded by O(log n/n) + O n -2ε .Lemma 2, Lemma 3, and Lemma 5 imply the existence of a stable matching with high probability for the large random market, thus concluding the proof of Theorem 1. Further elaboration and details can be found in Appendix E.7 Experiments Given the limitations of the ESDA algorithm in computing stable matchings in certain scenarios, we employ a constraint programming (CP) approach as an alternative. This method consistently generates a stable matching whenever one exists [Sun et al., 2024] . We implement them in Python and execute them on a standard laptop without additional computational resources. To generate priorities from the Mallows distributions, we utilize the PrefLib library [Mattei and Walsh, 2013]  
experiments on real-life datasets: 
 We present the experimental results on the six real-life datasets. It is noteworthy that the ESDA algorithm not only successfully identifies a stable matching but also consistently produces the same outcome as the constraint programming (CP) solution for all datasets. Moreover, the ESDA algorithm achieves a computation time that is more than 10 times faster than the CP (see Table 5 in Appendix F.2).To investigate the importance of similarity in daycare priorities on the performance of ESDA, we generate new datasets by perturbing the original real-world data using Mallows distributions. For each daycare, we independently sample priority orders from the Mallows distribution with varying dispersion parameters and replace the original priority order. We consider dispersion parameters ranging from 0.0 to 1.0 in increments of 0.1 and conduct 100 experiments for each case. Figure 1 illustrates the results, demonstrating that ESDA successfully computes a stable matching in more than 80% of cases when the dispersion parameter ϕ is at most 0.8. It is worth noting that when ϕ = 0.0, daycare priorities are identical to the original priorities. However, when the dispersion parameter is large, the ESDA may only find a stable matching in less than 50% of cases, even if one may exist.We illustrate the steps to generate synthetic datasets. Initially, we define the number of families, In the second row, we report the mean computational complexity along with its 95% confidence intervals, calculated only for the instances where the algorithm successfully found a stable matching.Regarding the experimental findings, the ESDA algorithm consistently identified a stable matching in all experiments. In addition to stability analysis, we conducted a comparison of the running time between the ESDA algorithm and the CP algorithm. Despite the potential requirement for the ESDA algorithm to check all permutations of F S in the worst case scenario, it consistently demonstrated notably faster performance than the CP algorithm across all cases.  
conclusion: 
 In this study, we investigate the factors contributing to the existence of stable matching in practical daycare markets. We identify the shared priority ordering among all daycares as one of the primary reasons. Our contribution includes a probability analysis for such large random markets and the introduction of the ESDA algorithm to identify stable matchings in practical datasets. Experimental results demonstrate the utility of ESDA under various conditions, suggesting its potential scalability to larger markets where optimization solutions, such as integer programming or constraint programming, may exhibit much longer processing times.A Related Work Ronn [1990] initially established that verifying the existence of stable matchings in the presence of couples is an NP-hard problem, even if each hospital offers only one position. Follow-up work by McDermid and Manlove [2010] showed this computational intractability result still holds even when couples' preferences are limited to pairs of positions within the same hospital. Furthermore, Biró et al. [2011] demonstrated that it remains NP-hard when all doctors are ranked according to a common order adopted by all hospitals.A classical work on matching with couples, conducted by Kojima et al. [2013] , illustrates that as the market size approaches infinity, the probability of a stable matching existing converges to 1, given the growth rate of couples is suitably slow in relation to the market size, e.g., when the number of couples is √ n where n represents the number of singles. Ashlagi et al. [2014] propose an improved matching algorithm, building on the foundation laid by Kojima et al. [2013] . This refined algorithm demonstrates that, even if the number of couples grows at a near-linear rate of n ϵ with 0 < ϵ < 1, a stable matching can still be found with high probability. In contrast, Ashlagi et al. [2014] highlight that as the number of couples increases at a linear rate, the probability of a stable matching existing diminishes significantly. Kojima et al. [2013] devised the Sequential Couples Algorithm to address matching problems involving couples, which follows a three-step procedure. First, it computes a stable matching without considering couples, using the DA algorithm. Next, it handles each couple according to a predefined order denoted as π. Single doctors displaced by couples are accommodated one by one, allowing them to apply to hospitals based on their preferences. However, if an application is made to a hospital where any member of a couple has previously submitted an application, the algorithm declares a failure and terminates, even though a stable matching may indeed exist.The Sorted Deferred Acceptance (SDA) algorithm, as introduced by Ashlagi et al. [2014] , follows a similar trajectory to the Sequential Couples Algorithm. We extend its application to the context of daycare matching with siblings. The algorithm begins by computing a stable matching without considering families with siblings, denoted as F S , using the DA algorithm. Subsequently, it sequentially processes each family, denoted as f , based on a predefined order denoted as π. Children without siblings who are displaced by family f are processed individually, enabling them to apply to daycare centers according to their preferences. If any child from family f ′ ∈ F S with siblings is affected during this process, a new order π ′ is attempted, with f being inserted before f ′ . The algorithm terminates and returns a failure if any child from family f is affected or if the same permutation has been attempted twice.One potential solution to overcome the non-existence of stable matchings is to explore restricted preference domains. In this regard, Klaus and Klijn [2005] investigated a restricted preference domain known as weak responsiveness, ensuring the presence of stable matchings in the presence of couples. Hatfield and Kojima [2010] introduced the concept of "bilateral substitute" within the framework of matching with contracts [Hatfield and Milgrom, 2005] , encompassing matching with couples as a specific case, and they demonstrated that weak responsiveness implies bilateral substitutes.In practical applications, the National Resident Matching Program employed a heuristic based on the incremental algorithm proposed by Roth and Vate [1990] . Biró et al. [2016] proposed a different approach involves the utilization of the Scarf algorithm [Scarf, 1967] to identify a fractional matching.If the outcome proves to be integral, it is then considered a stable matching. Moreover, researchers have explored the application of both integer programming and constraint programming to address the complexities of matching with couples [Manlove et al., 2007 , Biró et al., 2014 , Manlove et al., 2017] . Notably, these methodologies have recently been adapted in the daycare matching market as well [Sun et al., 2023 [Sun et al., , 2024]] .Another trend in the literature explores the combination of bandit algorithms with matching market design. In these studies, preferences are initially unknown and are learned through the interactions between the two sides of agents (see [Das and Kamenica, 2005 , Liu et al., 2020 , Basu et al., 2021 , Liu et al., 2021 , Jagadeesan et al., 2021 , Kong et al., 2022] ). This contrasts with our setting, where preferences and priorities are submitted to the system in advance. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: This paper investigates a practical matching problem involving the assignment of children to daycare centers in Japan. The goal is to understand the conditions under which stable matchings are more likely to exist. If a stable matching is unlikely, alternative solutions must be developed, such as adopting weaker versions of stability by minimizing the number of blocking coalitions, restricting the preference domain of families, and other approaches.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
 
 Appendix: The primary reason for modifying the stability concept lies in the differing selection criteria between hospital-doctor matching and daycare allocation. In the hospital-doctor matching problem, hospitals have preferences over doctors. In contrast, daycare centers use priority orderings based on 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.The stability concept studied in [Ashlagi et al., 2014] was originally designed for matching with couples and defined by enumerating all possible scenarios. To distinguish it from our concept, we refer to their stability as ABH-stability, named after the authors' initials.In Definition 11, we consolidate these scenarios into a concise format, which highlights the differences from our definition. The primary distinction from Definition 4 lies in the input toCh d (•) in condition 2: it uses Ch d (µ(d) ∪ C(f, j, d)), instead of Ch d (µ(d) \ C(f ) ∪ C(f, j, d)).Definition 11 (ABH-Stability). Given a feasible and individually rational matching µ, family f A feasible and individually rational matching satisfies ABH-stability if no blocking coalition exists.with children C(f ) = {c 1 , ..., c k } and the j-th tuple of daycares ≻ f,j = (d * 1 , ..., d * k ) in ≻ f ,ABH-Stability maintains alignment with the stability notion presented by Kojima et al. [2013] . In the latter study, the authors explore a responsive preference domain in which daycare priorities are defined over sets of children. Despite differences in the choice function employed, the foundational idea of defining stability exhibits conceptual coherence between these two works.Example 5 (Non-existence of Stable Matchings). Consider three families: f 1 with children C(f 1 ) = {c 1 , c 2 }, f 2 with children C(f 2 ) = {c 3 , c 4 },≻ f1 : (d 1 , d 2 ) ≻ f2 : (d 2 , d 3 ) ≻ f3 : (d 3 , d 1 ) ≻ d : c 1 , c 6 , c 3 , c 2 , c 5 , c 4 ∀d ∈ DWe denote the option of being unmatched as ∅ for brevity. There are three feasible matchings except for the empty matching which can not be stable, namely:• Matching µ 1 where µ 1 (f 1 ) = (d 1 , d 2 ), µ 1 (f 2 ) = (∅, ∅), and µ 1 (f 3 ) = (∅, ∅).• Matching µ 2 where µ 2 (f 1 ) = (∅, ∅), µ 2 (f 2 ) = (d 2 , d 3 ), and µ 2 (f 3 ) = (∅, ∅).• Matching µ 3 where µ 3 (f 1 ) = (∅, ∅), µ 3 (f 2 ) = (∅, ∅), and µ 3 (f 3 ) = (d 3 , d 1 ).Matching µ 1 cannot be stable, because family f 2 could form a blocking coalition with a pair of daycares (d 2 , d 3 ), where Ch d2 ({c 2 , c 3 }) = {c 3 } and Ch d3 ({c 4 }) = {c 4 }. Similarly, matching µ 2 is blocked by family f 3 and daycares (d 3 , d 1 ), and matching µ 3 is blocked by family f 1 and daycares(d 1 , d 2 ). Consequencely, none of the matchings µ 1 , µ 2 , and µ 3 is stable.C.1 Deferred Acceptance (DA)The Deferred Acceptance (DA) algorithm is a classical algorithm in matching theory under preferences [Gale and Shapley, 1962, Roth, 1985] . The (children-proposing) DA algorithm proceeds iteratively through the following two phases. In the application phase, children first apply to their most preferred daycares that have not rejected them so far. In the selection phase, each daycare selects children based on its priorities from the pool of new applicants in the current round and the temporarily matched children from the previous round without exceeding specific quotas. The algorithm terminates when no child submits any further applications. An essential property of the DA algorithm is that it always converges to a stable matching within polynomial time when siblings are not involved. In the case of a rejection cycle involving families, we mandate that i) at least two distinct families are present in the rejection chain, and ii) the rejection chain initiates and concludes with the same family. It is possible that the starting child c * 1 and the ending child c * t are different, but they are from the same family.∈ {c * 1 , c * 2 , • • • , c * t } such that c ′ ̸ = c * 1 ,In cases where no child has siblings, rejection cycles may occur, but they are guaranteed to eventually terminate. This termination is ensured by the following reasons: i) When a daycare reaches its quota, the number of matched children remains constant, even though the set of matched children may vary. ii) Children cannot be matched to a daycare that previously rejected them, as a daycare never regrets rejecting a child with lower priority than its currently matched children when it meets its quota. Consequently, a child does not need to reapply to any daycare that has rejected them.However, these arguments do no longer hold in the presence of siblings. This is because when one child is rejected by a daycare, their sibling may be compelled to leave the matched daycare, due to their joint preferences over tuples of daycares, rather than a rejection. Consequently, vacancies arise at a daycare that was previously full, enabling a previously rejected child to reapply. This suggests that a rejection cycle may persist indefinitely.The Sequential Couples algorithm, devised by Kojima et al. [2013] to address matching problems involving couples, follows a three-step procedure. First, it computes a stable matching without considering couples, using the DA algorithm. Next, it handles each couple according to a predefined order denoted as π. Single doctors displaced by couples are accommodated one by one, allowing them to apply to hospitals based on their preferences. However, if an application is made to a hospital where any member of a couple has previously submitted an application, the algorithm declares a failure and terminates, even if a stable matching indeed exists.The Sorted Deferred Acceptance (SDA) algorithm, as introduced by Ashlagi et al. [2014] , follows a similar trajectory to the Sequential Couples algorithm. We extend its application to the context of daycare matching with siblings. The algorithm begins by computing a stable matching without considering families with siblings, denoted as F S , using the DA algorithm. Subsequently, it sequentially processes each family, denoted as f , based on a predefined order denoted as π. Children without siblings who are displaced by family f are processed individually, enabling them to apply to daycare centers according to their preferences. If any child from family f ′ ∈ F S with siblings is affected during this process, a new order π ′ is attempted, with f being inserted before f ′ . The algorithm terminates and returns a failure if any child from family f is affected or if the same permutation has been attempted twice.Theorem 2. The matching returned by the original SDA algorithm may not be stable.Proof. We present a counterexample in Example 6 to prove Theorem 2.Example 6. Consider two families:f 1 with children C(f 1 ) = {c 1 , c 2 }, f 2 with children C(f 2 ) = {c 3 }.There are three daycares: D = {d 1 , d 2 , d 3 }, each with a single slot. The preference profile of the families and the priority profile of the daycares are as follows:≻ f1 : (d 1 , d 2 ), (d 2 , d 3 ), ≻ f2 : d 2 ≻ d : c 1 , c 3 , c 2 ∀d ∈ D.Then, SDA produces a matching µ(f 1 ) = {(d 2 , d 3 )} while leaving child c 3 unmatched. However, by Definition 4, this matching is not stable. This is because family f 1 could form a blocking coalition with (d 1 , d 2 ) by allowing c 1 to transfer his seat at d 2 to sibling c 2 .This completes the proof of Theorem 2. Note that no matching for this example satisfies stability in Definition 4.The ESDA algorithm commences with the application of the Deferred Acceptance (DA) algorithm to families without siblings F O . The resulting matching is denoted as µ O . The ESDA algorithm operates with an order π defined over the set {1, • • • , |F S |}. To keep track of attempted permutations, we introduce the collection Π, initialized with {π}.The pivotal step in the ESDA algorithm involves the sequential insertion of families F S based on the order π. Let π(i) denote the i-th element in π, starting with i = 1, and let F S π(i) denote the π(i)-th family in F S . We define µ as the current matching during the ESDA process, and µ i denotes the matching before processing the π(i)-th family in F S . Both µ and µ i are initialized with µ O .Consider the π(i)-th family f ∈ F S , denoted as f = F S π(i) . Family f makes proposals to the j-th tuple of daycares, denoted as ≻ f,j , with the initialization of j at 1. Define D(f, j) as the set of distinct daycares in ≻ f,j . For each daycare d ∈ D(f, j), we calculate C(f, j, d), representing the set of children from family f applying to daycare d w.r.t. ≻ f,j .According to the choice function outlined in Definition 3, the input is µ(d) \ C(f ) ∪ C(f, j, d),excluding siblings from C(f ) who do not apply to daycare d w.r.t. ≻ f,j . If C(f, j, d) cannot be chosen by all d ∈ D(f, j), the algorithm advances to the next tuple of daycares by updating j ← j +1.Otherwise, family f can be matched to ≻ f,j in µ.Let A denote a set of children who i) do not belong to family f and ii) are involved in the rejection chains when matching f to ≻ f,j . Two possibilities can arise.Case 1) If any child from familyf ′ ∈ F S \ {f } is involved in A, i.e., A ∩ C(f ′ ) ̸ = ∅, a new order π ′is generated by inserting f before f ′ . If π ′ has been attempted previously, the algorithm terminates, returning failure (Type 2), a concept that will be detailed shortly. Otherwise, the algorithm restarts with the new order π ′ and add π ′ to Π. Once B becomes empty, we verify whether µ T equals µ. If they are not identical, we revisit family f by setting i ← i; otherwise, we update µ i+1 ← µ and proceed to the next family in F S by settingi ← i + 1.Our proof that ESDA always generates a stable matching if it does not terminate with failures, 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 6. For a given order π over families F S , let µ i (π) denote the matching obtained during the ESDA procedure before processing family ≻ f,k that is better than µ(f ), then f is still rejected as each matched child at d ∈ D(f, j) has a weakly higher priority. Thus, f cannot create new vacancies by moving to a better tuple of daycares.F S π(i) ∈ F S .Consequently, the number of matched children at each daycare does not decrease.For a given matching µ and a daycare d, let L(µ, 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 L(•).We will now demonstrate the following lemma.Lemma 7. Given an order π over families F S , if, during the ESDA process, the rank L(µ, d)increases for any daycare d, then ESDA fails to generate a matching under the current order π over families F S .Proof. We next prove Lemma 7 by examining the changes in L(µ, d) at each daycare d throughout the execution of the ESDA algorithm under a given order π.[Line 1] The ESDA algorithm begins by employing the DA algorithm on families F O . At each step of the DA algorithm, a rejected child is substituted by another child with a higher priority. Consequently, for each daycare d, the value of L(µ, d) either decreases or remains unchanged.Algorithm 1 Extended Sorted Deferred Acceptance (ESDA) Input: an instance I = (C, F, D, Q, ≻ F , ≻ D ) and a default order π = 1, 2, ..., |F S | Output: a stable matching or a failure 1: Apply DA to F O and denote the obtained matching as µ O 2: Initialize Π ← {π}, storing the permutations of π that have been attempted 3: Initialize i ← 1 with π(i) being the i-th element in π 4: Initialize µ ← µ O (current matching) and µ i ← µ O (the matching before processing the π(i)-th family in F S ) 5: while i ≤ |F S | do {Iterate through F S according to π} Following the same argument, we can continue this chain until we reach a child, say c t , who cannot be matched to a better daycare d t than µ i (c t ) in µ. If daycare d t has a vacant seat under µ, it implies that d t must have had a vacant seat under µ i before processing family f . However, this contradicts the fact that c t was rejected by d t under µ i . Therefore, all the children c t , c t-1 , c t-2 , . . . , c 1 could form a rejection chain ending with child c, leading to a Type-1 Failure.Continuing this reasoning, we must arrive at some child, say c t , who cannot be matched to a better daycare d t than µ i (c t ) in this way. This is because family f cannot create more vacancies than the number of children rejected by it when changing from ≻ f,k to ≻ f,j , unless other families from f ′ ∈ F S \ {f } is rejected. However, in that case we will go to lines 15-22 instead. Therefore, we can conclude that the children c t , c t-1 , c t-2 , • • • , c 1 , c could form a rejection chain ending with child c, resulting in a Type-1 Failure.Having meticulously examined all conceivable scenarios during the ESDA procedure, it is evident that π is incapable of leading to a matching if L(µ, d) experiences an increase for any daycare d.This completes the proof of Lemma 7. If this happens, then the rank of matched children L(•) at some daycare decreases, contradicting Lemma 7, which implies that π can produce a matching. Thus, we know f cannot be matched to a better tuple even if passing seats are allowed. For both cases, we conclude that family f w cannot pariticipate in a blocking coalition w.r.t. matching µ.Moving on to the second last family f w-1 , we apply a similar reasoning.When inserting family f w-1 into the market, if it can be matched to a better tuple after the stabilization step, it contradicts Lemma 7. After family f w is introduced into the market, two key observations hold: i) the number of matched children does not decrease at any daycare, as per Lemma 6, and ii) for each daycare d, L(µ, d) does not increase, meaning no daycare accepts a child with a lower priority, per Lemma 7.Consequently, family f w-1 still cannot be matched to a better tuple of daycares after the insertion of the last family f .Continuing this logic through induction, we conclude that no family f i ∈ F S π(i) can be matched to a better tuple of daycares under the order π. In other words, none of the families in F S can participate in a blocking coalition. For the same reasons, it follows that any family f ∈ F O cannot be matched to a better daycare either.For each permutation of π, the algorithm may iterate multiple times of checking f for lines 45-46, if the current matching µ changes after the stabilization step. Since the choices in each only child's preference ordering are finite, the check terminates in a finite time or returns with a failure.Furthermore, the total number of permutations of π is also finite, thus ensuring the algorithm's termination. This concludes the proof of Theorem 3. ≻ f1 : (d 1 , d 3 ) ≻ f2 : d 1 , d 2 ≻ f3 : d 2 , d 1 ≻ d1 : c 4 , c 1 , c 3 ≻ d2 : c 3 , c 4 ≻ d3 : c 2The initial matching µ O is obtained through the Deferred Acceptance (DA) algorithm, whereµ O (c 3 ) = d 1 and µ O (c 4 ) = d 2 . Upon inserting family f 1 , child c 1 is matched to daycare d 1 ,and child c 2 is matched to daycare d 2 , resulting in the rejection of child c 3 from daycare d 1 . Subsequently, when child c 3 applies to daycare d 2 , it leads to the rejection of child c 4 . Finally, when child c 4 applies to daycare d 1 , it results in the rejection of child c 1 .Thus, a rejection chain is formed: The preferences of the families and the priorities of the daycares are outlined as follows:c 1 → c 3 → c 4 → c 1 ,≻ f1 : (d 1 , d 2 ) ≻ f2 : d 1 , d 2 ≻ d1 : c 1 , c 3 ≻ d2 : c 3 , c 2The initial matching µ O is obtained through the Deferred Acceptance (DA) algorithm, with µ O (c 3 ) = ≻ f1 : (d 1 , d 2 ), (d 1 , d 3 ) ≻ f2 : (d 2 , d 3 ) ≻ d1 : c 1 ≻ d2 : c 3 , c 2 ≻ d3 : c 2 , c 4When family f 1 is inserted, it secures a match with (d 1 , d 2 ). Subsequently, when family f 2 is added, child c 2 from family f 1 is rejected, prompting a change in the order to π ′ = {2, 1} and a restart of the algorithm. Now, if we add family f 2 first in the revised order π ′ , it obtains a match with (d 2 , d 3 ). However, when family f 1 is added and applies to (d 1 , d 2 ), child c 2 has a lower priority than child c 3 , resulting in the rejection of family f 1 . Consequently, family f 1 applies to (d 1 , d 3 ), causing family f 2 to be evicted in turn.This leads us to modify the order π ′ to π * = {1, 2}, which has been attempted previously. Thus, the ESDA algorithm terminates due to a Type-2 Failure.In this section, we outline the proof for Theorem 1. Our main approach is to set an upper limit on the likelihood of encountering the two types of failure in the ESDA algorithm.Theorem 1. Given a random market Ĩ with ϕ = O(log n/n), the probability of the existence of a stable matching converges to 1 as n approaches infinity.We leverage the following lemma in our proof. It asserts that if an ordering ≻ is generated from a given Mallows distribution D ≻0,ϕ , the probability of child c ′ being ranked higher than child c in ≻ is no greater than 4ϕ dist(c,c ′ ) , given that c ≻ 0 c ′ , where dist(c, c ′ ) represents the distance between c and c ′ in ≻ 0 .Lemma 8 ([Levy, 2017] ). If ≻ is a random ordering drawn from the Mallows distribution D ≻0,ϕ , then for all c, c ′ ∈ C,Pr c ′ ≻ c | c ≻ 0 c ′ ≤ 4ϕ dist(c,c ′ ) where dist(c, c ′ ) = |{c ′′ ∈ C | c ≻ 0 c ′′ ≻ 0 c ′ }| + 1. E.1 Proof of Lemma 1Lemma 1. Under the uniformly bounded condition, the probability p d of selecting any daycare d is limited by σ/m where m denotes the total number of daycares.Proof. For each daycare d, we have1/σ ≤ p d /p d ′ ≤ σ. Therefore, p d ′ /σ ≤ p d ≤ σ • p d ′ . If we sum this inequality over each d ′ ∈ D, we obtain m • p d ≤ d ′ ∈D σ • p d ′ = σ. Thus, p d ≤ σ/m. E.2 Proof of Lemma 2Lemma 2. Given a random market Ĩ with ϕ = O(log n/n), the probability of Type-1-a Failure in the SDA algorithm is bounded by O (log n) 2 /n .Proof. We first consider a Type-1-a Failure, where a rejection chainc 1 → c * 2 → • • • → c * ℓ → c 1 exists.Here, child c 1 belongs to a family f ∈ F S with multiple children, while the other childrenc * 2 , • • • , c * ℓ ∈ C O have no siblings. Let E a ℓ represent the event of such a rejection chain c 1 → c * 2 → • • • → c * ℓ → c 1 , with length ℓ ≥ 3.We next show that, for any ≻ 0 , we haveEQUATIONSuppose that in this rejection chain, child c 1 applies to daycare d 1 , while children Let ≻ 1 represent the priority ordering of daycare d 1 . For i ∈ {2, . . . , ℓ -1}, let ≻ i denote the priority ordering of daycare d * i . Recall that for each i = 1, . . . , ℓ -1, the priority ordering ≻ i is drawn from the Mallows distribution D ≻0,ϕ . We consider two cases.Case (i): Suppose the reference ordering ≻ 0 satisfies the following conditionEQUATIONBy Lemma 8, we havePr[c * ℓ ≻ 1 c 1 ≻ 1 c * 2 |≻ 0 ] ≤ Pr[c 1 ≻ 1 c * 2 | c * 2 ≻ 0 c 1 ] ≤ 4ϕ. For all i = 2, ..., ℓ -1, we also have Pr[c * i ≻ i c * i+1 |≻ 0 ] ≤ 4ϕ. From d * 1 ̸ = d * 2, we know ≻ 1 and ≻ 2 are independent. Then we havePr E a ℓ |≻ 0 ≤ Pr c 1 ≻ 1 c * 2 |≻ 0 • Pr c * 2 ≻ 2 c * 3 |≻ 0 • Pr c * ℓ-1 applies to d 1 ≤ 16ϕ 2 p d1 .Lemma 1 states that p d1 ≤ σ/m. Then we haveEQUATIONCase (ii): If ≻ 0 does not satisfy the condition in Formula (2), thenPr[c * ℓ ≻ 1 c 1 ≻ 1 c * 2 |≻ 0 ] ≤ 4ϕ 2holds or there exists i ∈ {2, ..., ℓ -1} such that Pr[c * i ≻ i c * i+1 |≻ 0 ] ≤ 4ϕ 2 . From this, we obtainEQUATIONFrom Inequalities (3) and (4) above, for both cases (i) and (ii), we have Pr[E a ℓ |≻ 0 ] ≤ 16σϕ 2 m . This completes the proof of Inequality (1).Given that ≻ 0 is drawn from a uniform distribution over all permutations of C, we can derive the following inequality for the probability of encountering Type-1-a Failure, denoted as E ℓ , for a particular length ℓ of the rejection chain:Pr E a ℓ ≤ ≻0∈S ′ Pr E a ℓ |≻ 0 • Pr[≻ 0 ] ≤ 16σϕ 2 m ≻0∈S ′ Pr[≻ 0 ] = 16σϕ 2 mwhere S ′ denotes all permutations on the set of children C that is used to generate ≻ 0 .To obtain the overall probability of Type-1-a Failure, we sum up the probabilities for all possible lengths ℓ and for all children F S . Recall that the length of each child's preference ordering is bounded by L, and the length of a rejection chain is upper bounded by (1 -α)n • L and lower bounded by 3. Thus, the probability that there exists a rejection cycle leading Type-1-a Failure is bounded from Proof. We next proceed to Type-1-b Failure, where a rejection chain is denoted asc 1 → c * 2 → • • • → c * ℓ → c ′ 1 .Here, c 1 and c ′ 1 are siblings of the same family f ∈ F S , while c * 2 , . . . , c * ℓ are children without siblings. Suppose that c * i applies to d * i for each i = 2, 3, ..., ℓ -1.If children c 1 and c ′ 1 have nearly identical priorities in ≻ 0 (diam f ≤ |C(f )|), the analysis aligns with that of Type-1-a Failure. Consequently, in this scenario, the probability of the rejection chain occurring is at most 16σϕ 2 /m for any ≻ 0 and for any 2 ≤ ℓ ≤ (1 -α)nL.If children c 1 and c ′ 1 have significantly different priorities in ≻ 0 (diamf > |C(f )|), then it only occurs with a probability at most 1/n 1+ε (ε > 0). Therefore, even in the worst-case scenario where≻ 0 satisfies c * 1 ≻ 0 c * 2 ≻ 0 • • • ≻ 0 c * ℓ ≻ 0 c ′ *1 , the probability that the last child c * ℓ causes c ′ 1 to be rejected, is bounded by σ n 1+ε m .Let E b ℓ denote the event where the rejection chain of length ℓ starting with c 1 and ending with c ′ 1 occurs. For any ℓ and ≻ 0 , we havePr E b ℓ |≻ 0 ≤ 16σϕ 2 m + σ n 1+ε m .We next sum up the probabilities for all possible lengths ℓ and for any two children in families with multiple children. The probability of Type-1-b Failure occurring is bounded byαn • k 2 • (1-α)nL ℓ=2 Pr E b ℓ ≤ α(1 -α)L k2 n 2 16σϕ 2 m + σ n 1+ε m = O (log n) 2 n + O(n -ε ).Here, we used m = Ω(n) and ϕ = O(log n/n). This concludes that Type-1 Failure does not happen with high probability.In addition to the concept of domination, we define the notion of top-domination.Definition 14 (Top Domination). Given a priority ordering ≻, we say that family f top-dominatesf ′ w.r.t. ≻ if max c∈C(f ) c ≻ max c ′ ∈C(f ′ ) c ′ .Lemma 4. Given a random market Ĩ 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 Failure occurs with a probability of at most O(log n/n).Proof. Consider any two families f, f ′ ∈ F S that do not nest with each other. Without loss of generality, we assume that f top-dominates f ′ , and f ′ does not dominate f , otherwise they would nest with each other. Then we have,EQUATIONSuppose f ′ appears before f in the order π over families F S , and f ′ is currently matched. When f is inserted into the market, we observe that the probability of f causing the rejection of f ′ is bounded by σ/m, i.e., Pr f rejects f ′ ≤ σ/m, given that preferences are uniformly bounded.Next, consider a new order π ′ in which f is placed before f ′ . We aim to analyze the probability of f ′ causing the rejection of f in a rejection chain of length ℓ.We begin with ℓ = 2. Suppose a child c ∈ C(f ) is currently matched to daycare d 1 , and another child c ′ ∈ C(f ′ ) also applies to daycare d 1 , resulting in the rejection of child c. As shown in Formula (5),we have c ≻ 0 c ′ . Since c ′ ≻ 1 c, we can deduce that Pr[c ′ ≻ 1 c |≻ 0 ] ≤ 4ϕ from Lemma 8.Let E ′ 0 be the event where f rejects f ′ , followed by f ′ rejecting f . The probability that one child in C(f ′ ) applies to d 1 is upper-bounded by σ/m. Therefore, we can derive:Pr E ′ 0 ≤ σ m 2 4ϕ = 4σ 2 ϕ m 2 .Next, we consider the scenario where a rejection chain of length ℓ + 2 occurs, where ℓ represents the number of children without siblings participating in the rejection chain. Suppose the rejection chainfollows the pattern c → c * 1 → c * 2 → • • • → c * ℓ → c ′ , where c * 1 , ..., c * ℓ ∈ C O .In this case, we have1 ≤ ℓ ≤ (1 -α)nL.Let E ′ ℓ be the event where f rejects f ′ , and subsequently f ′ rejects f using a rejection chain of length ℓ. For any ≻ 0 , the replacement by the Mallows distribution must happen at least twice. Thus, for each ℓ = 1, 2, . . . , (1 -α)nL, we havePr E ′ ℓ |≻ 0 ≤ σ ′ m 2 16ϕ 2 ≤ 16σ ′ ϕ 2 m 2 .We sum up the probabilities for all possible ≻ 0 , and achievePr E ′ ℓ ≤ 16σ ′ ϕ 2 m 2for each ℓ = 1, 2, . . . , (1 -α)nL. Then we obtain(1-α)nL ℓ=1 Pr E ′ ℓ ≤ 16(1 -α)Lσnϕ 2 m 2 .Finally, since m = Ω(n) and ϕ = O(log n/n), we getPr there exists a pair of families with siblings cause rejections with each other = f,f ′ ∈F S Pr   (1-α) kn ℓ=0 E ′ ℓ   ≤ f,f ′ ∈F S (1-α)nL ℓ=0 Pr E ′ ℓ = f,f ′ ∈F S   Pr E ′ 0 + (1-α)nL ℓ=1 Pr E ′ ℓ   ≤ (αn) 2 16σϕ m 2 + 16(1 -α) kσnϕ 2 m 2 = O log n n .≤ αn 2 • 1 n 1+ε 2 ≤ α 2 n 2 • 1 n 1+ε 2 = O n -2ε .Since ε > 0 is a constant, the probability that any two families do not nest with each other approaches 1 as n tends to infinity.We now upper-bound the probability of Type-2 Failure. In cases where two families nest with each other, Type-2 Failure may occur with a constant probability. However, we have demonstrated that the probability of two families nesting with each other is at most O(n -2ε ). In instances where no two families nest with each other, Type-2 Failure happens with a probability of at most O(log n/n) as shown in Lemma 4. Therefore, we can express the probability of Type-2 Failure as follows:Pr Type-2 Failure happens = O n -2ε + O(log n/n).This completes the proof.Lemma 2, 3 and 5 imply the existence of a stable matching with high probability for the large random market, thus concluding the proof of Theorem 1.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.Firstly, the number of children in each market varies from 500 to 1600, with the proportion of children having siblings consistently spanning from 15% to 20%, as shown in Table 1 Secondly, the preference ordering of an only child is relatively short compared to the available facilities, averaging between 3 and 4.5 choices. Likewise, children from families with siblings exhibit a similar average of 3 to 4.5 distinct daycares in their individual preferences. Furthermore, siblings within the same family often share a similar set of daycares in their joint preference ordering. The details are presented in Thirdly, a critical aspect not mentioned in Section 3.1 is that each child is associated with an age ranging from 0 to 5. Drawing inspiration from prior work [Sun et al., 2023] , we make the assumption that there are six copies of the same daycare, each catering to a specific age. The distribution of children participating in the market is uneven, with a notable majority being aged 0 and 1. In Table 3 , we present the count of families with siblings and twins (i.e., pairs of siblings of the same age).Fourthly, despite the total capacity of all daycares exceeding the number of applicants, there exists a significant imbalance between demand and supply across different ages. Specifically, there is a shortage of slots for children aged 0 and 1, while there is a surplus of slots for ages 4 and 5, as shown in Fifthly, municipalities assign priority scores to children, with siblings from the same family typically sharing identical scores. Subsequently, daycares make slight adjustments to these priority scores to establish a strict priority ordering. As a result, all daycares tend to have similar priority orderings over the children.We employ both the Extended Sorted Deferred Acceptance (ESDA) algorithm and the constraint programming (CP) algorithm to find a stable matching for each real-life dataset. The results demonstrate that both algorithms successfully produce a stable matching. We compared the computational efficiency of the ESDA and CP approaches in terms of their runtime performance in Table 5 .In the experiments with synthetic datasets, the ESDA algorithm consistently identifies a stable matching whenever one exists, provided that the dispersion parameter ϕ does not exceed 0.5 (refer to Figure 2 in Section 7.2). However, as the dispersion parameter approaches 1, the ESDA algorithm may fail to find a stable matching, even when one exists. This is illustrated in Figure 3 . Interestingly, even when ϕ = 1, stable matchings are present in more than half of the cases. It is unclear why stable matching still exist in such settings with a high probability, and we leave it as an open question. Justification: Our objective is to elucidate why stable matchings exist in practical daycare markets. Through a realistic probabilistic model, we have theoretically demonstrated that stable matchings occur with high probability, and numerical experiments using real world data and synthetic data further reinforce this contribution.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.To preserve anonymity, their identities are not disclosed in this submission. 


Decision: The authors study a generalization of the stable matching problem (stable matching with siblings). All of the reviewers agreed that the theoretical and empirical contributions are interesting and the work is generally well done. However, the core audience for this work is unlikely to find itself at NeurIPS, and the paper's results, while solid, are not so groundbreaking or broad as to easily transcend areas. 

As such, this is a borderline decision, weighing the strength of the results against the recognition, support, and follow-up work they would get from publishing outside of the core discipline. Upon discussion with the senior area chair, it is our opinion that this work's focus is relatively narrow and it deserves to be published in a more AGT focused venue, be it EC, SAGT, or other related conferences, where it's likely to be well received.

Reviews: review: paper_summary: paper_summary: This paper studies the existence of a stable daycare-children matching in the presence of siblings from the same families with same preferences over the daycares. The authors particularly study the case when the daycares have similar preferences over the set of children, and the market size is large. They propose a variant of the Sorted Deferred Acceptance algorithm to compute the stable matchings.
strength_weakness: strength_weakness: 1. The assumption that day cares have similar priorities over children is slightly unrealistic.
2. The random daycare market for which the results are derived is somewhat restrictive.
questions: questions: 1. Can the authors give some evidence for whether daycare centers do have similar priorities over children or that the daycare centers use a priority scoring function? Is this just an assumption made by the authors to simplify the computation of stable matchings, or is there evidence supporting this assumption? 
2. Is the priority scoring function the same across all the daycares?
3. Can you repeat the algorithm multiple times until you get a successful matching, if the dispersion parameter is large?
limitations: limitations: Limitations sufficiently addressed by the authors.
paper_summary: paper_summary: This paper introduces the problem of daycare matching with siblings, an extension of matching with couples. Here, children in families (of size 1 or larger) are matched to daycares. Families have ranked preferences over the tuples of daycares their children end up at (since their preference for one child at one daycare may affect their preference of another child at some daycare), and daycares have preferences over children. In most cases, daycares do not differentiate between children within a family. This is an important problem to solve in Japan, and the authors actually worked with the Japanese daycare matching market in order to produce this work.

Their contributions are: 1) introduce the problem along with notions of rationality/stability/assumptions/etc, 2) propose an extended sorted deferred acceptance algorithm and prove that it will only return stable matchings and will fail to recognize a possible stable matching with probability approaching 1 as the problem grows, and 3) run experiments on their algorithm.

Their model is defined in a pretty standard way according to stable matching literature. The novelty, of course, is the introduction of families generalizing the size of couples. Their stability definition uniquely allows children in the same family to pass along seats to each other, so that a family may use that to their advantage in forming a blocking coalition. They assume that daycares have similar rankings over children and that they are drawn according to the Mallows Model, and that families only have few daycares they are interested in.

The algorithm itself works much like deferred acceptance. First, single children can propose to daycares per usual. Then, families with multiple children begin proposing, presumably according to their full ranking of matching tuples. When a single child is unseated from a daycare, they can simply propose to their next choice. When a family f has an unseated child when family f' is processed, the algorithm attempts again under a new order where f' goes before f. This can cause many iterations.

In the experiments, they use real datasets from Japan as well as larger synthetically-generated datasets. They compare their algorithm to a baseline constraint programming solution, showing that their algorithm returns the same solution faster.

Quick note: diameter is introduced in the main body but only used in the appendix. Perhaps move it to the appendix.
strength_weakness: strength_weakness: I am a bit concerned about the literature review provided. I am aware there is much more research that has been conducted on matching markets with complementaries (I am not knowledgeable enough to know what papers would be most useful), and I know there are various papers in this field. However, very few previous works are cited in this paper. It would be great if the authors could clarify the place of their work in the context of current literature and give confidence that this problem or a generalization of it has not already been studied. In fact, this is very important to motivate the paper.

Otherwise, there are a few points in the paper that are unclear. Much of it is very high level and lacks details, which is okay because it writes a narrative, but it comes at a cost of understanding the details of the proofs. More notably, I think the authors didn't spend enough time explaining their algorithm. I found it somewhat vague and I was uncertain about how it worked, and yet it is an integral part of the paper. This definitely needs to be improved.
questions: questions: 1. Line 256: What does the "outcome" refer to? You can't be considering the entire matching - obviously the matching will change when you process a new family.

2. Line 257: "...check whether a family f can be matched to a better tuple..." - What do you mean "can"? What are the conditions for this? Are we saying at the point in $\pi'$ where f is inserted, could it be better matched? Wouldn't they have matched to the preferable tuple in the deferred acceptance methods using $\pi'$? This is very unclear to me.

3. I didn't understand in the algorithm by what mechanism children can transfer seats to siblings. What am I missing?

4. Def 9: Again, I'm likely just missing something here. Domination is defined by the highest priority of family f being prioritized higher than the lowest priority of family f', correct? Doesn't this seem rather likely? In fact, shouldn't there always exist at least one instance of domination in every ordering?

5. Are there any other papers that have studied this problem or a generalization? Where does your work fall in the context of literature?
limitations: limitations: Everything seems adequate.
paper_summary: paper_summary: The authors study a variant of the many-to-one matching problem called the stable matching problem with siblings, which generalizes the stable matching problem with couples. In this problem, some families $f \in F$ may have more than one and at most $k$ siblings, ordered by age $(c_1,\dots,c_k)$. Each family $f = (c_1,\dots,c_k)$ expresses a joint linear preference order for daycares, denoted as 
$>_f \subseteq D \times D \dots \times D$,

 where $>_{f,j} = (d_1,\dots,d_k)$ represents the $j$th preference of family $f$, and $d_i$ corresponds to the preference for child $c_i$. Note that $>_f$ is an ordered set—a tuple. Each daycare $d \in D$ expresses a linear preference order $>_d \subseteq C$ for a subset of children and a maximum capacity $Q(d)$.

The objective is to find a (stable) matching such that no blocked pair exists. In essence, a blocked pair is a tuple (of edges) $(x_1,\dots,x_\ell)$ and $(y_1,\dots,y_\ell)$ such that swapping $x_i$ with $y_i$ results in a new matching that assigns children to daycares with higher priority for at least one family while not negatively impacting the assignment of any other family or daycare preferences.

A stable matching might not exist for restrictive settings of the problem, as the authors illustrate with a simple example in Appendix B.3. My understanding is that if the preferences form cycles, it becomes impossible to find a feasible solution that satisfies these preference constraints. However, in a daycare market where priorities are generated from a specific distribution, particularly random, the authors demonstrate that the probability of a stable matching existing converges to $1$ as the number of children $n$ approaches infinity.They present algorithms to solve the problem and conduct experiments on synthetic and real-world datasets, demonstrating that they can find feasible solutions in most instances.
strength_weakness: strength_weakness: While the paper makes significant contributions, there are some areas that could be improved. The writing is occasionally imprecise, making it challenging to follow the arguments and understand the definitions clearly. In particular, the choice of notation can be confusing (see detailed comments and questions). The structure of the paper is somewhat disorganized, with most of the proofs deferred to the appendix. Considering the strict page limits, this may be reasonable. However, Sections 3 and 4 could be compressed and written more concisely, and some proofs (or at least proof sketches) can be included in the main paper. I have only reviewed the proofs at a high level and have not verified the claims in sufficient detail. Given the strict reviewing timeline, this is the best I can do.
questions: questions: Line 97: The authors define $ f $ as a function $ f(c) \in F $ which maps $ f: C \rightarrow F $. Then they consider $ f \in F $ as $ f $ being an element in $ F $. This is confusing and imprecise.

Line 98: Using the same symbol for the function and set is incorrect. $ F(f) \subseteq C $ is imprecise; use a different alphabet to denote a function. I think this function should be $ x: f \rightarrow 2^C $ to be precise.

Line 99: $ C(f) = \{c_1,\dots,c_k\} $ should be $ C(f)=(c_1,\dots,c_k) $, since the set is ordered based on age, appropriate notation should be used.

Line 107: Why is the notation used as $ (d_1^*,\dots,d_k^*) $ and $ d_1,\dots,d_k $? What does $ * $ denote here?

Line 113: Using the same function $ \mu $ to map both children to daycares and daycares to children is confusing. Perhaps the authors should reconsider this; an appropriate way would be $ \mu: C \rightarrow D $. Even with the current definition of $ \mu $, using $ \mu(f) $ is very confusing and inaccurate in my opinion, as the function is defined for elements of $C \cup D$ and not a subset of $C \cup D$.

Line 137: Again, $ Ch_d(C') \subseteq C' $ is confusing to parse. It should be $ Ch_d: C' \rightarrow 2^{C'} $ right?

Example 1: What is the capacity of daycares? I am assuming it is $ 1 $.
limitations: limitations: The authors do not discuss limitations and potential negative social impact of their work.
paper_summary: paper_summary: The paper describes the problem of matching students to daycare centers, with each family allowed to express preferences about the joint allocation of all siblings within the family. The authors present a modified notion of a stable matching, in which a family may choose to withdraw one of its children from a daycare in favor of a different child, so long as the daycare still prefers this assignment among alternatives with the first child removed. Under this stronger notion of stability, they show that the existing SDA algorithm may produce unstable outputs. They present an extension to the algorithm ESDA, whose successful outputs meet the new stability condition. They also show that the algorithm will be successful with high probability for a particular distribution over problem instances. In this distribution, children populate a daycare preference order by selecting from a fixed distribution over the daycares, and families aggregate these preferences into preferences over joint allocations, using an arbitrary aggregation function. Daycares sample a preference order over children from a Mallows model, with low dispersion. 
Finally, the authors show some empirical results from real Japanese municipalities in which ESDA produces stable matchings in all cases.
strength_weakness: strength_weakness: My first question is about goodness of fit of the paper to NeurIPS. The best fit from the CFP is:
* Social and economic aspects of machine learning (e.g., fairness, interpretability, human-AI interaction, privacy, safety, strategic behavior)
specifically for strategic behavior. However, I'm not sure this should be called economic aspects *of machine learning* specifically. I'll leave this issue with the area chair---my personal view is that it's not a great match. There are some related papers that have appeared in past conference instances (for instance, on deferred acceptance variants, but with more of a focus on computational complexity of an algorithmic approach, such as https://papers.nips.cc/paper_files/paper/2019/hash/cb70ab375662576bd1ac5aaf16b3fca4-Abstract.html).

Second, I'm concerned about the family preference model in section 4.1. In particular, the title of the paper says "Large Markets," and as the size of the market grows beyond a small geographic area, it seems like that geographic preferences (for nearby daycares) will play a role. However, the random model is based on a single global distribution of preferences that applies to all families across all locations. This distribution is then further constrained to place similar probabilities on all daycares. There is no analysis of the empirical data to justify this uniformity assumption. Additionally, the model assigns independent preferences to two siblings of the same family, which seems to miss a) the fact that a family may have certain specific desires, and b) the family's geo preferences will apply similarly to all children, and c) sending multiple siblings to the same daycare may provide complementarities such as less logistic overhead for transport.
questions: questions: I'd love to hear responses from the authors on the two points I raise in the Weaknesses section above.

A few smaller points:

Line 113: the definition of a matching as mapping from C \cup D to C \cup D seems off -- is the intention to map to C\cup 2^{D}? Also, \mu(c) is a daycare (or a singleton set containing a daycare?), while \mu(d) is a set of children? Maybe I'm missing the structure, but this seems unclear.

Definition 1: what is the motivation for each family to be matched either to a tuple from their preference order or the unassigned tuple? Why is it not preferred to have an assignment for just some children in the family, versus none (d_0,\ldots,d_0)?
limitations: limitations: I think the authors have done a good job here.

Comments: title: Followup on geo
Followup on geo
response to rebuttal
Request for clarification
comment: Thank you for your responses. Should this paper get accepted, I would greatly appreciate including more references to matching with complementaries, even if not directly related. For someone like me who is somewhat familiar with that field but doesn't know all the research, this could be very useful for understanding that your work is truly novel. Just stating these works exist and how they differ from yours is important.
Thank you, your response makes sense, very interesting and I appreciate the discussion.
> My question here is more for the future than an ask for the current paper: is it possible to strengthen the theorem to include a notion of proximity. 

Thank you for your insight. If locations are selected uniformly at random in a unit square, it may result in preferences being uniformly randomly distributed. Thus, we believe that the distribution satisfies Definition 5 (Uniformly Bounded), and our results are applicable. A potential avenue for future research would be to consider a model where locations are deterministically given, and preferences are generated by adding randomness to deterministic preferences based on these fixed locations. In such a scenario, the assumption of a fixed distribution $\mathcal{P}$ (Definition 5: Uniformly Bounded) may not hold.

> Does this characterization sound correct? If so, do you have any sense for which case holds? It seems that the correlation of sibling preferences, compared to the correlation of non-sibling preferences should given an indication of case 1 versus 2?

Currently, we cannot determine the details. For Case 1 (Alignment with Theorem 1), individual municipalities are geographically large with childcare centers in various locations, so preferences might align well with the Uniformly Bounded. On the other hand, for Case 2 (Effectiveness beyond Theorem 1), the algorithm may work effectively beyond this assumption. For instance, in our experiments, when we slightly and adversarially altered family preferences from their current state, stable matchings continued to exist. However, when we made more significant adversarial changes to preferences, there were cases where the ESDA algorithm failed. This suggests that the assumptions in Theorem 1 are somewhat important for the ESDA algorithm.
Regarding your suggestion about comparing the correlation of sibling preferences to non-sibling preferences, we agree that this is significant. In our current model, all family preferences are generated independently. Investigating the correlation could indeed be effective in examining the applicability of the algorithm and understanding the nature of real-world preferences.
Understood about the issue that geo location of families is not available in the dataset (for privacy reasons). And to be clear on the high-order bit, I'm still in favor of accepting this paper. But I'd like to follow up on this a little.

First, I think the authors' final point is a good one. It's not clear (at least to me) that distributed markets with strong geo preferences should be fundamentally easier or harder than markets without -- it's possible that problem instances with strong geo preferences behave like a number of smaller problem instances, one for each geographic region, which is clearly useful structure. Likewise for other forms of family preference.

Next, let's touch on the theoretical discussion (section 4, and in particular, Theorem 1). I believe this is the only place that the assumption that a fixed distribution $\cal P$ is used to seed individual preferences for daycares. Theorem 1 is nice, and seems to me to be powerful compared to earlier results. My question here is more for the future than an ask for the current paper: is it possible to strengthen the theorem to include a notion of proximity. A standard approach, for example, would be to assume households and daycares are located uniformly in a unit square, and that the student preference distribution includes a convenient term based on the distance between the household and the daycare. There is perhaps a loose intuition that for sufficiently large n, the theorem should still hold, as the preferences for the (diverging) number of nearby households will look almost identical, again given $m=\Omega(n)$. This doesn't really need a response -- it's more of a passing observation.

When it comes to the empirical data, here we see the algorithm working very well, and there are two possibilities:
1. The municipalities, for some reason, have family preferences that are inline with Theorem 1, so do not have a strong geo effect or other heterogeneous family preferences. This is interesting because it shows that Theorem 1 aligns with real-world cases.
2. Family preferences are in fact heterogeneous, perhaps for geographic reasons, but the algorithm continues to work well, beyond the bounds of Theorem 1. This is also interesting, because it shows the applicability of the algorithm in practice is broader than the theorem.

Does this characterization sound correct? If so, do you have any sense for which case holds? It seems that the correlation of sibling preferences, compared to the correlation of non-sibling preferences should given an indication of case 1 versus 2?

To summarize, I am supportive, and any additional understanding of the nature of the assumptions in section 4.1 (how much they are required by theorem 1, and how much they entail in practice) only increases my confidence in the generality of the results. Thank you for any additional thoughts on this subject.
Firstly, we do not have access to the geographical information of families, as it is private and confidential. Consequently, we were unable to generate a distribution that incorporates preferences for nearby daycares based on the data sets we have.

Secondly, we followed the approach outlined by Kojima et al. (2013), where the joint preferences of siblings are derived from a random distribution seperately. In this paper, our aim is to understand how common priorities among daycares influence the existence of stable matchings.

Lastly, we fully agree with your observation that the pattern in families’ preferences also impacts the existence of stable matchings. We will address this aspect with a more nuanced analysis in the next phase of our research.
I have read the authors' responses and retain my original assessment.
Thanks to the authors for their response. I didn't fully understand the response to the following question:

----
Second, I'm concerned about the family preference model in section 4.1. In particular, the title of the paper says "Large Markets," and as the size of the market grows beyond a small geographic area, it seems like that geographic preferences (for nearby daycares) will play a role. However, the random model is based on a single global distribution of preferences that applies to all families across all locations. This distribution is then further constrained to place similar probabilities on all daycares. There is no analysis of the empirical data to justify this uniformity assumption. Additionally, the model assigns independent preferences to two siblings of the same family, which seems to miss a) the fact that a family may have certain specific desires, and b) the family's geo preferences will apply similarly to all children, and c) sending multiple siblings to the same daycare may provide complementarities such as less logistic overhead for transport.
----

I'm particular wondering here about a scenario in which the algorithm is applied to a broad area, each family ranks daycares that are within walking distance, versus those that require an hour's drive across the city, and will in many cases prefer a closer one. I believe the random model assumes draws from a global preference distribution of daycares (whether independently drawn for siblings or not), where I would expect the reality to be much closer to a distribution that incorporates preferences for nearby daycares. I may well be misunderstanding something in the model or response -- clarification appreciated.