scieee AI-readable full text Open interactive document viewer

Pair-efficient reallocation of indivisible objects

Ekici, Özgün

Abstract

EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.

Full text

Ekici, Özgün Article Pair-efficient reallocation of indivisible objects Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Ekici, Özgün (2024) : Pair-efficient reallocation of indivisible objects, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 19, Iss. 2, pp. 551-564, https://doi.org/10.3982/TE5471 This Version is available at: https://hdl.handle.net/10419/320245 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Theoretical Economics 19 (2024), 551–564 1555-7561/20240551 Pair-efficient reallocation of indivisible objects Özgün Ekici Department of Economics, Ozyegin University We revisit the classical object reallocation problemunder strict preferences. When attention is constrained to the set of Pareto-efficient rules, it is known that top trading cycles (TTC) is the only rule that is strategy-proof and individually rational. We relax this constraint and consider pair efficiency. A rule is pair-efficient if it never induces an allocation at which a pair of agents gain from trading their assigned objects. Remarkably, even in the larger set of pair-efficient rules, we find that TTC is still the only rule that is strategy-proof and individually rational. Our characterization result gives strong support to the use of TTC in object reallocation problems. Keywords. Indivisible object, pair efficient, strategy-proof, individually rational, top trading cycles. JEL classification. C78, D61, D63, D82. 1. Introduction This paper considers the object reallocation problem: There is a group of agents, each of whom initially owns a distinct indivisible object. Agents have strict preferences over objects. Each agent’s preference information is private. A rule specifies how to reallocate objects based on the preference information reported by agents. We study object reallocation as a mechanism design problem: We are interested in rules satisfying desirable properties (axioms). We take two properties to be indispensable. First, the rule should incentivize agents to report preference information truthfully. We are interested in strategy-proof rules under which an agent never gains from misreporting. When this property is not satisfied, agents may strategize, which requires acquiring information about other agents’ preferences and formulating better strategies. This process is arguably tiresome and wasteful. Second, we demand that the rule never assigns an agent an object worse than her endowment (the object that she owns). A rule satisfying this property is said to be individually rational. If a rule is not individually rational, agents may opt out. Therefore, individual rationality is a minimal voluntary participation constraint. In an elemental result, Ma (1994) showed that when attention is constrained to the set of Pareto-efficient rules, the only strategy-proof and individually-rational rule is top Özgün Ekici: [email protected] This paper greatly benefited from various comments and suggestions by Jay Sethuraman, William Thomson, and an anonymous referee. An abstract of the manuscript appeared in the proceedings of the 23rd ACM Conference on Economics and Computation (EC’22), July 11–15, 2022, Boulder, CO, USA. ©2024 The Author. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE5471 552 Özgün Ekici Theoretical Economics 19 (2024) trading cycles (TTC). Pareto efficiency is a natural efficiency requirement and, therefore, the result by Ma (1994) gives strong support to the use of TTC in object reallocation problems. This rule reallocates objects to agents in a stepwise manner by identifying and executing “top trading cycles.” A top trading cycle, or for short, a cycle, involves a group of agents who own one another’s favorite objects. When these cycles are executed, each agent involved in a cycle is assigned her favorite object. Then these agents and their assigned objects are removed from consideration, which leaves a reduced problem with a smaller number of agents and their endowments. In the reduced problem, new cycles are identified and executed similarly, and so on. TheresultbyMa(1994) shows that to find strategy-proof and individually-rational rules other than TTC, one must relax the efficiency requirement. In this study, we do just that and substitute Pareto efficiency with pair efficiency. Pareto efficiency requires that at any induced allocation, no group of agents can gain from trading their assignments. In contrast, pair efficiency only requires that no pair of agents can gain from trading their assignments. Put differently, at an outcome, Pareto-efficiency rules out every efficiencyimproving trade, but pair efficiency only rules out efficiency-improving trades involving pairs of agents. Since any efficiency-improving trade must involve at least two agents, pair efficiency is arguably a minimal efficiency requirement. We illustrate the extent to which pair efficiency relaxes Pareto efficiency in Example 1in Section 2.2. In the example, for n≥7 agents, we describe a preference profile according to which there is a single Pareto-efficient allocation but the number of pair-efficient allocations exceeds 2n. Our relaxation of the Pareto-efficiency requirement also has a practical motivation. In this line of research, the literature focuses only on the welfare of the agents who trade objects, but we may imagine situations in which the social planner also has a stake in the outcome. For instance, when an employer (social planner) reallocates tasks (objects) to employees (agents), he may be interested in an outcome at which tasks will be performed productively. If the social planner cares about the outcome, the actual Pareto-efficient set of allocations becomes a superset of the set of allocations that are Pareto-efficient based only on agents’ preferences. Indeed, for purposes of implementation, pair efficiency may be a more suitable requirement than Pareto efficiency. If an allocation is not Pareto-efficient, it admits an efficiency-improving trade. Therefore, after its implementation, agents could trade their assignments and destabilize the allocation. However, it would be a premature conclusion to say that a Pareto-inefficient allocation will always be destabilized. If the associated efficiency-improving trade cycles are all large, involving many agents, agents may find it hard to recognize and coordinate such trades. Therefore, after its implementation, the allocation may remain stable. However, the same argument cannot be made if an efficiency-improving trade involves only a pair of agents. A mutually beneficial pairwise exchange is easier to recognize and execute for the involved agents. Therefore, for implementation purposes, while Pareto efficiency may be too demanding, pair efficiency is a natural minimal requirement. Although pair efficiency is a significant relaxation of Pareto efficiency, remarkably, the main result of our paper shows that in object reallocation, this relaxation does not give rise to new allocation rules. In Theorem 1, we show that TTC is characterized by 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5471 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Pair-efficient reallocation 553 the properties of strategy-proofness, individual rationality, and pair efficiency. Put differently, even if the Pareto-efficiency requirement is relaxed and substituted by pair efficiency, TTC still turns out to be the unique strategy-proof and individually rational rule satisfying this property. As mentioned above, individual rationality is a minimal voluntary participation constraint and pair efficiency is a minimal efficiency requirement. Therefore, by showing that TTC is the only strategy-proof rule that satisfies these two minimal conditions, our main result gives very strong support for its use in object reallocation problems. The characterization result by Ma (1994) follows as a corollary of our Theorem 1. The notion of pair efficiency has been explored in previous research in the context of the reallocation of divisible resources. Feldman (1973) explored the dynamics of pairwise barter trade to achieve a pairwise optimal allocation. Goldman and Starr (1982) introduced the more general t-wise optimality notion and developed necessary conditions and sufficient conditions for t-wise optimality to imply Pareto optimality. However, to our knowledge, ours is the first study that explores the concept in the context of the reallocation of indivisible resources. We believe that a key contribution of our paper is our novel proof technique. Exploiting the procedural nature of TTC, we define an index that measures the level of similarity of outcomes induced by an arbitrary rule and TTC. This similarity index lies at the heart of our proof by minimal counterexample when showing Theorem 1. We believe that in future studies, working with a similarity index can also be useful while studying the properties of other procedural rules. The rest of the paper is organized as follows. The following subsection presents other related research. Section 2introduces the model and TTC. Section 3presents our main result. 1.1 Other related research The object reallocation problem was introduced by Shapley and Scarf (1974). The TTC rule is also first mentioned in their paper. They attributed it to David Gale and mentioned that it finds a core allocation. Roth and Postlewaite (1977) later showed that there is only one allocation in the core, which is found by TTC. Roth (1982)provedthatTTCis strategy-proof; Bird (1984) showed that it is coalitionally strategy-proof. There are several characterization studies on TTC in the literature. As mentioned above, Ma (1994) showed that TTC is the only rule that is strategy-proof, individually rational, and Pareto-efficient. Svensson (1994), Anno (2015), and Sethuraman (2016) provided shorter proofs of this result. Miyagawa (2002) showed that a rule that is strategy-proof, individually rational, anonymous, and nonbossy is either TTC or the endowment rule. In a more recent study, Fujinaka and Wakayama (2018) characterized TTC in terms of strategy-proofness, individual rationality, and endowments-swappingproofness. This last property means that a pair of agents cannot both gain from trading their endowed objects before the rule is implemented. Notice that while pair efficiency is an efficiency criterion, endowments-swapping-proofness is a nonmanipulability notion. For two other characterization studies on TTC, see Takamiya (2001) and Morrill (2013). 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5471 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 554 Özgün Ekici Theoretical Economics 19 (2024) In their paper, Hylland and Zeckhauser (1979) considered the object allocation problem, in which agents have no private endowments and objects are initially collectively owned. Abdulkadiroglu and Sönmez (1999) introduced the mixed-ownership extension of the object allocation problem. There is a line of research in the literature identifying classes of rules in object allocation and reallocation problems. In these studies, Pareto efficiency plays a pivotal role as the efficiency criterion: In a general class of allocation problems, Sönmez (1999) showed that there exists a Pareto-efficient, individuallyrational, and strategy-proof solution only if the core is essentially single-valued (as in the object reallocation problem). In the mixed-ownership extension of the object allocation problem, Sönmez and Ünver (2010) characterized a class of rules by a set of properties that includes Pareto efficiency. In the object allocation problem, Pápai (2000) introduced hierarchical exchange rules and characterized them by the properties of Pareto efficiency, group-strategy-proofness, and reallocation-proofness. Later, Pycia and Ünver (2017) introduced an even larger class of rules called top cycles, and they characterized them by the properties of Pareto efficiency and group-strategy-proofness. 2. Model 2.1 Preliminaries Let I={1, 2, ,n}be a finite set of agents. Let O={o1,o2,,on}be a finite set of indivisible objects such that oidenotes agent i’s endowment. Agents are equipped with strict preferences over objects. Let P=(Pi)i∈Idenote a preference profile where Pidenotes agent i’s strict preference relation. If agent iprefers object oto ¯ oat Pi,wewriteoPi¯ o.LetRidenote the at least as good as relation associated with Pi.Thus,oRi¯ omeans oPi¯ oor o=¯ o. When convenient, we describe a preference relation as an ordering of objects, from agent’s first choice to last choice. Let Pbe the set of strict preference relations over O.Thus,Pi∈Pand P∈Pn. Sometimes, we work with mixed profiles. For S⊆I,(¯ PS,PI\S)denotes the mixed profile such that for i∈S, the preference relation is ¯ Pi(as under profile ¯ P), and for i∈ I\S, the preference relation is Pi(as under profile P). If S={i},wesimplywrite(¯ Pi,PI\i). Later in the text, we work with a mixed profile (P+ i1,P↑ i2,P↑ i3,,P↑ ik,PI\S). This means that the preference relation is P+ i1for i1,P↑ isfor is∈{i2,,ik},andPifor i∈I\S.Other mixed profile notations are understood accordingly. An allocation assigns an object to each agent. A rule recommends an allocation for each preference profile. The formal definitions are as follows. An allocation μ:I→Ois a one-to-one mapping from the set of agents to the set of objects. For i∈I,μ(i)denotes agent i’s assignment at μ.Let Mdenote the set of allocations. Arule φ:Pn→Mis a mapping from the set of preference profiles to the set of allocations. That is, a rule φassociates each profile Pwith an allocation φ(P).Fori∈I, φi(P)denotes agent i’s assignment at φ(P). 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5471 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Pair-efficient reallocation 555 2.2 Axioms We introduce next the axioms (properties) that are central to our analysis. As a nonmanipulability condition, we consider strategy-proofness. Agents cannot manipulate (gain by misreporting) under a strategy-proof rule. The formal definition is as follows. An agent ican manipulate a rule φat profile Pby misreporting her preferences as ¯ Pi∈P(¯ Pi= Pi)ifφi(¯ Pi,PI\i)Piφi(P).Aruleφis strategy-proof if no agent can manipulate it at any preference profile. That is, under a strategy-proof rule, reporting true preferences is a weakly dominant strategy. As a voluntary participation condition, we consider individual rationality, which requires that an agent is never assigned an object worse than her endowment. Agents may opt out of an allocation rule if this condition is not satisfied. The formal definition is as follows. An allocation μis individually rational at Pif for each i∈I,μ(i)Rioi.Aruleφis individually rational if for each P∈Pn, the allocation φ(P)is individually rational at P. We will consider two efficiency notions. The first one is Pareto efficiency, which rules out at the outcome efficiency-improving trades between any group of agents. The second one is the weaker pair-efficiency notion, which only rules out efficiency-improving trades between pairs of agents. The formal definitions are as follows. An allocation μis Pareto-efficient at Pif there exists no allocation ¯μsuch that for each i∈I,¯μ(i)Riμ(i), and for some i∈I,¯μ(i)Piμ(i).Aruleφis Pareto-efficient if for each P∈Pn, the allocation φ(P)is Pareto-efficient at P. An allocation μis pair-efficient at Pif there do not exist i,j∈I,i= j,suchthat μ(i)Pjμ(j)and μ(j)Piμ(i).Aruleφis pair-efficient if for each P∈Pn, the allocation φ(P)is pair-efficient at P. By definition, pair efficiency is a weaker notion than Pareto efficiency. We illustrate the extent to which pair efficiency relaxes Pareto efficiency in Example 1. In the example, we introduce a “circular” preference profile under which there is a single Pareto-efficient allocation, but the number of pair-efficient allocations exceeds 2nwhen there are n≥7 agents. Example 1. We will consider a circular preference profile Pnunder which objects can be labeled as x1,x2,,xnsuch that for each agent i,xiPn ixi+1Pn iPn ixi+n−1,where xn+s=xs. This is illustrated in Figure 1.UnderPn, objects can be placed around a circle Figure 1. Preferences under a circular profile. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5471 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 556 Özgün Ekici Theoretical Economics 19 (2024) such that for each agent i, her preference ranking runs clockwise from her first choice xi to her last choice xi−1. Under Pn, there is one Pareto-efficient allocation, where each agent ireceives her first choice, xi.UnderPn,letF(n)be the number of pair-efficient allocations. We will show that F(n)>2nfor n≥7. Let f(n,s)be the number of pair-efficient allocations that assign exactly sout of n agents to their first choices. Then F(n)=n s=0f(n,s). Next, we will calculate f(n,s). Our calculation is recursive and depends on a key observation. Notice that under Pn, we can construct the pair-efficient allocations for which sagents receive their first choices in two steps as follows. •We select sout of nagents and match them with their first choices. •If s<n, we are left with a reduced problem with n−sagents and n−sobjects. In the reduced problem, we choose a pair-efficient matching at which no agent receives her first choice. This matching, combined with the matches of sagents to their first choices, induces a pair-efficient allocation in our original problem with nagents and nobjects. Note that sout of nagents can be selected in n sways. Also, in a problem with n−sagents and n−sobjects, by definition, there are f(n−s,0 )pair-efficient matchings at which no agent receives her first choice. Thus, f(n,s)=n sf(n−s,0 ).To make this formula work for s=n,wesetf(0, 0)=1. Also, notice that, by definition, f(1, 0)=f(2, 0)=0. Thus, we get F(n)= n  s=0n sf(n−s,0 ). Let n≥7. We will also assume that nis odd. Thus, n=2k+1forsomek≥3. The assumption that nis odd is not essential for our arguments, but it helps simplify the exposition below. The interested reader can show that with a minor adjustment, our subsequent arguments can be used to show the desired result for neven, too. Using the facts that n n−s=n sand n s=0n s=2n, with some algebraic manipulation, we get F(n)= n  s=0n s+ n  s=0n sf(n−s,0 )−1 =2n+ k  s=0n sf(n−s,0 )+f(s,0 )−2. To show that F(n)>2n, it suffices to show that in the above summation, the term f(n−s,0 )+f(s,0 )−2 is always nonnegative and it is positive for s=0. One can easily verify that under a circular profile with 2t−1or2tagents where t≥2, we get a pair-efficient allocation when each agent receives her lth-best object for l∈ 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5471 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Pair-efficient reallocation 557 {2, 3, ,t}. Since n≥7, this implies the following inequalities: For s=0, f(n−s,0 )≥3; for s∈{1, 2},f(n−s,0 )≥2; for s∈{3, 4, ,k},f(n−s,0 )≥1andf(s,0 )≥1. Thus, as required, the term f(n−s,0 )+f(s,0 )−2 is always nonnegative and it is positive for s=0. Thus, F(n)>2n. 2.3 Top trading cycles We introduce next the top trading cycles (TTC) rule. Atop trading cycle, or for short, a cycle, is a sequence of distinct agents and objects such that each agent in the cycle points to her favorite object and each object points to its owner. A cycle can be illustrated as i1→oi2→i2→oi3→···→ik−1→oik→ik→oik+1→ik+1=i1. Above, i1,i2,,ikare distinct agents. Agent ispoints to object os+1and os+1points to its owner is+1for s=1, ,k. Thereby, the cycle forms. The size of a cycle is the number of agents involved in that cycle. For instance, the size of the cycle indicated above is k.Wewrite|C|to indicate the size of a cycle C. For two cycles C1and C2, we say that C1is smaller than C2if |C1|<|C2|or if |C1|= |C2|and in these two cycles, the agent whose index is smallest is in cycle C1.Inagroup of cycles, the smallest cycle is the one that is smaller than the others. Note that given two cycles, if no agent is part of both cycles, one of them must be smaller than the other. Additionally, given a group of cycles, if no agent is part of multiple cycles, one cycle in the group must be the smallest. In the rest of the paper, when we make size comparisons, no agent will be part of multiple cycles. Therefore, in the groups of cycles that we consider, the smallest cycle will always be well defined. As an illustration, suppose that we are considering the group of cycles C1,C2,C3such that C1 comprises the agents 2, 7, C2comprises the agents 3, 6, and C3comprises the agents 1, 4, 5. Then the group’s smallest cycle is C1:C1is smaller than C3because |C1|=2and |C3|=3; C1is also smaller than C2because |C1|=|C2|=2, but in these two cycles, 2 is the agent whose index is smallest and it is part of C1. When a cycle is executed, it means every agent involved in that cycle is assigned the object to which she points. For instance, if the cycle illustrated above is executed, agent isis assigned object ois+1for s=1, ,k. When we say that an allocation executes a cycle, it means that at that allocation, every agent involved in that cycle is assigned the object to which she points. For instance, if allocation μexecutes the cycle illustrated above, then μ(is)=ois+1for s=1, ,k. The TTC rule, which is subsequently presented in a formal format, proceeds in a stepwise manner as follows. Every agent points to her favorite object and every object points to its owner. This gives rise to one or more cycles. These cycles are executed. In the next step, these agents and their assigned objects are removed from consideration. This leaves a reduced problem with a smaller number of agents and objects. The rule then operates on the reduced problem by identifying and executing new cycles, and so on. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5471 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 558 Özgün Ekici Theoretical Economics 19 (2024) It turns out that under TTC, the order in which cycles are executed is inconsequential.1For instance, let C1and C2be the cycles that arise at Step 1. One possibility is that we execute both C1and C2, and then proceed to Step 2. Alternatively, we can execute only C1and then proceed to Step 2. In this latter scenario, at Step 2, C2still remains. However, the execution of C1at Step 1 may trigger the formation of some new cycles, say C3and C4. Then we get three cycles at Step 2: C2,C3,C4. At Step 2, we may execute any combination of these three cycles and then proceed to Step 3. Ultimately, the same allocation is induced by TTC, independent of the order in which the cycles that arise are executed. However, to show our main result, we need a specification of the TTC rule that exactly pinpoints which cycle is executed at which step. To this end, we will assume that at any point in time, TTC proceeds by executing only the smallest cycle (as defined above). We introduce this specification of TTC below. Top Trading Cycles Given a preference profile, TTC finds an allocation in a stepwise manner as follows. Step 1. Construct a directed graph as follows. The nodes are agents and objects. For each agent, there is an edge from that agent to her favorite object. For each object, there is an edge from the object to its owner. Since there is an outgoing edge from each node and the nodes are finite, this gives rise to one or more cycles. Execute the smallest cycle among them. If a node remains, proceed to Step 2. Otherwise, terminate. Step t≥2. With remaining agents and objects, construct a new directed graph as follows. The nodes are agents and objects. For each agent, there is an edge from that agent to her favorite (remaining) object. For each object, there is an edge from the object to its owner. Since there is an outgoing edge from each node and the nodes are finite, this gives rise to one or more cycles. Execute the smallest cycle among them. If a node remains, proceed to Step t+1. Otherwise, terminate. In the rest of the paper, when we speak of TTC, it is understood that we mean its above specification. 3. Main result Theorem 1. TTC is the only rule that is strategy-proof, individually rational, and pairefficient. Ma (1994) showed that in the set of Pareto-efficient rules, TTC is the only rule that is strategy-proof and individually rational. Since pair efficiency is a relaxation of Pareto efficiency, his characterization result follows as a corollary of Theorem 1. In his paper, Ma (1994) also showed that strategy-proofness, individually rationality, and Pareto efficiency are independent axioms. That is, via three examples, he showed that a rule that satisfies two of these axioms need not satisfy the third one. The three examples in his paper can also be used to show the independence of the three axioms in Theorem 1.For the examples, the interested reader may refer to his paper. The rest of the paper is devoted to the proof of Theorem 1.Section3.1 describes our proof technique and introduces some tools. Section 3.2 presents our proof. 1See Remark 1 in Abdulkadiroglu and Sönmez (1999) and Lemma 6 in Carroll (2014). 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5471 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License