Efficient and strategy-proof allocation mechanisms in economies with many goods

Momi, Takeshi Article Efficient and strategy-proof allocation mechanisms in economies with many goods Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Momi, Takeshi (2017) : Efficient and strategy-proof allocation mechanisms in economies with many goods, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 12, Iss. 3, pp. 1267-1306, https://doi.org/10.3982/TE1792 This Version is available at: https://hdl.handle.net/10419/197133 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Theoretical Economics 12 (2017), 1267–1306 1555-7561/20171267 Efficient and strategy-proof allocation mechanisms in economies with many goods Takeshi Momi Department of Economics, Doshisha University In this paper, we show that in pure exchange economies where the number of goods equals or exceeds the number of agents, any Pareto-efficient and strategyproof allocation mechanism always allocates the total endowment to some single agent even if the receivers vary. Keywords. Social choice, strategy-proofness, Pareto efficiency, exchange economy. JEL classification. D71. 1. Introduction Following the seminal work of Hurwicz (1972), the manipulability and efficiency of allocation mechanisms in pure exchange economies have been studied intensively. Zhou (1991) established that any Pareto-efficient and strategy-proof allocation mechanism is dictatorial in exchange economies with two agents having classical (i.e., continuous, strictly monotonic, and strictly convex) preferences. The dictatorship result in twoagent economies has been strengthened by being proven in the domain of restricted preferences.1 Compared with the result in two-agent economies, it is an open question whether Pareto-efficient and strategy-proof allocation mechanisms can be characterized in economies with many agents. This is the issue that we examine in this paper. In manyagent economies, there actually exist Pareto-efficient, strategy-proof, and nondictatorial allocation mechanisms. Satterthwaite and Sonnenschein (1981) constructed such a mechanism, relying on the reverse dictator’s preference, to select one agent among the remaining agents, who is allocated the total endowment. Kato and Ohseto (2002) constructed a mechanism in economies with four or more agents, such that all agents have the opportunity to be allocated the total endowment. A specific feature shared by all known Pareto-efficient and strategy-proof allocation mechanisms is that some single agent receives the whole amount of goods even if the receivers vary. Such a mechanism is called alternately dictatorial. The natural question to be asked is whether there exists a Pareto-efficient, strategy-proof, and nonalternately dictatorial allocation mechanism. Takeshi Momi : [email protected] I would like to thank the three anonymous referees and a co-editor for their helpful comments and suggestions. 1See Schummer (1997), Ju (2003), Hashimoto (2008), and Momi (2013a). Nicoló (2004), however, showed a Pareto-efficient, strategy-proof, and nondictatorial mechanism in the domain of Leontief preferences. Copyright ©2017 The Author. Theoretical Economics. The Econometric Society. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at http://econtheory.org. DOI: 10.3982/TE1792 1268 Takeshi Momi Theoretical Economics 12 (2017) In this paper, we show that in exchange economies where the number of goods equals or exceeds the number of agents, any Pareto-efficient and strategy-proof allocation mechanism is alternately dictatorial. We believe that our method and result provide a first step toward solving the general question without conditions on numbers of goods and agents. In the following subsections, we discuss our method in detail and compare our result with those of related papers to highlight the contributions in this paper. 1.1 Approach In this paper, we study what we call the option set in detail. An agent’s option set, when the other agents’ preferences are fixed, is defined as the union of the agent’s consumption bundles allocated by a mechanism while his preference changes. Then the agent’s consumption bundle allocated by a strategy-proof mechanism should be the most preferred one in the option set with respect to his preference. Therefore, the option set completely describes how the agent’s consumption changes under a strategy-proof mechanism in response to changes in his preference when the other agents’ preferences are fixed. Note that the option set must be either the zero consumption bundle or the total endowment, under an alternately dictatorial mechanism. In this paper, we assume that a positive consumption bundle different from the total endowment is allocated by a mechanism, and we then study the agent’s option set in a neighborhood of the consumption bundle. Through the analysis of the option set, we investigate how consumption changes in response to changes in the agent’s preference, and we obtain allocations that contradict the Pareto efficiency and strategy-proofness of the mechanism. This is the approach that Hashimoto (2008)andMomi (2013a, 2013b) followed to analyze two-agent economies. In two-agent economies, we can determine an agent’s option set as the inverted image of an upper contour set of the other agent’s preference. This easily yields the dictatorship result in two-agent economies. In economies with many agents, we cannot obtain the exact shape of the option set. However, we can still derive the topological properties of the option set. Roughly speaking, we show that in a neighborhood of an allocated consumption bundle that is neither zero nor the total endowment, the option set is the smooth surface of a strictly convex set. This property is sufficient to yield allocations that contradict Pareto efficiency and strategy-proofness. Throughout the paper, the condition that the number of goods equals or exceeds the number of agents plays an important role. In the core part of the paper, we deal with homothetic preferences and consider preferences that satisfy independence in the following sense. An efficient allocation given by a Pareto-efficient mechanism uniquely determines the supporting price, and the supporting price vector uniquely determines the direction of possible consumption of each agent with a homothetic preference. We refer to this direction vector as the consumption-direction vector of the agent. If these consumption-direction vectors are independent among agents, then there is a unique way to scale these vectors so that they sum up to the total endowment. That is, a supporting price induced by a Pareto-efficient mechanism determines the allocation itself Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1269 when the consumption-direction vectors are independent. In other words, a consumption bundle of an agent uniquely determines the other agents’ consumption bundles under independence of the consumption-direction vectors. This works in many-agent economies as in two-agent economies: an agent’s consumption immediately determines the other agent’s consumption as the rest of the goods, which makes two-agent economies decisively tractable. It is clear that we need at least as many goods as the number of agents for the existence of a preference profile satisfying the independence of the consumption-direction vectors. Through the option set, we know how an agent’s consumption changes in response to changes in his preference, as mentioned above. If the consumption-direction vectors are independent, this change of an agent’s consumption exactly determine how other agents’ consumption changes, that is, how the allocation itself changes. Using this, the proof in this paper proceeds as follows. We suppose that an agent is allocated consumption that is neither zero nor the total endowment. First, we establish that the agent’s option set is the smooth surface of a strictly smooth set in a neighborhood of the consumption bundle. Then we observe that such an option set induces allocations that contradict the Pareto efficiency and strategy-proofness. This implies that any agent’s consumption is either zero or the total endowment; that is, the allocation is alternately dictatorial. 1.2 Related literature As mentioned above, the general characterization of Pareto-efficient and strategy-proof mechanisms in many-agent economies is still an open problem. Some studies show the incompatibility of Pareto efficiency and strategy-proofness with allocation restrictions. Serizawa (2002) shows the incompatibility with the individual rationality restriction, where agents originally possess their initial endowments and a mechanism is assumed to allocate consumption that benefits all agents. Serizawa and Weymark (2003) show the incompatibility with the minimum consumption guarantee restriction, where the consumption of each agent is assumed to be away from zero by some minimum distance. Momi (2013b) shows the incompatibility with a simple positivity restriction, where a mechanism is assumed to allocate positive consumption to all agents. Alternatively, Barberà and Jackson (1995) discard Pareto efficiency and characterize strategy-proof mechanisms satisfying the individual rationality restriction. These allocation restrictions are so strong that they exclude any mechanism wherein some agents receive zero consumption. In particular, alternately dictatorial allocations violate these restrictions. Therefore, as long as there are at least as many goods as agents, the result in this paper, where Pareto efficiency and strategy-proofness induce alternately dictatorial allocations, yields the above-mentioned results by Serizawa (2002), Serizawa and Weymark (2003), and Momi (2013b) as a corollary. Some studies investigate the nonbossiness condition. A mechanism is called nonbossy if a change in the preference of an agent does not affect the allocation as long as it does not affect the agent’s own consumption. Momi (2013b) shows that any Paretoefficient, strategy-proof, and nonbossy mechanism is dictatorial. Goswami et al. (2014) 1270 Takeshi Momi Theoretical Economics 12 (2017) show that any Pareto-efficient, strategy-proof, nonbossy, and continuous mechanism is dictatorial even in the restricted domain of quasi-linear preferences. See Hatfield (2009) for a study of Pareto-efficient, strategy-proof, and nonbossy mechanisms in the context of allocating indivisible goods. The nonbossiness condition almost immediately implies that an alternately dictatorial mechanism is dictatorial; that is, it excludes a mechanism where receivers of the total endowment vary. Therefore, as long as there are at least as many goods as agents, the above-mentioned result by Momi (2013b) is obtained as a corollary of this paper’s result. The characterization of Pareto-efficient and strategy-proof mechanisms has been obtained not only for two-agent economies but also for three-agent economies. Momi (2013b) proves that any Pareto-efficient and strategy-proof allocation mechanism in three-agent economies is either dictatorial or of the Satterthwaite and Sonnenschein (1981) type. Unfortunately, this approach crucially relies on the assumption of three agents and it seems difficult to extend it to economies with more agents. Although Momi (2013b) studies the option set, he focuses on a preference profile where two out of three agents have the same preference. In such a case, these two agents can be identified, and the option set of the other agent is given by the turned-over image of an upper contour set of this preference, as in two-agent economies. Alternatively, given the assumption on the numbers of agents and goods, the current paper’s result does not cover the case of economies with three agents and two goods, which is covered by Momi (2013b). However, it might be possible to extend our proof to cover this case. As mentioned in the previous subsection, and as is seen in the proof, what is crucial is that the consumption bundle of an agent uniquely determines the other agents’ consumption. Suppose that the number of agents exceeds the number of goods by exactly 1. If the consumption bundle of an agent is determined, then the other agents’ consumption should be determined uniquely under independence of their consumption-direction vectors because their total consumption equals the total endowment minus the predetermined consumption. However, such a slight extension is of minor importance. The interesting and challenging question is, of course, whether we can have a Pareto-efficient, strategy-proof, and nonalternately dictatorial allocation mechanism without any restrictions on the numbers of agents and goods. The rest of the paper is organized as follows. Section 2 describes the model and results. Section 3 explains some technical aspects of the paper and demonstrates a technique for constructing a preference. Section 4 reveals the properties of the option set. Sections 5and 6provide the proofs of the results in Section 2.Section 7 provides concluding remarks. The Appendix contains proofs of all lemmas and propositions in Sections 3and 4. 2. Model and results We consider an economy with Nagents, indexed by N={1N},whereN≥2,and Lgoods, indexed by L={1L},whereL≥2. The consumption set for each agent is RL +. A consumption bundle for agent i∈Nis a vector xi=(xi 1xi L)∈RL +.The total endowment of goods for the economy is =(1L)∈RL ++. An allocation is a Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1271 vector x=(x1xN)∈RLN +. Thus, the set of feasible allocations for the economy with Nagents and Lgoods is X=x∈RLN +: i∈N xi≤ A preference Ris a complete, reflexive, and transitive binary relation on RL +.The corresponding strict preference PRand indifference IRare defined in the usual way. For any xand xin RL +,xPRximplies that xRxand not xRx,andxIRximplies that xRxand xRx. Given a preference Rand a consumption bundle x∈RL +, the upper contour set of Rat xis UC(x;R) ={x∈RL +:xRx}, and the lower contour set of Rat xis LC(x;R) ={x∈RL +:xRx}.WeletI(x;R) ={x∈RL +:xIRx}denote the indifference set of Rat x,andletP(x;R) ={x∈RL +:xPRx}denote the strictly preferred set of Rat x. A preference Ris continuous if UC(x;R) and LC(x;R) are both closed for any x∈ RL +. A preference Ris strictly convex on RL ++ if UC(x;R) is a strictly convex set in RL for any x∈RL ++. A preference Ris monotonic if, for any xand xin RL +,x>x implies that xRx.2A preference Ris strictly monotonic on RL ++ if, for any xand xin RL ++, x>x implies that xPRx.3A preference Ris homothetic if, for any xand xin RL +and any t>0,xRximplies that (tx)R(tx). A preference Ris smooth if for any x∈RL ++, there exists a unique vector p∈SL−1 +≡{x∈RL +:x=1}such that pis the normal of a supporting hyperplane to UC(x;R) at x. We call the vector pthe gradient vector of Rat x, and write p=p(Rx). Note that if Ris smooth, strictly convex on RL ++,and strictly monotonic on RL ++, then the gradient vector is positive in the positive orthant: p(R x) ∈SL−1 ++ ≡{x∈RL ++ :x=1}for any x∈RL ++. We call a preference classical when it is continuous, strictly convex on RL ++,and strictly monotonic on RL ++,andweletRCdenote the set of classical preferences. Furthermore, we let Rdenote the set of classical, smooth, and homothetic preferences. In this paper, we prove the results in the restricted domain Rand then extend them to RC. A preference profile is an N-tuple R=(R1RN)∈RN. We write the subprofile obtained by removing Rifrom Ras R−i=(R1Ri−1Ri+1RN)and write the profile (R1Ri−1¯ RiRi+1RN)as (¯ RiR−i).WealsowriteR−{ij}to denote the subprofile obtained by removing Riand Rjfrom R. A social choice function f:RN→Xassigns a feasible allocation to each preference profile in RN. For a preference profile R∈RN, the outcome chosen can be written as f(R)=(f 1(R)fN(R)),wherefi(R)is the consumption bundle allocated to agent i by f. Definition 1. A social choice function f:RN→Xis strategy-proof if fi(R)Rifi(¯ Ri R−i)for any i∈N,anyR∈RN,andany ¯ Ri∈R. A feasible allocation is Pareto efficient if there is no other feasible allocation that benefits someone without making anyone else worse off. That is, x∈Xis Pareto efficient 2For vectors xand xin RL,x>x denotes that xl≥x lfor any l∈Land x= x. 3Therefore, if Ris continuous, strictly convex on RL ++, and strictly monotonic on RL ++,thenUC(x;R) ⊂ RL ++ for any x∈RL ++ and the boundary ∂RL +is an indifference set. 1272 Takeshi Momi Theoretical Economics 12 (2017) for preference profile Rif there exists no ¯ x∈Xsuch that ¯ xiRixifor any i∈Nand ¯ xjPRjxj for some j∈N. We say that a social choice function is Pareto efficient if it always assigns a Pareto-efficient allocation. Definition 2. A social choice function f:RN→Xis Pareto efficient if f(R)is Pareto efficient for any R∈RN. We say that a social choice function is dictatorial if there exists an agent who is always allocated the total endowment. Definition 3. A social choice function f:RN→Xis dictatorial if there exists i∈N such that fi(R)=for any R∈RN. We say that a social choice function is alternately dictatorial if it always allocates the total endowment to some single agent. Note that under an alternately dictatorial social choice function, the identity of the receiver of the total endowment may vary depending on preference profiles. Definition 4. A social choice function f:RN→Xis alternately dictatorial if, for any R∈RN,thereexistsiR∈Nsuch that fiR(R)=. This paper’s main result is as follows. Theorem.When L≥N, a Pareto-efficient and strategy-proof social choice function f: RN→Xis alternately dictatorial. This is proved in the preference domain R.Let ¯ Rbe a preference domain such that R⊂¯ R⊂RC, and let us extend Definitions 1–4to ¯ R. Corollary.When L≥N, a Pareto-efficient and strategy-proof social choice function f:¯ RN→Xis alternately dictatorial. 3. Preliminary results In this section, we explain some technical aspects of this paper. We introduce a metric in the space of preferences and show a technique of preference construction. Furthermore, we define the pseudo-efficiency of a social choice function and the feasible consumption set for an agent. As in the previous works, including Serizawa (2002)andMomi (2013b), we introduce the Kannai metric into Rfollowing Kannai (1970), to discuss the continuity in R.For x∈RL +\0,welet[x]denote the ray starting from zero and passing through x:[x]= {y∈RL +:y=txt ≥0}.Wedefine1≡(11)∈RL +so that [1]denotes the principal diagonal of RL +. Using these definitions, the Kannai metric d(RR)for continuous and monotonic preferences Rand Ris defined as dRR=max x∈RL + I(x;R) ∩[1]−Ix;R∩[1]  1+x2 Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1273 where ·denotes the Euclidean norm in RL. With the Kannai metric, Ris a metric space. See Kannai (1970) for details. We often discuss the distance between upper contour sets of preferences. Note that any homothetic preference is identified by one indifference set or upper contour set in RL ++ because the other indifference sets of the homothetic preference are determined by similarity transformations. For any subsets Aand Bin RL,wewriteA+B={a+ b∈RL:a∈Ab ∈B}and A−B={a−b∈RL:a∈Ab ∈B}.WecallasubsetA⊂ RL ++ monotonic when x+RL +⊂Aholds for any x∈A,andwedefineMas the set of closed and monotonic subsets of RL ++.ForanyA∈M, the homothetic, continuous, and monotonic preference RAthat has Aas its upper contour set is uniquely determined. We define the distance dM(A B) between Aand Bin Mas dM(AB) =d(RARB) Thus, the convergence of candidate upper contour sets with respect to this metric implies the convergence of the corresponding preferences with respect to the Kannai metric.4 In this paper, we use B(¯ R) ⊂Rto denote the open ball set of preferences in R,with center ¯ Rand radius >0:B(¯ R) ={R∈R:d(R ¯ R) < }.WeuseB⊂Rto denote an open ball set of preferences without a specified center or radius, For a preference R∈Rand a consumption bundle x∈RL +, a preference ¯ Ris called a Maskin monotonic transformation (MMT, hereafter) of Rat xif ¯ x∈UC(x;¯ R) and ¯ x= x implies that ¯ xPRx. It is well known that if an agent receives xat a preference profile R, strategy-proofness implies that this agent receives the same consumption bundle x when his preference is subject to an MMT at x.AsshowninMomi (2013b, Lemma 4), for a preference R∈Rand a consumption bundle x∈RL ++, there exists a preference that is an MMT of Rat xin any neighborhood of R. For a price vector p∈SL−1 ++ and a consumption vector x∈RL ++,weletp⊥denote the hyperplane perpendicular to p, i.e., p⊥={y∈RL:py =0},andletH(x;p) denote the upper right-hand side half-space of the hyperplane, i.e., H(x;p) =y+p⊥+RL +. Now, we demonstrate a technique for constructing a preference that satisfies a given pair of a gradient vector and a consumption bundle in a neighborhood of a given preference. Let ¯ R∈Rbe a preference that has a gradient vector ¯ p∈SL−1 ++ at a consumption bundle ¯ x∈RL ++,asdrawninFigure 1.Welet(xnpn)be another pair consisting of a consumption bundle and a price vector, and construct a preference Rnthat has pnas the gradient vector at xn.Thisnin xnshould not be confused with the subscripts labeling goods. It is not difficult to imagine such a preference Rnin a neighborhood of ¯ Rif 4Note the difference between the Kannai metric for preferences and the Hausdorff metric for the corresponding indifference or upper contour sets. Fix a consumption vector x. the convergence R→R∗with respect to the Kannai metric does not generally imply convergence I(x;R) →I(x;R∗)with respect to the Hausdorff metric because the indifference sets are not bounded. For example, let P ⊂SL−1 ++ be a compact set and let K=z∈P[z]denote the union of rays [z]passing through z∈P. Then I(x;R) ∩Kis compact and the convergence R→R∗implies the convergence I(x;R) ∩K→I(x;R∗)∩Kwith respect to the Hausdorff metric. Alternatively, the convergence of candidate indifference or upper contour sets with respect to the Hausdorff metric implies the convergence of the corresponding preferences with respect to the Kannai metric. 1274 Takeshi Momi Theoretical Economics 12 (2017) Figure 1. Preference construction. pnand xnare sufficiently close to ¯ pand ¯ x, respectively. Furthermore, we can have the preference Rnso that its gradient vector at ¯ xis ¯ pif pn¯ x>p n([xn]∩I(¯ x;¯ R)),asdrawn in Figure 1. To understand this condition, consider another price vector psuch that p¯ x≤p([xn]∩I(¯ x;¯ R)), as drawn in the figure. It is clear that any strictly convex preference with the gradient vector pat xncannot have ¯ pas its gradient vector at ¯ x.Thisis summarized as Lemma 1. Note that the condition pn([¯ x]∩I(xn;¯ R)) > pnxnin the lemma is equivalent to the above-mentioned pn¯ x>p n([xn]∩I(¯ x;¯ R)), because the preference ¯ Ris homothetic. See the Appendix for the proof of Lemma 1. Lemma 1. Let a preference ¯ R∈Rhave a gradient vector ¯ p∈SL−1 ++ at a consumption bundle ¯ x∈RL ++:¯ p=p( ¯ R ¯ x).Let{xn}∞ n=1and {pn}∞ n=1be sequences of consumption bundles and price vectors that converge to ¯ xand ¯ p, respectively: xn→¯ xand pn→¯ pas n→∞. For any >0, there exists ¯ nsuch that for any n>¯ nthere exists a preference Rn∈B(¯ R) such that p(Rnxn)=pn. Furthermore, if pn([¯ x]∩I(xn;¯ R)) > pnxnholds for n> ¯ n,we can have Rn∈B(¯ R) satisfying p(Rn¯ x) =¯ pin addition to p(Rnxn)=pn. We say that a social choice function is pseudo-efficient if it allocates a Paretoefficient allocation or allocates zero consumption to all agents. Definition 5. A social choice function f:RN→Xis pseudo-efficient if, for any R∈ RN,f(R)is Pareto efficient or fi(R)=0for any i∈N. It is clear that if a social choice function is Pareto efficient, then it is also pseudoefficient. Until the last step in the proof of the theorem provided in Section 6,weprove all lemmas and propositions with a pseudo-efficient social choice function rather than with a Pareto-efficient social choice function. This is because, in the proof of the theorem, we apply the lemmas and propositions to a subeconomy N⊂Nwith N(<N) agents. Note that pseudo-efficiency in such a subeconomy does not contradict Pareto efficiency in the whole economy. Let a social choice function fbe Pareto efficient in Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1281 bundles, f2(R1¯ R2¯ R−{12})and f2(R1˜ R2¯ R−{12}), have the same normal vector. This contradicts the strict convexity of the option set shown in Proposition 3 because these two consumption bundles of agent 2do not coincide by our choice of ˜ R2. For a price vector p∈SL−1 ++ in a neighborhood of ¯ p,welet ¯ y(p) denote the point on G1(¯ R−1)such that ¯ y(p) +p⊥is the hyperplane tangent to G1(¯ R−1)at ¯ y(p),andwelet ˜ y(p) denote the point on G1(˜ R2¯ R−{12})such that ˜ y(p)+p⊥isthehyperplanetangent to G1(˜ R2¯ R−{12})at ˜ y(p). Because of Propositions 1–5in the previous section, ˜ y(p) and ˜ y(p) are determined uniquely for any pin a neighborhood of ¯ p. Note that we can pick a price vector pin any neighborhood of ¯ psuch that the hyperplanes ¯ y(p)+p⊥and ˜ y(p)+ p⊥are different. The existence of such a pshould be clear because nonexistence of such apin a neighborhood of ¯ pimplies the coincidence of G1(¯ R−1)and G1(˜ R2¯ R−{12})in a neighborhood of ¯ x1, which contradicts the discussion in the previous paragraph. Thus, we let {pn}∞ n=1be a sequence of price vectors converging to ¯ p:pn→¯ pas n→∞,such that ¯ y(pn)+(pn)⊥and ˜ y(pn)+(pn)⊥are different for any n.Thenwehave¯ y(pn)→¯ x1 and ˜ y(pn)→¯ x1as n→∞. For each sufficiently large n, we pick agent 1’s preferences, R1 nand R1 nin B1, satisfying the following conditions: (i) the gradient vector of R1 nat ¯ y(pn)is pn, (ii) the gradient vector of R1 nat ˜ y(pn)is pn, and (iii) either ¯ y(pn)∈P(˜ y(pn);R1 n)or ˜ y(pn)∈P(¯ y(pn);R1 n). For example, such preferences can be obtained as follows. As the hyperplanes ˜ y(pn)+(pn)⊥and ¯ y(pn)+(pn)⊥are different, ¯ y(pn)is in the upper right-hand side of ˜ y(pn)+(pn)⊥or ˜ y(pn)is in the upper right-hand side of ¯ y(pn)+(pn)⊥.Here,we assume the former, as drawn in Figure 3, and construct R1 nand R1 nsatisfying ¯ y(pn)∈ P(˜ y(pn);R1 n). A symmetric discussion can be applied for the other case. To obtain R1 n∈B1satisfying (i), we directly apply the preference construction in Lemma 1 so that ¯ R,(¯ x ¯ p),and(xnpn)in Lemma 1 correspond to ¯ R1,(¯ x1¯ p),and (¯ y(pn)pn), respectively, in the present setup. As ¯ y(pn)and pnconverge to ¯ x1and ¯ p, respectively, as n→∞,R1 nconverges to ¯ R1,asshowninLemma 1, and hence R1 nis in B1for a sufficiently large n. Alternatively, R1 n∈B1satisfying (ii) and (iii) is obtained as follows. If nsatisfies ¯ y(pn)∈P(˜ y(pn);¯ R1),weconstructR1 nin a neighborhood of ¯ R1satisfying (ii) by directly applying the preference construction in the first part of Lemma 1 so that ¯ R,(¯ x ¯ p), and (xnpn)in Lemma 1 correspond to ¯ R1,(¯ x1¯ p),and(˜ y(pn) pn), respectively, in the present setup. As ˜ y(pn)and pnconverge to ¯ x1and ¯ p, respectively, as n→∞,R1 nconverges to ¯ R1,asshowninLemma 1, and hence R1 nis in B1for a sufficiently large n.If ¯ y(pn)∈P(˜ y(pn);¯ R1), then (iii) is satisfied with R1 nwhen nis sufficiently large because R1 nis then sufficiently close to ¯ R1. Even if nsatisfies ¯ y(pn)/∈P(˜ y(pn);¯ R1),weconstructR1 nas we did in the proof of Lemma 1.Weletnbe a scalar smaller than the distance between the hyperplanes ¯ y(pn)+p⊥ nand ˜ y(pn)+p⊥ n,anddefineEnas the upper contour set of ¯ R1at ¯ y(pn)−npn cut off by the hyperplane ¯ y(pn)+(pn)⊥:En=UC(¯ y(pn)−npn;¯ R1)∩H(¯ y(pn);pn). Then we consider a preference R1such that R1has the gradient vector pnat ˜ y(pn) and the strictly preferred set at ˜ y(pn)includes En:En⊂P(˜ y(pn);R1). The existence of such a preference R1is clear because the set Enis in the upper right-hand side of the hyperplane ˜ y(pn)+(pn)⊥and away from the hyperplane. Then we define Fnas 1282 Takeshi Momi Theoretical Economics 12 (2017) the intersection of the upper contour set of R1at ˜ y(pn)and that of ¯ R1at ¯ y(pn)−npn: Fn=UC(˜ y(pn);R1)∩UC(¯ y(pn)−npn;¯ R1). Note that ¯ y(pn)is in the interior of Fn.This Fncannot be an upper contour set of a smooth preference because it has the edge at the intersection I(˜ y(pn);R1)∩I(¯ y(pn)−npn;¯ R1). We let  nbe a scalar smaller than the distance between ¯ y(pn)and the boundary of Fn. Using this  n, we round the edge of Fnas in Lemma 6 and let R1 nbe the preference whose upper contour set is the smoothed set. That is, we let ¯ D n⊂RL +denote a closed ball with radius  nand define a closed set Cnas the union of such closed balls with radius  nincluded in Fn.Thatis,Cn=¯ D n⊂Fn ¯ D n.Wedefine ˜ R1 nas the preference such that it has Cnas an upper contour set. It is clear from the construction that ˜ y(pn)+(pn)⊥is the supporting hyperplane of Cnat ˜ y(pn)and that ¯ y(pn)is in the interior of Cn, and hence, R1 nsatisfies (ii) and (iii). To observe that R1 nis in B1for a sufficiently large n, note that the set Fnconverges to UC(¯ x1;¯ R1)as n→∞.Asn→∞, the scalar  nwe used to round the edge of Fnconverges to 0.ThusR1 nconverges to ¯ R1as n→∞. We write f(R1 n¯ R−1)=x n=(x1 nxN n)and f(R1 n˜ R2¯ R−{12})=x n=(x1 n xN n).Thisnin xi nand xi nshould not be confused with the subscripts labeling goods. It is clear that x1 n=¯ y(pn)and x1 n=˜ y(pn). We now focus on agent 2’s preferences. Note that x2 nis the most preferred consumption bundle in G2(R1 n¯ R−{12})with respect to ¯ R2, and the gradient vector of ¯ R2at x2 n is pn. Furthermore, x2 nis the most preferred consumption bundle in G2(R1 n¯ R−{12}) with respect to ˜ R2, and the gradient vector of ˜ R2at x2 nis pn. A strictly convex preference cannot have the same gradient vector pnat both consumption bundles x2 nand x2 n. We show that for a sufficiently large n,wehaveagent2’s preference in B2such that the gradient vector at x2 nis pnand the gradient vector at x2 nis arbitrarily close to pn. For example, such a preference can be obtained as follows. We let Dbe a closed ball with a small radius tangent to the hyperplane x2 n+p⊥ nat x2 nin the upper right-hand side of the hyperplane such that D\x2 nis included in P(x2 n;¯ R2). Then we consider the intersection of the ray [x2 n]and the hyperplane x2 n+p⊥ n,andwelet ¯ Dbe the closed ball with the same radius as Dtangent to the hyperplane x2 n+p⊥ nat the intersection in the upper right-hand side of the hyperplane, as drawn in Figure 3. We now define Knas the convex hull of UC(x2 n;¯ R2)∪¯ D:Kn=co(UC(x2 n;¯ R2)∪¯ D). The convex hull Kncannot be an upper contour set of a preference because it is not strictly convex. We construct a preference by Lemma 5. We fix any positive unit vector a∈SL−1 ++ and consider the L−1-dimensional linear space a⊥.Fory∈a⊥,weletL(y) denote the half-line starting from yand extending in the direction of the vector a:L(y) = {x∈RL|x=y+tat ≥0}.Welet0<s<1be a scalar and define ˆ R2 ns as the preference that has the following as an indifference set:  y∈a⊥sL(y) ∩∂Kn+(1−s)L(y) ∩Ix2 n;¯ R2 From the construction, the gradient vector of ˆ R2 ns at x2 nis pnand the gradient vector at x2 nconverges to pnas sconverges to 1.Weobservethat ˆ R2 ns ∈B2for any s∈(01)when nis sufficiently large. As n→∞,pnconverges to ¯ p, and both x1 nand x1 nconverge to Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1283 ¯ x1. Hence, both x2 nand x2 nconverge to ¯ x2. Therefore, as n→∞,x2 nbecomes closer to x2 nand the intersection of [x2 n]and the hyperplane x2 n+p⊥ nalso becomes closer to x2 n. Then the set Knin the above construction becomes closer to the upper contour set UC(x2 n;¯ R2)of the preference ¯ R2. That is, the preference ˆ R2 ns becomes closer to ¯ R2. Now, we set a sufficiently large nso that R1 nR1 n∈B1and ˆ R2 ns ∈B2for any s∈(01). We write f(R1 nˆ R2 ns¯ R−{12})=ˆ xns =(ˆ x1 ns ˆ xN ns)and f(R1 nˆ R2 ns¯ R−{12})=ˇ xns = (ˇ x1 ns ˇ xN ns), and we show that these allocations contradict the strategy-proofness of the social choice function when sis sufficiently close to 1. Alternatively, as the preference ˆ R2 ns has the gradient vector pnat x2 n,themostpreferred consumption in G2(R1 n¯ R−{12})with respect to ˆ R2 ns is x2 n. Therefore ˆ xns =x n,as shown in Lemma 2.Inparticular,ˆ x1 ns =x1 n=¯ y(pn) Alternatively, the gradient vector of ˆ R2 ns at x2 nconverges to pnas s→1as shown above. Therefore, as s→1, the most preferred consumption bundle in G2(R1 n¯ R−{12}) with respect to ˆ R2 ns converges to x2 n.Then ˇ xns converges to x n.Inparticular, ˇ x1 ns converges to x1 n=˜ y(pn)as s→1.AsR1 nand R1 nsatisfy (iii), this implies that ˆ x1 ns ∈ P(ˇ x1 ns;R1 n)or ˇ x1 ns ∈P(ˆ x1 ns;R1 n)for a value of ssufficiently close to 1. This contradicts the strategy-proofness of fon Bwithrespecttoagent1because ˆ x1 ns and ˇ x1 ns are consumption bundles allocated to agent 1for his preferences R1 nand R1 n, respectively, when the other agents’ preferences are (ˆ R2 ns¯ R−{12}). As a preparatory step in proving the theorem, we let R∗=(R1∗RN∗)be a preference profile such that the consumption directions g(Ri∗p),i=1N, are independent for any price vector p∈SL−1 ++ .Forexample,letRi∗,i=1N, be the preferences represented by Cobb–Douglas utility functions ui¯αi(x) =(x1)¯αi 1···(xL)¯αi L,wheretheparameter vectors ¯αi=(¯αi 1¯αi L),i=1N, are independent among agents. Then each g(Ri∗p)is parallel to (¯αi 1/p1¯αi L/pL), and the consumption directions are independent with any price vector. We show that for any preference profile in a neighborhood of R∗, the consumptiondirection vectors are independent at any Pareto-efficient allocation. For a scalar ≥0, we let P={p∈SL−1 ++ :=N i=1tig(Rip)where ti≥0Ri∈B(Ri∗)i ∈N}denote the set of price vectors at the possible Pareto-efficient allocations, with preferences Riin the -neighborhoods of Ri∗,i=1N. Note that the closure of P, i.e., P,isawayfrom the boundary ∂SL−1 ++ when is sufficiently small because Pconverges to P0as →0and because P0, the set of price vectors at possible Pareto-efficient allocations with Ri∗,i∈N, is away from the boundary. We fix a scalar >0so that P⊂SL−1 ++ . For any fixed price vector p, the consumption direction vector g(Rip) converges to g(Ri∗p) as Riconverges to Ri∗with respect to the Kannia metric. Therefore, we let  >0be a sufficiently small scalar such that g(Rip),i=1N, are independent for any Ri∈B (Ri∗),i=1N,andanyp∈P.Wedefineˆ=min{}.Thus, for any preferences Riin Bˆ(Ri∗),i=1N, the consumption directions g(Rip), i=1N, are independent with any price vector at the possible Pareto-efficient allocations with such preferences. We now prove the theorem. We suppose that a social choice function fis Pareto efficient and strategy-proof on the whole domain RN. As mentioned in Section 3, 1284 Takeshi Momi Theoretical Economics 12 (2017) fi(R)∈intA∪{0}for any agent iand any preference profile R. Therefore, all we have to show is that fi(R)/∈int Afor any i=1N and any R∈RN. We assume that an agent receives consumption in int Aat some preference profile ¯ R∈RN(where the consumption-direction vectors are not independent). We show a contradiction. We repeat the replacement of the preferences of agents who receive consumption in intAas follows. We define ¯=ˆ/N. Step 1.Wefirstpickanagenti1who receives consumption in intAat ¯ R.Wereplace his preference with Ri1∗.LetR=(R1RN)denote the new preference profile after this replacement: Ri1=Ri1∗and Ri=¯ Rifor i= i1. Agent i1’s consumption at Ris neither 0nor because of the strategy-proofness of f. Therefore, there exists another agent i2who also receives consumption in int Aat Rbecause of the Pareto efficiency of f. We replace agent i2’s preference with Ri2∗and let R denote the profile after this replacement. Note that agent i2’s consumption at R is neither 0nor because of the strategy-proofness. Then we consider the replacement of ¯ Ri1and ¯ Ri2with any Ri1∈B¯(Ri1∗)and any Ri2∈B¯(Ri2∗), respectively. As a result of this replacement, there should exist a preference profile ˜ R =(˜ R1 ˜ RN)where ˜ Ri1 ∈B¯(Ri1∗)and ˜ Ri2 ∈B¯(Ri1∗),˜ Ri =¯ Rifor any agents other than i1and i2, and there exists a third agent i3other than i1and i2who receives consumption in int Aat ˜ R. If such a preference profile does not exist, then let f be the social choice function f restricted to agents i1and i2, with other agents’ preferences fixed to ¯ Ri,i/∈{i1i2}.Then f is a social choice function in the two-agent economy of agents i1and i2that is Pareto efficient and strategy-proof on B¯(Ri1∗)×B¯(Ri2∗)and that allocates consumption in intAto both agents at (Ri1∗Ri2∗). This contradicts Proposition 6. Step 2.Nowwereplaceagenti3’s preference with Ri3∗.LetR =(R1RN) denote the preference profile after this replacement: Ri1 =˜ Ri1,Ri2 =˜ Ri2,Ri3 = Ri3∗,andRi =¯ Rifor i/∈{i1i2i3}. Note that agent i3’s consumption at R is neither 0 nor because of the strategy-proofness. Then we consider the replacement of Ri1,Ri2,andRi3 with any Ri1∈B¯(Ri1), Ri2∈B¯(Ri2),andRi3∈B¯(Ri3), respectively. As a result, there should exist a preference profile ˜ R =(˜ R1 ˜ RN)where ˜ Ri ∈Bi ¯(Ri)for i∈{i1i2i3},˜ Ri =¯ Rifor i/∈{i1i2i3}, and there exists a fourth agent i4/∈{i1i2i3}who receives consumption in intAat ˜ R. If such a preference profile does not exist, then let f be the social choice function frestricted to agents i1,i2,andi3with other agents’ preferences fixed to ¯ Ri, i/∈{i1i2i3}.Thenf is a social choice function in the three-agent economy of agents i1, i2,andi3that is pseudo-efficient and strategy-proof on B¯(Ri1)×B¯(Ri2)×B¯(Ri3) and that allocates consumption in intAto at least two agents at the preference profile (Ri1Ri2Ri3).5Furthermore, R was obtained as a result of the replacement in the previous step and the replacement of agent i3’s preference: Ri =˜ Ri ∈ 5For example, suppose that fi1(R)∈int A,fi2(R)=0,fi3(R)∈intA, and fi(R)=0for i/∈{i1i2i3}. Then the agents i1,i2, and i3may receive zero consumption without violating the strategy-proofness and Pareto efficiency of the social choice function fwhen agent i2’s preference is replaced. To deal with this case, we proved the lemmas and propositions with a pseudo-efficient social choice function. Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1285 Bi ¯(Ri∗)for i∈{i1i2}and Ri3 =Ri3∗. Therefore, Ri ∈B¯(Ri∗)⊂Bˆ(Bi∗)for any i∈ {i1i2i3}. The consumption-direction vectors of these three agents are independent at (Ri1Ri2Ri3). This contradicts Proposition 6. Step 3. We repeat the process. We replace agent i4’s preference with Ri4∗.Let R =(R1RN)denote the preference profile after this replacement: Ri =˜ Ri for i∈{i1i2i3},Ri4 =Ri4∗,andRi =¯ Rifor i/∈{i1i2i3i4}. Note that agent i4’s consumption at R is neither 0nor because of the strategy-proofness. Then we consider the replacement of the preferences of these agents i1,i2,i3,and i4with any preferences in the ¯-neighborhoods B¯(Ri)of Ri,i∈{i1i2i3i4},respectively. As a result, there should exist a preference profile ˜ R =(˜ R1 ˜ RN)where ˜ Ri ∈Bi ¯(Ri)for i∈{i1i2i3i4},˜ Ri =¯ Rifor i/∈{i1i2i3i4}, and there exists a fifth agent i5/∈{i1i2i3i4}who receives positive consumption in int Aat ˜ R. If such a preference profile does not exist, then let f be the social choice function frestricted to agents i1,i2,i3,andi4, with other agents’ preferences fixed to ¯ Ri, i/∈{i1i2i3i4}.Thenf is a social choice function in the four-agent economy of agents i1,i2,i3,andi4that is pseudo-efficient and strategy-proof on B¯(Ri1)×B¯(Ri2)× B¯(Ri3)×B¯(Ri4)and that allocates consumption in int Ato at least two agents at the preference profile (Ri1Ri2Ri3Ri4). Furthermore, R wasobtainedasaresult of the replacement in the previous step and the replacement of agent i4’s preference: Ri =˜ Ri ∈Bi ¯(Ri)for i∈{i1i2i3}and Ri4 =Ri4∗. Combined with the result Ri ∈B¯(Ri∗)for any i∈{i1i2i3}in the previous step, we have Ri ∈B2¯(Ri∗)⊂Bˆ(Ri∗) for any i∈{i1i2i3i4}. Therefore, the consumption-direction vectors of these four agents are independent at (Ri1Ri2Ri3Ri4). This contradicts Proposition 6. We repeat the process until Step N−2.InStepk(≤N−2), we replace agent ik+1’s preference with Rik+1∗,whereagentik+1receives consumption that is neither 0 nor .WeletRk+1=(R1k+1RNk+1)denote the preference profile after the replacement. We consider replacing these k+1agents’ preferences with preferences in the ¯neighborhoods of Rik+1,i∈{i1ik+1}, respectively, and obtain preference profile ˜ Rk+1=(˜ R1k+1 ˜ RNk+1),where ˜ Rik+1∈B¯(Rik+1)for i∈{i1ik+1}, ˜ Rik+1=¯ Rifor i/∈{i1ik+1},andthereexistsa(k +2)th agent ik+2/∈{i1ik+1} who receives consumption in int Aat ˜ Rk+1. If such a preference profile does not exists, then fk+1, which is the social choice function frestricted to agents i1ik+1with other agents’ preferences fixed to ¯ Ri, is a social choice function in the (k +1)-agent economy that is pseudo-efficient and strategy-proof on B¯(Ri1k+1)× ··· × B¯(Rik+1k+1)and it allocates consumption in intAto at least two agents at the preference profile (Ri1k+1Rik+1k+1).Furthermore, Rk+1was obtained as a result of the replacement in Step k−1and the replacement of agent ik+1’s preference: Rik+1=˜ Rik∈Bi ¯(Rik)for i∈{i1ik}and Rik+1k+1=Rik+1∗. Combined with the result Rik∈B(k−2)¯(Ri∗)for any i∈{i1ik} in Step k−1,wehaveRik+1∈B(k−1)¯(Ri∗)⊂Bˆ(Ri∗)for any i∈{i1ik+1}.Therefore, the consumption-direction vectors of these k+1agents are independent at (Ri1k+1Rik+1k+1). This contradicts Proposition 6. Finally, in Step N−2, we replace agent iN−1’s preference with RiN−1∗,whereagentiN receives consumption that is neither 0nor .WeletRN−1=(R1N−1RNN−1) 1286 Takeshi Momi Theoretical Economics 12 (2017) denote the preference profile after the replacement. We consider replacing these N−1agents’ preferences in the ¯-neighborhoods of RiN−1,i∈{i1iN−1},respectively, and obtain preference profile ˜ RN−1=(˜ R1N−1 ˜ RNN−1),where ˜ RiN−1∈ B¯(RiN−1)for i∈{i1iN−1},˜ RiN−1=¯ Rifor i/∈{i1iN−1}, that is, for i=iN,and the agent iNreceives consumption in intAat ˜ RN−1. Note that RiN−1∈B(N−3)¯(Ri∗)⊂ Bˆ(Ri∗)for i∈{i1iN−1}. We replace agent iN’s preference RiNwith RiN∗and let RNdenote the preference profile after this replacement. Because of strategy-proofness, agent iNreceives consumption that is neither 0nor at RN. Then the Pareto-efficient and strategyproof social choice function fallocates consumption in intAto at least two agents at RN∈N i=1Bˆ(Ri∗), where the consumption-direction vectors are independent. This contradicts Proposition 6. This ends the proof of the theorem. 6. Proof of Corollary The theorem implies that if a social choice function f:RN→Xis pseudo-efficient and strategy-proof, then fi(R)∈{0}for any agent iand any R∈RN. We prove the corollary by repeatedly applying this result, as we repeatedly applied Proposition 6 to prove the theorem. We let f:¯ RN→Xbe a Pareto-efficient and strategy-proof social choice function defined on a domain ¯ RN,whereR⊂¯ R⊂RC.AsinthecaseofR∈RN, as mentioned in Section 3,fi(R)∈intA∪{0}for any agent iand any preference profile R∈¯ RN. Therefore, all we have to prove is that fi(R)/∈intAfor any agent iand any R∈¯ RN. We suppose that ¯ R=(¯ R1 ¯ RN)∈¯ RNis a preference profile where an agent receives consumption in int A, and show a contradiction. We let R∗=(R1∗RN∗)∈RNbeapreferenceprofileinRN. We repeat the replacement of the preferences of agents who receive positive consumption as follows. We first pick an agent i1who receives consumption in intAat ¯ R. We replace his preference with Ri1∗.LetR=(R1RN)denote the new preference profile after this replacement: Ri1=Ri1∗and Ri=¯ Rifor i= i1.Asagenti1’s consumption at Ris neither 0nor , there exists another agent i2who receives positive consumption in int Aat R.Wereplace this agent’s preference with Ri2∗and let R denote the preference profile after this replacement. Note that agent i2’s consumption at R is neither 0nor . Then we consider the replacement of agent i1’s and agent i2’s preferences with any preferences in R. As a result of the replacement, there should exist a preference profile ˜ R =(˜ R1 ˜ RN),where ˜ Ri1 ∈R,˜ Ri2 ∈R,and ˜ Ri =¯ Rifor i/∈{i1i2},andthereexists another agent i3, different from i1and i2, receiving positive consumption in intAat ˜ R. If such a preference profile does not exist, then let f be the social choice function f restricted to agents i1and i2, with other agents preferences fixed to ¯ Ri,i/∈{i1i2}.Then f is a social choice function in the two-agent economy of agents i1and i2that is Pareto efficient and strategy-proof on R×Rand allocates consumption in int Ato both agents at (Ri1∗Ri2∗). This contradicts the theorem. Now we replace agent i3’s preference with Ri3∗and let R denote the preference profile after the replacement: Ri1 =˜ Ri1,Ri2 =˜ Ri1,Ri3 =Ri3∗,andRi =¯ Rifor Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1287 i/∈{i1i2i3}. Note that agent i3’s consumption at R is neither 0nor .Thenweconsider the replacement of the preferences of agents i1,i2,andi3with any preferences in R. As a result of the replacement, there exists a preference profile ˜ R,where ˜ Ri ∈R for i∈{i1i2i3},˜ Ri =¯ Rifor i/∈{i1i2i3}, and there exists a fourth agent i4/∈{i1i2i3} who receives consumption in int Aat ˜ R. If such a preference profile does not exist, then let f be the social choice function frestricted to agents i1,i2,andi3, with other agents’ preferences fixed to ¯ Ri,i/∈{i1i2i3}.Thenf is a social choice function in the three-agent economy of agents i1,i2,andi3that is pseudo-efficient and strategy-proof on R×R×Rand allocates positive consumption in int Ato at least two agents at the preference profile (Ri1Ri2Ri3). This contradicts the theorem. We replace the fourth agent’s preference with Ri4∗and consider the replacement of these four agents’ preferences with any preferences in R. Repeating this process, we finally obtain a preference profile in RNwhere at least two agents have consumption in intA. This contradicts the theorem and ends the proof of the corollary. 7. Concluding remarks In this paper, we prove that as long as there are at least as many goods as agents, a Paretoefficient and strategy-proof social choice function is alternately dictatorial. Our proof is based on the analysis of the option set. We show that the option set is the smooth surface of a strictly convex set if a consumption bundle is allocated in the interior of the feasible consumption set. Then we observe that such an option set induces allocations that contradict Pareto efficiency and strategy-proofness to prove that any agent is allocated zero consumption or the total endowment. As far as we are aware, this paper is the first to investigate the option set in many-agent economies. We believe that this approach will be useful for the study of the properties of a strategy-proof social choice function in more general setups. The difficulty in dealing with economies with many agents is that the price vector does not uniquely determine the allocation. In other words, the consumption bundle of an agent does not determine the other agents’ consumption. This is in sharp contrast to two-agent economies, where one agent’s consumption determines the other’s uniquely, because their consumption bundles sum to the total endowment under Pareto efficiency. In this paper, to overcome this difficulty, we made the key assumption that there are at least as many goods as agents. Under this assumption, it is possible to find a preference profile that ensures the independence of the consumption-direction vectors. If the consumption-direction vectors are independent, then an agent’s consumption determines other agents’ consumption uniquely. Using this property, we first prove the alternately dictatorial result at such a preference profile and then extend it to preference profiles that may not satisfy the independence of the consumption-direction vectors. It is still an open question whether a Pareto-efficient and strategy-proof social choice function is alternately dictatorial in economies where the number of agents exceeds the number of goods. It is clear that consumption-direction vectors are dependent in such an economy and that our approach cannot be applied directly to this type of economy. In future research, we hope to find answers to this challenging question. 1288 Takeshi Momi Theoretical Economics 12 (2017) Figure 4. Construction of Is. Appendix A.1 Technical results In this section, we prove some technical results concerning preference construction that we repeatedly use in the proofs of the lemmas and propositions. We fix any positive unit vector a∈SL−1 ++ and consider the L−1-dimensional hyperplane a⊥.Fory∈a⊥,welet L(y) denote the half-line starting from yand extending in the direction of the vector a: L(y) ={x∈RL|x=y+tat ≥0}. For any consumption vector x∈RL +and any preference R∈R, the indifference set I(x;R) intersects with L(y) only once for any y∈a⊥because Ris strictly monotonic in RL ++. If A⊂RL ++ is a closed, strictly convex set with smooth boundary satisfying x+RL +⊂ Afor any x∈A, then there exists a preference R∈Rsuch that Aequals an upper contour set of R.LetB⊂RL ++ be a closed, convex set with a smooth boundary satisfying x+R+⊂Bfor any x∈B.WhenBdoes not satisfy strict convexity, it cannot be an upper contour set of a preference in R. We often make the set Binto a strictly convex set by considering a convex combination of Bwith a strictly convex set Aas follows. With a parameter s∈[01],wedefineI sas Is= y∈a⊥sL(y) ∩∂A+(1−s)L(y) ∩∂B(2) Figure 4 depicts the construction of Is. Lemma 5. For any s∈(01),thesetIs+RL +,whereIsis constructed by (2),isaclosed, strictly convex set and its boundary Isis smooth. Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1289 Proof. We choose any orthogonal unit vectors e1eL−1that span a⊥, and introduce a new orthogonal coordinate system (z1zL)so that the set of vectors e1eL−1, and ais its basis. That is, z=(z1zL)in this coordinate system corresponds to z1e1+···+zL−1eL−1+zLain the original coordinate system (x1xL).Wewritez−L to denote the first L−1elements: zL=(z1zL−1). As Aand Bare closed sets satisfying x+RL +⊂Afor any x∈Aand x+RL +⊂Bfor any x∈B, the half-line L(y) intersects with the boundaries ∂A and ∂B only once for any y∈a⊥. Thus, we let α:RL−1→R+and β:RL−1→R+be functions in the coordinate system (z1zl)so that the graphs equal the boundaries ∂A and ∂B, respectively: ∂A ={(z−Lα(z−L)) ∈RL|z−L∈RL},∂B ={(z−Lβ(z−L)) ∈RL|z−L∈RL}. We let γs:RL→R+denote the function defined as γs(z−L)=sα(z−L)+(1− s)β(z−L).ThenI sdefined by (2) equals the graph of γsand the set Is+RL +equals {(z−LzL)∈RL|zL≥γs(z−L)}in the coordinate system (z1zL). Therefore, Is+RL +is aclosedset. For the strict convexity of Is+RL +, we need to prove the strict convexity of the function γs. Pick any z −L∈RL−1and z −L∈RL−1,andletz −L=qz −L+(1−q)z −Lwith any scalar q∈(01). All we have to show is γsz −L<qγ sz −L+(1−q)γsz −L(3) The left-hand side of (3)isγs(z −L)=sα(z −L)+(1−s)β(z −L). The right-hand side of (3)isqγs(z −L)+(1−q)γs(z −L)=q{sα(z −L)+(1−s)β(z −L)}+(1−q){sα(z −L)+(1− s)β(z −L)}.AsAis strictly convex, the function αis strictly convex, and hence α(z −L)< qα(z −L)+(1−q)α(z −L).AsBis convex, the function βis convex, and hence β(z −L)≤ qβ(z −L)+(1−q)β(z −L). Therefore, we have the inequality (3). As both Aand Bhave smooth boundaries, the functions αand βare differentiable.6 Then γsis also differentiable, and Isis a smooth boundary of the set Is+RL +.7 We often turn a convex set into a convex set with a smooth boundary by rounding its edges. Let A⊂RLbe a closed convex set such that its interior is not empty. We let ¯ D⊂RLdenote a closed ball with radius anddefineaclosedsetCas the union of such closed balls with radius included in A:C=¯ D⊂A¯ D.Ifis sufficiently small, then there exists a closed ball with radius that is a subset of A, and hence Cis not an empty set. Lemma 6. Let A⊂RLbe a closed, convex set such that int A= ∅. When is sufficiently small, C=¯ D⊂A¯ Dis a closed, convex set with a smooth boundary. If Aisastrictly convex set, then Cis a strictly convex set. 6Afunctiong:RL−1→Ris differentiable at z−Lif there exists (T1TL−1)∈RL−1such that lim h→0 g(z−L+h) −g(z−L)−T1h1−···−TL−1hL−1  h=0 where h=(h1hL−1).Then(−T1−TL−11)is the normal vector of the supporting hyperplane to the graph of gat (z−Lg(z−L)) inthecoordinatesystem(z1zL). 7In the coordinate system (z1zL),ifTA=(TA 1TA L−11)and TB=(TB 1TB L−11)are the normal vectors of the supporting hyperplanes to Aand Bat (z−Lα(z−L)) and (z−Lβ(z−L)), respectively, then sTA+(1−s)TBis the normal vector of the supporting hyperplane to Isat (z−Lγs(z−L)). 1290 Takeshi Momi Theoretical Economics 12 (2017) Proof.WeprovethatCisaclosedset. Welet{xn}∞ n=0be a sequence of points in C converging to ¯ xand prove ¯ x∈C. From the definition of C, there exists a closed ball ¯ Dn  with radius such that xn∈¯ Dn ⊂Afor each n.Letcndenote the center of the closed ball ¯ Dn .Asxnis convergent, the union n¯ Dn of the closed balls is bounded, and hence the sequence {cn}∞ n=0has a convergent subsequence {cnk}∞ k=0.Weletcnk→¯ cas k→∞.We let ¯ D(c) denote the closed ball with center cand radius .Givenxnk→¯ xas k→∞and xnk∈¯ D(ck)⊂A,wehave ¯ x∈¯ D(¯ c) ⊂A. Therefore, ¯ x∈Cfrom the definition of C. We prove that Cis a convex set. We let x∈C,x ∈C,ands∈(01),andprovethat sx+(1−s)x ∈C. From the definition of C, there exist closed balls ¯ D and ¯ D such that x∈¯ D ⊂Aand x ∈¯ D ⊂A.LetKbe the convex hull of ¯ D ∪¯ D :K={z∈RL +|z= rz+(1−r)zz∈¯ D z ∈¯ D r∈[01]}. It is clear that sx+(1−s)x ∈K.AsKequals the union of closed balls with radius that have their centers between the centers of ¯ D  and ¯ D , there exists a closed ball ¯ D with radius such that sx+(1−s)x ∈¯ D ⊂K. Convexity of Aimplies K⊂A. Therefore, sx+(1−s)x ∈¯ D ⊂K⊂Aand sx+(1− s)x ∈Cfrom the definition of C. We show that the boundary of Cis smooth. If it is not smooth at a point xon the boundary of C, then there are two different hyperplanes tangent to Cat x. However, as Cis a union of closed balls, there should exist a closed ball with radius that is tangent to xand included in C. This is a contradiction. Finally, we prove that Cis a strictly convex set if Ais also a strictly convex set. We suppose that Cis not strictly convex. Given Cis convex as shown above, this implies that there is a segment [xx]in RLsuch that the segment is on the boundary of Cand Cis tangent to an L−1-dimensional hyperplane Halong the segment [xx]. Then there exist closed balls ¯ D and ¯ D in Cwith radius that are tangent to the hyperplane Hat x and x.LetKbe the convex hull of ¯ D ∪¯ D and let s∈(01)be any scalar. The convex hull Kis tangent to Halong the segment [xx], and there exists a closed ball ¯ D ⊂K with radius that is tangent to the hyperplane Hat sx+(1−s)x. Note that K⊂C⊂A because Cis a convex set. From the definition of C, if a closed ball ¯ Din Cwith radius  touches the boundary of C, then the closed ball also touches the boundary of A.Thatis, if there exists a point x∈∂¯ D∩∂C, then there exists a point y, which might be different from x,suchthaty∈∂¯ D∩∂A.Assx+(1−s)x is in ∂¯ D ∩∂C, the closed ball ¯ D  touches the boundary of A,thatis,thereexistsysuch that y∈∂¯ D ∩∂A.LetHdenotes the supporting hyperplane of ¯ D at y.Giventhat ¯ D is located between ¯ D and ¯ D in K,then,H, which is a supporting hyperplane of D , has an intersection with Kother than y. Alternatively, strict convexity of Aimplies that Adoes not have an intersection with the hyperplane Hother than y∈∂A. This is a contradiction.  Lemma 7. If A⊂RLand B⊂RLare closed convex sets with smooth boundaries, then the convex hull of their union, co(A ∪B), also has a smooth boundary. Proof. Note that any point in the boundary of co(A ∪B) is either in the boundary of A, in the boundary of B, or a convex combination of points in the boundaries of Aand B. That is, if y∈∂co(A ∪B), then either y∈∂A,y∈∂B,ory=sx+(1−s)x,wherex∈∂A, x ∈∂B,ands∈(01). Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1297 scalar Ri, depending on Ri,suchthat DRifiRi¯ R−i∩Gi¯ R−i⊂fiRi¯ R−i+pRi¯ R−if⊥−RL +(4) Note that all we have to show is the existence of an ¯ Risatisfying (4)at ¯ R,where consumption-direction vectors are independent and fi(¯ R)∈intA. Suppose this claim to be true. If Riis in a neighborhood of ¯ Ri,thenf(Ri¯ R−i)is in a neighborhood of f(¯ R) by Proposition 1, and, hence, the consumption-direction vectors of agents remain independent at the preference profile (Ri¯ R−i)and fi(Ri¯ R−i)∈intA. Then there exists an Risatisfying (4) by the supposed claim. Contrary to the existence of an ¯ Risatisfying (4), we suppose that Gi(¯ R−i)has an intersection with fi(¯ R)+p( ¯ Rf)⊥+RL ++ in any neighborhood of fi(¯ R).Thenwehave a preference in a neighborhood of ¯ Rithat has two most preferred consumption bundles in Gi(¯ R−i), which contradicts Lemma 4. The rigorous proof proceeds as follows. We write f(¯ R)=(¯ x1 ¯ xN)and p( ¯ Rf)=¯ p. We construct agent i’s new preference as follows. For a parameter >0,weconsider the set H(¯ xi;¯ p) ∩UC(¯ xi−¯ p;¯ Ri). Applying Lemma 6, we round the edge of this set. We let  <be a scalar smaller than and consider a closed ball ¯ D with radius .Welet Cbe the union of such closed balls with radius  included in the set H(¯ xi;¯ p)∩UC(¯ xi− ¯ p;¯ Ri):C=¯ D ⊂H(¯ xi;¯ p)∩UC(¯ xi−¯ p;¯ Ri)¯ D . Note that the surface of the set Cis flat in a neighborhood of ¯ xi. We apply Lemma 5 to make Cinto an upper contour set of a preference. We fix any positive unit vector a∈SL−1 ++ and consider the L−1-dimensional linear space a⊥.For y∈a⊥,weletL(y) denote the half-line starting from yand extending in the direction of the vector a:L(y) ={x∈RL|x=y+tat ≥0}. For a parameter t∈(01],weletRi t be agent i’s preference that has as its indifference set It = y∈a⊥tL(y) ∩I¯ xi;¯ Ri+(1−t)L(y) ∩∂C Observe that Ri 1=¯ Riand that Ri t is an MMT of Ri tat ¯ xifor t>t , and the indifference set I(¯ xi;Ri t )becomes flatter in a neighborhood of ¯ xias t→0. Furthermore, observe that if is sufficiently small, then ∂Cis close to the indifference set I(¯ xi;¯ Ri), and hence Ri t is close to ¯ Rifor any t.Weletbe sufficiently small such that Ri t ∈Bifor any t∈(01]. For any t,¯ xiis an intersection between Gi(¯ R−i)and UC(¯ xi;Ri t ), and it is the unique intersection for t=1. By the assumption that Gi(¯ R−i)has an intersection with ¯ xi+¯ p⊥+ RL ++ in any neighborhood of ¯ xi,UC(¯ xi;Ri t )has intersections with Gi(¯ R−i)other than ¯ xi when tis small. We let t()be the largest tsuch that UC(¯ xi;R1 t )has such an intersection with Gi(¯ R−i)in fi(¯ R)+p( ¯ Rf))⊥+RL ++.Then,withrespecttoRi t(),thereexisttwo most preferred consumption bundles in Gi(¯ R−i)and this contradicts Lemma 4.This ends the proof of the existence of Risatisfying (4). We now prove the statement of the proposition. For example, we choose the scalars ¯and satisfying (1) as follows. We consider Risatisfying (4)foreachRiin a neighborhood of ¯ Ri.For>0, we consider the -neighborhood of ¯ Ri, i.e., B( ¯ Ri),and 1298 Takeshi Momi Theoretical Economics 12 (2017) define α() as the infimum of Rifor Ri∈B(¯ Ri):α() =infRi∈B(¯ Ri)Ri. Note that → α() is a positive and decreasing function by the definition. Alternatively, we define β() as the supremum of the distance between f(Ri¯ R−i)and fi(¯ R)for Ri∈B(¯ Ri): β() =supRi∈B(¯ Ri)f(Ri¯ R−i)−fi(¯ R). Note that → β() is a positive and increasing function and β() →0as →0because of the continuity of f. We pick a scalar satisfying β()<1 2α()and define ¯=β(). The existence of such a scalar is ensured by the properties of the functions → α() and → β() mentioned above. It can be easily seen that these are the desired scalars. If Riis in the neighborhood B(¯ Ri)of ¯ Ri, then in the neighborhood Dα()(f i(Ri¯ R−i)), the option set Gi(¯ R−i)is in the lower left-hand side of the hyperplane f(Ri¯ R−i)+p((Ri¯ R−i))f)⊥: Dα()fiRi¯ R−i∩Gi¯ R−i⊂fiRi¯ R−i+pRi¯ R−if⊥−RL + As the distance between fi(Ri¯ R−i)and f(¯ R)is at most ¯and α()>2¯,wehave D¯(f ( ¯ R)) ⊂Dα()(fi(Ri¯ R−i)).Hence,wehave(1). A.8 Proof of Proposition 3 As in the proof of Proposition 2, we only have to prove that if the consumption-direction vectors are independent at ¯ Rand if fi(¯ R)∈intA, then the statement of the proposition holds at the preference profile ¯ R. Without loss of generality, we prove the proposition for agent 1. We suppose that g( ¯ Rip(¯ Rf)),i=1N, are independent at ¯ R=(¯ R1 ¯ RN)∈Band f1(¯ R)∈intA. We write f(¯ R)=¯ x=(¯ x1 ¯ xN)and p( ¯ Rf)=¯ p. We have to prove that ¯ x1is the unique intersection between G1(¯ R−1)and ¯ x1+¯ p⊥in a neighborhood of ¯ x1. Contrary to the statement of the proposition, we suppose that for any scalar >0, there exists ˜ x1 in the -neighborhood D(¯ x1)of ¯ x1such that ˜ x1 is different from ¯ x1,and that ˜ x1 is the intersection between G1(¯ R−1)and ¯ x1+¯ p⊥. We show a contradiction. We first observe that when is sufficiently small, the hyperplane ¯ x1+¯ p⊥is tangent to G1(¯ R−1)along the segment [¯ x1˜ x1 ]≡{t¯ x1+(1−t)˜ x1 ∈RL +:0≤t≤1}.Wepickan arbitrary consumption bundle x1∈(¯ x1˜ x1 )≡{t¯ x1+(1−t)˜ x1 ∈RL +:0<t<1}and consider a preference R1in a neighborhood of ¯ R1so that the gradient vector of R1at x1 is ¯ p.Whenis sufficiently small, x1is sufficiently close to ¯ x1,andwecanhavesucha preference R1in a neighborhood of ¯ R1.Weletx1denote the most preferred consumption in G1(¯ R−1)with respect to R1and let pdenote the gradient vector of R1at x1. As shown in Proposition 2,x1is in the lower left-hand side of the hyperplane ¯ x1+¯ p⊥. Therefore, ¯ px1≤¯ p¯ x1=¯ p˜ x1 , and hence ¯ px1≤¯ px1. By the same reasoning, ¯ x1and ˜ x1  are in the lower left-hand side of the hyperplane x1+(p)⊥. Therefore, p¯ x1≤px1and p˜ x1 ≤px1, and hence px1≤px1. These two inequalities are satisfied for the two combinations (¯ px1)and (px1)of a gradient vector and a consumption bundle with the preference R1if and only if ¯ p=pand x1=x1. As our choice of x1is arbitrary on (¯ x1˜ x1 ), this implies that ¯ x1+¯ p⊥is tangent to G1(¯ R−1)along the segment [¯ x1˜ x1 ].From now on, we assume that is sufficiently small so that ¯ x1+¯ p⊥is tangent to G1(¯ R−1)along the segment [¯ x1˜ x1 ]. Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1299 Figure 6. Proof of Proposition 3. For each , we pick a consumption bundle ˆ x1 ∈(¯ x1˜ x1 )and a preference ˆ R1 such that the gradient vector of ˆ R1 at ˆ x1 is ¯ pand ˆ R1 converges to ¯ R1as →0.Wecanhave such a preference because ˆ x1 →¯ xas →0. Similarly, we let ˜ R1 be a preference such that the gradient vector of ˜ R1 at ˜ x1 is ¯ pand ˜ R1 converges to R1as →0. It is clear that f1(˜ R1 ¯ R−1)=˜ x1 ,f1(ˆ R1 ¯ R−1)=ˆ x1 ,andp(( ˜ R1 ¯ R−1)f) =p(( ˆ R1 ¯ R−1)f) =¯ p.Wewrite f( ˜ R1 ¯ R−1)=˜ x=(˜ x1  ˜ xN )and f( ˆ R1 ¯ R−1)=ˆ x=(ˆ x1  ˆ xN ). For agent i= 1, the consumption bundles, ¯ xi,ˆ xi ,and˜ xi are all on the same ray [g( ¯ Ri¯ p)]because of the same price vector ¯ p. Under the independence of the consumption-direction vectors, which holds for preferences in a neighborhood of ¯ R, ˜ x1 = ¯ x1implies that there exists an agent i= 1such that ˜ xi = ¯ xi. Without loss of generality, we assume agent 2is such an agent. Then ˆ x2 is between ¯ x2and ˜ x2 on the same ray, and either ¯ x2<ˆ x2 <˜ x2 or ˜ x2 <ˆ x2 <¯ x2holds. Figure 6 describes the situation where the closure of agent 1’s option set is tangent to the hyperplane ¯ x1+¯ p⊥along the segment [¯ x1˜ x1 ], contrary to the statement of the proposition. In the following proof, we show that the other agents’ option sets are also flat and observe that such flat option sets contradict the pseudo-efficiency and strategyproofness of the social choice function. We now show that when is sufficiently small, G2(ˆ R1 ¯ R−{12})is flat in a neighborhood of ˆ x2 . We suppose that it is not flat in any neighborhood of ˆ x2 ,asdrawn in Figure 5.Welet>0be a scalar and let ˇ R2 be agent 2’s preference in the - neighborhood B(¯ R2)of ¯ R2such that the gradient vector ˇ pof ˇ R2 at the most preferred consumption bundle in G2(ˆ R1 ¯ R−{12})with respect to ˇ R2 is different from ¯ p, as drawn in the figure. As the closure of the option set is not flat in any neighborhood of ˆ x2 ,wecanhavesuchapreference ˇ R2 in any -neighborhood of ¯ R2.Wewrite f( ˆ R1 ˇ R2 ¯ R−{12})=ˇ x=(ˇ x1  ˇ xN ).9We have ˇ p→¯ pand ˇ x→ˆ xas →0. 9The set G2(ˆ R1 ¯ R−{12})may have an edge at ˆ x2 , and ˇ xmay be ˆ x2 . 1300 Takeshi Momi Theoretical Economics 12 (2017) As ˆ x1 is between ¯ x1and ˜ x1 , either ˇ p¯ x1>ˇ pˆ x1 >ˇ p˜ x1 ,ˇ p¯ x1<ˇ pˆ x1 < ˇ p˜ x1 ,or ˇ p¯ x1=ˇ pˆ x1 =ˇ p˜ x1 holds. When ˇ p¯ x1>ˇ pˆ x1 >ˇ p˜ x1 ,asdrawnin Figure 2,orwhen ˇ p¯ x1=ˇ pˆ x1 =ˇ p˜ x1 , we focus on the two combinations (¯ x1¯ p) and (ˇ x1 ˇ p)of a consumption bundle and a price vector. We consider a preference R1 in a neighborhood of ¯ R1such that the gradient vector of R1 at ¯ x1is ¯ pand that at ˇ x1 is ˇ p:¯ p=p(R1 ¯ x1)and ˇ p=p(R1 ˇ x1 ). For example, such a preference R1 can be obtained as follows. We write y= [ˇ x1 ]∩I(ˆ x1 ;ˆ R1 ).WeletR∗ be an MMT of ¯ R1at ¯ x1and let Kdenote the convex hull of UC(ˆ x1 ;ˆ R1 )∪UC(¯ x1R∗ ):K=co(UC(ˆ x1 ;ˆ R1 )∪UC(¯ x1R∗ )). Observe that the convex hull Kis tangent to the hyperplane y+ˇ p⊥ at y.ThisKcannot be an upper contour set of a preference because it is not a strictly convex set. We let Rbe a preference such that its gradient vector at yis ˇ pand its upper contour set at y includes K:K⊂UC(y;R).WeuseRand make Kinto an upper contour set of a preference by applying Lemma 5. We fix any positive unit vector a∈SL−1 ++ and consider the L−1-dimensional linear space a⊥.Fory∈a⊥,weletL(y) denote the halfline starting from yand extending in the direction of the vector a:L(y) ={x∈RL|x= y+tat ≥0}.WeletR be a preference, for which the indifference set at yis  y∈a⊥sL(y) ∩I(y;R)+(1−s)L(y) ∩∂K (5) with a sufficiently small s>0. Finally, we construct a preference R1 in a neighborhood of R such that ˇ p=p(R1 ˇ x1 )and ¯ p=p(R1 ¯ x1)by directly applying the preference construction in Lemma 1 so that ¯ R,(¯ x ¯ p),and(xnpn)in Lemma 1 correspond to R ,(ˇ xˇ p),and(¯ x ¯ p) in the present setup, respectively. We observe that Lemma 1 can be applied to R when ,,andsin (5) are sufficiently small. As →0,wehaveˆ x→¯ x.As→0,wehaveˇ x→ˆ xand ˇ p→¯ p. Thus, when and are sufficiently small, we have ˇ x1 and ˇ psufficiently close to ¯ x1and ¯ p, respectively. Therefore, we can apply the preference construction method in Lemma 1. The condition in Lemma 1 is ¯ p([ˇ x]∩I(¯ x;R )) > ¯ p¯ xin the present setup. We set and .Ass→0in (5), UC(¯ x1;R )converges to Kand [ˇ x]∩I(¯ x;R ) converges to y, which satisfies ¯ py>¯ p¯ x. Therefore, the condition is satisfied when sin (5) is sufficiently small. Next, we observe that R1 is in a neighborhood of ¯ R1when ,,andsin (5) are sufficiently small. As →0,wehave ˆ x1 →¯ x1and ˆ R→¯ R1,and,hence,UC(ˆ x1 ;ˆ R )converges to UC(¯ x;¯ R1). Since UC(¯ x1;R∗ )⊂UC(¯ x1;¯ R1),Kconverges to UC(¯ x;¯ R1).Ass→0 in (5), UC(y;R )converges to K. Therefore, as →0and s→0,UC(y;R ) converges to UC(¯ x1;¯ R1)and R converges to ¯ R1.AsR1 converges to R as →0 and →0,wehaveR1 in a neighborhood of ¯ R1as desired when ,,andsare sufficiently small. With the preference R1 ,wehavef(R1 ˇ R2 ¯ R−{12})=ˇ xand f(R1  ¯ R−2)=¯ x. This contradicts the strategy-proofness of fon Bwith respect to agent 2be- Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1301 cause ˇ x→ˆ xas →0,and ˆ x2 , which is on the same ray as ¯ x2,satisfies ˆ x2 <¯ x2or ¯ x2<ˆ x2 as mentioned above. The discussion is symmetric when ˇ p¯ x1<ˇ pˆ x1 <ˇ p˜ x1 . We focus on the two pairs (ˇ x1 ˇ p)and (˜ x1 ¯ p). Similar to the discussion above, we can construct a preference R1 in a neighborhood of ˜ R1 , and thus in a neighborhood of ¯ R1,suchthat the gradient vectors of R1 at ˜ x1 and ˇ x1 are ¯ pand ˇ p, respectively. Then we have f(R1 ˇ R2 ¯ R−{12})=ˇ x, which converges to ˆ xas →0,andf(R1 ¯ R−2)=˜ x.This again contradicts the strategy-proofness of fon Bwith respect to agent 2. This ends the proof that G2(ˆ R1 ¯ R−{12})is flat in a neighborhood of ˆ x2 when is sufficiently small. In addition to ˆ x1 and ˆ R1 , we pick another consumption bundle ´ x1 (= ˆ x1 )on (¯ x1˜ x1 )and another preference ´ R1 for each such that the gradient vector of ´ R1 at ´ x1 is ¯ pand ´ R1 converges to ¯ R1as →0. It is clear that f1(´ R1 ¯ R−{12})=´ x1 and p(( ´ R1 ¯ R−{12})f) =¯ p.Wewritef( ´ R1 ¯ R−{12})=´ x=(´ x1  ´ xN ). Similar to the discussion above, G2(´ R1 ¯ R−{12})is flat in a neighborhood of ´ x2 when is sufficiently small. Under the independence of the consumption-direction vectors, ´ x2 is on the same ray as ˆ x2 and ´ x2 = ˆ x2 because of ´ x1 = ˆ x1 . Now we exchange the roles of agents 1and 2. Facing the closure of the option set G2(ˆ R1 ¯ R−{12}), which is flat in a neighborhood of ˆ x2 ,welet be a scalar such that with respect to any preference R2in the -neighborhood B (¯ R2)of R2,themostpreferred consumption bundle in G2(ˆ R1 ¯ R−{12}), which should be f2(ˆ R1 R2¯ R−{12}),is in the flat part. Then p( ˆ R1 R2¯ R{12})=¯ p. In particular, for each sufficiently small scalar ,welet ` R2  be agent 2’s preference in B2  (¯ R2)such that f2(ˆ R1 ` R2  ¯ R−{12})− ˆ x2 /∈S(g( ¯ R3;¯ p)g( ¯ RN;¯ p)),whereS(g( ¯ R3;¯ p)g( ¯ RN;¯ p)) denotes the N−2- dimensional linear space spanned by the consumption-direction vectors of agents i= 3N. We can have such a preference ` R2  because we can have f2(ˆ R1 ` R2  ¯ R−{12})− ˆ x2 in any L−1-dimensional directions on the flat part of G2(ˆ R1 ¯ R−{12}). Note that the condition f2(ˆ R1 ` R2  ¯ R−{12})−ˆ x2 /∈S(g( ¯ R3;¯ p)g( ¯ RN;¯ p)) implies that f1(ˆ R1 ` R2  ¯ R−{12})= ˆ x1 under the independence of the consumption-direction vectors. We write f( ˆ R1 ` R2  ¯ R−{12})=` x =(` x1   ` xN  ). Similar to the discussion above, we now have that ` x1  (= ˆ x1 )is on the same ray as ˆ x1 and G1(` R2  ¯ R−{12})is flat in a neighborhood of ` x1  when  is sufficiently small. We write f( ´ R1 ` R2  ¯ R−{12})=˙ x =(˙ x1   ˙ xN  ).As →0,wehave ` R2  →¯ R2, and hence ˙ x →´ x . Therefore, when  is sufficiently small, ˙ x2  is on the flat part of G2(´ R1 ¯ R−{12})in a neighborhood of ´ x2 .As→0, both ˆ R1 and ´ R1 converges to ¯ R1and, hence, both preferences become closer. Therefore, when is sufficiently small, ˙ x1  is sufficiently close to ` x1  anditisintheflatpartofG1(` R2  ¯ R−{12})in a neighborhood of ` x1  . Now we consider four allocations ˆ x,´ x,` x ,and˙ x with sufficiently small  and . Clearly, these satisfy four equations: N i=1ˆ xi =,N i=1´ xi =,N i=1` xi  =, and N i=1˙ xi  =. As the price vector ¯ pis the same in all allocations, and the preferences of all agents, except agents 1and 2, are unchanged, we have, for i=3N, 1302 Takeshi Momi Theoretical Economics 12 (2017) ´ xi =aiˆ xi ,` xi  =biˆ xi ,and ˙ xi  =ciˆ xi with some scalars ai,bi,andci.Asforagent1,we have ` x1  =tˆ x1 and ˙ x1  =t´ x1 with a scalar t,because ` x1  and ˆ x1 are on the same ray [g( ˆ R1 ¯ p)],˙ x1  and ´ x1 are on the same ray [g( ´ R1 ¯ p)], and the segments [` x1  ˙ x1  ]and [ˆ x1 ´ x1 ]are both perpendicular to ¯ p. Similarly, we have ´ x2 =sˆ x2 and ˙ x2  =s` x2  with a scalar sfor agent 2. Thus, we have ˆ x1 +ˆ x2 +ˆ x3 +···+ ˆ xN = ´ x1 +sˆ x2 +a3ˆ x3 +···+aNˆ xN = tˆ x1 +` x2 +b3ˆ x3 +···+bNˆ xN = t´ x1 +s` x2 +c3ˆ x3 +···+cNˆ xN = From the first and second equations, we have sˆ x1 −´ x1 +(s −a3)ˆ x3 +···+(s −aN)ˆ xN =(s −1) From the third and fourth equations, we have tsˆ x1 −´ x1 +(sb3−c3)ˆ x3 +···+(sbN−cN)ˆ xN =(s −1) Because of the independence of the consumption-direction vectors and ˆ x1 = 0,is not in the linear space spanned by ˆ x3  ˆ xN . Thus, these two equations hold only if s=1 or t=1. However, this contradicts that ` x1  = ˆ x1 and ´ x2 = ˆ x2 . A.9 Proof of Proposition 4 As in the proof of Proposition 2, we only have to prove that if the consumption-direction vectors are independent at ¯ Rand if fi(¯ R)∈intA, then the statement of the proposition holds at the preference profile ¯ R. Without loss of generality, we prove the statement for agent 1. We suppose that g( ¯ Rip(¯ Rf)),i=1N, are independent at ¯ R=(¯ R1 ¯ RN)and that f1(¯ R)∈intA. We write f(¯ R)=¯ x=(¯ x1 ¯ xN)and ¯ p=p( ¯ Rf). As shown in Proposition 2,¯ x1+¯ p⊥is a hyperplane tangent to G1(¯ R−1)at x1,and G1(¯ R−1)is in the lower left-hand side of this hyperplane. We suppose that G1(¯ R−1)has an edge at ¯ x1and that there exists another hyperplane tangent to G1(¯ R−1)at ¯ x1with a normal vector ˜ pdifferent from ¯ p. We show a contradiction. As G1(¯ R−1)is in the lower left-hand side of ¯ x1+¯ p⊥, and in the lower left-hand side of ¯ x1+˜ p⊥, any hyperplane ¯ x1+(t ¯ p+(1−t) ˜ p)⊥,t∈[01],istangenttoG1(¯ R−1)at ¯ x1 We let >0be a small scalar. For each , we pick a preference ˜ R1 in the - neighborhood B(¯ R1)of ¯ R1such that the gradient vector of ˜ R1 at ¯ x1is different from ¯ p and ¯ x1is the most preferred consumption bundle in G1(¯ R−1)with respect to ˜ R1 .Theexistence of such a preference should be clear from the above discussion. We let ˜ pdenote the gradient vector of ˜ R1 at ¯ x1:˜ p=p( ˜ R1 ¯ x1).Wewritef( ˜ R1 ¯ R−1)=˜ x=(˜ x1  ˜ xN ). It is clear that ˜ x1 =¯ x1and ˜ p=p(( ˜ R1 ¯ R−1)f).As→0,˜ R→¯ R1,˜ p→¯ p,and˜ x→¯ x. Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1303 Figure 7. Proof of Proposition 4. Figure 7 describes the situation where the closure of agent 1’s option set has an edge at ¯ x1, contrary to the statement of the proposition. In the following proof we observe that this induces allocations that contradict the pseudo-efficiency and strategy-proofness of the social choice function f. As f1(¯ R)∈intAand fi(¯ R)∈intA∪{0}for any ias observed at the end of Section 3, there exists another agent receiving positive consumption in int A. Without loss of generality, we assume that agent 2is such an agent: f2(¯ R)∈intA. As ¯ R1and ˜ R1 have different gradient vectors at ¯ x1,P(¯ x1;˜ R1 )\UC(¯ x1;¯ R1)= ∅.Then there exists a consumption bundle yin any neighborhood of ¯ x1such that yis indifferent to ¯ x1with respect to ¯ R1and yis strictly preferred to ¯ x1with respect to ˜ R1 .Welet{yn}∞ n=1 be a sequence of such consumption bundles converging to ¯ x1as n→∞:yn∈I(¯ x1;¯ R1), yn∈P(¯ x1;˜ R1 ),andyn→¯ x1as n→∞.Weletp ndenote the gradient vector of ¯ R1at yn: p n=p( ¯ R1yn). We focus on agent 2. With each sufficiently large n,weletx2 nbe a consumption vector on G2(¯ R−2)such that the hyperplane x2 n+p⊥ nis tangent to G2(¯ R−2)at x2 n.Such a consumption vector x2 nis obtained uniquely because ¯ x2is the unique intersection between G2(¯ R−2)and ¯ x1+¯ p⊥,asshowninProposition 3,andp n→¯ pas n→∞.We have x2 n→¯ x2as n→∞.10 We let R2 nbe agent 2’s preference that has gradient vector p nat x2 nand converges to ¯ R2as n→∞. Such a preference can be obtained by directly applying the preference construction in the first part of Lemma 1 so that ¯ R,(¯ x ¯ p),and(xnpn)in Lemma 1 correspond to ¯ R2,(¯ x2¯ p),and(x2 np n), respectively, in the present setup. It is clear that with respect to R2 n,x2 nis the most preferred consumption bundle in G2(¯ R−2),and,hence, f2(R2 n¯ R−2)=x2 nand p((R2 n¯ R−2)f) =p2 n.Wewritef(R2 n¯ R−2)=x n=(x1 nxN n). Observe that x1 nis on the ray [yn]. 10The term G2(¯ R−2)mayalsohaveanedgeat ¯ x2and x2 nmay be ¯ x2. 1304 Takeshi Momi Theoretical Economics 12 (2017) For each sufficiently small , there exists a sufficiently large n,andwecanhave agent 2’s preference ˆ R2 n in B2such that (I) the gradient vector of ˆ R2 n at ˜ x2 is ˜ p,and (II) the gradient vector of ˆ R2 n at x2 nis p n. To obtain such a preference, we directly apply the preference construction in Lemma 1 so that ¯ R,(¯ x ¯ p),and(xnpn)in Lemma 1 correspond to ¯ R2,(˜ x2 ˜ p),and(x2 np n), respectively, in the present setup. We observe that we can apply the preference construction in Lemma 1.As→0, ˜ x2 →¯ x2and ˜ p→¯ p.Asn→∞,x2 n→¯ x2and p2 n→¯ p. Therefore, when is sufficiently small and nis sufficiently large, x2 nand p nare sufficiently close to ˜ x2 and ˜ p, respectively, and, hence, we can apply Lemma 1.Wesetasufficientlysmall. The strict convexity of ¯ R2ensures that ¯ p([˜ x2 ]∩I(¯ x2;¯ R2)) > ¯ p¯ x2.Asn→∞,x2 n→¯ x2and p2 n→¯ p. Therefore, we have the condition in Lemma 1,p n([˜ x2 ]∩I(x2 n;¯ R2)) > p nx2 nin the present setup when nis sufficiently large. We write f( ˆ R2 n¯ R−2)=ˆ xn =(ˆ x1 n ˆ xN n)and f( ˜ R1 ˆ R2 n¯ R−{12})=ˇ xn =(ˇ x1 n  ˇ xN n).Wehaveˇ x2 n =˜ x2 because of (I) and, hence, ˇ xn =˜ xby Lemma 2.Alternatively, we have ˆ x2 n =x2 nbecause of (II) and, hence, ˆ xn =x n. In particular, note that ˆ x1 n =x1 nand, hence, ˆ x1 n is on the ray [yn]. We first consider the case where ˆ x1 n ∈P(¯ x1;˜ R1 ).Ifagent1has the preference ˜ R1  and faces other agents’ preferences (ˆ R2 n¯ R−{12}), he is better off by reporting ¯ R1and achieving ˆ x1 n than reporting the true preference ˜ R1 and achieving ˇ x1 n =˜ x1 =¯ x1.This contradicts the strategy-proofness of fon B. Next, we consider the case ˆ x1 n /∈UC(¯ x1;¯ R1).Ifagent1has preference ¯ R1and faces other agents’ preferences (ˆ R2 n¯ R−{12}), he is better off by reporting ˜ R1 and achieving ˇ x1 n =˜ x1 =¯ x1than reporting his true preference ¯ R1and achieving ˆ x1 n. Again, this contradicts the strategy-proofness of fon B. As ˆ x1 n ∈[y ],whereyn∈I(¯ x1;¯ R1)and yn∈P(¯ x1;˜ R1 ), only these two cases need to be considered. A.10 Proof of Proposition 5 Without loss of generality, we prove the proposition for agent 1. We suppose that g( ¯ Rip(¯ Rf)),i=1N, are independent at ¯ R=(¯ R1 ¯ RN)and that f1(¯ R)∈intA. We write f(¯ R)=x=(¯ x1 ¯ xN)and p( ¯ Rf)=¯ p. We consider the Cobb–Douglas utility functions uα(x) =xα1 1···xαL Lwith parameter α=(α1αL)∈SL−1 ++ and the preferences represented by these utility functions. Observe that the gradient vector of the preferences represented by the utility function uα(x) at a consumption bundle x=(x1xL)is given by the normalization of (α1 x1αL xL). Alternatively, if a preference represented by a Cobb–Douglas utility function uα(x) has gradient vector p=(p1pL)at x=(x1xL), then the parameter α is the normalization of (p1x1pLxL). We let uα∗(x) be the Cobb–Douglas utility function such that agent 1’s preference R1α∗represented by uα∗(x) has gradient vector ¯ pat ¯ x1. We consider a preference R1αrepresented by a Cobb–Douglas utility function uα, where αis in a neighborhood of α∗.Then,ofcourse,R1αis in a neighborhood of R1α∗. Theoretical Economics 12 (2017) Efficient and strategy-proof allocation mechanisms 1305 As fis supposed to satisfy pseudo-efficiency and strategy-proofness only on B,we let ˜ f1(R1α¯ R−1)denote the most preferred consumption in G1(¯ R−1)withrespecttothe preference R1α.IfR1α∈B1,then,ofcourse,f(R1α¯ R−1)=˜ f(R1α¯ R−1). We have ˜ f(R1α∗¯ R−i)=¯ xand ˜ f1(R1α¯ R−i)is in a neighborhood of ¯ x1when αis in a neighborhood of α∗because of the properties of G1(¯ R−1)showninPropositions2–4. Observe that α= αimplies that ˜ f1(R1α¯ R−1)= ˜ f1(R1α¯ R−1)because ˜ f1(R1α¯ R−1)= ˜ f1(R1α¯ R−1)and α= αimply that R1αand R1αhave different gradient vectors at the same consumption bundle, which contradicts Proposition 4.Thus,each˜ f1(R1α¯ R−1) in a neighborhood of ¯ x1is identified with the corresponding parameter α∈SL−1 ++ in a neighborhood of α∗and, hence, in a neighborhood of ¯ x1,α˜ f1(R1α¯ R−1)is an L−1- dimensional manifold. To end the proof, we prove that in a neighborhood of ¯ x1,α˜ f1(R1α¯ R−1),G1(¯ R−1), and G1(¯ R−1)coincide. We let ˜ pαdenote the gradient vector of R1αat ˜ f1(R1α¯ R−1): ˜ pα=p(R1α˜ f1(R1α¯ R−1)).Whenαis in a neighborhood of α∗and ˜ f1(R1α¯ R−1)is in a neighborhood of ¯ x1, we construct a new preference ˜ R1∈B1such that the gradient vector of ˜ R1at ˜ f1(R1α¯ R−1)is ˜ pα. For example such a preference ˜ R1can be obtained by applying the preference construction in the first part of Lemma 1 so that ¯ R,(¯ x ¯ p),and (xnpn)in Lemma 1 correspond to ¯ R1,(¯ x1¯ p),and(˜ f1(R1α¯ R−1) ˜ pα), respectively, in the present setup. As αconverges to α∗,˜ f1(R1α¯ R−1)converges to ¯ x1and ˜ pαconverges to ¯ p,and,hence,Lemma 1 is applicable and ˜ R1converges to ¯ R1, as shown in the lemma. Then ˜ f1(R1α¯ R−1) ˜ pα)is the most preferred consumption in G1(¯ R−1)with respect to ˜ R1∈B1,and ˜ f1(R1α¯ R−1)=f( ˜ R1¯ R−1)∈G1(¯ R−1),asinLemma 3. Therefore, we have α˜ f(R1α¯ R−1)⊂G1(¯ R−1)⊂G1(¯ R−1)in a neighborhood of ¯ x1. To observe that any element of G1(¯ R−1)in a neighborhood of ¯ x1is included in α˜ f1(R1α¯ R−1), note that any ray [y]in a neighborhood of [¯ x1]intersects with G1(¯ R−1)once at the most because of strategy-proofness and, hence, G1(¯ R−1)is at most L−1dimensional. References Barberà, Salvador and Matthew O. Jackson (1995), “Strategy-proof exchange.” Econometrica, 63, 51–87. [1269] Goswami, Mridu Prabal, Manipushpak Mitra, and Arunava Sen (2014), “Strategyproofness and Pareto-efficiency in quasi-linear exchange economies.” Theoretical Economics, 9, 361–381. [1269] Hashimoto, Kazuhiko (2008), “Strategy-proofness versus efficiency on the Cobb– Douglas domain of exchange economies.” Social Choice and Welfare, 31, 457–473. [1267,1268] Hatfield, John William (2009), “Strategy-proof, efficient, and nonbossy quota allocations.” Social Choice and Welfare, 33, 505–515. [1270] Hurwicz, Leonid (1972), “On informationally decentralized systems.” In Decision and Organization: A Volume in Honor of Jacob Marschak (C.B.McGuireandRoyRadner, eds.), 297–336, North-Holland, Amsterdam. [1267] 1306 Takeshi Momi Theoretical Economics 12 (2017) Ju, Biung-Ghi (2003), “Strategy-proofness versus efficiency in exchange economies: General domain properties and applications.” Social Choice and Welfare, 21, 73–93. [1267] Kannai, Yakar (1970), “Continuity properties of the core of a market.” Econometrica, 38, 791–815. [1272,1273] Kato, Miki and Shinji Ohseto (2002), “Towards general impossibility theorems in pure exchange economies.” Social Choice and Welfare, 19, 659–664. [1267] Momi, Takeshi (2013a), “Note on social choice allocation in exchange economies with Cobb–Douglas preferences.” Social Choice and Welfare, 40, 787–792. [1267,1268] Momi, Takeshi (2013b), “Note on social choice allocation in exchange economies with many agents.” Journal of Economic Theory, 148, 1237–1264. [1268,1269,1270,1272, 1273,1280] Nicoló, Antonio (2004), “Efficiency and truthfulness with Leontief preferences. A note on two-agent, two-good economies.” Review of Economic Design, 8, 373–382. [1267] Satterthwaite, Mark A. and Hugo Sonnenschein (1981), “Strategy-proof allocation mechanism at differentiable points.” Review of Economic Studies, 48, 587–597. [1267,1270] Schummer, James (1997), “Strategy-proofness versus efficiency on restricted domains of exchange economies.” Social Choice and Welfare, 14, 47–56. [1267] Serizawa, Shigehiro (2002), “Inefficiency of strategy-proof rules for pure exchange economies.” Journal of Economic Theory, 106, 219–241. [1269,1272] Serizawa, Shigehiro and John A. Weymark (2003), “Efficient strategy-proof exchange and minimum consumption guarantees.” Journal of Economic Theory, 109, 246–263. [1269] Zhou, Lin (1991), “Inefficiency of strategy-proof allocation mechanisms in pure exchange economies.” Social Choice and Welfare, 8, 247–254. [1267] Co-editor Johannes Hörner handled this manuscript. Manuscript received 25 February, 2014; final version accepted 1 September, 2016; available online 6 September, 2016.