Local and global consistency properties for student placement

Local and Global Consistency Properties for Student Placement∗ Bettina Klaus†Flip Klijn‡ March 2011 Abstract In the context of resource allocation on the basis of priorities, Ergin (2002) identifies a necessary and sufficient condition on the priority structure such that the student-optimal stable mechanism satisfies a consistency principle. Ergin (2002) formulates consistency as a local property based on a fixed population of agents and fixed resources – we refer to this condition as local consistency and to his condition on the priority structure as local acyclicity. We identify a related but stronger necessary and sufficient condition (unit acyclicity) on the priority structure such that the student-optimal stable mechanism satisfies a more standard global consistency property. Next, we provide necessary and sufficient conditions for the student-optimal stable mechanism to satisfy converse consistency principles. We identify a necessary and sufficient condition (local shift-freeness) on the priority structure such that the student-optimal stable mechanism satisfies local converse consistency. Interestingly, local acyclicity implies local shift-freeness and hence the student-optimal stable mechanism more frequently satisfies local converse consistency than local consistency. Finally, in order for the student-optimal stable mechanism to be globally conversely consistent, one again has to impose unit acyclicity on the priority structure. Hence, unit acyclicity is a necessary and sufficient condition on the priority structure for the student-optimal stable mechanism to satisfy global consistency or global converse consistency. JEL classification: D63, C78. Keywords: acyclicity, consistency, converse consistency, student placement. 1 Introduction A student placement problem is determined by a set of students, a set of position types, the number of available positions – the quota – of each type, and the students’ strict preferences over position types (e.g., a position type could represent the admission to a college or university) and remaining unassigned. A student placement mechanism assigns to any given student placement ∗Bettina Klaus gratefully acknowledges financial support from the Netherlands Organisation for Scientific Research (NWO) under grant VIDI-452-06-013. Flip Klijn gratefully acknowledges support from Plan Nacional I+D+I (ECO2008-04784), Generalitat de Catalunya (SGR2009-01142), the Barcelona GSE Research Network and the Consolider-Ingenio 2010 (CSD2006-00016) program. A first draft of this paper was written while Flip Klijn was visiting Harvard Business School. He gratefully acknowledges a research fellowship from HBS. †Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland; e-mail: [email protected] ‡Corresponding author: Institute for Economic Analysis (CSIC), Campus UAB, 08193 Bellaterra (Barcelona), Spain; e-mail: [email protected] 1 problem an allocation of the position types to the students such that every student receives at most one position and quotas are binding. In contrast to so-called house allocation problems, where an assignment is made on the basis of students’ preferences over position types alone,1we assume that in a student placement problem additional information is available.2For instance, college admissions of undergraduate students are often based on rankings obtained from one or several entrance exams. Then, students who achieved higher test scores in the entrance exam of a certain college have higher priority for admission at that college than students with lower test scores. We will model this situation using strict priority rankings of individuals for each position type (possibly using tie-breaking). We call the collection of strict priority rankings a priority structure. A placement mechanism violates the priority of student ifor position xif there exist preferences under which student ienvies student jwho obtains xeven though ihas a higher priority for xthan j. A placement mechanism is fair if it never violates the priority of any student. Ergin (2002) focuses on the so-called student-optimal stable mechanism (introduced by Gale and Shapley, 1962) since it is fair and Pareto superior to any other fair placement mechanism. Ergin (2002, Theorem 1) provides a necessary and sufficient “acyclicity” condition on the priority structure for the student-optimal stable mechanism to satisfy several appealing properties. In particular, he considers a notion of consistency. However, Ergin (2002) formulates consistency as a local property based on a fixed population of agents and fixed resources – we refer to this condition as local consistency and to his condition on the priority structure as local acyclicity. Ergin’s (2002) consistency notion is different from the standard consistency notion since the set of students and the quotas are fixed in Ergin’s (2002) model. We identify a related but stronger necessary and sufficient condition (unit acyclicity) on the priority structure such that the student-optimal stable mechanism satisfies a more standard global consistency property (Theorem 2).3 Next, we are interested in a property that is closely related to consistency, namely converse consistency. Converse consistency refers to an inverse of the reduction operation that consistency uses. Thomson (2009, page 30) describes converse consistency as a property of “decentralizability”: given some problem, if an allocation is chosen for each of its associated reduced two-agent problems, then it should be chosen for the problem involving the whole group. Converse consistency has some practical appeal whenever small problems are much easier to solve than large ones. For two-sided matching problems, the two-agent subgroup assumption that converse consistency is based on is usually adjusted to include somewhat larger groups of agents (Thomson, 2009, page 209). Given the matching character of our model (and the fact that we are interested in the properties of a specific matching mechanism), two papers exploring aspects of converse consistency for marriage problems (one-to-one matching problems) are Sasaki and Toda (1992) and ¨ Ozkal-Sanver (2009). Sasaki and Toda (1992) show that the core correspondence for marriage markets satisfies converse consistency and that this property is part of a core 1Sometimes it is also assumed that exactly one position of each type is available. Some recent articles on house allocation problems are Ergin (2000), Ehlers (2002), Ehlers et al. (2002), and Ehlers and Klaus (2003, 2006, 2007). 2See, for instance, Balinski and S¨onmez (1999), Ergin (2002), and Kesten (2006). 3For instance, Thomson’s (2009, page 16) “Fundamental Definition” of consistency deals with a variable population setup and imposes the consistency requirement on all subpopulations as well. 2 characterization; we briefly discuss ¨ Ozkal-Sanver (2009) below. For an overview of the literature on converse consistency in other contexts we refer to Thomson (2004, 2009). ¨ Ozkal-Sanver (2009, Example 3.2) shows that, depending on the priority structure, the student-optimal stable mechanism may not satisfy converse consistency. In view of this negative result, there are (at least) two ways to proceed. The first approach is to expand the student-optimal stable mechanism to obtain a conversely consistent (multi-valued) correspondence. A particularly interesting correspondence is the minimal expansion that is conversely consistent. ¨ Ozkal-Sanver took this approach and her main result is the identification of the minimal conversely consistent extension of the student-optimal stable mechanism (¨ Ozkal-Sanver, 2009, Theorem 4.1). In view of the practical and theoretical relevance of the student-optimal stable matching mechanism, a second approach would consist of the identification of conditions under which it is conversely consistent. Our paper takes this approach. Similarly to the previous discussion on consistency, one can consider local converse consistency based on a fixed set of students and a fixed quota vector, or allow for the general variable population and resource context and consider (standard) global converse consistency. We first identify a necessary and sufficient condition (local shift-freeness) on the priority structure such that the student-optimal stable mechanism satisfies local converse consistency (Theorem 3). Interestingly, local acyclicity implies local shift-freeness (Lemma 2) and hence the student-optimal stable mechanism more frequently satisfies local converse consistency than local consistency (Corollary 1). Furthermore, in situations where at most one position per position type is available, both conditions coincide (Lemma 3) and the student-optimal stable mechanism satisfies local converse consistency if and only if it satisfies local consistency (Corollary 2). Finally, in order for the student-optimal stable mechanism to be globally conversely consistent, one again has to impose unit acyclicity on the priority structure (Theorem 4). Hence, the student-optimal stable mechanism is globally conversely consistent if and only if it is globally consistent (Corollary 3). The paper is organized as follows. In Section 2 we introduce the student placement model and the student-optimal stable mechanism. Section 3 (4) contains the local and global (converse) consistency results mentioned above. 2 Student Placement Let ¯ N={1,...,n}denote a set of students with n≥3. Let X={x1,...,xp}denote a set of (real) position types with |X| ≥ 3.4For each position type x∈X, at most ¯qx∈Ncopies are available with 1 ≤¯qx≤ | ¯ N|. Furthermore, while ¯qxdenotes the maximal number of positions of type xthat might become available, by qx∈ {0,1,...,¯qx}we denote the number of positions, the quota,of position type xthat are available. A quota vector q≡(qx)x∈Xdenotes the quota of all position types. Note that we use the term “position x” when we refer to one of the qxpositions of position type x. Let 0 denote the null position, which does not belong to X; “receiving the null position” means “not receiving any position.” Since the null position is freely available, we simply assume q0=∞. 4The cases |¯ N| ≤ 2 or |X| ≤ 2 are trivial because then the central properties of the article (consistency and converse consistency) have no bite. Furthermore, our results remain unchanged for infinite ¯ Nor X. 3 Each student i∈¯ Nis equipped with a strict, transitive, and complete preference relation Riover X∪ {0}, i.e., Riis a linear order over X∪ {0}. Given x, y ∈X∪ {0},x Piymeans that student istrictly prefers xto y. If x Pi0, then position xis acceptable for student i, otherwise it is unacceptable (and 0 Pix). Let Rdenote the set of strict, transitive, and complete preference relations over X∪ {0}. For each N⊆¯ N,RNis the set of (preference) profiles R= (Ri)i∈N such that for all i∈N,Ri∈ R. Given N′⊆N⊆¯ Nand R∈ RN, let RN′denote the profile (Ri)i∈N′; it is the restriction of profile Rto the set of students N′. Let x∈X. We call a linear order ≻xover ¯ Napriority ordering for position type x. Given i, j ∈¯ N,i6=j, student ihas a higher priority for position xthan student jif i≻xj. A priority structure is a profile ≻= (≻x)x∈Xspecifying for each position type a priority ordering. A(student) placement problem (N, R, q) consists of a (finite) set of students N⊆¯ N, preferences R∈ RN, and a quota vector q= (qx)x∈Xsuch that for all positions x∈X, 0 ≤qx≤¯qx. We assume that the null position is available in any placement problem. Finally, we assume that a priority structure ≻over Xis externally given (we do not include it in the description of a placement problem because we assume it to be fixed). For each placement problem (N, R, q), each student i∈Nis to be allocated exactly one position in X∪{0}taking quotas as upper bounds. Formally, an allocation for (N, R, q) is a list α= (αi)i∈Nsuch that for all i∈N,αi∈X∪ {0}, and for all x∈X,|{i∈N:αi=x}| ≤ qx. Thus, an allocation is by definition feasible. Note that not all available positions need to be assigned. Given i∈N, we call αithe allotment of student iat α. Next, we introduce the notion of a reduced student placement problem and of a reduced allocation. Consider a student placement problem (N, R, q), an allocation αfor it, and a subset N′⊆Nof students. Then, the reduced placement problem (N′, RN′, q(N′, α)) for students N′ at allocation αis defined as the placement problem where the set of students equals N′and the only position types that are available to them are those not allocated to students in N\N′at α, i.e., for all x∈X,q(N′, α)x=qx− |{i∈N\N′:αi=x}|. Let αN′denote the allocation (αi)i∈N′. It is the restriction of allocation αto the set of students N′. Note that αN′is an allocation for (N′, RN′, q(N′, α)). An allocation αis individually rational for placement problem (N, R, q) if for each i∈N, allotment αiis acceptable for student i. An allocation αis non-wasteful for placement problem (N, R, q) if there are no student i∈N and position x∈Xsuch that x Piαiand |{j∈N:αj=x}| < qx. An allocation αviolates the priority of student i∈Nfor placement problem (N, R, q) if there exists a position xsuch that student ihas a higher priority for xthan one of the students assigned to it and student iprefers to switch to position x, i.e., there exist x∈Xand j∈N\{i} such that i≻xj,αj=x, and x Piαi. A(student) placement mechanism is a function ϕthat assigns to each placement problem (N, R, q) an allocation ϕ(N, R, q). A placement mechanism ϕis individually rational if for each placement problem (N, R, q), ϕ(N, R, q) is individually rational for placement problem (N, R, q). 4 A placement mechanism ϕis non-wasteful if for each placement problem (N, R, q), ϕ(N, R, q) is non-wasteful for placement problem (N, R, q). A placement mechanism ϕis fair (Balinski and S¨onmez, 1999) if for each placement problem (N, R, q), ϕ(N, R, q) does not violate the priority of any student for placement problem (N, R, q). Given a placement problem (N, R, q), we can associate (N, R, q) with a college admissions problem as follows (Balinski and S¨onmez, 1999): the set of students equals N, the set of position types Xcorresponds to the set of colleges, the quota vector qdescribes colleges’ quotas, preferences Rcorrespond to students’ preferences over colleges, and the priority structure ≻ is taken to represent colleges’ responsive preferences over students. Furthermore (Balinski and S¨onmez, 1999, Lemma 2), an allocation αis individually rational, non-wasteful, and fair for placement problem (N, R, q) if and only if the associated “matching” αis stable for the associated college admissions problem, i.e., αis individually rational for (N, R, q) and there exists no studentposition blocking pair (i, x)∈N×(X∪ {0}) such that x Piαiand (s1) |{j∈N:αj=x}| < qx or (s2) there exists k∈Nsuch that αk=xand i≻xk.5 For each placement problem (N, R, q), we denote by ϕ≻(N, R, q) the student-optimal stable allocation for placement problem (N, R, q) that is obtained by using Gale and Shapley’s (1962) student-proposing deferred-acceptance algorithm: •At the first step of the student-proposing deferred-acceptance algorithm, every student in Napplies to her/his favorite position. For each position x∈X∪ {0}, the qxapplicants who have the highest priority for x(all applicants if there are fewer than qxor x= 0) are placed on the waiting list of position x, and all others are rejected. (If qx= 0, then all proposing students are rejected.) •At the r-th step of the student-proposing deferred-acceptance algorithm, those applicants who were rejected at step r−1 apply to their next best position. For each position x∈X∪ {0}, the qxapplicants among the new applicants and those on the waiting list who have the highest priority for position xare placed on the updated waiting list of position x, and all others are rejected. The student-optimal deferred-acceptance algorithm terminates when every student is on a waiting list. Note that the null object has unlimited capacity and eventually any student is put on the waiting list of a real position x∈Xor the null object. Once the algorithm ends, positions are assigned to the students on the respective position waiting lists and the resulting allocation is the student-optimal stable allocation ϕ≻(N, R, q) for the placement problem (N, R, q). By ϕ≻we denote the student-optimal stable mechanism that assigns to each placement problem (N, R, q) the student-optimal stable allocation ϕ≻(N, R, q). 5The definition of stability here is less general than the one for college admissions problems because for student placement problems, position types always “find all students acceptable.” For more details on the well-known college admissions model and basic and well-known results for this model, we refer the interested reader to Gale and Shapley (1962) and Roth and Sotomayor (1990). 5 3 Consistency 3.1 Local Consistency Ergin (2002) refers to the student-optimal stable mechanism ϕ≻as the “best rule” and analyzes for which priority structures ≻,ϕ≻satisfies well-known and desirable properties given a fixed set of students N⊆¯ Nand a fixed quota vector q. Ergin (2002, Theorem 1) provides a necessary and sufficient acyclicity condition (Definition 2 below) for the student-optimal stable mechanism to satisfy either of Pareto efficiency,6group-strategy proofness,7and a (local!) consistency property (Ergin, 2002, p. 2494) that we explain next. Loosely speaking, a placement mechanism is consistent if, whenever some students leave with their allotments, the placement mechanism allocates the remaining positions among the students who did not leave in the same way as in the original placement problem. In order to introduce consistency of a placement mechanism in a model where the set of agents and resources are fixed a priori, Ergin (2002) only requires a local consistency check for all reduced placement problems that are obtained from an original placement problem (N, R, q) (Nand qbeing fixed).8 Formally, Ergin (2002, p. 2493) only requires that ϕ≻is consistent on the domain of reduced placement problems that are obtained from a placement problem (N, R, q) when a subset of agents N′⊆Nreallocates resources after agents in N\N′have left with their allotments at ϕ≻(N, R, q). Definition 1. Local consistency Let N⊆¯ Nbe a set of students and qa quota vector. A placement mechanism ϕis locally consistent for (N, q) if for each profile R∈ RNand each subset of students N′⊆N: [for all i∈N′,ϕi(N′, RN′, q(N′, ϕ(N, R, q))) = ϕi(N, R, q)]. △ Next, we introduce Ergin’s (2002, p. 2492) acyclicity condition for priority structures. Again, since the set of agents Nand the quota vector qare fixed, acyclicity has a “local character.” Definition 2 (Ergin, 2002).Local cycles and local acyclicity Let N⊆¯ Nbe a set of students and qa quota vector. Given a priority structure ≻, a local cycle for (N, q) is constituted of ordered and distinct x, y ∈X(qx, qy6= 0) and i, j, k ∈Nsuch that the following two conditions are satisfied: cycle condition i≻xj≻xk≻yiand c-scarcity condition there exist disjoint (and possibly empty) sets Nx, Ny⊆N\ {i, j, k}such that Nx⊆ {l∈N:l≻xj},Ny⊆ {l∈N:l≻yi},|Nx|=qx−1, and |Ny|=qy−1. A priority structure ≻is locally acyclic for (N, q) if it has no local cycles for (N, q). △ If quotas are all equal to 1, then the cycle condition is sufficient to establish the existence of a local cycle. For other quotas, the c-scarcity condition limits the definition of a local cycle 6A placement mechanism is Pareto efficient if no assigned allocation can be (Pareto) improved such that all students are weakly better off and some are strictly better off. 7A placement mechanism is group-strategy proof if no group of students, by jointly misrepresenting their preferences, can change their allotments such that all members of the group are weakly better off and some are strictly better off. 8Thomson and Zhou (1993) take a similar “local consistency” approach in a model with atomless economies. 6 to cases where there indeed exist students’ preferences such that students i,j, and kcompete for position types xand y(in the absence of this competition, e.g., because the quotas do in fact not limit the access of the students to positions xand y, a local cycle will not lead to the violation of Pareto efficiency, group strategy-proofness, or local consistency – see Ergin, 2002, for further discussion). Ergin (2002, Theorem 1, (iii)⇔(iv), p. 2494) characterizes local consistency of the studentoptimal stable mechanism by local acyclicity (Ergin, 2002, uses the terms consistency and acyclicity without referring to their local character). Theorem 1 (Ergin, 2002).Local consistency of the student-optimal stable mechanism Let N⊆¯ Nbe a set of agents, qa quota vector, and ≻a priority structure. Then, ϕ≻is locally consistent for (N, q)if and only if ≻is locally acyclic for (N, q). 3.2 Global Consistency In the literature, consistency is usually defined for models with a variable population and variable resources.9In order to distinguish this standard notion of consistency from Ergin’s local consistency property, we will refer to it as global consistency. In our variable population and variable resources extension of Ergin’s (2002) model, a mechanism ϕis globally consistent if for any set of present agents Nand for any set of available resources (represented by a quota vector q), it is locally consistent. Definition 3. Global consistency A placement mechanism ϕis globally consistent if it is locally consistent for all (N, q) such that N⊆¯ Nand qis a quota vector. △ Using Ergin’s (2002) result (Theorem 1), we now identify a necessary and sufficient condition for priority structure ≻to guarantee that ϕ≻is globally consistent. Definition 4. Unit cycles and unit acyclicity Given a priority structure ≻, a unit cycle is constituted of ordered and distinct x, y ∈Xand i, j, k ∈¯ Nsuch that the following condition is satisfied: cycle condition i≻xj≻xk≻yi. A priority structure ≻is unit acyclic if it has no unit cycles. △ Theorem 2. Global consistency of the student-optimal stable mechanism Let ≻be a priority structure. Then, ϕ≻is globally consistent if and only if ≻is unit acyclic. Proof. Let ≻be a priority structure. By definition, ϕ≻is globally consistent if for all N⊆¯ Nand all quota vectors q,ϕ≻is locally consistent for (N, q). By Theorem 1 (Ergin, 2002, Theorem 1, (iii)⇔(iv)), this is equivalent to the priority structure ≻being locally acyclic for all N⊆¯ Nand for all quota vectors q. We complete the proof by showing that ≻being locally acyclic for all N⊆¯ Nand for all qis equivalent to ≻being unit acyclic. 9See Ergin (2000) and Thomson (2004, 2009) for the indivisible-object assignment setting and general allocation problems, respectively. 7 If ≻is unit acyclic, then the cycle condition in Definition 2 cannot be satisfied for any three agents i, j, k ∈N⊆¯ N. Hence, ≻is locally acyclic for all N⊆¯ Nand for all q. Now assume that ≻is not unit acyclic. Hence, there exist distinct x, y ∈Xand i, j, k ∈¯ N such that i≻xj≻xk≻yi. Let N={i, j, k}and qsuch that qx= 1, qy= 1, and for all z∈X\ {x, y},qz= 0. Then, we have constructed a local cycle for (N, q). 4 Converse Consistency We are also interested in a property that is closely related to consistency: converse consistency. Converse consistency refers to an inverse of the reduction operation that consistency uses. Given some problem, it requires that if a mechanism or correspondence (partially) chooses an allocation for each of its associated reduced two-agent problems, then the (whole) allocation should be chosen for the problem involving the whole group. Sasaki and Toda (1992) and ¨ OzkalSanver (2009) consider converse consistency for the closely related class of marriage problems (one-to-one matching problems). Furthermore, Thomson (2004, 2009) provides an extensive survey of consistency and its converse for various economic models. Since we focus on the student-optimal stable mechanism, we introduce converse consistency directly for mechanisms and not (as is the standard) for correspondences. 4.1 Local Converse Consistency Similarly as in Section 3, we first introduce local converse consistency. Definition 5. Local converse consistency Let N⊆¯ Nbe a set of students and qa quota vector. A placement mechanism ϕis locally conversely consistent for (N, q) if for each profile R∈ RNand for each allocation αfor placement problem (N, R, q): [if for all N′⊆Nwith |N′|= 2, ϕ(N′, RN′, q(N′, α)) = αN′, then ϕ(N, R, q) = α]. △ The following example demonstrates that a student-optimal stable mechanism might violate local converse consistency (our example is a simplification of ¨ Ozkal-Sanver’s, 2009, Example 3.2). Example 1. A priority structure ≻such that ϕ≻is not locally conversely consistent Let X={x, y, z},N={1,2,3}, and qx=qy=qz= 1. Consider the priority structure ≻and preferences R∈ RNas given in the tables below. ≻x≻y≻z 1 2 3 2 3 1 3 1 2 and R1R2R3 z x y x y z For this placement problem, ϕ≻(N, R, q) = (z, x, y). Let α= (x, y, z). One easily verifies that for all N′⊆Nwith |N′|= 2, ϕ≻(N′, RN′, q(N′, α)) = αN′. However, ϕ≻(N, R, q)6=α. Therefore, ϕ≻is not locally conversely consistent for (N, q). (Incidentally, notice that αis the position-type-optimal stable matching of the associated marriage problem.) Observe that 1≻x2≻y3≻z1, which turns out to be the “problematic part” in priority structure ≻that causes ϕ≻to violate local converse consistency. ⋄ 8 Given a fixed set of students Nand a fixed quota vector q, we first analyze which priority structures ≻guarantee that the student-optimal stable mechanism ϕ≻is locally conversely consistent for (N, q). In line with Ergin’s (2002) result, we show that local acyclicity of the priority structure for (N, q) is sufficient for ϕ≻to be locally conversely consistent for (N, q). However, it turns out that the class of priority structures that induce ϕ≻to be locally conversely consistent for (N, q) is strictly larger than the class of locally acyclic priority structures for (N, q). We first introduce local shift-freeness of a priority structure ≻for (N, q). We then prove that local shift-freeness for (N, q) is a necessary and sufficient condition for the student-optimal stable mechanism ϕ≻to be locally conversely consistent for (N, q) (Theorem 3). Definition 6. Local shifts and local shift-freeness Let N⊆¯ Nbe a set of students and qa quota vector. Given a priority structure ≻, a local shift for (N, q) is constituted of ordered and distinct x, y, z ∈X(qx, qy, qz6= 0) and i, j, k ∈Nsuch that the following two conditions are satisfied: shift condition i≻xj≻yk≻ziand s-scarcity condition there exist disjoint (and possibly empty) sets Nx, Ny, Nz⊆N\ {i, j, k} such that Nx⊆ {l∈N:l≻xj},Ny⊆ {l∈N:l≻yk},Nz⊆ {l∈N:l≻zi},|Nx|=qx−1, |Ny|=qy−1, and |Nz|=qz−1. A priority structure ≻is locally shift-free for (N, q) if it has no local shifts for (N, q). △ If quotas are all equal to 1, then the shift condition is sufficient to establish the existence of a local shift. For other quotas, the s-scarcity condition limits the definition of a local shift to cases where there indeed exist students’ preferences such that students i,j, and kcompete for position types x,y, and z(in the absence of this competition, e.g., because the quotas do in fact not limit the access of the students to positions x,y, and z, a local shift will not cause the student-optimal stable mechanism ϕ≻to violate local converse consistency). Note that Example 1 exhibits a local “3-shift” in the sense that it involves 3 students (and 3 position types). We will use the following concept of more general local shifts to prove our main result. Definition 7. Local k-shifts Let N⊆¯ Nbe a set of students and qa quota vector. Given a priority structure ≻, a local k-shift for (N, q) is constituted of ordered and distinct x1,...,xk∈X(qx1,...,qxk6= 0) and i1,...,ik∈Nwith k≥3 such that the following two conditions are satisfied: k-shift condition i1≻x1i2≻x2i3≻x3· · · ≻xk−1ik≻xkik+1 := i1and s-scarcity condition there exist disjoint (and possibly empty) sets Nxl⊆N\ {i1,...,ik}(l= 1,...,k) such that Nxl⊆ {j∈N:j≻xlil+1}and |Nxl|=qxl−1 (l= 1,...,k). △ We next show that for any pair (N, q), the presence of a local k-shift for (N, q) implies the presence of a local shift for (N, q). Lemma 1. Let N⊆¯ Nbe a set of students and qa quota vector. If priority structure ≻has a local k-shift for (N, q), then it has a local shift for (N, q). 9 vacuously satisfied). Hence, by Corollary 2, ϕ≻is not locally conversely consistent for (N, q). So, ϕ≻is not globally conversely consistent. Part II: Assume ϕ≻is not globally conversely consistent. Then, for some set of agents N⊆¯ N and quota vector q,ϕ≻is not locally conversely consistent for (N, q). By Theorem 3, the priority structure ≻has a local shift for (N, q). Let x, y, z ∈X(qx, qy, qz6= 0) and (without loss of generality) 1,2,3∈Nconstitute a local shift for (N, q). Let Nx, Ny,and Nzbe the corresponding sets in the s-scarcity condition. Consider ˜qwith ˜qx=qx− |Nx|= 1, ˜qy=qy− |Ny|= 1, ˜qz=qz− |Nz|= 1, and ˜qx′= 0 (x′∈X\ {x, y, z}). Then, ˜qis a unit quota vector and x, y, z ∈Xand 1,2,3∈Nconstitute a local shift for (N, ˜q). By Lemma 2 (or Lemma 3), there is a local cycle for (N, ˜q). Hence, the priority structure ≻has a unit cycle. Corollary 3. ϕ≻is globally conversely consistent if and only if ϕ≻is globally consistent. References Balinski, M., and T. S¨onmez (1999): A Tale of Two Mechanisms: Student Placement, Journal of Economic Theory 84, 73–94. Ehlers, L. (2002): Coalitional Strategy-Proof House Allocation, Journal of Economic Theory 105, 298–317. Ehlers, L., and B. Klaus (2003): Resource-Monotonic House Allocation, International Journal of Game Theory 32, 545–560. Ehlers, L., and B. Klaus (2006): Efficient Priority Rules, Games and Economic Behavior 55, 372–384. Ehlers, L., and B. Klaus (2007): Consistent House Allocation, Economic Theory 30, 561–574. Ehlers, L., B. Klaus, and S. P´apai (2002): Strategy-Proofness and Population-Monotonicity for House Allocation Problems, Journal of Mathematical Economics 83, 329–339. Ergin, H. ˙ I. (2000): Consistency in House Allocation Problems, Journal of Mathematical Economics 34, 77-97. Ergin, H. ˙ I. (2002): Efficient Resource Allocation on the Basis of Priorities, Econometrica 70, 2489–2497. Gale, D., and L.S. Shapley (1962): College Admissions and the Stability of Marriage, The American Mathematical Monthly 69, 9–15. Kesten, O. (2006): On Two Competing Mechanisms for Priority-Based Allocation Problems, Journal of Economic Theory 127, 155–171. ¨ Ozkal-Sanver, ˙ I (2009): Minimal Converse Consistent Extension of the Men-Optimal Solution, Murat Sertel Center for Advanced Economic Studies Working Paper 1. 16 Roth, A.E. (1982): The Economics of Matching: Stability and Incentives, Mathematics of Operations Research 7, 617–628. Roth, A.E. (1984): The Evolution of the Labor Market for Medical Interns and Residents: a Case Study in Game Theory, Journal of Political Economy 92, 991–1016. Roth, A.E. (1985): The College Admissions Problem is not Equivalent to the Marriage Problem, Journal of Economic Theory 36, 277–288. Roth, A.E., and M.A.O. Sotomayor (1990): Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Econometric Society Monograph Series. New York: Cambridge University Press. Sasaki, H., and M. Toda (1992): Consistency and Characterization of the Core of Two-Sided Matching Problems, Journal of Economic Theory 56, 218–227. Thomson, W. (2004): Consistency and its Converse: an Introduction. University of Rochester. Mimeo. Thomson, W. (2009): Consistent Allocation Rules (Version: June 8, 2009). University of Rochester. Mimeo. Thomson, W., and L. Zhou (1993): Consistent Solutions in Atomless Economies, Econometrica 61, 575–587. 17