This paper studies general multi-unit probabilistic assignment problems involving indivisible objects, with a particular focus on achieving the fairness notion of equal treatment of equals (ETE) and satisfying various efficiency criteria. We extend the definition of ETE so that it accommodates a wide range of constraints and applications. We introduce the ETE reassignment procedure, which transforms any assignment into one that satisfies ETE, and examine whether the efficiency properties satisfied by the original assignment—namely, ex-post efficiency, ordinal efficiency, and rank-minimizing efficiency—are preserved under the ETE reassignment. We show that, while the ETE reassignment of an ex-post efficient assignment remains ex-post efficient, it may fail to preserve ordinal efficiency in general settings. However, since the ETE reassignment of a rank-minimizing assignment preserves rank-minimizing efficiency, there must exist an assignment satisfying both ETE and ordinal efficiency. Furthermore, we propose a computationally efficient method for constructing assignments that satisfy both ETE and ordinal efficiency under general upper bound constraints by combining the serial dictatorship rule with appropriately specified priority lists and the ETE reassignment procedure.

JEL classification: C78, D63, D47

Keywords: Probabilistic assignment, Equal treatment of equals, Ordinal efficiency, Rank-minimizing, General upper bound constraints

1 Introduction↩︎

This paper studies general multi-unit assignment problems with indivisible objects, focusing on the fairness requirement known as equal treatment of equals (ETE), which requires that agents with identical relevant characteristics receive equal treatment. Rooted in Aristotle’s Nicomachean Ethics (Book V), ETE represents an intuitive notion of fairness. A large body of empirical and experimental research suggests that individuals dislike unfair outcomes and are often willing to bear costs to avoid them; see, for example, Fehr and Charness (2025) for a survey. This suggests that, even when efficiency is a central concern, allocation rules should satisfy at least a minimal fairness requirement such as ETE.

However, in environments with indivisible objects, strict enforcement of ETE may lead to inefficiencies when the number of equals demanding an object exceeds its supply. To address this issue, the recent literature, including Bogomolnaia and Moulin (2001), Budish et al. (2013), Erdil (2014), and Basteck and Ehlers (2025), considers probabilistic assignments. Under such assignments, fairness is preserved by requiring equals to receive identical probability distributions over objects rather than identical deterministic outcomes.

In this literature, agents with identical preference orderings are typically regarded as equals. This definition raises several practical difficulties. First, it is incompatible with policy goals such as affirmative action, because it precludes giving preferential treatment to disadvantaged agents who report the same preferences as advantaged ones.³ Second, if agents who are asymmetric in terms of feasibility constraints are nevertheless regarded as equals, achieving efficiency may become difficult.⁴ Accordingly, we adopt an extended notion of ETE that avoids these problems.

In this paper, we investigate whether an assignment that satisfies (the extended) ETE can also satisfy additional desirable properties, and, if so, how such an assignment can be constructed. To obtain an ETE assignment, we use the following simple procedure. First, we arbitrarily fix a pure assignment, in which each agent receives an individual assignment with probability one. Second, for each group of equals, we pool the individual assignments they receive under this pure assignment and redistribute them uniformly within the group, so that each agent receives each of these assignments with equal probability. This procedure is called the ETE reassignment of an assignment. It can be naturally extended to cases where the original assignment is not pure but probabilistic. In general settings, the ETE reassignment yields an assignment that satisfies ETE.

The key question is whether the properties satisfied by the original assignment are preserved under its ETE reassignment. If they are preserved, then obtaining the ETE reassignment itself is straightforward, and hence—for our purposes—it suffices to construct an original assignment that satisfies the target properties. In this study, we focus on three efficiency notions from the existing literature as the properties of interest.

First, we consider ex-post efficiency (hereafter EE), which requires that every pure assignment realized with positive probability must be (Pareto) efficient. We show that if the initial assignment is EE, then its ETE reassignment is also EE. Second, we focus on ordinal efficiency (OE), which is stronger than EE. An assignment is OE if it is not first-order stochastically dominated by any other assignment for any agent. Unfortunately, in general, the ETE reassignment of an OE assignment may not be OE. Third, we consider a stronger notion of efficiency, known as rank-minimizing efficiency (hereafter RE). In general, an RE assignment always exists and is also OE. Moreover, since the ETE reassignment of an RE assignment remains RE, this ensures the existence of assignments that satisfy both ETE and RE (and thus OE).

However, except in the special case of unit demand with simple capacity constraints, no computationally efficient method is known for deriving an RE assignment. This implies that, although an ETE reassignment itself is easy to obtain, finding an original RE assignment remains computationally hard. We therefore propose a computationally efficient method for constructing an assignment that satisfies both ETE and OE in general settings.

We consider the case where feasible assignments are restricted by general upper bounds. In this setting, the serial dictatorship rule with an arbitrary priority list yields an OE assignment; however, the ETE reassignment of this assignment may fail to be OE. In contrast, if the priority list satisfies a property called consecutive equals, the serial dictatorship rule yields an OE assignment whose ETE reassignment is also OE.

2 Related Literature↩︎

We consider a general multi-unit assignment model, which includes the course allocation problem, for example, see Sönmez and Ünver (2010) and Budish and Cantillon (2012). Kojima (2009) examines probabilistic assignments in a multi-unit assignment model. Balbuzanov (2022) generalizes Kojima’s model by incorporating general feasibility constraints, as practical course allocation problems often involve various restrictions, such as those arising from scheduling constraints. In the models of Kojima (2009) and Balbuzanov (2022), agents are assumed to have specific preferences such that each agent holds a fixed ranking over individual objects, and only the expected number of assigned objects matters. In contrast, we allow agents to have general preferences.

We focus on a relatively weak fairness notion, ETE. This concept has been studied extensively across a wide range of allocation problems (Varian, 1974; Moulin, 2004; Thomson, 2011; Yokote et al., 2019). In single-unit assignment problems, including one-to-many matching environments, ETE has been analyzed by Bogomolnaia and Moulin (2001). ETE is weaker than several other fairness notions, such as envy-freeness. These stronger notions typically impose requirements that go beyond the naı̈ve definition of ETE, which requires only that agents with identical preferences receive identical assignments. As a result, such fairness notions may be incompatible with certain policy objectives, including affirmative action, which intentionally prescribes differential treatment among agents who may share the same preferences.

We consider three efficiency notions: EE, OE, and RE. Among them, RE is the strongest, followed by OE, and EE is the weakest. OE is a widely used concept in the probabilistic assignment literature, including Bogomolnaia and Moulin (2001) and Budish et al. (2013). Recently, several studies, such as Featherstone (2010), have focused on RE, as many real-world matching authorities take the rank positions of assignments into account. Since Feizi (2024) shows that several fairness notions other than ETE are incompatible with RE, it is appropriate to adopt ETE as the fairness notion along with RE.

We study the case in which feasible assignments are subject to general upper bound constraints. Our general constraint structure encompasses, as special cases, the regional caps discussed by Kamada and Kojima (2015), as well as the object-specific general upper bound constraints considered by Okumura (2019) and Kamada and Kojima (2024). While Imamura and Kawase (2025) consider this general constraint structure, their model is limited to the unit-demand setting.⁵ In the multi-unit demand case with general upper bound constraints, we introduce a method for deriving an assignment that satisfies both OE and ETE.

We compare our method, which applies the ETE reassignment, with several existing methods proposed in the literature. To begin with, it is worth noting that these existing methods were originally designed to satisfy the standard notion of ETE. As emphasized above, mechanisms that provide preferential treatment to disadvantaged agents through affirmative action do not satisfy this standard notion. Moreover, the standard notion is not compatible with several efficiency concepts when general constraint structures are allowed. Therefore, we extend the concept of ETE and develop a method for deriving assignments that satisfy this extended notion.

First, Nikzad (2022), Ortega and Klein (2023), Troyan (2024), and Okumura (2026a) study the uniform rank-minimizing mechanism, which satisfies both RE and ETE in the unit-demand case with simple capacity constraints. However, as noted by Troyan (2024, footnote 11), this mechanism suffers from a computational drawback: finding all rank-minimizing assignments is computationally infeasible. In contrast, our method is computationally efficient for constructing an assignment that satisfies both RE and ETE in the unit-demand case with simple capacity constraints.

Second, the random serial dictatorship rule is discussed in several previous studies, such as Bogomolnaia and Moulin (2001), and yields assignments satisfying both EE and ETE. However, as shown by Bogomolnaia and Moulin (2001), the outcome of this rule may fail to satisfy OE. In contrast, we provide a method that yields assignments satisfying both OE and ETE under a general constraint structure.

Third, Bogomolnaia and Moulin (2001) introduce the probabilistic serial mechanism, which satisfies both OE and envy-freeness, and hence ETE. Budish et al. (2013) generalize this mechanism and show that it yields assignments satisfying both OE and envy-freeness under general constraint structures. However, in their extension of the probabilistic serial mechanism, Budish et al. (2013) restrict their attention to single-unit demand settings.

Balbuzanov (2022) also proposes a generalized probabilistic serial mechanism that applies under more general constraints with multi-unit demand and shows that its outcome satisfies both OE and ETE. Nevertheless, for this mechanism to attain efficiency, it is necessary that agents have specific preference structures, as explained above.

Nguyen et al. (2016) also generalize the probabilistic serial mechanism and show that it yields assignments satisfying both OE and envy-freeness even when agents’ ordinal preferences exhibit a limited degree of complementarities, provided that bounded violations of simple capacity constraints are allowed. In contrast, our method does not rely on such approximate feasibility: although we adopt a weaker fairness requirement, we impose feasibility strictly and remain applicable to more general preference profiles.

Finally, it should be noted that the mechanism that naively applies the results of this study is vulnerable to strategic manipulation. For comparison, as shown by Bogomolnaia and Moulin (2001) and Budish et al. (2013), the random serial dictatorship rule satisfies strategy-proofness in a strict sense, whereas the probabilistic serial mechanism satisfies a weaker form of this property.⁶ In contrast, the mechanism that naively applies our results fails to satisfy strategy-proofness even in a weak sense; that is, under truth-telling, an agent’s outcome can be first-order stochastically dominated by that under a manipulation.

Even in the existing literature on multi-unit demand models, achieving strategy-proofness has been shown to be difficult. In particular, Balbuzanov (2022) shows that their generalized probabilistic serial mechanism fails to satisfy weak strategy-proofness in the considered setting. Moreover, Kornbluth et al. (2025) establish that the generalized probabilistic serial mechanism proposed by Nguyen et al. (2016) likewise does not satisfy weak strategy-proofness. These results suggest that, in general multi-unit demand models, imposing both fairness and strategy-proofness may be difficult, even when strategy-proofness is required only in a weak sense. Therefore, in this paper, we abstract from strategy-proofness and focus instead on mechanisms that are efficient and fair.

3 Model↩︎

Let \(A\) and \(O\) be finite sets of agents and object types respectively. A pure assignment \(y\) is a \(\left\vert A\right\vert \times \left\vert O\right\vert\) matrix, where \(y_{ao}\in \mathbb{Z}_{+}\) represents the number of copies of object type \(o\) assigned to agent \(a\). Moreover, let \(y_{a}=\left( y_{ao}\right) _{o\in O}\in \mathbb{Z}_{+}^{\left\vert O\right\vert }\) and \(y_{o}=\left( y_{ao}\right) _{a\in A}\in \mathbb{Z}_{+}^{\left\vert A\right\vert }.\)

Pure assignments are subject to constraints. A pure assignment that satisfies these constraints is called a feasible pure assignment. Let \(Y\) be the set of all feasible pure assignments, which is assumed to be a non-empty and finite set.

The set \(Y\) may be subject to various types of constraints, including physical capacity constraints and institutional constraints. In addition, if one is interested only in assignments that satisfy certain desirable properties, \(Y\) can be defined as the set of all assignments satisfying those properties. For instance, given a priority structure, if attention is restricted to stable assignments, then \(Y\) coincides with the set of all stable assignments.

Let \(X\subseteq \mathbb{Z}_{+}^{\left\vert O\right\vert }\) be the set of all possible pure (individual) assignments for \(a\in A\). We assume that \(X\) is finite. An integer vector \(x=\left( x_{1},\cdots ,x_{\left\vert O\right\vert }\right) \in \mathbb{Z}_{+}^{\left\vert O\right\vert }\) is said to be a feasible pure assignment for \(a\) if \(x=y_{a}\) for some \(y\in Y\). Note that \(X\) may include some infeasible pure assignment for some agents, since the feasibility constraints encoded in \(Y\) may be complex. Specifically, if \(x_{o}=1\) and \(x_{o^{\prime }}=0\) for all \(o^{\prime }\in O\setminus \left\{ o\right\}\), we simply write \(x=o\). Likewise, an integer vector \(z=\left( z_{1},\cdots ,z_{\left\vert A\right\vert }\right) \in \mathbb{Z}_{+}^{\left\vert A\right\vert }\) is said to be a feasible pure assignment for \(o\) if \(z=y_{o}\) for some \(y\in Y\).

We introduce standard constraints in the single-unit assignment model. First, we say that \(Y\) satisfies(single) unit demand if\(y\in Y\) implies \[\sum\limits_{o\in O}y_{ao}=1\text{ for all }a\in A.\]Next, let \(q_{o}\in \mathbb{Z}_{++}\) be the capacity (i.e., the number of copies) of \(o\in O\). We say that \(Y\) satisfies thesimple capacity constraint if \(y\in Y\) implies \[\sum\limits_{a\in A}y_{ao}\leq q_{o}\text{ for all }o\in O\text{.}\]

Let \(\succsim _{a}\) be a preference relation of \(a\) over \(X\), where \(x\succ _{a}x^{\prime }\) means that \(a\) prefers \(x\) to \(x^{\prime }\) and \(x\succsim _{a}x^{\prime }\) means \(x\succ _{a}x^{\prime }\) or \(x=x^{\prime }\). Note that \(y_{a}\succ _{a}y_{a}^{\prime }\) indicates that \(a\) prefers the pure assignment \(y\) to \(y^{\prime }\). A feasible pure assignment \(y\in Y\) is efficient if there is no feasible pure assignment \(y^{\prime }\in Y\) that Pareto dominates \(y\); that is, \(y_{a}^{\prime }\succ _{a}y_{a}\) for some \(a\in A\) and \(y_{b}^{\prime }\succsim _{b}y_{b}\) for all \(b\in A\).

Let \(A_{1},\cdots ,A_{N}\) be a partition of \(A\), where \(N\leq \left\vert A\right\vert\), and for any \(n=1,\cdots ,N\), \(a,b\in A_{n}\) if and only if \(a\) and \(b\) are equals. We refer to each \(A_{n}\) as a group of equals.

Throughout this paper, we impose the following two assumptions.

Assumption 1

For each \(n=1,\cdots ,N\) and any \(a,b\in A_{n}\),\(\succsim _{a}=\succsim _{b}\).

Assumption 1 means that two agents are regarded as equals only if their preference orders are identical. Note that \(a\) and \(b\) may belong to different groups of equals even if \(\succsim _{a}=\succsim _{b}\). For example, if affirmative action permits giving priority to racial minority students in assignments, then two students with different races are no longer considered “equals”.

Assumption 2

For any two agents (equals) \(a,b\in A_{n}\)for some \(n=1,\cdots ,N\), let \(y\)and \(y^{\prime }\)be two pure assignments such that \(y_{ao}=y_{bo}^{\prime }\)and \(y_{bo}=y_{ao}^{\prime }\) for all \(o\in O,\)and \(y_{co}=y_{co}^{\prime }\)for \(c\in A\setminus \left\{ a,b\right\}\). Then, \(y\in Y\) implies \(y^{\prime }\in Y\).

Assumption 2 means that if two agents are equals, then the feasibility of an assignment is unchanged even if their assignments are exchanged. That is, in this paper, equals are assumed to be equals also with respect to the constraints. This assumption is also adopted in Balbuzanov (2022).

As an illustrative example, we consider the Japanese day-care matching market (Okumura, 2019). An assignment may become infeasible if an older child is replaced by an infant, due to differences in staffing requirements and space allocation. Accordingly, in such markets, two agents of different ages may belong to different groups of equals even if their preference orders are identical.

By Assumptions 1 and 2, agents are regarded as equals only if they have identical preferences and face identical constraints. However, in contrast to the definition of Balbuzanov (2022), we allow that agents with identical preferences and constraints are not equals.

Section 6 discusses which characteristics should be regarded as available, paying particular attention to policy considerations and the potential incentive problems that may arise when assignment decisions rely on personal characteristics.

Next, we consider a (probabilistic) assignment, which is represented by a lottery over \(Y\) denoted by \(\sigma :Y\rightarrow \left[ 0,1\right]\), such that \[\sum\limits_{y\in Y}\sigma \left( y\right) =1\text{,}\]where \(\sigma \left( y\right)\) represents the probability that pure assignment \(y\) is realized. Let \(\Sigma\) be the set of all possible lotteries over \(Y\). That is, we focus on assignments that are implementable as a lottery over feasible pure assignments. Moreover, let \[\mathrm{Supp}(\sigma )=\left\{ y\in Y\text{ }\left\vert \text{ }\sigma \left( y\right) >0\right. \right\}\]be the support of \(\sigma\). For notational simplicity, when \(\sigma \left( y\right) =1\), we write \(y\left( =\sigma \right)\) as the assignment.

Kesten et al. (2017) also represent assignments as probability distributions over pure assignments and point out several advantages of this approach. In their terminology, the mechanism we consider is a lottery mechanism.

An assignment \(\sigma\) is said to be ex-post efficient (EE) if any \(y\in \mathrm{Supp}(\sigma )\) is efficient. In the subsequent section, we consider two other efficiency notions, both of which are stronger than ex-post efficiency.

Let \(\mathbf{x}\) be a random variable where \(\mathbf{x}=x\in X\) with probability \(\Pr \left( x;\mathbf{x}\right)\). Let \(\mathbf{x}\left( \sigma \right) _{a}\) be a random variable representing the individual assignment of \(a\) under \(\sigma\); that is, \[\Pr \left( x;\mathbf{x}\left( \sigma \right) _{a}\right) =\sum\limits_{y:\text{ }y_{a}=x}\sigma \left( y\right) \text{.}\]

We consider stochastic dominance relations of these random variables. For \(a\in A,\) let \(\left\{ x^{1},x^{2},\cdots ,x^{\left\vert X\right\vert }\right\} =X\) be such that \(x^{i}\succ _{a}x^{i+1}\) for all \(i=1,2,\cdots ,\left\vert X\right\vert -1\). Let\[F_{a}\left( x,\mathbf{x}\right) =\sum\limits_{i=i^{\prime }+1}^{\left\vert X\right\vert }\Pr \left( x^{i};\mathbf{x}\right) ,\text{ where }x=x^{i^{\prime }}\text{ }\]represent the probability that the pure assignment of \(a\) is less preferable than \(x\) under \(\mathbf{x}\). Let \[\bar{F}_{a}\left( x,\mathbf{x}\right) =1-F_{a}\left( x,\mathbf{x}\right) ,\]which represents the probability that the pure assignment of \(a\) is more preferable than or is equal to \(x\) under \(\mathbf{x}\). Then, a random variable \(\mathbf{x}\) is first-order stochastically dominated by \(\mathbf{x}^{\prime }\) for agent \(a\)if \[\bar{F}_{a}\left( x^{i},\mathbf{x}^{\prime }\right) \geq \bar{F}_{a}\left( x^{i},\mathbf{x}\right)\]for all \(i=1,2,\cdots ,\left\vert X\right\vert\). Moreover, \(\mathbf{x}\) is strictly first-order stochastically dominated by \(\mathbf{x}^{\prime }\) for agent \(a\)if \(\mathbf{x}\) is first-order stochastically dominatedby \(\mathbf{x}^{\prime }\) for agent \(a\)and \(\mathbf{x\neq x}^{\prime }\).

These concepts differ from those in Kojima (2009) and Balbuzanov (2022). In their models, probabilistic assignments are represented as matrices of expected numbers of objects, because agents’ preferences depend only on the expected number of each object.⁷ In order to ensure that probabilistic assignments can be represented in this way, they generalize the Birkhoff–von Neumann theorem. By contrast, our approach does not rely on such a representation.

To illustrate how restrictive it is to focus only on the expected number of each object, consider the following example.

Example 1↩︎

Let \[\begin{align} y_{a} &=&\left( y_{ao_{1}},y_{ao_{2}},y_{ao_{3}}\right) =(1,1,0), \\ y_{a}^{\prime } &=&(0,1,1),y_{a}^{\prime \prime }=(0,0,1),y_{a}^{\prime \prime \prime }=(1,0,0). \end{align}\]First, suppose that \(o_{1}\) and \(o_{2}\) are substitutes and \(o_{3}\) is an independent good. Let the preference ordering be given by \(x^{1}=y_{a}^{\prime },\) \(x^{2}=y_{a},\) \(x^{3}=y_{a}^{\prime \prime \prime }\) and \(x^{4}=y_{a}^{\prime \prime }\) (\(x^{i}\succ _{a}x^{i+1}\) for all \(i=1,2,3\)). Second, suppose that \(o_{1}\) and \(o_{2}\) are complements and \(o_{3}\) is an independent good. In this case, we let the preference ordering be given by \(x^{1}=y_{a},\) \(x^{2}=y_{a}^{\prime },\) \(x^{3}=y_{a}^{\prime \prime }\) and \(x^{4}=y_{a}^{\prime \prime \prime }\).

Let \(\sigma\) and \(\sigma ^{\prime }\) where \(\sigma \left( y\right) =\sigma \left( y^{\prime \prime }\right) =0.5\) and \(\sigma ^{\prime }\left( y^{\prime }\right) =\sigma ^{\prime }\left( y^{\prime \prime \prime }\right) =0.5\). Then, \[\begin{align} \sigma \left( y\right) \times (1,1,0)+\sigma \left( y^{\prime \prime }\right) \times (0,0,1) &=& \\ \sigma \left( y^{\prime \prime }\right) \times (0,1,1)+\sigma \left( y^{\prime \prime \prime }\right) \times (1,0,0) &=&\left( 0.5,0.5,0.5\right) ; \end{align}\]that is, the expected number of each object assigned to \(a\) is identical between two assignments \(\sigma\) and \(\sigma ^{\prime }\). However, by our definition, in the first case, \(\mathbf{x}\left( \sigma \right) _{a}\) is strictly first-order stochastically dominated by \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\)for agent \(a\), and in the second case, \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\) is strictly first-order stochastically dominated by \(\mathbf{x}\left( \sigma \right) _{a}\)for agent \(a\). Thus, evaluating assignments solely based on the expected number of each object assigned in multi-unit demand models is restrictive.

We say that an assignment \(\sigma\) satisfies equal treatment of equals (hereafter ETE) if for any two agents \(a\) and \(b\) belonging to the same group of equals, \(\mathbf{x}\left( \sigma \right) _{a}=\mathbf{x}\left( \sigma \right) _{b}\) meaning that \(\mathbf{x}\left( \sigma \right) _{b}\) and \(\mathbf{x}\left( \sigma \right) _{b}\) have the same distribution.

We now define the ETE reassignment, a procedure for deriving an assignment that satisfies ETE from a given initial assignment. First, we briefly illustrate the ETE reassignment of \(\sigma\) considering a simple case where \(\sigma =y\) is a pure assignment. Let \(A_{n}=\left\{ a_{i},\cdots ,a_{i+j}\right\}\) be agents who are equals, where \(j\geq 1\). Then, the individual assignments of them \(y_{a_{i}},\cdots ,y_{a_{i+j}}\) may differ from one another. In the ETE reassignment of \(\sigma =y\), these individual assignments are pooled and then redistributed among them, so that each agent receives each of these assignments with equal probability \(1/\left( j+1\right)\).

Formally, let \(\pi :A\rightarrow A\) be a bijection satisfying \(\pi \left( a\right) =b\) implies \(a,b\in A_{n}\) for some \(n=1,\cdots ,N\). Let \(\pi ^{1},\pi ^{2},\cdots ,\pi ^{L}\) be distinct possible such bijections where \[L=\left\vert A_{1}\right\vert !\times \cdots \times \left\vert A_{N}\right\vert !.\]Moreover, let \[L_{-n}=\left\vert A_{1}\right\vert !\times \cdots \times \left\vert A_{n-1}\right\vert !\times \left\vert A_{n+1}\right\vert !\times \cdots \times \left\vert A_{N}\right\vert !.\]Fix an arbitrary \(y\in Y\). We let for \(l=1,\cdots ,L\), \(y^{l}\) be such that \(y_{\pi ^{l}(a)o}^{l}=y_{ao}\) for all \(a\in A\) and \(o\in O\). We let \(Y_{D}\left( y\right) =\left\{ y^{1},\cdots ,y^{L}\right\}\) and say that each element of \(Y_{D}\left( y\right)\) is derived from \(y\). Note that any \(y\) is derived from itself. By Assumption 2, every assignment that is derived from any feasible assignment is also feasible.

Let \(\sigma _{y}\) be the expected assignment such that \[\begin{align} \sigma _{y}\left( y^{\prime }\right) &=&\frac{1}{L}\text{ if }y^{\prime }\in Y_{D}\left( y\right) , \\ \sigma _{y}\left( y^{\prime }\right) &=&0\text{ if }y^{\prime }\in Y\setminus Y_{D}\left( y\right) . \end{align}\]Note that since \(y\) is derived from itself, \(\sigma _{y}\left( y\right) =1/L\).

For a given expected assignment \(\sigma\), we say that a probabilistic assignment \(\sigma ^{\prime }\) is the ETE reassignment of \(\sigma\) if for each \(y^{\prime }\in Y\),

\[\sigma ^{\prime }\left( y^{\prime }\right) =\sum\limits_{y\in Y}\sigma \left( y\right) \times \sigma _{y}\left( y^{\prime }\right) .\]

We introduce an example to understand the ETE reassignment.

Example 2↩︎

Let\[\begin{align} y& =\left( \begin{array}{ccccc} y_{a_{1}o_{1}} & y_{a_{1}o_{2}} & y_{a_{1}o_{3}} & y_{a_{1}o_{4}} & y_{a_{1}o_{5}} \\ y_{a_{2}o_{1}} & y_{a_{2}o_{2}} & y_{a_{2}o_{3}} & y_{a_{2}o_{4}} & y_{a_{2}o_{5}} \\ y_{a_{3}o_{1}} & y_{a_{3}o_{2}} & y_{a_{3}o_{3}} & y_{a_{3}o_{4}} & y_{a_{3}o_{5}} \\ y_{a_{4}o_{1}} & y_{a_{4}o_{2}} & y_{a_{4}o_{3}} & y_{a_{4}o_{4}} & y_{a_{4}o_{5}} \\ y_{a_{5}o_{1}} & y_{a_{5}o_{2}} & y_{a_{5}o_{3}} & y_{a_{5}o_{4}} & y_{a_{5}o_{5}}\end{array}\right) =\left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) , \\ y^{\prime }& =\left( \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) . \end{align}\]We assume that \(y\) and \(y^{\prime }\) are feasible. Let \(\sigma\) be such that \(\sigma \left( y\right) =1/3,\) and \(\sigma \left( y^{\prime }\right) =2/3\). Now, suppose that \(A_{1}=\left\{ a_{1},a_{2}\right\}\), \(A_{2}=\left\{ a_{3},a_{4}\right\}\) and \(A_{3}=\left\{ a_{5}\right\}\). Let \(y^{1},\cdots ,y^{4}\) and \(y^{\prime 1},\cdots ,y^{\prime 4}\) be pure assignments derived from \(y\) and \(y^{\prime }\) respectively, where\[\begin{align} y^{1}& =\left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) ,y^{2}=\left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) ,y^{3}=\left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) \\ y^{4}& =\left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) ,y^{\prime 1}=\left( \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) ,y^{\prime 2}=\left( \begin{array}{ccccc} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) , \\ y^{\prime 3}& =\left( \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) ,y^{\prime 4}=\left( \begin{array}{ccccc} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) . \end{align}\]If \(\sigma ^{\prime }\) is the ETE reassignment of \(\sigma\), then\[\begin{align} \sigma ^{\prime }\left( \bar{y}\right) &=&\frac{1}{12}\text{ where }\bar{y}\in Y_{D}\left( y\right) =\left\{ y^{1},\cdots ,y^{4}\right\} , \\ \sigma ^{\prime }\left( \bar{y}^{\prime }\right) &=&\frac{1}{6}\text{ where }\bar{y}^{\prime }\in Y_{D}\left( y^{\prime }\right) =\left\{ y^{\prime 1},\cdots ,y^{\prime 4}\right\} . \end{align}\]Under \(\sigma ^{\prime }\), objects \(o_{1},o_{2},o_{3}\) and \(o_{4}\) are assigned to \(a_{1}\) and \(a_{2}\) with probability \(1/6\), \(1/6,\) \(1/3\) and \(1/3,\) respectively. Moreover, \(o_{1},o_{2},o_{3}\) and \(o_{4}\) are assigned to \(a_{3}\) and \(a_{4}\) with probability \(1/3\), \(1/3,\) \(1/6\) and \(1/6,\) respectively. Thus, \(\sigma ^{\prime }\) satisfies ETE.

We have the following result.

Proof. Fix an arbitrary probabilistic assignment \(\sigma\) and an arbitrary assignment for one agent\(\;x\in X\). Moreover, we consider \(A_{n}\).

Let \(\bar{Y}\) be the set of pure assignments satisfying for any \(y\in \bar{Y}\), \(y_{a}=x\) for some \(a\in A_{n}\). First, if \(\bar{Y}=\emptyset\), then \(\Pr \left( x;\mathbf{x}\left( \sigma \right) _{a}\right) =0\) and \(\Pr \left( x;\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\right) =0\) for all \(a\in A_{n}\). Therefore, we have (?? ) in the case where \(\bar{Y}=\emptyset\).

Second, suppose \(\bar{Y}\neq \emptyset\) and let \(y\in \bar{Y}\). Let \(\bar{n}:\bar{Y}\rightarrow \left\{ 1,\cdots ,\left\vert A_{n}\right\vert \right\}\) where \(\bar{n}\left( y\right)\) represents the number of agents in \(A_{n}\) who obtains \(x\) at \(y\in \bar{Y}\). We consider \(Y_{D}\left( y\right)\). Then, for each agent in \(A_{n}\) denoted by \(b\), there are \(L_{-n}\times \bar{n}\left( y\right) \times \left( \left\vert A_{n}\right\vert -1\right) !\) pure assignments in \(Y_{D}\left( y\right)\) where \(b\) obtains \(x\). This follows because one chooses which of the \(\bar{n}\left( y\right)\) agents receiving \(x\) is assigned to \(b\), permutes the remaining \(\left\vert A_{n}\right\vert -1\) agents in the group, and combines this with all permutations of agents in the other groups.

Therefore, for each \(a\in A_{n}\), if \(\bar{Y}\neq \emptyset\), then\[\begin{align} \Pr \left( x;\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\right) &=&\sum\limits_{y\in \bar{Y}}\sigma \left( y\right) \frac{L_{-n}\times \bar{n}\left( y\right) \times \left( \left\vert A_{n}\right\vert -1\right) !}{L} \\ &=&\sum\limits_{y\in \bar{Y}}\sigma \left( y\right) \frac{\bar{n}\left( y\right) }{\left\vert A_{n}\right\vert }=\frac{1}{\left\vert A_{n}\right\vert }\sum\limits_{b\in A_{n}}\Pr \left( x;\mathbf{x}\left( \sigma \right) _{b}\right) . \end{align}\]Q.E.D.

By Lemma 1, we immediately have the following result.

Next, Lemma 1 also yields a very simple way to derive the ETE reassignment. Since \(L\) can be extremely large, the ETE reassignment may at first appear to be complicated. However, by Lemma 1, the ETE reassignment of any \(\sigma \in \Sigma\) can be obtained through the following simple procedure. First, a pure assignment \(y\) is realized according to the probability distribution \(\sigma\). Second, for each group of equals in the realized assignment \(y\), we pool the assignments received by the members of the group under \(y\), construct a lottery that assigns these assignments to the members with equal probability, and then reallocate them accordingly.

Next, we consider the ETE reassignment of an EE assignment.

Proof. Let \(y\in \mathrm{Supp}(\sigma )\) be an efficient pure assignment. Let \(y^{l}\) be an arbitrary assignment derived from \(y\), where \(\pi ^{l}\) is the permutation used to construct \(y^{l}\) from \(y\). We show that \(y^{l}\) is also efficient. Suppose not; that is, \(y^{l}\) is Pareto dominated by a feasible assignment \(y^{\prime }\). Let \(y^{\prime \prime }\) be such that \(y_{ao}^{\prime \prime }=y_{\pi ^{l}(a)o}^{\prime }\) for all \(a\in A\). Then, by Assumption 2, \(y^{\prime \prime }\) is feasible and Pareto dominates \(y\). However, these facts contradict that \(y\) is efficient. Q.E.D.

By Propositions 1 and 2, the ETE reassignment of an EE assignment satisfies both EE and ETE. Once an EE assignment is available, obtaining an assignment that satisfies both EE and ETE is straightforward. In the subsequent section, we focus on two efficiency notions that are stronger than EE.

Next, we consider the case where the affirmative action policy is adopted. For example, suppose that an affirmative action policy is implemented such that each agent in \(A_{n}\) has a characteristic that justifies preferential treatment under the affirmative action policy, but each agent in \(A_{m}\) does not. Note that we allow agents in \(A_{n}\) and those in \(A_{m}\) to have identical preferences.

Proof. Fix an agent \(a\) andlet \(\left\{ x^{1},x^{2},\cdots ,x^{\left\vert X\right\vert }\right\} =X\) be such that \(x^{i}\succ _{a}x^{i+1}\) for all \(i=1,2,\cdots ,\left\vert X\right\vert -1\). Then, for all \(a\in A_{n}\), all \(b\in A_{m}\), all \(i=1,2,\cdots ,\left\vert X\right\vert\), \[\bar{F}_{a}\left( x^{i},\mathbf{x}\left( \sigma \right) _{a}\right) \geq \bar{F}_{a}\left( x^{i},\mathbf{x}\left( \sigma \right) _{b}\right) ,\]and for some \(a^{\prime }\in A_{n}\), some \(b^{\prime }\in A_{m},\) and some \(j=1,2,\cdots ,\left\vert X\right\vert\),\[\bar{F}_{a}\left( x^{j},\mathbf{x}\left( \sigma \right) _{a^{\prime }}\right) >\bar{F}_{a}\left( x^{j},\mathbf{x}\left( \sigma \right) _{b^{\prime }}\right) .\]By (?? ), \[\begin{align} \Pr \left( x;\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\right) &=&\frac{1}{\left\vert A_{n}\right\vert }\sum\limits_{\hat{a}\in A_{n}}\Pr \left( x;\mathbf{x}\left( \sigma \right) _{\hat{a}}\right) , \\ \Pr \left( x;\mathbf{x}\left( \sigma ^{\prime }\right) _{b}\right) &=&\frac{1}{\left\vert A_{m}\right\vert }\sum\limits_{\hat{b}\in A_{m}}\Pr \left( x;\mathbf{x}\left( \sigma \right) _{\hat{b}}\right) . \end{align}\]Therefore, for all \(a\in A_{n}\), all \(b\in A_{m}\), all \(i=1,2,\cdots ,\left\vert X\right\vert\),\[\bar{F}_{a}\left( x^{i},\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\right) \geq \bar{F}_{a}\left( x^{i},\mathbf{x}\left( \sigma ^{\prime }\right) _{b}\right) .\]Moreover, since the strict inequality holds for some pair \(\left( a^{\prime },b^{\prime }\right) ,\) averaging preserves strictness, so\[\bar{F}_{a}\left( x^{j},\mathbf{x}\left( \sigma ^{\prime }\right) _{a^{\prime }}\right) >\bar{F}_{a}\left( x^{j},\mathbf{x}\left( \sigma ^{\prime }\right) _{b^{\prime }}\right) .\]Therefore, for all \(a\in A_{n}\) and \(b\in A_{m}\), \(\mathbf{x}\left( \sigma ^{\prime }\right) _{b}\) is strictly first-order stochastically dominated by \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\) for \(a\). Q.E.D.

We consider an assignment \(\sigma\) such that agents in \(A_{n}\) receive preferential treatment compared to those in \(A_{m}\). Then, this property is preserved in the ETE reassignment of \(\sigma\). Thus, the ETE reassignment allows us to obtain an assignment that satisfies ETE while maintaining preferential treatment for agents possessing specific characteristics even if they have identical preferences. Note that this does not happen when we simply treat agents with identical preferences as equals, as defined in previous studies.

4 Ordinal Efficiency and Rank-minimizing↩︎

In this section, we focus on two efficiency notions that are stronger than EE. First, an assignment \(\sigma\) is said to be ordinally dominated by \(\sigma ^{\prime }\) if \(\mathbf{x}\left( \sigma \right) _{a}\) first-order stochastically dominated by \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\) for all \(a\in A\) and the former strictly first-order stochastically dominated by the latter for some \(a\in A\). An assignment is said to be ordinally efficient (OE) if it is not ordinally dominated by any other assignment. Note that a pure assignment is OE if and only if it is efficient.

First, we have the following result.

Proof. Suppose not; that is, \(\sigma\) is OE but \(\sigma ^{\ast }=y\) is not. Then, there is an assignment \(\sigma ^{\ast \ast }\) that ordinally dominates \(\sigma ^{\ast }=y\). Since \[\sum\limits_{\hat{y}\in Y}\sigma ^{\ast \ast }\left( \hat{y}\right) =1\text{ and }\sum\limits_{\hat{y}\in Y}\sigma \left( \hat{y}\right) =1,\]we have \[\sigma \left( y\right) \times \sum\limits_{\hat{y}\in Y}\sigma ^{\ast \ast }\left( \hat{y}\right) +\sum_{y^{\prime }\in Y\setminus \left\{ y\right\} }\sigma \left( y^{\prime }\right) =1.\]Define an assignment \(\sigma ^{\ast \ast \ast }\) by\[\begin{gather} \sigma ^{\ast \ast \ast }\left( y\right) =\sigma \left( y\right) \times \sigma ^{\ast \ast }\left( y\right) \\ \sigma ^{\ast \ast \ast }\left( y^{\prime }\right) =\sigma \left( y\right) \times \sigma ^{\ast \ast }\left( y^{\prime }\right) +\sigma \left( y^{\prime }\right) , \end{gather}\]for all \(y^{\prime }\in Y\setminus \left\{ y\right\}\). Then, \(\sigma ^{\ast \ast \ast }\) is a valid assignment. Since \(\sigma ^{\ast \ast }\) ordinally dominates \(\sigma ^{\ast }=y\) and \(\sigma \left( y\right) >0\), \(\sigma ^{\ast \ast \ast }\) ordinally dominates \(\sigma\). However, this contradicts that \(\sigma\) is OE. Q.E.D.

In this study, we represent an assignment as a lottery over pure assignments. Lemma 2 means that if a lottery over pure assignments is OE, then each of the pure assignments is also OE. This immediately implies the following fact.

4.1 Unit demand and simple capacity constraint↩︎

Contrary to Lemma 2, Bogomolnaia and Moulin (2001) show that, even under unit demand and simple capacity constraints, an assignment may fail to be OE although all pure assignments in its support are OE. Nevertheless, as shown below, while the ETE reassignment of an OE assignment need not be OE in general, it is always OE in this simple setting.

This result follows from Theorem 1 in Okumura (2026b). Okumura (2026b) considers a model in which objects, called schools in his terminology, have priority orders over agents, called students in his terminology, and shows that the ETE reassignment of a constrained efficient assignment is an ex ante stable lottery that is not ordinally dominated by any other ex ante stable lottery. If \(Y\) satisfies the unit demand and simple capacity constraints, then the model considered in this paper corresponds to the special case of his model in which all priority orders are complete indifferences. In this case, every feasible assignment is ex ante stable, and constrained efficiency coincides with ordinal efficiency. Hence, the ETE reassignment of an OE assignment is also OE.

However, Proposition 3 cannot be generalized; that is, the ETE reassignment of an OE assignment may fail to be OE in general case. We provide the following example.

Example 3↩︎

Let \(A=\left\{ a_{1},\cdots ,a_{4}\right\}\), \(O=\left\{ o_{1},\cdots ,o_{4}\right\}\), and all agents are equals in this example. Here, we assume that \(Y\) satisfiessingle-unit demand. Moreover, suppose \[\succ _{a}:o_{1},o_{2},o_{3},o_{4}\]for all \(a\in A\).⁸ Let\[\begin{align} y &=&\left( \begin{array}{cccc} y_{a_{1}o_{1}} & y_{a_{1}o_{2}} & y_{a_{1}o_{3}} & y_{a_{1}o_{4}} \\ y_{a_{2}o_{1}} & y_{a_{2}o_{2}} & y_{a_{2}o_{3}} & y_{a_{2}o_{4}} \\ y_{a_{3}o_{1}} & y_{a_{3}o_{2}} & y_{a_{3}o_{3}} & y_{a_{3}o_{4}} \\ y_{a_{4}o_{1}} & y_{a_{4}o_{2}} & y_{a_{4}o_{3}} & y_{a_{4}o_{4}}\end{array}\right) =\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{array}\right) , \\ y^{\prime } &=&\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1\end{array}\right) ,y^{\prime \prime }=\left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0\end{array}\right) . \end{align}\]We assume that a pure assignment is feasible if and only if it is derived from \(y,\) \(y^{\prime }\) or \(y^{\prime \prime }\). Then, \(\sigma =y\) is an OE assignment.

Let \(\sigma ^{\prime }\) be an ETE reassignment of \(\sigma =y\), which is given by \[\Pr \left( o_{i};\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\right) =\frac{1}{4}\]for all \(i=1,\cdots ,4\) and all \(a\in A\).

Let\[y^{1}=\left( \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\end{array}\right) ,y^{2}=\left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0\end{array}\right) ,\]which are derived from \(y\) and thus feasible. Define \(\sigma ^{\prime \prime }\) by \[\sigma ^{\prime \prime }\left( y^{\prime }\right) =\sigma ^{\prime \prime }\left( y^{\prime \prime }\right) =\sigma ^{\prime \prime }\left( y^{1}\right) =\sigma ^{\prime \prime }\left( y^{2}\right) =\frac{1}{4}.\]Then, for all \(a\in \left\{ a_{1},a_{4}\right\}\),\[\begin{align} \Pr \left( o_{1};\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\right) &=&\Pr \left( o_{4};\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\right) =\frac{1}{4}, \\ \Pr \left( o_{2};\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\right) &=&\frac{1}{2},\Pr \left( o_{3};\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\right) =0, \end{align}\]and for all \(a^{\prime }\in \left\{ a_{2},a_{3}\right\}\) and all \(i=1,\cdots ,4\), \[\Pr \left( o_{i};\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a^{\prime }}\right) =\frac{1}{4}.\]

Then, since \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\) is first-order stochastically dominated by \(\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\) for all \(a\in A\), with strict inequality for \(a_{1}\) and \(a_{4}\), \(\sigma ^{\prime }\) is not OE, even though it is the ETE reassignment of an OE assignment.

Thus, there may exist some OE assignment whose ETE reassignment is not OE. In the next subsection, we show that there exists an OE assignment whose ETE reassignment is also OE.

4.2 General existence result↩︎

Here, we consider whether there exists an OE assignment whose ETE reassignment is also OE. To address this question, we introduce a stronger notion of efficiency than OE.

For each \(a\in A\), let \[r\left( x;a\right) =\left\vert \left\{ x^{\prime }\in X\text{ }\left\vert \text{ }x^{\prime }\succ _{a}x\right. \right\} \right\vert +1,\]which represents the rank position of \(x\) in the preference order of \(a\). Note that \(\bar{F}_{a}\left( x,\mathbf{x}\right)\) represents the probability that the rank of the object assigned to \(a\) is \(r\left( x;a\right)\) or better. Let \(R:\Sigma \rightarrow \mathbb{R}\) be defined by\[R\left( \sigma \right) =\sum\limits_{y\in Y}\sigma \left( y\right) \sum\limits_{a\in A}r\left( y_{a};a\right) ,\]which is the expected value of the sum of rank positions of the assignment in the preference orders of all agents. We say that \(\sigma \in \Sigma\) is rank-minimizing efficient (RE) if \(R\left( \sigma \right) \leq R\left( \sigma ^{\prime }\right)\) for all \(\sigma ^{\prime }\in \Sigma\).

Featherstone (2020) shows that there exist RE assignments and each of them is OE in the unit-demand case with simple capacity constraints.⁹ We generalize the result.

Proof. Since \(\Sigma\) is compact \(R\) is continuous on \(\Sigma\), the existence of some RE assignments is trivial. We show that each of them is OE. Let \(\sigma \in \Sigma\) be an RE assignment. Suppose not; that is, there is \(\sigma ^{\prime }\in \Sigma\) such that \(\mathbf{x}\left( \sigma \right) _{a}\) is first-order stochastically dominated by \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\) for all \(a,\) and \(\mathbf{x}\left( \sigma \right) _{a^{\prime }}\) is strictly first-order stochastically dominated by \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a^{\prime }}\) for some \(a^{\prime }\). Then, since \(\mathbf{x}\left( \sigma \right) _{a}\) is first-order stochastically dominated by \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\) for all \(a\), \[\sum\limits_{y\in Y}\sigma \left( y\right) r\left( y_{a};a\right) \geq \sum\limits_{y\in Y}\sigma ^{\prime }\left( y\right) r\left( y_{a};a\right) .\]Moreover, since the dominance is strict for \(a^{\prime }\), \[\sum\limits_{y\in Y}\sigma \left( y\right) r\left( y_{a^{\prime }};a^{\prime }\right) >\sum\limits_{y\in Y}\sigma ^{\prime }\left( y\right) r\left( y_{a^{\prime }};a^{\prime }\right) .\]Thus,\[R\left( \sigma \right) =\sum\limits_{a\in A}\sum\limits_{y\in Y}\sigma \left( y\right) r\left( y_{a};a\right) >\sum\limits_{a\in A}\sum\limits_{y\in Y}\sigma ^{\prime }\left( y\right) r\left( y_{a};a\right) =R\left( \sigma ^{\prime }\right) ,\]which contradicts that \(\sigma\) is RE. Q.E.D.

Thus, there always exists an RE assignment that must be OE. As a further advantage of this efficiency notion, we have the following result.

Proof. We show that the ETE reassignment of an RE assignment must be RE. To show this result, we prove the following result.

Proof. We arbitrarily choose \(y\in \mathrm{Supp}\left( \sigma \right)\), where \(\sigma\) is an RE assignment. First, we show that the pure assignment \(\sigma ^{\prime }=y\) is also an RE assignment.

Suppose not; that is,

\[R\left( \sigma \right) =\sum\limits_{y\in Y}\sigma \left( y\right) \sum\limits_{a\in A}r\left( y_{a};a\right) <\sum\limits_{a\in A}r\left( y_{a};a\right) \text{.}\]Then, since \(\sigma \left( y\right) >0\), there must exist \(y^{\prime }\in \mathrm{Supp}\left( \sigma \right)\) such that \[\sum\limits_{a\in A}r\left( y_{a}^{\prime };a\right) <\sum\limits_{y\in Y}\sigma \left( y\right) \sum\limits_{a\in A}r\left( y_{a};a\right) ,\]which contradicts that \(\sigma\) is an RE assignment. Therefore, \[R\left( \sigma \right) =\sum\limits_{a\in A}r\left( y_{a};a\right) , \label{a}\tag{1}\] for all \(y\in \mathrm{Supp}\left( \sigma \right)\); that is, \(\sigma ^{\prime }=y\) is also an RE assignment.

Next, let be \(\left\{ y^{1},y^{2},\cdots ,y^{n}\right\} =\mathrm{Supp}\left( \sigma \right)\) such that any of them is RE. Then, we can let \[R^{\ast }=\sum\limits_{a\in A}r\left( y_{a}^{1};a\right) =\cdots =\sum\limits_{a\in A}r\left( y_{a}^{n};a\right) ,\]for some constant \(R^{\ast }\). Hence\[R\left( \sigma \right) =\sum\limits_{y\in Y}\sigma \left( y\right) R^{\ast }=R^{\ast }\text{,}\]and thus \(\sigma\) is RE. Q.E.D.

We now prove the first claim of the theorem. Let \(\sigma\) be an RE assignment and\(\;y\in \mathrm{Supp}\left( \sigma \right)\). By Lemma 5, \[R\left( \sigma \right) =\sum\limits_{a\in A}r\left( y_{a};a\right) .\]By construction, for any \(y^{\prime }\in Y_{D}\left( y\right)\), \[\sum\limits_{a\in A}r\left( y_{a}^{\prime };a\right) =\sum\limits_{a\in A}r\left( y_{a};a\right) .\]Hence, every pure assignment in the support of the ETE reassignment of \(\sigma\) attains the same total rank. By Lemma 5, the ETE reassignment of \(\sigma\) is also RE. Thus, we have the first sentence of Theorem 1.

By Lemma 4, there must exist an RE assignment \(\sigma\). Let \(\sigma ^{\prime }\) be the ETE reassignment of \(\sigma\). By Proposition 1 and the first sentence, \(\sigma ^{\prime }\) satisfies ETE and RE. Moreover, by Lemma 4, \(\sigma ^{\prime }\) also satisfies OE. Q.E.D.

By Theorem 1, there exists an assignment that satisfies both ETE and OE. In Example 3, \(\sigma =y^{\prime \prime }\) is an RE assignment and satisfies ETE. Moreover, obviously \(\sigma =y^{\prime \prime }\) is OE.

As stated above, \(Y\) can be taken as the set of matchings that are stable in the ex-post sense with the priority orders of objects. In this case, Theorem 1 establishes the existence of an ETE assignment whose total rank is no greater than that of any other stable matching. However, due to Assumption 2, this implicitly assumes that the priority orders among equals are tied.¹⁰

In what follows, we examine whether such an assignment can be derived in a computationally efficient manner. First, in the case with unit-demand and simple capacity constraints, an RE assignment can be computed efficiently (see, for example, Korte and Vygen 2005, Ch. 11). Since an ETE reassignment for a given assignment can be performed in polynomial time, we can obtain an RE assignment that satisfies ETE in a computationally efficient way in this specific case.

As noted above, the literature has introduced the uniform RE mechanism, which implements all RE assignments with equal probability. However, as pointed out by Troyan (2024), finding all RE assignments is computationally infeasible even in the unit-demand setting with simple capacity constraints, which raises a concern from the perspective of computational complexity. In contrast, our method derives an assignment satisfying both ETE and RE in a computationally efficient manner in this setting.

However, in more general settings, no computationally efficient method is known for deriving an assignment that satisfies both ETE and RE (or more weakly OE). Although, as is clear from Lemma 1, the ETE reassignment of any assignment can be easily executed, a computationally efficient method for finding an RE assignment remains unknown in the general case. Therefore, in the next subsection, we propose a method for deriving an assignment that satisfies both ETE and OE in a more general setting.

4.3 General upper bounds↩︎

Here, we introduce a computationally efficient method for deriving a pure assignment whose ETE reassignment is OE under fairly general constraints. Specifically, we consider the case in which \(Y\) satisfies the following conditions.

The set of feasible pure assignments \(Y\) satisfies the general upper bounds constraint if for any \(y\in Y,\) any \(y^{\prime }\in \mathbb{Z}_{+}^{\left\vert A\right\vert \times \left\vert O\right\vert }\) such that \(0\leq y_{ao}^{\prime }\leq y_{ao}\) for all \(\left( a,o\right) \in \left( A\times O\right)\) also belongs to \(Y\).

We introduce a specific version of this constraint. For each \(o\in O\), let \(Z_{o}\subseteq \mathbb{Z}\) denote the set of feasible assignments for \(o\). We say that \(Z_{o}\) satisfies the general upper bounds constraint for \(o\)if, for any \(z\in Z_{o},\) any \(z^{\prime }\in \mathbb{Z}_{+}^{\left\vert A\right\vert }\) satisfying \(z_{a}^{\prime }\leq z_{a}\) also belongs to \(Z_{o}\). We say that the set of feasible pure assignments \(Y\) satisfies the general upper bounds constraint for each object, if for every \(o\in O\), the set \(Z_{o}\subseteq \mathbb{Z}_{+}^{\left\vert A\right\vert }\) satisfies the general upper bounds constraint for\(o\), and any \(y\in \mathbb{Z}_{+}^{\left\vert A\right\vert \times \left\vert O\right\vert }\) such that \(y_{o}\in Z_{o}\) for all \(o\in O\) belongs to \(Y\).

As shown in the example below, the former constraint structure is more general than the latter; that is, if \(Y\) satisfies the general upper bounds constraint for each object, then it also satisfies the general upper bounds constraint.

Okumura (2019) and Kamada and Kojima (2024) consider the set of (pure) assignments satisfying the general upper bounds constraint for each object in the unit-demand case. Imamura and Kawase (2025) also study the set of assignments that satisfy the general upper bounds constraint, though their model is also restricted to the unit-demand case.

We consider the difference of these constraints by introducing an example.

Example 4↩︎

Let \(A=\left\{ a_{1},a_{2}\right\}\) and \(O=\left\{ o_{1},o_{2}\right\}\). Let \[\begin{align} y &=&\left( \begin{array}{cc} y_{a_{1}o_{1}} & y_{a_{1}o_{2}} \\ y_{a_{2}o_{1}} & y_{a_{2}o_{2}}\end{array}\right) =\left( \begin{array}{cc} 1 & 0 \\ 0 & 0\end{array}\right) , \\ y^{\prime } &=&\left( \begin{array}{cc} 0 & 0 \\ 0 & 1\end{array}\right) ,y^{\prime \prime }=\left( \begin{array}{cc} 1 & 0 \\ 0 & 1\end{array}\right) . \end{align}\]Suppose \(y,y^{\prime }\in Y\). If \(Y\) satisfies the general upper bounds constraint for each object, then \(y^{\prime \prime }\in Y\). However, if \(Y\) satisfies only the general upper bounds constraint, then it is possible that \(y^{\prime \prime }\notin Y\).

To illustrate the importance of the general upper bounds constraint, we consider the following examples.

First, as discussed by Kamada and Kojima (2015), regional maximum quotas have been introduced in the Japanese medical residency matching market to mitigate the overconcentration in specific regions. Such regional limitations are incorporated into our model through general upper bound constraints. To see this point, we revisit Example 3. Suppose that \(o_{1}\) and \(o_{2}\) are in the same region, and there is the regional maximum quota; that is, \(y\in Y\) if and only if\[\sum\limits_{a\in A}\left( y_{ao_{1}}+y_{ao_{2}}\right) \leq 1.\]Then, \(y,y^{\prime }\in Y\) but \(y^{\prime \prime }\notin Y\).

Similarly, in order to achieve the same objective of ensuring a certain level of allocation to specific regions, regional minimum quotas can also be introduced. Specifically, suppose that only \(o_{1}\) and \(o_{2}\) belong to the same region, and that this region has a minimum quota of \(n\in \left( 0,\left\vert A\right\vert \right)\). Thus, an assignment \(y\) is feasible if and only if the following condition holds: \[\sum\limits_{a\in A}\left( y_{ao_{1}}+y_{ao_{2}}\right) \geq n. \label{f}\tag{2}\] At first glance, this may appear to be incompatible with general upper bound constraints. However, as pointed out by Balbuzanov (2022), such minimum quota constraints can in fact be reformulated and treated as general upper bound constraints.

Specifically, we assume single-unit demand and that there exists a null object \(o_{0}\in O\), corresponding to the outside option of each agent. Under this formulation, constraint (2 ) is equivalent to \[\sum\limits_{a\in A,o\in O\setminus \left\{ o_{1},o_{2}\right\} }y_{ao}\leq \left\vert A\right\vert -n.\]Therefore, assignment problems with regional minimum quotas are also encompassed by the case where \(Y\) satisfies general upper bound constraints.¹¹ Note that this reformulation relies on the presence of the null object, which absorbs the remaining assignments.

Second, we consider the case where each school may have multiple admission slots with different amounts of scholarship. Suppose that there is one school with a total capacity of 200 students. The school offers three types of admission slots: one with a scholarship of 4,000 USD, denoted by \(o_{1}\); another with a scholarship of 2,000 USD, denoted by \(o_{2}\); and one without any scholarship, denoted by \(o_{3}\). We assume that the school has a total scholarship financial budget of 100,000 USD. Then, \(y\in Y\) if and only if \[\begin{align} \sum_{a\in A}\sum_{o\in \left\{ o_{1},o_{2},o_{3}\right\} }y_{ao} &\leq &200, \\ \sum_{a\in A}y_{ao_{1}}\times 4000+\sum_{a\in A}y_{ao_{2}}\times 2000 &\leq &100,000. \end{align}\]This \(Y\) satisfies the general upper bounds constraint, but does not satisfy the general upper bounds constraint for each object.

Third, we consider a controlled school choice problem. There is also one school with a total capacity of 200 students. Let \(S_{1}\), \(S_{2}\), and \(S_{3}\) be the sets of students (agents in our terminology) from different categories, respectively. Note that the intersection of any two of these three sets may be non-empty. This implies that, as also considered by Kurata et al. (2017), Aygün and Bo (2021), and Sönmez and Yenmez (2022), we allow for cases in which an agent possesses multiple characteristics that justify preferential treatment under affirmative action. As stated by Aygün and Turhan (2017, 2020), students from these categories may have preferences not only over schools but also over the admission categories through which they are accepted, as exemplified by the case of engineering school admissions in India.

Based on the case of engineering school admissions in India, there exist four different slots as below. Let \(o_{1}\), \(o_{2}\), and \(o_{3}\) be reserved slots for students in \(S_{1}\), \(S_{2}\), and \(S_{3},\) respectively. Moreover, let \(o_{4}\) be the open slot that can be assigned to any students. We consider the hard bound constraints; that is, if there are not enough applications for \(o_{i}\), some seats in \(o_{i}\) will remain empty for \(i=1,2,3\).¹² Then, for example, let\[\begin{align} \sum_{a\in S_{1}}y_{ao_{1}}+\sum_{a\in A\setminus S_{1}}y_{ao_{1}}\times \left( \infty \right) &\leq &30, \\ \sum_{a\in S_{2}}y_{ao_{2}}+\sum_{a\in A\setminus S_{2}}y_{ao_{2}}\times \left( \infty \right) &\leq &15, \\ \sum_{a\in S_{3}}y_{ao_{3}}+\sum_{a\in A\setminus S_{3}}y_{ao_{3}}\times \left( \infty \right) &\leq &54, \\ \sum_{a\in A}y_{ao_{4}} &\leq &101, \end{align}\]where \(\infty\) represents a sufficiently large number. This implies that \(30,\) \(15\), and \(54\) seats are preserving for \(S_{1},\) \(S_{2},\) and \(S_{3},\) respectively, and moreover, \(101\) seats are open to all students. Note that students from the categories may be able to choose one from multiple slots.

Even if \(Y\) satisfies the general upper bounds constraint for each object, the ETE reassignment of an OE assignment may not be OE. To illustrate this fact, we provide the following example.¹³

Example 5↩︎

Let \(A=A_{1}\cup A_{2}\) where \(A_{1}=\left\{ a_{1},a_{2},a_{3}\right\}\) and \(A_{2}=\left\{ a_{4},a_{5},a_{6}\right\}\), and \(O=\left\{ o_{1}\right\}\). Suppose that \(y\in Y\) if either (1) \(\sum\nolimits_{a\in A}y_{ao_{1}}\leq 2\) or (2) \(y_{ao_{1}}=0\) for all \(a\in A_{1}\) or all \(a\in A_{2}\). That is, three agents can simultaneously obtain one copy of \(o_{1}\) if and only if they are equals. Since there is only one object type, \(Y\) satisfies the general upper bounds constraint for each object.

Then, let \(y\) be such that \(y_{a_{1}o_{1}}=y_{a_{4}o_{1}}=1\) and \(y_{a_{i}o_{1}}=0\) for all \(i=2,3,5,6\). Then, the ETE reassignment of \(\sigma =y\) denoted by \(\sigma ^{\prime }\) satisfies \[\Pr \left( o_{1};\mathbf{x}\left( \sigma ^{\prime }\right) _{a_{i}}\right) =\frac{1}{3}\]for all \(i=1,\cdots ,6\). On the other hand, let \(\sigma ^{\prime \prime }\) be such that \(\sigma ^{\prime \prime }\left( y^{\prime }\right) =\sigma ^{\prime \prime }\left( y^{\prime \prime }\right) =1/2\) where\[\begin{align} y_{a_{1}o_{1}}^{\prime } &=&y_{a_{2}o_{1}}^{\prime }=y_{a_{3}o_{1}}^{\prime }=1,\text{ }y_{a_{4}o_{1}}^{\prime }=y_{a_{5}o_{1}}^{\prime }=y_{a_{6}o_{1}}^{\prime }=0, \\ y_{a_{1}o_{1}}^{\prime \prime } &=&y_{a_{2}o_{1}}^{\prime \prime }=y_{a_{3}o_{1}}^{\prime \prime }=0,\text{ }y_{a_{4}o_{1}}^{\prime \prime }=y_{a_{5}o_{1}}^{\prime \prime }=y_{a_{6}o_{1}}^{\prime \prime }=1. \end{align}\]Then, \[\Pr \left( o_{1};\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a_{i}}\right) =\frac{1}{2},\]for all \(i=1,\cdots ,6\). Thus, \(\sigma ^{\prime }\) is ordinally dominated by \(\sigma ^{\prime \prime }\) even though \(\sigma ^{\prime }\) is the ETE reassignment of an OE assignment.

Although the ETE reassignment of any OE assignment remains OE under unit demand and simple capacity constraints, Example 5 shows that this property fails under general upper bound constraints; that is, the ETE reassignment of an OE assignment may fail to be OE. Nevertheless, Theorem 1 guarantees that even in such general settings, there exists at least one OE assignment whose ETE reassignment is also OE. In what follows, we propose a computationally efficient method to derive such an assignment under general upper bound constraints.

We introduce the serial dictatorship rules. First, let a priority list \(\alpha =\left( \alpha _{1},\cdots ,\alpha _{\left\vert A\right\vert }\right)\) be a permutation of \(A\). The serial dictatorship rule with priority list \(\alpha\) is as follows:

Step 0

Let \(y^{0}\in Y\) be such that \(y_{ao}^{0}=0\) for all \((a,o)\in A\times O\).

Step \(t=1,\cdots ,\left\vert A\right\vert\)

Let \(y^{t}\in Y\) be such that \(y_{a}^{t}=y_{a}^{t-1}\) for all \(a\in \left( A\setminus \left\{ \alpha _{t}\right\} \right)\), and \[y_{\alpha _{t}}^{t}\in \arg \max_{\succsim _{\alpha _{t}}}\left\{ x\in X_{\alpha _{t}}\left\vert \exists y\in Y\text{ s.t. }y_{\alpha _{t}}=x,\text{ }y_{a}=y_{a}^{t-1}\text{ }\forall a\in A\setminus \left\{ \alpha _{t}\right\} \right. \right\} .\]

We have the following result.

Proof. Let \(\alpha\) be an arbitrary priority list. Suppose not; that is, \(\sigma =y\) is ordinally dominated by some assignment \(\sigma ^{\prime }\). Then, there is \(t\in \left\{ 1,\cdots ,\left\vert A\right\vert \right\}\) such that \[\Pr \left( y_{\alpha _{t^{\prime }}};\mathbf{x}\left( \sigma \right) _{\alpha _{t^{\prime }}}\right) =1=\Pr \left( y_{\alpha _{t^{\prime }}};\mathbf{x}\left( \sigma ^{\prime }\right) _{\alpha _{t^{\prime }}}\right)\]for all \(t^{\prime }=1,2,\cdots ,t-1,\) and \[\Pr \left( y_{\alpha _{t}};\mathbf{x}\left( \sigma \right) _{\alpha _{t}}\right) =1>\Pr \left( y_{\alpha _{t}};\mathbf{x}\left( \sigma ^{\prime }\right) _{\alpha _{t}}\right) .\]That is, there is \(y^{\prime }\in \mathrm{Supp}\left( \sigma ^{\prime }\right)\) such that \(y_{\alpha _{t^{\prime }}}^{\prime }=y_{\alpha _{t^{\prime }}}\) for all \(t^{\prime }=1,2,\cdots ,t-1,\) and \(y_{\alpha _{t}}^{\prime }\succ _{\alpha _{t}}y_{\alpha _{t}}\). Since \(Y\) satisfies the general upper bounds constraint and \(y^{\prime }\) is feasible, \(y^{\prime \prime }\) such that \(y_{\alpha _{t^{\prime }}}^{\prime \prime }=y_{\alpha _{t^{\prime }}},\) \(y_{\alpha _{t}}^{\prime \prime }=y_{\alpha _{t}}^{\prime }\) and \(y_{\alpha _{t^{\prime \prime }}o}^{\prime \prime }=0\) for all \(t^{\prime \prime }=t+1,\cdots ,\left\vert A\right\vert\) and \(o\in O\) is also feasible. This implies that, at step \(t\), agent \(\alpha _{t}\) could have chosen \(y_{\alpha _{t}}^{\prime }\), which they strictly prefer to \(y_{\alpha _{t}}\), while maintaining feasibility. This contradicts the construction of the serial dictatorship rule. Thus, \(\sigma =y\) is OE. Q.E.D.

There may exist some priority list \(\alpha\) such that the ETE reassignment of the result of serial dictatorship rule with \(\alpha\) is not OE. To show this fact, we revisit Example 5. If the priority list \(\alpha\) satisfies \(\alpha _{1}\in A_{1}\) and \(\alpha _{2}\in A_{2}\) (or \(\alpha _{1}\in A_{2}\) and \(\alpha _{2}\in A_{1}\)), then the result of the rule with \(\alpha\) is \(y\) and thus the ETE reassignment of \(y\) is not OE. Otherwise; that is, if the priority list \(\alpha\) satisfies either \(\alpha _{1},\alpha _{2}\in A_{1}\) or \(\alpha _{1},\alpha _{2}\in A_{2}\), then the ETE reassignment of the result of the rule with \(\alpha\) is OE. This observation suggests that the choice of the priority list is crucial for preserving ordinal efficiency under ETE reassignment.

We consider the following specific priority lists. A priority list \(\alpha\) is said to satisfy consecutive equals if, for any\(\;a,b\in A\) with \(a=\alpha _{i}\) and \(b=\alpha _{j}\) are equals and \(j>i\) imply that either \(j=i+1\) or the agents \(\alpha _{i},\alpha _{i+1},\cdots ,\alpha _{j}\) are also equals. We have the following result.

Proof. Let \(\alpha\) be a priority list that satisfies consecutive equals. We index the groups \(A_{1},\cdots ,A_{N}\) along \(\alpha\) so that, whenever \(\alpha _{i}\) \(\in A_{n}\) and \(\alpha _{j}\in A_{m}\), \(n<m\) implies \(i<j\); in particular, \(\alpha _{1}\in A_{1}\) and \(\alpha _{\left\vert A\right\vert }\in A_{N}\). Let \(y\) be the outcome of the serial dictatorship rule with \(\alpha\) and \(\sigma =y\), and \(\sigma ^{\prime }\) be the ETE reassignment of \(\sigma =y\). Moreover, let \(\sigma ^{\prime \prime }\) be an arbitrary assignment such that \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\) is first-order stochastically dominatedfor all \(a\) by \(\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\). To prove this theorem, it suffices to show that for all \(a\in A\), \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a}=\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\).

We first establish the following fact.

Proof of Claim 1. Since \(\alpha\) satisfies consecutive equals, we can write \(A_{n+1}=\left\{ \alpha _{i},\cdots ,\alpha _{i+j}\right\}\) for some \(j\geq 0\). Since the agents in \(A_{n+1}\) have the same preference order by Assumption 1, we have \[y_{\alpha _{i}}\succsim _{a}y_{\alpha _{i+1}}\succsim _{a}\cdots \succsim _{a}y_{\alpha _{i+j}}\]for all \(a\in A_{n+1}\). Let \(x_{1}=y_{\alpha _{i}}\). We first show that no agent in \(A_{n+1}\) can receive an assignment strictly preferred to \(x_{1}\) in any \(y^{\prime \prime }\in \mathrm{Supp}\left( \sigma ^{\prime \prime }\right)\).

Let \(x\) be an arbitrary individual assignment such that \(x\succ _{\alpha _{i}}x_{1}\). Let \(\bar{y}\) be such that \(\bar{y}_{a}=y_{a}\) for all \(a\in A_{1}\cup \cdots \cup A_{n}\) and \(\bar{y}_{\alpha _{i}}=x\). Then, by the construction of the serial dictatorship rule with \(\alpha\) and \(Y\) satisfies the general upper bounds constraint, \(\bar{y}\) is infeasible. Next, let \(\bar{y}^{\prime \prime }\) be such that \(\bar{y}_{a}^{\prime \prime }=y_{a}^{\prime \prime }\) for all \(a\in A_{1}\cup \cdots \cup A_{n}\) and \(\bar{y}_{\alpha _{i}}^{\prime \prime }=x\). Since \(\left\{ y_{a}^{\prime \prime }\right\} _{a\in A_{l}}=\left\{ y_{a}\right\} _{a\in A_{l}}\) for all \(l=1,\cdots ,n\) and since the agents within each \(A_{l}\) are equals, \(\bar{y}^{\prime \prime }\) is also infeasible. Hence \(x_{1}\succsim _{a}y_{\alpha _{i}}^{\prime \prime }\) for all \(a\in A_{n+1}\).

Suppose \(y_{\alpha _{i}}=\cdots =y_{\alpha _{i+k}}=x_{1}\) where \(k=0,\cdots ,j\); that is, for \(y\), there are \(k+1\) agents in \(A_{n+1}\) who obtain \(x_{1}\). Then, by the construction of the ETE reassignment, \[\Pr \left( x_{1};\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\right) =\frac{k+1}{j+1}\]for all \(a\in A_{n+1}\). Since \(\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\) is first-order stochastically dominatedfor all \(a\in A_{n+1}\) by \(\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\), and since \(x_{1}\succsim _{a}y_{a^{\prime }}^{\prime \prime }\) for all \(a,a^{\prime }\in A_{n+1}\), it follows that \[\Pr \left( x_{1};\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\right) \geq \frac{k+1}{j+1}=\Pr \left( x_{1};\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\right) \label{y}\tag{3}\] for all \(a\in A_{n+1}\).

For any \(y^{\prime \prime }\in \mathrm{Supp}\left( \sigma ^{\prime \prime }\right) ,\) there are at most \(k+1\) agents in \(A_{n+1}\) who obtain \(x_{1}\). If \(k=j\), this is immediate, since \(A_{n+1}\) contains exactly \(j+1=k+1\) agents. Thus, suppose \(k<j\). Then, \[x_{1}=y_{\alpha _{i}}=\cdots =y_{\alpha _{i+k}}\succ _{a}y_{\alpha _{i+k+1}}\text{,}\]assigning \(x_{1}\) to agent \(\alpha _{i+k+1}\) yields a strictly better assignment for them. By the construction of the serial dictatorship rule, if we let \(\bar{y}\) be an assignment such that \[\bar{y}_{a}=y_{a}\text{ for all }a\in A_{1}\cup \cdots \cup A_{n}\cup \left\{ \alpha _{i},\cdots ,\alpha _{i+k}\right\}\] and \(\bar{y}_{\alpha _{i+k+1}}=x_{1}\). By the definition of the serial dictatorship rule, \(\bar{y}\) is infeasible. Since \(\left\{ y_{a}^{\prime \prime }\right\} _{a\in A_{l}}=\left\{ y_{a}\right\} _{a\in A_{l}}\) for all \(l=1,\cdots ,n,\) and since \(Y\) satisfies the general upper bounds constraint, any assignment that gives \(x_{1}\) to \(k+2\) or more agents in \(A_{n+1}\) is also infeasible. Hence for any \(y^{\prime \prime }\in \mathrm{Supp}\left( \sigma ^{\prime \prime }\right) ,\) there are at most \(k+1\) agents in \(A_{n+1}\) who obtain \(x_{1}\).

Therefore, \[\sum_{a\in A_{n+1}}\Pr \left( x_{1};\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\right) \leq k+1\text{.}\]On the other hand, as shown above, for every \(a\in A_{n+1}\), (3 ) is satisfied. Therefore \[\Pr \left( x_{1};\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\right) =\frac{k+1}{j+1}=\Pr \left( x_{1};\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\right)\]for every \(a\in A_{n+1}\).

Moreover, for each \(y^{\prime \prime }\in \mathrm{Supp}\left( \sigma ^{\prime \prime }\right) ,\) at most \(k+1\) agents in \(A_{n+1}\) can receive \(x_{1}\). Since the expected number of such agents is equal to \(k+1\), for every \(y^{\prime \prime }\in \mathrm{Supp}\left( \sigma ^{\prime \prime }\right)\), exactly \(k+1\) in \(A_{n+1}\) receive \(x_{1},\) just as \(y\).

Next, let \(y_{\alpha _{i+k+1}}=x_{2}\), which is the second best pure assignment for each \(a\in A_{n+1}\) under \(y\). By the same argument as above, we can show that \(\Pr \left( x_{2};\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}\right) =\Pr \left( x_{2};\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\right)\) for all \(a\in A_{n+1}\) and that, for each \(y^{\prime \prime }\in \mathrm{Supp}\left( \sigma ^{\prime \prime }\right) ,\) the number of agents in \(A_{n+1}\) who receive \(x_{2}\) is the same as in \(y\).

Iterating this argument over all distinct individual assignments received by agents in \(A_{n+1}\) under \(y\), we conclude that \(\mathbf{x}\left( \sigma ^{\prime \prime }\right) _{a}=\mathbf{x}\left( \sigma ^{\prime }\right) _{a}\) for all \(a\in A_{n+1}\) and that \(\left\{ y_{a}^{\prime \prime }\right\} _{a\in A_{n+1}}=\left\{ y_{a}\right\} _{a\in A_{n+1}}\) for all \(y^{\prime \prime }\in \mathrm{Supp}\left( \sigma ^{\prime \prime }\right)\). Q.E.D.

By Theorem 2, the following computationally efficient method derives an assignment that satisfies both OE and ETE. First, we construct a priority list that satisfies consecutive equals. Second, we derive an assignment by using serial dictatorship rule with the priority list constructed in the first step. Third, we derive the ETE reassignment of the assignment constructed in the second step.

Note that any of the results of this method may not be RE. To show this, we provide the following example.

Example 6↩︎

Let \[\begin{gather} \succ _{a_{1}}:o_{1},o_{3},o_{2},o_{4}, \\ \succ _{a_{2}}:o_{2},o_{1},o_{3},o_{4}, \\ \succ _{a_{3}}:o_{1},o_{2},o_{3},o_{4}, \\ \succ _{a_{4}}:o_{1},o_{2},o_{3},o_{4}. \end{gather}\]Suppose that \(a_{3}\) and \(a_{4}\) are equals. There are \(12\) priority lists satisfying consecutive equals. Among them, since the outcome of our method does not depend on the priority difference between \(a_{3}\) and \(a_{4}\), we only consider the six priority lists in which \(a_{3}\) is ranked higher than \(a_{4}\). To be precise, the following priority lists are summarized as the following table meaning that \(\alpha _{1}^{1}=a_{1},\) \(\alpha _{2}^{1}=a_{2},\) \(\alpha _{3}^{1}=a_{3},\) and \(\alpha _{4}^{1}=a_{4},\) ... .

Then, let \(y^{i}\) be the result of the serial dictatorship rule with priority list \(\alpha ^{i}\) such that\[\begin{align} y^{1} &=&y^{3}=\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{array}\right) , \\ y^{2} &=&\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\end{array}\right) ,y^{4}=\left( \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0\end{array}\right) , \\ y^{5} &=&\left( \begin{array}{cccc} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\end{array}\right) ,y^{6}=\left( \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\end{array}\right) . \end{align}\]Thus, if \(\sigma ^{i}=y^{i}\) is the result of our method above with priority list \(\alpha ^{i}\), then \[\begin{align} R\left( \sigma ^{1}\right) &=&R\left( \sigma ^{3}\right) =R\left( \sigma ^{4}\right) =R\left( \sigma ^{5}\right) =9, \\ R\left( \sigma ^{2}\right) &=&R\left( \sigma ^{6}\right) =10. \end{align}\]However, if\[\sigma =y=\left( \begin{array}{cccc} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1\end{array}\right) ,\]then \(R\left( \sigma \right) =8\). Note that \(y\) is achieved by the serial dictatorship rule with \(\alpha\) such that \(\alpha _{1}=a_{3},\) \(\alpha _{2}=a_{1},\) \(\alpha _{3}=a_{2},\) and \(\alpha _{4}=a_{4}\), which does not satisfy consecutive equals. Therefore, none of the assignments \(\sigma ^{i}\) for \(i=1,\cdots ,6\) is rank-minimizing efficient.

5 Strategic implications↩︎

We consider the following mechanism that naively applies the results of this study. First, agents simultaneously report their preference rankings denoted by \(\bar{\succ}=\left( \bar{\succ}_{a}\right) _{a\in A}\). Second, a priority list \(\alpha\) satisfying consecutive equals is determined. Third, the serial dictatorship rule with \(\alpha\) is implemented. Fourth, the ETE reassignment of the assignment obtained in the third step is derived.

Let \(f\left( \bar{\succ}\right)\) be the result of this mechanism when agents report \(\bar{\succ}=\left( \bar{\succ}_{a}\right) _{a\in A}\). Let \(\succ _{a}\) be the true preference of \(a\) and \(\succ =\left( \succ _{a}\right) _{a\in A}\). If \(\bar{\succ}=\succ ,\) then all agents reveal their true preference orders (i.e., truth-telling)

We show that this mechanism is not strategy-proof, even in a weak sense. That is, for some \(\succ\), some \(a\in A\), and some \(\succ _{a}^{\prime },\) \(\left( f\left( \succ \right) \right) _{a}\) is first-order stochastically dominated for \(a\) by \(\left( f\left( \succ _{a}^{\prime },\succ _{-a}\right) \right) _{a}\).

Hereafter, if there some preference order \(\succ _{a}^{\prime }\) such that \(\left( f\left( \succ \right) \right) _{a}\) is first-order stochastically dominated by \(\left( f\left( \succ _{a}^{\prime },\succ _{-a}\right) \right) _{a}\) for \(a,\) then we simply say that \(a\) has an incentive to manipulate its preference order.

Example 7↩︎

In this example, the agents with identical preference orders are considered equals. Let \(A=\left\{ a_{1},a_{2},a_{3}\right\}\) and \(O=\left\{ o_{1},o_{2},o_{3}\right\}\). We consider the unit-demand case and moreover, the following three preference orders \[\begin{align} \theta &:&\text{ }o_{1},o_{2},o_{3}, \\ \theta ^{\prime } &:&\text{ }o_{2},o_{1},o_{3}, \\ \theta ^{\prime \prime } &:&\text{ }o_{2},o_{3},o_{1}. \end{align}\]

Since there are three agents, there are six possible priority lists: \(\alpha ^{1}=\left( a_{1},a_{2},a_{3}\right) ,\) \(\alpha ^{2}=\left( a_{1},a_{3},a_{2}\right) ,\) \(\alpha ^{3}=\left( a_{2},a_{1},a_{3}\right) ,\) \(\alpha ^{4}=\left( a_{2},a_{3},a_{1}\right) ,\) \(\alpha ^{5}=\left( a_{3},a_{1},a_{2}\right) ,\) and \(\alpha ^{6}=\left( a_{3},a_{2},a_{1}\right)\).

First, we consider the case \(\left( \bar{\succ}_{a_{1}},\bar{\succ}_{a_{2}},\bar{\succ}_{a_{3}}\right) =\left( \theta ,\theta ,\theta \right)\). Since all agents have identical preferences in this case, they are considered equals. Then, \(f\left( \theta ,\theta ,\theta \right) =\)\[\left( \begin{array}{ccc} y_{a_{1}o_{1}} & y_{a_{1}o_{2}} & y_{a_{1}o_{3}} \\ y_{a_{2}o_{1}} & y_{a_{2}o_{2}} & y_{a_{2}o_{3}} \\ y_{a_{3}o_{1}} & y_{a_{3}o_{2}} & y_{a_{3}o_{3}}\end{array}\right) =\left( \begin{array}{ccc} 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3\end{array}\right) .\]

Second, we consider the case \(\left( \bar{\succ}_{a_{1}},\bar{\succ}_{a_{2}},\bar{\succ}_{a_{3}}\right) =\left( \theta ,\theta ,\theta ^{\prime }\right)\). There are four priority lists satisfying consecutive equals \(\alpha ^{1},\) \(\alpha ^{3},\) \(\alpha ^{5}\) and \(\alpha ^{6}\). Among them, \(\alpha ^{1}\) and \(\alpha ^{3}\) yield the same assignment, as do \(\alpha ^{5}\) or \(\alpha ^{6}\). Therefore, it suffices to consider \(\alpha ^{1}\) and \(\alpha ^{5}\).

Suppose that \(\alpha ^{1}\) (or \(\alpha ^{3}\)) is used when \(\left( \bar{\succ}_{a_{1}},\bar{\succ}_{a_{2}},\bar{\succ}_{a_{3}}\right) =\left( \theta ,\theta ,\theta ^{\prime }\right)\). Suppose that the true preferences of the agents are also \(\left( \succ _{a_{1}},\succ _{a_{2}},\succ _{a_{3}}\right) =\left( \theta ,\theta ,\theta ^{\prime }\right)\). If all agents report truthfully, then\[f\left( \theta ,\theta ,\theta ^{\prime }\right) =y^{\prime }=\left( \begin{array}{ccc} 1/2 & 1/2 & 0 \\ 1/2 & 1/2 & 0 \\ 0 & 0 & 1\end{array}\right) .\]is realized. On the other hand, if \(a_{3}\) reports \(\bar{\succ}_{a_{3}}=\theta\) instead, then \(f\left( \theta ,\theta ,\theta \right)\) (as described above) is realized. Therefore, \(a_{3}\) has an incentive to manipulate its preference order.

On the other hand, suppose that \(\alpha ^{5}\) (or \(\alpha ^{6}\)) is used when \(\left( \bar{\succ}_{a_{1}},\bar{\succ}_{a_{2}},\bar{\succ}_{a_{3}}\right) =\left( \theta ,\theta ,\theta ^{\prime }\right)\). Suppose that the true preferences of the agents are also \(\left( \succ _{a_{1}},\succ _{a_{2}},\succ _{a_{3}}\right) =\left( \theta ,\theta ,\theta ^{\prime }\right)\). Then,\[f\left( \theta ,\theta ,\theta ^{\prime }\right) =y^{\prime \prime }=\left( \begin{array}{ccc} 1/2 & 0 & 1/2 \\ 1/2 & 0 & 1/2 \\ 0 & 1 & 0\end{array}\right) .\]In this case, we consider the manipulation of \(a_{2}\) such that \(\bar{\succ}_{a_{2}}=\theta ^{\prime \prime }\); that is, \(\left( \bar{\succ}_{a_{1}},\bar{\succ}_{a_{2}},\bar{\succ}_{a_{3}}\right) =\left( \theta ,\theta ^{\prime \prime },\theta ^{\prime }\right)\).

First, we additionally assume that the priority list is \(\alpha ^{1},\) \(\alpha ^{3},\) \(\alpha ^{4},\) or \(\alpha ^{6}\). Then, in \(f\left( \theta ,\theta ^{\prime \prime },\theta ^{\prime }\right) ,\) \(a_{2}\) is assigned to \(o_{1}\) and \(o_{2}\) with probability \(0.5\) each. Thus, if \(\alpha ^{1}\) (\(\alpha ^{3},\) \(\alpha ^{4},\) or \(\alpha ^{6}\)) is used when \(\left( \bar{\succ}_{a_{1}},\bar{\succ}_{a_{2}},\bar{\succ}_{a_{3}}\right) =\left( \theta ,\theta ^{\prime \prime },\theta ^{\prime }\right)\) and \(\alpha ^{5}\) (or \(\alpha ^{6}\)) is used when \(\left( \bar{\succ}_{a_{1}},\bar{\succ}_{a_{2}},\bar{\succ}_{a_{3}}\right) =\left( \theta ,\theta ,\theta ^{\prime }\right) ,\) then \(a_{2}\) has an incentive to manipulate.

Second, suppose that \(\alpha ^{5}\) (or \(\alpha ^{6}\)) is used when \(\left( \bar{\succ}_{a_{1}},\bar{\succ}_{a_{2}},\bar{\succ}_{a_{3}}\right) =\left( \theta ,\theta ,\theta ^{\prime }\right)\), and \(\alpha ^{2}\) (or \(\alpha ^{5}\)) is adopted when \(\left( \bar{\succ}_{a_{1}},\bar{\succ}_{a_{2}},\bar{\succ}_{a_{3}}\right) =\left( \theta ,\theta ^{\prime \prime },\theta ^{\prime }\right)\). In this case, suppose the true preferences of the agents are also \(\left( \succ _{a_{1}},\succ _{a_{2}},\succ _{a_{3}}\right) =\left( \theta ,\theta ^{\prime \prime },\theta ^{\prime }\right)\). Then,\[f\left( \theta ,\theta ^{\prime \prime },\theta ^{\prime }\right) =\left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0\end{array}\right) .\]However, in this case, if \(a_{2}\) reports \(\bar{\succ}_{a_{2}}=\theta\) instead, then \(y^{\prime \prime }\) (as described above) is realized. Therefore, \(a_{2}\) has an incentive to manipulate its preference order.

If the priority list of agents is determined independently of their revealed preferences, then the serial dictatorship rule satisfies strategy-proofness. However, in our mechanism, in order to ensure OE, the priority list must satisfy consecutive equals, which necessarily makes it dependent on the revealed preferences. Therefore, some agents may have an incentive to manipulate their preferences.

Therefore, the mechanism that naively applies the results of this study is vulnerable to strategic manipulation, in contrast to the random serial dictatorship and the probabilistic serial mechanisms. The issue does not lie in the ETE reassignment procedure itself, but rather in the requirement that the priority list in the serial dictatorship rule must satisfy consecutive equals.

6 Who should be considered equals?↩︎

We extend the notion of ETE so that it can accommodate policy goals such as affirmative action. In our formulation, characteristics other than preferences—such as gender, race, or economic disadvantage—may be incorporated when defining equality. If too many characteristics are taken into account, almost no agents will be regarded as equals, and ETE will hold trivially.

However, using such detailed information when determining assignments raises concerns. First, except in cases where measures such as affirmative action are justified, basing assignment decisions on inherent characteristics—such as those individuals are born with—widely considered unacceptable but may also be illegal in many countries.

Second, concerns also arise when assignment decisions rely on individual characteristics that reflect agents’ ex-post economic or social behavior. For example, in the Japanese day-care matching market, when multiple parents with similar working conditions at their place of employment apply to the same day-care center, tie-breaking is often determined by factors such as household income or the duration of residence in the area.¹⁴ Such a system may create incentives for parents to reduce their working hours or refrain from relocating, thereby distorting important economic decisions. Accordingly, using strategically manipulable characteristics to differentiate among agents raises significant concerns.

While assigning students based on entrance examinations can be justified as a means of promoting academic achievement, it also carries the risk of fostering excessive competition, which has become a serious concern in many East Asian countries. Therefore, since the set of personal characteristics that can or should be used is limited, some agents must be treated as equals.¹⁵

As a result, ETE does not hold automatically, and it becomes important to compute ETE assignments using methods such as those developed in this paper.

7 Concluding Remarks↩︎

In this paper, we discuss assignments that satisfy both efficiency and ETE by employing the ETE reassignment procedure.

We show that even under RE, the strongest definition of efficiency in this paper, assignments that are both efficient and satisfy ETE do exist in general cases. In the case with unit demand and simple capacity constraints, an RE assignment can be executed efficiently. Therefore, if we restrict attention to this specific setting, our method can yield assignments that satisfy both RE and ETE. However, in more general cases, no computationally efficient method is known for deriving such assignments is known.

Therefore, we next focus on OE, the second strongest notion of efficiency. Under general upper bound constraints, we show that if an OE assignment is obtained by applying the serial dictatorship rule with a priority list satisfying the consecutive equals property, its ETE reassignment also preserves OE. Although this does not constitute a complete solution to the aforementioned problem, it has significant merit, as general upper bound constraints encompass many important applications and OE represents a compelling notion of efficiency.

The mechanism that naively applies the results of this study is vulnerable to strategic manipulation. However, this vulnerability may not stem from the ETE reassignment procedure itself. Thus, it may remain possible that a mechanism satisfying ETE, OE, and weak strategy-proofness can be designed by utilizing ETE reassignment.¹⁶ Nevertheless, whether such a mechanism exists remains an open question

Furthermore, this paper investigates whether the efficiency of an assignment is preserved when it is transformed into an ETE assignment through the ETE reassignment procedure. It is also worth considering whether other properties of assignments are retained after the ETE reassignment. For instance, future work may explore stability in matching problems as well as constrained efficiency.

References↩︎

---

1. Department of Logistics and Information Engineering, Tokyo University of Marine Science and Technology (TUMSAT), 2-1-6 Etchujima, Koto-ku, Tokyo 135-8533, Japan, Phone: +81-3-5245-7300, Fax: +81-3-5245-7300, E-mail: okuyasu@gs.econ.keio.ac.jp↩︎

2. The author is grateful to Minoru Kitahara for insightful comments and suggestions. This work was supported by JSPS KAKENHI Grant Number 25K05004.↩︎

3. In fact, affirmative action policies have been implemented in various school choice markets, including those in Brazil, China, India, and the United States. Such policies are designed to address structural disadvantages arising from differences in gender, race, income level, or other inherent attributes—disparities that individual effort alone cannot overcome.↩︎

4. For example, in the Japanese daycare matching market (Okumura, 2019), replacing an older child with an infant may render an assignment infeasible. Enforcing ETE in such cases typically entails an efficiency loss. Therefore, we regard agents as equals only if they are identical in both preferences and relevant constraints.↩︎

5. Kamada and Kojima (2024) and Imamura and Kawase (2025) illustrate that general upper-bound constraints are applicable to a wide range of real-world settings, such as the refugee matching problems (Andersson and Ehlers, 2020), the day-care matching problems (Okumura, 2019), and the controlled school choice problems (Abdulkadiroğlu and Sönmez, 2003).↩︎

6. Basteck and Ehlers (2025) introduce another mechanism that satisfies EE, ETE, and strategy-proofness.↩︎

7. In fact, Kojima (2009) explicitly assumes that agents’ preferences over sets of objects are additively separable across objects, and mentions in footnote 7 that this assumption is restrictive.↩︎

8. This means that \(o_{1}\succ _{a}o_{2}\succ _{a}o_{3}\succ _{a}o_{4}\) for all \(a\in A\). In the examples in this study, the preferences of agents are represented in this simplified manner.↩︎

9. For a discussion of the relationship between rank-minimizing and other notions of efficiency, see Feizi (2024).↩︎

10. Kesten and Ünver (2015) and Han (2024) explicitly consider the priority orders of objects and assume that the priority orders among equals are tied.↩︎

11. Balbuzanov (2022) shows that any feasibility constraint can be reformulated as an upper-bound constraint; however, this transformation may not be computable in polynomial time for certain classes of constraints. Since this section of this paper focuses on computationally efficient methods, the approach proposed by Balbuzanov (2022) cannot be generally employed, except in trivial cases.↩︎

12. In the actual case of engineering school admissions in India, the capacities of some reserved slots are treated as hard bounds—if there are not enough applicants, those slots remain vacant. However, some other types of reserved slots may be converted into general-category slots if left vacant. For further details, see Aygün and Turhan (2017).↩︎

13. This example (Example 5) is suggested by Minoru Kitahara, and I am grateful for his contribution.↩︎

14. Yamaguchi et al. (2018) document that, in many cities in Japan, daycare applications are ranked largely according to parents’ working hours at the time of application. Takenami (2025) notes that, in Tama City, when parents’ working hours are at the same level, ties are broken based on factors such as length of residence and household income.↩︎

15. In principle, ties can be broken using arbitrary identifiers, such as Social Security Numbers. This kind of tie-breaking is essentially the same as using a probabilistic assignment, which is the method we study in this paper.↩︎

16. As shown by Bogomolnaia and Moulin (2001), there exists no mechanism that satisfies ETE, OE, and strategy-proofness (in the strict sense), when there are three or more agents, even in the case of single-unit demand and simple capacity constraints. Aziz and Kasajima (2017) show that in the case of multi-unit demand and simple capacity constraints, there exists no mechanism that satisfies all three properties, when there are two or more agents.↩︎