Serial Rules in a Multi-Unit Shapley-Scarf Market

Games and Economic Behavior 136 (2022) 428–453 Contents lists available at ScienceDirect Games and Economic Behavior journal homepage: www.elsevier.com/locate/geb Serial Rules in a Multi-Unit Shapley-Scarf Market✩ Péter Biróa,b,1, Flip Klijnc,d,∗,2, Szilvia Pápaie,3 aInstitute of Economics, Research Centre for Economic and Regional Studies, Hungarian Academy of Sciences, Hungary bDepartment of Operations Research and Actuarial Sciences, Corvinus University of Budapest, Hungary cInstitute for Economic Analysis (CSIC), Spain dBarcelona School of Economics, Spain eDepartment of Economics, Concordia University, Canada a r t i c l e i n f o a b s t r a c t Article history: Received 17 May 2021 Available online 18 October 2022 JEL classification: C72 C78 D61 Keywords: Indivisible goods Circulation Shapley-Scarf market Serial dictatorship Efficiency We study generalized Shapley-Scarf exchange markets where each agent is endowed with multiple units of an indivisible and agent-specific good and monetary compensations are not possible. An outcome is given by a circulation which consists of a balanced exchange of goods. We focus on circulation rules that only require as input ordinal preference rankings of individual goods, and agents are assumed to have responsive preferences over bundles of goods. We study the properties of serial dictatorship rules which allow agents to choose either a single good or an entire bundle sequentially, according to a fixed ordering of the agents. We also introduce and explore extensions of these serial dictatorship rules that ensure individual rationality. The paper analyzes the normative and incentive properties of these four families of serial dictatorships and also shows that the individually rational extensions can be implemented with efficient graph algorithms. ©2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). 1. Introduction Background Many different situations call for exchanging goods, services, or other items of interest in a centralized manner without using money or prices that facilitate the exchange. In a student exchange program, for instance, universities send exchange ✩We thank the editor, an associate editor, and two anonymous reviewers for their comments that helped to improve the paper. We also thank seminar and workshop participants at Boston College, Keio University (Third International Workshop on Market Design Technologies for Sustainable Development), Université Paris Dauphine, Corvinus Game Theory Seminar, 10th Matching in Practice workshop (Toulouse), Workshop on Game Theory and Social Choice (Budapest), 21st CTN Workshop (Moscow), 2016 GTMD conference (St. Petersburg), 2016 GAMES Congress (Maastricht), MATCH-UP 2017 Conference (Boston), Lausanne Economic Theory Workshop 2017, 1st Catalan Economic Society Conference, Axiomatizations in Game Theory Workshop (Pécs), and in particular Haris Aziz, Jérôme Lang, Julien Lesca, Rosemarie Nagel, Hans Peters, Madhav Raghavan, Tayfun Sönmez, William Thomson, and Utku Ünver for their comments and suggestions. *Corresponding author. E-mail addresses: peter[email protected] (P. Biró), flip.kli[email protected] (F. Klijn), [email protected] (S. Pápai). 1P. Biró gratefully acknowledges the financial support by the Hungarian Academy of Sciences, Momentum Grant No. LP2021-2, and by the Hungarian Scientific Research Fund, OTKA, Grant No. K143858. 2F. Klijn gratefully acknowledges financial support from AGAUR–Generalitat de Catalunya (2017-SGR-1359) and the Spanish Agencia Estatal de Investigación (AEI) through grants ECO2017-88130-P and PID2020-114251GB-I00 (funded by MCIN/ AEI /10.13039/501100011033) and the Severo Ochoa Programme for Centres of Excellence in R&D (Barcelona School of Economics, SEV-2015-0563 and CEX2019-000915-S). 3S. Pápai gratefully acknowledges financial support from an FRQSC grant titled “Formation des coalitions et des réseaux dans les situations économiques et sociales avec des externalités” (SE-144698). https://doi.org/10.1016/j.geb.2022.10.006 0899-8256/©2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 students to other universities and receive exchange students from elsewhere in return. Centralized transplant exchanges at a national level or internationally are also important examples, since buying and selling organs is prohibited in most countries. Various websites support the bartering of goods such as clothing and books, or swapping services based on professional skills. Similarly, time banks serve the purpose of exchanging different services in a beneficial manner in a town or neighborhood. The reallocation of shifts in healthcare, swapping sabbatical homes, and timeshare exchanges which allow for trading holiday rights in specific resorts are further examples of exchange without making any payments. Even the financial sector has cases of cyclic liabilities that can be resolved using financial clearing, which means the releasing of financial liabilities in a cyclic manner without further compensation. Some of the pertinent common features of these exchanges can be captured by the simple circulation model introduced by Biró et al. (2022). Each market in this circulation model is a generalized Shapley-Scarf market (Shapley and Scarf, 1974), where agents are endowed with multiple units of an indivisible and agent-specific good. It is often desirable, if not crucial, to obtain a balanced exchange in these exchange markets, i.e., for each agent the number of units of other goods received equals the number of units of her own good given to other agents. We therefore require that the outcome of a market be given by a circulation, which consists of a balanced exchange of goods. Furthermore, we study circulation rules which take as input preferences over individual goods only. These types of rules are attractive in practical situations where it may be difficult to elicit complex preferences over bundles of goods. For classical Shapley-Scarf markets, where each agent is endowed with one unit of her good, one exchange rule stands out on the domain of strict preferences: David Gale’s celebrated Top Trading Cycles (TTC) rule. Gale’s TTC rule is the unique rule that satisfies three key properties, namely individual rationality,4Pareto-efficiency,5and strategy-proofness6in the classical Shapley-Scarf markets (Ma, 1994). Biró et al. (2022)showed that for generalized Shapley-Scarf markets there is no circulation rule that satisfies the combination of individual rationality, a weak version of Pareto-efficiency, and a weak version of strategy-proofness. Given this incompatibility, Biró et al. (2022) explored to what extent two natural generalizations of the TTC rule satisfy these and other properties. In particular, they found that these rules do not have good efficiency properties. One source of inefficiency are the multiple ways in which preferences over individual goods can be extended to preferences over bundles: TTC-based rules do not properly take into account that some agent may prefer bundles that contain her top good together with some rather inferior good while some other agent may prefer, to the contrary, “intermediate” bundles, see Biró et al. (2022, Proposition 3) for more details. Our approach and motivation In this paper, we take a different approach. Assuming that there is a natural order of the agents determined by e.g. priority or seniority, an intuitive assignment procedure is to let the agents pick their most preferred goods or bundles following this order, known in general as a serial dictatorship. Priority rules or serial dictatorships are not only natural and common in many practical situations, but they can be more easily explained and “understood” than TTC-inspired rules; practitioners or participants in these markets may not have an adequate background to properly understand or appreciate the latter. Moreover, as it turns out, serial dictatorship rules tend to have better efficiency properties in the circulation model compared to TTC-based rules.7 Pareto efficiency and individual rationality of circulations are more basic requirements than – and incompatible with – strategy-proofness. However, in practice, agents may not be able to report more than an ordinal ranking of the individual goods. Therefore, achieving Pareto efficiency plus individual rationality based on such lean reports raises both an existence and computational complexity issue.8In this context we study serial dictatorship rules for the circulation model. 1.1. Illustrative examples We first illustrate the working of the families of serial dictatorship rules that we study. Consider a market with three agents: N={1, 2, 3}. Agent 1 has capacity q1=1 and agents 2 and 3 have capacity q2=q3=2. Initially each agent iis endowed with a “null bundle” that consists of qiunits of her own good. Since goods are agent-specific we will refer to the good of agent ias good i. Each agent is interested in obtaining a bundle of exactly qiunits of possibly different goods in total. Let the agents’ preferences over individual goods in this market be given as follows: 1 :2 11 13 2 :3 21 22 3 :2 33 31 Here, for example, agent 3 prefers good 2 to her own good, but finds good 1 unacceptable (i.e., worse than her own good). 4A rule is individually rational if at each problem it assigns an acceptable bundle to each agent. 5A rule is Pareto-efficient if at each problem the assigned circulation is not Pareto-dominated by some other circulation, i.e., it is not possible to make all agents weakly better off and at least one agent strictly better off. 6A rule is strategy-proof if at each problem no agent can obtain a more preferred bundle by misrepresenting her preferences. 7A summary of the efficiency properties of the families of serial dictatorship rules studied in this paper is provided in Table 5in Section 6.1. 8For instance, Pareto-efficiency of our so-called Multiple-Serial-IR rules follows by definition; the difficulty is in showing that the rules operate on the underlying profiles of ordinal preferences of individual goods (Theorem 15). 429 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 We assume that agents’ preferences over bundles are “responsive” to preferences over individual goods: (1) an agent finds a bundle unacceptable if it contains any unacceptable good9and (2) preferences are monotonic in the sense that replacing one unit of a good in a bundle by one unit of a more preferred good yields a more preferred bundle. The agents’ preferences over bundles are partially determined by responsiveness. For instance, in the case of agent 3, the bundle (1, 1, 0) that consists of one unit of good 1 and one unit of good 2 is not acceptable (i.e., worse than agent 3’s null bundle (0, 0, 2)) because it contains a unit of the unacceptable good 1. Also, agent 3 prefers bundle (0, 2, 0)to bundle (0, 1, 1)because the former is obtained from the latter by replacing one unit of a good by a more preferred good. Responsiveness typically does not pin down the complete preference relation over bundles: for example, in the case of agent 2 responsiveness does not tell which of the two acceptable bundles (2, 0, 0)and (0, 1, 1)is preferred to the other bundle. Using this market, we demonstrate the four families of rules that we study in this paper. For each family of rules all goods are first collected and then agents pick single goods/bundles sequentially. More specifically, the common feature of the allocation processes that we explore is that we start with the “empty allocation” and then agents sequentially, following a fixed order, take one good or a complete bundle in turn until their capacities are reached. At the end of the sequential process we obtain a circulation that is not necessarily individually rational. However, if we require the intermediate allocations to be extendable to an individually rational circulation then our final circulation will also be individually rational. First we illustrate the so-called Single-Serial rules where agents select the goods one by one, together with their individually rational counterparts, the Single-Serial-IR rules. Then we demonstrate the so-called Multiple-Serial rules where agents choose complete bundles sequentially, as well as their individually rational counterparts, the Multiple-Serial-IR rules. Single-Serial rules. This first family of rules lets agents pick a single good at a time following a fixed order. Each agent i appears qitimes in the fixed order. As an illustration, we consider the Single-Serial rule based on the order π=(1, 2, 3, 2, 3). Following π, at each step an agent picks her most preferred available good, as depicted in Table 1. Thus, the resulting bundles are x1=(0, 1, 0), x2=(0, 0, 2), and x3=(1, 1, 0), for agents 1, 2, and 3, respectively. Note that at step 5 agent 3 was obliged to pick the only remaining (unit of) good 1. Since good 1 is unacceptable to agent 3, her bundle x3is unacceptable. Therefore, the circulation x ≡(xi)i∈Nobtained by the Single-Serial rule is not individually rational. Table 1 Single-Serial rule. atstep 12345 agent 12323 picksgood23231 Single-Serial-IR rules. The family of Single-Serial-IR rules is obtained by adapting the family of Single-Serial rules to ensure individual rationality. Specifically, at each step an agent picks her most preferred good among the available goods such that this choice is compatible with an individually rational final circulation. Using again the order π=(1, 2, 3, 2, 3), the goods that are picked are shown in Table 2. Steps 1–3 are the same in Tables 1and 2. However, at step 4, agent 2 is obliged to pick good 1 to ensure that at the last step agent 3 can pick an acceptable good. Thus, the resulting bundles are y1=(0, 1, 0), y2=(1, 0, 1), and y3=(0, 1, 1), for agents 1, 2, and 3, respectively. By construction, the circulation y ≡(yi)i∈Nobtained by the Single-Serial-IR rule is individually rational. Table 2 Single-Serial-IR rule. atstep 12345 agent 12323 picksgood23213 Multiple-Serial rules. The third family of rules lets agents sequentially pick a complete bundle following a fixed order. Hence, each agent appears once in the fixed order. As an illustration, we consider the Multiple-Serial rule based on the order ¯ π=(2, 1, 3). Following ¯ π, at each step an agent picks her most preferred available bundle from the available goods, as depicted in Table 3. Note that at step 3 agent 3 was obliged to pick the remaining goods: one unit of good 1 and one unit of good 2. Since good 1 is unacceptable to agent 3, her bundle is unacceptable. Therefore, the circulation obtained by the Multiple-Serial rule is not individually rational. Table 3 Multiple-Serial rule. at step 1 2 3 agent 2 1 3 picks bundle (0,0,2) (0,1,0) (1,1,0) 9This assumption and its possible relaxation are discussed in Section 6.3. 430 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 Multiple-Serial-IR rules. The last family of rules is obtained by adapting the family of Multiple-Serial rules to ensure individual rationality. Specifically, at each step an agent picks her most preferred bundle from the available goods such that this choice is compatible with an individually rational final circulation. Using again the order ¯ π=(2, 1, 3), the bundles that are picked are shown in Table 4. Step 1 is the same in Tables 3and 4. However, at step 2 agent 1 is obliged to pick good 1 to ensure that at the last step agent 3 can pick an acceptable bundle. By construction, the circulation obtained by the Multiple-Serial-IR rule is individually rational. Table 4 Multiple-Serial-IR rule. at step 1 2 3 agent 2 1 3 picks bundle (0,0,2) (1,0,0) (0,2,0) 1.2. Our main contributions We first show that if a circulation is Pareto-efficient then it can be obtained by some Single-Serial rule (Proposition 2). Hence, Single-Serial rules are exhaustive in the sense that they yield all Pareto-efficient circulations. However, as the illustrative example shows, Single-Serial rules are not necessarily individually rational. Moreover, we show that when they do yield an individually rational circulation it is only guaranteed to be Pareto-efficient for lexicographic preferences (Lemma 1 and Example 2). Single-Serial-IR rules are by definition individually rational. Since checking whether an intermediate allocation can still be extended to an individually rational circulation is non-trivial, it is important to show that the Single-Serial-IR rules can be implemented efficiently, i.e., in polynomial time. We prove this by establishing that extendability to an individually rational circulation is equivalent to the existence of a maximum flow in an associated maximum flow problem. More specifically, this equivalence allows us to give an alternative definition of Single-Serial-IR rules (Theorem 7) and then, using the FordFulkerson theorem, show its efficient implementation (Corollary 10). Finally, we prove that Single-Serial-IR rules are Paretoefficient for lexicographic preferences and any individually rational and Pareto-efficient circulation can be obtained by some Single-Serial-IR rule (Proposition 11). While Multiple-Serial rules are Pareto-efficient by definition, they are not necessarily individually rational, as demonstrated by the illustrative example. We establish that Multiple-Serial-IR rules do satisfy both properties. The (non-trivial) key issue here is to show that Multiple-Serial-IR rules satisfy our requirement that they only depend on the ordinal preferences over individual goods (Theorem 15). Moreover, since Multiple-Serial-IR rules are particular Single-Serial-IR rules, they can be implemented efficiently (Corollary 16). 1.3. Organization of the paper In Section 2, we introduce the circulation model. In Sections 3and 4, we present our Single-Serial-(IR) rules and MultipleSerial-(IR) rules, respectively, and prove our main results on individual rationality, Pareto-efficiency, and computational complexity. In a separate section, Section 5, we show which of our rules also satisfy strategy-proofness or other weaker incentive properties. Section 6provides a concise summary of the properties satisfied by our rules, discusses generalized serial rules, and describes how our positive results may be extended to more general models. Finally, Section 7discusses the related literature and applications. 2. The circulation model Let Nwith n =|N| ≥2be the set of agents. Each agent i ∈Nis endowed with a finite number of qi∈Nunits of an indivisible, homogeneous, and agent-specific good. We call the non-negative integer qiagent i’s capacity. Let q =(qi)i∈Nbe the capacity profile. Since goods are agent-specific, for each i ∈N, we often refer to the good of agent ias good i. An assignment for agent iis a vector xi=(xij)j∈N∈NNwith j∈Nxij ≤qi, where xij denotes the amount (i.e., number of units) of good jthat ireceives. One particular assignment for agent iis the null assignment 0iwhere agent ireceives no good, i.e., for each j, 0ij =0. An allocation is a vector of assignments x =(xi)i∈Nsuch that for each good j ∈N, i∈Nxij ≤qj. A bundle for agent iis a vector xi=(xij)j∈N∈NNwith j∈Nxij =qi. Clearly, each bundle is an assignment. One particular bundle for agent iis the null bundle eiwhere agent ireceives no good different from her own, i.e., eij =0for all j = i, or equivalently, eii =qi. Let Xidenote the set of possible bundles for agent i. A circulation is a vector of bundles such that each agent receives as many goods as she gives away from her initial endowment. Formally, a circulation is a vector of bundles x =(xi)i∈N∈(Xi)i∈Nsuch that for each good j ∈N, i∈Nxij =qj. Let Xdenote the set of circulations. Each agent ihas preferences iover all individual goods, i.e., preferences over receiving a unit of good j ∈N\{i}and the option of receiving (retaining) a unit of her good i. We assume that iis a linear order on N, i.e., it is strict, complete, and transitive. For any j, l ∈Nwith j = l, j ildenotes that agent iprefers receiving one unit of good jover receiving one unit of good l. Let idenote the weak counterpart of i, i.e., j ilif and only if j ilor j =l. If j ii, then good jis acceptable to agent i; otherwise it is unacceptable to i. 431 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 Each agent ihas a linear order Pion the set of possible bundles Xi. A bundle xiis acceptable to iif xiPieior xi=ei; it is unacceptable to iotherwise. We assume that the preferences Piover Xiare a responsive extension of the associated preferences iover individual goods. Formally, Piis a linear order that satisfies the following two conditions. Let xi, x i∈ Xi. (r1) eiPixiif there is j ∈N\{i}with i ijsuch that xij >0; and (r2) x iPixiif there are j, l ∈Nwith j ilsuch that x ij =xij +1, x il =xil −1, and x ik =xik for all k ∈N\{ j, l}. Condition (r1) is a property of “absolute desirability”: it states that agent ifinds a bundle unacceptable if it contains some good that is unacceptable to her. Condition (r2) is a monotonicity property: it states that agent iprefers bundle x ito xiif x iis obtained from xiby replacing one unit of some good with one unit of a more preferred good. Remark 1. Note that if a bundle only contains acceptable goods to some agent then, by repeated application of (r2), the agent finds the bundle acceptable. Hence, it follows from (r1) and (r2) that a bundle is acceptable if and only if it only contains acceptable goods.  Let Ridenote the weak counterpart of Pi. So, xiRix iif either xiPix ior xi=x i. We denote the set of responsive preferences for agent iby Pi. Let P=× i∈NPibe the set of profiles of responsive preferences. A market is a triple (N, q, P)where P∈P, or simply P. For any responsive preferences Pi∈Piof agent i, we denote the underlying preferences over individual goods by Pi. For any P∈P, P=(Pi)i∈N. Whenever no confusion is possible we write ifor Piand for P. Next we introduce the classes of additive and lexicographic preferences. An agent has additive preferences if there is a (cardinal) utility function on the set of acceptable goods such that for any pair of acceptable bundles, the agent prefers the bundle with highest sum of utilities (of the goods in the bundle). We can assume without loss of generality that the utility of her own good equals 0. Formally, agent i’s responsive preferences Piare additive if there exists a utility function ui:{j ∈N:j ii} →R++ such that for all xi,x i∈Xiwith xi,x iRiei,⎡ ⎣x iPixiif and only if  j:jii x ijui(j)>  j:jii xijui(j)⎤ ⎦.(1) An agent has lexicographic preferences if whenever she compares any two acceptable bundles, she prefers the bundle with the largest number of units of her most preferred good; if the two bundles have the same number of units of her most preferred good, then she prefers the bundle with the largest number of units of her second most preferred good; etc. In other words, the agent first maximizes the number of units of her top good, then maximizes the number of units of her second most preferred good, and so on. Therefore, lexicographic preferences are a specific type of additive preferences, i.e., additive preferences that require a particular scheme of “strongly decreasing” utilities. Formally, agent i’s responsive preferences Piare lexicographic if there exists a utility function ui:{j ∈N:j ii} →R++ where for all k,lii,[kilif and only if ui(k)>qiui(l)](2) such that condition (1) holds. Condition (2)says that receiving a unit of the top good is “more important” than receiving any number of other goods, receiving a unit of the second most preferred good is “more important” than receiving any number of the third most preferred or less preferred goods, etc. When preferences are lexicographic, the ordinal ranking over acceptable bundles is completely determined by the ordinal ranking over individual goods.10 We denote the set of lexicographic preferences for agent iby PL i. Let PL=× i∈NPL ibe the set of profiles of lexicographic preferences. We require the exchange of the indivisible goods to be balanced. In other words, any outcome of a market should be a circulation. Our aim is to study rules that can be used by a centralized clearinghouse to obtain a circulation for each market. In practice such clearinghouses often only collect the ordinal preferences of the participating agents over individual goods. Moreover, given our assumption that preferences are responsive, the most important information about preferences is concisely summarized by the ranking of individual goods. For this reason we introduce the following definition of a circulation rule. Fix the set of agents Nand the vector of capacities q. A circulation rule f :P→Xspecifies a circulation for each preference profile. For each preference profile P∈P, fi(P)denotes agent i’s bundle at P. In view of the discussion above, we require circulation rules to operate on the underlying profiles of ordinal preferences over individual goods. In other words, for any two preference profiles, if each agent has the same underlying ordinal preferences over individual goods at both profiles, then a circulation rule yields the same circulation at both profiles. Formally, 10 None of our results requires a similar assumption on the ordinal ranking over unacceptable bundles. 432 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 for all P,P∈Pwith P= P,f(P)=f(P). (3) In fact, the first two families of rules that we study will be defined directly on the domain of ordinal preferences over individual goods, and hence satisfy (3)by definition. We first introduce the key desiderata. The first property that we consider indispensable is individual rationality, a standard property which requires that each agent receives a bundle that is acceptable to her. Definition 1. A circulation xis individually rational for agent i ∈Nat P∈Pif xiis acceptable, i.e., xiRiei, or equivalently, for each jwith xij >0, j Pii. A circulation xis individually rational at P∈Pif it is individually rational for all agents at P. A circulation rule fis individually rational if for all P∈P, f(P)is individually rational at P. Given the relatively simple structure and the particular interest of lexicographic preferences within the class of responsive preferences, we will examine two different versions of each property where applicable: “necessarily satisfied” and “possibly satisfied,” indicating whether the property holds for every responsive extension of the underlying preferences over individual goods, or only for the lexicographic extension that can be inferred from the ordering of individual goods. Thus, “necessarily satisfied” corresponds to the property being satisfied by the entire domain of responsive preferences and is the standard version of the property for responsive preferences over bundles. The “possibly satisfied” version is weaker; namely, it corresponds to the property being satisfied by the lexicographic extension of any preferences over the individual goods. Henceforth, we will denote the weaker version of each property by adding the prefix “ig” (the acronym for “individual good”) to the name of the standard version of the property. However, note that by Remark 1, the two versions of individual rationality are equivalent. In view of the discussion above, we introduce two versions of the other key property, Pareto-efficiency. Definition 2. A circulation xis Pareto-dominated by another circulation yat P∈Pif for each agent i ∈N, yiRixiand for some agent j ∈N, yjPjxj. A circulation rule fis (necessarily) Pareto-efficient if for all P∈P, f(P)is not Pareto-dominated by any other circulation at P. A circulation rule fis ig-Pareto-efficient if for all profiles of lexicographic preferences P∈PL, f(P)is not Pareto-dominated by any other circulation at P. Remark 2. Checking whether a circulation is Pareto-efficient for additive preferences is NP-hard (Aziz et al., 2019), where the input is given as the cardinal utilities of agents over the individual goods. On the other hand, checking ig-Pareto-efficiency of a circulation from the agents’ ordinal preferences is tractable in polynomial time (Aziz et al., 2015). This suggests that a centralized clearinghouse may find ig-Pareto-efficiency sufficient, especially since the agents may relatively easily detect if the circulation does not satisfy it. However, ensuring Pareto-efficiency (i.e., not “just” ig-Pareto-efficiency) is relevant beyond the detectability argument, as it is an important requirement from the point of view of social welfare.  Proposition 1 in Biró et al. (2022)shows that individual rationality and ig-Pareto-efficiency are not compatible with another important desideratum, ig-strategy-proofness.11 Given this incompatibility, Biró et al. (2022) focused on two different generalizations of Gale’s Top Trading Cycles rule (which does satisfy the three properties in the basic model where each agent has unit capacity). In this paper, we take a different approach by studying classes of serial dictatorships to achieve individual rationality and ig-Pareto-efficiency or Pareto-efficiency. In fact, it is not obvious that there exist rules that satisfy both individual rationality and Pareto-efficiency. The reason is that our requirement that circulation rules operate on the underlying profiles of ordinal preferences over individual goods, i.e., satisfy condition (3), creates tension with Pareto-efficiency on the domain of responsive preferences. We refer to Example 2in the next section for an illustration of this tension. We postpone the statement (and proof) that individual rationality and Pareto-efficiency are compatible (Corollary 18), as it follows from the result that our class of Multiple-Serial-IR rules satisfies all requirements (Proposition 17). 3. Single-Serial rules Given a capacity profile q, a q-priority order of agents is an ordered sequence in which each agent iappears exactly qi times. Formally, let Q=i∈Nqi. A q-priority order of agents is a vector πin (i1,i2,...,iQ):for all k=1,...,Q,ik∈Nand |{l=1,...,Q:il=ik}| = qik. The Single-Serial rule associated with a q-priority order πis defined as follows. Fix a preference profile. Following the order π, each agent sequentially chooses her most preferred good among the remaining goods (i.e., goods that have not been exhausted yet). Next we provide a formal definition. For each allocation xand each j ∈N, let the remainder rx(j)be the number of units of good jthat have not been allocated at x, i.e., rx(j) =qj−i∈Nxij. 11 A circulation rule is strategy-proof if for each agent it is a weakly dominant strategy to reveal her true preferences. As explained in the discussion on “ig,” the (weaker) property ig-strategy-proofness requires that the true preferences are a weakly dominant strategy only for the lexicographic extension of any preferences over the individual goods. We refer to Definition 3in Section 5for the formal definition. 433 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 Input: A q-priority order π=(i1, i2, ..., iQ)and preferences over individual goods =P. Step 0:For all i ∈N, let x0 i=0ibe agent i’s null assignment. Step k =1, ..., Q:Let j∗∈Nbe the good with rxk−1(j∗) >0such that j∗iklfor all l ∈Nwith rxk−1(l) >0. Define xkby xk ikj∗=xk−1 ikj∗+1 and xk ij =xk−1 ij for all (i, j) = (ik, j∗). Output: The circulation of the Single-Serial rule associated with πevaluated at profile is xQ. Single-Serial rules are well-defined, since they operate on profiles of ordinal preferences over individual goods. However, as the following example illustrates, they need not be individually rational even if preferences are lexicographic. Example 1. Consider the market (N, q, P)where N={1, 2}, q1=q2=1, and (lexicographic) preferences Pgiven by: 1 :2 11 2 :2 21 Consider the q-priority order (1, 2). The corresponding Single-Serial rule yields the individually irrational circulation where agent 1 receives her most preferred good and agent 2 receives an unacceptable good.  However, whenever a Single-Serial rule yields an individually rational circulation, it is also Pareto-efficient, provided that preferences are lexicographic. We say that an allocation xis extendable to a circulation yif x ≤y, i.e., for each agent iand each good j, xij ≤yij. Lemma 1. Let P∈PLbe a profile of lexicographic preferences. Let xbe an individually rational circulation. If some Single-Serial rule yields xat P, then xis Pareto-efficient at P. Proof. Suppose π=(i1, i2, ..., iQ)is a q-priority order such that its associated Single-Serial rule yields circulation xand x is not Pareto-efficient at P. Let ybe a circulation that Pareto-dominates x. Since x = y, there is a smallest k =1, ..., Qsuch that xk(i.e., the allocation at the end of step kof the assignment procedure) is not extendable to y. This implies that at step k, agent ik chooses a good j∗such that xk ikj∗>yikj∗. Let l ∈Nbe such that l ikj∗. By the definition of step k, for each i ∈N, xk−1 il ≤yil and rxk−1(l) =0, i.e., i∈Nxk−1 il =ql. Since yis a circulation, i∈Nyil =ql. Hence, xk−1 ikl=yikl. We conclude that xikj∗≥xk ikj∗>yikj∗and for each good l ∈Nwith l ikj∗we have xikl≥xk−1 ikl=yikl. But then, since xikand yikare acceptable bundles to ik, condition (2)of the definition of lexicographic preferences implies that xikPikyik, which contradicts the fact that yPareto-dominates x. The following example shows that the requirement of lexicographic preferences in Lemma 1cannot be omitted. Example 2. Consider the market (N, q, P)where N={1, 2, 3, 4, 5, 6}, q1=q2=q3=q4=1, q5=q6=2, and responsive12 preferences Pwith (0, 1, 1, 0, 0, 0)P5(1, 0, 0, 1, 0, 0), (1, 0, 0, 1, 0, 0)P6(0, 1, 1, 0, 0, 0)and such that the underlying preferences i(i ∈N)over acceptable individual goods are as follows: 1 :5 11 2 :5 22 3 :6 33 4 :6 44 5 :1 52 53 54 55 6 :1 62 63 64 66 Consider the q-priority order (5, 6, 6, 5, 1, 2, 3, 4). The corresponding Single-Serial rule gives the individually rational circulation xwhere each agent i ∈{1, 2, 3, 4}receives one unit of her most preferred good, agent 5 receives bundle (1, 0, 0, 1, 0, 0), and agent 6 receives bundle (0, 1, 1, 0, 0, 0). However, this circulation is not Pareto-efficient, as switching the bundles of agents 5 and 6 is a Pareto improvement. So, xis not Pareto-efficient at P. The market above also allows us to illustrate why the requirement that circulation rules operate on the underlying profiles of ordinal preferences over individual goods, i.e., satisfy condition (3), creates tension with Pareto-efficiency on the domain of responsive preferences. Consider the market (N, q, P)that is the same as (N, q, P)except that now (1, 0, 0, 1, 0, 0)P 5(0, 1, 1, 0, 0, 0)and (0, 1, 1, 0, 0, 0)P 6(1, 0, 0, 1, 0, 0). One easily verifies that xis Pareto-efficient at P. 12 It is easy to see that there are additive preferences whose underlying preferences over individual goods are . 434 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 Similarly, there are individually rational circulations that are Pareto-efficient at P, but not at P. This raises the question whether for any profile of ordinal preferences over individual goods there exists an individually rational allocation that is Pareto-efficient at all possible responsive extensions. Corollary 18 provides an affirmative answer: there exist rules that satisfy both individual rationality and Pareto-efficiency.  The next example shows that the requirement of individual rationality in Lemma 1cannot be omitted either. Example 3. Consider the market (N, q, P)where N={1, 2, 3, 4, 5, 6}, q1=q2=q3=q4=1, q5=q6=2, and consider lexicographic preferences Psuch that the underlying preferences i(i ∈N) over individual goods are as follows:13 1 :5 11 1··· 2 :5 22 2··· 3 :6 33 3··· 4 :6 44 4··· 5 :1 52 53 55 54 56 6 :1 62 63 64 65 66 Consider the q-priority order (1, 2, 3, 4, 5, 6, 6, 5). The corresponding Single-Serial rule gives the circulation xwhere each agent i ∈{1, 2, 3, 4}receives one unit of her most preferred good, agent 5 receives (unacceptable) bundle (1, 0, 0, 1, 0, 0), and agent 6 receives (acceptable) bundle (0, 1, 1, 0, 0, 0). Clearly, xis not individually rational. Moreover, xis not Paretoefficient, since switching the bundles of agents 5 and 6 is a Pareto improvement: agent 5 would receive an acceptable bundle and agent 6 would be better off as well by obtaining a unit of her most preferred good.  Our next result shows that Single-Serial rules are “exhaustive” in terms of Pareto-efficiency. More precisely, for any profile of preferences, each Pareto-efficient circulation (whether individually rational or not) can be obtained by applying some Single-Serial rule to the preference profile. This result was proved by Cechlárová et al. (2014)in a similar setting. However, since their result does not imply ours, we present a (simpler) proof for our model. Proposition 2. Let P∈Pbe a profile of preferences. If a circulation xis Pareto-efficient at P, then xis obtained by some Single-Serial rule applied to P. Proof. Let P∈Pbe a profile of preferences. Let xbe a circulation that is Pareto-efficient at Pand suppose, by contradiction, that there is no q-priority order of agents for which the corresponding Single-Serial rule applied to Pyields x. We first construct a partial q-priority order that results in an allocation as “close” to xas possible. Consider the following procedure. Let ybe the empty allocation (where each agent receives her null assignment) and let σbe the empty order. Check whether there are any agent iand good jon the market such that 1) jis i’s first choice among the goods that are on the market and 2) by assigning one additional unit of good jto ithis extended allocation ywould still be extendable to x. If there are an agent iand a good jthat satisfy conditions 1) and 2), pick one such pair, say agent i∗and good j∗, and update yi∗j∗≡yi∗j∗+1 and σ≡(σ, i∗). If j∈Nyi∗j=qi∗, then remove agent i∗from the market. Similarly, if i∈Nyij∗=qj∗, then remove good j∗from the market. We repeat this incremental procedure until we reach an allocation ythat is not extendable with the first choice of any agent. (We reach such an allocation by the assumption that xcannot be obtained with any Single-Serial rule.) Let kbe a good that is on the market. Then i∈Nyik <qk=i∈Nxik. Since for each agent i ∈N, yik ≤xik, there is some agent i∗∈Nwith yi∗k<xi∗k. In fact, any such i∗is an agent that is still on the market.14 We now build a directed graph D(y)on the remaining goods as follows. Let kand jbe any two goods that are on the market. If for some agent i∗that is on the market we have 1) yi∗k<xi∗kand 2) jis i∗’s most preferred good among the available goods (hence yi∗j=xi∗j), then there is a directed edge from kto j. From the above it follows that for each good kthat is still on the market, there is a directed edge going out from k. Therefore, D(y)contains at least one directed cycle, say (b1, b2, ..., br). For each directed edge from bito bi+1, let aibe an agent that is on the market such that 1) aihas strictly more units of good biat xthan at yand 2) good bi+1is the most preferred good for aiamong all goods that remain on the market (modulo r). Since each agent has strict preferences, it follows that {a1, ..., ar}contains rdifferent agents. Construct the circulation xfrom xby carrying out the trades in the cycle. That is, move one unit of good bi+1from agent ai+1to agent ai(modulo r). Since preferences satisfy condition (r2) of responsiveness, each agent aistrictly prefers x aito xai. Hence, xPareto-dominates x, which obviously contradicts the fact that xis Pareto-efficient.  13 ··· indicates that preferences can be completed in an arbitrary way. 14 Let pbe a removed agent. For each good r∈N(removed or not), ypr ≤xpr . Since r∈Nypr =qp, it follows that for each good r∈Nwe have in fact ypr =xpr. 435 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 3.1. Single-Serial-IR rules Since Single-Serial rules do not necessarily yield individually rational circulations, we adjust them by demanding that for each (sequential) choice of a good the resulting allocation be IR-extendable. An allocation xis IR-extendable if there exists an individually rational circulation xsuch that xis extendable to x. The adjusted serial rules will henceforth be referred to as Single-Serial-IR rules. Input: A q-priority order π=(i1, i2, ..., iQ)and preferences over individual goods . Step 0:For each i ∈N, let x0 i=0ibe agent i’s null assignment. Step k =1, ..., Q:Let J⊆Nconsist of goods jsuch that •rxk−1(j) >0 and •the allocation zdefined by zikj=xk−1 ikj+1 and zil =xk−1 il for all (i, l) = (ik, j)is IR-extendable. Let j∗∈Jbe such that for each j ∈J, j∗ikj. Define xkby xk ikj∗=xk−1 ikj∗+1 and xk il =xk−1 il for all (i, l) = (ik, j∗). Output: The circulation of the Single-Serial-IR rule associated with πevaluated at profile is xQ. The empty allocation (where each agent receives her null assignment) is IR-extendable, because we can give each agent her original endowments. Hence, the algorithm above is well-defined. Also, Single-Serial-IR rules are well-defined, as they operate on profiles of ordinal preferences over individual goods. Moreover, by definition, Single-Serial-IR rules yield individually rational circulations. Remark 3. Note that if a Single-Serial rule associated with some q-priority order πyields an individually rational circulation xat a preference profile , then the Single-Serial-IR rule associated with πalso yields circulation xat . Remark 3coupled with Example 2shows that Single-Serial-IR rules need not be Pareto-efficient. However, we will establish that Single-Serial-IR rules are ig-Pareto-efficient (Proposition 11). Towards a proof of this result, we will first establish some technical results so that we can provide and use an alternative description (Theorem 7) of the Single-SerialIR rules. The alternative description also enables us to show that Single-Serial-IR rules can be efficiently implemented from a computational point of view (Corollary 10). We introduce some additional notation. Let (N, q, P)be a market. Let xbe an allocation. Let |xi|be the number of units of (possibly different) goods that agent ireceives at x, i.e., |xi| =j∈N|xij|, and let dx(i) =qi−|xi|be the demand of agent iat allocation x. For S⊆N, let dx(S) =i∈Sdx(i)and rx(S) =i∈Srx(i). Note that rx(N)= j∈N rx(j)= j∈Nqj− i∈N xij = j∈N qj− j∈N i∈N xij = i∈N qi− i∈N j∈N xij = i∈N qi− i∈N |xi| = i∈N (qi−|xi|)= i∈N dx(i)=dx(N). (4) For S⊆N, let I(S)denote the goods that are acceptable to some member of S, i.e., I(S) ={i ∈N:i jjfor some j ∈S}. We say that Shas overdemand at xif dx(S) >rx(I(S)). If some set of agents has overdemand at an allocation xthen xis certainly not IR-extendable. Lemma 3below shows that the reverse of this statement is also true, i.e., IR-extendability is characterized by absence of overdemand. Lemma 3. An allocation xis IR-extendable if and only if no set of agents has overdemand at x, i.e., for each S⊆N, dx(S) ≤rx(I(S)). Before we provide a proof of Lemma 3, we introduce a directed graph that turns out to be a useful tool for the proof of Lemma 3and for the description of an efficient implementation of Single-Serial-IR rules. 436 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 remaining goods coincides with the bundle obtained from a greedy procedure where the agent picks the most preferred (and available) goods one by one. Therefore, when analyzing the computational complexity of Multiple-Serial rules, we can assume that the input of the algorithm is P, rather than P. Obviously, Multiple-Serial rules need not be individually rational: the Single-Serial rule that yields an individually irrational circulation in Example 1is a Multiple-Serial rule, since all agents’ capacities are equal to one. The following result is immediate. Proposition 13. Multiple-Serial rules are Pareto-efficient. Next we introduce and study Multiple-Serial-IR rules which are the rules obtained by adjusting the Multiple-Serial rules to guarantee individual rationality while maintaining Pareto-efficiency. 4.1. Multiple-Serial-IR rules Since Multiple-Serial rules do not necessarily yield individually rational circulations, we adjust them by demanding that for each (sequential) choice of a bundle the resulting allocation be IR-extendable. The adjusted serial rules will henceforth be referred to as Multiple-Serial-IR rules. Input: An order π=(i1, ..., in)of the agents and a preference profile P∈P. Step 0:For each i ∈N, let x0 i=0ibe agent i’s null assignment. Step k =1, ..., n:Let Yikdenote the collection of bundles yik∈Xikfor agent iksuch that •for each good j ∈N, yikj≤rxk−1(j)and •the allocation zdefined by zik=yikand zi=xk−1 ifor all i = ikis IR-extendable. Let y∗ ik∈Yikbe the bundle such that for each yik∈Yik, y∗ ikRikyik. Define xkby setting xk ik=y∗ ikand xk i=xk−1 ifor all i = ik. Output: The circulation of the Multiple-Serial-IR rule associated with πevaluated at profile Pis xn. Remark 8. If a Multiple-Serial rule associated with some order πyields an individually rational circulation xat a preference profile P, then the Multiple-Serial-IR rule associated with πalso yields circulation xat P. Next we show that Multiple-Serial-IR rules operate on the underlying profiles of ordinal preferences over individual goods, i.e., (3)is satisfied. This will allow us to assume that the input of the algorithm above is P, rather than P, and show that Multiple-Serial-IR rules can be efficiently implemented for such concise inputs. We first prove a technical lemma. Given an IR-extendable allocation x, we say that an assignment yiis feasible to receive for agent i(at x) if after giving the goods in yito agent i(on top of those in xi), the resulting allocation xis IR-extendable (here xis the allocation defined by x ij =xij +yij for all jand x l=xlfor all l = i). Lemma 14. Let i ∈N. Let xbe an IR-extendable allocation and let yiand zibe two assignments that are both feasible to receive for agent iat xand such that |yi| <|zi|. Then there is a good jin zisuch that after adding jto yithe extended assignment is also feasible to receive for agent iat x. Proof. Let i ∈N. First we prove the lemma for |yi| =1 and |zi| =2. Suppose that the statement is not true. Let yiconsist of good jand let ziconsist of two goods, kand l, with the possibility that k =l. Let xdenote the extension of xby yi and let x denote the extension of xby zi. Note that xand x are both IR-extendable but, by our assumption, at xneither knor lis feasible to receive for i. Therefore, by Lemma 4, there is a constrained set Sat xsuch that i /∈Sand k ∈I(S), and similarly, there is a constrained set T(which possibly coincides with S) at xsuch that i /∈Tand l ∈I(T). In particular, k, l ∈I(S) ∪I(T) =I(S∪T). Note that xonly differs from xby adding a unit of good jto xi. Since i /∈S, it follows that for each s ∈S, dx(s) =dx(s). Hence, dx(S) =dx(S). Suppose j /∈I(S). Then, for each s ∈I(S), rx(s) =rx(s). Hence, rx(I(S)) =rx(I(S)). Since kis feasible to receive for iat x, it follows from Lemma 4that Sis not constrained at x. Thus, dx(S) = rx(I(S)). But then it follows from the above that dx(S) = rx(I(S)) as well, which contradicts that Sis constrained at x. Hence, j ∈I(S). Similarly, j ∈I(T). Hence, j ∈I(S) ∪I(T) =I(S∪T). We now show that S∪Thas overdemand at x. First, since i /∈S∪T, it follows that for all p ∈S∪Twe have x p=xp=x p. Thus, dx(S∪T) =dx (S∪T). Second, by the definitions of xand x and the fact that j, k, l ∈I(S∪T), it follows that rx(I(S∪T)) =rx(I(S∪T)) +1 and rx (I(S∪T)) =rx(I(S∪T)) −2. Hence, rx (I(S∪T)) =rx(I(S∪T)) −1. By Lemma 5, S∪Tis a constrained set at x. Therefore, 443 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 dx (S∪T)=dx(S∪T)=rx(I(S∪T)) =rx (I(S∪T)) +1, which shows that S∪Thas overdemand at x. Using Lemma 3we obtain a contradiction with the fact that x is IRextendable. Hence, the lemma holds when |yi| =1 and |zi| =2. Now we complete the proof of the lemma by extending the previous argument and by using the above subcase. Suppose the lemma is not true. Among all triples (x, yi, zi)that violate the statement pick one for which |yi|is minimal. Note |yi| >0. Next, note that yiand zido not have any good in common. Otherwise, this good could be added to xiand omitted from both yiand zi, resulting in another triple, say (x, y i, z i), which violates the statement while |y i| <|yi|, contradicting the minimality of |yi|. Let kbe some good in yi. Let y ibe the assignment that results from removing good kfrom yi. (Then obviously y iis feasible to receive for agent iat x.) If there is still no good from zithat can be added to y iwhile keeping the thus extended assignment feasible to receive for iat x, then the triple (x, y i, zi)violates the statement while |y i| <|yi|, which contradicts the minimality of |yi|. Hence, there is a good in zi, say j, that can be added to y isuch that the thus extended assignment (say y i) would still be feasible to receive for iat x. Extend xby assigning jto iand let xbe the resulting allocation, i.e., the only difference between xand xis that x ij =xij +1. Let z ibe the assignment obtained from ziby removing good j. We will show that the triple (x, y i, z i)also violates the statement and, since |y i| <|yi|, we obtain a contradiction with the minimality of |yi|. First, by definition of x and good j, assignments y iand z iare both feasible to receive for agent iat x. Moreover, since |yi| <|zi|, we also have |y i| <|z i|. Finally, there is no good lin z isuch that after adding lto y ithe extended assignment is also feasible to receive for agent iat x. To show the last claim, suppose this is not the case, i.e., () there does exist a good lin z isuch that after adding lto y ithe extended assignment is also feasible to receive for agent iat x. Then consider the triple (x∗, y∗ i, z∗ i)where x∗is obtained from xby adding y ito xiand where y∗ iis the assignment that consists of good kand z∗ iis the assignment that consists of goods jand l. We verify that (x∗, y∗ i, z∗ i)violates the statement of the lemma. First, since y iis feasible to receive for agent iat x, allocation x∗is IR-extendable. Second, |y∗ i| =1 <2 =|z∗ i|. Third, since yiis feasible to receive for agent iat x, it follows that y∗ iis feasible to receive for agent iat x∗. Fourth, by (), z∗ iis feasible to receive for agent iat x∗. Finally, since (x, yi, zi) violates the statement, it follows that we cannot add either good jor good lto y∗ isuch that the extended assignment is feasible to receive for agent iat x∗. However, given that |y∗ i| =1and |z∗ i| =2, it follows from the first part of the proof that (x∗, y∗ i, z∗ i)does not violate the statement of the lemma. This contradiction completes the proof.  Theorem 15. Each Multiple-Serial-IR rule operates on the underlying profiles of ordinal preferences over individual goods, i.e., (3)is satisfied. More precisely, the bundle of each agent can also be obtained in a greedy way by selecting (when it is her turn) one by one the most preferred goods from the goods that are feasible to receive for the agent. Proof. First note that checking IR-extendability only requires the ordinal preferences over individual goods. Hence, to determine whether a good is feasible to receive also only requires the ordinal preferences over individual goods. Let i ∈N. Let the greedy method yield bundle gifor agent i. Suppose that the Multiple-Serial-IR rule yields a different bundle, say fi. Let us order the goods in both giand fiaccording to agent i’s ordinal preferences over individual goods. More specifically, for each k ∈{1, ..., qi}, let fi(k)and gi(k)be the k-th most preferred good in fiand gi, respectively. (Note that some good may appear multiple times in fiand/or gi. Therefore it is possible that for some k ∈{1, ..., qi}we have fi(k) =fi(k +1)and/or gi(k) =gi(k +1).) Suppose iweakly prefers gi(k)to fi(k)for each k ∈{1, ..., qi}. Then, by responsiveness, giis weakly preferred to fi. Since gi= fi, it follows that giis strictly preferred to fi, which contradicts the optimality of agent i’s choice in the Multiple-Serial-IR rule. Therefore, there is some index k ∈{1, ..., qi}such that istrictly prefers fi(k)to gi(k), and thus ialso strictly prefers each of the goods fi(l)with 1 ≤l ≤kto gi(k). Let zibe the assignment that consists of the kmost preferred goods in fi and let yibe the assignment that consists of the k −1most preferred goods in gi(here multiple units of the same good are also counted). By Lemma 14, there is a good jin zisuch that after adding jto yithe extended assignment is also feasible to receive for agent i, which contradicts the selection of the greedy method.  Remark 9. Theorem 15 can be proved alternatively using matroids as follows.22 Let i ∈N. Let xbe an IR-extendable allocation. The collection Mof sets of up to kgoods (k ≤rx(i)) that are feasible to receive for iat xsubject to IR-extendability is a matroid. To see this, note that the exchangeability property of matroids is precisely the contents of Lemma 14 (the other matroid properties are satisfied trivially). Thus, by applying Theorem 1 in Gourvès (2019)it follows that for any responsive preferences Pi, the most preferred bundle of kgoods in Mcan be obtained by choosing kgoods greedily according to Pi, which shows Theorem 15. 22 We are grateful to an anonymous reviewer for pointing out the alternative approach with matroids. 444 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 Corollary 16. Each Multiple-Serial-IR rule is a Single-Serial-IR rule. In particular, it can be efficiently implemented. Proof. Consider any Multiple-Serial-IR rule. Let π=(i1, ..., in)be the associated order of the agents. Let ¯ πbe the q-priority order in which the first q1entries are agent i1, the next q2entries are agent i2, etc. According to Theorem 15, the MultipleSerial-IR rule (associated with π) coincides with the Single-Serial-IR rule associated with ¯ π. Then efficient implementation follows from Corollary 10. The following proposition follows easily from the definition of the Multiple-Serial-IR rules. Proposition 17. Multiple-Serial-IR rules are individually rational and Pareto-efficient. Proof. Individual rationality is immediate. Suppose a Multiple-Serial-IR rule associated with order π=(i1, ..., in)is not Pareto-efficient. Then there is a preference profile P∈Psuch that the rule applied to Pgives a circulation xthat is Paretodominated by some circulation x. Following the order π, consider the first agent iksuch that xik= x ik. Since x ikPikxik, it follows from Step kof the definition of the Multiple-Serial-IR rule that xcannot be individually rational. So, there is an agent i ∈Nfor which eiPix i. Since xis individually rational, xiRiei. Hence, xiPix iwhich contradicts the fact that x Pareto-dominates x. Proposition 17 also shows that individual rationality and Pareto-efficiency together are compatible with our requirement that circulation rules operate on the underlying profiles of ordinal preferences over individual goods. Corollary 18. There are individually rational and Pareto-efficient rules. A converse to Proposition 17 does not hold. More precisely, there are markets where some individually rational and Pareto-efficient circulation cannot be obtained with any Multiple-Serial-IR rule (and hence, by Remark 8, also not with any Multiple-Serial rule; thus a converse statement to Proposition 13 does not hold either). We demonstrate this with the following example. Example 4. Consider the market (N, q, P)where N={1, 2, 3}, q1=q2=q3=2, and consider preferences Psuch that the underlying preferences i(i ∈N) over acceptable individual goods are as follows: 1 :3 11 2 :3 22 3 :1 32 33 The three circulations x :x13 =x22 =x31 =2, x:x 11 =x 23 =x 32 =2, and x :x 11 =x 13 =x 22 =x 23 =x 31 =x 32 =1 are individually rational and Pareto-efficient independently of the particular responsive preferences P3of agent 3over bundles (in particular, we can assume that all preferences are lexicographic).23 However, the only (individually rational and Pareto-efficient) circulations that can be obtained by Multiple-Serial-IR rules are xand x. Specifically, orders (1,2,3), (1,3,2), (3,1,2), and (3,2,1) yield x, while orders (2,1,3) and (2,3,1) yield x. Thus, the individually rational and Pareto-efficient circulation x cannot be obtained by any Multiple-Serial-IR rule. Given Remark 8, it is clear that the class of Multiple-Serial rules can only yield a subset of the circulations obtained by the Multiple-Serial-IR rules, in addition to possibly some individually irrational circulations. Specifically in this example, Multiple-Serial rules lead to the following: orders (1,2,3), (1,3,2), and (3,1,2) yield x, order (2,1,3) yields x, and orders (2,3,1) and (3,2,1) yield the individually irrational circulation ygiven by y12 =y23 =y31 =2. Therefore, the individually rational and Pareto-efficient circulation x cannot be obtained by any Multiple-Serial rule either.  Example 4together with Proposition 11 demonstrate an interesting difference between Multiple-Serial-IR and SingleSerial-IR rules: given any profile of lexicographic preferences Pand any circulation xthat is individually rational and Paretoefficient at P, xcan be obtained by some Single-Serial-IR rule, but possibly not by any Multiple-Serial-IR rule. When we compare the Single-Serial rules with the Multiple-Serial rules (with or without individual rationality), the Multiple-Serial rules achieve Pareto-efficiency even for responsive preferences, but the price we pay is that not all Paretoefficient circulations can be obtained as illustrated by Example 4. In particular, the circulations obtained by the MultipleSerial rules tend to be rather unfair, since the agents who choose first can obtain the goods that possibly all agents prefer 23 Given 1and 2, the responsive preferences P1and P2of agents 1and 2are uniquely determined. For agent 3, 3together with responsiveness does not specify whether receiving two units of good 2 is preferred to one unit of good 1 together with one unit of good 3. 445 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 most. More “equitable” (but still Pareto-efficient) circulations in which several agents receive (possibly commonly) most preferred goods are typically not obtained through Multiple-Serial rules. This indicates that there is a trade-off between the rule being Pareto-efficient for responsive preferences and being “equitable.” 5. Manipulability In this section, we determine which of our rules satisfy incentive properties. As a starting point, we note that Proposition 1 in Biró et al. (2022)shows that individual rationality and ig-Pareto-efficiency are not compatible with another important desideratum, ig-strategy-proofness. For any P∈Pand any i ∈N, denote P−i=(Pj)j=i. Definition 3. Agent i ∈Ncan manipulate circulation rule fat P∈Pif there exists a deviation P i∈Pisuch that fi(P i, P−i)Pifi(P). A circulation rule fis (necessarily) strategy-proof if no agent can manipulate fat any P∈P. A circulation rule fis ig-strategy-proof if no agent can manipulate fat any profile of lexicographic preferences P∈PL.24  The following example illustrates the incompatibility of individual rationality, ig-Pareto-efficiency, and ig-strategyproofness. Specifically, Serial-IR rules satisfy the first two properties, and are hence vulnerable to manipulations. Example 5. Consider the market (N, q, P)where N={1, 2, 3}, q1=q2=q3=1, and lexicographic preferences Psuch that the preferences over acceptable goods are given by 1 :3 11 2 :3 21 22 3 :2 33 Consider the Single-Serial-IR rule associated with the order (1, 2, 3). This rule yields circulation xwhere x13 =x21 =x32 =1. However, if agent 2 removes good 1from her list of acceptable goods then the rule yields circulation xwhere x 11 =x 23 = x 32 =1. Obviously, agent 2prefers x 2to x2. The literature considered several weaker incentive properties, which we explore next. For each agent i ∈N, let Lidenote the set of strict (ordinal) preferences over individual goods for agent i. A truncation of a preference list over individual goods is a preference list obtained by making some of the lowest-ranked acceptable goods unacceptable. Formally, a preference  i∈Liis a truncation of i∈Liif for all k, l ∈Nwe have [if k  il  ii, then k il ii] and [if k  iiand l ik, then l  ii]. The first condition says that if two goods are listed as acceptable under the “manipulation”  i, then they are ordered in the same way as in the true preferences i. The second condition says that if a good is listed as acceptable under the “manipulation”  iand there is some other good that is more preferred in the true preferences i, then the latter good is also acceptable under the “manipulation”  i. Definition 4. Agent i ∈Ncan manipulate circulation rule fat P∈Pby means of truncation if there exists a deviation P i∈Pisuch that P iis a truncation of Piand fi(P i, P−i)Pifi(P). A circulation rule fis (necessarily) truncation-proof if no agent can manipulate fat any P∈Pby means of truncation.25 A circulation rule fis ig-truncation-proof if no agent can manipulate fby means of truncation at any profile P∈PLof lexicographic preferences.26  A preference  i∈Liis a dropping of i∈Liif for all k, l ∈N, [if k  il  ii, then k il ii]. Obviously, since the requirement in the definition of dropping is exactly the first condition in the definition of truncation, it follows that each truncation is a dropping. Definition 5. Agent i ∈Ncan manipulate circulation rule fat P∈Pby means of dropping if there exists a deviation P i∈Pi such that P iis a dropping of Piand fi(P i, P−i)Pifi(P). A circulation rule fis (necessarily) dropping-proof if no agent can manipulate fat any P∈Pby means of dropping. A circulation rule fis ig-dropping-proof if no agent can manipulate fby means of dropping at any profile P∈PLof lexicographic preferences.27  24 Since circulation rules operate on profiles of ordinal preferences over individual goods, equivalent definitions of strategy-proofness and ig-strategyproofness are obtained by demanding that the deviation P iis lexicographic. 25 Kojima (2013) similarly defined “non-manipulability via truncation” in the context of resource allocation with multi-unit demand. 26 Since circulation rules operate on profiles of ordinal preferences over individual goods, equivalent definitions of truncation-proofness and ig-truncationproofness are obtained by requiring that the deviation P iis lexicographic. 27 Since circulation rules operate on profiles of ordinal preferences over individual goods, equivalent definitions of dropping-proofness and ig-droppingproofness are obtained by requiring that the deviation P iis lexicographic. 446 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 Note that strategy-proofness implies dropping-proofness, which in turn implies truncation-proofness. Similarly, igstrategy-proofness implies ig-dropping-proofness, which in turn implies ig-truncation-proofness. Since preferences are lexicographic and agent 2’s manipulation is a truncation, Example 5provides an instance of a Single-Serial-IR rule that is not ig-truncation-proof. Hence, there are Single-Serial-IR rules that do not satisfy any of the six incentive properties! Note that since in Example 5each agent’s capacity equals one, the Single-Serial-IR rule is a MultipleSerial-IR rule. Thus, there are Multiple-Serial-IR rules that do not satisfy any of the six incentive properties. However, as a positive result we show that Multiple-Serial-IR rules are safe against so-called swapping manipulations. A preference  i∈Liis a swapping of i∈Liif for all k ∈N, k ii ⇐⇒ k  ii. Hence, a swapping can swap (the order of) goods, but what is (un)acceptable remains (un)acceptable. Definition 6. Agent i ∈Ncan manipulate circulation rule fat P∈Pby means of swapping if there exists a deviation P i∈Pisuch that P iis a swapping of Piand fi(P i, P−i)Pifi(P). A circulation rule fis (necessarily) swapping-proof if no agent can manipulate fat any P∈Pby means of swapping. A circulation rule fis ig-swapping-proof if no agent can manipulate fby means of swapping at any profile P∈PLof lexicographic preferences.28  Proposition 19. Multiple-Serial-IR rules are swapping-proof. Proof. Consider the kth agent, say ik, in the order of a Multiple-Serial-IR rule. This agent cannot change the choices of the first k −1agents by replacing her true preferences by some swapping. The reason is that restrictions on choices are determined by IR-extendability, which does not vary between agent ik’s true preferences and any swapping (because the set of acceptable goods is the same). Furthermore, at step k, agent ikweakly prefers choosing her most preferred (feasible) bundle with respect to her true preferences to choosing her most preferred (feasible) bundle with respect to any swapping.  An agent i ∈Nis said to be of unit-capacity if qi=1. Corollary 20. Single-Serial-IR rules are swapping-proof for unit-capacity agents. Remark 10. We note that Single-Serial rules are in general not ig-swapping-proof. This is a well-known weakness of serial rules (see e.g. Hatfield, 2009) that is experienced for instance in sports drafts when teams sequentially choose one player at a time: sometimes it can be beneficial to choose a popular player rather than a personal favorite among the remaining players, since the latter may still be available in subsequent rounds, while the popular player will surely be taken. Moreover, we also conclude by the same token that Single-Serial-IR rules are not ig-swapping-proof (except for unit-capacity agents, as described in Corollary 20).  Finally, we consider a different kind of manipulation, namely the possibility of hiding endowments.29 Let i ∈Nand let qbe a capacity profile. We denote q−i=(qj)j=i. In the next definition, we express the circulation outcome explicitly as a function of the capacity profile, in addition to the preference profile. Definition 7. A circulation rule fis hiding-proof if for all i ∈N, P∈P, and q i<qi, fi(P, q) Rifi(P, (q−i, q i)) +qi−q i qiei.30 A circulation rule fis ig-hiding-proof if for all i ∈N, P∈PL, and q i<qi,fi(P, q) Rifi(P, (q−i, q i)) +qi−q i qiei. Remark 11. Hiding-proofness implies individual rationality. For instance, in the market exhibited in Example 1agent 2 can profit by hiding her resources. Hence, there are Single-Serial and Multiple-Serial rules that are not ig-hiding-proof (and hence not hiding-proof). It is easy to check that Single-Serial-IR and Multiple-Serial-IR rules are hiding-proof (and hence ig-hiding-proof).  6. Concluding remarks 6.1. Summary of properties Table 5summarizes our findings regarding the properties of the families of circulation rules that we have studied in this paper. In the table ✓ indicates that a property (row) is satisfied by any rule in the family (column) and ✗ indicates that it is not. For a comparison, the table also includes the properties of the most important rules studied in Biró et 28 Since circulation rules operate on profiles of ordinal preferences over individual goods, equivalent definitions of swapping-proofness and ig-swappingproofness are obtained by requiring that the deviation P iis lexicographic. 29 In the context of classical exchange economies, Postlewaite (1979)was the first to introduce and study “non-manipulability by withholding.” 30 Note that eiis the bundle that consists of qiunits of good i. Hence, qi−q i qieiconsists of (the hidden) qi−q iunits of good i. 447 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 Table 5 Properties of rules. Serial rules Single Single-IR Multiple Multiple-IR cTTC STC individually rational ✗✓✗✓✓✓ Pareto-efficient ✗✗ ✓ ✓ ✗✗ ig-Pareto-efficient ✗✓✓✓✓✗ strategy-proof ✗✗ ✓ ✗ ✗✓ ig-strategy-proof ✗✗ ✓✗✗✓ dropping-proof ✓✗ ✓ ✗ ✗✓ ig-dropping-proof ✓✗ ✓ ✗ ✓✓ truncation-proof ✓✗ ✓ ✗ ✓✓ ig-truncation-proof ✓✗ ✓ ✗ ✓✓ swapping-proof ✗✗ ✓ ✓ ✗✓ ig-swapping-proof ✗✗ ✓ ✓ ✗✓ hiding-proof ✗✓ ✗ ✓ ✓✓ ig-hiding-proof ✗✓ ✗ ✓ ✓✓ Table 6 Basis for the properties. Serial rules Single Single-IR Multiple Multiple-IR individually rational Example 1By def. Example 1By def. Pareto-efficient Example 2Remark 3+Example2By def. Proposition 17 ig-Pareto-efficient Example 3Corollary 12 By def. Proposition 17 strategy-proof Remark 10 Example 5Trivial Example 5 ig-strategy-proof Remark 10 Example 5Trivial Example 5 dropping-proof Trivial Example 5Trivial Example 5 ig-dropping-proof Trivial Example 5Trivial Example 5 truncation-proof Trivial Example 5Trivial Example 5 ig-truncation-proof Trivial Example 5Trivial Example 5 swapping-proof Remark 10 Remark 10 Trivial Proposition 19 ig-swapping-proof Remark 10 Remark 10 Trivial Proposition 19 hiding-proof Remark 11 Remark 11 Remark 11 Remark 11 ig-hiding-proof Remark 11 Remark 11 Remark 11 Remark 11 al. (2022): the circulation Top Trading Cycles (cTTC) rule and the family of Segmented Trading Cycle (STC) rules. As we noted earlier, Proposition 1 in Biró et al. (2022)shows that there is no rule that satisfies individual rationality, ig-Paretoefficiency, and ig-strategy-proofness. As is clear from Table 5, there are rules that satisfy any two of the three properties: (1) Multiple-Serial rules satisfy ig-Pareto-efficiency and ig-strategy-proofness, (2) STC rules satisfy individual rationality and ig-strategy-proofness, and (3) Single/Multiple-Serial-IR rules (and the cTTC rule) satisfy individual rationality and ig-Paretoefficiency. To accompany Table 5, we display in Table 6where the proof comes from for each entry regarding the serial rules. For the proofs of the entries on cTTC and the STC rules we refer to Biró et al. (2022). 6.2. Generalized serial rules For each Single-Serial/Single-Serial-IR rule we have assumed that there is a fixed q-priority order of the agents, i.e., independently of the preferences. Similarly, for each Multiple-Serial/Multiple-Serial-IR rule we have assumed that there is a fixed order of the agents. However, as we have focused our study on individual rationality and (ig)-Pareto-efficiency, to establish our results and examples in Sections 3and 4we have not compared outcomes across different preference profiles. Hence, our analysis also holds for “generalized serial rules” where we allow the order to depend on the preference profile. In particular, we obtain the following result as a corollary to Propositions 13 and 2. Corollary 21. Each generalized Multiple-Serial rule is Pareto-efficient. Each Pareto-efficient rule is a generalized Single-Serial rule. Note that not every Pareto-efficient rule is a generalized Multiple-Serial rule, see, e.g., the last paragraph in Example 4. Similarly, not every generalized Single-Serial rule is Pareto-efficient, see, e.g., Example 3. Note that in both examples preferences are lexicographic. Fig. 1depicts our findings on Pareto-efficient circulations and Single-Serial and Multiple-Serial rules in a Venn diagram. A special case of a generalized Single-Serial-IR rule is the cTTC rule studied in Biró et al. (2022) which is individually rational and ig-Pareto-efficient (see Remark 7). This also follows from the next result, which is a corollary to Proposition 11. Corollary 22. A rule is individually rational and ig-Pareto-efficient if and only if it is a generalized Single-Serial-IR rule. 448 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 Proposition 2+Example3 PE Proposition 13 +Example4(2nd part) SS MS Lexicographic/Responsive preferences Fig. 1. Venn diagram. Fix preferences P. Let PE denote the set of Pareto-efficient circulations at P. Let SS (MS) denote the set of circulations obtained by applying Single-Serial (Multiple-Serial) rules to P. The examples show that the set inclusion can be strict. Proposition 11 / Corollary 22 PE+IR Proposition 17 +Example4 SSIR  MSIR Lexicographic Proposition 11(ii) + Example 2with Remark 3 PE+IR SSIR MSIR Responsive Fig. 2. Venn diagrams. Fix preferences P. Let PE+IR denote the set of Pareto-efficient and individually rational circulations at P. Let SSIR (MSIR) denote the set of circulations obtained by applying Single-Serial-IR (Multiple-Serial-IR) rules to P. The examples show that the set inclusion can be strict. The following result is obtained as a corollary to Propositions 17 and 11(ii). Corollary 23. Each generalized Multiple-Serial-IR rule is Pareto-efficient and individually rational. Each Pareto-efficient and individually rational rule is a generalized Single-Serial-IR rule. Note that not every Pareto-efficient and individually rational rule is a generalized Multiple-Serial-IR rule, see, e.g., Example 4(where preferences are lexicographic). When preferences are not lexicographic, not every generalized Single-Serial-IR rule is Pareto-efficient and individually rational, see, e.g., Example 2coupled with Remark 3. Fig. 2depicts our findings on Pareto-efficient and individually rational circulations and Single-Serial-IR and Multiple-Serial-IR rules in a Venn diagram. Figs. 1and 2show that the natural interest in Pareto-efficient circulations and Pareto-efficient and individually rational circulations should motivate a further study of serial rules. 6.3. Extensions Obviously, our negative results still hold in extended models. We describe below how our positive results may be extended to models with link-capacities, heterogeneous goods, or more complex preferences. 449 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 Link-capacities Instead of (or besides) the agent-capacities we could have link-capacities, i.e., a cap on the number of goods an agent can send to, or receive, from other agents. This is a very typical setting for circulation problems in graph theory, and some practical applications do have this kind of requirement, e.g., in the Erasmus exchange program the number of students from university Uthat visit university Vis bounded by the specifications in the bilateral contract between Uand V. We opted for defining our model through agent-capacities to easily relate it to existing models on the exchange of indivisible goods. However, any link-capacitated market can always be transformed into an agent-capacitated market under responsive preferences by introducing artificial agents. For instance, if agent jcannot receive more than qij units of good i, then we introduce an artificial agent/good ij with capacity qij. In agent i’s preferences we replace good jby good ij, and agent ij only finds good jacceptable. Thus, feasible circulations are in one-to-one correspondence in the two markets. Moreover, the original agents evaluate any circulation in the same way in the two markets. Finally, since the new nodes do not have any strategic role in the extended market (they only have unit capacity),31 the manipulability of any circulation rule does not change from one setting to the other. Heterogeneous goods We can reduce the model with heterogeneous goods to our circulation model as follows. For the sake of exposition, assume that all (units of) goods are distinct. Let each unit of the heterogeneous case be an artificial agent with unit capacity in our circulation model. Each artificial agent only finds acceptable its original owner. Any original agent’s preferences over artificial agents are induced by her original preferences over heterogeneous goods. As an illustration, the generalized TTC for the heterogeneous case, which was introduced and studied in Fujita et al. (2015), is equivalent to the cTTC rule for the reduced circulation market with homogeneous goods in Biró et al. (2022). The artificial agents cannot manipulate the cTTC rule because of their unit capacity. Yet the strategic possibilities of the original agents are different. For instance, a manipulation in which an agent in the heterogeneous goods market hides some of her goods corresponds to a group manipulation in the reduced market. The precise connections between the two markets and the properties of the circulation rules could be pursued in future research. More complex preferences First we discuss the relevance of the assumption that an unacceptable good makes a bundle unacceptable. In our definition of responsiveness of agents’ preferences over bundles we assume that acceptable bundles can only contain acceptable goods (r1). Our results on Single-Serial and Multiple-Serial rules still hold when (r1) is dropped. The reason is that Single-Serial and Multiple-Serial rules do not satisfy individual rationality. However, the assumption is important for SingleSerial-IR and Multiple-Serial-IR rules. Since these rules were constructed to guarantee individual rationality, it is crucial to have enough structure on the set of acceptable bundles. For instance, to obtain the alternative definition of Single-Serial-IR rules (that does not require checks of IR-extendability) we use (r1), see, e.g., the maximum flow problem employed in the proof of Lemma 3. Assumption (r1) is reasonable in many real-life applications, such as Erasmus exchanges (where a student cannot be sent to a university she never applied to) or organ exchanges (where only transplantable organs can be accepted by a country). However, there are also many applications where “negative utility goods” (a.k.a. bads) can be accepted by agents if they are compensated with “positive utility goods.” For instance, consider the allocation of courses to university professors. A professor may have a usual set of acceptable courses, but she may be willing to teach a course she finds much less interesting than any of her usual courses, as long as she is compensated with a new special topics course of her choosing. The non-trivial question of extending our results on individually rational serial rules to cover situations where an acceptable bundle may contain unacceptable goods is left for future research. One could also consider a different input for the rules. In this paper we only use the ordinal preferences of the agents over the individual goods and assume responsive and lexicographic preference extensions. But circulation rules could also be based on the agents’ cardinal utilities of individual goods (see, e.g., Aziz et al., 2019), again with responsive and lexicographic preference extensions. This would extend the class of circulation rules and the set of possible strategic manipulations, for example. More generally, one could study the case where agents submit linear preferences over the whole set of bundles or even choice functions. It could be interesting to focus on particular preference domains, e.g. substitutable choice functions. Such general models are used in some recent studies on stable networks, e.g. Hatfield et al. (2013). However, the main challenge of allowing the agents to submit their full preferences over the possible bundles is that such input would be exponentially large in the number of agents/goods. This is a well-known issue in applications such as course allocation (Budish et al., 2017) or combinatorial auctions (Milgrom, 2000). 7. Related literature and applications Our paper is in the intersection of two strands of literature, namely the literature that studies serial dictatorships for allocation problems and the literature on exchange with multiple indivisible goods. 31 We refer to Biró et al. (2022)for further details. 450 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 In the first strand, serial dictatorships were shown to satisfy desirable properties such as Pareto-efficiency and strategyproofness in various allocation problems. Svensson (1999)characterized serial dictatorships by Pareto-efficiency, nonbossiness Satterthwaite and Sonnenschein (1981), and neutrality in the classical house allocation problem where the houses are public endowments. For multiple object allocation, Pápai (2001), Ehlers and Klaus (2003), and Hatfield (2009) obtained the same characterization result on increasingly smaller preference domains. Namely, Pareto-efficiency, non-bossiness, and strategy-proofness characterize sequential dictatorships (a variation on serial dictatorships where only the first agent is fixed in the ordering and subsequent agents in the ordering are determined by previous assignments). On the domain where agents always desire a fixed quota of heterogeneous objects and preferences are responsive, Hatfield (2009)also proved that these three axioms together with neutrality characterize the subfamily of serial dictatorships. In a more general setting with agent-specific quotas, Hosseini and Larson (2019)proved that when preferences are lexicographic an allocation rule is strategy-proof, non-bossy, neutral, and satisfies a mild Pareto-efficiency requirement if and only if it is a serial dictatorship. Pápai (2000)studied multiple assignment problems with monotonic and quantity-monotonic preferences and established further similar characterizations of serial dictatorships. Consistency and solidarity axioms were considered in the same model by Klaus and Miyagawa (2001) who also derived serial dictatorship results. All these papers study serial dictatorship rules that allow each agent to pick a good or a set of goods only once, which accounts for the positive result on incentives, as indicated by the use of strategy-proofness in many characterizations. When agents are allowed to choose only one good at a time and have multiple turns which are not necessarily consecutive, for example as in our Single-Serial and Single-Serial-IR rules, serial dictatorships possess an intricate strategic structure, which was investigated by Manea (2007). He considered a model in which all bundles are acceptable and preferences are represented by additive utility functions and proved that subgame perfect equilibrium circulations are not necessarily Pareto-efficient and generally not every Pareto-efficient circulation is sustained at some subgame perfect equilibrium in the perfect information game induced by serial rules. We discussed the incentive properties of our rules in Section 5. As we saw, the difficulty with incentives stems from two different sources: one is the above-mentioned multiple non-consecutive turns of agents, which applies to the Single-Serial and Single-Serial-IR rules. The other one is that requiring individual rationality interferes with the nice incentive properties of serial dictatorships and creates room for manipulation by truncation, which applies to the Single-Serial-IR and Multiple-Serial-IR rules. In contrast to our set-up, all of the above papers explored allocation problems without initial private endowments. The second relevant strand of the literature focuses on the exchange of multiple indivisible goods, which presupposes that agents initially own the goods. The first generalization of the Shapley-Scarf market was due to Konishi et al. (2001) who studied the core in a model with multiple types of goods, where each agent initially owns one good of each type and only goods of the same type can be traded for each other. They showed that in this model there is no individually rational, Pareto-efficient, and strategy-proof rule. Klaus (2008)proved that the type-wise top trading cycle rule in this model is not Pareto-dominated by any other strategy-proof rule, while Pápai (2003) obtained an axiomatic characterization of a similar top trading cycles rule in a model with heterogeneous goods and responsive preferences. Pápai (2007)is a further axiomatic study of exchange in a model with general preferences over heterogeneous goods. With the exception of this last paper, all of the above papers on exchange either require or end up with a balanced exchange, depending on the approach they take. Recently, artificial intelligence and computer science papers also considered related exchange problems. Todo et al. (2014)studied a model with multiple private endowments and showed that individual rationality, Pareto-efficiency, and strategy-proofness are not compatible for lexicographic preferences. Fujita et al. (2015)studied a model with lexicographic preferences and showed that their augmented TTC rule always yields an assignment in the core. Hence, their rule is individual rational and Pareto-efficient, but not strategy-proof. However, they proved that it is NP-hard to find a beneficial preference misreport. Lesca and Todo (2018) considered the so-called service exchange problem where each agent is willing to provide her service in order to receive in exchange the service of someone else. Assuming that each agent cares about the service that she receives and the person who receives her service, they showed that finding an individually rational and Pareto-efficient circulation is NP-hard, unless all preferences are “set-restricted.” Apart from Biró et al. (2022), there are four recent, closely related papers that studied the balanced exchange of multiple indivisible goods. Two of these papers are on tuition and student exchanges from a two-sided (Dur and Ünver, 2019) and one-sided (Dur et al., 2019) perspective, respectively. The other two papers are motivated by time banks (Andersson et al., 2021) and shift reallocation (Manjunath and Westkamp, 2021). We discuss below the main differences among the models as well as the main findings of these four papers. Dur and Ünver (2019)studied a model where the agents on the two sides of the market are students and universities. Students want to exchange their seats and universities are interested in exchanging their enrolled students.32 In the largest students exchange program of this kind, the European Erasmus program, students pay their tuition fee to their “home university” during the exchange period. So, to ensure the longevity of the program, it is essential that exchanges be balanced, i.e., for each university, the number of incoming students equals the number of outgoing students. Each university has a priority order over its outgoing students and responsive preferences over incoming students. The latter assumption on the universities’ preferences fits many markets, especially labor markets and those of tuition exchanges, where exchanges are 32 Dur and Ünver (2019)also listed many other applications with similar characteristics where students exchange their tuition, teachers or other professionals exchange their positions temporarily, etc. 451 P. Biró, F. Klijn and S. Pápai Games and Economic Behavior 136 (2022) 428–453 often long-term.33 Assuming that both sides of the market are strategic, Dur and Ünver (2019)proposed a two-sided top trading cycles rule (2S-TTC). They showed that 2S-TTC is balanced-efficient, group strategy-proof for students, acceptable, respecting internal priorities, individually rational, and immune to quota manipulation by universities. Moreover, they proved that 2S-TTC is the unique rule that satisfies the first four properties. In other applications the exchange is short-term, such as the Erasmus exchange program where students are visiting foreign universities for one or two semesters. In this case it seems reasonable to assume that universities care most about their outgoing students, since these students will come back and graduate at their home university. In their follow-up paper on Erasmus exchange, Dur et al. (2019) dropped the assumption of Dur and Ünver (2019) that universities have preferences over incoming students, but kept the internal priority order of universities over their outgoing students. It is assumed that this internal priority order is a non-strategic decision, although in practice it can be strategic, as universities may care about which of their students temporarily visit other universities. Dur et al. (2019)studied a generalized version of the TTC rule with both cycles and chains, allowing for small deviations from the balancedness condition. This approach is closer to Biró et al. (2022) where we also studied generalized TTC rules, while in the current paper we focused on serial rules which are closer to current practices in the Erasmus exchange program. Andersson et al. (2021)studied a balanced exchange problem motivated by time banks. In time banks the participants exchange their services in a one-to-one fashion without monetary transfers. In practice, this is usually implemented either by bilateral agreements or through a dynamic credit system. The model of Andersson et al. (2021)is similar to ours: (i) agents have agent-specific goods and only care about the goods they receive and (ii) the outcome is required to be balanced. However, the main difference is that (Andersson et al., 2021) focused on a different preference domain where each agent (a) has dichotomous preferences over other agents’ goods and (b) has a specific upper bound for each acceptable good (i.e., not one upper bound for the size of bundles). A bundle is acceptable if and only if it contains only acceptable goods and respects the associated upper bounds. An acceptable bundle is preferred to another acceptable bundle if the former contains more goods from other agents. For this setting Andersson et al. (2021)proposed a rule that is individually rational and maximizes the total number of acceptable goods exchanged in a balanced way, which guarantees Pareto-efficiency. They showed that their rule is also strategy-proof and that the underlying graph algorithm can be implemented efficiently. As shown in Biró et al. (2022), the three properties (individual rationality, Pareto-efficiency, and strategy-proofness) are incompatible in our model, except for very specific capacity configurations. Manjunath and Westkamp (2021)studied a balanced exchange problem motivated by shift reallocation. Their model is different from ours in that each agent is assumed to be endowed with heterogeneous goods, in the sense that each agent (worker) can be endowed with different goods (shifts), and not all the goods of an agent may be acceptable to another agent. They studied a restricted trichotomous preference domain: all desirable goods are ranked first, in the most preferred indifference class, followed by all undesirable goods endowed to the agent, leaving the undesirable goods of others for the third and lowest-ranked indifference class. These assumptions are natural in the context of shift exchanges studied by Manjunath and Westkamp (2021), since the acceptability of a shift mainly depends on its timing and not on whose pre-assigned shift it was. In contrast to both (Andersson et al., 2021) and our paper, they dispense with the assumption that a bundle is acceptable if it contains only acceptable goods. Similarly to Andersson et al. (2021), their main result is an efficiently computable rule that is individually rational, Pareto-efficient, and strategy-proof. However, their property of Pareto-efficiency is slightly weaker than the maximal volume property of Andersson et al. (2021), and the two algorithms and the proofs for strategy-proofness are also different. Student exchange programs, time banks, and shift reallocation are all real-life applications that are captured by our model with responsive preferences or can be studied using a slightly adapted model. Another relevant application is financial clearing. Banks or companies often have cyclic liabilities or debts that can cause liquidity problems or even create systemic risk. In a financial clearing (or portfolio compression) the parties involved agree to clear the same amount of debt in a cycle of liabilities (see for example Csóka and Herings, 2018; D’Errico and Roukny, 2021; and Schuldenzucker and Seuken, 2020). Each party has natural preferences over all possible clearances. For instance, each party may want to secure payments from riskier partners first. The search for clearing cycles can be coordinated by private companies or national agencies (as in e.g. Gavrila and Popa, 2021). Any proposed set of clearing cycles constitutes a circulation in the market, and vice versa: any circulation can be decomposed into clearing cycles (see Veraart, 2020). Multiple-Serial-IR rules could serve as appropriate preference-based solutions in these markets for which the particular selection order may be based on an objective criterion such as the financial vulnerability of the companies. If the participants agree to accept any clearing cycle, which ensures that dropping manipulations cannot occur, then the Multiple-Serial-IR rule becomes strategy-proof, given that it is swappingproof (see Proposition 19). References Andersson, T., Cseh, Á., Ehlers, L., Erlanson, A., 2021. Organizing time banks: lessons from matching markets. Am. Econ. J. Microecon. 13 (1), 338–373. Aziz, H., Biró, P., Lang, J., Lesca, J., Monnot, J., 2019. Optimal reallocation under additive and ordinal preferences. Theor. Comput. Sci. 790, 1–15. Aziz, H., Gaspers, S., Mackenzie, S., Walsh, T., 2015. Fair assignment of indivisible objects under ordinal preferences. Artif. Intell. 227, 71–92. Biró, P., Klijn, F., Pápai, S., 2022. Balanced exchange in a multi-unit Shapley-Scarf market. Barcelona School of Economics Working Paper 1342. 33 An example is the French teacher re-allocation scheme (Combe et al., 2022). 452