Theoretical Economics Letters, 2013, 3, 340349 Published Online December 2013 (http://www.scirp.org/journal/tel) http://dx.doi.org/10.4236/tel.2013.36056 Open Access TEL Cycles and Rationalization Patrick de Lamirande Financial and Information Management, Cape Breton University, Sydney, Canada Email: Patrick_deLamirande@cbu.ca Received September 27, 2013; revised October 27, 2013; accepted November 4, 2013 Copyright © 2013 Patrick de Lamirande. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. In accor dance of the Creative Commons Attribution License all Copyrights © 2013 are reserved for SCIRP and the owner of the intellectual property Patrick de Lamirande. All Copyright © 2013 are guarded by law and by SCIRP as a guardian. ABSTRACT This paper studies the composition of the Paretian allocation set in the context of a finite number of agents and a finite number of indivisible goods. Each agent receives at most one good and no monetary compensation is possible (typically called the house allocation problem). I introduce the concept of a cycle which is a sequence of allocations where each allocation is linked to the following allocation in the sequence by the same switch of goods between a subset of agents. I characterize the profiles of agent preferences when the Paretian set has cycles. Keywords: Indivisible Goods; Cycle; Rationalizability; Pareto Allocations 1. Introduction The house allocation problem consists of the assignment of indivisible goods to a set of agents who can receive only one object in the final allocation. Such problems are very common: allocation of rooms between roommates, lectures between professors, offices between colleagues, etc. This class of problems was introduced by [1]. For this paper, agents own all goods collectively. While authors prove the existence of a competitive equilibrium, [2] shows that this competitive equilibrium is unique when preferences are strict over the set of goods. Reference [3] proves that this unique solution can be implemented by a strategyproof allocation mechanism. Furthermore, there is a unique strategyproof, individually rational and Pare to optimal allocation mechanism leading to the unique core allocation [4]. Reference [5] shows the equivalence between the competitive allocation from random en dowments and the random serial dictatorship while [6] proves that all mechanisms that are strategyproof, non bossy and neutral must be serially dictatorial. Reference [7] models the case where there exists at the same time tenants and new comers on the same market. They intro duce the top trading cycles mechanism in this setup and show that it is Pareto efficient, individually rational and strategyproof. Reference [8] introduces the possibility of having weak preferences over the set of goods and shows some restrictions on agent preferences for which effi ciency and coalitional strategyproofness are compati ble1. The purpose of this paper is to look at rationalizability in the context of the house allocation problem. In other words, I am interested in answering the following ques tions: is it possible to say if, for a given set of allocations, there is a preference profile which supports this set as a Paretian allocation set? An example is students’ seats in class. For every lecture, there is an allocation of seats. Considering the set of allocations, it is possible to test the rationality of students’ preferences over seats by studying observed allocations. In existing papers on the house allocation problem, only the [9] mentions explicitly the composition of the Paretian allocation set. They show that for any two allo cations in the Paretian set, there exists a sequence of al locations belonging to the Paretian set such that they are pairwise connected, i.e. there are only two agents swi tching their goods and all others stay with the same good. This means that a set with two allocations that are not pairwise connected cannot be rationalized. The main difficulty of using direct inference, i.e. test ing each possible preference profile if it supports the al location set as a Paretian allocation set, is linked to number of such preference profiles. As an example, if the number of goods is 5, then the number of possible allo 1This list of papers treating of the house allocation problem is not ex haustive.
P. DE LAMIRANDE 341 cations is 120 but the number of preference profiles is close to 25 billion2. Consequently, it seems reasonable to find a quickest method to study rationalizability. In this paper, I introduce the concept of a cycle. A cy cle is a subset of allocations in which a subset of agents switches their goods according to a specific scheme. The presence of cycles in a given set of allocations which is presumingly a Paretian set gives us information on the potential preference profiles which would support this set as a Paretian allocation set. With the concept of a cycle, I derive some conditions regarding the number of alloca tions that have to belong to an allocation set in order for it to be a Paretian allocation set. The paper is organized as follows. In Section 2, I pre sent the house allocation problem and I define the con cept of a cycle. Section 4 talks about the properties of the cycle and Section 5 presents the implication of the pres ence of cycles in the Paretian allocation set. Section 6 concludes. 2. Definitions and Notations Let 1, 2,,N 2 denote the set of agents with . The set of goods is 12 ,,, xx x where all goods are different. I define an allocation 12 ,,,aaa a where i aX is the good allocated to agent i with ij for . For any set of agents and for any set of goods aaij NN X with NX , , NX denotes the set of all possible al locations of goods in to agents in . X N Agent ’s preferences are represented by a binary re lation i which is complete, transitive and antisymmet ric (strict preference). Given 12 i P , xX, 1i2 Px means that agent strictly prefers i1 to 2 . Also, ij YY means agents and PPi have the same pre ferences over the set of goods . I define a profile as Y 1,,PP P and the domain of all possible profiles is denoted by ,NX. Definition 1: An allocation is Pareto optimal for a given profile if a P ˆ aA,NX such that ˆforatleastone ˆˆ or1, 2,, iii jjjj j aPai N aPaa aj PO P denotes the set of all Paretian allocations when the profile is . Then, must be an ele ment of which is the set of all nonempty subsets of P PO P ,NX , NX . It is important to note here that, for all preference profiles , the set is never empty. This means that, for every preference profile , there is at least one allocation which is not Pareto domi nated by another allocation. P PO PP Definition 2: A set is rationalizable if there is pre ference profile such that the Paretian allocation set for is , i.e. S P PS SPOP . 3. Cycles Since direct inference is at least difficult, it seems natural to look at the structure of the Paretian set to identify some patterns that can be used to find one associated preference profile. Two groups of Paretian sets are trivi ally easy to rationalize. First, consider a Paretian set with only one allocation. Any preference profile where every agent has the allocated good as his most preferred good rationalizes this Paretian set. The second case is the other extreme case where the Paretian set is composed be all possible allocations. In such case, any preference profile where agents have the same preferences rationalizes this set. However, intermediate cases are more difficult to infer directly. To solve this problem, I propose the concept of cycle. Definition 3: Let the set and NN X with NX . Let ,n 12 ,,nnn with 12 ,n N ,, nn and 12 ,,, e xxx with 12 ,,, xxX . A set has a cycle ,NXSA ,Cnx if a S 12 ,,,Saa s 12 12 12 12 11 12 22 23 11 ,, ,, ,, ,, nn nn nn nn ax ax ax ax such that 1 2 1 1 12 11 , , , , n n n n ax ax ax ax ax ax ax ax S For example, if the set has the cycle 12 , this means there are three alloca tions and belonging to such that 3 xx 3 11 11 2 22 122 33 13 2 ,, ,, axax ax axax 1,2, 3,C 1 ,aa , 2 ,x aS 1 2 33 2 33 3 132 ,, ax axax ax 1 It is important to underline that and n are vectors and not subsets of and N respectively. The reason is that the order of appearance within the vector is im portant to the definition of the cycle. To illustrate the importance of this distinction, consider the two following sets: 232 13 1 ,,, , ,,, , xx xx xxxx 31312 32 321 ,, ,, ,,, , x xxx x xxx 11 2 x x 2 S S S The set 1 has the cycle 123 1,2, 3,,,Cxxx and 2 the cycle S 13 2, 3,,,C2. But those two cy cles are different. For this reason, vectors must be used to define a cycle. 1, xxx 2The number of possible allocation is given by while the number !n of possible preference profiles is . !n n Open Access TEL
P. DE LAMIRANDE 342 Also, it should be noted that it is possible to write the same cycle in many ways. Lemma 1 gives the number of ways to write the same cycle3. Lemma 1: Any cycle of elements can be written in 2 card R ways where 1, 2,,1with0R mod where mod is the modulo operator and card R re turns the number of elements in R (cardinality of R )4. The following example illustrates the lemma. Example 1: Suppose I have the set 123 231 312 ,,,,, , ,,Sxxxxxxxxx . Then, by Lem ma 1, there are 2 3 33card R18 ways to write the cycle: 123 231 312 123 231 312 123 231 312 321 213 132 321 1, 2, 3,,,1, 2, 3,,, 1, 2, 3,,,2, 3,1,,, 2, 3,1,,,2, 3,1,,, 3,1, 2,,,3,1, 2,,, 3,1, 2,,,3, 2,1,,, 3, 2,1,,,3, 2,1,,, 2,1,3 ,,,2,1, CxxxCxx CxxxCxx CxxxCxx CxxxCxx CxxxCxx CxxxCxx CxxxC x x x x x x 213 132 321 213 132 3,, , 2,1,3,,,1,3, 2,,, 1,3,2,,,1,3, 2,,, xx CxxxCxx CxxxCxx x x It must be noted that card R is always higher or equal to 2 when is higher or equal to 3. The number 1 and1 always belong to R . Since the number of ways to write the same cycle can be large5, I propose using the lexicographic ordering to have a unique notation for a given cycle. Definition 4: For two vectors and of l com ponents, is lexicographically dominated by w if v w v 11 112 2 112 2 or ,or ,,, ll wv wvwv wvwv wv The first step is to choose from all possibilities of writing a given cycle the ways for which the vector is lexicographically dominated by (or equal to) the others. Secondly, from those variants, I choose the one for which the component subscripts of n are lexicographically dominated by the other vector . Let’s apply this process to the cycle in Example 1. The first step tells us to select the vector which is lexico graphically dominated by the others. This vector is n 1,2, 3. Then, from the different ways to write the cycle with 1,2, 3n , which are 123 1, 2,,,Cxx3 ,x , 23 3 ,,,x 1 and 1, 2,C xx 312 1, 2,,,Cxx3 ,x , we select the one which has the vector whose component subscripts are lexicographically dominated by the com ponent subscripts of the other ’s. I find that the unique solution is 123 I most emphasize that the definition of a cycle is inde pendent of what other agents get. For example, consider the two following sets: 1,2, 3,C, ,xxx . 1 12345 1245312534 2 2134521453 12534 ,,,,, ,,,,, ,,,, ,,,,,,,,,,,,,, S xxxx xxxxx xxxxx S xxxxxxxxx xxxxx These sets have the same cycle 345 3, 4, 5,,,Cxxx even if they do not have the same allocations. An interesting question is how many different cycles could the set have for set of agents and a given subset of goods ? There are SN X ! different vectors n and ! different possible vectors . There are 2 ! possibilities. But, I have already shown that there are car 2 d R ways to write the same cycle. So there are 2 1! card R different cycles for a given subset of agents and a subset of goods . N X Also, it is possible that a Paretian set contains more than one cycle. In particular, it could happen that the Paretian set PO P has two cycles: ,Cnx and ,Cnx with NN and XX. To examine this case, I define the concept of subcycle. Definition 5: Suppose that the set has a cycle ,SAXN ,Cnx . The cycle ,xCn is a subcycle of ,Cnx if NN and XX. Example 2 illustrates the concept of subcycle. Example 2: Suppose that the set has a cycle S 1234 1, 2,3, 4,,,,Cxxxx . Let s is the set of allocations SS a belonging to such that S 1122 33 44 12 2334 41 13 24 3142 14 2132 43 ,,, ,,, ,,, ,,, ss ss ssss ssss ssss axaxaxax axaxaxax axaxaxax axaxaxax or or or 3All proofs are in Appendix. 4For , , mod is the remainder of the division of by . 5For example, if , then we can write the same cycle in 200 dif ferent ways. 5m Then, this cycle contains 4 different subcycles: 13 1, 3,,Cxx , 24 1, 3,,Cxx , 13 2, 4,,Cxx and 24 2, 4,,Cxx Open Access TEL
P. DE LAMIRANDE 343 To know if the cycle ,Cnx has subcycles, I study the set R . The next lemma tells us the condition nec essary for ,Cnx to have subcycles. Lemma 2: If 1card R , then ,Cnx has subcycles. Example 3: Suppose a set has the cycle S ,Cnx 456 ,,, with and 1, 2,3, 4,5, 6n 123 ,, xxxx 16 ,,aa xx . This means there are 6 allocations belonging to such that: S 11 11 11 112233445566 222222 12233445566 666666 16213243546 ,,,,, ,,,,, ,, ,,, axaxaxaxaxax axaxaxaxaxax axaxaxaxaxax 1 5 Set . Then, cycle 62,3, 4,6R ,Cnx with 1,n4 and 14 , xx is a subcyle of ,Cnx. The last definition about cycles is the following: Definition 6: The set has a complete cycle ,SAXN , c CNX with and NN X where cardXN card if for all 12 ,n,,nnn with 12 ,, ,nnnN and 12 ,,, xxx with 12 ,, , xx X , contains the cycle S ,Cnx . In other words, the set has a complete cycle T , c CNX if there is at least one allocation that belongs to for all possible permutations of goods belonging to between agents belonging to . X N 4. Properties of Cycles and Complete Cycles The presence of a cycle ,Cnx in a Paretian set PO P gives information about the preferences of agents. The first insight given by a cycle is about pairs of goods which are neighbors in the vector . Proposition 1: If has a cycle PO P ,Cnx , then ,ij N 11 11 ,, ,, and kk kk ij xx xx ij xx xx PP PP 1, 2, 3,,1k . Consequently, if the Paretian set has a cycle, then all agents belonging to the cycle have same preferences over any pairs of neighbor goods in that cycle. With this proposition, some information on the associated profile is provided by the presence of a cycle in the Paretian set. However, information on preferences is only over each pair P 1 , kk xx and the pair 1 , x . No informa tion about the preferences over all pairs of goods be longing to the set can be extracted from the cycle. The following example demonstrates the problem. X Example 4: Suppose the cycle 1234 1, 2,3, 4,,,,Cxxx PO P 1234 1313 3131 2222 4444 PPP P xxx xxx xxx xxx Then when the good 3 is allocated to someone who belongs to 1, 3, the good 1 is allocated to the other agent in that set. The cycle does not contain an allocation where the good 1 is allocated to someone in 1, 3 and the good 3 to someone in . This means that agents in 2, 4 1, 3 could have different preferences over the set 13 , x than agents in . The same is true for the set of goods 2, 4 24 , x. To analyze preferences over a pair of goods which are not neighbors to each other in the vector , I use the concept of subcycle. In Section 2, I showed that a subcy cle is a cycle. So, if a cycle has subcycles, Proposition 1 can be used to infer agents’ preferences. Proposition 2: Suppose has a cycle PO P ,Cnx . For R , ,, ii yy yy nn xx xx PP 1, 2,,,1,2,,iy Let’s apply this proposition to the following example. Example 5: Suppose has a cycle PO P ,Cnx with 1, 2,3, 4,5, 6n and ,,, 123456 ,, xxxxxx . Then, this means there are six allocations 123456 ,,,,,aaaaaa POP 11 such that 1 1122 66 22 2 1223 6 333 1324 6 44 4 1425 6 55 5 1526 6 66 6 1621 6 ,,, ,,, ,,, ,,, ,,, ,,, axax ax axax ax axax ax axax ax axaxax axax ax 1 2 3 4 5 Consider goods 1 and 4 . Then, 11 11 44 44 144 , , axax axax 1 Then agents 1 and 4 have same preferences over the 14 , x. If we continue, we find that 1) Agents in 1, 2,3, 4,5, 6 have the same prefer ences over sets 12 , x2 ,, 3 x, 34 , x, 45 , x, 56 , x and 16 , x. 2) Agents in 1, 3, 5 have the same preferences over sets 13 , x, 24 , x, 35 , x, 46 , x, 51 , x and 26 , x. 3) Agents in 2, 4, 6 have the same preferences over sets 13 , x, 24 , x, 35 , x, 46 , x, 51 , x x belongs to the Paretian set . Then the following profile supports the cycle. Open Access TEL
P. DE LAMIRANDE 344 and 26 , x. 4) Agents in 1, 4 have the same preferences over sets 14 , x, 25 , x and 36 , x. 5) Agents in have the same preferences over sets 2,5 14 , x, 25 , x and 36 , x. 6) Agents in have the same preferences over sets 3, 6 14 , x, 25 , x and 36 , x. This result gives additional information about the pro file since it provides information on preferences over pairs of goods which are not neighbors in the cycle. Subcycles can be analyzed on their own since they are themselves distinct cycles, but they could be supported by different preference profiles across agents than the larger cycle. However, by using subcycles, it is only pos sible to show that agents which are neighbors in a subcy cle have the same preferences over all pairs of goods which are neighbor in this subcycle and it is possible that two distinct subsets of agents in the cycle hold different preferences over the same subset of goods. P While Proposition 2 gives us information about pref erences over pairs of goods that are neighbors in a sub cycle, Proposition 3 deals with the other pairs. Proposition 3: Suppose that has a cycle PO P ,x Cn . For all pairs of goods , x X with such that belongs to R , ,,, ij xx xx PP ij N It must be noted that if is a prime number, all pairs of goods are treated by Proposition 3 since 1R . In this case, all agents in have the same preferences over the set . N X Corolla ry 1: If has a cycle PO P ,Cnx and is a prime number, then , , ij N ij YY PP This result is very strong. Only one cycle is enough to conclude that a subset of agents have the same prefer ences over a subset of goods. Unfortunately, as showed above, this result cannot be extended to any number of individuals in . N Another case can lead to the conclusion that agents in a subset of have the same preferences over a subset of goods. N Proposition 4: If has a complete cycle PO P ,CNX X c, the agents in have the same preferences N over . The presence of a complete cycle gives us more in formation about agent preferences. In fact, a cycle could give the same information if the number of elements in that cycle is a prime number. Unless it has this charac teristic, a cycle by itself does not give information on preferences over all goods. But, if a single cycle cannot give the same information than a complete cycle, many cycles can provide it. Proposition 5: Let the set be a subset of and a subset of N N X with .carcardXdN . Let be the lowest prime number such that 0 mod . If PO P has 12!1 cycles with same n and same , then the agents in have the same preferences over . X N X To illustrate the idea of this proof, consider the fol lowing example. Suppose 6card X and suppose has the following cycles : S the 6 cycles given by 12 3 1,2,3,4,5,6 ,,,,,,Cxxx the 6 cycles given by 124 1,2,3,4,5,6 ,,,,,,Cxxx the 6 cycles given by 12 5 1,2,3,4,5,6 ,,,,,,Cxxx the 6 cycles given by 12 6 1,2,3,4,5,6 ,,,,,,Cxxx the 6 cycles given by 132 1,2,3,4,5,6 ,,,,,,Cxxx the 6 cycles given by 142 1,2,3,4,5,6 ,,,,,,Cxxx the 6 cycles given by 152 1, 2,3, 4,5,6,,,,,,Cxxx the 6 cycles given by 16 2 1, 2,3, 4,5,6,,,,,,Cxxx S If has only these cycles, this means agents 1, 3 and 5 could have different preferences over 12 , x than agents 2, 4 and 6. To have all agents with the same pref erences, I must add at least one more cycle. An interesting question concerning the composition of the Paretian set is what happens to the remaining agents. If the Paretian set has a cycle ,Cnx , it is interesting to know if there is an allocation in , NN XX such that agents outside the cycle get the same goods in all alloca tions which can constitute the cycle. In other words, if I define c XX , , the question is: “Is there a c NN N , cc NX zA z such that the set composed by all allocations belonging to where agents in get has a cycle c S PPO c N ,Cnx ?” The answer is: there is no guarantee that the existence of such an element. Take the following example: Example 6: Suppose the preferences for 6 agents are given by 12345 6 111166 333324 242455 425511 554233 666642 PPP PPP xxxxx xxxxx xxxx x xxxxx xxxxx xxxxy Open Access TEL
P. DE LAMIRANDE 345 Then 123456 123465 234156 234165 341256 341265 412356 412365 ,,,,, ,,,,, ,,,,, ,,,,, ,,,,, ,,,,, ,, ,,, ,, ,,, xxxxx POP xxxxx POP xxxxxPOP xxxxx POP xxxxx POP xxxxx POP xxxxx POP xxxxx POP I obtain a cycle ,Cnx with 1, 2,3, 4n and ,,, 1234 xxxx . But the subset of in which allocations give 5 PO P to agent 5 and 6 to agent 6 does not contain the cycle ,Cnx . This is also true for the subset of in which allocations give PO P 6 to agent 5 and 5 to agent 6. Example 6 shows that the existence of such an ele ments is not guaranteed. Nevertheless if such element exists and the agents in have the same preferences over the set , then the Paretian set contains a complete cycle N Y ,X c Proposition 6: Let the set be a subset of and a subset of CN . N N X with carcard X d N . Suppose that all agents in have the same preferences over the set . If the subset of N X PO c N P composed of alloca tions in which agents belonging to get , cc NX zA has the cycle ,Cnx , then PPO has a complete cycle , c CNX in which get . c N z To illustrate this proposition, consider the case where the Paretian set contains the allocations PO P 12345 ,,,, xxxx, 23145 ,,,, xxxx and 312 4 5 ,,,, xxxx. Then, PO P has the cycle 123 xx 1,2, 3,,,Cx . By Proposition 6, the allocations 12 3 45 ,,,, xxxx , 21345 ,,,, xxxx and 32145 ,,,, xxxx PO P must also belong to . Then, PO P 3 ,,, has a complete cycle . 123 1, 2, c Cxx x 5. Cycles and Paretian Sets Finding a preference profile that rationalizes a set is easy in some cases. When S ,SANX a , then any pref erence profile such that agents have same preferences rationalizes the set has a Paretian set. Also, if the set has only one allocation , this set can be rational ized by any preference profile in which each agent gets his most preferred good. Even in the case where has two allocations, this set can be rationalized if the two allocations are pairwise connected. However, it is not possible to go further. At the first look, it is impossible to say if a set can be rationalized even if all allocations are pairwise connected6. S S S S Fortunately, it is possible to find some necessary con ditions on rationalizable sets. Before presenting some conditions on rationalizable sets, I need the following proposition. Proposition 7: Suppose has a cycle PO P ,Ciy. Let be an agent belonging to and l iN an element of . If all agents belonging to X Ni have the same preferences over the set l x , then agents belonging to have same preferences over N l x . The next proposition describes the restrictions on the number of allocations PO P 3n must contain. Proposition 8: If and ,PO PA N X, then 11cardPO Pn !n . If P 1!1P nnPO , then there exist an agent and a good l i belonging to such that there is no allocation belonging to with h a PPO h i ax l and the preference profile is given by 1) , hl Y Y PP ghNYXx 2) , gh X X PP ghNi 3) , ,for some lk lk ik xx xx PPgNixX l x Using Proposition 8, it is possible to know if a set cannot be rationalized just by looking to the number of allocations belonging to this set. If 11!1,!card Snnn1 P, then there exists no preference profile such that SPOP. But, the reverse is not true. This is a necessary condition. Furthermore, it is possible to use cycles to find other in tervals such that, if the number of allocations of a set belongs to those intervals, then this set cannot be ration alized. However, it is not possible to find a general form for all of those intervals. 6. Conclusions The rationalizability in the context of house allocation is hard to provide. Except in cases where there are only a few allocations (1, 2 or 3) or for extreme cases (the set of all possible allocations or for singleton), it is very diffi cult to conclude. The use of cycles can help to analyze the rationalizability of an allocation set. While Proposition 8 studies the number of elements necessary for an allocation set to be rationalizable, Pro position 6 presents a case where the fact that a set con tains a cycle implies that it must contain some specific allocations too. Proposition 8 could be extended to in clude more conditions, but to devise a complete state ment of all cases promises to be very long and compli cated. From my point of view, the most interesting ave 6For example, consider the set 1234 2134 1243 ,,,,,,,, ,,,T xxxxxxxxxxxx. All allocations are pair wise connected but this set cannot be rationalized. Open Access TEL
P. DE LAMIRANDE Open Access TEL 346 nue for the use of cycles is to employ them like I do in Proposition 6. In short, cycles can be useful to study di rectly the rationalizability of an allocation set, since by using cycles, it is possible to say if a given allocation set is missing some allocations to be rationalizable. 7. Acknowledgements I would like to acknowledge Mathieu Dufour, Walter Bossert, Lars Ehlers, Yves Sprumont and Yves Richelle for their helpful comments. Of course, all remanning errors are mine. REFERENCES [1] L. Shapley and H. Scarf, “On Cores and Indivisibility,” Journal of Mathematical Economics, Vol. 1, No. 1, 1974, pp. 2337. http://dx.doi.org/10.1016/03044068(74)900330 [2] A. E. Roth and A. Postlewaite, “Weak versus Strong Do mination in a Market with Indivisible Goods,” Journal of Mathematical Economics, Vol. 4, 1977, pp. 131137. http://dx.doi.org/10.1016/03044068(77)900040 [3] A. Roth, “Incentive Compatibility in a Market with Indi visibilities,” Economic Letters, Vol. 9, 1982, pp. 127132. http://dx.doi.org/10.1016/01651765(82)900039 [4] J. Ma, “StrategyProofness and the Strict Core in a Mar ket with Indivisibilities,” International Journal of Game Theory, Vol. 23, 1994, pp. 7583. http://dx.doi.org/10.1007/BF01242849 [5] A. Abdulkadiroğlu and T. Sönmez, “Random Serial Dic tatorship and the Core from Random Endowments in House Allocation Problems,” Econometrica, Vol. 66, No. 3, 1998, pp. 689701. http://dx.doi.org/10.2307/2998580 [6] L.G. Svensson, “StrategyProof Allocation of Indivisible Goods,” Social Choice and Welfare, Vol. 16, 1999, pp 557567. http://dx.doi.org/10.1007/s003550050160 [7] A. Abdulkadiroğlu and T. Sönmez, “House Allocation with Existing Tenants,” Journal of Economic Theory, Vol. 88, 1999, pp. 233260. http://dx.doi.org/10.1006/jeth.1999.2553 [8] L. Ehlers, “Coalitional StrategyProofness House Alloca tion,” Journal of Economic Theory, Vol. 105, 2002, pp. 298317. http://dx.doi.org/10.1006/jeth.2001.2813 [9] A. BenShoham, R. Serrano and O. Volij, “The Evolution of Exchange,” Journal of Economic Theory, Vol. 114, 2004, pp. 310328. http://dx.doi.org/10.1016/S00220531(03)001121
P. DE LAMIRANDE 347 Appendix Proof of Lemma 1: Suppose the set has a cycle S ,Cnx . Then, the set contains S allocations such that: 11 1 112 2 22 2 1223 1 121 ,,, ,,, ,,, axax ax axaxax axax ax 1 I can write this cycle by using 23 1 ,,,, xx xx . Then, all cycles with ,Cnx which has its com ponents switching neighbor to neighbor relative to give the same cycle. This gives different ways to write the same cycle. I can do the same thing by switch ing elements of and I find also n r ways to write the cycle. Now, consider the number which is a positive integer strictly lower than . Suppose that there exists no positive integer strictly lower than q such that . Let 0modrq 11 21 11 1,1,21, ,11 ,, ,, rmod rmod r nrmod rmodr xxxx x and consider the cycle ,Cn x . Since r does not belong to R , this means all components of n and are different. So, the cycle is the same than ,Cn x ,x Cn . This is true for all which are positive integers strictly lower than r and do not belong to R . Finally, I obtain 2 card R . Proof of Lemma 2: Without lost of generality (WL OG), let’s take the cycle ,Cnx with 1, 2,,n and 12 ,,, xx x . If 1 card R , it means that there is atleast one r which does not belong to R . If does not belongs to rR , this means there is a positive integer q strictly lower than such that . 0rq mod Now, consider the vector of agents 1,1,21, ,11 II nmod modq and the vector of goods 11 21 11 ,, ,, II mod mod q xxxx x Since is not equal to r and is strictly lower then q , the set is not equal to . I obtain the cycle which is a subcycle of N N Cn,x ,Cnx . Proof of Propositio n 1: WLOG, suppose that 1, 2,,n and 12 ,,, xxx . Consider 1 , hh x where . Suppose that agent 1 prefers 1h 1, 2,,1hn over h . Because has the cycle PO P ,Cnx , there is an allocation belonging to PO P such that 1h is allocated to agent 2 and h to agent 1. Since this allocation belongs to , then agent 2 must also prefer PO P 1h to h . Again, because PO P has the cycle ,Cnx , there is an allocation belonging to PO P such that 1h is allocated to agent 3 and h to agent 2. Since this allocation belongs to PO P , then agent 3 must prefer 1h to h . If I continue for all agents belonging to , I find that all agents belong ing to must have similar preferences for all pairs N , hh1 x with h1, 2,,1 and for the pair 1, x . Proof of Propositio n 2: WLOG, suppose that 1, 2,,n and , 12 ,, xxx . Let qr be the smallest integer such that, for r and not belonging to r R , 0modq r r . If does not belong to r R , then for every 1,2,, r and every 1, 2,,1qr , the cycle , s xCn with 1 ,, ,I II mod q r rmod x s s xx 2r m,, ,, I rmod nr xx 2 , od 1qr is a subcyle of ,Cn x. Because , s Cn x is a sub cycle of ,x Cn , PO P must have the cycle , s Cn x. I can then apply Proposition 1. Proof of Propositio n 3: WLOG, suppose that 1, 2,,n and , 12 ,, xx x . Now, take and with 1, 2,,1 and 1,, eta and let . By assumption, belongs to the set R . Suppose that 1 P . Because PO P has the cycle ,Cnx , there is an allocation belonging to PO P such that is allocated to agent 1 and to agent 1. Since this allocation belongs to PO P , then agent 1 must prefer to . Again, be cause PO P has the cycle ,Cn x, there is an allo cation belonging to PO P such that is allocated to agent 2 1mod and to agent 1 . Since this allocation belongs to , then agent PPO 2mod 1 must prefer to . I can continue until I show that Px with , 1mod 1 1, 1, 2mod 1, Since there is no positive integer q such that 0mod q , then the set 1,1, mod 2 1, ,1 1 mod has elements. So all agents belonging to have the same N preferences over the set , x . Proof of Proposition 4: Suppose the opposite is true, i.e. there exists ,ij N and , xX such that i j Px Px This means the good will never be allocated to Open Access TEL
P. DE LAMIRANDE 348 when the good is allocated to . That contradicts the existence of a complete cycle. i Proof of Proposition 5: Suppose is prime. By Corollary 1, if has a cycle PPO ,x Cn , then all agents belonging to have the same preferences over the set . N X Now, suppose is not a prime number and let be the smallest prime number higher than 1 such that . 0mod , Suppose 12 x N 1 X . Let and be two non empty subsets of such that all agents belonging to prefer goods 1 N2 N 1 N to 2 and all agents belonging to prefer goods 2 N2 to 1 . Suppose has PPO cycles for ,Cn t x 1, 2,,t . By convention, 11 t x t for all . For all cycles , I define t ,Cn t x the positions of 2 in the vector so that t v 2 t x By Proposition 3, if there is a such that , and let . 1 t tt t does not belong to R , then all agents must have the same preferences. Suppose t belongs to R for all t. Let the set Π be equal to ,2 ,, which is a subset of R The maximum number such that all . t belong to Π is 21 ! . If t 12! , then there is at least one cycle with ,t Cnx . By Proposi tion 2, then agents belonging to the same set ,,12jj,,j for 1, 2,,j have the same preferences. But, agents in different subsets could have different preferences. If I add another cycle ,Cnx , then does not belong to . If Π does not belong to R , by Propo sition 3, all agents must have the same preferences over 12 , x. If belongs to R , by Proposition 1, for 1, 2,h, ,,hh , agents belonging to 2 ,,h 1mod have the same preferences. Since does not belong to , then and Πh h does not belong to the same set ,,12jj,,j 1, 2j for , , h. So the two sets which contain agent and h must have the same preferences. I can continue to conclude that all agents must have the same preferences. Proof of Propositio n 6: WLOG, suppose that 12 ,,, xxx and 1, 2,N, . Let the set c be equal to and . XX c NNN Now suppose that aP OP where agents belong ing to get goods belonging to . This means there exists an allocation N X ,b AXI such that f or j or at least one 2, , iii jjj j bPa i bPab ajN 1, There are three possible cases for the allocation . The first case consists of a reallocation between agents in .. b c N But this kind of reallocation cannot Pareto dominate the allocation because there exists an allocation belonging to the Paretian set in which agents belonging to get . If a reallocation between agents in dominates , then the allocation should not belong to aa c N c Nz aa PPO . The second case is a reallocation between agents in . Again, it is not possible for this new allocation to dominate the allocation . I assume that all agents in have the same preferences over goods in N Na . Then no reallocation between agents in could Pareto do minate the allocation . N a Finally, the last possibility is a reallocation between agents in both sets Because the agents in have the same preferences, N 1 is preferred to k by all agents in . N Suppose the agent who gets 1 in the new allocation is agent . Because of the cycle, there is an allocation in this cycle such that gets good k . Then this al location could not be in the Paretian set because this al location will be dominated. This means that the allocation where gets k is Pareto dominated and contradicts the existence of a cycle ,x Cn in the set . S Proof of Proposition 7: For all pairs of goods be longing to x , I can apply Proposition 2 or Propo sition 3 to find that there is at least one agent belonging to N with the same preferences as . Because all agents belonging to N have the same preferences over x , then all agents belonging to have the same preferences over N x . Proof of Proposition 8: Let Ψ, NXPOP. By assumption, Ψ1!n . Step 1: Consider the good 1 . Suppose that agent 1 gets good 1 the least often in the allocations belonging to . Then, the number of allocations in Ψ where agent 1 gets Ψ 1 is less than 1! which is strictly lower than 2! . This means there is at least one cycle 1 ,Cnx 1 with 12,3, ,n and 1 23 ,, , xxx since there are exactly 2 ! of such cycles. Now take 2 . Again WLOG, suppose that 2 is the good which is the least assigned to agent 2 in the set when good 1 Ψ is assigned to agent 1. The number of allocations in this case is less than 2! 1 which is strictly lower than . This means there is at least one cycle 3! 2 ,Cn2 x with 23, ,n and Open Access TEL
P. DE LAMIRANDE Open Access TEL 349 2 2 3,, n xx since there are exactly of such cycles. 3! I can continue until 1t is a prime number. Let belong to 1tt ,,, xx and suppose that agent gets good the most often in the allocations be longing to when 1 PO P is allocated to agent 1, 2 to agent 1 2,,t to agent . Then, by Corol lary 1, all agents who belong to 1t tt ,1, , have the same preferences over the set , 1tt ,, xxx Step 2: Now, consider the general case where agents in . ,1,,ss 12 ,,, ss s have the same preferences over the set , xx xx . But there is at least one cycle ,Cnx with ,,,1nss 12 ,, ss s and ,, xx xx N ,, ss 12 , s . By Proposition 7, all agents belonging to must have the same preferences over the set , xx xx . Step 3: I can use the same approach with the two re maining . Doing so, I find that all agents belonging to ,1,,ss have the same preferences over the set 12 ,,, ss s, xx x 2,3, , . I use this approach until I find that all agents belong ing to 23 ,,, have the same preferences over the set xx . Step 4: If Ψ is strictly lower than , this means there is at least one cycle 1!n ,Cnx, Then, by Proposition 7, all agents have the same preferences over the set 23 ,,, xx . Now, if steps 1 to 3 are done once again with 2 and 3 instead of 1 , it can be seen that all agents must have the same preferences over the set 123 ,,,, xxx . Step 5: Now suppose that Ψ is equal to 1! . Suppose that there are two allocations and be longing to 1 a2 a such that all agents get different goods, there is no 12 such that aa 1, 2,, Let the vector be the cycle of goods from to . In other words, the good allocated to agent . 1 ai 2 a i in the allocation goes to agent 1. Since there are two allocations composing the same cycle 1 a i ,Cnx and there are 1! allocations, this means there is at least one cycle and I obtain that all agents must have the same preferences. The only way to avoid the possibility of having a cycle of elements in the set is for all allocations belonging to PPO , there is a good which is never allocated to an agent. Suppose this good is and the agent never getting in PO P is . Since all allocations belong to PO P , all agents have the same preferences over the set I and all agents belonging to x have the same preferences over the set . If all agents have the same preferences, then PO P must contain all allocations. So, this means there is at least one good belonging to x for which agent and other agents must have different preferences.
