Fair Matching under Constraints: Theory and Applications

Abstract

This paper studies a general model of matching with constraints. Observing that a stable matching typically does not exist, we focus on feasible, individually rational, and fair matchings. We characterize such matchings by fixed points of a certain function. Building on this result, we characterize the class of constraints on individual schools under which there exists a student-optimal fair matching, the matching that is the most preferred by every student among those satisfying the three desirable properties. We study the numerical relevance of our theory using data on government-organized daycare allocation.

“Didn’t Get a Slot in Day Care. Drop Dead, Japan!!!”

An anonymous mother

1 INTRODUCTION

Daycare services for young children in Japan, as in many countries, are rationed by the government using matching mechanisms, and a large excess demand for daycare seats is a highly contentious political issue. A blog post by an anonymous mother who could not secure a slot in a daycare for her child became viral in 2016, leading to a large protest movement, a debate in Diet, and Prime Minister Abe’s promise to improve the situation (Osaki, 2016; Prime Minister’s Office, 2017). In the midst of such a heated political environment, increasing allocation of slots at daycares in a fair manner is now among the very top priorities for many politicians.

One notable complication of the daycare allocation problem is that the necessary teacher–child ratio varies across different ages. In the Japanese case, for instance, the national regulation requires at least one teacher for every three children of age 0 while the ratios are one teacher for every 6 children for ages 1 and 2, 20 children for age 3, and 30 children for ages 4 and 5 (Cabinet Office of Japan, 2017). This means that each daycare centre’s feasibility constraint cannot be expressed by a mere capacity constraint. In fact, many matching markets are subject to constraints that are beyond the scope of the standard theory. In the medical match in the U.K. in the last century, for example, some hospitals required a cap on the number of women in their workforce (Roth, 1991). In school choice, a school may be subject to diversity requirements (Abdulkadiroğlu and Sönmez, 2003). As discussed in more detail later, many more matching markets with constraints have recently become the subject of research, including problems of refugee resettlement, college admissions with budget constraint, and school choice under bullying concerns.

The aim of this paper is to study a general model of matching with constraints. Framing the problem as matching between students and schools, we seek to understand the theoretical properties of this problem (with an eye on market design—we apply our theory to the daycare allocation problem based on real data from Japan). Instead of considering various special cases one by one, we begin with a very general model. In that model, each school is subject to an arbitrary constraint, which is represented simply by an arbitrary family of subsets of students that are feasible at that school. The standard model with capacity constraints is a special case in which a set of students is feasible at a school if and only if its cardinality is no greater than the school’s capacity, but many more cases fall into the scope of our model.

Given the generality of the constraints, a stable matching does not necessarily exist. In fact, we find that each school’s constraint being a capacity constraint is a “necessary and sufficient” condition for guaranteeing existence (in a certain “maximal domain” sense). Faced with this impossibility result, we focus on a condition weaker than stability. More specifically, we consider a fairness notion which requires there be no justified envy, that is, there be no student who prefers a school to her outcome while another student with lower priority is matched to the school. We require this notion of fairness as well as feasibility and individual rationality as our basic requirements (by contrast, we do not require non-wastefulness, which together with the previous three conditions are equivalent to stability). Our first main result provides a characterization of matchings that satisfy these properties as fixed points of a certain mapping.

Equipped with the fixed-point characterization, we identify the class of constraints that guarantee the existence of a desirable matching. For this goal, we first define a student-optimal fair matching, SOFM. A matching is an SOFM if it satisfies fairness, feasibility, and individual rationality and, in addition, it is weakly preferred by every student to any matching that satisfies fairness, feasibility, and individual rationality. This is analogous to the well-known student-optimal stable matching but adapted to our more general environment where the latter may not exist. We identify a class of constraints on individual schools under which an SOFM exists. Specifically, if the constraint at each school is in a class that we call general upper-bounds, meaning that any subset of a feasible set of students is also feasible, then an SOFM exists. Moreover, if the constraint of even just one school is not a general upper-bound, then there exist student preferences and capacity constraints at other schools such that an SOFM fails to exist. In this sense, general upper-bound is the most permissive restriction on constraints that leads to the existence of an SOFM.

The family of general upper-bounds subsumes many constraints of interest. Standard cases such as capacities and type-specific quotas are examples of general upper-bounds, while floor (minimum) quotas and proportionality constraints are not. While excluding some cases, the family of general upper-bounds includes many less-known or more recent cases. Examples include college admissions with students with disabilities, refugee matching under multidimensional constraints, school choice under bullying concerns, and separation of conflicting groups in refugee matching.

The daycare allocation problem we discussed earlier provides an interesting example to which our theory can be applied. Daycare services are often highly subsidized and regulated in many countries such as most European and Asian countries. In Japan, the assignment of seats in daycare centres for children (of ages 0 to 5) is conducted by each municipality. It is a matching market: prices are set by the municipality, parents report ordinal preferences over daycare centres, and the municipality assigns seats following an algorithm based on reported preferences and pre-specified priorities over the applicants.¹

As discussed earlier, heterogeneity of teacher–child ratio across age groups implies that the constraint at each daycare centre cannot be described by a capacity constraint. Most municipalities, however, treat the number of seats for each age group at each daycare centre as fixed and rigid. This leads to an artificial constraint that is more restrictive than the original daycare constraint since the former fails to take into account the inherent flexibility in the latter. We establish that the original daycare constraint and the rigid constraint are both general upper-bounds, and that the SOFM under the former constraint is Pareto superior to the one under the latter.

We supplement our theoretical investigation by analysing the data we obtained from two municipalities in Japan: Yamagata City and Bunkyo City, which are rural and urban cities in Japan, respectively. First, we compare SOFMs under the original daycare constraint and the rigid constraint. With 250 simulations for each mechanism, we find that the effect of allowing flexibility in constraints is substantial in our data from both municipalities. For example, the average fractions of children who are matched with a strictly preferred daycare centre are 60.35% in Yamagata and 51.64% in Bunkyo, and the numbers of unallocated children decrease by 87.67% and 48.81%, respectively. Second, we compare the SOFMs with the real allocations in those municipalities. The real allocation mechanisms use rigid constraints while eliminating justified envy only within the same age group and tolerating existence of justified envy across different ages. Although theoretically no clear general relation exists between the SOFMs and the real outcomes, we find that the loss from the rigidity in the real allocations overwhelms the efficiency gains resulting from tolerating existence of certain justified envy. For example, the average fractions of children who are matched with a strictly preferred daycare centre in the SOFM under flexible constraints are 16.56% in Yamagata and 25.30% in Bunkyo, while the corresponding numbers for the real allocation are merely 5.02% in Yamagata and 13.61% in Bunkyo. Moreover, the real allocation leaves a significant amount of justified envy: the proportions of applicants who have justified envy toward another applicant are 33.05% in Yamagata and 40.82% in Bunkyo. These results suggest that, relative to the mechanisms that are used in reality, our proposed mechanism may result in a nontrivial improvement in efficiency while eliminating justified envy completely.

In order to guarantee existence, we require fairness while dropping non-wastefulness. Moreover, the fairness notion is strong in a sense because even if a student and a school cannot feasibly match with each other, the student’s envy is still considered justifiable. An alternative would be to drop fairness while maintaining non-wastefulness, or to weaken the fairness notion so that a student’s envy is not justifiable if matching her with the corresponding school results in infeasibility. Which approach is more reasonable depends on applications. In the examples that we have in mind, some waste is tolerated while our fairness notion is considered primarily important. We provide real examples as well as in-depth discussions in, for instance, Remark 1 in Section 2 and Section 6.1.

We study a variety of further issues, including the following topics. First, we show that our theory readily generalizes to the case in which school priorities are weak, which extends the scope of applications to real-life cases such as disaster relief and centralized college admissions. We also study strategic issues. Although the SOFM mechanism is not strategy-proof unless all constraints are capacity constraints (in a maximal domain sense), we show that it is not the drawback of SOFM alone but it is, in fact, shared by every fair mechanism which satisfies feasibility and a mild efficiency requirement. Moreover, we show that the SOFM mechanism satisfies an incentive compatibility property called truncation-proofness, and that the mechanism is difficult to manipulate in large markets in a specific sense. In addition, we analyse the relationship between our general upper-bound and the “multidimensional constraints” studied by Delacrétaz et al. (2016). We also study a relationship with Hatfield and Milgrom (2005) and establish a sense in which our results are not implied by theirs.

1.1. Related literature

First and foremost, this paper contributes to the literature of matching with constraints. We discuss the most relevant related works in various parts of this paper. Other notable studies in this literature include Abdulkadiroğlu (2005), Ergin and Sönmez (2006), and Hafalir et al. (2013) for school choice, Abraham et al. (2007) for a project allocation problem, and Westkamp (2013) and Aygun and Turhan (2016) for college admissions. Importantly, these papers study specific classes of constraints motivated by their intended applications. In a sharp contrast, the present paper starts with a fully general class of constraints and finds conditions on constraints under which desirable matchings and mechanisms exist. These approaches are complementary to each other.

There is another strand of literature on matching with certain constraints that shares a broad motivation with our work while differing in several crucial aspects. Inspired by medical residency matching in Japan, Kamada and Kojima (2015) study a stable matching problem in which the number of doctors who can be matched to hospitals in each region is subject to a constraint. Alternative solution concepts are studied by Kojima et al. (2018) and Goto et al. (2014), while more general constraints are studied by Biró et al. (2010), Kamada and Kojima (2017, 2018), and Goto et al. (2017). In particular, general upper-bound may be reminiscent of a condition called heredity studied by Goto et al. (2017) and Kamada and Kojima (2017). While sharing broad motivation, there are at least two major differences between these studies and ours. First, they study constraints imposed jointly on subsets of institutions (e.g. hospitals or schools) while our paper considers constraints imposed separately on individual institutions. Second, they restrict attention to constraints over the numbers of individuals in different institutions, while the present paper allows constraints to depend on the identity of the individuals. Due to these modelling differences, these two lines of works differ in many dimensions including scopes of applications, desirable properties considered, methods used, and obtained results. In particular, some of the papers cited here make use of the results from Hatfield and Milgrom (2005), while the results in the present paper cannot be obtained from that paper (see Appendix C.2).

Although not as closely related, there is also a recent literature on pure object allocation under constraints. Milgrom (2009) and Milgrom and Segal (2014) consider auction mechanisms under constraints, while Budish et al. (2013) analyse the problem of implementing lotteries for stochastic object allocation under constraints. The latter analysis has been extended in various directions by Che et al. (2013), Pycia and Ünver (2015), Akbarpour and Nikzad (2017), and Nguyen et al. (2016). These papers are different from ours in that they are primarily concerned with pure object allocation. Moreover, they do not consider elimination of justified envy, our central concern.

Our existence theorem relies on Tarski’s fixed point theorem. This theorem has been used to find a stable matching in the literature such as Roth and Sotomayor (1988), Adachi (2000), Fleiner (2003), Echenique and Oviedo (2004, 2006), Hatfield and Milgrom (2005), Echenique and Yenmez (2007), Ostrovsky (2008), Hatfield and Kominers (2017) and Wu and Roth (2018). Given that our solution concept of fairness is different from stability, the fixed-point mapping we employ is different from those used in the existing research, and existing approaches do not work.² In particular, as we mentioned earlier, Appendix C.2 establishes a precise sense in which the existing method of Hatfield and Milgrom (2005) cannot be used to obtain our results.

Elimination of justified envy is a standard fairness requirement in the literature of school choice (Balinski and Sönmez, 1999; Abdulkadiroğlu and Sönmez, 2003). Tolerating some waste is less standard but becoming more common, perhaps due to difficulty (or even impossibility) of eliminating both waste and justified envy. Feasible, individually rational, and fair (but possibly wasteful) matchings are studied by Sotomayor (1996) and Blum et al. (1997) for one-to-one matching, Wu and Roth (2018) for many-to-one matching, Delacrétaz et al. (2016) for matching with multidimensional constraints, Kesten and Yazici (2012) for a setting in which all students are in the same priority class with one another at all schools, and Biró (2008), Fleiner and Jankó (2014), and Biró and Kiselgof (2015) for many-to-one matching with weak priorities. Our paper subsumes the settings of all these papers, so our results directly apply to their environments.

A small but rapidly growing literature has recently analysed the allocation of daycare seats, one of the applications of the present paper. Motivated by the practice in Denmark, Kennes et al. (2014) study the issue of dynamic stability arising from the overlapping-generations structure of children’s composition in daycare centres. Veski et al. (2017) study the effect of changes in priorities in the context of kindergarten allocation practices in Estonia. In a more descriptive work, Herzog and Klein (2018) discuss a variety of policy issues in childcare systems in several German municipalities. While sharing the interest in application of matching theory to childcare, the overlap with our paper is rather tangential; none of these papers analyses the problem of constraints, the primary focus of the present work. A recent paper by Okumura (2019) is motivated by the daycare seat assignment in Japan and considers the issue of flexible allocation across ages, although his solution concept does not require our fairness concept and none of his results implies ours, and vice versa.³

Lastly, this paper is part of the growing literature on matching theory and market design. Ever since the seminal contribution by Gale and Shapley (1962), matching theory proved to be a source of fruitful insights. What is especially remarkable is its use in applications to market design. Research in this field has been successfully applied to various problems such as medical match (Roth, 1984; Roth and Peranson, 1999), school choice (Balinski and Sönmez, 1999; Abdulkadiroğlu and Sönmez, 2003), organ donation (Roth et al., 2004, 2005, 2007) and course allocation (Sönmez and Ünver, 2010; Budish and Cantillon, 2012), among others.

The remainder of this paper proceeds as follows. Section 2 introduces our model. In Section 3, we provide a fixed-point characterization of matchings that satisfy feasibility, individual rationality, and fairness. Based on that result, Section 4 identifies a necessary and sufficient condition for the existence of an SOFM. Turning to numerical analysis, in Section 5, we conduct simulations to quantify the welfare gains of relaxing constraints based on real data on the allocation of slots at daycare centres. Then, Section 6 provides a number of discussions. We conclude in Section 7. All proofs that are not in the main text are found in the appendix. Information on the datasets is found in Yamagata City (2017) and Bunkyo City (2017), and details on the codes for simulations are found in Kamada and Kojima (2021).

2 MODEL

Let there be a non-empty finite set of students I and a non-empty finite set of schools S. Each student i has a strict preference relation $≻i$ over the set of schools and being unmatched (being unmatched is denoted by $∅$⁠). For any $s,s′∈S∪{∅}$⁠, we write $s⪰is′$ if and only if $s≻is′$ or $s=s′$⁠. Each school s has a strict priority order $≻s$ over the set of students (note that we assume all schools regard all students as acceptable). For any $i,i′∈I$⁠, we write $i⪰si′$ if and only if $i≻si′$ or $i=i′$⁠. We denote by $≻I=(≻i)i∈I$ the profile of all students’ preferences, and by $≻S=(≻s)s∈S$ the profile of all schools’ priority orders. When there are three students i, $i′$⁠, and $i″$⁠, for example, we write

to mean that student i is of the highest priority, $i′$ is of the second-highest priority, and $i″$ is of the lowest priority at s. School s is said to be acceptable to student i if $s≻i∅$⁠. We write, for example,

to mean that school s is the most preferred, $s′$ is the second most preferred, and s and $s′$ are the only acceptable schools under preferences $≻i$ of student i.

Each school s is subject to a constraint. A constraint at school s is a nonempty collection $Fs⊆2I$ of sets of students. Denote $FS=(Fs)s∈S$⁠. We say that a subset $I′⊆I$ is feasible at s if $I′∈Fs$ and it is infeasible otherwise.

We refer to a tuple $(I,S,≻I,≻S,FS)$ as a problem.

A matching  $μ$ is a mapping that satisfies (i) $μi∈S∪{∅}$ for all $i∈I$⁠, (ii) $μs⊆I$ for all $s∈S$ and (iii) for any $i∈I$ and $s∈S$⁠, $μi=s$ if and only if $i∈μs$⁠. That is, a matching simply specifies which student is assigned to which school (if any).

Let us define a few basic terms. First, a matching $μ$ is feasible if $μs∈Fs$ for each $s∈S$⁠. Second, a matching $μ$ is individually rational if $μi⪰i∅$ for each $i∈I$⁠. That is, no student is matched with an unacceptable school. Third, we say that i  has a justified envy toward  $i′$ if there exists $s∈S$ such that $s≻iμi$⁠, $i′∈μs$ and $i≻si′$⁠. We say that a matching $μ$ is fair if there exist no students i and $i′$ such that i has a justified envy toward $i′$ (see Remark 1 for a discussion). Fourth, a matching $μ$ is non-wasteful if there is no pair $(i,s)∈I×S$ such that $s≻iμi$ and $μs∪{i}$ is feasible at s.⁴ Finally, a matching $μ$ is said to be stable if it is feasible, individual rational, fair, and non-wasteful.

As we will see in Example 1, there may not exist a stable matching. For this reason, we will weaken our desiderata by dropping non-wastefulness, while still requiring fairness. The following concept will be of particular interest.

 

Given $(I,S,FS)$⁠, a mechanism φ is a function that maps preference profiles to matchings for each profile of priority orders. The matching under φ at students’ preference profile $≻I$ and priority profile $≻S$ is denoted $φ≻S(≻I)$⁠, and student i’s match is denoted by $φi≻S(≻I)$ for each $i∈I$⁠.

In $(I,S,FS)$⁠, a mechanism φ is said to be strategy-proof if there do not exist a profile of priority orders $≻S$⁠, a profile of students’ preferences $≻I$⁠, a student $i∈I$⁠, and preferences $≻i′$ of student i such that

An interpretation is that, for each realized preference profile for all students, each student simultaneously reports their preferences to the mechanism. Strategy-proofness requires that, in this game, reporting their true preferences is an optimal strategy for each student, irrespective of the reporting by the other students. In other words, no student has an incentive to misreport her preferences under the mechanism.⁵

3 FIXED-POINT CHARACTERIZATION OF FAIR MATCHINGS

This section studies matchings that satisfy the desirable properties introduced in the last section. More specifically, we characterize all the matchings that satisfy fairness, individual rationality, and feasibility by fixed points of a certain function on a finite (and hence a complete) lattice. We later use this result to study the existence and structure of matchings that satisfy these properties.

Our first observation is that there does not necessarily exist a stable matching.

(Non-existence of a stable matching)

    

Roughly, the theorem characterizes the set of fair matchings (along with feasibility and individual rationality) as the set of fixed points of the mapping T. Note that the theorem does not impose any restriction on the form of constraints, besides non-emptiness. In particular, we do not assume that constraints are general upper-bounds, which is formally defined in the next section. We use this result in the next section to study existence of SOFM.

 

4 GENERAL UPPER-BOUND AND SOFM

This section studies the existence and structure of matchings that satisfy fairness, individual rationality, and feasibility. More specifically, we establish a tight relationship between the existence problem and the nature of the constraints. We show that the class of general upper-bounds characterizes the situations in which an SOFM is guaranteed to exist.

4.1 General Upper-Bound

 

That is, a constraint at school s is a general upper-bound if, for any set of students that is feasible at s, every subset of it is also feasible. Note that if a constraint $Fs$ is a general upper-bound then $∅∈Fs$ must hold. This is because non-emptiness of $Fs$ implies existence of some $I′⊆I$ such that $I′∈Fs$⁠, and we have $∅⊆I′$⁠.

A special case of a general upper-bound is a capacity constraint: a constraint $Fs$ is a capacity constraint if there exists an integer $q∈N$ such that, for any $I′⊆I$⁠, $I′∈Fs$ if and only if $|I′|≤q$⁠. Let us provide real-life examples of constraints to discuss the applicability of general upper-bound as well as its limitation.

• (1)

  Diversity in school choice (type-specific quotas): Many school districts require certain diversity of the student body at each school. A common way in the literature to formalize this requirement is to impose type-specific quotas (Abdulkadiroğlu and Sönmez, 2003).¹³ Specifically, we require a constraint $Fs$ to satisfy the following: There exist a partition of the students $I:=⋃t∈TIt$ with an index set $T$ (with $It∩It′=∅$ if $t≠t′$⁠) and integers $q∈N$ and $qt∈N$ for every $t∈T$ such that, for any $I′⊆I$⁠, $I′∈Fs$ if and only if $|I′|≤q$ and $|I′∩It|≤qt$ for every $t∈T$⁠. Because $I″⊆I′$ and $I′∈Fs$ imply $|I″|≤|I′|≤q$ and $|I″∩It|≤|I′∩It|≤qt$ for every $t∈T$⁠, this constraint is a general upper-bound.

• (2)

  College admissions with students with disabilities (budget constraints): In college admissions, it is widely recognized that students with disabilities incur more cost to the university. For example, The University of Oxford’s admissions website mentioned in Remark 1 describes a variety of accommodation and financial assistance they offer to students with disabilities. One way to model this setup is through a budget constraint. Formally, assume that each student i is associated with cost $ci∈R+$ and say that constraint $Fs$ is a budget constraint if there exists $b∈R+$ such that, for any $I′⊆I$⁠, $I′∈Fs$ if and only if $∑i∈I′ci≤b$⁠. College admissions with students with disabilities could be modelled as a situation in which students with disabilities have higher cost than those without disabilities. Budget constraint is not necessarily a capacity constraint as seen in Example 1, but it is clearly a general upper-bound because $I″⊆I′$ and $I′∈Fs$ imply $∑i∈I″ci≤∑i∈I′ci≤b$⁠.

  Cases of budget constraints in college admissions may also arise in different contexts (Biró et al., 2010; Abizada, 2016). For example, a wide variety of universities commit to so-called “need-blind admission,” where admission decisions are made without regard to applicants’ financial situations. Yet, a college may be subject to a budget constraint. Because different students may need different amounts of financial aid, the constraint cannot be described as a capacity constraint in general, but it is a budget constraint and hence a general upper-bound.

• (3)

  Refugee match (multidimensional constraints): There are many refugees seeking resettlement across the world. As of the end of 2016, there were 22.5 million refugees worldwide (United Nations High Commissioner for Refugees, 2017), and the number is growing. Given such an impending situation, authorities in many countries are faced with the task of matching refugee families to different localities. One of the requirements in this problem is to match all members of a family to the same place. In addition, different refugee families need different kinds of services such as job training, language class, and so on. Given the available resources of a locality, variations in family size and needs for different types of resources imply that the constraint is not necessarily a capacity constraint. This type of constraint is called multidimensional constraints and studied by Delacrétaz et al. (2016).¹⁴  Appendix C.1 formally analyses this model and shows that, among other things, this constraint is a general upper-bound.

• (4)

  Anti-bullying school choice design: Bullying has a negative effect on the victim academically as well as mentally. It is a concern in many countries, and governments take measures to address this issue. Motivated by such a concern, Kasuya (2016) considers anti-bullying policies in the context of school choice design. Specifically, he analyses a requirement that, no pair of a bully and his or her victim be placed in the same school. To express this formally as a constraint, let $B⊆I×I$ be the set of bullying incidents, meaning that $(i,j)∈B$ implies that “i has bullied j.” The constraint at each school s (ignoring other types of constraints such as the school’s capacity for simplicity) can be expressed as $Fs={I′⊆I|(i,j)∈B⇒{i,j}⊈I′}$⁠. This is a general upper-bound because $I″⊆I′$ and ${i,j}⊈I′$ imply ${i,j}⊈I″$⁠, hence $I′∈Fs$ implies $(i,j)∈B⇒{i,j}⊈I″$⁠.

• (5)

  Separating conflicting groups in refugee match: Separating different types of individuals may be important not only in the bullying context, but also in other applications. For example, in refugee match, authorities are concerned that refugees from conflicting religious or ethnic groups may fight with each other in refugee shelters if they live close to each other. The policy to separate them by placing them in different locations is used or being considered as a temporary, if not permanent, solution (Breitenbach, 2015). To model this policy formally as a constraint, assume that there exists a partition of the students (refugee families in this context) $I:=⋃t∈TIt$ with an index set $T$ (with $It∩It′=∅$ if $t≠t′$⁠) and, for any $I′⊆I$⁠, $I′∈Fs$ if and only if there exists $t∈T$ such that $I′⊆It$⁠. This is a general upper-bound because $I″⊆I′$ and $I′∈Fs$ imply there exists $t∈T$ such that $I″⊆I′⊆It$⁠.

• (6)

  Daycare allocation: In many countries around the world, assignment of daycare seats for small children is organized by the (local) government through a matching mechanism. There are often legal restrictions on a teacher–child ratio at each daycare centre. Since such a ratio varies across different ages of children, the constraints implied by these regulations cannot be described by capacity constraints. In Section 5, we show that they can be described as general upper-bounds and study the data of daycare allocation in Japan, where finding a desirable allocation in the face of this non-capacity general upper-bound has become a pressing practical issue (Okumura, 2019).

Of course, not all constraints of interest are general upper-bounds. The following are some of the examples.

• (1)

  Floor constraints: Floor constraints may appear in a variety of environments. For example, in school choice, a school may need at least a certain number of students in order to organize group activities, have students interact with one another, or simply to operate efficiently enough given the fixed costs. Formally, the constraint $Fs$ at each school s (ignoring other types of constraints such as the capacity of the school) is that there exists an integer $q≥1$ such that, for any $I′⊆I$⁠, $I′∈Fs$ if and only if $|I′|≥q$ (Ehlers et al., 2011; Fragiadakis et al., 2012; Fragiadakis and Troyan, 2017). This is not a general upper-bound because any $I′⊆I$ with $|I′|≥q$ is in $Fs$ but, for instance, $∅$ is a subset of $I′$ but $|∅|=0<q$⁠. Similarly, a type-specific floor constraint, i.e. a constraint in which at least a certain number of students of specific types are needed for feasibility, is not a general upper-bound.

• (2)

  Proportionality constraints: As mentioned earlier, a common requirement in matching markets is to achieve certain balance of workforce or student body. Such a requirement is sometimes expressed in terms of proportion. For instance, in the public school district of Cambridge, Massachusetts in 2003, the proportion of students from low socioeconomic status families was required to be within a range of 15% of the district-wide proportion (Nguyen and Vohra, 2017). A constraint $Fs$ is a proportionality constraint (Nguyen and Vohra, 2017) if there exist a partition of the students $I:=⋃t∈TIt$ with an index set $T$ (with $It∩It′=∅$ if $t≠t′$⁠) and numbers $αt,βt∈[0,1]$ for every $t∈T$ with $αt≤βt$ and $∑t∈Tαt≤1≤∑t∈Tβt$ such that, for any $I′⊆I$⁠, $I′∈Fs$ if and only if $αt|I′|≤|I′∩It|≤βt|I′|$ for every $t∈T$⁠. This is not necessarily a general upper-bound because any $I′⊆I$ with $αt|I′|≤|I′∩It|≤βt|I′|$ for every $t∈T$ is in $Fs$ but, for instance, $I″:=I′∩It$ for any $t∈T$ is a subset of $I′$ while $|I″∩It|=|I″|>βt|I″|$ if $βt<1$ and $I″≠∅$⁠, so $I″∉Fs$⁠.

We do not necessarily assert that real-market constraints are general upper-bounds in all or even most applications. In fact, the two examples of constraints shown just above are demonstrably not general upper-bounds. Instead, our study aims to characterize the situations, in terms of restrictions on constraints, under which a solution with desirable properties exists. As shown in Section 4.2, it turns out that general upper-bound is necessary and sufficient for guaranteeing the existence of such a solution.

4.2 Existence of SOFM

Equipped with Theorem 1, our approach is to study the desirable matchings by way of analysing the fixed points of the cutoff adjustment function T. Our first observation is, though, that under general upper-bounds, the existence of a matching satisfying fairness as well as feasibility and individual rationality is trivial; an empty matching, i.e. a matching with $μi=∅$ for each $i∈I$⁠, satisfies all the properties above.¹⁵ Since an empty matching is typically highly inefficient, this example also suggests that only requiring the above three conditions may not lead to a desirable outcome for students. To the extent that we care about student outcomes, an interesting question is whether one can identify a fair matching that is desirable in terms of welfare. The next theorem answers this question in the affirmative.

   

Proof of Claim 1 .

 

To complete the proof of the theorem, let $p*$ be the smallest fixed point of the function T, whose existence is guaranteed by Claim 1. By the first part of Theorem 1, $μp*$ is a feasible, individually rational, and fair matching. Take an arbitrary matching $μ$ that is feasible, individually rational, and fair. By the second part of Theorem 1, there exists a fixed point p of T such that $μ=μp$⁠. By the relation $p*≤p$ and the definition of $Ds(⋅)$ for each $s∈S$⁠, the equality $μ=μp$ implies that $μip*⪰iμi$ for each student $i∈I$⁠. Hence we have shown that $μp*$ is an SOFM, completing the proof.

(Implication of Theorem 2 )

 

The proof of Theorem 2 is based on Tarski’s fixed point theorem. This proof method implies that the set of fair matchings (along with feasibility and individual rationality) has a lattice structure under general upper-bounds. It also implies that a simple algorithm can be used to find the SOFM under such constraints, building on the cutoff adjustment function T. Consider the following algorithm, called the cutoff adjustment algorithm:

• •

  Step 0: Let $p0:=(1,1,…,1)$⁠.

• •

  Step $t≥1$⁠: Let $pt=T(pt−1)$⁠. If $pt=pt−1$⁠, terminate the algorithm and define the outcome as the matching $μpt$⁠.¹⁷ Otherwise, go to step $t+1$⁠.

The cutoff adjustment algorithm is well-defined (i.e. it terminates in a finite number of steps). To see this, first note that since $p≤T(p)$ for any $p∈P$ by the definition of T and the fact that $∅∈Fs$ for each $s∈S$ under general upper-bound, we have $pt−1≤pt$ for every positive integer t. Because P is a finite set, $pt*−1=pt*$ for some finite $t*$⁠.¹⁸

To see that this algorithm produces the SOFM, note that $p*:=pt*−1=pt*$ satisfies $p*=T(p*)$⁠, i.e.  $p*$ is a fixed point of T. Moreover, for any fixed point $p′$ of T, we have $p0≤p′$ by definition of $p0$⁠, so $p*=Tt*(p0)≤Tt*(p′)=p′$⁠, implying that $p*$ is the smallest fixed point of T. Since the matching corresponding to the smallest fixed point of T is the SOFM (see the proof of Theorem 2 for details), the outcome produced by this algorithm is the SOFM. Thus, we have established the following result:

 

Under capacity constraints, a standard way to find a stable matching is the deferred acceptance algorithm. In Section 6.4, we present a generalization of the deferred acceptance algorithm which finds the SOFM under a general upper-bound and compare it with the cutoff adjustment algorithm.

As mentioned earlier, the class of general upper-bounds subsumes many practical cases, but there are some constraints that are not general upper-bounds, such as floor constraints. A question of interest, then, is whether the conclusion of Theorem 2 holds without the assumption of general upper-bound. The following result offers a sense in which the answer to this question is negative.

 

This result shows that the class of general upper-bounds is a “maximal domain,” providing a sense in which Theorem 2 cannot be generalized further. In other words, general upper-bound is the most permissive restriction on constraints imposed on individual schools (as long as the capacity constraints are included) which guarantees the existence of an SOFM. Even if an SOFM is a desirable outcome, the policy maker cannot expect to always find an SOFM unless the constraints of each school is a general upper-bound. This finding may shed light on the non-existence and impossibility results in the literature. Settings with those negative results include floor constraints (Biró et al., 2010; Ehlers et al., 2011; Fragiadakis et al., 2012; Fragiadakis and Troyan, 2017) and proportionality constraints (Nguyen and Vohra, 2017). These constraints are not general upper-bounds as pointed out in Section 4.1.

 

5 ALLOCATION OF DAYCARE CENTRE SLOTS

This section describes the problem of allocating slots at daycare centres, “daycare allocation,” as an application of our theory. Then we conduct numerical analysis based on unique datasets on daycare allocation we obtained to study the numerical impact of allowing flexibility in constraints.

5.1 Background and institutional detail

Child care services are often highly subsidized and regulated in many countries. Some Scandinavian countries such as Sweden regard daycare service as parents’ right and guarantee a seat in some, albeit not necessarily the parents’ first choices, daycare centre. At the other end of the spectrum are countries such as the U.S., in which a typical daycare centre is run by a private provider and financed by tuitions from parents, though with regulations. Some countries such as Japan lie between these extremes: daycare services are highly subsidized and regulated, but at the same time a slot at a daycare is not guaranteed for parents. In many of those countries, the supply of slots at daycares is very limited, leaving a large number of applicants unmatched and thus making allocation of slots at daycares an especially big concern for parents.

Japan provides a good example of the large excess demand for daycare seats. Recently, a blog post titled “Didn’t Get a Slot in Day Care. Drop Dead, Japan!!!” by an anonymous mother became viral, leading to a large protest movement. The blog post made its way into debates in the National Diet, forcing prime minister Abe to respond to the complaint (Osaki, 2016), with him later promoting various policies to increase child care capacity by more than 300,000 in 5 years (Prime Minister’s Office, 2017). The above blog title was chosen as one of the top ten “New Words and Buzzwords” of 2016, although the organizers admitted to uneasiness about selecting what is essentially a swear word (Kikuchi, 2016). In the midst of such a heated political environment, increasing the number of allocated slots at daycares in a fair manner is now among the very top agendas for many politicians; For instance, mayors of all ten most populous municipalities list daycare policy as one of their major political agendas. As we illustrate shortly, our theory may prove useful for daycare allocation problems with excess demand. For this purpose, we describe daycare allocation in Japan in some detail below.

In Japan, daycare centres serve children aged between 0 and 5 as of the beginning of a new academic year, and the assignment of seats in daycare centres is under the authority of each municipality.²¹ A number of features of this market make it an unusually good subject of application of matching theory. First, daycares are heavily subsidized, with the tuitions and fees set by each municipal government at a low level, leading to excess demand in many municipalities.²² Given the excess demand, municipalities ration slots in daycare centres based on an algorithm. In fact, parents literally report ordinal preferences over daycare centres.²³ Moreover, while in principle a child could start attending a daycare at any time of the year, almost all seats are allocated for the beginning of the academic year, which is April in Japan. Thus, unlike in some other matching problems such as organ allocation, it appears to be a good approximation to treat each year’s allocation as a single static problem, just as is assumed in the present paper (as well as in most matching theory research in school choice and labour markets). Another aspect of daycare allocation in Japan is that, faced with high demand for daycare seats and resulting rationing, many municipalities follow formal assignment rules (the most popular are versions of serial dictatorship and the “Boston” mechanism).

For our purpose, three aspects of this market are especially important. First, the assignment rules are based on reported preferences as well as priorities, where the latter are determined by applicant characteristics such as whether parents have full-time jobs and whether the parent is a single parent, among others. Second, the national regulation requires the teacher–child ratio be at least one teacher for every three children of age 0 while the ratios are one teacher for every 6 children for ages 1 and 2, 20 children for age 3, and 30 children for ages 4 and 5 (Cabinet Office of Japan, 2017).²⁴ While such a constraint is clearly not the traditional capacity constraint as per-capita resources needed to care for a child varies across the child’s age, it is a general upper-bound and hence our theory implies an SOFM exists in this problem. Third, even though the true constraint itself is not a capacity constraint, most municipalities treat the number of seats at each daycare centre for each age as fixed and non-transferable across different ages, thus effectively setting an artificial capacity constraint.

One might wonder if teachers specialize in certain ages and cannot be moved across different age groups. In Japan, however, the license to work as a daycare teacher is not associated with any specific age groups. Furthermore, as illustrated in the next paragraph, municipalities indeed treat teachers as transferrable across different age groups.

One might also think that implementing non-capacity constraints is unrealistic from the administrative point of view. Quite the contrary, faced with great pressure to improve daycare allocation, some municipalities have been experimenting with making the allocation “more flexible” by relaxing the artificial capacity constraint in one way or another. Specifically, they have introduced policies to have daycare centres with excess supply of seats for certain ages admit more children of ages with excess demand, although in ad hoc manners.²⁵ Such policies could be quite effective if designed and implemented well. In fact, due to a variety of institutional features, it turns out that even highly demanded daycare centres often have some vacancies for older children while having excess demand for younger children. For example, Suzuki (2018) points out that about 190,000 seats (across all ages and including both accredited and non-accredited daycares) were vacant in Japan as of 2017, and attributes a significant part of this figure to the excess supply of seats for older children.

To proceed formally, let there be a set of ages $T$ and for each $t∈T$⁠, let there be a teacher–child ratio $rt$⁠. The interpretation is that if one teacher can watch up to n children of age t, then $rt=1/n$⁠. A constraint $Fs$ is a daycare constraint if there are a number $ms$ (representing the number of teachers) and a partition of the students (children in this context) $I:=⋃t∈TIt$ (with $It∩It′=∅$ if $t≠t′$⁠) such that, for any $I′⊆I$⁠, $I′∈Fs$ if and only if

Because $I″⊆I′$ implies $|I″∩It|≤|I′∩It|$ for every $t∈T$⁠, this constraint is a general upper-bound. In our personal communication, a city official verified that this inequality is the correct way to interpret the legal requirement.

Despite the fact that the constraint is as described in inequality (5.1), municipalities often operationalize it by having their assignment based on a more restrictive constraint. We say that a constraint $Fs′$ is a rigid constraint associated with $Fs$ if there exists a number $qt$ for each age $t∈T$ such that $∑t∈Trtqt≤ms$⁠, where for any $I′⊆I$⁠, $I′∈Fs′$ if and only if $|I′∩It|≤qt$ for every $t∈T$⁠. Note that the latter is a special case of the constraint of type-specific quotas discussed in Section 4.1, with an additional property that the capacity for the number of students in the entire school s is not binding.²⁶

5.2 Theoretical preparation

We are interested in the impact of applying SOFM in practice. In preparation for numerical analysis, this section provides theoretical results (which we will later quantify with data).

We first analyse the effect of allowing flexibility in seat allocation across different ages. To isolate the effect of flexibility, for this exercise, we fix the studied mechanism to be the SOFM. The following observation is of interest even though it is straightforward to show:

 

In words, the first part of this proposition shows that relaxing constraints leads to a Pareto improvement of student outcomes. The second part shows that, in particular, the set of unmatched students becomes weakly smaller in the set inclusion sense as the constraints are relaxed. This proposition, while being a very simple (perhaps trivial) observation, may be of interest in practice. This shows that a policy maker may be able to improve the welfare of the market participants if she relaxes the constraints, say by devoting more resources or simply by lifting some regulations. While this seems intuitive and hardly surprising, it is worth noting that it is a Pareto improvement for students. In other words, relaxing constraints does not create any distributional trade-offs and makes every student weakly better off.

To put this proposition into perspective, let us mention a comparative statics result due to Konishi and Ünver (2006).²⁷ The latter result states that, under capacity constraints, when the capacity of each school increases, every student becomes weakly better off at the student-optimal stable matching. Because the SOFM reduces to the student-optimal stable matching under capacity constraints (see Section 6.5 for a formal definition and analysis), Proposition 2 is a generalization of the result of Konishi and Ünver (2006) to the cases in which constraints are not necessarily capacity constraints.

To apply Proposition 2 to our daycare allocation problem, we compare the SOFM under the daycare constraint (henceforth “flexible SOFM”) and the SOFM under an arbitrary rigid constraint associated with that daycare constraint (henceforth “rigid SOFM”). Since the relaxation from “rigid” constraints to “flexible” ones satisfies the hypothesis of Proposition 2 in the context of daycare allocation, we obtain the following corollary.

 

Another theoretical issue we study involves an efficiency property of SOFM. Due to the insistence on fairness, one may wonder if the SOFM results in severe inefficiency. We next address this concern by providing upper bounds on a measure of inefficiency.

Formally, given $≻I$⁠, let $MIR$ be the set of individually rational matchings and, for each matching $μ$⁠, let $|μ|=∑s∈S|μs|$⁠. We define the waste of a feasible matching $μ∈MIR$ under $(≻I,FS)$ by

In words, the waste of a matching is the maximum number of additional students who can be matched to schools without displacing any existing students or violating feasibility or individual rationality.

Let $W¯(FS)=∑s∈Sw¯s(Fs)$⁠, where for each $s∈S$⁠,

when the set on the right-hand side is nonempty, and 0 otherwise. To illustrate this notion, recall that we allow for general constraints beyond capacity constraints. Thus, it is possible that one student cannot be feasibly matched to the school s in addition to existing students $I′$ while some other n students can. The measure $w¯s$ is the maximum of n across all $I′$⁠. The measure $W¯$ is the sum of $w¯s$ for all schools. The following proposition demonstrates that the function $W¯$ provides an upper bound of the waste.

 

We note that there is a sense in which the bound in Proposition 3 is tight. To see this, consider a problem with one school s. For any general upper-bound constraint $Fs$⁠, there exist a priority and a preference profile such that the waste of SOFM is exactly equal to the bound $w¯s(Fs)$⁠.²⁸

In the daycare matching application, it is theoretically possible—in the worst case—to have large waste under the SOFM mechanism.²⁹ This worst case, however, is based on a particular preference and priority structure such that, at each school s, a 0-year-old child is the highest in the priority among those who are rejected, and there is a set $I~s$ of nine (or more) 4- or 5-year-old children who are also rejected, where $I~s$ and $I~s′$ are disjoint if $s≠s′$⁠.

Such a preference and priority structure strikes us as highly unlikely, and thus we present an upper bound for the waste for each given preference and priority structure.³⁰ Formally, let $W^(≻I,≻S,FS):=∑s∈Sw^s(≻I,≻S,FS)$⁠, where for each $s∈S$⁠,

To explain, $w^s$ is the highest number of unmatched students at the SOFM who can be profitably added to school s without violating the feasibility constraint. The measure $W^$ is the sum of $w^s$ for all schools. The next proposition establishes that $W^$ provides an upper bound of the waste and finds its relation with the other bound $W¯$⁠.

 

The first part implies that $W^$ serves as an upper bound for the waste under the SOFM. To obtain the intuition for this result, we note that the only difference between the waste at the SOFM and $W^$ is that the latter may “count” the same unmatched student multiple times if she regards multiple schools with vacancy as acceptable. The second part compares the two bounds, where we show the bound $W¯$ is looser than $W^$⁠. This is because $W¯$ does not use any information about priority or preferences. We note that Proposition 3 is a corollary of these two results.

While Corollary 1 is unambiguous about the direction of welfare change for students when the constraints change, it is silent about the magnitude of the welfare improvement. Similarly, Proposition 3 does not provide the actual waste in a given application, merely offering its bounds. Proposition 4 refines the bound, but whether that bound is large or small in applications is not clear from the general expression (5.3). For better quantification, we next study real-life data of daycare allocation.

5.3 Data and simulations

We use administrative data on daycare seat allocation obtained from Yamagata City and Bunkyo City in Japan. Yamagata City is the prefectural capital of Yamagata prefecture in the northeastern part of Japan, with about 250,000 residents as of 2018. Bunkyo City is one of the 23 special districts of Tokyo. It has about 230,000 residents as of 2018 and has a population density 30 times larger than that of Yamagata City. Compared with Yamagata, Bunkyo City is much more urban, has a higher concentration of educational institutions, and attracts many more dual-income families investing heavily in education and demanding childcare, which seems to make its daycare allocation problem more pressing. Despite such a difference, it turned out that the results of the simulations for these two municipalities resemble each other. For this reason, we only detail the result from Yamagata City here, while providing the results for Bunkyo City in the Appendix B. Our data involve applicants (who are anonymized), usually parents, representing children who would begin attending the daycare in April of 2018. There were 1,437 applicants aged between 0 and 5 as of 1 April 2018 on which they would begin attending the daycare. There were 442, 469, 195, 211, 63, and 57 children in ages 0, 1, 2, 3, 4, and 5, respectively. For each applicant, the data show her reported preferences over the daycare centres and priority ranking (the priorities are common across daycare centres). The average length of the reported preference ranking is 4.52. The priority order is based on the applicant characteristics such as parents’ job status and the number of adults available for care at home. In fact, Yamagata City (2019b) discloses the explicit formula that converts relevant characteristics of each family to the (common) priority ranking. There are 93 daycare centres in our dataset. For each daycare centre, the data show how many seats are supplied for each age (under the rigid constraint).³¹ The total number of seats supplied is 1682. Finally, the dataset contains the matching produced by Yamagata’s mechanism, which we call the “actual allocation.”

Regarding reported preferences, we note that the mechanism in Yamagata is based on serial dictatorship (with no restriction on the number of daycares that can be listed).³² Strategy-proofness of serial dictatorship appears to be fairly well understood in practice, which gives some justification for treating reported preferences as true preferences. A popular how-to book for parents (Habu, 2016), for example, compares strategic properties of serial dictatorship with those of Boston mechanism as follows (these two mechanisms are the most popular mechanisms for daycare allocation in Japan). “In the first mechanism [serial dictatorship], …there is no advantage or disadvantage associated with your stated first choice, while in the second mechanism [Boston mechanism], …if you list a competitive daycare centre as your first choice, the probability that you will be admitted by no daycare centre can increase.”

In our simulation, we made several modelling choices given data limitations. First, the data we have involve ties although the actual priority order is strict. This is because our data lack information on some characteristics used by Yamagata to determine the strict order, such as whether the child is currently in an alternative form of childcare and whether the family has a member with disability. Given the absence of further information, we randomly break ties using a single tie-breaking rule according to the uniform distribution; Note that priorities are common across daycare centres in practice in Yamagata, and our single tie-breaking rule replicates such a property. For each mechanism that we consider, we conducted 250 runs of simulations, with each run corresponding to a realization of the tie-broken priorities.

The second limitation involves constraints. For daycare centres, our dataset does not show the entire collection of feasible sets of children or the number of teachers corresponding to the flexible constraints. Instead, it only shows the number of advertised seats at each daycare centre for each age, which is exactly enough to specify the rigid constraints. To overcome this limitation, we define $ms$ for each s in the daycare constraints (equation (5.1)) by $ms:=∑t∈Trt⋅qt,$ where $rt$ and $qt$ are those in the data (recall that $rt$ is the teacher–child ratio under the national regulation, and $qt$ is the number of advertised seats for age t at daycare centre s). That is, $ms$ is the smallest possible number of teachers such that the constraint implied by the number of advertised seats in data is a rigid constraint associated with our daycare constraint.³³

Third, we assume that our data of reported preferences are true preferences, and that the same preferences would be reported in all mechanisms. These assumptions are justified by the fact that all the mechanisms we study in this section are strategy-proof. In particular, as mentioned earlier, the reported preferences in our data are based on a version of serial dictatorship whose strategy-proofness is well understood. In addition, while the SOFM mechanism is not strategy-proof in general, in Section 6.3 we observe that it is strategy-proof under common priority across daycare centres (a feature in our dataset). We note that the recent literature provides empirical evidence that agents may misreport their preferences even under strategy-proof mechanisms.³⁴ Our results are valid up to the assumption that families truthfully report their preferences.

We find that the effect of allowing flexibility in constraints under SOFM is substantial in our data: the average number of children who are matched with a strictly preferred daycare centre in the flexible SOFM compared to the rigid SOFM is 867.27, which amounts to 60.35% of all applicants (Table 1).³⁵ By contrast, no applicant is made worse off, as implied by Proposition 2. The number of children who are unallocated changes from 713.79 to 88.02, a 87.67% decrease (Figure 1). The average numbers of children who are matched to their first choice, first two choices, and the first three choices increase by 124.04%, 75.84%, and 59.29%, respectively (Figure 2).³⁶ Our analysis suggests that utilizing the flexible nature of the constraints can be substantial in some environments.

Next, we compare the rigid and flexible SOFMs with Yamagata’s actual assignment. Yamagata’s mechanism is based on what we call rigid (justified) envy-tolerating serial dictatorship (rigid ETSD). Rigid ETSD runs serial dictatorship, treating the problem for each age as separate from others. That is, for each age, it runs serial dictatorship for children of that age and the number of seats committed to that age in advance. This means that, among other things, there may remain justified envy between two children i and $i′$ if they are of different ages, while by construction there is no justified envy between children of the same age.³⁷ Yamagata’s assignment is expected to have some efficiency advantage over the rigid SOFM since justified envy is tolerated across different ages. Meanwhile, the comparison between Yamagata’s assignment and the flexible SOFM is theoretically indeterminate. This is because Yamagata’s assignment is based on the rigid constraint, which may or may not overwhelm the efficiency gains from tolerating justified envy across different ages.

 

Our simulations reveal that the flexible SOFM outperforms Yamagata’s assignment not only in terms of fairness but also in terms of efficiency. Regarding efficiency, all of our efficiency measures favour the flexible SOFM; The average fraction of unmatched children decreased by 62.71%, and 16.56% of children are matched with strictly preferred daycare under the flexible SOFM while only 5.02% are matched with strictly preferred daycare under the actual allocation. Turning our focus to fairness, Table 2 provides several measures of justified envy for Yamagata’s assignment (note that all measures of justified envy are zero for the rigid and flexible SOFM). There are 989 pairs $(i,s)$ such that i has a justified envy toward someone matched to s under the actual allocations, which amounts to 15.24% of all pairs $(i,s)$ such that s is acceptable to i. Also, students involved in at least one of such pairs and daycares involved are 33.05% and 66.67% of the respective total numbers. The amount of justified envy for Yamagata’s actual assignment seems broadly comparable to those in TTC on Boston and New Orleans data (Abdulkadiroglu et al., 2017).

Another natural question is to see what happens in serial dictatorship if the rigid constraint is removed so that it is only subject to the daycare constraint. In the induced mechanism, called flexible (justified) envy-tolerating serial dictatorship (flexible ETSD), the current dictator receives her most preferred daycare such that adding her to the current match does not lead to infeasibility.

Since some justified envy is tolerated while the constraint is flexible in this mechanism, its efficiency is expected to be even higher than both Yamagata’s actual assignment and the flexible SOFM (in fact, it is easy to verify that the flexible ETSD is Pareto efficient for applicants and that it does not allow for any waste). Perhaps surprisingly, however, the magnitude of the improvement of this mechanism over the flexible SOFM seems rather small; the average number of unmatched children decreases only by 13.83 (15.72%) and the average number of children who become strictly better off under the flexible ETSD is 49.78 (3.46%). This difference is much smaller than the improvement of the flexible SOFM over Yamagata’s assignment, whose corresponding numbers are 174.98 (62.71%) and 237.94 (16.56%), respectively. Moreover, the average of the upper bounds of the waste under the flexible SOFM, $W^(≻I,≻S,FS)$⁠, turned out to be 24.5 slots. Hence, the waste under the flexible SOFM does not seem to be significant. Meanwhile, a significant amount of justified envy still remains under flexible ETSD, although the numbers are less than under Yamagata’s actual assignment. These numbers suggest that the flexible SOFM may be a potentially useful mechanism in daycare allocation.

One question of interest is whether the numerical patterns we find for Yamagata are generalizable outside this specific case. To answer this question, we conduct the same set of simulations based on the data we obtained from Bunkyo City, one of the 23 special districts of Tokyo. It is much more urban than Yamagata and also has many educational institutions across children’s ages including the University of Tokyo. It also features much severer shortage of daycare seats; almost half of the applicants are unassigned in the actual allocation. Despite these differences, Appendix B reports that our simulations on Bunkyo’s data finds efficiency gains from removing rigid constraints in daycare assignments comparable to those found in Yamagata. ³⁸

Summary. The key findings from our simulations are as follows:

• (1)

  Relaxing the constraint from the rigid constraint to the daycare constraint results in a significant Pareto improvement.

• (2)

  Although insisting on our fairness notion may in principle cause waste, it is small in data. Moreover, the SOFM under the daycare constraint is almost as efficient as a Pareto-efficient alternative, the flexible ETSD. Meanwhile, the latter mechanism leaves a significant number of parents with justified envy toward others while our mechanism completely eliminates justified envy.

• (3)

  SOFM under the daycare constraint outperforms the actual allocation in efficiency, while the latter leaves a significant number of parents with justified envy.

• (4)

  The findings are not specific to Yamagata, and are confirmed by data in another city as well.

6 DISCUSSION

This section provides discussions. Section 6.1 extends our analysis to the cases with weak priority. In Section 6.2, we show that capacity constraints are necessary and sufficient for guaranteeing the existence of a stable matching in the “maximal domain” sense. Section 6.3 addresses strategic issues under general upper-bounds. Section 6.4 provides an alternative algorithm that finds the SOFM. In Section 6.5, we examine the difference between the SOFM and the student-optimal stable matching. Appendix C.1 compares our model with a model of multidimensional constraints. In Appendix C.2, we provide a sense in which our results cannot be obtained from the existing results in the “matching with contracts” model.

6.1 Weak priority orders

As we have argued, there are practical problems in which fairness is so important that even some inefficiencies are tolerated. This is perhaps most vividly seen in the context of natural disasters, where the organizer of a disaster shelter needs to allocate the relief supplies such as food. For example, in the wake of the Great Hanshin Earthquake in 1995 which killed more than 6,400 people in Japan, the organizers of a disaster shelter who had 150 lunch boxes and two boxes of apples refrained from allocating them because they were not sufficient to allocate to everyone. In another shelter, the government instructed not to allocate relief supplies until there were enough to allocate to everyone in the shelter.³⁹ Even without such an instruction by the government, the organizers of yet another shelter made the same rule on their own (Hayashi, 2003).

Similar cases are repeatedly reported during natural disasters. For example, in the aftermath of Tohoku earthquake of 2011 which killed more than 15,800 people in Japan, the organizers of a disaster shelter in Fukushima refrained from allocating relief supplies, and they attributed their decision to fairness concerns, saying they “were worried about conflicts among disaster victims” (Town of Tomioka, 2015).

 

One of the key features of these problems is that priorities are weak. For instance, in the first of the aforementioned shelters in the Great Hanshin Earthquake, priority is given to the elderly and children before everyone else, but there were a large number of people in the same priority class (there were more than 1,000 people in total). In the third shelter, there were only four priority classes (for instance, individuals whose houses were destroyed by the earthquake are given higher priority than those whose houses were not and who only need relief supplies).

Motivated by these real cases, in this subsection, we study fair matching under weak priorities. To do so, we generalize the model of Section 2 by assuming each school s has a weak priority order over the set of students. Specifically, the weak priority $⪰s$ is not required to have the property that $i⪰si′$ and $i′⪰si$ imply $i=i′$⁠. In this context, we say that i has a justified envy toward $i′$ if there exists $s∈S$ such that $s≻iμi$⁠, $i′∈μs$ and $i⪰si′$⁠. Note that this condition reduces to the earlier definition when priorities are strict. Fairness and stability are analogously defined, while all other concepts are unchanged.

The following example shows a stable matching fails to exist even if the constraints are capacity constraints.

(Non-existence of a stable matching under weak priorities)

 

The above example shows that a stable matching based on fairness defined in this subsection does not necessarily exist, even if all schools have capacity constraints.⁴⁰ In fact, it is possible to show that strictness of the priorities is “necessary” in a maximal-domain sense. This suggests that requiring stability is too demanding.

The good news is that there exists an SOFM even under weak priorities if the constraint of each school is a general upper-bound. We can show this result by largely following the proof of Theorem 2, though with some care that we detail shortly: As in the proof of Theorem 2, consider the space of cutoff profiles $P={1,…,|I|,|I|+1}S$⁠. For each $s∈S$⁠, assign indices $1,2,…,|I|$ to all the students, one index for each student, with the restrictions that (i) each index is assigned to exactly one student and (ii) if $i≻si′$⁠, then i has a higher index than $i′$⁠. For each school s, let $i(s,l)$ be the student whose index is l.⁴¹ Intuitively, the indices represent a tie-breaking of the given weak priority, where 1 represents the lowest and $|I|$ the highest ranks among all the students in I breaking the ties.

With this modification, the rest of the proof for Theorem 2 needs little change. In particular, as in the original proof, we can show that if a cutoff profile p is a fixed point of T, then matching $μp$ such that $μsp=Ds(p)$ for each $s∈S$ is fair. One might wonder why such a proof works; we “break ties” when defining the indices of students while fairness requires there be no envy even between students with the same rank according to the original weak priority.⁴²

To see the reason, recall the definition of the demand function $Ds(⋅)$⁠,

Here, the key is that all the relationships in $Ds(⋅)$ involving school priorities are specified with respect to the original weak priority, not the one after breaking ties. This allows that, for any given cutoff profile p, if multiple students have the same rank at a school, then either all of them can demand that school or none of them can, ensuring there be no envy among them.

For concreteness, consider an example with three students $i1$⁠, $i2$⁠, and $i3$ and one school s, where $i3$ has the highest priority while $i1$ and $i2$ are tied and below $i3$⁠. Assume that s is acceptable to all students. Then $Ds(p)$ reduces to $Ds(p):={i∈I|i⪰si(s,ps)}$⁠. The indexing procedure would assign either 1 or 2 to $i1$⁠, the other index to $i2$⁠, and 3 to $i3$⁠. Suppose we assign 1, 2, and 3 to $i1,i2$⁠, and $i3$⁠, respectively. In constructing $Ds(p)$⁠, the only subtle case is when $ps=2$⁠.⁴³ In that case, one might think that $Ds(p)={i2,i3}$ holds because $i2$ and $i3$ have indices no smaller than 2 while $i1$’s index is 1, and it might interfere with fairness because $i1$ would have a justified envy toward $i2$⁠. Fortunately, this concern is unfounded because $i(s,2)=i2$ and $i1$ and $i2$ have the same priority at s, so $i1⪰si(s,2)$ holds, and thus $Ds(p)={i1,i2,i3}$⁠. The point is that even though the index of $i1$ is strictly lower than that of $i2$⁠, that is only for convenience, and our construction of the demand $Ds(p)$ relies on the original weak priority, guaranteeing fairness of the induced matching.

Finally, let us mention that, although fairness concerns may be the most salient in allocation during disasters such as the major earthquakes discussed earlier, there are other examples in which fairness issues are present and weak priority orders are involved. For example, Hungarian college admissions are conducted by a central clearinghouse and a fair matching is produced, where the fairness notion follows our definition (so Hungarian college admissions tolerate waste in practice). In their system, priorities at each college are based on test scores, and the applicants with the same score are ranked equally (Biró, 2008). Chilean college admissions share these features, although the mechanism in use differs from the one in Hungary (Ríos et al., 2014). Similarly, fairness is explicitly taken into account in Turkish Navy, where officers in charge of logistical support are instructed to distribute resources homogeneously across units (Kesten and Yazici, 2012). Our analysis may be applied to each of these applications in practice.

6.2 Non-existence of a stable matching

In Section 4, we showed that there is an environment in which no stable matching exists under a general upper-bound. In this subsection, we provide a theorem clarifying the extent to which this impossibility result holds.

 

Since a stable matching is guaranteed to exist if each school has a capacity constraint (Gale and Shapley, 1962; Roth and Sotomayor, 1990), Theorem 4 provides a tight characterization for the existence of a stable matching. Roughly, capacity constraints are the maximal domain for the existence of a stable matching, that is, a stable matching is guaranteed to exist if and only if each school has a capacity constraint. This result provides a justification for market designers faced with non-capacity constraints to seek a solution that may be unstable. The SOFM may be an appealing alternative because it always exists under general upper-bound and, while possibly unstable, it is most preferred by every student among all matchings that are fair, individually rational and feasible.

One might wonder why this impossibility result does not contradict the existence of a stable matching with substitutable preferences (e.g. responsive preferences with type-specific quota) which may not be associated with any capacity constraint. One major difference is that our definition of stability requires that there exist no justified envy even if satisfying such justified envy is infeasible, which fits the applications we have in mind (see Remark 1 for a discussion of different fairness notions).

6.3 Strategic issue

Assume that the constraint at each school is a general upper-bound. Consider a mechanism, called the SOFM mechanism which, for every input, produces the SOFM; of course, this mechanism is well-defined by Theorem 2 because we assume each school’s constraint is a general upper-bound. One question of interest is whether the SOFM mechanism is strategy-proof. To answer this question, we begin by noting that the SOFM mechanism is strategy-proof if the constraint of each school is a capacity constraint. This is because the SOFM and the student-optimal stable matching coincide under capacity constraints (Balinski and Sönmez, 1999), and the mechanism that produces the student-optimal stable matching is strategy-proof in that setting (Dubins and Freedman, 1981; Roth, 1982).

Given this observation, the remaining question is whether strategy-proofness holds more generally. The following result offers a sense in which such a generalization is impossible.

 

Theorem 5 only relaxes $Fs$ while keeping $F−s$ to be capacity constraints, and hence this is a maximal domain result. An implication is that the SOFM mechanism is no longer guaranteed to be strategy-proof once we go beyond the class of capacity constraints. Given this impossibility, one question of interest is whether any other reasonable mechanism satisfies strategy-proofness along with fairness, individual rationality, and feasibility. Of course, the mechanism that always produces an empty matching is strategy-proof and satisfies the other three properties, but that mechanism is hardly justifiable as it is extremely inefficient. Thus, the relevant question is whether there is a mechanism satisfying strategy-proofness and the other desiderata, while also satisfying at least some desirable efficiency property.

As it turns out, the lack of strategy-proofness is not the drawback of the SOFM mechanism alone, but is shared by a broad class of mechanisms that satisfy a very mild efficiency property. To state this finding formally, we say that mechanism φ satisfies unanimity if, for any $≻I$ and $≻S$⁠, if a matching $μ$ such that $μi$ is the most preferred outcome for every $i∈I$ at $≻i$ is feasible, then $φ≻S(≻I)=μ$⁠. In words, unanimity requires that if a matching in which every student is matched to her first choice is feasible, then the mechanism should produce that matching. This is arguably a very mild requirement and is satisfied by the SOFM mechanism and many other mechanisms. It turns out that this mild requirement is incompatible with strategy-proofness and other properties, as stated in the following generalization of Theorem 5.

 

This result shows that the lack of strategy-proofness is not a deficiency specific to the SOFM mechanism. Rather, this theorem establishes that there is a more fundamental incompatibility between strategy-proofness and other requirements once we go beyond the restrictive domain of capacity constraints.

Although the lack of strategy-proofness is inherent in the SOFM mechanism and even other mechanisms satisfying fairness, it does not necessarily imply that misreporting happens in practice.

To see this, first suppose that the priority over the students is common across all schools. In that case, one can show that the SOFM outcome can be produced by a variant of a serial dictatorship with respect to the common priority. Based on this observation, it is straightforward to show that the SOFM under common priority is strategy-proof. While common priority is fairly restrictive, it is satisfied in some practical applications such as daycare allocation in Japan (see Section 5).

Second, even if the priority is not common across schools, it may be difficult for students to precisely identify the case in which her misreporting is profitable, let alone what particular preferences to use for misreporting. We provide two such senses.

The first sense is that a particularly simple and canonical class of misreporting is never profitable under the SOFM mechanism. Formally, we say a preference relation $≻i′$ is a truncation of preference relation $≻i$ if $s≻i′s′$ if and only if $s≻is′$ for every $s,s′∈S$⁠, and $s≻i′∅$ implies $s≻i∅$ for every $s∈S$⁠. In $(I,S,FS)$⁠, a mechanism φ is said to be truncation-proof if there do not exist a profile of priority orders $≻S$⁠, a profile of students’ preferences $≻I$⁠, a student $i∈I$⁠, and (reported) preference relation $≻i′$ of student i that is a truncation of $≻i$ such that

Truncations are simple and commonly studied in the literature on matching (see e.g. Roth and Vande Vate, 1991).

 

We note that an analogous result does not hold for more general constraints. More specifically, in Appendix C.3 we consider an example in which school constraints are not general upper-bounds. In that example, we show there is no truncation-proof mechanism that always produces a Pareto-undominated fair matching.

The second sense in which manipulations may be difficult can be seen through the cutoff adjustment algorithm which by Proposition 1 implements the SOFM mechanism.

 

That is, if a student’s manipulation leads her to match with a more preferred school, then that school’s cutoff has to be strictly lower under the misreported preferences. Straightforward as this observation may be, it helps identify cases in which strategic manipulation is not profitable. For instance, in large markets, the cutoff of a school is determined by the highest-priority applicant who is rejected from it, and this depends on the entire distribution of students’ reported preferences as well as school priorities. Thus, it appears unlikely that any one particular student is in a position to influence the cutoff in any significant manner.

Based on the above discussion, we aim to prove that the SOFM mechanism has an approximate incentive compatibility property in large markets. Specifically, we consider a model with tiers of students (see e.g. Kesten, 2010; Che and Tercieux, 2019 for matching models with tiers). The tier structure is a generalization of the priority structure in the Japanese daycare allocation problem for which we conducted simulations (Section 5), and represents cases in which schools’ priorities may be different but have certain commonality.

Formally, we consider a sequence of problems  $(Π1,Π2,…)$ as follows. The nth problem is denoted $Πn=(In,Sn,≻In,≻Sn,FSn)$⁠, and there are constants $L,L′<∞$ such that, for each $n∈N$⁠, the following hold.

• •

  The number of students is n, i.e.  $|In|=n$⁠.

• •

  The number of schools is bounded, i.e.  $|Sn|<L$⁠.

• •

  The set of students $In$ is partitioned into $Kn$ “tiers,” i.e.  $⋃k=1KnTkn=In$⁠, $Tkn∩Tk′n=∅$ for all k and $k′$ with $k≠k′$⁠.

• •

  For each $s∈Sn$⁠, $i≻si′$ holds if $i∈Tkn$ and $i′∈Tk+1n$ for any k.

• •

  The size of each tier is bounded, i.e.  $|Tkn|<L′$ for each k.

• •

  The constraint $Fs$ is a general upper-bound for each $s∈Sn$⁠.

Let the SOFM mechanism be denoted by ϕ. Given a problem $Π=(I,S,≻I,≻S,FS)$⁠, let

be the set of students who have incentives to misreport their preferences.

 

That is, the fraction of students who have a profitable misreporting strategy tends to zero in the limit as the market becomes large. The result is rather strong for at least two reasons. First, the definition of $D(Π)$ is permissive in the sense that the mere existence of a profitable misreporting strategy is sufficient to count a student as having an incentive for misreporting, irrespective of, for example, the number of such misreporting strategies or difficulty of finding them. Second, for each problem $Πn$ in the sequence, the preferences of students are arbitrary, and in particular, it can be chosen so that $D(Πn)$ takes the maximum size. The result states that even if the preferences in $Πn$ for each n is replaced with such preferences, the limit of the fraction $|D(Πn)||In|$ is still zero.

 

6.4 An alternative algorithm

Suppose that the constraint at each school is a general upper-bound. Consider the following generalization of the deferred acceptance algorithm, called the cumulative offer algorithm:

• •

  Step $t≥1$⁠: Each student applies to her first choice school among those that have never rejected anyone whose priority is weakly higher than her if it is acceptable, while making no application otherwise. For each school s, let ${i1,i2,…,ik}$ be the set of students who have ever applied to it, with $i1≻si2≻s⋯≻sik$⁠. If ${i1,i2,…,ik}∈Fs$⁠, then let s temporarily keep ${i1,i2,…,ik}$⁠; otherwise, let s temporarily keep the set of students of the form ${i1,i2,…,ik′}$ such that ${i1,i2,…,ik′}∈Fs$ and ${i1,i2,…,ik′+1}∉Fs$⁠.⁴⁵ School s rejects all the remaining students who have ever applied to it, ${ik′+1,…,ik}$⁠. If no student is rejected by a new school, then terminate the algorithm and define the outcome as the matching in which each school is matched to the set of students who it currently keeps.⁴⁶ Otherwise, go to Step $t+1$⁠.

The algorithm terminates in a finite number of steps because there is a new rejection in every step that is not terminal and there are only a finite number of student-school pairs. Therefore, the outcome of this algorithm is well-defined.

Note that this algorithm has a “cumulative” feature, that is, when a school temporarily keeps students, it considers all the students who have ever applied to it, even if they were rejected in an earlier step. Moreover, the school never rejects an applicant i while keeping another student $i′$ with lower priority, even if keeping i is infeasible and keeping $i′$ is feasible. These features are important for guaranteeing fairness of the resulting matching.

 

A corollary of Propositions 1 and 8 is that the outcomes of the cumulative offer algorithm and the cutoff adjustment algorithm coincide with each other. Given this fact, one might question the merit of our approach based on Tarski’s fixed point theorem on the space of cutoffs. Our response is that there are at least two reasons to favour our approach. First, with our approach, it is easy to show that there exists an SOFM; this result is based on the well understood structure of fixed points of an increasing function on a complete lattice. By contrast, while it is possible to establish that the outcome of the cumulative offer algorithm is the SOFM without reference to this lattice structure, it would need a specific argument tailored to that particular algorithm.⁴⁷ Second, and related, the “right” way to generalize the deferred acceptance algorithm is not clear in the absence of the insight from our approach. For example, the “cumulative” nature of our cumulative offer algorithm, i.e. that each school considers the current and previous applicants, is not an ex ante obvious feature for the right generalization of the deferred acceptance algorithm.

6.5 SOSM and SOFM

One may wonder whether the following claim might hold: If there exists a stable matching $μ$ such that $μi⪰iμi′$ holds for each $i∈I$ and any stable matching $μ′$ (the student-optimal stable matching, or the SOSM) in that market, it is the same as the SOFM. This claim turns out to be false. To see this, consider the following example.

  

7 CONCLUSION

This paper studied a matching problem where institutions are subject to general constraints. Observing that a stable matching typically does not exist, our approach is to tolerate some waste while requiring fairness. Our first main result characterizes feasible, individually rational, and fair matchings by fixed points of a certain mapping on the space of cutoff profiles. Building upon this result, we find a necessary and sufficient condition for guaranteeing the existence of a student-optimal fair matching (SOFM). The condition is that the constraint of each school is a general upper-bound. Then we provide a constructive algorithm to find an SOFM based on our fixed-point mapping. Furthermore, we apply our findings to centralized allocation of daycare seats and find that the SOFM mechanism under flexible constraints performs substantially better than an alternative algorithm that treats age-specific capacities as rigid constraints.

This paper leaves various important questions for future research. For instance, our result shows the general upper-bound is exactly the condition that guarantees the existence of an unambiguously desirable fair matching, i.e. an SOFM. In particular, when the constraint of even one school fails to be a general upper-bound, there is no guarantee that an SOFM exists. In such a case, a natural question for researchers and policymakers alike is what kind of property to aim for. One possibility may be to find a Pareto-undominated fair matching as defined in Remark 4 (Section 4.2). Although the existence of such a matching is rather straightforward given the finiteness of the environment, a constructive algorithm may be nontrivial and interesting. For example, the cutoff adjustment algorithm does not always find a Pareto-undominated fair matching (see Appendix C.3). Moreover, as pointed out in Section 6.3, there exists no truncation-proof mechanism that produces a Pareto-undominated fair matching under general constraints (recall that the SOFM mechanism is truncation-proof under general upper-bounds).

Also, a more in-depth study of the trade-off between fairness and non-wastefulness may be interesting. At various places of the present paper (such as the Introduction, Remark 1, and Section 6.1), we have been making clear that our fairness notion is the appropriate one in the applications that we have in mind. Moreover, the theoretical and empirical analyses in Section 5 show that the efficiency loss from requiring our strong notion of fairness is not significant in our daycare application. We acknowledge, however, that there can be other applications in which efficiency loss can be significant. For such applications, it may be of interest to quantify the efficiency loss as well as “fairness loss” of a non-wasteful solution to appropriately trade-off these two. Such a study, of course, is beyond the scope of the present paper but could be a fruitful direction of research.

Another direction for future research would involve data. For example, we conducted numerical analysis of datasets on daycare allocation in two municipalities and found large welfare gains in both cases. To what extent is such a finding generalizable to daycare allocation elsewhere? How about other applications such as school choice with diversity constraints, college admissions involving students with disabilities, and refugee matching? These questions are beyond the scope of our paper, but they seem to be important questions for future research.

Finally, it would be interesting to use our findings for design in practice. Such an experience may not only improve outcomes in real problems like daycare seat allocation, but it may also provide more insight about possible directions for future research. For instance, is the lack of exact strategy-proofness for students a major drawback in practice, or is an approximate incentive compatibility as shown in our analysis sufficient to eliminate strategic behaviour? Is the SOFM mechanism transparent enough for applicants to understand or trust? Are there any unintended consequences of the change in the mechanism? These are just a few of many possible questions that one may be able to investigate with the feedback from policy experience. We wait for future research to answer these questions.

Acknowledgments

We thank the editor, Adam Szeidl, and anonymous referees for helpful comments. We are grateful to Mayor Takahiro Sato of Yamagata City and the officials at Yamagata’s childcare department, especially Mr Kazuhiro Sato, as well as Mayor Hironobu Narisawa of Bunkyo City and the officials at Bunkyo’s childcare department, especially Mr Hideki Okawa, Mr Junya Takahashi, and Takahito Yokoyama, for providing data on their daycare seat allocation, as well as for answering numerous questions about their allocation mechanisms, on which our analysis in Section 5 is based. We benefited from an interview with Arisa Wada at Yamagata Mirai Lab. We are also grateful to Atila Abdulkadiroglu, Tommy Andersson, Eduardo Azevedo, Péter Biró, Gabriel Carroll, Yeon-Koo Che, Yan Chen, Federico Echenique, Haluk Ergin, Nima Haghpanah, John William Hatfield, Michihiro Kandori, Yusuke Kasuya, Thilo Klein, Ayako Kondo, Jacob Leshno, George Mailath, Mihai Manea, Megumi Murakami, Tomoko Murata, Aki Matsui, Yusuke Narita, Makiko Nishi, Shunya Noda, Yasunori Okumura, Arthur Robson, Al Roth, Larry Samuelson, Cameron Taylor, Kentaro Tomoeda, Pete Troyan, Utku Unver, Bob Wilson, Qingyun Wu, Yosuke Yasuda, and seminar participants at Chinese University of Hong Kong, Waseda, Osaka, Keio, Northwestern, Stanford, Universitat Autònoma de Barcelona, International Workshop on Economic Theory (Otaru), Conference on Economic Theory (Columbia), Matching in Practice (Cologne), Market Design Conference (Vanderbilt), Workshop on Mechanism Design and Behavioral Economics (Glasgow), SAET 2018 (Taipei), Asian Meeting of Econometric Society (Seoul), Workshop on Matching, Search and Market Design (National University of Singapore), and UBC-HKU summer theory conference (Vancouver) for comments. We gratefully acknowledge excellent research assistance of Omair Butt, Ashley Dreyer, Atharva Gupta, Ye Rin Kang, Kevin Li, Shivam Patel, Priyanka Shende, Lingxuan Wu, Yutong Zhang, and especially Yue Fan. Kojima’s research was supported by the National Research Foundation through its Global Research Network Grant (NRF-2016S1A2A2912564).

Supplementary Data

Supplementary data are available at Review of Economic Studies online.

Data Availability Statement

The data underlying this article were provided by Yamagata City and Bunkyo City by permission. The code is available on Zenodo at https://doi.org/10.5281/zenodo.7690023.

References

Footnotes

Author notes