Discussion Paper No.318
Matching with Minimal Quota:
Case Study of a Student-Supervisor Assignment
in a Japanese University
Toshiji Kawagoe
Future University Hakodate

Taisuke Matsubae
Chuo University

August 2019

INSTITUTE OF ECONOMIC RESEARCH
Chuo University
Tokyo, Japan

Matching with Minimal Quota: Case Study of a StudentSupervisor Assignment in a Japanese University #Toshiji Kawagoe* and Taisuke Matsubae⊺

August 2019
Abstract
This study presents a case of student-supervisor matching in a Japanese university. We
report on the recent reform in the matching mechanism between students andsupervisors in the Japanese university. A mechanism based on the deferred acceptance(DA) was adopted in this reform. In this mechanism, both students and supervisors areclassified as one of the types, depending on their affiliations. Then, supervisors set typespecific maximal and minimal quotas. For fulfilling minimal quotas, maximal quotas
are dynamically adjusted. It is proved that the mechanism may not satisfy strategyproofness and feasibility, but it eliminates justified envy among the same “type” ofstudents. Moreover, if the sum of ranks of the student and supervisor in the final
assignment is viewed as a measure of welfare, there is no domination relationshipbetween this mechanism and the DA mechanism.
JEL classification: C78, C93, D78, I20
Keywords: school choice, strategy-proofness, distributional constraint, market design#

The authors are grateful to Fuhito Kojima, Morimitsu Kurino, Kentaro Tomoeda, Makoto Yokoo, andparticipants of the Econometric Society Australian Meeting 2019 for their comments and advices. This
paper is a result of research conducted at “contemporary policy research group,” Institute of Economic
Research Chuo University. We would like to thank Editage (www.editage.com) for English language
editing.
*
Department of Complex and Intelligent Systems, Future University Hakodate, kawagoe@fun.ac.jp.
⊺Faculty of Economics, Chuo University, matsubae@tamacc.chuo-u.ac.jp

1. Introduction
In this study, we report on the recent reform in the matching mechanism between
students and supervisors in a Japanese university.
In the Japanese university, for writing a graduation thesis, third-year
undergraduate students designate their supervisors from among the university faculty
members according to their preferences at the near end of the school year. Since eachsupervisor has limited capacity, a matching mechanism must be designed.
The most popular matching mechanism used so far in many Japanese
universities was the Boston mechanism. In this mechanism, all the students apply totheir first-choice supervisors, and each supervisor accepts applicants based on his/herown priority ordering of students. Once a supervisor’s quota is filled, the remaining
applicants are rejected. The accepted students’ assignment is final at this point. Students
rejected in this step apply to their next choice supervisors, and the iterating continues till
all the students are assigned.
The other popular matching mechanism is Priority Matching. In thismechanism, students submit their preferences and priority orderings of supervisors, thesum of a student’s ranking for a supervisor and the supervisor’s ranking for the student
is calculated, then the student-supervisor pairs are formed in ascending order of the sum(with a tie-breaking rule).
It is well known that neither of these mechanisms is strategy-proof, that is,
manipulating students’ preferences may be beneficial to them. To overcome thisproblem, a simple alternative may be the Serial Dictatorship (SD) mechanism. In thismechanism, given a specified order (based on factors like a GPA score), students apply
to their first-choice supervisors, and each supervisor accepts them up to his/her quota.
Essentially, SD is strategy-proof. Unfortunately, a matching outcome produced by SD as
well as the other two mechanisms mentioned above are not stable, that is, a studentsupervisor pair may have justified envy for another student-supervisor combination in
the resulting matching outcome.
Accordingly, adopting the Deferred Acceptance (DA) mechanism (Gale andShapley, 1962) is a natural consequence to overcome these problems. In fact, DA isstrategy-proof, and a matching outcome produced by DA is always stable. Even though
increasing number of DA applications in resident matching and school choice arereported, adoption of DA in a Japanese university is still uncommon.
In 2015, the education committee of Future University Hakodate, Japan,
decided to use DA in the assignment process of undergraduate students, who write
graduation thesis, to supervisors. One of the authors (Kawagoe) of the present study was2

a member of the committee. Based on his explanation of the working and desirable
properties of DA, the committee soon understood and accepted DA, but the members
asked several substantial qualifications to DA. The most challenging one is about
imposing minimal quota in the assignment process, that is, every supervisor must be
assigned a positive number of students in the resulting matching outcome. This isproblematic because of the “rural hospitals theorem” in the matching theory. In thecontext of the present study, this theorem simply states that a supervisor who is not
assigned any student in a stable matching is never assigned any student in any otherstable matchings. Thus, for satisfying minimal quota, one must give up the stability
requirement.
However, a non-negligible number of faculty members believed that imposing
minimal quota was necessary. The reasons cited included that if a supervisor is not
assigned a certain number of students, it may not be feasible for the supervisor to
manage the on-going research projects. The other reason was a request for equal shareof educational burden among the supervisors, that is, it was deemed that allowing a
supervisor who was not assigned any student was unfair.
Due to such arguments, the committee decided to impose minimal quota. Notethat imposing minimal quota generally leads to instable matching because a student’s
assignment in stable matching, for example, must be modified for fulfilling minimal
quota.
In the literature, several studies propose a mechanism to implement minimal
quota by discarding one of the components in the definition of stability, that is, nojustified envy and non-wastefulness (Fragiadakis et al. 2015; Fragiadakis and Troyan,
2017; Tomoeda, 2018). By examining these mechanisms, the committee decided tochoose the mechanism proposed by Fragiadakis and Troyan (2017) as the basis for thematching mechanism.
Another concern the committee discussed was about handling students’preferences for a supervisor whose affiliation is different from that of students. In
Future University Hakodate, students are segregated into four major courses in thesecond year.1 Thereafter, students choose their supervisors from among their course
faculty members. However, a few students wanted to choose supervisors whose
affiliation is different from their own, and such requests are respected.
Before 2015, as there were only a few students, they were assigned supervisors
before other students’ assignment process began. However, this was problematic. If
1

In Future University Hakodate, there are two departments with two sub-departments
each. The sub-department is called “course” in the university.
3

students feel safe to be assigned to a supervisor whose affiliation is different from theirown (as they need not compete with other students over supervisors whose affiliation is
the same), they can misrepresent preferences as if the supervisor is their first-choice. Or,
if a sufficient number of students with different affiliations have been accepted, asupervisor is reluctant to accept more students who share the same affiliation. In thiscase, students who have the same affiliation may experience justified envy against
students whose affiliation is different. Thus, the previous treatment for students whose
affiliation is different may violate strategy-proofness and stability.
This problem is very similar with the matching problem under affirmative
action policy. There are several research papers concerned about the matchingmechanism with affirmative action policy (e.g., Abdulkadiroglu, 2003, 2005;
Abdulkadiroglu and Sönmez, 2003; Kojima, 2012; Matsubae, 2011; Hafalir et al., 2013;
Kawagoe et al., 2017). The committee decided to choose the DA-based mechanism
proposed by Kojima (2012) and Mastubae (2011) for handling students in different
courses. Before the assignment process begins, each supervisor must declare quotas forboth students whose affiliation is the same and for students with a different affiliation. It
is assumed that all students whose affiliation is the same is acceptable to supervisors,
but students whose affiliation is different may not be. In the context of affirmative
action, the former students are considered as majority and the latter students as minority.
Thus, the mechanism proposed by the committee was a mixture of minimal
quota and affirmative action policy. In this mechanism, both students and supervisors
are classified as one of the types, depending on their affiliations. Then, supervisors set
maximum and minimum type-specific quotas. For fulfilling minimal quotas, maximal
quotas were dynamically adjusted. Unfortunately, it has been proved that themechanism did not satisfy strategy-proofness and feasibility but eliminated justified
envy among students with the same type.
The mechanism was implemented in 2016, and totally 254 students and 67
supervisors participated. All the students were matched, and minimal quotas were
fulfilled for every supervisor, even though, in theory, the mechanism did not satisfy
feasibility. The mechanism was not strategy-proof, but most students seemed to submit
their true preferences. About 90% of the students were assigned to their fifth or bettersupervisors. For supervisors, about 70% of the students who were matched with themwere their fifth choice or better. As for the sum of ranks of the student and supervisor instudent-supervisor pairs in the resulting matching, about 80% were smaller than orequal to ten. Thus, the matching outcome was quite satisfactory.
The remainder of the study is structured as follows. Section 2 provides a brief4

overview of the institution of student-supervisor matching adopted in a Japanese
university, based on DA with type-specific quotas and affirmative action. Section 3
presents the formal model of student-supervisor matching with affirmative action via
type-specific quotas. Section 4 presents the results for the 2016 student-supervisor
matching. Section 5 concludes. All the propositions and proofs are included inAppendix A. The raw data in our student-supervisor assignment problem are available
in an online Appendix.

2. Overview of the institution of student-supervisor matching
Future University Hakodate is in Hokkaido, Japan. It is essentially a computer science
department, which is divided into four major courses; Complex Systems, Intelligent
Systems, Information Systems, and Information Design courses.
Undergraduate students are assigned to one of these courses during the second
year. Later, before the fourth year of education begins, the process of matching students
with supervisors is conducted so that students prepare their graduation thesis.
Supervisors also belong to one of the courses. Students are advised to choose
supervisors who belong to the same course, but they can also choose supervisors fromother courses. Students can also choose supervisors who belong to the Communication
Media Laboratory (CML).
The Maximal quota for each supervisor in each course is determined by
dividing the total number of students in the course by the total number of supervisors inthe same course, so that students are not unmatched. Basically, the maximal quota
determined through this method is four or five students. If supervisors would like, they
can accept two additional students in the same course. As for students in different
courses, supervisors must declare the maximal quota to them. However, if they do notwant to accept any of them, it can be set equal to zero.
The Minimal quota is determined by a uniform consent among supervisors inthe same course, and each supervisor in the same course has basically the same amountof minimal quota. Minimal quota used was one or two in the majority of courses, but
one course chose three. As supervisors in the CML have no obligation to accept any
student, the minimal quota for them is set equal to zero.
Before starting the matching process, the chief of the educational committee inthe university explains about the matching process and the basic properties of the DA
mechanism for students, including the fact that truth-telling is a dominant strategy.
Later, for two weeks, students interview with supervisors whom they would
5like to apply. After that, students submit their preferences for supervisors through paper
forms. They also rank every supervisor in the same course, for avoiding no match. Of
course, they can also rank supervisors in different courses, but the number is restricted
to two.
Then, each supervisor is informed via an electronic file delivery system about
students’ preferences and additional information such as GPA, number of compulsory
courses, and the total number of courses that students have already secured credits. The
supervisors can only see the preferences of the students who rank themselves. Based onsuch information, supervisors submit their priority orderings to students via theelectronic file delivery system. Supervisors must rank all the students who belong to thesame course, but they can eliminate students who are in different courses, if they do notwant to accept them.
Subsequently, based on students’ preferences, supervisors’ priority orderings,
and type-specific maximal and minimal quotas, a matching outcome is determined. The
algorithm used is based on the Deferred Acceptance (DA) mechanism withmodifications. We call it the DAMin mechanism, which is explained in the next section.

3. ModelWe present a formal model of a student-supervisor matching with type-specificmaximum and minimum quotas described in Section 2. As the algorithm used is a DAbased mechanism, we first describe DA with no distributional constraints for simplicity.
3.1 Student-supervisor problem in general
The basic setups for a student-supervisor problem are as follows:(1) A non-empty finite set of students 𝑆 = {𝑠& , 𝑠( , … , 𝑠* };(2) A non-empty finite set of supervisors 𝑇 = {𝑡& , 𝑡( , … , 𝑡. };(3) Students’ preference profile is 𝑃 = 0𝑃12 , 𝑃13 , … , 𝑃14 5, where 𝑃16 is a preference
relation over 𝑇 for the student 𝑠7 . We assume in this study that preferences arestrict for all the students. 𝑡8 𝑃16 𝑡9 means that student 𝑠7 prefers 𝑡8 to 𝑡9 . Let 𝑅16
denote the weak preference relationship induced by 𝑃16 , that is, 𝑡8 𝑃16 𝑡9 or 𝑡8 = 𝑡9
if and only if 𝑡8 𝑅16 𝑡9 . We also assume that every supervisor is acceptable to every
student and there is no constraint on the size of the submitted preference.2
2

Calsamiglia et al. (2010) conducted an experiment to compare school choice problems
with and without the constraint on the size of the submitted preference list and found6(4) Supervisors’ priority profile is ≿= <≿=2 , ≿=3 , … , ≿=> ?, where ≿=@ is the priority
ordering over 𝑆 for supervisor 𝑡8 .3 The priority ordering is also assumed to bestrict for all supervisors. Denote ≻B@ as supervisor 𝑡8 's strict priority ordering;
thus, 𝑠7 ≻=@ 𝑠C if and only if 𝑠7 ≿=@ 𝑠C but not 𝑠C ≿=@ 𝑠7 .
(5) Each supervisor 𝑡8 ∈ 𝑇 has a non-negative integer 𝑞=@ , which is the capacity of thesupervisor 𝑡8 (i.e., total number of students she can accept). We call it total.

capacity. Let 𝑞 = 0𝑞=@ 5

8G&

be the vector of total capacity.

Then, matching 𝜇 involves mapping from the set 𝑆 ∪ 𝑇 to the set of all
subsets of 𝑆 ∪ 𝑇 such that
(M1) |𝜇(𝑠7 )| = 1 for each student 𝑠7 , and 𝜇(𝑠7 ) = 𝑠7 if 𝑠7 ∉ 𝜇(𝑡8 ) for any
supervisor 𝑐8 ;(M2) For each 𝑠7 ∈ 𝑆 and 𝑐8 ∈ 𝐶, 𝜇(𝑠7 ) = 𝑡8 if and only if 𝑠7 ∈ 𝜇(𝑡8 ); and(M3) |𝜇(𝑡8 )| ≤ 𝑞=@ and 𝜇(𝑡8 ) ⊆ 𝑆 for each supervisor 𝑡8 .
(M1) and (M2) mean that all the students are matched with at most one supervisor orwith themselves. (M3) implies that all the supervisors are matched with up to thenumber of students allowed by their total capacity.
Mechanism 𝜑 is a mapping that produces a matching for any preference
profile. For determining a matching 𝜇, DA mechanism (Gale and Shapley, 1962) isused. The mechanism runs as follows.
Assignment process of DA mechanism:
Step 1: Every student applies to her first-choice supervisor. For each supervisor 𝑡8 ,𝑞=@ applicants who have highest priority for 𝑡8 are tentatively accepted by 𝑡8 , andthe others are rejected.
Step 𝑘 ≥ 2: Applicants who were rejected at step 𝑘 − 1 apply to their next-choicesupervisors. For each school 𝑡8 , 𝑞=@ students who have the highest-priority for 𝑡8
among the new applicants and those accepted by step 𝑘 − 1 are tentatively
accepted, and the rest are rejected.
that the proportion of (truncated) truth-telling is significantly higher in theunconstrained than in the constrained case. As a result, efficiency is significantly
reduced, and stability is low in the constrained compared to the unconstrained case.
3
This means that every student is acceptable to every supervisor.
7

Terminal condition: If either every student is accepted or no more supervisors remain in
the submitted preferences for unmatched students, the process terminates.
The mechanism stops at a finite number of steps, and the resulting matching 𝜇 is
unique. Moreover, the matching 𝜇 is stable and student optimal.
Stability: A matching 𝜇 is stable if the following apply:(S1) 𝜇(𝑠7 )𝑃16 𝑠7 for each student 𝑠7 ∈ S, and(S2) if 𝑡8 𝑃16 𝜇(𝑠7 ), then |𝜇(𝑡8 )| = 𝑞=@ and 𝑠C ≻=@ 𝑠7 for any student 𝑠C ∈𝜇(𝑡8 ).
(S1) means the condition of individual rationality that all the students prefer matchingwith a supervisor than matching with themselves. (S2) means that no pair (𝑡8 , 𝑠7 ) can
be a blocking pair for matching 𝜇; thus, if student 𝑠7 prefers supervisor 𝑡8 to theoutcome obtained under matching 𝜇, then the total capacity of supervisor 𝑡8 is alreadyfull, and supervisor 𝑡8 does not give student 𝑠7 higher priority than any other student𝑠C she accepts under 𝜇. If a matching outcome is not stable, one student feels justified
envy against another student.
Justified envy: For a matching 𝜇, 𝑠7 feels justified envy against another student 𝑠C if
𝜇(𝑠C ) 𝑃16 𝜇(𝑠7 ), 𝑠7 ≻Y<1Z ? 𝑠C , and there exists another matching 𝜈 such that
𝜈(𝑠7 ) = 𝜇(𝑠C ), 𝜈<𝑠C ? ≠ 𝜇<𝑠C ? 𝑎𝑛𝑑 𝜈(𝑠9 ) = 𝜇(𝑠9 ) 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑠9d7,C .
The definition of student optimality is as follows.
Student-optimal stable matching: A stable matching that every student weakly prefers
to any stable matching.
Mechanism 𝜑 is a student-optimal stable mechanism (SOSM) if it produces studentoptimal stable matching for any preference profile.
Theorem 1 (Theorems 1, 2 in Gale and Shapley 1962): Given (𝑃, ≳), the DA
mechanism is SOSM.
Further, the DA mechanism is strategy-proof: stating a true preference is the dominant
strategy for students.
8Strategy-proofness: Let 𝜑(𝑃) be a matching induced by a matching mechanism 𝜑under a true preference profile 𝑃, and 𝜑16 (𝑃) be student 𝑠7 's matching outcome in𝜑(𝑃). For any student 𝑠7 ’s preference 𝑃1f6 and any profile of other students’preferences other than 𝑠7 , 𝑃gh16 , if
𝜑1 <𝑃1 , 𝑃gh1 ?𝑅1 𝜑1 <𝑃1f , 𝑃gh1 ?
7

6

6

6

6

6

6

holds, 𝜑 is strategy-proof.
Theorem 2 (Theorem 9 in Dubins and Freedman, 1981; Theorem 5 in Roth, 1982b): theDA mechanism is strategy-proof.
However, the resulting matching with DA is not always Pareto-efficient (Abdulkadiroglu,
2003).4
Pareto-efficiency: A matching is Pareto-efficient if it is not Pareto-dominated by anyother matching.
A matching 𝜇 Pareto-dominates another matching 𝜈 if 𝜇(𝑠7 )𝑅16 𝜈(𝑠7 ) for every
student 𝑠7 ∈ 𝑆 and 𝜇<𝑠C ?𝑃1Z 𝜈<𝑠C ? for at least one 𝑠C ∈ 𝑆. Thus, a matching 𝜇 Paretodominates another matching 𝜈 if every student prefers the supervisor assigned under 𝜇
to the supervisor assigned under 𝜈, and at least one student strictly prefers the outcome
obtained under 𝜇.
3.2 Student-supervisor problem with type-specific maximal and minimal quotas.
We then consider a student-supervisor problem with type-specific maximal and minimal
quotas. This is also called the controlled school choice problem in the literature andstudied by Ehlers et al. (2014) and Fragiadakis and Troyan (2017).
To consider this problem, we add the following settings to the general setting
described in the previous subsection.
Note that the outcome of the DA mechanism is not necessarily efficient in the context
of school choice. Ergin (2002) shows that the outcome of the DA mechanism is Pareto
efficient if and only if the school priorities satisfy a certain acyclicity condition. Ehlers
and Erdil (2010) generalize the result in the case where school priorities are coarse. Thiscan be interpreted as a negative result for the efficiency of the DA mechanism, sinceschool priorities are not likely to satisfy the acyclicity conditions of Ergin (2002) and
Ehlers and Erdil (2010) in applications.

49𝛩 = {𝜃& , … , 𝜃k } is the finite set for types of students, and each student belongs
to at most one of the following types. We interpret “type” as a course that a student
belongs to. The function 𝜏: 𝑆 → 𝛩 assigns one of the types for each student anddenotes that 𝑆o is the set of students of type 𝜃 ∈ Θ, and 𝑇o is the set of supervisors oftype 𝜃 ∈ Θ. We assume that types are publicly observable (i.e., types cannot be
misreported).
For all types 𝜃 ∈ 𝛩 and supervisor 𝑡 ∈ 𝑇o , in addition to total quota 𝑞= , eachsupervisor has a type-specific maximal quota 𝑈=,o and a type-specific minimal quota
𝐿=,o . Let 𝑈 = (𝑈=,o )=∈s,o∈t be the vector of maximal quota and 𝐿 = <𝐿=,o ?=∈s,o∈t be
the vector of minimal quota. Moreover, denote 𝑈=,ho as the maximum number ofstudents other than type 𝜃 assigned to supervisor 𝑡 ∈ 𝑇o , and 𝐿=,ho as the minimum
number of students other than type 𝜃 assigned to supervisor 𝑡 ∈ 𝑇o . We assume
0 ≤ 𝐿=,o ≤ 𝑈=,o ≤ 𝑞= for all (𝑡 (∈ 𝑇o ), 𝜃). We also assume that 𝑈=,ho = 𝑞= and𝐿=,ho = 0. Thus, we consider a school choice problem where minimal quota constraint
is binding when student and supervisor types are the same.
Denote ℳ as the set of matchings. For any 𝜇 ∈ ℳ, let 𝜇o (𝑡) be the set ofstudents of type 𝜃 assigned to a supervisor 𝑡 ∈ 𝑇o under matching 𝜇.
Feasibility: A matching 𝜇 is feasible if 𝐿=,o ≤ |𝜇o (𝑡)| ≤ 𝑈=,o for all (𝑡 (∈ 𝑇o ), 𝜃)
and |𝜇(𝑡)| ≤ 𝑞= . In other words, feasible matching satisfies type-specific minimal andmaximal quotas for any type as well as the total capacity for any supervisor.
Denote ℳw ⊂ ℳ as the set of feasible matchings. We assume in the study that ℳw ≠∅; this is the (obviously necessary) requirement that the distributional constraints suchas maximal and minimal quotas are consistent with the number of students of each type
actually present in the market.
The definition of justified envy defined in subsection 3.1 should be modified
accordingly with the introduction of maximal and minimal quotas.
Justified envy: For a matching 𝜇, a student 𝑠7 ∈ 𝜇(𝑡8 ) justifiably envies student 𝑠C ∈𝜇(𝑡9 ) if (i) 𝑡9 𝑃16 𝑡8 , (ii) 𝑠7 ≻=z 𝑠C , and (iii) there exists an alternative matching 𝜈 ∈ ℳw
such that 𝜈(𝑠7 ) = 𝑡9 , 𝜈<𝑠C ? ≠ 𝑡9 , and 𝜈(𝑠{ ) = 𝜇(𝑠{ ) for all ℎ ≠ 𝑖, 𝑗.
In other words, student 𝑠7 justifiably envies another student 𝑠C if (i) she prefers
supervisor 𝑡9 to whom student 𝑠C is assigned to 𝑡8 , (ii) has a higher rank than 𝑠C on
10

the priority ordering of supervisor 𝑡9 , (iii) and 𝑠7 and 𝑠C can be reassigned without
violating any distributional constraints (and without altering the allocation of any otherstudent). If no student justifiably envies any other student, then the matching eliminates
justified envy.
‚

Then, denote 𝐷𝐴<• ? (⋅) as the DA mechanism with maximal quota vector 𝑈′.
A DA mechanism with minimal quota (henceforth, DAMin) is defined as follows. Notethat the maximal quota for each supervisor would be reduced at each period if thematching outcomes are not feasible.
We also use the following notations in describing DAMin: the mapping
𝑅𝑎𝑛𝑘(⋅) maps a supervisor 𝑡 assigned to a student to the supervisor’s ranking number{1, … , 𝑛} for the student on her priority, 𝑇… ≔ {𝑡′ ∈ 𝑇 ∶ |𝜇o (𝑡′)| > 𝐿=f,o , 𝑓𝑜𝑟 𝑎𝑛𝑦 𝜃},…………………(𝑡′) ≔ max 𝑅𝑎𝑛𝑘(𝑡′).
and for any 𝑡′ ∈ 𝑇…, 𝑅𝑎𝑛𝑘
1∈Y(=f)Assignment process of DAMin mechanism:
Step 1: Starting with maximal quotas vector 𝑈& = <𝑈=&2 , 𝑈=&3 , ⋯ , 𝑈=&> ?, determine a2matching outcome with 𝐷𝐴(• ) (𝑃) (as defined in subsection 3.1) with 𝑈& . If thematching outcome 𝜇 is feasible, the algorithm is terminated, and the matchingoutcome is finalized. If not, proceed to next Step.
Step 𝑘 ≥ 2: If a feasible matching is not obtained in Step 𝑘 − 1, ∃ 𝑡 ∈𝑇o 𝑠. 𝑡. |𝜇o (𝑡)| < 𝐿=,o , the rankings of student rated lowest are compared amongsupervisors whose minimal quotas are fulfilled. Thus, we choose supervisor 𝑡 f such…………………(𝑡′) is maximum in 𝑡 f ∈ 𝑇…, and the maximal quota for supervisor 𝑡′ isthat 𝑅𝑎𝑛𝑘
adjusted to 𝑈=f8h& − 1. Note that if there are two or more supervisors satisfying theabove condition, one of them would be randomly chosen. With this updated@

maximal quota vector 𝑈 8 , run 𝐷𝐴(• ) (𝑃) again. If the resulting matching 𝜇 is
feasible, terminate the algorithm and the matching outcome is finalized. If not,proceed to Step 𝑘 + 1.
Terminal condition: If (i) either every student is accepted, or (ii) no more acceptablesupervisors remain in the submitted preferences for unmatched students, or (iii) if
for every supervisor, the number of students of the same type who is assigned ismore than his/her minimal quota; 𝐿=,o ≤ |𝜇o (𝑡)|, or (iv) 𝑈=,o = 𝐿=,o for all(𝑡(∈ 𝑇o ), 𝜃) (by updating maximal quota vector, the maximal quota for any
supervisor will be less than his/her minimal quota), the process terminates. The
mechanism stops at a finite number of steps, and the resulting matching 𝜇 is
unique.
11

The following example shows the working of DAMin.
Example 1.
There are five students 𝑆 = {𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” } and there are two types 𝛩 = {𝜃& , 𝜃( }.
So, the students are divided as 𝑆o2 = {𝑠( , 𝑠’ } and 𝑆o3 = {𝑠& , 𝑠“ , 𝑠” }. There are three
supervisors 𝑇 = {𝑡& , 𝑡( , 𝑡’ }, and they are divided as 𝑇o2 = {𝑡& } and 𝑇o3 = {𝑡( , 𝑡’ }.
Total quotas, and type-specific minimal and maximal quotas are as follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=&2 ,o2 ? = (3, 1, 2),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=&3 ,o2 ? = (1, 1, 1),<𝑞=– , 𝐿=– ,o3 , 𝑈=&– ,o3 ?} = (2, 1, 2)}.

True preference profiles for each student are as follows.5
𝑃1 & : 𝑡’ 𝑡& 𝑡( ,𝑃13 : 𝑡& 𝑡’ 𝑡( ,𝑃1– : 𝑡& 𝑡( 𝑡’ ,𝑃1— : 𝑡& 𝑡( 𝑡’ ,𝑃1˜ : 𝑡’ 𝑡& 𝑡( .
Priority orderings for each supervisor are as follows.6≻=2 : 𝑠( 𝑠“ 𝑠’ 𝑠& 𝑠” ,≻=3 : 𝑠& 𝑠( 𝑠’ 𝑠“ 𝑠” ,≻=– : 𝑠” 𝑠( 𝑠’ 𝑠“ 𝑠& .
Assume that every student submits her true preference. Then, all the students are assigned
to their first choice, but this matching is not feasible. In fact, supervisor 𝑡( has not…………………(𝑡’ ) > 𝑅𝑎𝑛𝑘…………………(𝑡& ) = 3, the maximal
satisfied her minimal quota. Then, since 5 = 𝑅𝑎𝑛𝑘
quota for supervisor 𝑡’ is reduced to 𝑈=(– =1 and the DA runs again with this updated
quota vector. As a result, student 𝑠& is rejected by his first-choice supervisor 𝑡’ . Then,he applies to his second-choice supervisor 𝑡& and is again rejected; finally, he is acceptedby his third-choice supervisor 𝑡( . As every student is assigned, DAMin ends and theresulting matching 𝜇 is as follows.
5

The notational convention is that supervisors are listed in the order of students’preferences and supervisors who are not on the preference list are unacceptable: for
instance, for student 𝑠& , supervisor 𝑡’ is preferred to supervisor 𝑡& , and supervisor 𝑡&
is preferred to supervisor 𝑡( . Henceforth, the same notation is used in the study.
6
The notational convention here is that students are listed in the order of supervisors’
priorities. Henceforth, the same notation is used in the study.
12𝑡𝜇 = š𝑠 , 𝑠& , 𝑠
(

’

“

𝑡(
𝑠&

𝑡’
𝑠” ›.

Remark 1:
DAMin starts with the standard DA, and then checks if, given the submitted
preferences, the resulting matching fulfills the feasibility constraint, especially theminimal quota. If feasibility is satisfied, the algorithm produces the same matchingoutcome as the standard DA. If not, one of the supervisors’ maximal quotas is reduced
by one. This does not necessarily reduce the number of assigned students to thesupervisor (i.e., when the number of assigned students is strictly less than the maximal
quota, reduction of maximal quota does not change anything.). However, repeating thisreduction process finally removes a student from the supervisor’s quota. If the rejectedstudent then applies to his next-choice supervisor and the supervisor accepts him, she
may reject her lowest priority student who was assigned in the previous step. In thisway, the rejection chain starts and continues until no student is rejected, according to the
DA algorithm. Thus, by lowering the maximal quota in sequence, we gradually fulfill
the minimal quota for every supervisor.
Remark 2:
Fragiadakis and Troyan (2017) proposed that the method for reducing maximal quota
exogenously determined one (for example, a randomly chosen sequence of thesupervisors). One of the authors (Kawagoe) of the present study, strongly recommended
it to the university’s education committee, but the chief of the committee finally decided
to choose the method for the endogenous one, that is, among the supervisors whose
number of assigned students are strictly greater than the minimal quota in the previous
step, the supervisor who is assigned the lowest ranked student with respect to his/her
submitted priority order is chosen. By changing the reduction sequence from exogenous
to endogenous, some good properties of DAMin, for example, strategy-proofness, islost.
The reason underlying the chief’s decision is the fact that with an exogenouslychosen sequence, a student was not removed from a supervisor whose worst student’s
rank was lower (in fact, 81st) but from another supervisor whose worst student’s rank
was relatively higher (in fact, 6th). With an endogenously chosen sequence, a supervisor
was in a better position by eliminating the lowest ranked student because the student
was unacceptable to her and the student could have a chance to be assigned to his nextchoice supervisor, changing the reduction sequence from exogenous to endogenous may
13not be so detrimental. In fact, the assumption that all students are acceptable may nothold. In the Japanese university, it was enforced that supervisors must accept any
student if seats are available. The sum of ranks of the student and supervisor in the final
assignment with the endogenously chosen sequence was slightly higher than the withthe exogenously chosen sequence, as well as with the original DA.
Remark 3: DAMin mechanism is SOSM.
Eliminates justified envy among students with same typeThus, if DAMin satisfies the desired properties described in subsection 3.1, it
guarantees that the final resulting matching eliminates justified envy among students
with the same type.
Proposition 1. DAMin eliminates justified envy among students with same type.
Feasibility
DAMin may produce infeasible matching outcomes because with DAMin any student
can apply to supervisor 𝑡 who is different type 𝜃 and whose maximal quota 𝑈=,ho is
not reduced.
Proposition 2. For any preference profile, DAMin may not be a feasible matching.
Remark 4:
The problem of infeasibility may occur not only under the DA-based mechanism suchas DAMin but also under any other kind of mechanism, if type-specific minimal quotas
are imposed, as some supervisors of type 𝜃 cannot fulfill their minimal quotas whensufficient number of students are assigned to supervisors whose types are other than 𝜃.
Strategy-proofness
If the method of reducing maximal quotas is exogenously determined, as Fragiadakis
and Troyan (2017) show, DAMin is strategy-proof. However, if it is endogenously
determined, DAMin may not be strategy-proof, as explained in Remark 2.
For example, consider a situation where student s applied to a popularsupervisor 𝑡 as his first choice. Even though maximal quota of supervisor 𝑡 is stillvacant; if there is another supervisor 𝑡′ whose minimal quota is not filled, the maximal
quota of supervisor 𝑡 may be reduced because she is the supervisor who is assigned the14worst student 𝑠 among supervisors who fulfill minimal quotas. As a result, if student 𝑠
may be assigned to a supervisor worse than 𝑡. Anticipating this, student s may hesitate
to state her true preference.
Proposition 3. For any 𝑃, DAMin is not strategy-proof.
Efficiency
First, we state that there is no Pareto dominance relationship between DAMin and theoriginal DA. As DAMin includes DA as a special case (e.g., when the final matchingoutcome is determined in Step 1 with DAMin), no ordinal Pareto domination
relationship holds between them.
Proposition 4. DAMin is not necessarily Pareto dominated by DA.
Then, as stated in Remark 2, in the actual matching of student-supervisor data in 2016,
the sum of ranks of the student and supervisor in the final assignment withendogenously chosen sequence was rather slightly higher than with the exogenouslychosen sequence and original DA.
When we consider the sum of ranks of the student and supervisor as a measureof welfare, DAMin is cardinally more efficient than DA by the sum of ranks of thestudent and supervisor. We formally define this type of efficiency as follows.
Cardinal efficiency: A matching outcome 𝜇 is cardinally more efficient than 𝜇′ by
the sum of ranks of the student and supervisor if∑1∈• 𝑅𝑎𝑛𝑘 <𝜇(𝑠)? + ∑=∈s ∑1f∈Y(=) 𝑅𝑎𝑛𝑘(𝑡) < ∑1∈• 𝑅𝑎𝑛𝑘 <𝜇′(𝑠)? +∑=∈s ∑1f∈Yf(=) 𝑅𝑎𝑛𝑘(𝑡) ,where the mapping 𝑅𝑎𝑛𝑘(⋅) maps a student 𝑠 assigned to a supervisor based on thestudent’s ranking number {1, … , 𝑚} for the supervisor on her preference.
Cardinal domination: If a matching 𝜇 with a mechanism 𝜑 is cardinally more
efficient than 𝜇′ with another mechanism 𝜓, 𝜑 cardinally dominates 𝜓.
Then, we have the following proposition.

15

Proposition 5. DAMin is not necessarily cardinally dominated by DA
However, the following proposition shows that under a certain priority
structure, DAMin is cardinally dominated by DA. To prove this, we use the following
definition of an essentially homogeneous priority structure introduced by Kojima(2013).
Essentially homogeneous (Kojima, 2013)
A priority structure ({𝑃= , 𝑞= }=∈s ) is essentially homogeneous if there exist no 𝑡, 𝑡 f ∈𝑇 and 𝑠, 𝑠 f ∈ 𝑆 such that (1) 𝑠 𝑃= 𝑠′ and 𝑠′ 𝑃= 𝑠, and (2) there exist sets of students
𝑆= 𝑆=f ⊂ 𝑆 ∖ {𝑠, 𝑠 f } such that |𝑆= | = 𝑞= − 1, |𝑆= ‚ | = 𝑞= ‚ − 1, 𝑆= = {𝑠 ff ∈ 𝑆 ∶ 𝑠 ff 𝑃= 𝑠 f },and 𝑆= ‚ = { 𝑠 ff ∈ 𝑆: 𝑠 ff 𝑃= ‚ 𝑠}.
Proposition 6. If a school’s priority structures are essentially homogeneous, thenDAMin is cardinally dominated by DA.
The concept of an essentially homogenous priority structure seems to be similar withthe acyclic condition introduced by Ergin (2002), or Kesten (2006).7 Thus, if a priority
structure has a cycle, the above negative result for DAMin may not hold. The following
example shows that this conjecture may be right.
Example 3.
We show the above statement with the following example. There are five students 𝑆 ={𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” } and there are two types 𝛩 = {𝜃& , 𝜃( }. So, the students are divided as
𝑆o2 = {𝑠’ , 𝑠“ , 𝑠” } and 𝑆o3 = {𝑠& , 𝑠( }. There are three supervisors 𝑇 = {𝑡& , 𝑡( , 𝑡’ }, andthey are divided as 𝑇o2 = {𝑡& , 𝑡( } and 𝑇o3 = {𝑡’ }. The total quotas, type-specific
Ergin (2002): A strong cycle is a set 𝑡, 𝑡 f ∈ 𝑇 and 𝑠7 , 𝑠C , 𝑠8 ∈ 𝑆 such that (1)𝑠7 𝑃= 𝑠C 𝑃¡ 𝑠8 , 𝑠8 𝑃=f 𝑠7 , and (2) there exist (possibly empty) disjoint sets of students
𝑆= , 𝑆=f ⊂ 𝑆 ∖ {𝑠7 , 𝑠C , 𝑠8 } such that 𝑆= ⊂ 𝑈= <𝑠C ? = 0 𝑠 ∈ 𝑆 ∶ 𝑠 𝑃= 𝑠C 5, |𝑆= | = 𝑞= −1, 𝑆= ‚ ⊂ 𝑈= ‚ (𝑠7 ), |𝑆= ‚ | = 𝑞=f − 1. A profile of supervisor priorities and capacities isweakly acyclic if no strong cycle exists.
Kesten (2006): A cycle is a set 𝑡, 𝑡 f ∈ 𝑇 𝑎𝑛𝑑 𝑆7 , 𝑠C , 𝑠C ∈ 𝑆 such that (1)𝑠7 𝑃= 𝑠C 𝑃= 𝑠8 , 𝑠8 𝑃=f 𝑠7 , 𝑠C , and (2) there is a (possibly empty) set 𝑆= ⊂ 𝑆 ∖0 𝑠7 , 𝑠C , 𝑠8 5𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑆= ⊂ 𝑈= (𝑠7 ) ∪ (𝑈= <𝑠C ? ∖ 𝑈= ‚ (𝑠8 )) 𝑎𝑛𝑑 |𝑆= | = 𝑞= − 1. A
profile of school priorities and capacities is acyclic if no cycle exists. Note that if apriority structure is a satisfied cycle, then the priority structure becomes a strong cycle.
716

minimal and maximal quotas are as follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (2, 1, 2),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (3, 1, 3),<𝑞=– , 𝐿=– ,o3 , 𝑈=– ,o3 ? = (2, 1, 2)}.

Under true preference profiles for each student
𝑃12 : 𝑡’ 𝑡& 𝑡( ,𝑃13 : 𝑡’ 𝑡& 𝑡( ,𝑃1– : 𝑡( 𝑡& 𝑡’ ,𝑃1— : 𝑡( 𝑡& 𝑡’ ,𝑃1˜ : 𝑡( 𝑡& 𝑡’ ,and priority orderings for each supervisor≻=2 : 𝑠’ 𝑠& 𝑠( 𝑠“ 𝑠” ,≻=3 : 𝑠“ 𝑠” 𝑠’ 𝑠( 𝑠& ,≻=– : 𝑠& 𝑠( 𝑠’ 𝑠“ 𝑠” ,the resulting final matching with DA is as follows. Note that the priority structures havecycle structure.
𝜇= £

𝑡&
∅

𝑡(
𝑠’ , 𝑠“ , 𝑠”𝑡’¤.
𝑠& , 𝑠(

The sum of students’ and supervisors’ ranks is 14. The result of DAMin is 𝜇¥7* :𝑡
𝜇¥7* = š𝑠 &’𝑡(𝑠“ , 𝑠”𝑡’
𝑠& , 𝑠( ›.

The sum of ranks of the student and supervisor is 12.
This example shows that if a priority structure has a cycle, DAMin cardinally dominates
DA. However, this property does not hold for any matching market as the following
example shows
Example 4.
There are five students 𝑆 = {𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” } and there are two types 𝛩 = {𝜃& , 𝜃( }.
So, the students are divided as 𝑆o2 = {𝑠’ , 𝑠“ , 𝑠” } and 𝑆o3 = {𝑠& , 𝑠( }. There are three
supervisors 𝑇 = {𝑡& , 𝑡( , 𝑡’ }, and they are divided as 𝑇o2 = {𝑡& , 𝑡( } and 𝑇o3 = {𝑡’ }.
Total quotas, type-specific minimal and maximal quotas are as follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (2, 1, 2),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (3, 1, 3),<𝑞=– , 𝐿=– ,o3 , 𝑈=– ,o3 ? = (2, 1, 2)}.
17

Under true preference, the profiles for each student are
𝑃12 : 𝑡’ 𝑡& 𝑡( ,𝑃13 : 𝑡’ 𝑡& 𝑡( ,𝑃1– : 𝑡( 𝑡’ 𝑡& ,𝑃1— : 𝑡( 𝑡& 𝑡’ ,𝑃1˜ : 𝑡( 𝑡& 𝑡’ ,and priority orderings for each supervisor are≻=2 : 𝑠“ 𝑠& 𝑠( 𝑠’ 𝑠” ,≻=3 : 𝑠“ 𝑠” 𝑠’ 𝑠( 𝑠& ,≻=– : 𝑠& 𝑠( 𝑠’ 𝑠“ 𝑠” ,the resulting final matching with DA is as follows. Note that the priority structure has acycle.
𝜇= £

𝑡&
∅

𝑡(
𝑠’ , 𝑠“ , 𝑠”𝑡’¤.
𝑠& , 𝑠(

The sum of students’ and supervisors’ rank is 14. The result of DAMin is 𝜇¥7* :𝑡
𝜇¥7* = š𝑠 &’𝑡(𝑠“ , 𝑠”𝑡’
𝑠& , 𝑠( ›.

The sum of students’ and supervisors’ rank is 17.
Then, DAMin with endogenous sequence can Pareto-dominate exogenous sequence ingeneral? Our conjecture is that there is no Pareto-dominated relationship among thesemechanisms. The following Proposition 7 supports our conjecture.
Proposition 7. There is no Pareto-dominated relationship in DAMin with endogenous
sequence, and the one with exogenous sequence for any matching market.
Then, DAMin with endogenous sequence cardinally dominates one with exogenous
sequence? We show that from the following proposition, there is no cardinal domination
relationship between both types of DAMin.
Proposition 8. There is no cardinal domination relationship between both types of
DAMin for any matching market.
These findings suggest that the only limitation of DAMin with endogenous sequence islack of strategy-proofness, when we compare it with the one with exogenous sequence.
18

However, the number of experimental findings show that (e.g., Kawagoe et al., 2018)
strategy-proofness is not satisfied even for the DA mechanism. Therefore, lack ofstrategy-proofness may not be a major problem in practice.
Comparison with related mechanisms
Fragiadakis et al. (2015) also study a model of school choice with minimal quotas (hardfloor constraints). The model they proposed is restricted to the case that each school has
an aggregate floor constraint, that is, they do not allow a school to have separate floors
for different types of students. Unlike the model proposed by Fragiadakis et al. (2015)
and Fragiadakis and Troyan (2017), DAMin allows a supervisor to have separate floors
for different types of students.
The extended-seat DA (ESDA) mechanism proposed by Fragiadakis et al.
(2015) fills an aggregate floor constraint by separating each school’s total quotas into
two parts, one part corresponds to minimal quotas and the other the remaining seats.
Subsequently, students are assigned to each school by filling minimum quota as early as
possible unless any justified envy causes any delay. Specifically, when students apply totheir first-choice schools, the schools accept them up to their minimal quotas based on
their priority orderings. Then, students who are rejected by their first-choice schools
apply for the remaining seats (total quotas minus minimal quotas) at their first-choice
schools. If they are again rejected, then they apply to their second-choice schools, andso on. The ESDA fulfills each school’s seats from the bottom, while the model proposedby Fragiadakis and Troyan (2017) and DAMin reduce each school’s seats from the top
to fulfill minimal quotas. Fragiadakis et al. (2015) proved that ESDA is strategy-proof
and satisfies a modified sense of stability (Fragiadakis et al., (2015) Theorem 3).
In the DAMin, maximal quota is reduced one by one. This causes unwarranted
and unfair feelings for supervisors who were removed students once assigned inprevious steps in the algorithm. On the other hand, ESDA fulfills minimal quotas,
unless justified envy is caused. In this case, as students are not removed but added up
for each supervisor, unfair feelings do not seem to occur. In fact, the example used in
Proposition 2 is feasible under ESDA:𝑡𝜇¦•§¨ = š𝑠 ,&𝑠(’𝑡(𝑠& , 𝑠“𝑡’𝑠” ›.

There is no cardinal domination between ESDA and DAMin. In the following
proposition, DAMin cardinally dominates ESDA.
Proposition 9. There is cardinally no dominating relationship between DAMin and
19

ESDA for any matching market.
Tomoeda (2018) also studies the model of a school choice with minimal quotas. He
proposes a mechanism called by Deferred Acceptance Mechanism with Precedence
Lists (DAPL). He also considers a dynamic DA based mechanism. In his model, forfulfilling minimal quotas, the rankings over students of the same type are dynamicallychanged, while maximal quotas are changed in DAMin. The DAPL is also strategyproof and satisfies a modified sense of stability (Tomoeda (2018) Proposition 2). The
proposed model is like our model, but it does not seem applicable to our situation
because interpretations of types in Tomoeda’s (2018) model and ours are different.
Tomoeda (2018) interprets a type as student’s characteristics, but we interpret a type asa student’s as well as supervisor’s affiliation. In other words, in Tomoeda (2018), a typeis defined only for students.
The inherent weakness of DAMin is the lack of strategy-proofness when areduction sequence is endogenously determined. However, some studies show thatmechanisms with some dynamic adjustment processes do not satisfy strategy-proofness.
For example, Haeringer and Iehlé (2016), who study a dynamic DA-based mechanism
such that students can resubmit their preferences for obtaining a better match in the laterstages of admission to a French college, prove that the mechanism is not strategy-proof.
Okumura (2017) studies a certain kind of school choice problem for resolving shortages
in childcare in nursery schools in Japan, where different quotas are set to different age
groups in each nursery school, and these quotas are dynamically adjusted in the schoolfor resolving co-existence of excess demand and supply for different age groups. The
proposed mechanism satisfies a modified sense of stability but is not strategy-proof.
However, if we put DAMin in the context of a large economy environment, it
would be possible to show that it is strategy-proof.8

4. Empirical data
The DAMin mechanism was implemented in 2016 at Future University Hakodate with
254 students and 67 supervisors. Totally, there are four courses in the university, andeach student belongs to at the most one course. In the following analyses, we refer to

8

For example, Kojima and Pathak (2009) study a large economy environment and thesame technique can be used to show strategy-proofness for DAMin in a large economy.
20

these courses as A, B, C, and D.9 Supervisors belong to either one of the four courses or
the Communication Media Laboratory (CML).
Students were recommended to apply to supervisors who belonged to the same
course, but they could apply to any supervisor in any course. In fact, 21.2% students (54out of 254) were assigned to supervisors in different courses. Due to this, althoughminimal quota was fulfilled for all the supervisors, the maximal quota for students in thesame course was not fulfilled for 7.5% supervisors (5 out of 67).
The maximal quotas for students in the same course were equal amongsupervisors in the same course. The maximal quotas were set to ensure that if every
student in the same course applied to supervisors in the same course, they could not be
unmatched. Therefore, the maximal quotas in each course were set equal to the numberof students in the course divided by the number of supervisors in the same course (if thecalculated number contained decimal points, it was rounded up to the closest integer).
The minimal quotas for students in the same course were basically equalamong supervisors belonging to the same course. However, it was different for the fourcourses, thereby reflecting the educational objective of each course. Supervisors had toset strictly positive minimal quotas for students who belonged to the same course, butthey could set minimal quotas equal to zero for students who belonged to different
courses. For supervisors who belonged to CML, maximal quotas were four and they
could set minimal quotas equal to zero for students in any course.
The number of students and supervisors, maximal and minimal quotas forstudents in the same course and in each course are summarized in Table 1.

# of students# of supervisors
Maximal quota
Minimal quota

A

B

C

D

CML

Total

62
13
6
2

62
12
6
2

86
19
4
2

44
13
4
3

0
10
4
0

254
67
-----

Table 1. # of students, # of supervisors, and maximal and minimal quotas for students inthe same course and in each course.
Students had to rank all the supervisors who belonged to the same course in
their submitted preferences, and supervisors also had to rank all the students who
belonged to the same course in their submitted priority orderings. When maximal quotas
9A, B, C, and D correspond to Complex Systems, Intelligent Systems, Information
Systems, and Information Design courses, respectively.
21

were set, this did not allow any student to be left unmatched. Students did not have torank supervisors in different courses, and supervisors also did not have to rank students
in different courses.
Given the preferences, priority orderings, maximal and minimal quotas, thematching outcome was determined by DAMin. No student was left unmatched, buteight supervisors could not fulfill their minimal quota at the first step of the algorithm in
DAMin. As a result, the quota adjusting process started and, finally, every supervisor
fulfilled her minimal quota at the 47th step.
The maximal ranking of a supervisor, as ranked by a student was 23 andminimal ranking was 14, depending on the number of supervisors in the course and a
student’s preference for supervisors in different courses.
Assignments in the final matching outcome
In the resulting matching, 71.7% students were matched with their first-choicesupervisor. Totally, 90% students were matched with their fifth or better supervisor. In
the worst-case scenario, a student was matched with his nineteenth choice. In the next
worst case, a student was matched with his fourteenth choice.
Rank

1st

2nd

3rd

4th

5th

6th

7th

8th

9th

10th

Freq.
%
Cum. %

182
71.7
71.7

22
8.7
80.3

13
5.1
85.4

9
3.5
89.0

5
2.0
90.0

6
2.4
93.3

2
0.8
94.1

4
1.6
95.7

4
1.6
97.2

0
0.0
97.2

Table 2. Matching results for students
The number of students who were assigned to their tenth choice, its relative
percentages, and cumulative percentages in the population are shown in Table 2.
Except for supervisors in the CML, the maximal number of students asupervisor ranked was 96 and minimal number was 47, depending on the number ofstudents in the course and the supervisor’s preference for students in different courses.
Up to four students applied to supervisors in the CML.
In the resulting matching, 21.7% students who were matched with supervisors
were their first-choice students. Totally 90.2% students whom supervisors were matchedwith were their 13th or better students. In the worst-case scenario, a supervisor wasmatched with his 81st choice. In next worst case, a supervisor was matched with his
73rd choice.
One may think that the matching outcome for supervisors are relatively worse
than students. However, note that supervisors had to accept up to their maximal quota.
22

Even in the best case, each supervisor had to accept four or more students, if the
maximal quota was fulfilled. Then, as 60.2% (73.6%) of students whom the supervisors
were matched with were up to their fourth (sixth) choice, relative performance of themechanism for supervisors is not worse than students (also remember that DAMin is a
student optimal.).
The number of supervisors who were assigned up to their tenth choice, its
relative percentages, and cumulative percentages in the population are shown in Table 3.
Rank

1st

2nd

3rd

4th

5th

6th

7th

8th

9th

10th

Freq.
%
Cum. %

55
21.7
21.7

42
16.5
38.2

30
11.8
50.0

26
10.2
60.2

22
8.7
68.9

12
4.7
73.6

12
4.7
78.3

11
4.3
82.7

5
2.0
84.6

4
1.6
86.2

Table 3. Matching results for supervisors
WelfareThe sums of a student’s rank for supervisor and a supervisor’s rank for a student in thestudent-supervisor pairs are shown in Table 4. If both a student and supervisor ismatched with their first choice, the sum of ranks is 2. Such cases occurred in 20.9%
matching cases. As already pointed out, each supervisor had to accept four or more
students, if the maximal quota is fulfilled, the sum of ranks should be 5 to 8. Then, 74%of the matching observed is such cases.
Rank

2

3

4

5

6

7

8

9

10

11-

Freq.
%
Cum. %

53
20.9
20.9

38
15.0
35.8

33
13.0
48.8

25
9.8
58.7

20
7.9
66.5

13
5.1
71.7

6
2.4
74.0

8
3.1
77.2

6
2.4
79.5

52
20.5
100.0

Table 4. Distribution of the sum of ranks for students and supervisors
Example 2 in Section 3 shows that if we consider the sum of ranks of the student andsupervisor in the final assignment as a measure of welfare, DAMin can dominate DA. It
is also the case in this matching. In fact, the sum of ranks of the student and supervisor
in the final assignment with the original DA is 2460, and the sum with DAMin withendogenous sequence is 2398. Thus, in this regard, DAMin improves welfare more thanDA.
Strategy-proofness23

In this student-supervisor matching, it is not possible to determine if students submitted
their true-preferences. Therefore, we asked students to respond via an online
questionnaire after the matching outcome was reported. About 45.3% students (115 outof 254) responded to the questionnaire.
Nearly 87.8% students (101 out of 115) answered that they are aware that thismatching process is based on the DA mechanism, 57.4% students (58 out of 101) readbooks or searched the Internet about the DA mechanism, 65.5% students (38 out of 58)
answered that they understood the DA mechanism, its working, and properties.
Nearly 54.8% students (63 out of 115) answered that strategy-proofness was
attractive, and 50.4% students (58 out of 115) responded that eliminating justified envy
is desirable.
About 41.7% students (48 out of 115) said that they had submitted true
preferences in full length, that is, ranked all the supervisors according to their true
preferences. Moreover, 55.7% students (64 out of 115) submitted true preferences forsupervisors whom they had ranked relatively higher. Only 2.6% students (3 out of 115)
did not submit their true preferences intentionally. In fact, they avoided their first-choicesupervisors. Probably they avoided popular supervisors and misrepresented their second
choice as their first choice.
Other strategic problems
In this matching process, before submitting their preferences, students had theopportunity to interview with supervisors for two weeks. For all students, theirpreferences for supervisors are usually incomplete information. This is partly because
they had never attended the lecture some supervisors taught. Thus, during this interview
period, recognizing each supervisor’s personality and educational and research
objective, students formed their “true” preferences. In this sense, preferences areendogenous (see Antler, 2015).
Nearly 97.4% students (112 out of 115) interviewed with at least one
supervisor. Students who interviewed with five or more supervisors were only 8.0% (9out of 112). About 75.0% students (84 out of 112) interviewed with two to four
supervisors, but 17.0% students (19 out of 112) interviewed with only one supervisor.
Though students were forced to submit their preferences for all supervisors in the same
course to avoid being unmatched, this result suggests that non-negligible number ofsupervisors were unacceptable to students. In other words, students’ preference wasvirtually truncated, that is, supervisors whom they had ranked as the first or a relatively
high choice were only reliable. It is well known that truncated preferences may cause24undesirable outcomes. Of course, as some students and supervisors knew each other, it
may be that students needed not search for other supervisors for achieving better
matching during the interview period.
Another concern is that students’ preference may be affected by supervisors’
persuasion during this interview period. In fact, we realized through informal talks withstudents that some supervisors made a credible threat to students that if they did notrank the supervisor as their first-choice, they would not accept them at all. As fulfillingmaximal quota was a major concern for some supervisors (gathering enough number ofstaff members in the laboratory was necessary to run the ongoing research project), they
had made such threats. These threats were really “credible” because supervisors could
submit their priority orderings after knowing students’ had submitted theirpreferences.10 This may be the reason that a large number of students were matchedwith their first choice.
Nonetheless, it is not clear if the truncated preference and/or credible threat
distorted the matching outcome. As a matter of fact, 80.0% students (92 out of 115)
answered that they had decided on submitted rankings according to their own
preferences. About 15.7% students (18 out of 115) worried about the competition for
popular supervisors, and 13.9% students (16 out of 115) answered that whether or not
known senior students have already been assigned to and/or mutual friends also applied
to the same supervisor was another factor of their choice, as in resident matching withcouples (Kojima and Kamada, 2013). Only 6.1% students (7 out of 115) randomly
decided.
These data seem to suggest that most students submitted their true preferences.

5. Discussion and conclusion
We have reported about a recent reform in the matching mechanism between students
and supervisors in a Japanese university. The proposed mechanism, DAMin, caneliminate justified envy among students with the same type, but does not satisfy
10

The chief of education committee and one of the authors (Kawagoe) of this study
strongly recommend that supervisors should submit their priority orderings without
knowing students’ preferences for avoiding any strategic effect. However, a nonnegligible number of supervisors claimed that they could not rank all students in thesame course without knowing their preferences. In a personal communication with
Fuhito Kojima, we were informed that he had ever heard of Alvin Roth also facing asimilar situation when he consulted the matching process for freshmen in a certain
university.
25

strategy-proofness and feasibility. As for strategy-proofness, experimental evidence
from laboratory experiments (Chen and Sönmez, 2006; Featherstone and Niederle,
2008; Pais and Pintér, 2008; Kawagoe et al., 2018) and field data (e.g., Echenique,Wilson and Yariv, 2013; Chen and Kesten, 2017) suggest that a non-negligible numberof students mispresent their preferences. Thus, it is still debatable if lack of strategyproofness is detrimental.
Although the fact that DAMin does not satisfy feasibility may be critical, in
actual matching outcomes in 2016, feasibility constraint was satisfied. This result may
be explained fully by extending our model to a large economic environment.11
During our discussion with the university education committee, a member
raised a question if submitting cardinal preferences may be better than ordinal
preferences to measure the strength of the preferences. The school choice problem withcardinal preferences studied so far is in the context of resolving the problem caused bytie-breaking.12 What causes matching process with type-specific quotas by allowing
cardinal preferences is not clear at this moment.
Another concern relates to the lattice structure of stable matching. As DAMin
is based on student-proposing DA, the resulting matching is student-optimal. However,a non-negligible number of supervisors seemed to feel uneasy about this. One of thereasons why endogenous reduction sequence was adopted in DAMin was to improvesupervisors’ welfare, as discussed in Remark 2 in subsection 3.2. If reflecting a
supervisor’s welfare as well as student’s is desirable, median matching or fractional
matching may be the candidate to achieve, although they are not strategy-proof.
However, we consider that reflecting a supervisor’s welfare is an important objective at
a matching mechanism between students and supervisors because as supervisors are
long-run players, they have more concern for the matching outcome than students. We
look forward to future research answering these questions.

1112

For example, see Kojima and Pathak (2009).
For example, see Abdulkadiroglu, Che and Yasuda (2015) .
26

Appendix A.
Proposition 1. DAMin eliminates justified envy among same type students.
Proof. Without loss of generality, consider DA with 𝑈 8 (𝑘 = 1, … , 𝑟). Denote thematching produced by DA with 𝑈 8 as 𝜇. Assume that a student 𝑠7 envies anotherstudent 𝑠C , who is the same type as his: 𝜇<𝑠C ? 𝑃16 𝜇(𝑠7 ) and 𝜏(𝑠7 ) = 𝜏<𝑠C ? = 𝜃. Let
step 𝑟 be the step in the DA algorithm at which student 𝑠7 is rejected from 𝜇(𝑠C ). In
step 𝑟, 𝑠7 is rejected because type 𝜃 specific minimal quota is filled with 𝐿Y<1Z?,ostudents of type 𝜃 ranked higher than 𝑠7 according to ≻Y<1Z ? , and the remaining seats8
are also filled with 𝑞Y<1
− ∑o∈t 𝐿Y<1Z ?,o students of any type ranked higher thanZ?

𝑠7 according to ≻Y(1Z ) . In future steps, a student accepted in step 𝑟 can be rejected fromtype 𝜃 specific minimal quota only if a higher ranked student of type 𝜃 applies, andthe same is true for students in the remaining seats. Thus, at the end of the algorithm, allstudents assigned to 𝜇(𝑠C ) either in type 𝜃 specific minimal quota or in the remaining
seats must be ranked higher than 𝑠7 . Since 𝜏<𝑠C ? = 𝜃 as well, this implies that𝑠C ≻Y<1Z ? 𝑠7 , that is, 𝑠7 does not have any justified envy against 𝑠C .
Q.E.D.
Proposition 2. For any preference profile, DAMin may not be a feasible matching.
Proof. We prove the statement with the following example. There are five students 𝑆 ={𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” } and there are two types 𝛩 = {𝜃& , 𝜃( }. So, the students are divided as
𝑆o2 = {𝑠& , 𝑠( } and 𝑆o3 = {𝑠’ , 𝑠“ , 𝑠” }. There are three supervisors 𝑇 = {𝑡& , 𝑡( , 𝑡’ }, andthey are divided as 𝑇o2 = {𝑡& , 𝑡( } and 𝐶o3 = {𝑡’ }. Total quotas, and type-specificminimal and maximal quotas are as follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (2, 1, 1),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (2, 1, 2),<𝑞=– , 𝐿=– ,o3 , 𝑈=– ,o3 ? = (1, 1, 1)}.

Under true preference profiles for each student
𝑃12 : 𝑡( 𝑡& 𝑡’ ,𝑃13 : 𝑡( 𝑡& 𝑡’ ,𝑃1– : 𝑡& 𝑡( 𝑡’ ,𝑃1— : 𝑡& 𝑡( 𝑡’ ,27

𝑃1˜ : 𝑡’ 𝑡& 𝑡( ,and priority orderings for each supervisor≻=2 : 𝑠’ 𝑠“ 𝑠( 𝑠& 𝑠” ,≻=3 : 𝑠& 𝑠( 𝑠’ 𝑠“ 𝑠” ,≻=– : 𝑠( 𝑠” 𝑠’ 𝑠“ 𝑠& ,the resulting in final matching with DAMin as follows.
𝑡
𝜇 = š𝑠 ,&𝑠’𝑡(𝑠& , 𝑠(

“

𝑡’
𝑠” ›.

However, 𝜇 is not feasible because no type 𝜃& student is assigned to type 𝜃&supervisor 𝑐& .
Q.E.D.
Proposition 3. For any 𝑃, DAMin is not strategy-proof.
Proof. We prove the statement with the following example. There are five students 𝑆 ={𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” } and there are two types 𝛩 = {𝜃& , 𝜃( }. Thus, the students are divided
as 𝑆o2 = {𝑠& , 𝑠( , 𝑠’ , 𝑠“ } and 𝑆o3 = {𝑠” }. There are three supervisors 𝑇 = {𝑡& , 𝑡( , 𝑡’ },and they are divided as 𝑇o2 = {𝑡& , 𝑡( } and 𝑇o3 = {𝑡’ }. Total quotas, and type-specificminimal and maximal quotas are as follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (2, 1, 2),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (1, 1, 1),<𝑞=– , 𝐿=– ,o3 , 𝑈=– ,o3 ? = (2, 1, 2)}.

Under true preference profiles for each student
𝑃12 : 𝑡& 𝑡( 𝑡’ ,𝑃13 : 𝑡& 𝑡( 𝑡’ ,𝑃1– : 𝑡’ 𝑡& 𝑡( ,𝑃1— : 𝑡& 𝑡’ 𝑡( ,𝑃1˜ : 𝑡’ 𝑡& 𝑡( ,and priority orderings for each supervisor≻=2 : 𝑠( 𝑠& 𝑠’ 𝑠“ 𝑠” ,≻=3 : 𝑠& 𝑠’ 𝑠( 𝑠“ 𝑠” ,≻=– : 𝑠“ 𝑠” 𝑠’ 𝑠( 𝑠& ,the resulting final matching with DAMin is as follows.
𝑡𝜇(𝑃) = š𝑠 &
(

𝑡(
𝑠&
28

𝑡’
𝑠“ , 𝑠”𝑠’𝑠’ ›.

Consider that student 𝑠’ states the following preference instead (any other student
reveals true preference.).
𝑃′1– : 𝑡( 𝑡& 𝑡’ .
Then, the resulting final matching with DAMin is as follows.
𝑡𝜇(𝑃h1– , 𝑃1f– ) = š𝑠 , &𝑠
&

𝑡(
𝑠’

(

𝑡’
𝑠“ , 𝑠” ›.

In this matching outcome, student 𝑠’ is strictly better off than in 𝜇(𝑃). Thus, student
𝑠’ has an incentive to misrepresent her true preference.
Q.E.D.
Proposition 4. DAMin is not necessarily Pareto dominated by DA.
We prove the statement with the following example. There are five students 𝑆 ={𝑠& , 𝑠( , 𝑠’ , 𝑠“ } and there are two types 𝛩 = {𝜃& , 𝜃( }. So, the students are divided as
𝑆o2 = {𝑠& , 𝑠( , 𝑠’ } and 𝑆o3 = {𝑠“ }. There are three supervisors 𝑇 = {𝑡& , 𝑡( , 𝑡’ }, andthey are divided as 𝑇o2 = {𝑡& , 𝑡( } and 𝑇o3 = {𝑡’ }. Total quotas, and type-specificminimal and maximal quotas are as follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (2, 1, 2),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (1, 1, 1),<𝑞=– , 𝐿=– ,o3 , 𝑈=– ,o3 ? = (2, 1, 2)}.

Under true preference profiles for each student
𝑃12 : 𝑡& 𝑡( 𝑡’ ,𝑃13 : 𝑡& 𝑡( 𝑡’ ,𝑃1– : 𝑡( 𝑡& 𝑡’ ,𝑃1— : 𝑡’ 𝑡& 𝑡( ,and priority orderings for each supervisor≻=2 : 𝑠( 𝑠& 𝑠’ 𝑠“ ,≻=3 : 𝑠& 𝑠’ 𝑠( 𝑠“ ,≻=– : 𝑠“ 𝑠’ 𝑠( 𝑠& ,the resulting final matching with DAMin is as follows.
𝑡𝜇§¨¥7* (𝑃) = š𝑠 , &𝑠
&

(

𝑡(
𝑠’

𝑡’
𝑠“ ›.

the resulting final matching with the original DA is as follows.
𝑡𝜇§¨ (𝑃) = š𝑠 , &𝑠
&

(

𝑡(
𝑠’

𝑡’
𝑠“ ›.

Thus, both matching outcomes are the same. Therefore, we conclude that DAMin is not29

Pareto dominated by the original DA.

Q.E.D.

Proposition 5. The DAMin is not necessarily cardinally dominated by DA.
Proof. We prove this statement using an example. There are three students 𝑆 ={𝑠& , 𝑠( , 𝑠’ } and there is one type 𝛩 = {𝜃& }; thus, assuming that every student is thesame type, 𝑆o2 = {𝑠& , 𝑠( , 𝑠’ }. There are two supervisors 𝑇 = {𝑡& , 𝑡( }, and their types
are the same as students, 𝑇o2 = {𝑡& , 𝑡( }. Total quotas, type-specific minimal andmaximal quotas are as follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (3, 1, 3),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (2, 1, 2)}.
Under preference profiles for each student
𝑃12 : 𝑡& 𝑡( ,𝑃13 : 𝑡& 𝑡( ,𝑃1– : 𝑡& 𝑡( ,and priority orderings for each supervisor;≻=2 : 𝑠& 𝑠( 𝑠’ ,≻=3 : 𝑠’ 𝑠& 𝑠( ,the resulting final matching with the original DA is as follows.
𝜇(𝑃) = £𝑡&𝑠& , 𝑠( , 𝑠’𝑡(¤∅

The sum of ranks of the student and supervisor at final assignment in this case is 9. The
resulting final matching with DAMin either with endogenous or exogenous sequence is
as follows.
𝑡𝜇′(𝑃) = š𝑠 ,&𝑠
&

(

𝑡(
𝑠’ ›

The sum of ranks of the student and supervisor at final assignment in this case is 8.
Q.E.D.
Proposition 6. If a school’s priority structures are essentially homogeneous, thenDAMin is cardinally dominated by DA.
Proof. Let 𝛼 be the sum of ranks of the student and supervisor under the original DA
matching outcome. If the matching outcome satisfied minimum quotas for all
supervisors, then the sum of ranks of the student and supervisor under the
DAMin matching outcome would be 𝛼.
30

Next, we consider a case in which the matching outcome does not satisfy minimum
quotas for some supervisors. We divide 𝛼 into two: 𝛼 = 𝛼 • + 𝛼 s . Let 𝛼 • be thesum of ranks of student, and 𝛼 s be the sum of ranks of supervisor. By the DA
procedure, 𝛼 • becomes necessarily larger than the sum of ranks of student 𝛼′• . We
prove 𝛼 s becomes necessarily bigger than the sum of ranks of supervisor. 𝛼 fs . To run
the proof, we assume that 𝛼 fs < 𝛼 s . Thus, some supervisor is matched with better
students under the DAMin than under the DA. Let the student and the supervisor be 𝑠&
and 𝑡& , respectively. By the DA procedure, 𝑠& is matched with a better supervisor
under the DA than under the DAMin. Supervisor 𝑡& has two cases: in case 1, 𝑡& is notsatisfied with the minimum quota; in case 2, 𝑡& is matched with a student worse than𝑠& . By assuming the priority structure, both cases also become 𝛼 fs = 𝛼 s . This is acontradiction. Thus, we consider the following relation:𝛼 = 𝛼 • + 𝛼 s < 𝛼 f• + 𝛼 fs = 𝛼′.
Q.E.D.
Proposition 7. There is no Pareto domination relationship between DAMin with an
endogenous sequence and the one with an exogenous sequence for any matchingmarket.
Proof. We prove the statement by the following example.
There are five students 𝑆 = {𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” } and there are two types 𝛩 = {𝜃& , 𝜃( }.
So, the students are divided as 𝑆o2 = {𝑠& , 𝑠( , 𝑠’ } and 𝑆o3 = {𝑠“ , 𝑠” }. There are three
supervisors 𝑇 = {𝑡& , 𝑡( , 𝑡’ }, and they are divided as 𝑇o2 = {𝑡& , 𝑡( } and 𝑇o3 = {𝑡’ }.
The total quotas and type-specific minimal and maximal quotas are as follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (2, 1, 2),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (2, 1, 1),<𝑞=– , 𝐿=– ,o3 , 𝑈=– ,o3 ? = (2, 2, 2)}.

Under true preference profiles for each student
𝑃12 : 𝑡& 𝑡( 𝑡’ ,𝑃13 : 𝑡( 𝑡& 𝑡’ ,𝑃1– : 𝑡& 𝑡& 𝑡& ,𝑃1— : 𝑡’ 𝑡& 𝑡( ,𝑃1˜ : 𝑡’ 𝑡& 𝑡( ,and the priority orderings for each supervisor31≻=2 : 𝑠( 𝑠& 𝑠’ 𝑠“ 𝑠” ,≻=3 : 𝑠( 𝑠’ 𝑠& 𝑠“ 𝑠” ,≻=– : 𝑠“ 𝑠” 𝑠’ 𝑠( 𝑠& ,the resulting final matching with DAMin with an endogenous reduction sequence is asfollows.
𝑡𝜇(𝑃) = š𝑠 𝑠&

& ’

𝑡(
𝑠(

𝑡’
𝑠“ , 𝑠” ›.

For DAMin with an exogenous reduction sequence, suppose that the sequence is given
as {𝑈& = (2, 1, 2), 𝑈 ( = (1, 1,1) }. Then, the resulting final matching is as follows.
𝑡𝜇(𝑃) = š𝑠 𝑠&

& ’

𝑡(
𝑠(

𝑡’
𝑠“ , 𝑠” ›.

Both matchings are the same. Thus, there is no Pareto domination among both types of
DAMin.
Q.E.D.

Proposition 8. There is no cardinal domination relationship between both types of
DAMin.
Proof. We show the statement with the following example. There are six students 𝑆 ={𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” , 𝑠ª } and there are two types 𝛩 = {𝜃& , 𝜃( }. So, the students are divided
as 𝑆o2 = {𝑠& , 𝑠( , 𝑠’ , 𝑠ª } and 𝑆o3 = {𝑠“ , 𝑠” }. There are three supervisors 𝑇 ={𝑡& , 𝑡( , 𝑡’ }, and they are divided as 𝑇o2 = {𝑡& } and 𝑇o3 = {𝑡( , 𝑡’ }. Total quotas, andtype-specific minimal and maximal quotas are as follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (4, 1, 3),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (2, 1, 2),<𝑞=– , 𝐿=– ,o3 , 𝑈=– ,o3 ? = (2, 1, 2)}.

Under true preference profiles for each student
𝑃12 : 𝑡& 𝑡( 𝑡’ ,𝑃13 : 𝑡& 𝑡’ 𝑡( ,𝑃1– : 𝑡& 𝑡( 𝑡’ ,𝑃1— : 𝑡’ 𝑡( 𝑡& ,𝑃1˜ : 𝑡’ 𝑡( 𝑡& ,𝑃1¬ : 𝑡& 𝑡( 𝑡’ ,32and priority orderings for each supervisor≻=2 : 𝑠ª 𝑠& 𝑠’ 𝑠( 𝑠“ 𝑠” ,≻=3 : 𝑠“ 𝑠’ 𝑠( 𝑠& 𝑠ª 𝑠” ,≻=– : 𝑠“ 𝑠( 𝑠” 𝑠& 𝑠’ 𝑠ª ,the resulting final matching with DAMin with endogenous sequence 𝜇-* is as follows.
Note that the priority structures have a cyclic structure.
𝑡𝜇-* = š𝑠 , 𝑠 & , 𝑠
&

’

𝑡(
𝑠”

ª

𝑡’
𝑠( , 𝑠“ ›.

The sum of ranks of the student and supervisor is 18.
For DAMin with an exogenous reduction sequence, suppose that the sequence is given
as {𝑈& = (3, 2, 2), 𝑈 ( = (3, 2, 1) }. Then, the resulting final matching with DAMin
with an endogenous sequence 𝜇-® :𝑡
𝜇-® = š𝑠 , 𝑠 , 𝑠& , 𝑠
&

(

’

ª

𝑡(
𝑠”

𝑡’
𝑠“ ›.

The sum of ranks of the student and supervisor is 24.
On the other hand, the following example shows that the sum of ranks of the student
and supervisor under DAMin with an exogenous one is lower than those under DAMin
with an endogenous sequence.
There are six students 𝑆 = {𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” , 𝑠ª } and there is one type 𝛩 = {𝜃& }. So,
the students are divided as 𝑆o2 = {𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” , 𝑠ª }. There are three supervisors 𝑇 ={𝑡& , 𝑡( , 𝑡’ }, and they are divided as 𝑇o2 = {𝑡& , 𝑡( , 𝑡’ }. The total quotas and typespecific minimal and maximal quotas are as follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (3, 1, 3),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (2, 1, 2),<𝑞=– , 𝐿=– ,o2 , 𝑈=– ,o2 ? = (3, 1, 3)}.

Under true preference profiles for each student
𝑃12 : 𝑡& 𝑡( 𝑡’ ,𝑃13 : 𝑡’ 𝑡& 𝑡( ,𝑃1– : 𝑡& 𝑡( 𝑡’ ,𝑃1— : 𝑡’ 𝑡( 𝑡& ,𝑃1˜ : 𝑡’ 𝑡( 𝑡& ,33

𝑃1¬ : 𝑡& 𝑡( 𝑡’ ,and priority orderings for each supervisor≻=2 : 𝑠ª 𝑠& 𝑠“ 𝑠( 𝑠’ 𝑠” ,≻=3 : 𝑠” 𝑠“ 𝑠( 𝑠& 𝑠ª 𝑠’ ,≻=– : 𝑠“ 𝑠( 𝑠” 𝑠& 𝑠’ 𝑠ª ,the resulting final matching with DAMin with an endogenous sequence 𝜇-* is asfollows. Note that the priority structures have a cyclic structure.
𝑡𝜇-* = š𝑠 ,&𝑠
&

𝑡(
𝑠’

ª

𝑡’
𝑠( , 𝑠“ , 𝑠” ›.

The sum of ranks of the student and supervisor is 23. For DAMin with an exogenous
reduction sequence, suppose that the sequence is given as {𝑈& = (3, 2, 3), 𝑈 ( =(3, 2, 2) }. Then, the resulting final matching with DAMin with an endogenous
sequence 𝜇-® :𝑡
𝜇-® = š𝑠 , 𝑠 &, 𝑠
&

’

ª

𝑡(
𝑠”

𝑡’
𝑠( , 𝑠“ ›.

The sum of students’ and supervisors’ rank is 19.
Q.E.D.
Proposition 9. There are no cardinally dominant relationships between DAMin and
ESDA for any matching market.
Proof. We show the statement with the following example. There are five students 𝑆 ={𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” } and there is one type 𝛩 = {𝜃& }. So, the students are divided as 𝑆o2 ={𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” }. There are three supervisors 𝑇 = {𝑡& , 𝑡( , 𝑡’ }, and they are divided as
𝑇o2 = {𝑡& , 𝑡( , 𝑡’ }. Total quotas, type-specific minimal and maximal quotas are as
follows.
(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (3, 1, 3),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (2, 1, 2),<𝑞=– , 𝐿=– ,o2 , 𝑈=– ,o2 ? = (2, 1, 2)}.

Under true preference profiles for each student
𝑃12 : 𝑡& 𝑡( 𝑡’ ,𝑃13 : 𝑡& 𝑡( 𝑡’ ,𝑃1– : 𝑡& 𝑡( 𝑡’ ,34

𝑃1— : 𝑡( 𝑡’ 𝑡& ,𝑃1˜ : 𝑡( 𝑡& 𝑡’ ,and priority orderings for each supervisor≻=2 : 𝑠& 𝑠( 𝑠’ 𝑠“ 𝑠” ,≻=3 : 𝑠” 𝑠“ 𝑠’ 𝑠( 𝑠& ,≻=– : 𝑠& 𝑠( 𝑠’ 𝑠“ 𝑠” ,the resulting final matching with DAMin 𝜇¥7* is as follows:𝑡𝜇¥7* = š𝑠 ,&𝑠&(𝑡(𝑠“ , 𝑠”𝑡’𝑠’ ›.

The sum of ranks of the student and supervisor is 16. The resulting final matching with
ESDA, 𝜇¦•§¨ is as follows:𝑡𝜇¦•§¨ = š𝑠 , 𝑠& , 𝑠
&

(

’

𝑡(
𝑠”

𝑡’
𝑠“ ›.

The sum of ranks of the student and supervisor is 17.
On the other hand, the following example is that ESDA cardinally dominates DAMin.
There are five students 𝑆 = {𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” } and there is one type 𝛩 = {𝜃& }. So, thestudents are divided as 𝑆o2 = {𝑠& , 𝑠( , 𝑠’ , 𝑠“ , 𝑠” }. There are three supervisors 𝑇 ={𝑡& , 𝑡( , 𝑡’ }, and they are divided as 𝑇o2 = {𝑡& , 𝑡( , 𝑡’ }. The total quotas and typespecific minimal and maximal quotas are as follows:(𝑞, 𝐿, 𝑈) ={<𝑞=2 , 𝐿=2 ,o2 , 𝑈=2 ,o2 ? = (3, 1, 3),<𝑞=3 , 𝐿=3 ,o2 , 𝑈=3 ,o2 ? = (2, 1, 2),<𝑞=– , 𝐿=– ,o2 , 𝑈=– ,o2 ? = (2, 1, 2)}.

Under true preference profiles for each student
𝑃12 : 𝑡& 𝑡( 𝑡’ ,𝑃13 : 𝑡& 𝑡( 𝑡’ ,𝑃1– : 𝑡& 𝑡( 𝑡’ ,𝑃1— : 𝑡( 𝑡’ 𝑡& ,𝑃1˜ : 𝑡( 𝑡& 𝑡’ ,and priority orderings for each supervisor≻=2 : 𝑠& 𝑠( 𝑠’ 𝑠“ 𝑠” ,≻=3 : 𝑠” 𝑠“ 𝑠’ 𝑠( 𝑠& ,≻=– : 𝑠“ 𝑠& 𝑠( 𝑠’ 𝑠” ,the resulting final matching with DAMin 𝜇¥7* is as follows:35

𝑡
𝜇¥7* = š𝑠 ,&𝑠&(𝑡(𝑠“ , 𝑠”𝑡’𝑠’ ›.

The sum of ranks of the student and supervisor is 17. The resulting final matching with
ESDA, 𝜇¦•§¨ is as follows:𝑡𝜇¦•§¨ = š𝑠 , 𝑠& , 𝑠
&

(

’

𝑡(
𝑠”

𝑡’
𝑠“ ›.

The sum of ranks of the student and supervisor is 14.
Q.E.D.

36

References
Abdulkadiroglu, A. (2003) “College admissions with affirmative action.” Columbia
University, Department of Economics, Discussion Papers, 0203–19.
Abdulkadiroglu, A. (2005) “College admissions with affirmative action.” International
Journal of Game Theory 33 (4), 535–549.
Abdulkadiroglu, A. and Sönmez, T. (2003) “School choice: a mechanism design
approach.” American Economic Review 98 (3), 729–747.
Abdulkadiroğlu, A., Che, Y. K. and Yasuda, Y. (2015). “Expanding “choice” in school
choice.” American Economic Journal: Microeconomics 7(1), 1–42.
Antler, Y. (2015) “Two-sided matching with endogenous preferences.” American
Economic Journal: Microeconomics 7(3), 241–258.
Aygün, O. and Bo, I. (2012) “College admission with multidimensional privileges: The
Brazilian affirmative action case,” Technical Report, mimeo.
Calsamiglia, C., Haeringer, G. and Klijn, F. (2010) “Constrained school choice: An
experimental study.” American Economic Review, 100 (4), 1860–1874.
Chen, P., Egesdal, M., Pycia, M. and Yenmez, M. B. (2016) “Manipulability of stablemechanisms.” American Economic Journal: Microeconomics, 8, 202–14.
Chen, Y. and Kesten, O. (2017) “Chinese college admissions and school choice reforms:
Theory and evidence.” Journal of Political Economy 125, 1, 99-139.
Chen, Y. and Sönmez, T. (2006) “School choice: An experimental study.” Journal of
Economic Theory, 127, 202–231.
Echenique, F., Wilson, A. J. and Yariv, L. (2016) “Clearing house for two-sided matching:
An experimental study.” Quantitative Economics, 7, 449–482
Ehlers, L., Hafalir, I., Yenmez, M. B. and Yildirim M. A. (2014) “School choice with
controlled choice constraints: Hard bounds versus soft bounds,’’ Journal of Economic
37

Theory, 153, 648–683.
Ergin, H. (2002): “Efficient Resource Allocation on the Basis of Priorities,”
Econometrica, 88, 485–494.
Featherstone, C. and Niederle, M. (2008) “Ex ante efficiency in school choicemechanisms: An experimental investigation.” NBER Working Paper Series, Working
Paper 14618.
Fragiadakis, D., Iwasaki, A., Troyan, P., Ueda, S. and Yokoo, M. (2015) “Strategy-proof
matching with minimum quotas.” ACM Transactions on Economics and Computation,
4, 6.
Fragiadakis, D. and Troyan, P. (2017) “Improving matching under hard distributional
constraints.” Theoretically Economics, 12, 863–908.
Gale, D. and Shapley, L. S. (1962) “College admissions and the stability of marriage.”
The American Mathematical Monthly 69(1), 9–15.
Haeringer, G. and Iehlé, V. (2016) “Timely matching.” mimeo.
Hafalir, I. E., Yenmez, M. B. and Yildrim, M. A. (2013) “Effective affirmative action inschool choice.” Theoretical Economics, 8(2), 325–63.
Kamada, Y. and Kojima, F. 2015 "Efficient matching under distributional constraints:
theory and applications." American Economic Review, 105(1), 67–99.
Kawagoe, T., Matsubae, T. and Takizawa, H. (2018) “The Skipping-down strategy andstability in school choice problems with affirmative action: Theory and experiment.”
Games and Economic Behavior, 109, 212–239.
Kesten, O. 2006. “On two competing mechanisms for priority-based allocation
problems.” Journal of Economic Theory ,127, 155–171.
Kojima, F. (2012) “School choice: Impossibilities for affirmative action.” Games andEconomic Behavior, 75 (2), 685–693.
38

Kojima, F. 2013. “Efficient resource allocation under multi-unit demand.” Games andEconomic Behavior, 82, 1–14.
Kojima, F. and Pathak, P. A. (2009) ‘‘Incentives and Stability in Large Two-Sided
Matching Markets,’’ American Economic Review, 99 (2009), 608–627.
Matsubae, T. (2011) “Do the minority students benefit from affirmative action policy inschool choice markets? Reconsidered.” SSRN (Social Science Research Network) ID:
270111.
Okumura, Y. (2017) “School choice with general constraints: a market design approachfor the nursery school waiting list problem in Japan.” Japanese Economic Review,https://doi.org/10.1111/jere.12212.
Pais, J. and Pintér, Á. (2008) “School choice and information: an experimental study onmatching mechanisms.” Games and Economic Behavior, 64, 303–328.
Roth, A. E. (1982) “The economics of matching: stability and incentives.” Mathematics
of Operations Research, 7, 617–628.
Roth, A. E. (1984) “The evolution of the labor market for medical interns and residents:
a case study in game theory.” Journal of Political Economy, 92, 991–1016.
Roth A. E. (1991) “A natural experiment in the organization of entry-level labormarkets: regional markets for new physicians and surgeons in the United Kingdom.”
American Economic Review, 81(3), 415–440.
Roth, A. E. (2008) “Deferred acceptance algorithms: history, theory, practice, and open
questions.” International Journal of Game Theory, 6(3), 537–569.
Roth, A. E. and Peranson, E. (1999) “The redesign of the matching market for American
physicians: some engineering aspects of economic design.” American Economic
Review, 89, 748–780.
Roth, A. E. and Sotomayor, M. A. O. (1990) Two-Sided Matching: A Study in Game
39

Theoretic Modeling and Analysis. Econometric Society monographs, Cambridge.
Sönmez, T. (1997) “Manipulation via capacities in two-sided matching Markets.”
Journal of Economic Theory, 77, 197–204.
Sönmez, T. (1999) “Can pre-arranged matches be avoided in two-sided matchingmarkets?” Journal of Economic Theory, 86, 148–156.
Sönmez, T. and Unver, U. (2009) “Matching, allocation, and exchange of discrete
resources.” Forthcoming, Handbook of Social Economics, eds. Jess Benhabib, Alberto
Bisin, and Matthew Jackson, Elsevier.
Tomoeda, K. (2018) “Finding a stable matching under type-specific minimum quotas.”
Journal of Economic Theory, 176, 81–117.

40