Institute for Economic Studies, Keio University
Keio-IES Discussion Paper Series

Inter-attribute equity in assignment problems:Leveling the playing field by priority design
Morimitsu Kurino、Tetsutaro Hatakeyama

14 June, 2022
DP2022-009
https://ies.keio.ac.jp/en/publications/18647/

Institute for Economic Studies, Keio University
2-15-45 Mita, Minato-ku, Tokyo 108-8345, Japan
ies-office@adst.keio.ac.jp
14 June, 2022

Inter-attribute equity in assignment problems:Leveling the playing field by priority design
Morimitsu Kurino、Tetsutaro Hatakeyama
Keio-IES DP2022-009
14 June, 2022
JEL Classification: C78; D47; D78
Keywords: Priority-based assignmen;Market design;Equity in attributes;The relative
position rule
Abstract
Priorities over agents are crucial primitives in assignment problems of indivisible
objects without monetary transfers. In this paper, we introduce a prioritization
problem: there are several exogenous attributes and each agent is equipped with one
such attribute, and the priority is initially determined only for agents with the same
attribute. This leads to a partial priority order. Our problem is to construct a complete
priority, which is needed to implement a known mechanism such as the serial
dictatorship. We propose a simple prioritization rule called the relative position rule.
We formulate three equity axioms and an invariance property; the priority
preservation law, the equal treatment of equal positions, the equal split, and theattribute-wise consistency. We show that the relative position rule is characterized bythese equity axioms. The result is applicable to general assignment problems withpartial priorities. In the context of college students’ exchange programs, the rule levels
the playing field in the sense that inequality across attributes is partially reduced.
Morimitsu Kurino
Faculty of Economics, Keio University
2-15-45 Mita, Minato-ku, Tokyokurino@econ.keio.ac.jp
Tetsutaro Hatakeyama
Graduate School of Economics, Keio University
2-15-45 Mita, Minato-ku, Tokyot.hatakeyama@keio.jp
Acknowledgement : We thank Hidekazu Anno, Takako Fujiwara-Greve, Toru Hokari,
Masatoshi Tsumagari, and participants at the 2022 Japanese Economic Association
Spring Meeting for helpful comments and suggestions. Hatakeyama acknowledges thefinancial support from JST SPRING, under Grant Number JPMJSP2123. Kurino
acknowledges the financial support from AMED under Grant Number JP21zf0127005,
JSPS KAKENHI 20K20279 and 22H00828. All remaining errors are our own.

Inter-attribute equity in assignment problems: Leveling theplaying field by priority design∗
Tetsutaro Hatakeyama†Morimitsu Kurino‡

June 14, 2022

Abstract
Priorities over agents are crucial primitives in assignment problems of indivisible objects
without monetary transfers. In this paper, we introduce a prioritization problem: there areseveral exogenous attributes and each agent is equipped with one such attribute, and thepriority is initially determined only for agents with the same attribute. This leads to a partialpriority order. Our problem is to construct a complete priority, which is needed to implementa known mechanism such as the serial dictatorship. We propose a simple prioritization rulecalled the relative position rule. We formulate three equity axioms and an invariance property;
the priority preservation law, the equal treatment of equal positions, the equal split, and theattribute-wise consistency. We show that the relative position rule is characterized by theseequity axioms. The result is applicable to general assignment problems with partial priorities.
In the context of college students’ exchange programs, the rule levels the playing field in thesense that inequality across attributes is partially reduced.
JEL Classification: C78; D47; D78
Keywords: Priority-based assignment; Equity in attributes; The relative position rule; Market
design∗We thank Hidekazu Anno, Takako Fujiwara-Greve, Toru Hokari, Masatoshi Tsumagari, and participants atthe 2022 Japanese Economic Association Spring Meeting for helpful comments and suggestions. Hatakeyama
acknowledges the financial support from JST SPRING, under Grant Number JPMJSP2123. Kurino acknowledges
the financial support from AMED under Grant Number JP21zf0127005, JSPS KAKENHI 20K20279 and 22H00828.
All remaining errors are our own.
†
Keio University, Graduate School of Economics, 2-15-45 Mita, Minato-ku, Tokyo 108-8345, Japan; email:t.hatakeyama@keio.jp‡
Keio University, Faculty of Economics, 2-15-45 Mita, Minato-ku, Tokyo 108-8345, Japan; email:kurino@econ.keio.ac.jp1

1

Introduction

Indivisible goods allocation problems without monetary transfers are often encountered in real life
markets such as on-campus housing (Abdulkadiroğlu and Sönmez, 1999; Kurino, 2014) and school
choice problems (Abdulkadiroğlu and Sönmez, 2003). The mechanisms used in these markets often
need a priority, or a complete and transitive order over agents. In general, the priority is formed
by a law or exogenous rule, which the literature has focused on.1 However, there is the case wherepriority has to be endogenously formed for a mechanism. In this paper, we study how to constructa priority fairly.
Universities all over the world have exchange programs in which millions of students study
abroad at their partner universities.2 Allocation of programs fairly to applicants at a low operating
cost is crucial for universities. One university in Japan, which consulted the authors, has sucha process of assigning about 400 students to hundreds of programs every year. Let us call thisuniversity “University X”.3 Due to the advantage of strategy-proofness and Pareto eﬃciency, it uses
an allocation mechanism of serial dictatorship: given priority over students, the highest-priority
student is assigned her most preferred program, the second-highest priority student her most
preferred among the remaining programs, and so on.4 However, before applying this mechanism,
it is necessary to construct a complete priority order. One way is to use the grade point average(GPA). However, because every student belongs to one of several faculties and then takes courses
oﬀered by that faculty with its own grading policy, the simple use of GPA would not be fairto all faculties.5 For this reason, University X held face-to-face interviews to have a complete
priority. However, conducting such interviews has become costly due to an increase in the number
of applicants. Therefore, University X decided to reform this prioritization process to a centralized
rule. The problem that needs to be solved is how to construct a complete priority from partialpriority where priority is available based on student GPAs derived from diﬀerent grading policies
of diﬀerent faculties. Then there is a conflict among faculties, because every faculty would want
the priority to favor its own students. Hence, University X faced a prioritization problem of setting
a fair rulebecause a priority ordering of students from various faculties is not complete but partial.
Motivated by University X’s example, we formulate the prioritization problem as an assignment
problem of assigning exogenous K priority groups to agents when preferences are common and1
To allocate dormitory rooms to students, many universities in the United States use seniority-based priority.
There are two priority groups, higher-priority group of non-freshmen and lower-priority group of freshmen. In
Boston public high school matching, there are typically three priority groups: the first-priority group of students
who have siblings attending the school, the second-priority group of students who live in the school’s walk zone,
and the last-priority group of remaining students.
2
For example, see the webpage https://www.statista.com/chart/3624/the-countries-with-the-most-studentsstudying-abroad/ for details (accessed March 25, 2022).
3
We are keeping its name secret due to a confidentiality agreement. We can provide the name upon request.
4
For example, see Svensson (1994; 1999) for the serial dictatorship.
5
For example, suppose there are two faculties, one with a mild grading policy and the other with a harsh grading
policy. A complete priority only by GPA favors the students of the former.

2

Figure 1: Prioritization problem

Note: Each “o” is a student. At first (left of the rule), students are ordered only within the same faculties. After
applying a rule (right of the rule), all students are weakly ordered. Students within the same group have the samepriority, while group 2’s students have strictly higher priority than group 1’s.

priorities are partial. Preferences here are over priority groups. Since it is natural to think thatevery agent prefers higher groups, we take agents’ preferences as common. Each agent is equippedwith one exogenous attribute, and the priority is determined for any two agents with the same
attribute, but not for diﬀerent attributes. In other words, we cannot compare any two agents acrossdiﬀerent attributes. The solution to this problem is a prioritization rule of finding a complete andtransitive (not necessarily linear) priority over agents, equivalently an assignment of agents K
priority groups.
To find a fair prioritization rule, we take an axiomatic approach as follows. We first state
how agents should be compared as three new axioms called the priority preservation law (PPL),the equal treatment of equal positions (ETP), and the equal split (ES). The priority preservation
law requires that, for any two agents of the same attribute, an agent of a lower position in apartial priority should not obtain a higher position in the resulting complete priority. The equal
treatment of equal positions, the equal treatment of equals in our context, compares students ofdistinct attributes by their relative positions, i.e., ranks in an attribute scaled to an interval (0,1].
It requires that two agents of the same relative positions should obtain exactly the same priority
group in the resulting complete priority. The equal split is a requirement regarding the equity indiﬀerent relative position levels. It says that for each attribute, if possible, the number of agentsthat fall into one priority group should be equal to that fall into another. In addition, we also
require one invariance property for the rule, called the attribute-wise consistency (AC). Whileconsistency axioms for assignment problems have been studied in literature (e.g., Ergin, 2000), theattribute-wise consistency requires that, when agents of some attribute leave with their assigned
objects, it does not aﬀect the assignment of remaining agents.
We introduce a prioritization rule, called the relative position rule. This rule assigns eachagent to a corresponding priority group with respect to her relative position in her own attribute.
The main features of this rule are: (i) it determines the assignment only by the information on3each agent’s own attribute, i.e., independently from the one on the others’, and (ii) its resulting
assignment is calculated for each agent in a very simple formula. We show in Theorem 1 that thisrule is characterized by the above equity axioms of PPL, ETP, and ES, together with an invarianceproperty of AC.
Because the number of priority groups are taken to be exogenous, we further analyze how manypriority groups would be appropriate for each prioritization problem. We first point out that afreely chosen and fixed number of priority groups may cause two distinct problems, unbalanced
treatment of attributes and position-wise envy of students. In response to a negative result that it
is generally diﬃcult to perfectly resolve both problems, we propose two solution concepts, called
the envy- and null-lexicographic optimum. These solutions are based on the spirit of minimizing
two kinds of negative excess in a problem, namely by lexicographic manner.
Our prioritization problem seems narrow at first, but is quite applicable to a general assignment
problem where priority is partial. The idea is to have the two stages of implementation. The firststage is to determine a complete and fair priority over agents. The second stage is to allocate real
objects (e.g., exchange programs) to agents based on their preferences and the priority constructedin the first stage. Since the second stage is a one-sided assignment problem with complete andtransitive (not necessarily linear) priority, we can achieve a strategy-proof and eﬃcient mechanism
such as serial dictatorship.
Contacted by the International Center of University X, we recommended the relative position
rule for exchange programs, which was adopted and will be implemented from 2022. In exchange
programs, the relative position rule is to “level the playing field.” When a faculty’s grading policy
is relatively harsh, the rule protects its students from being given tremendously low priorities.
Under the rule, each student only needs to care about her position within a faculty. This eﬀect
is similar to that of aﬃrmative-action-oriented quota setting in school choice (Hafalir et al., 2013)that protects minority students. However, unfortunately, we also obtain a similar result to Kojima(2012) that improvement in priority may end up with worse assigned object.

1.1

Related Literature

Indivisible goods allocation problems without monetary transfers were first studied by Shapley
and Scarf (1974). Since then, in many studies, such as those on house allocation problems (Abdulkadiroğlu and Sönmez, 1999; Kurino, 2014) and school choice problems (Abdulkadiroğlu andSönmez, 2003), exogenous priority over agents arises in natural ways. Among a few, Álvarez andMedina (2020) consider a school choice problem with students’ transferable characteristics, which
are the source of higher priority. They introduce an algorithm which determines both priority
and student-school matching simultaneously. More similarly, Greenberg et al. (2021) characterize
the cumulative oﬀer mechanism together with a priority (or more precisely a choice rule) by fiveaxioms, while we characterize a priority alone by four axioms. While our model considers partial4

priorities, in school choice literature, there are several papers in which complete but weak priority
is considered such as Erdil and Ergin (2008) and Erdil and Kumano (2019). Balbuzanov andKotowski (2019) study exchange economy in which priority may be partial, but their approach is
diﬀerent from ours; they define new concepts of cores based on property rights and characterizethem by generalized top trading cycles algorithm.
Equity concepts in assignment problems have been studied in the school choice context. Hafalir
et al. (2013) explore how to implement an aﬃrmative action policy respecting its spirit. Kojima(2012) shows impossibility results for two natural aﬃrmative action policies. Though our study
is not for aﬃrmative action objective, it is technically related with the above-mentioned papers(i.e., we wish to help students of faculties with harsh grading policy like they aim to help minority
students). However, these papers treat exogenous quota (and reserve) as primitive, while ourapproach is to find equitable quota endogenously by axioms. To our knowledge, there are a few
papers in which quota is determined within models. Kamada and Kojima (2015) and Kumano
and Kurino (2022) adjust initially given quota by their proposing algorithms, so that the resulting
allocations Pareto improve. Our approach is diﬀerent from theirs in that we do not require initialquota as primitive and determine the desirable quota by axioms.
The structure of this paper is as follows. Section 2 introduces the model and three equity
axioms. Section 3 characterizes the prioritization rule. Section 4 is dedicated to two considerations
about the rule. Section 5 extends the model to general assignment problems. Section 6 concludes
the paper. All the proofs can be found in the appendix.

2

Model

We consider the problem of assigning ordered groups to agents who are partially ordered. Eachagent who initially belongs to an attribute is assigned a group. To obtain a rule that works wellin any population domain, we employ a variable population setting. We set a rule as a function of
population in the next section.
There are K (priority) groups to be assigned to agents. We abuse the notation as K ={1, . . . , K}. We assume that each group has no exogenous capacity restriction so that it can be
assigned to any number of agents.6 An agent has one attribute. Let F be a set of potential
attributes, called faculties. In the case of universities, an attribute of a student is the department
to which she belongs. We use f or g as a generic element of F. Let Sf be a set of potential agents,or students, belonging to faculty f 2 F. Each potential student belongs to only one faculty, thatis, for all f, f 0 2 F with f 6= f 0 , we have Sf \ Sf 0 = ;. Within each faculty f 2 F, its students
are ordered by a linear order ⌫f on Sf , but across distinct faculties students are not ordered. We
6

Our problem can also be interpreted as endogenous selection of capacity, or quota, for each combination of agroup and an attribute. Equity requirements determine desirable quota.

5call ⌫f a priority. Since a priority ⌫f is a linear order, there is no tie among distinct students.
Thus, s ⌫f s0 if and only if s f s0 or s = s0 . For simplicity, we assume that F and each Sf arecountable sets.
Let F ( F and Sf ( Sf be finite sets of faculties and students in faculty f . We denote by
nf the number of students in Sf , i.e., nf = |Sf |. Once Sf is fixed, we can define an absolute
position of student s 2 Sf in faculty f as a(s|Sf ) = |{s0 2 Sf | s ⌫f s0 }|. This represents therank of student s from the bottom. For example, when Sf = {s, s0 , s00 } and s f s0 f s00 , we have(a(s|Sf ), a(s0 |Sf ), a(s00 |Sf )) = (3, 2, 1). Thus we have {a(s|Sf )}s2Sf = {nf , nf 1, ..., 2, 1}. On thea(s|S )
other hand, we define a relative position of student s in Sf as nf f .
A prioritization problem, or a problem, is represented by (F, {Sf }f 2F ) where F ( F,
Sf ( Sf . For notational simplicity, we denote it by (F, {Sf }). The problem is to assign K groups
to students who are prioritized only in their own faculties. For each problem, we assume that
|F | 2 and K 2. Even though we do not include students’ preferences in primitives explicitly,
we assume that, in each problem, all students have the common linear preference in which K is
the most preferred, K 1 the second most preferred, K 2 the third most preferred, and so on.
This restriction is to focus on the preferences over priority groups, in which every agent prefers a“higher” group. As described in Section 5, this restriction is also a natural one when preferences
for real objects are heterogeneous.
An (priority) assignment at a problem (F, {Sf }) is represented by a collection {S k }k2K ofsubsets of the set of all students, [f 2F Sf , such that [k2K S k = [f 2F Sf and for all k, k 0 2 K with0
k 6= k 0 , we have S k \ S k = ;. Here the collection is composed of K groups and each student s is
assigned one group, say k 2 K, i.e., belongs to set S k . In other words, a student in S k is assigned
group k. Each S k is called the k-th worst group (in the sense of the common preferences).
Note that the k-th worst group S k may consist of students from diﬀerent faculties, and thus S k ispartitioned to {Sfk }f 2F where Sfk is the set of students in faculty f who belongs to the k-th worst
Sgroup. Thus, we have {S k }k2K = {[f 2F Sfk }k2K and Sf = k2K Sfk . We call each Sfk a subgroupof S k . Note that s 2 Sfk stands for (i) s is a student of faculty f and (ii) s is assigned the k-th
worst group.
We introduce several equity axioms for an assignment. The first one is on the equity within afaculty.
Definition 1 (Priority preservation law). An assignment {S k }k2K satisfies the priority preservation law (PPL) if for each faculty f 2 F , when a student s 2 Sf has lower priority than astudent s0 2 Sf , then the assigned group for s is not better than the one for s0 . More precisely, for0each f 2 F , for any s, s0 2 Sf with a(s|Sf )  a(s0 |Sf ), when s 2 S k and s0 2 S k , we have k  k 0 .
The priority preservation law says that the priority of two students within a faculty is transformed to the resulting assignment in the sense that for any two students in any faculty, thelower-priority student is assigned a worse group.
6

Next, we formalize an inter-attribute equity by applying the idea of equal treatment of equals
to our problem. We consider two students to be “equal” if they have the same relative positions.
Thus, our axiom requires equal students to be assigned the same group. Note that we compare
students across faculties by their relative positions.
Definition 2 (Equal treatment of equal positions). An assignment S k k2K satisfies the equal
treatment of equal positions (ETP) if, for any two faculties f, f 0 2 F , when two students areof the same relative position then these two students are assigned the same group. More precisely,a(s0 |S 0 )a(s|S )
for any f, f 0 2 F , for any s 2 Sf and any s0 2 Sf 0 , when nf f = n 0f , for some k 2 K, we havef{s, s0 } ✓ S k .
In a situation like University X’s case, we can compare students only within a faculty by using
priority. Since two students of diﬀerent faculties are not comparable, we compare them by using
the information of relative positions; we regard them “equals” if the relative positions are the same.
We note that this requirement implies anonymity of faculties in the sense of population; when two
faculties accommodate the same number of students, the assigned group for the best student in one
faculty is the same as that for the best student in another, the assigned group for the next student
in one faculty is the same as that for the next student in another, and so on. More precisely, whenf, f 0 satisfy nf = nf 0 , it requires that for each i = 1, 2, ..., nf , a(s|Sf ) = a(s0 |Sf 0 ) = i implies forsome k(i), {s, s0 } ✓ S k(i) .
The following is the last requirement regarding the equity in diﬀerent relative position levels.
Definition 3 (Equal split). An assignment S k k2K satisfies the equal split (ES) if, for eachfaculty f 2 F , when K divides the number of students nf , then all of the assigned group in
faculty f have the same number of students. More precisely, when some number m 2 N satisfies
an equation nf = mK for some f 2 F , then, for each k 2 K, we have |Sfk | = m.
The equal split is a requirement which regards equity in positions in a faculty. Let us consider
the case in which each student can improve her priority within a faculty by eﬀort investment. If thegroup size diﬀers tremendously, one student (in the bottom of a small group) may easily improve
her priority while another student (in the bottom of a large group) may not. For example, when
we divide 100 students to 30:5:5:60, a student at #68 (from the bottom) may easily improve his
assigned group while a student at #38 may not. When ES binds, we can see that the inequality
in this sense is partially eased.
Example 1. List of faculties, population, and the number of groups are F = {A, B}, (nA , nB ) =(6, 8), and K = 3.
The priority preservation law excludes the case in which student s 2 SA with a(s|SA ) = 2(lower position) is assigned a group S 2 but student s0 2 SA with a(s0 |SA ) = 3 (higher position) is
assigned a group S 1 .
7

Figure 2: Relation of three axioms.
Since students s 2 SA with a(s|SA ) = 3 and s0 2 SB with a(s0 |SB ) = 4 obtain the same0A)B)
relative positions a(s|S= a(sn|S= 0.5, the equal treatment of equal positions requires them tonA
Bbe assigned the same group. Similarly, students s00 2 SA with a(s00 |SA ) = 6 and s000 2 SB witha(s000 |SB ) = 8 (top students in faculties) are required to be assigned the same group.
Since the number of students in faculty A is divided by the number of groups K = 3, the equal
split requires that the number of faculty A’s students who are assigned the same group is exactly
two for each of k = 1, 2, 3.7

3Prioritization Rules

Next, we formulate assignment rules in our context. A prioritization rule is a function 'that associates a priority assignment '(F, {Sf }) = {S k }k2K to each problem (F, {Sf }). For eachproblem (F, {Sf }), we denote by 'kg (F, {Sf }) the set of students in faculty g for group k underrule ', i.e., if '(F, {Sf }) = {S k }k2K , for each g 2 F , 'kg (F, {Sf }) = Sgk . Moreover, we denote by's (F, {Sf }) the assigned group of student s under rule '. We say that a prioritization rule satisfies
the priority preservation law, the equal treatment of equal positions, or the equal split when its
resulting assignment satisfies it for any problems.
We now introduce a condition for rules that requires no externality from other attributes.
Definition 4 (Irrelevance of other attributes). A prioritization rule ' satisfies the irrelevanceof other attributes (IOA) if for each faculty g 2 F , when the numbers of students of g are thesame in two population profiles {Sf }f 2F , {Ŝf }f 2F , then, for each group, the number of g’s students
7

When we require both the priority preservation law and the equal split, only one assignment is possible forfaculty A’s students (i.e., students with absolute positions of 6 and 5 are assigned the best group, those with 4 and3 are assigned the next group, and the remaining are assigned the worst group).

8are the same for these two profiles. More precisely, for each g 2 F , for each {Sf }f 2F , {Ŝf }f 2F ,when ng = n̂g , for each k 2 K, we have |'kg (F, {Sf })| = |'kg (F, {Ŝf })|.
The irrelevance of other attributes requires that increase or decrease in population of a faculty
should not aﬀect the assignment of other faculties. For an agent, even if reassignment due to her
own attribute’s population change may be understandable, that due to other attribute’s population
change may not. The irrelevance of other attributes protects agents from irrelevant changes of
population.
Since the irrelevance of other attributes seems quite restrictive in some situation, we compare
it with several invariance properties. To this end, we adapt the standard axioms of populationmonotonicity, consistency, and converse consistency in our prioritization problem. See Thomson(2011) for these axioms in various models. For the population-monotonicity, we consider thefollowing definition.
Population-monotonicity. A prioritization rule ' is population-monotonic (PM) if, when astudent is added in the worst position, assignments for existing students are never worse oﬀ. Moreprecisely, for each problem (F, {Sf }) , for each faculty g 2 F , for each Sg0 = Sg [ {s0 } such thata(s0 |Sg0 ) = 1, we have, for each s 2 [f 2F Sf , 's (F, {Sg0 } [ {Sf }f 2F \{g} ) 's (F, {Sf }).
When a student is added in an arbitrary position other than the worst, e.g., in the middle, its
eﬀect on other students may not be in one direction; students at better positions than the added
student may be better oﬀ but the remaining ones may be worse oﬀ. Therefore, in the definition
above, we only consider the cases where the eﬀect is obviously in one direction. For the next two
axioms, we need the concept of reduced problems. For each problem (F, {Sf }), for each subset of
faculties G ⇢ F , we call (G, {Sg }g2G ) a reduced problem of (F, {Sf }).8
Attribute-wise consistency. A prioritization rule ' is attribute-wise consistent (AC) if, foreach reduced problem, each student is assigned the same group as the one assigned in the original
problem. More precisely, for each problem (F, {Sf }) with |F |3, for each subset of faculties
G ⇢ F with |G| 2, we have, for each student s 2 [g2G Sg , 's (G, {Sg }g2G ) = 's (F, {Sf }f 2F ).
Attribute-wise converse consistency. A prioritization rule ' is attribute-wise conversely
consistent (ACC) if, for each problem, each student is assigned the same group as the one
assigned in reduced problems. More precisely, for each problem (F, {Sf }) with |F | 2, when foreach subset of faculties G ⇢ F with |G| = 2, '(G, {Sg }g2G ) = {[g2G Sgk }k2K , we have '(F, {Sf }) ={[f 2F Sfk }k2K .
The attribute-wise consistency requires that, when students of some faculties leave with theirassigned groups, it does not aﬀect the remaining students’ assigned groups. The attribute-wise
converse consistency is namely its converse. We only consider reduced problems where all students
8

We note that this definition is a bit restrictive when compared to those in literature. Only the cases where awhole students of a faculty leave are considered as reduced problems here.

9

of a faculty simultaneously leave because, when an arbitrary subset of students leaves, requiring
no eﬀect on remaining students seems too much restrictive. For instance, consider that a faculty’s
students except its bottom one “s” leave. It is not obvious that we should keep s in the worst
group, i.e., allowing him to be reassigned a better group may be reasonable.
The relations between the irrelevance of other attributes and above invariance properties are
as follows.
Lemma 1. Suppose that a prioritization rule ' satisfies the priority preservation law, the equal
treatment of equal positions, and the equal split.
(i) A rule ' satisfies the irrelevance of other attributes if and only if it is attribute-wise consistent.
(ii) A rule ' is attribute-wise conversely consistent if it satisfies the irrelevance of other attributes.
However, ' may not satisfy the irrelevance of other attributes if it is attribute-wise conversely
consistent.
(iii) A rule ' is population-monotonic if it satisfies the irrelevance of other attributes. However,' may not satisfy the irrelevance of other attributes if it is population-monotonic.
The next rule is of our main interest. For each x 2 R, let [x] 2 Z be the largest integer that
does not exceed x. For instance, [3.14] = 3, [2.71828] = 2, and [3] = 3.
Definition 5 (Relative position rule). The relative position rule '⇤ is a prioritization rule suchthat for each problem (F, {Sf }), for each student s 2 [f 2F Sf , her assigned group '⇤s (F, {Sf })satisfies
nf {'⇤s (F, {Sf }) 1}
nf '⇤s (F, {Sf })< a(s|Sf ) .
KKThe above formula determines a unique assigned group '⇤s (F, {Sf }) = k 2 K for each student
s 2 [f 2F Sf , i.e., if some k 2 K satisfies both inequality for a student, any other k 0 2 K do
not satisfy them. When K divides nf , all groups accommodate the same number of students
nfrom this faculty (|'kf (F, {Sf })|= Kf 2 N for each k 2 K). This is clearly what the equal split
requires. In other cases, the relative position rule results in “approximately” equal group sizes (i.e.,nn|'kf (F, {Sf })| 2 ( Kf 1, Kf + 1) for each k 2 K).
Example 2. List of faculties, population, and the number of groups are F = {A, S}, (nA , nS ) =(5, 8), and K = 5. For student s 2 SA with a(s|SA ) = 3, the relative position rule assigns hergroup S 3 since a(s|SA ) = 3 = [ nAK⇥3 ]. On the other hand, for student s0 2 SS with a(s0 |SS ) = 5,
the relative position rule assigns him group S 4 since [ nSK⇥3 ](= 4.8) < a(s|SS ) = 5  [ nSK⇥4 ](= 6.4).
Using Lemma 2 below, we can see this rule actually meets the requirements of all other axioms
above (Proposition 1).
10Figure 3: The assignment by '⇤ in Example 2.
Lemma 2. Suppose that an assignment {S k }k2K is generated by the relative position rule. Then,for each s 2 Sf , s 2 S k if and only if
k

1
K

<

a(s|Sf )
k
 .
nf
K

Proposition 1. The relative position rule satisfies (i) the priority preservation law, (ii) the equal
treatment of equal positions, (iii) the equal split, (iv) the irrelevance of other attributes, (v) the
attribute-wise consistency, (vi) the attribute-wise converse consistency, and (vii) the populationmonotonicity.
Moreover, as in Theorem 1 below, we can characterize the relative position rule '⇤ by the
combination of four axioms.
Theorem 1. A prioritization rule satisfies (i) the priority preservation law, (ii) the equal treatmentof equal positions, (iii) the equal split, and (iv) the attribute-wise consistency if and only if it is
the relative position rule.
We note that, by Lemma 1, the relative position rule is also characterized by the combinationof (i)-(iii) above and (iv’) the irrelevance of other attributes. Though the relative position rulesatisfies the attribute-wise converse consistency and the population-monotonicity, because they do
not imply the irrelevance of other attributes, we cannot characterize the rule by the combinationof (i)-(iii) and (iv”) the attribute-wise converse consistency or (iv” ’) the population-monotonicity.
The logical independence of four axioms is shown in the following examples.
Example 3. Consider the “reversed” version of the relative position rule '1 such that
'1s (F, {Sf }) = (K + 1)
violates PPL.

'⇤s (F, {Sf }). We can verify that this rule satisfies ETP, ES, and AC, but⌃

Example 4. Consider the “faculty-dependent” rule '2 such that, for each s 2 [f 2F Sf ,11

Assignment by '⇤Assignment by '1

Assignment by '2

Assignment by '3

Assignment by '4

Figure 4: The assignment by each rule in Example 7.
8<'⇤ (F, {S }) [ nf 2 N]
fsK2's (F, {Sf }) =:h(s)otherwise

where h(s) = h(s0 ) if and only if for some f 2 F , {s, s0 } ✓ Sf . We can verify that this rule satisfies
PPL, ES, and AC, but violates ETP.
⌃
Example 5. The “constant” rule '3 such that '3s (F, {Sf }) = 1 satisfies PPL, ETP, and AC, butviolates ES.
⌃
Example 6. Consider the “domain-conditional” rule '4 such that8a(s0 |S 0 )a(s00 |S 00 )>>'⇤s (F, {Sf })[9s0 2 Sf 0 , s00 2 Sf 00 s.t. n 0f = n 00f 6= 1]
>
f
f
<
nf 0
0
'4s (F, {Sf }) =_[9f 2 F s.t. K 2 N]>>>:min{K, a(s|S )} otherwise.
f

We can verify that this rule satisfies PPL, ETP, and ES, but violates AC.

⌃

Example 7. List of faculties, population, and the number of groups are F = {A, S}, (nA , nS ) =(3, 5), (n0A , n0S ) = (2, 5), and K = 2. The relative position rule '⇤ and other rules '1 , '2 , '3 , '4
above assign students as in figure 4.

124Discussion

4.1

Student-Optimal Group Number

Until now we have taken the number of groups, K, as exogenously given, and then discussed thedesirability of the relative position rule. In this section, we discuss how to choose K endogenously.
To see points inherent in this problem, let us consider the following example.
Example 8 (Queuing problem9 ). There are one facility (an amusement park or a museum) andtwo types of students (customers), eight with normal tickets (type N ) and four with special tickets(type S, old, handicapped, invitee etc). To avoid crowds, this facility divides students to K priority
groups {S k }k2K (students in S k 1 can enter several minutes/hours after those in S k ). Within types
N and S, students are ordered as queues s8N N ... N s1N and s4S S ... S s1S on a first-comefirst-served basis. When the facility owner uses the relative position rule to treat two types fairly
based on the relative positions in queues, the problem that the owner faces is the selection of
the number of priority groups K. Consider the following two cases and the results of the relative
position rule (See Figure 5.).
Case 1: When K = 2, the rule gives S 2 = {s8N , s7N , s6N , s5N , s4S , s3S } and S 1 = {s4N , s3N , s2N , s1N , s2S , s1S }.
k/2
Case2: When K = 8, the rule gives S k = {skN } for odd k’s; S k = {skN , sS } for even k’s.
⌃
In this example, the parameter K is not primitive, but is actually a design variable. This leads
to the questions: (i) if there exists the optimal K (in some sense), and (ii) how we can find it (ifexists). From this point on, we will search for answers maintaining the following assumption.
Assumption 1 (Preference domain). Each student prefers (i) to be assigned a higher priority
group, and (ii) less number of students for her own assigned group.
The first assumption is the same as that of previous sections. The second one, a negative
externality of students, is not obvious but is plausible when customers hate crowds, and/or objects
are scarce.
Back to Case 1 (K = 2) in Example 4. In type N , s4N is assigned to the lower group S 1 , while
her upper-priority neighbor, or immediate predecessor at ⌫N , s5N is assigned to the higher group
S 2 . The diﬀerence in their relative positions is 5 8 4 = 0.125. In type S, s1S is assigned to S 1 , thesame group as the neighbor s2S , while the diﬀerence in their relative positions is 2 4 1 = 0.25. Hence,
there is a gap in treatments of s4N and s1S : Even though the former is closer to his upper-priority
neighbor than the latter to her neighbor, only the latter is successfully assigned the same group as
his neighbor. We can view that, when K=2, s4N “envies” s1S in the sense of position diﬀerences. In
9This example is diﬀerent from generally considered queuing problems (e.g., Maniquet (2003)) in that (i) morethan two agents can be served simultaneously, and (ii) no monetary compensations are allowed. Bloch (2017)considers a queuing model without monetary transfers but he applies a stochastic assignment rule.

13

K=2

K=8

Figure 5: Two problems in Example 8.
this case, there is also a gap in treatment of s5N and s2S ; The former is closer to his lower-priority
neighbor, or immediate successor at ⌫N , than the latter to her neighbor while only the latter isassigned the same group as the neighbor. We can also view that when K=2, s2S “envies” s5N in thesense of position diﬀerences. We note that s4N ’s envy is by (i) of Assumption 1, while s2S ’s is by(ii) of Assumption 1.
In Case 2, no students envy others but another problem occurs. In type S, no students are
assigned to four out of eight priority groups, i.e., SS1 ,SS3 ,SS5 ,SS7 are all null. We can see that siS is in
2i 1
the same group as s2i
N , strictly higher group than sN ’s. The result that seems slightly preferable
to type S occurs because we permit each subgroup to be null, i.e., to be assigned to no students.
In this case, among K ⇥ |F | = 8 ⇥ 2 = 16 subgroups, SS1 ,SS3 ,SS5 ,SS7 are null.
The above discussion shows that our next goal is to eliminate envious students and null subgroups. We can see that neither of them exist only when K = 4. Therefore, we view K = 4 as the
optimum in this example.
Definition 6 (Position-wise envy). Consider a problem (F, {Sf }) and an assignment {S k } with afixed K.
1. A student s has a lower-side envy at an assignment {S k } if she is assigned the strictly worsegroup than her upper-priority neighbor and some student has an upper-priority neighbor in
the same priority group as his, even though the diﬀerence between his relative position andhis neighbor’s is strictly larger than that of s and her neighbor’s. That is, for s 2 Sfk ,a 1 (a(s|Sf ) + 1|Sf ) 2/ Sfk ; and for some f 0 2 F \{f } with nf 0 < nf , for some k 0 2 K, there is00
s0 2 Sfk0 such that a 1 (a(s0 |Sf 0 ) + 1|Sf 0 ) 2 Sfk0 .
2. A student s has an upper-side envy at an assignment {S k } if she is assigned the samegroup as her lower-priority neighbor and some student has a lower-priority neighbor in thestrictly worse priority group than his, even though the diﬀerence between his relative positionand his neighbor’s is strictly smaller than that of s and her neighbor’s. That is, for s 2 Sfk ,a 1 (a(s|Sf ) 1|Sf ) 2 Sfk ; and for some f 0 2 F \{f } with nf 0 > nf , for some k 0 2 K, there is00
s0 2 Sfk0 such that a 1 (a(s0 |Sf 0 ) 1|Sf 0 ) 2/ Sfk0 .
14

3. A student s is position-wise envious at an assignment {S k } when she has either lower-side
or upper-side envy.
In reality, the numbers of students (purchasing tickets or applying to the exchange programs)
arise in a random manner. Thus, in most cases, we can expect that two distinct faculties havediﬀerent numbers of students (nf 6= nf 0 if f 6= f 0 ) and each faculty has at least two students. We
call such a case the regular case. Unfortunately, the next proposition shows negative results. We
omit the proof because it is almost straightforward from Definition 6.10
Proposition 2. In the regular case, given the relative position rule, the following hold.
(i) No students are position-wise envious if and only if K is not less than the second largest numberin {nf }f 2F .
(ii) No subgroups are null if and only if K is not greater than the smallest number in {nf }f 2F .
(iii) When |F | 3, there are no K’s in which both envious students and null subgroups never exist.
Therefore, we next search for the “second-best” solution concepts. For each problem (F, {Sf }),given the relative position rule '⇤ , we introduce two definitions of optimal K’s as follows. The
formulation is based on the nucleolus of cooperative games, that is similar to our solution in thespirit of minimizing (a kind of) negative excess in a model.11
Definition 7 (Lexicographic optima). For each problem (F, {Sf }) and each prioritization rule', denote the number of students with lower-side envy plus those with upper-side envy under Kby ✓e (K|F, {Sf }, ').12 In the same manner, denote the number of null subgroups under K by✓; (K|F, {Sf }, '). That is,✓e (K|F, {Sf }, ') := | [f 2F {s 2 Sf | s is lower-side envious at (F, {Sf }, K, ')}|+| [f 2F {s 2 Sf | s is upper-side envious at (F, {Sf }, K, ')}|,;✓ (K|F, {Sf }, ') := | [f 2F {Sfk ✓ Sf | Sfk = ; at (|F, {Sf }, K, ')}|.
1. K is the envy-lexicographic optimum for (F, {Sf }, '⇤ ) if K minimizes ✓; ( · |F, {Sf }, '⇤ )among the minimizers of ✓e ( · |F, {Sf }, '⇤ ). That is, we have(a) for each K 0

102, ✓e (K|F, {Sf }, '⇤ )  ✓e (K 0 |F, {Sf }, '⇤ ), and(b) for each K 0
2 with ✓e (K|F, {Sf }, '⇤ ) = ✓e (K 0 |F, {Sf }, '⇤ ), ✓; (K|F, {Sf }, '⇤ ) ✓; (K 0 |F, {Sf }, '⇤ ).

We comment only about (ii). “Only if” is immediate from contrapositive. “If” is shown as follows. Supposenf kn (k 1)nf k
nf (k 1)n
nf K. Then, for each k 2 K, [ K] [ fK ] [ K] = [ Kf ] 1. Therefore, for each k 2 K, there isK
s 2 Sf such that '⇤s (F, {Sf }) = k. Statement (ii) also holds in non-regular cases.
11
For a modern definition and the nature of the nucleolus, for example, see Chapter 5 of Moulin (1991).
12
When a student has both lower-side and upper-side envies, we count them as two. Thus, ✓e (K|F, {Sf }, ') is
not always the same as the number of position-wise envious students at (F, {Sf }, K, ').

15

2. K is the null-lexicographic optimum for (F, {Sf }, '⇤ ) if K minimizes ✓e ( · |F, {Sf }, '⇤ )among the minimizers of ✓; ( · |F, {Sf }, '⇤ ). That is,(a) for each K 02, ✓; (K|F, {Sf }, '⇤ )  ✓; (K 0 |F, {Sf }, '⇤ ), and(b) for each K 0
2 with ✓; (K|F, {Sf }, '⇤ ) = ✓; (K 0 |F, {Sf }, '⇤ ), ✓e (K|F, {Sf }, '⇤ ) ✓e (K 0 |F, {Sf }, '⇤ ).
The idea of two lexicographic optima is to prioritize two policy objectives, reducing envy andnull, in a lexicographic manner. The envy (null) optimum mainly focuses on reducing the number ofenvious students (null subgroups) and supplementary reduces the other. Roughly speaking, larger(smaller) K induces more null subgroups (envious students) but it does less envious students (nullsubgroups). The next proposition helps finding these optima as well as assuring the existence.13
Proposition 3. For any problems, the following two hold.
(i) In the regular case, K = max{nf | nf < max{ng }} is the unique envy-lexicographic optimum.
f 2F

g2F

Otherwise, either max{nf | nf < max{ng }} or max{nf } is (possibly one of ) the envy-lexicographic
f 2F

g2F

f 2F

optimum.
(ii) In the regular case, K = min{nf } is the unique null-lexicographic optimum. Otherwise, either
f 2F

min{nf } or 2 is (possibly one of ) the null-lexicographic optimum.
f 2F

The following example illustrates the result of Proposition 3.
Example 9. Add faculty C (children) and students SC = {s7C , ..., s1C } to Example 8. Since nN , nS ,and nC are distinct, this is a regular case of |F | = 3. See Table 1. K = 7 is the unique envylexicographic optimum because ✓e (K) is minimized where K
7, and among them, ✓; (K) is
minimized at K = 7. K = 4 is the unique null-lexicographic optimum because ✓; (K) is minimized
where K  4, and among them, ✓e (K) is minimized at K = 4.
13

By this proposition, we can actually construct a lattice of desirable group numbers. Technically, its structure is similar to that of stable matchings in marriage markets (Adachi, 2000), yielding the men- and womenoptimal matching as maximum and minimum of the defined order. Let (F, {Sf }) be an arbitrarily regularcase. Let K ⇤ (F, {Sf }) be a set of natural number K’s satisfying min{nf }  K  max{nf | nf < max{ng }}.
f 2F

f 2F

g2F

Let ⌫K ⇤ be a relation on K ⇤ (F, {Sf }) such that, for any K, K 0 2 K ⇤ (F, {Sf }), K ⌫K ⇤ K 0 if and only if✓e (K|F, {Sf }, '⇤ )  ✓e (K 0 |F, {Sf }, '⇤ ) and ✓; (K|F, {Sf }, '⇤ ) ✓; (K 0 |F, {Sf }, '⇤ ). The pair (K ⇤ (F, {Sf }), ⌫K ⇤ )forms a lattice. Within K ⇤ (F, {Sf }), the maximal (minimal) element of ⌫K ⇤ is the best (worst) in the number of
position-wise envious students, while being the worst (best) in the number of null subgroups.

16

Table 1: a regular case of |F | = 3
upper-sidenull
envious students
subgroups
s7C , s6C , s5C , s3C , s2C , s4S , s2S
7
6
4
2
4
sC , sC , sC , sC , sS
753sC , sC , sC
s7C , s4C
SS1
s7C
SS4 , SS1
5
SS , SS3 , SS1
SC1 , SS7 , SS5 , SS3 , SS1
1
SN, SC5 , SC1 , SS8 , SS6 , SS4 , SS2 , SS1

K
2
3
4
5
6
7
8
9

lower-side
envious students
s4N , s3C
s5N , s2N , s4C , s2C
s6N , s4N , s2N
6sN , s4N , s3N , s1N
s6N , s5N , s4N , s2N , s1N-

4.2

Modeling Options✓e (K)
9
9
6
6
6
0
0
0

✓; (K)
0
0
0
1
2
3
5
8

In the analysis in the previous sections, the concept of students’ absolute and relative positions
played a key role. We refer them to define an axiom of the equal treatment of equal positions andthe relative position rule that implements the axioms.
Recall that the absolute position is defined as the rank of each student from the bottom withina faculty. So, one question here is: if we modify the definition to “the rank of each student fromthe top,” does the relative position rule still meet the equal treatment of equal “modified” (relative)
positions? In other words, when two students are of the same relative position from the top, arethese two students assigned the same group? This question arises because there are many ways ofdefining absolute positions.14 Unfortunately, we obtain a negative result for this question.
To see the result, we first define the inverse absolute position, each student’s rank in her facultyfrom the top. For each problem (F, {Sf }), for each student s 2 [f 2F Sf , the inverse absolute
position is given by ainv (s|Sf ) := |{s0 2 Sf | s0 ⌫f s}|. For example, when Sf = {s, s0 , s00 } ands f s0 f s00 , we have (ainv (s|Sf ), ainv (s0 |Sf ), ainv (s00 |Sf )) = (1, 2, 3). We observe the relation foreach student s 2 [f 2F Sf , ainv (s|Sf ) = nf + 1 a(s|Sf ). Similarly, we define an inverse relative
ainv (s|Sf )position of student s in Sf as. Then, we consider the following example.
nf
Example 10. List of faculties, population, and the number of groups are F = {A, S}, (nA , nS ) =(3, 6), and K = 2. In figure 7, sif is the student of an absolute position a(sif |Sf ) = i. The
assignment of the left image, (S 2 , S 1 ), is given by the relative position rule. Since the rule satisfies
the equal treatment of equal positions, each pair of equal relative position students, (s3A , s6S ) ata(s3A |SA )a(s6S |SS )a(s2A |SA )a(s4S |SS )a(s1A |SA )
3
6
2
4
2
4
1
2
=
=
=
,
(s
,
s
)
at
=
=
=
,
or
(s
,
s
)
at
= 13 =
A
S
A
S
nA
3
6
nS
nA
3
6
nS
nA
2

a(s |S )2= nSS S , is assigned the same group ({s3A , s6S } ⇢ S 2 , {s2A , s4S } ⇢ S 2 , or {s1A , s2S } ⇢ S 1 ).
6
14

Other than the original and this subsection’s formulations, the following definition may also be natural. For
each problem (F, {Sf }), for each student s 2 [f 2F Sf , let â(s|Sf ) := |{s0 2 Sf | s f s0 }| = a(s|Sf ) 1. WhenSf = {s, s0 , s00 } and s f s0 f s00 , we have (â(s|Sf ), â(s0 |Sf ), â(s00 |Sf )) = (2, 1, 0). This is also the rank of a
student from the bottom but the bottom student’s absolute position is normalized to be zero.

17

Figure 6: Two diﬀerent assignments in Example 10.
Each sif is of an inverse absolute position ainv (s|Sf ) = nf + 1

i, i.e.,(ainv (s3A |SA ), ainv (s2A |SA ), ainv (s1A |SA )) = (1, 2, 3), and(ainv (s6S |SS ), ainv (s5S |SS ), ainv (s4S |SS ), ainv (s3S |SS ), ainv (s2S |SS ), ainv (s1S |SS )) = (1, 2, 3, 4, 5, 6).
For inverse relative positions, pairs (s3A , s5S ), (s2A , s3S ), and (s1A , s1S ) are of the same inverse
ainv (s3A |SA )ainv (s5S |SS ) ainv (s2A |SA )ainv (s3S |SS )= 13 = 26 =,= 23 = 46 =,andrelative positions because
nA
nS
nA
nS
ainv (s1A |SA )ainv (s1S |SS )= 33 = 66 =.
nAnS

We notice that pairs of the same inverse relative positions diﬀer
from those of the same relative positions (e.g., s3A is of the same relative position as s6S , but is of
the same inverse relative position as s5S ). Then, a pair (s2A , s3S ) is not assigned the same group(s2A 2 S 2 but s3S 2 S 1 ).
In figure 7, in the assignment of the right image (S 02 , S 01 ), each pair of equal inverse relative
position students is assigned the same group, e.g., (s2A , s3S ) ⇢ S 01 . However, a pair (s2A , s4S ) is of
the same relative position but is not assigned the same group (s2A 2 S 01 but s4S 2 S 02 ).
⌃Formally, we state the inverse version of the equal treatment of equal positions as follows.1516
As is shown in Example 9, the relative position rule does not satisfy this requirement.
Equal treatment of equal inverse positions. An assignment S k k2K satisfies the equal
treatment of equal inverse positions (ETIP) if, for any two faculties f, f 0 2 F , when two
students are of the same inverse relative position then these two students are assigned the same
ainv (s|Sf )group. More precisely, for any f, f 0 2 F , for any s 2 Sf and any s0 2 Sf 0 , when=nfainv (s0 |Sf 0 ), for some k 2 K, we have {s, s0 } ✓ S k .
nf 0

The following rule, the inverse version of the relative position rule, satisfies the equal treatmentof equal inverse positions above. The assignment (S 02 , S 01 ) in Example 9 is given by this rule.
15

The priority preservation law, also depending on the formulation of absolute positions, is rewrite as follows:0for each f 2 F , for any s, s0 2 Sf with ainv (s|Sf )ainv (s0 |Sf ), when s 2 S k and s0 2 S k , we have k  k 0 .
This is completely the same requirement as the original definition because ainv (s|Sf ) ainv (s0 |Sf ) is equivalent toa(s|Sf )  a(s0 |Sf ).
16
Using an alternatively formulated absolute position on a footnote above, we can change the statement as follows:â(s0 |S 0 )â(s|S )for any f, f 0 2 F , for any s 2 Sf and any s0 2 Sf 0 , when nf f = n 0 f , for some k 2 K, we have {s, s0 } ✓ S k .
fis equivalent to 1â(s|Sf )=1
nf0

â(s |S 0 )â(s|Sf )= n 0fnf
fâ(s0 |Sf 0 )nf 0 +1 a(s0 |Sf 0 )ainv (s0 |Sf 0 )nf +1 a(s|Sf )ainv (s|Sf ), or=, which means
=
.
nf 0
nf
nf 0
nf
nf 0

This requirement is completely the same as the equal treatment of equal inverse positions because

18Thus, this rule does not satisfy the equal treatment of equal positions.
Inverse relative position rule. For each k 2 K, let ⇡(k) = K + 1 k. The inverse relative
position rule '⇤inv is a prioritization rule such that for each problem (F, {Sf }), for each student
s 2 [f 2F Sf , her assigned group '⇤inv(F, {Sf }) satisfiess

nf {⇡('⇤inv(F, {Sf }))
s
K

1}

inv

<a

(s|Sf ) 

nf ⇡('⇤inv(F, {Sf }))s.
KThis rule is characterized by the equal treatment of equal inverse positions with other threeaxioms (Proposition 4. (c)). This result is obtained by renaming positions in Theorem 1 in astraightforward way. We omit the complete proof for the following proposition because (a) is by
Proposition 1 and Example 9, (b) is by the above argument and Example 9, (c) is by the above
argument, and (d) is by Theorem 1 and (c).
Proposition 4. (a) The relative position rule satisfies the equal treatment of equal positions but
it may not satisfy the equal treatment of equal inverse positions.
(b) The inverse relative position rule satisfies the equal treatment of equal inverse positions but it
may not satisfy the equal treatment of equal positions.
(c) A prioritization rule satisfies (i) the priority preservation law, (ii’) the equal treatment of equal
inverse positions, (iii) the equal split, and (iv) the attribute-wise consistency if and only if it is theinverse relative position rule.
(d) There are no prioritization rules that satisfy (i) the priority preservation law, (ii) the equal
treatment of equal positions, (ii’) the equal treatment of equal inverse positions, (iii) the equal split,and (iv) the attribute-wise consistency.
Thus, when we require the axioms of (i), (iii), and (iv) above, there are at least two reasonableprioritization rules: the relative and the inverse relative position rules. The judgment of which
rule to implement depends on which axiom out of (ii) equal treatment of equal positions and (ii’)
equal treatment of equal inverse positions, we wish to emphasize.
Finally, we additionally note the following conditions that are actually incompatible if we choose
the relative or the inverse relative position rule.
Definition 8 (Top/Bottom-agent invariance). (i) A prioritization rule ' is top-agent invariant
if each student who is top-ranked within her faculty is always assigned the best group. That is,for each (F, {Sf }), for each g 2 F , for each s 2 Sg such that a(s|Sg ) = ng , 's (F, {Sf }) = K.
(ii) A prioritization rule ' is bottom-agent invariant if each student who is bottom-ranked
within her faculty is always assigned the worst group. That is, for each (F, {Sf }), for each g 2 F ,for each s 2 Sg such that a(s|Sg ) = 1, 's (F, {Sf }) = 1.
19

As the following proposition shows it, the relative position rule satisfies only the former while
the inverse relative position rule does only the latter. We omit the straightforward proof.17 In
reality, University X adopts the relative position rule, instead of the inverse relative position rule,considering the top-agent invariance being a desirable feature of a prioritization rule.
Proposition 5. (i) The relative position rule is top-agent invariant but is not bottom-agent invariant.
(ii) The inverse relative position rule is bottom-agent invariant but is not top-agent invariant.

5

Extension: Priority Design for General Assignment Problems

In the example of University X, our prioritization problem is followed by an assignment problem
of exchange programs, real indivisible objects. In this section, we apply the argument of previous
sections to a general assignment problem where priority is partial. The idea is to have the two stagesof implementation which are in line with University X’s practice. In the first stage, we determine
a complete, transitive, and fair priority. We apply the relative position rule to achieve equity
requirements such as the equal treatment of equal positions. Hence, this stage is a prioritization
problem of previous sections. The second stage consists of allocating real objects (e.g., exchange
programs) to agents. Allocation is determined based on agents’ preferences and the priority formedin the first stage, i.e., this is an assignment problem of indivisible objects with single priority.
Because the priority is complete and transitive but is weak, i.e., students in the same priority
group are of the same priority, a tie-breaking rule is required to allocate objects. A tie-breaking
rule is a rule that transforms each weak priority into a linear priority that is consistent with the
weak priority. In this paper, we assume an exogenous rule following a common formulation in theliterature (e.g., Abdulkadiroğlu et al., 2009).18
Assumption 2 (Tie-breaking rule). For each prioritization problem (F, {Sf }), there is a linear
order ⌫0 (F, {Sf }) in the set of all students [f 2F Sf that agrees with each priority within a faculty⌫f |Sf , i.e., for each f 2 F , ⌫0 (F, {Sf })|Sf =⌫f |Sf .
17

The part (i) is shown as follows. For s 2 Sg such that a(s|Sg ) = ng , since a(s|Sg ) =

h

ng K
K

i

, '⇤s (F, {Sf }) = K
h
i
ng ⇥2
by the definition of '⇤ . When (ng , K) = (2, 4), for s0 2 Sg such that a(s0 |Sg ) = 1, since a(s0 |Sg ) =
,
K

00
00
'⇤s0 (F, {Sf }) = 2(> 1).
h The
i part (ii) can be shown in the same manner. For s 2 Sg such that a(s |Sg ) = 1, since
ng K
K

⇤inv
, and K = ⇡(1), '⇤inv. When (ng , K) = (2, 4),s00 (F, {Sf }) = 1 by the definition of 'hin ⇥2
for s000 2 Sg such that a(s000 |Sg ) = ng , since ainv (s000 |Sg ) = 1 = gK , and 2 = ⇡(3), '⇤inv
1).
s000 (F, {Sf }) = 3(= K18
One practical interpretation of this rule is the descending order of GPA or a lottery result.

ainv (s00 |Sg ) = ng =20

Figure 7: The approach to exchange program allocation.
Our objective is, where the tie-breaking rule is not necessarily fair, to observe the eﬀect of
having the first stage above. Thus, we do not require any assumptions or axioms for the tiebreaking rule other than above. When we fix a problem, we refer a tie-breaking rule as ⌫0 .
The following example, based on the practice at University X, illustrates this idea.
Example 11 (Two-stage implementation). Consider a university composed of two faculties, schoolsof arts (A) and sciences (S). This university provides students six diﬀerent exchange programs{a, b, c, d, e, f }, while each student can take part in at most one program, and each program accommodates at most one student. Let the number of students be six for faculty A and four forfaculty S. Assume that students are initially ordered within each faculty as s6A A ... A s1A ands4S S ... S s1S .
Stage 1: Prioritization problem. We apply a prioritization rule to combine the priorities
above to a complete one, so that an assignment rule can be applied on the subsequent stage. The
university chooses the relative position rule with K = 4 (envy- and null-lexicographic optimum).
Then, we obtain a priority assignment(S 4 , S 3 , S 2 , S 1 ) = ({s6A , s5A , s4S }, {s4A , s3S }, {s3A , s2A , s2S }, {s1A , s1S }).
Stage 2: Assignment problem. We apply an assignment rule to allocate exchange programs
to students. We apply the following exogenous tie-breaker, which is consistent with ⌫A and ⌫S
but is seemingly preferable for faculty A’s students⌫0 : s6A , s5A , s4A , s3A , s4S , s2A , s3S , s2S , s1A , s1S .
We apply the tie-breaking rule to (S 4 , S 3 , S 2 , S 1 ) (i.e., first, for S 4 , three students are ordered by⌫0 as s6A , s5A , s4S , next, for S 3 , two students are ordered by ⌫0 as s4A , s3S , and so on) and obtain⌫⇤ : s6A , s5A , s4S , s4A , s3S , s3A , s2A , s2S , s1A , s1S .
As the assignment rule, the university chooses the serial dictatorship rule induced by ⌫⇤ . It
21

proceeds in the order of ⌫⇤ , as s6A takes her best program (e.g., d) first, s5A takes his best among
the remaining (e.g., a), and so on.
⌃
We first observe the eﬀect of having Stage 1, i.e., the eﬀect of the relative position rule, tothe resulting linear priority ⌫⇤ under an exogenous tie-breaking rule ⌫0 . When Stage 1 is not
implemented, the priority the university can use is ⌫0 itself. Thus, the eﬀect of Stage 1 is thediﬀerence between ⌫0 and ⌫⇤ . We observe that, from ⌫0 to ⌫⇤ ,(i) Average rank (from the bottom) of A’s students changes from 41/6=(10+9+8+7+5+2)/6 to
37/6=(10+9+7+5+4+2)/6,(ii) Average rank of S’s students changes from 14/4=(6+4+3+1)/4 to 18/4=(8+6+3+1)/4,(iii) The diﬀerence of average ranks in faculties reduced from 10/3 to 5/3, and(iv) Each A’s student is weakly worse oﬀ in her rank, while each S’s student is weakly better oﬀ.
This example indicates that the relative position rule partially decreases the feature of ⌫0 ,even if ⌫0 is used to tie-breaking within each group. Thus, the rule is beneficial for students offaculties like S. Especially when the feature of ⌫0 is not desirable, the rule helps “leveling theplaying field.” 19 It means that initially disadvantaged students can improve their ranks.
We next state a proposition that formalizes the intuition from the example. Let ⌫0 be an
arbitrary tie-breaking rule. Let ⌫⇤ , or more precisely ⌫⇤ (F, {Sf }, K, ⌫0 ), be a linear order in[f 2F Sf with application of the relative position rule '⇤ , such that for any distinct students s, s0 2
[f 2F Sf , s ⌫⇤ s0 if and only if (i) '⇤s (F, {Sf }) > '⇤s0 (F, {Sf }) or (ii) '⇤s (F, {Sf }) = '⇤s0 (F, {Sf })and s ⌫0 s0 . We denote each student s’s absolute positions in all students by a0 (s|{Sf }) := |{s0 2[f 2F Sf | s ⌫0 s0 }| (in ⌫0 ) or a⇤ (s|{Sf }) := |{s0 2 [f 2F Sf | s ⌫⇤ s0 }| (in ⌫⇤ ) respectively.
a (s|{Sf })f 2F nf0
Proposition 6. (i) |F | = 2. If a student s 2 [f 2F Sf obtains a relative position Pin ⌫0a(s|Sf ), his absolute position weakly improves by the use ofnflower than the one in his own faculty
the relative position rule '⇤ . That is, for each (F, {Sf }) with |F | = 2, for each s 2 [f 2F Sf such
a0 (s|{Sf })a(s|S )
that P< nf f , a⇤ (s|{Sf }) a0 (s|{Sf }).
nf
f 2F(ii) |F |a(s|Sf )nf

2. If a student s 2 [f 2F Sf obtains a relative position

a0 (s|{Sf })P
f 2F nfin ⌫0 lower than

{ K1 + P |F | nf }, his absolute position strictly improves by the use of the relative position
f 2F

a (s|{S })0frule. That is, for each (F, {Sf }), for each s 2 [f 2F Sf such that P<
f 2F nf⇤a (s|{Sf }) > a0 (s|{Sf }).

a(s|Sf )nf{ K1 + P |F | nf },f 2FThis proposition says that, when |F | = 2, a student who is more disadvantaged in all faculties
than in his own faculty, measured by the relative positions, improves his absolute position in all
19

The phrase “leveling the playing field” here has a slightly diﬀerent meaning than that in a well-known study(Pathak and Sönmez, 2008). While they help strategically naive households by introducing the deferred acceptancemechanism, we help students of faculties with harsh grading policies using the relative position rule. If we apply
the rule to student prioritization for school choice problems, it is understood as a kind of aﬃrmative action policy
to balance the treatment of students with diﬀerent backgrounds.

22

faculties by the use of the relative position rule. However, when |F | 3, since such students may
exist in several faculties, not all these students but those who are suﬃciently disadvantaged can
improve their absolute positions in all faculties.
Next, we move on to the assignment of real objects.20 In contrast to above, the result is not
so optimistic. Let H be a finite set of real objects (e.g., exchange programs in Example 10) and“self-match” {;}. We denote by h a generic element of H. We assume that each real object can be
assigned to at most one student, and each student prefers at most one object. Self-match yields nocapacity restrictions. Let %s be a preference of student s 2 [f 2F Sf on H. We assume each %s islinear, i.e., for any a, b 2 H, a %s b and b %s a if and only if a = b. An assignment {hs }s2[f 2F Sf is alist such that for each s 2 [f 2F Sf , hs 2 H, and for each h 2 H\{;}, |{s 2 [f 2F Sf | hs = h}|  1.
An assignment rule is a function that associates with each preference profile %= {%s }s2[f 2F Sfan assignment (%) = {hs }s2[f 2F Sf . We denote assigned object for student s by s (%) = hs .
Among possible rules, the following one is of our interest here.
Serial dictatorship rule. The serial dictatorship (SD) rule ⌫ induced by a (linear) priority ⌫chooses the assignment so that for each student s 2 [f 2F Sf , s⌫ (%) is her most preferred object
in the set of real objects and self-match H, excluding the real objects assigned to students withhigher priority than her. More precisely, for each s 2 [f 2F Sf ,⌫s (%) = arg max

8
<
:

2

%s | h 2 4H\[

s0 :a(s0 |{Sf })>a(s|{Sf })3⌫5s0 (%) [ {;}

9
=
;

.

It is well known that the serial dictatorship rules induced by any priorities are strategy-proof
and Pareto eﬃcient (Svensson, 1994). Moreover, since serial dictatorship rule is a specific caseof student-proposing deferred acceptance rules, it respects improvements (Balinski and Sönmez,1999). It means that, if only one student improves in the priority, her assigned object is not worse
than the one before the improvement, when evaluated by her own preference. However, when
multiple students improve their positions in the priority, its eﬀect is not obvious. It means that, if
more than two students improve in the priority, some of them may obtain worse object than the
one before the improvement. Because the relative position rule adjusts several students’ positionsin the priority simultaneously, improvement in priority (from ⌫0 to ⌫⇤ ) does not always imply
improvement of assigned object. That is, the implementation of Stage 1, the relative position rule,
may hurt some initially disadvantaged students, when evaluated by their own preferences.
Proposition 7. Even if a student obtains a better position in ⌫⇤ than in ⌫0 , her assigned object
may be worse in ⌫⇤ -based serial dictatorship than in ⌫0 -based serial dictatorship, in the sense of20

We formulate the situation as a one-to-one assignment problem for notational simplicity. The same argument
can be naturally applied to many-to-one assignments.

23

her preference. More precisely, there exists (F, {Sf }) such that for some s 2 [f 2F Sf , for some %,⇤a⇤ (s|{Sf }) a0 (s|{Sf }) but s⌫0 (%) %s s⌫ (%).

6

Conclusion

In this paper, we examine a fair prioritization problem of agents, given a set of partial priorities
and a notion of agents’ relative positions. Theorem 1 shows that the relative position rule '⇤ isa unique rule that satisfies all of our requirements, which are: the priority preservation law, theequal treatment of equal positions, the equal split, and the attribute-wise consistency. In moregeneral assignment problems with partial priorities, the rule '⇤ has a feature that helps levelingthe playing field; agents of specific attributes, e.g., faculty S of Example 11, are better oﬀ.
At the end of the paper, we note on some limitations of our model and possibilities of further
development of the rule in general assignment problems.
Faculties as strategic agents. In some cases, it is natural for faculties to want their own
students to benefit more - this is actually the case for University X. In this situation, faculties
may try to strategically manipulate the resulted priority assignment. For instance, if each priority
is private information held by each faculty, and the university collects the information to form acomplete priority, faculties may have incentive to misreport the information. Suppose that there
are two faculties A and B with two students each and two priority groups. We consider true
ranking results s2B , s2A , s1B , s1A . If faculty A wishes to maximize average rank (from the bottom) of
its own students, it will possibly benefit by reporting 0A : s1A , s2A instead of A : s2A , s1A , to obtains2B , s1A , s2A , s1B . As a result of this misreporting, the average rank of students in A improves from2(= (3 + 1)/2) to 2.5(= (3 + 2)/2). However, it hurts s2A , whose absolute position changes fromthree to two.
Student-specific evaluation. If we wish to achieve the “true” ranking of students, our model
may not be appropriate. For example, consider that two faculties A and B are clearly diﬀerent in
the level of students, i.e., the bottom student in A is better (in any sense) than the top one in B.
Under the objective of finding a true ranking, our rule’s resulting priority assignment may not be
acceptable: another formulation and another rule are required.
Endogenous or exogenous quota. In reality, it is common to set exogenous quota for each
attribute and each group or object, but our approach is to endogenously determine it using equity
axioms. Comparing exogenous and endogenous quotas may give practical implications.

7

Appendix

We first prove useful lemmas.
24

Lemma 3. The following two statements are equivalent.
(a) ' satisfies PPL.
P(b) For each g 2 F , for each s 2 Sg , 's (F, {Sf }) = k where jk 1 |'jg (F, {Sf })| < a(s|Sg ) Pjjk |'g (F, {Sf })|.
0

Proof. (b))(a): Suppose (b) is satisfied. For s 2 Sgk and s0 2 Sgk with a(s|Sg )  a(s0 |Sg ),
P
P
P
j
j
j
0
jk 1 |'g (F, {Sf })| < a(s|Sg ) jk |'g (F, {Sf })| andjk0 1 |'g (F, {Sf })| < a(s |Sg ) 
P
P
P
j
j
j
0
jk0 |'g (F, {Sf })| implyjk 1 |'g (F, {Sf })| <jk0 |'g (F, {Sf })|, i.e., k  k .
(a))(b): Suppose (a) is satisfied. Assume, by way of contradiction, that s 2 Sgk but a(s|Sg ) PPj
1 < jk 1 |'jg (F, {Sf })| implies that there exists s00 2 Sg ,jk 1 |'g (F, {Sf })|. Then, a(s|Sg )0such that a(s00 |Sg ) > a(s|Sg ) and s00 2 Sgk where k 0  k. In the same manner, if we assume thatPPjs 2 Sgk but jk |'jg (F, {Sf })| < a(s|Sg ),1 implies that therejk |'g (F, {Sf })|  a(s|Sg )
000
000
000
k0
0
exists s 2 Sg , such that a(s |Sg ) < a(s|Sg ) and s 2 Sg where k > k. These contradict to
PPL.
Lemma 4. Suppose that ' satisfies PPL. The following two statements are equivalent.
(a) ' satisfies IOA.
(b) For each g 2 F , for each {Sf }f 2F , {Ŝf }f 2F , when ng = n̂g , for any s 2 Sg and ŝ 2 Ŝg witha(s|Sg ) = a(ŝ|Ŝg ), 's (F, {Sf }) = 'ŝ (F, {Ŝf }).
Proof. (b))(a) is immediate. We show (a))(b). Suppose (a) is satisfied. Take {Sf }f 2F , {Ŝf }f 2F
such that for g 2 F , ng = n̂g . By IOA, for each k 2 K, |'kg (F, {Sf })| = |'kg (F, {Ŝf })|. Takes 2 Sg and ŝ 2 Ŝg with a(s|Sg ) = a(ŝ|Ŝg ). We must show 's (F, {Sf }) = 'ŝ (F, {Ŝf }). It follows
PP
from Lemma 3 that for k = 's (F, {Sf }), jk 1 |'jg (F, {Sf })| < a(s|Sg )  jk |'jg (F, {Sf })|,
PP
and for k̂ = 'ŝ (F, {Ŝf }), jk̂ 1 |'jg (F, {Ŝf })| < a(ŝ|Ŝg )  jk̂ |'jg (F, {Ŝf })|. Since for eachj 2 K, |'jg (F, {Sf })| = |'jg (F, {Ŝf })|, and a(s|Sg ) = a(ŝ|Ŝg ), we have 's (F, {Sf }) = k = k̂ ='ŝ (F, {Ŝf }).
Lemma 5. Suppose that ' satisfies IOA. The following two statements are equivalent.
(a) ' satisfies PPL and ETP.
a(s0 |S 0 )a(s|S )(b) For each f, f 0 2 F , for each s 2 Sf and s0 2 Sf 0 , when nf f  n 0f , we have 's (F, {Sf }) f's0 (F, {Sf }).
Proof. (b))(a): When (b) is true, PPL and ETP are given by restrictions f = f 0 anda(s0 |Sf 0 )respectively.
nf 0a(s|Sf )=nf(a))(b): Suppose (a) is true but (b) is not for (F, {Sf }f 2F ), where we denote (nf , nf 0 ) = (n1 , n2 ).
a(s0 |S 0 )a(s|S )
Let s 2 Sf and s0 2 Sf 0 be nf f  n 0f , but 's (F, {Sf }) = k > k 0 = 's0 (F, {Sf }). Callf(a(s|Sf ), a(s0 |Sf 0 )) = (a, a0 ) in advance.
(i) Consider (F, {Sf0 }) where (n0f , n0f 0 ) = (n1 , n1 n2 ), and for each g 2 F \{f, f 0 }, Sg0 = Sg . Lemma
4 implies by PPL and IOA that for s 2 Sf0 such that a(s|Sf0 ) = a, 's (F, {Sf0 }) = k. Sincea(s|Sf0 )
=
n0f

2
a
= nn0 a , ETP implies that for s0 2 Sf0 0 such that a(s0 |Sf0 0 ) = n2 a, 's0 (F, {Sf0 }) = 's (F, {Sf0 }) = k.
n1
f0

25

(ii) Consider (F, {Sf00 }) where (n00f , n00f 0 ) = (n2 , n2 ),and for each g 2 F \{f, f 0 }, Sg00 = Sg . Lemma 4
implies that for s00 2 Sf00 such that a(s00 |Sf00 ) = a0 , 's00 (F, {Sf00 }) = 's0 (F, {Sf0 }) = k 0 .
000
2
1 2
0
000
(iii) Consider (F, {Sf000 }), where (n000f , nf 0 ) = (n , n n ), and for each g 2 F \{f, f }, Sg = Sg .
000
000 000
0
000
000
000 000
Lemma 4 implies that for s000
1 2 Sf such that a(s1 |Sf ) = a , and for s2 2 Sf 0 such that a(s2 |Sf 0 ) =00
1 0n2 a, 's000(F, {Sf000 }) = k 0 and 's000(F, {Sf000 }) = k respectively. Since na000 = na2 = nn000a , ETP implies
1
2
f

f0

000
000 000
1 0
that for s000
(F, {Sf000 }) = 's000(F, {Sf000 }) = k 0 . Then, for
3 2 Sf 0 such that a(s3 |Sf 0 ) = n a , 's000
31aa0
n 1 a0000000 n2 as000(F, {Sf000 }) = k > k 0 = 's000(F, {Sf000 }), a contradiction to
2 , s3 2 Sf 0 , n0000 = n1  n2 = n0000 but 's000
2
3ff
PPL within f 0 .

PROOF OF LEMMA 1. Suppose that ' satisfies PPL, ETP, and ES.
(i) (() Suppose that ' satisfies AC. Let |F |2. Let f 2 F . Let {Sg }g2F and {Ŝg }g2F with
nf = n̂f . Take f 0 2 F \ F , and Sf 0 , Ŝf 0 with nf 0 = n̂f 0 = nf K. We denote P = (F, {Sg }g2F ),P 0 = (F [ {f 0 }, {Sg }g2F [{f 0 } ), P̂ = (F, {Ŝg }g2F ), and P̂ 0 = (F [ {f 0 }, {Sg }g2F [{f 0 } ). It is suﬃcient
to show that for each s 2 Sf , and each ŝ 2 Ŝf with a(s|Sf ) = a(ŝ|Ŝf ), we have 's (P ) = 'ŝ (P̂ ).
Let i 2 {1, . . . , nf }, s 2 Sf , and ŝ 2 Ŝf with a(s|Sf ) = a(ŝ|Ŝf ) = i.
1. There is s0 2 Sf 0 such that a(s0 |Sf 0 ) = a(s|Sf )K. Since's (P 0 ) = 's0 (P 0 ).

a(s0 |S 0 )a(s|Sf )Ka(s|S )= Knf f = n 0f , by ETP,nff

2. Similarly, by ETP, there is ŝ0 2 Ŝf 0 such that a(ŝ0 |Ŝf 0 ) = a(ŝ|Ŝf )K. Thus, 'ŝ (P̂ 0 ) = 'ŝ0 (P̂ 0 ).
3. For each k 2 K, it follows from ES that |Sfk0 | = nf as nf 0 = nf K; similarly, |Ŝfk0 | = nf , asn̂f 0 = nf K. Thus, since a(s0 |Sf 0 ) = a(ŝ0 |Ŝf 0 ) = iK, then by PPL, 's0 (P 0 ) = 'ŝ0 (P̂ 0 ).
4. Then, it follows from (1), (2), and (3) that 's (P 0 ) = 's0 (P 0 ) = 'ŝ0 (P̂ 0 ) = 'ŝ (P̂ 0 ).
5. Moreover, by AC, 's (P ) = 's (P 0 ) and 'ŝ (P̂ ) = 'ŝ (P̂ 0 ).
Finally, by (4) and (5), we have 's (P ) = 's (P 0 ) = 'ŝ (P̂ 0 ) = 'ŝ (P̂ ).
()) Suppose, by way of contradiction, that ' satisfies IOA but it does not satisfy AC. Then,for some (F, {Sg }g2F ) with |F |3 and for some G ⇢ F with |G|
2 there is f 2 F ands 2 Sf ( [g2G Sg such that 's (G, {Sg }) 6= 's (F, {Sg }). Let 's (F, {Sg }) = k and 's (G, {Sg }) = k 0
so that k 6= k 0 . Choose a faculty f 0 2 G arbitrarily. Take a problem (F, {Ŝg }g2F ) such that Ŝf = Sfand n̂f 0 = nf K. Let s0 2 Ŝf 0 such that a(s0 |Ŝf 0 ) = a(s|Sf )K.
1. By ES, since n̂f 0 = nf K, for each k 2 K, |'kf 0 (F, {Ŝg })| = nf and |'kf 0 (G, {Ŝg })| = nf . Thus,
since s0 2 Ŝf 0 and f 0 2 F \ G, it follows from PPL that 's0 (F, {Ŝg }) = 's0 (G, {Ŝg }).
2. It follows from IOA that since Ŝf = Sf , we have 's (F, {Ŝg }) = 's (F, {Sg }) = k and's (G, {Ŝg }) = 's (G, {Sg }) = k 0 .

26

a(s0 |Ŝf 0 )a(s|Sf )Ka(s|S )
= nf K= nf f , it follows from ETP and (2) that 's0 (F, {Ŝg }) = 's (F, {Ŝg }) =n̂f 0k and 's0 (G, {Ŝg }) = 's (G, {Ŝg }) = k 0 .

3. Since

Therefore, by (1) and (3), we have k = 's0 (F, {Ŝg }) = 's0 (G, {Ŝg }) = k 0 . This contradicts ourassumption that k 6= k 0 .
(ii) It is straightforward that IOA implies ACC. The following example shows the case in which 'satisfies ACC but it does not satisfy IOA. Let F = {f, g, h} and K = 2. Consider two problems(F, {Sf }) and (F, {Ŝf }), with (nf , ng , nh ) = (2, 3, 4) and (n̂f , n̂g , n̂h ) = (3, 3, 3). We denote a
student of i-th absolute position as sif , sig , or sih . For (F, {Sf }), (F, {Ŝf }), and their reduced
problems, the assignments by ' are as follows.

GF{f, g}{g, h}{f, h}[g2G '2g (G, {Sg }){s2f , s2g , s3g , s3h , s4h }{s2f , s3g }{s2g , s3g , s3h , s4h }{s2f , s3h , s4h }Table 2: Assignments for (ii)[g2G '1g (G, {Sg })[g2G '2g (G, {Ŝg })1
1 1 2{sf , sg , sh , sh }{s2f , s3f , s2g , s3g , s2h , s3h }{s1f , s1g , s2g }{s2f , s3f , s2g , s3g }{s1g , s1h , s2h }{s2g , s3g , s2h , s3h }1
1 2{sf , sh , sh }{s2f , s3f , s2h , s3h }[g2G '1g (G, {Ŝg }){s1f , s1g , s1h }{s1f , s1g }{s1g , s1h }{s1f , s1h }Since '1g ({f, g}, {Sf }) 6= '1g ({g, h}, {Sf }), ACC holds in (F, {Sf }). However, though ng = n̂g ,|'1g ({f, g}, {Sf })| = 2 6= 1 = |'1g ({f, g}, {Ŝf })|. IOA is violated.
(iii) It is straightforward that IOA implies PM. The following example shows the case in which' satisfies PM but it does not satisfy IOA. Let F = {f, g} and K = 2. Consider two problems(F, {Sf }) and (F, {Ŝf }), with (nf , ng ) = (3, 5) and (n̂f , n̂g ) = (3, 6). ' assigns'(F, {Sf }) = {{s3f , s4g , s5g }, {s1f , s2f , s1g , s2g , s3g }}, and '(F, {Ŝf }) = {{s2f , s3f , s4g , s5g , s6g }, {s1f , s1g , s2g , s3g }}.
Since 's2f (F, {Sf }) = 1 < 2 = 's2f (F, {Ŝf }), PM is satisfied but IOA is violated.
PROOF OF LEMMA 2. Let s 2 Sf .
n (k 1)n k()) Let s 2 S k . Then, for k = '⇤s (F, {Sf }), [ f K ] < a(s|Sf )  [ Kf ] holds from the definition.
n kn (k 1)
It is immediate that a(s|Sf )  [ Kf ]  nf Kk . On the other hand, because [ f K ], a(s|Sf ) 2 N,n (k 1)a(s|S )
nf kK1 < [ f K ] + 1  a(s|Sf ). Therefore, kK1 < nf f  Kk holds.
(() Suppose that kK1 <n ka(s|Sf )nfn (k 1)

 Kk . It is immediate that [ f Kn knf (k 1)< a(s|Sf ). If we
K
nf k
n k
< [ Kf ] + 1  a(s|Sf ), aK]assume [ Kf ] < a(s|Sf ), since [ Kf ], a(s|Sf ) 2 N, it follows thatn (k 1)n kcontradiction. [ f K ] < a(s|Sf )  [ Kf ] leads s 2 Sfk ✓ S k . (Q.E.D.)

PROOF OF PROPOSITION 1.
PPL: This is clear from Lemma 3. The relative position rule is a specific case of rules in statementnf kn (k 1)(b); |'⇤k[ f K ].
f (F, {Sf })| = [ K ]ETP: Suppose s 2 Sf and s0 2 Sf 0 with
Lemma 2.

a(s0 |Sf 0 )a(s|Sf )=. 's (F, {Sf }) = 's0 (F, {Sf }) follows from
nf
nf 0

27

n

n

ES: When Kf 2 N, for each k 2 K, |'kf (F, {Sf })| = |Sfk | = |{s 2 Sf | Kf {'⇤s (F, {Sf }) 1} <nna(s|Sf )  Kf '⇤s (F, {Sf })}| = Kf .
IOA, AC, and ACC: These are also clear from the formula of '⇤s , only depending on the numberof students in own faculty, not those in other faculties.
PM: Since population change does not aﬀect other faculty’s assignment under '⇤ , we only check theeﬀect within each faculty. Lemma 2 shows that '⇤s (F, {Sf }) = k is equivalent to kK1 < a(s|Sf )  Kk .
For Sf0 = Sf [ {s0 } such that a(s0 |Sf0 ) = 1, for each s 2 Sf , we have a(s|Sf0 ) = a(s|Sf ) + 1. Because0k0
Lemma 2 also implies that '⇤s (F, {Ŝf }) = k 0 is equivalent to k K 1 < a(s|Sf0 )  K, a(s|Sf0 ) > a(s|Sf )implies k 0 k. (Q.E.D.)
PROOF OF THEOREM 1. “If” part is immediate from Proposition 1. We show “Only if”
part. Suppose ' satisfies PPL, ETP, ES, and IOA.
Pn kClaim 1. For each k 2 K, jk |'jf (F, {Sf })| [ Kf ].
P
Proof. For (F, {Sf }), for g 2 F , for k1 2 K, let jk1 |'jg (F, {Sf })| = [ ngKk1 ] 1 =: a1 . Notethat for s1 2 Sg such that a(s1 |Sg ) = a1 + 1, by PPL, 's1 ((F, {Sf })) > k1 . Pick another problem(F, {Sf0 }) such that for g 0 2 F , n0g0 = K, and for g 2 F , Sg0 = Sg . ES implies that for s01 2 Sg0 0 suchthat a(s01 |Sg0 0 ) = k1 , 's01 (F, {Sf0 }) = k1 while Lemma 4 implies by PPL and IOA that 's1 (F, {Sf0 }) ='s1 (F, {Sf }) > k1 . However,a(s01 |Sg0 0 )0

1 n g k1[
] = a1n+1
implies that statement (b) in Lemma
0
n0g K
g
P
Applying the same argument shows that jk1 |'jf (F, {Sf })| =

n0g0

= kK1

5 is violated, a contradiction.
n k
n k
n k
[ fK 1 ] 2, [ fK 1 ] 3, [ fK 1 ] 4, ... also lead a contradiction.
Pn kClaim 2. For each k 2 K, jk |'jf (F, {Sf })|  [ Kf ].
P
Proof. For (F, {Sf }), for g 2 F , for k2 2 K, let jk2 |'jg (F, {Sf })| = [ ngKk2 ] + 1 =: a2 . Note thatfor s2 2 Sg such that a(s2 |Sg ) = a2 , by PPL, 's2 (F, {Sf })  k2 . Let ✏ := 1 { ngKk2 [ ngKk2 ]} 2 (0, 1]
ng
and take a corresponding (suﬃciently large) number m✏ := [ ✏K
] + 1. Then, pick another problem
0
0
0
✏
0
(F, {Sf }) such that for g 2 F , ng0 = m K, and for g 2 F , Sg = Sg . ES implies that for s02 2 Sg0 0such that a(s02 |Sg0 0 ) = m✏ k2 + 1, 's02 (F, {Sf0 }) = k2 + 1 while Lemma 4 implies by PPL and IOA
that 's2 (F, {Sf0 }) = 's2 (F, {Sf })  k2 . However,00a(s02 |Sg0 0 )n0g0✏= mmk✏2K+1 = kK2 + m1✏ K  kK2 + n✏0 =gn ka(s |S )1{[ gK 2 ] + 1} = na20 = n2 0 g implies that statement (b) in Lemma 5 is violated, a contradiction.
n0g
g
g
P
n k
n k
n k
Applying the same argument shows that jk2 |'jf (F, {Sf })| = [ fK 2 ] + 2, [ fK 2 ] + 3, [ fK 2 ] + 4, ...

also lead a contradiction.

By Claims 1 and 2, we characterize the relative position rule by (i) PPL, (ii) ETP, (iii) ES,and (iv) IOA. Since Lemma 1 shows that AC and IOA are equivalent under (i)-(iii), the relative
position rule is now characterized by the combination of (i), (ii), (iii), and (iv’) AC. (Q.E.D.)

28

PROOF OF PROPOSITION 3. Throughout the proof, fix a problem (F, {Sf }) and the rule'⇤ . Thus, we omit the notation of ✓e ( · |F, {Sf }, '⇤ ) and ✓; ( · |F, {Sf }, '⇤ ) as ✓e ( · ) and ✓; ( · ).
We denote, for each K, the number of lower-side envious students and that of upper-side envious
students by ✓l (K) and ✓u (K). Thus, ✓e (K) = ✓l (K) + ✓u (K).
(a) We first perform the following process to obtain {nj , q j }j=1,...,J , a regular case representationof {nf }f 2F . Align {nf } in ascending order with arbitrary tie-breaking.
Step 1. Pick the first (smallest) element from {nf } and name it n1 . Let j(1) = 1 and q 0 (1) = 1.
Step k
2. Pick the k -th element from {nf }. If the element is strictly larger than the element
picked in step k 1, let j(k) = j(k 1) + 1, q j(k 1) = q 0 (k 1), q 0 (k) = 1, and name the elementnj(k) . Otherwise, let j(k) = j(k 1) and q 0 (k) = q 0 (k 1) + 1. After step |F |, let J = j(|F |),q j(|F |) = q 0 (|F |), and terminate the process.
(b) Using the form {nj , q j }j=1,...,J , by induction of K, we next prove the relations
PP(1) ✓l (K) = Jj=11 (K 1)q j+1 1nj >K , and (2) ✓u (K) = Jj=11 (nj K)q j 1nj >K .
We note that, if ng = min{nf } = n1 , since no g 0 2 F such that ng0 < ng exist, no students in ghave lower-side envy. Similarly, if ng = max{nf } = nJ , since no g 0 2 F such that ng0 > ng exist,
no students in g have upper-side envy.
Step 1. Let K = 2. For j 2, 1 out nj students, top of the worse group, has lower-side envy ifSthere is f with nf < nj , at least two students are assigned to one group, i.e., ij 1 {ni > 2} =PP{nj 1 > 2}. Thus, we have ✓l (2) = Jj=2 1 ⇥ q j ⇥ 1nj 1 >2 = Jj=11 (2 1)q j+1 1nj >2 .
For j  J 1, nj 2 out nj students, all but bottom of each group, have upper-side envy if at leastS
two students exist in each of this faculty and f with nf > nj , i.e., i j {ni > K} = {nj > K}.
P
P
Thus, we have ✓u (2) = Jj=11 (nj 2) ⇥ q j ⇥ 1nj >2 = Jj=11 (nj 2)q j 1nj >2 .
Step k
2. Assume that (1) and (2) are true for K = k 1 and let K = k. Fluctuation from✓l (K 1) to ✓l (K) is sum of a) decrease by ((K 1) 1)q j if nj 1 is exactly equal to K, and b)
increase by q j if nj 1 is strictly larger than K. Thus,ll✓ (K) = ✓ (K

1)

J
X

((K

j=2

=

J 1
X

(K

1)

j

1) ⇥ q ⇥ 1nj 1 >K 1\nj 1 K +

J
X
j=2

1 ⇥ q j ⇥ 1nj 1 >K 1\nj 1 >K

1)q j+1 1nj >K .

j=1

Similarly, fluctuation from ✓u (K 1) to ✓u (K) is sum of a) decrease by (njexactly equal to K, and b) decrease by q j if nj is strictly larger than K.

29(K1))q j if nj isuu✓ (K) = ✓ (K

J 1
X

1)

(n

j

1)) ⇥ q ⇥ 1nj >K 1\nj K

(K

j=1

=

J 1
X

(nj

J 1
X

j

j=1

1 ⇥ q j ⇥ 1nj >K 1\nj >KK)q j 1nj >K .

j=1(c) Finally, we show the proposition as follows.
Envy-lexicographic optimum. Formulae (1) and (2) show ✓l (K) = ✓u (K) = 0 if and only if
K nJ 1 . When K = nL 1 , null subgroups arise in faculties with nf  nJ 2 . As K grows, empty
groups increase in faculties with nf  nJ 1 , and will arise in faculties with nf = nJ after K nJ .
Therefore, K = nJ 1 is the unique optimum in cases including regular ones. When nJ 1 does notexist, i.e., nf = nf 0 for any f, f 0 , there are multiple optima including nf .
Null-lexicographic optimum. By Footnote 8, it is suﬃcient to find the minimizer of ✓e ( · )subject to K  n1 . If n1 = 1, since K 2, K = 2 is the solution. Otherwise, where K < n1 ,lu

✓ (K) + ✓ (K) =

J 1
X

(K

1)q

j+1

+ (n

j

j

K)q = (n

1

1

K)q +

j=1

= (q JJ 1
X(nj

1)q j + (K

1)q J

(nj

1)q j + (K

1)q J

j=2

q 1 )K + n1 q 1 +

J 1
X

(nj

1)q j

q J ...(c.1)

j=2

Where K = n1 ,lu

✓ (K) + ✓ (K) =

J 1
X

(K

1)q

j+1

+ (n

j

j

K)q = (1

2

K)q +

j=2

= (q JJ 1
Xj=2

q 2 )K + q 2 +

J 1
X

(nj

1)q j

q J ...(c.2)

j=2

Immediately, if q 1 = q 2 = q J , the statement is true. Since (c.1) is a monotone function of K, thesolution is either of corners {2, n1 }. K = n1 is the minimizer if
⇥ J
⇤ ⇥
⇤
(q
q 1 ) + n1 q 1 (q J q 2 )n1 + q 2 ^ (q J q 1 )(n1 1) + n1 q 1 (q J q 2 )n1 + q 2⇥⇤ ⇥⇤, q 1 + q 2 q J 0 ^ q 1 + (n1 1)q 2 q J 0 .
Since the former is binding, we obtain that K = n1 is the optimum if q 1 + q 2
is the optimum if q 1 + q 2 q J 0. (Q.E.D.)

qJ

0 and K = 2

PROOF OF PROPOSITION 4.
(i) Fix an arbitrary problem (F, {Sf }) with F = {f, g}, in which at least one student s 2 Sf withn +na0 (s|{Sf }) < fnf g a(s|Sf ) exists. Name him s. Since the relative position rule satisfies PPL,a⇤ (s|{Sf }) = a(s|Sf ) + |{s00 2 Sg | '⇤s00 (F, {Sf }) < '⇤s (F, {Sf })}| + |{s00 2 Sg | ['⇤s00 (F, {Sf }) =30

'⇤s (F, {Sf })] ^ [s 0 s00 ]}| ...(*).
(Case 1: a0 (s|{Sf }) = a(s|Sf )) It is immediate from (*) that a⇤ (s|{Sf }) a(s|Sf ) = a0 (s|{Sf }).
(Case 2: a0 (s|{Sf }) < a(s|Sf )) Take s0 2 Sg such that a(s0 |Sg ) = a0 (s|{Sf }) a(s|Sf ). Then, by0n +na(s|S )g)a0 (s|{Sf }) < fnf g a(s|Sf ), a(sn|S< nf f . Lemma 5 implies that 's0 (F, {Sf })  's (F, {Sf }).
g
If '⇤s0 (F, {Sf }) = '⇤s (F, {Sf }), by its construction, s0 is included in the last term of RHS in (*).
Otherwise, s0 is included in the second term. PPL of '⇤ implies that a⇤ (s|{Sf })a(s|Sf ) +0a(s |Sg ) a0 (s|{Sf }).
The same result does not hold when |F | 3, as shown in the next example. Let F = {f, g, h},(nf , ng , nh ) = (9, 7, 24), K = 5. 0 is as follows (sif stands for a student with a(sif |Sf ) = i).
3a(s3f |Sf )
13
3
3
2
1
7 6 5 4 3 2 1 3 2 1
3 a0 (sf |{Sf })=<=. However,0 : ..., sf , sf , sf , sg , sg , sg , sg , sg , sg , sg , sh , sh , sh . For , sf , P
40
9nf
f 2F nf
⇤ 3
3
00
00
⇤
a (sf |{Sf }) = a(sf |Sf ) + |{s 2 Sg [ Sh | 's00 (F, {Sf }) = 1}| + |{s 2 Sg [ Sh | ['s00 (F, {Sf }) =2] ^ [s 0 s00 ]}| = 3 + (1 + 4) + (1 + 0) = 9 < 13 = a0 (s3f |Sf ).
a0 (s|{Sf })(ii) Fix an arbitrary problem (F, {Sf }), in which at least one student s 2 Sf with P<
f 2F nfa(s|Sf )a0 (s|{Sf }){ K1 + P |F | nf } exists. Name him s and his faculty f . The assumption P
<
nf
f 2F
f 2F nf⇤Pa(s|Sf )a(s|S )n ' (F,{S })1{ K1 + P |F | nf } implies a0 (s|{Sf }) < { nf f
} f 2F nf |F |  { n1f [ f s K f ]
nf
K
f 2F
P
'⇤s (F,{Sf }) 1 P
1
}
n
|F
|

|F |.
f
f 2F
f 2F nfK
K⇤
00
On the other hand, a (s|{Sf }) = |{s 2 [f 2F Sf | '⇤s00 (F, {Sf }) < '⇤s (F, {Sf })}| + |{s00 2 [f 2F Sf |P
P
nf ('⇤s (F,{Sf }) 1)
nf ('⇤s (F,{Sf }) 1)['⇤s00 (F, {Sf }) = '⇤s (F, {Sf })] ^ [s ⌫0 s00 ]}|
[
]
{
1} =
f 2F
f 2F
K
K
'⇤s (F,{Sf }) 1 P⇤|F |. Thus, we obtain a (s|{Sf }) > a0 (s|{Sf }). (Q.E.D.)
f 2F nfK

PROOF OF PROPOSITION 5.
Let F = {f, g}, (Sf , Sg ) = ({s6 , s5 , s4 }, {s3 , s2 , s1 }) with 0 : s6 , s5 , s4 , s3 , s2 , s1 , K = 3, andH = {a, b, c, d, ;}. ⌫⇤ is determined as ⇤ : s6 , s3 , s5 , s2 , s4 , s1 . % is as follows.
Table 3: List of preferences% s 6 % s5 % s 4 % s 3 % s 2 % s 1
d
a
d
a
c
c
a
c
;
b
a
a
b
b
a
c
b
;
c
d
b
d
d
d
;
;
c
;
;
b
(%) is determined as s⌫60 = d, s⌫50 = a, s⌫40 = ;, s⌫30 = b, s⌫20 = c, and s⌫10 = ;. Similarly,
⇤
⇤
⇤
⇤
⇤
⇤
⌫⇤
(%) is determined as s⌫6 = d, s⌫3 = a, s⌫5 = c, s⌫2 = b, s⌫4 = ;, and s⌫1 = ;. We can see⇤
for s2 , a⇤ (s2 |{Sf }) = 3 > 2 = a0 (s2 |{Sf }) but s⌫20 (%) = c %s2 b = s⌫2 (%). (Q.E.D.)⌫031

References
Abdulkadiroğlu, A., P. A. Pathak, and A. E. Roth (2009): “Strategy-proofness versus
Eﬃciency in Matching with Indiﬀerences: Redesigning the NYC High School Match,” American
Economic Review, 99, 1954–1978.
Abdulkadiroğlu, A. and T. Sönmez (1999): “House Allocation with Existing Tenants,” Journal of Economic Theory, 88, 233–260.
——— (2003): “School Choice: A Mechanism Design Approach,” American Economic Review, 93,
729–747.
Adachi, H. (2000): “On a characterization of stable matchings,” Economics Letters, 68, 43–49.
Álvarez, C. R. and A. R. Medina (2020): “School Choice with Transferable Students’ Characteristics,” Working paper.
Balbuzanov, I. and M. H. Kotowski (2019): “Endowments, exclusion, and exchange,” Econometrica, 87, 1663–1692.
Balinski, M. and T. Sönmez (1999): “A Tale of Two Mechanisms: Student Placement,” Journalof Economic Theory, 84, 73–94.
Bloch, F. (2017): “Second-best mechanisms in queuing problems without transfers: The role ofrandom priorities,” Mathematical Social Sciences, 90, 73–79.
Erdil, A. and H. Ergin (2008): “What’s the Matter with Tie-breaking? Improving Eﬃciency
in School Choice,” American Economic Review, 98, 669–689.
Erdil, A. and T. Kumano (2019): “Eﬃciency and stability under substitutable priorities with
ties,” Journal of Economic Theory, 184, 104950.
Ergin, H. (2000): “Consistency in House Allocation Problems,” Journal of Mathematical Economics, 34, 77–97.
Greenberg, K., P. A. Pathak, and T. Sönmez (2021): “Mechanism Design meets Priority
Design: Redesigning the US Army’s Branching Process,” Working paper.
Hafalir, I. E., M. B. Yenmez, and M. A. Yildirim (2013): “Eﬀective Aﬃrmative Action in
School Choice,” Theoretical Economics, 8, 325–363.
Kamada, Y. and F. Kojima (2015): “Eﬃcient matching under distributional constraints: Theory and applications,” American Economic Review, 105, 67–99.

32

Kojima, F. (2012): “School choice: Impossibilities for aﬃrmative action,” Games and Economic
Behavior, 75, 685–693.
Kumano, T. and M. Kurino (2022): “Quota Adjustment Process,” Working paper.
Kurino, M. (2014): “House Allocation with Overlapping Generations,” American Economic Journal: Microeconomics, 6, 258–289.
Maniquet, F. (2003): “A characterization of the Shapley value in queueing problems,” Journalof Economic Theory, 109, 90–103.
Moulin, H. (1991): Axioms of Cooperative Decision Making, Cambridge University Press, Cambridge.
Pathak, P. A. and T. Sönmez (2008): “Leveling the Playing Field: Sincere and SophisticatedPlayers in the Boston Mechanism,” American Economic Review, 98, 1636–1652.
Shapley, L. and H. Scarf (1974): “On Cores and Indivisibility,” Journal of Mathematical
Economics, 1, 23–37.
Svensson, L.-G. (1994): “Queue Allocation of Indivisible Goods,” Social Choice and Welfare, 11,
223–230.
——— (1999): “Strategy-proof Allocation of Indivisible Goods,” Social Choice and Welfare, 16,
557–567.
Thomson, W. (2011): “Fair allocation rules,” in Handbook of social choice and welfare, Elsevier,vol. 2, 393–506.

33