Available online at www.sciencedirect.com ScienceDirect Journal of Economic Theory 196 (2021) 105303 www.elsevier.com/locate/jet Foundations of pseudomarkets: Walrasian equilibria for discrete resources ✩ Antonio Miralles a,b,∗ , Marek Pycia c,∗ a Università degli Studi di Messina, Italy b Universitat Autonoma de Barcelona - Barcelona Graduate School of Economics, Spain c University of Zurich, Switzerland Received 23 December 2014; final version received 9 May 2021; accepted 9 June 2021 Available online 16 June 2021 Abstract We study the assignment of discrete resources in a general model encompassing a wide range of applied environments, such as school choice, course allocation, and refugee resettlement. We allow single-unit and general multi-unit demands and any linear constraints. We prove the Second Welfare Theorem for these environments and a strong version of the First Welfare Theorem. In this way, we establish an equivalence between strong efficiency and decentralization through prices in discrete environments. Showing that all strongly efficient outcomes can be implemented through pseudomarkets, we provide a foundation for using pseudomarkets in market design. © 2021 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). JEL classification: D47; D50; D60 ✩ From 2014 till 2019 this paper was posted and presented under the title “Prices and Efficient Assignments Without Transfers” (first presentation: May 2014, first posted draft: October 2014; substantial revision: February 2017). We would like to thank Salvador Barbera, Roland Benabou, Dirk Bergemann, Simon Board, Sergiu Hart, Andrew McLennan, Andreu Mas-Colell, Jordi Massó, Moritz Meyer-ter-Vehn, Alessandro Pavan, Michael Richter, William Thomson, Utku Unver, Rakesh Vohra, William Zame, Juan Enrique Martínez-Legaz and audiences at UCLA, UAB, SAET 2015, and U Zurich for helpful comments, and Tuomas Kari, Julian Teichgräber, and Simpson Zhang for excellent research assistance. Miralles gratefully acknowledges the hospitality of Ortygia Business School, UCLA, and Carnegie Mellon University, where most of the work has been undertaken, as well as the financial support from the Spanish Governments (SEV-2015- 0563, ECO2017-83534P) and the Catalan Government (SGR2017 0711). Pycia gratefully acknowledges the support of UCLA, where he was a faculty member when working on this paper, as well as the support from the William S. Dietrich II Economic Theory Center at Princeton University. * Corresponding authors. E-mail addresses: amirallesasensio@unime.it (A. Miralles), marek.pycia@econ.uzh.ch (M. Pycia). https://doi.org/10.1016/j.jet.2021.105303 0022-0531/© 2021 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 Keywords: Random assignment; Pseudomarkets; Welfare theorems; Walrasian equilibrium; Discrete markets; Multi-unit demand; Single-unit demand; Complementarities; Constraints 1. Introduction Efficiency is the key objective in assignment of discrete resources, or bundles of resources, in environments such as school choice, course assignment, and refugee resettlement. In these environments, the standard stochastic allocation mechanisms that only rely on participants’ ordi- nal rankings over resources or bundles are known to cause efficiency losses.1 Since Hylland and Zeckhauser (1979), we know that efficient mechanisms can be constructed by endowing market participants with token money that they can use to buy probability shares in allocated objects, with the allocation determined via Walrasian equilibrium. The resulting mechanisms—known as pseudomarkets—became central to the literature on efficient assignment in discrete environ- ments.2 The two main questions the present paper addresses are: how flexible is the pseudomarket approach? in particular, can all efficient assignments be implemented via pseudomarkets? By answering these two questions—and establishing a positive answer to the second one—we pro- vide a foundation for the market design literature’s focus on pseudomarkets: in market design contexts, our characterization of efficient assignments allows one to restrict attention to pseudo- markets at least in settings, such as large markets, where pseudomarket price mechanisms are incentive compatible.3 This positive answer is tantamount to proving for general discrete alloca- tion environments an analogue of the Second Welfare Theorem of the classic Walrasian theory: that every Pareto efficient assignment can be decentralized through the use of prices. In classic Walrasian markets, at least one good is divisible, and agents always strictly prefer having more of this good; in reduced-form models of markets the role of such a good is played by numeraire or money. The presence of such numeraire good implies that each agent is locally non-satiated, that is, for any assignment there is a nearby assignment that the agent strictly prefers. In contrast, our agents may be satiated if they receive their most preferred bundles. 1 Such losses are particularly pronounced when market participants have multi-unit demands as established by Budish and Cantillon (2012) and Budish (2011) in the course allocation context. The losses are also present in single-unit demand environments such as school choice: Bogomolnaia and Moulin (2001), Abdulkadiroglu et al. (2011), Featherstone and Niederle (2016), Miralles (2008), and Pycia (2014) provide theoretical analyses of such losses, and Abdulkadiroglu et al. (2017) provide their empirical evaluation. While deterministic mechanisms fare better—unlike stochastic mechanisms they can be Pareto efficient—in many environments stochasticity plays an important role, for instance because of fairness considerations, cf. Abdulkadiroglu and Sonmez (2003) and Abdulkadiroglu et al. (2009). Refugee resettlement entails the allocation of discrete resources to the refugee families, and ordinal allocation mechanisms inherit the efficiency losses first established in school choice and course allocation studies; for a discussion of these mechanisms in refugee context, see e.g. Andersson and Ehlers (2020), Delacretaz et al. (2020), and Pycia (2019). Even allocating legal tender money is a special case of our setting as long as the money comes in a finite number of discrete coins and banknotes; however the cited analyses of efficiency losses of ordinal mechanisms relied on the absence of legal tender. 2 We provide a review of this rich literature below. 3 See He et al. (2018) for asymptotic strategy-proofness of pseudomarkets, Azevedo and Budish (2019) for their strategy-proofness in the large, and Pycia (2014) for Nash equilibria. While these papers assume that participants’ budgets are fixed, in an ongoing work we show that this assumption may be relaxed. 2 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 We establish a tight link between efficiency and pseudomarkets despite the failure of local non-satiation. The feature of the environment that enables this unexpected link is the discreteness of resources being allocated; otherwise our allocation model is general. There is a finite set of agents and objects. Agents are assigned bundles of objects and we impose no assumptions on agents’ utilities from the bundles. Lotteries over bundles are evaluated in line with the expected utility theory. As we allow for arbitrary multi-unit demands, our model accommodates as special cases all types of substitutes, complements, externalities among objects in the same bundle, as well as the canonical single-unit demand model of Hylland and Zeckhauser (1979). Extending Hylland and Zeckhauser’s pseudomarkets to our general setting, we study Walrasian equilibria in which each agent is endowed with token money; the amount of token money held after the assignment has no impact on agents’ utilities.4 Our main result takes a particularly simple form in the single-unit demand settings such as school choice: every Pareto efficient assignment may be supported in a Walrasian equilibrium with properly chosen budgets, and hence decentralized via prices. The link between efficiency and prices remains valid in the general multi-unit-demand random assignment model in which agents receive lotteries over bundles of indivisible goods. In the general multi-unit-demand case the statement of this link is however more subtle because—as we show in an example—there are environments in which some assignments are Pareto efficient, in the sense of being undominated by any feasible random assignment, and at the same time these assignments cannot be supported in any Walrasian equilibrium.5 We thus prove the Second Welfare Theorem for allocations that are strongly Pareto efficient in the following sense: they are undominated by random allocations that are feasible at least in expectation.6 Importantly, we prove that strong efficiency is not only sufficient but also necessary for the Second Welfare Theorem, that is we also prove the analogue of the First Welfare Theorem for strong efficiency: every Walrasian equilibrium is efficient in the strong sense.7 The conjunction of our First and Second Welfare Theorems establishes the equivalence of pseudomarkets and strong efficiency, thus answering the first of our two leading questions, how flexible pseudomarkets are. 4 For earlier extensions of Hylland and Zeckhauser’s idea to multi-unit demand settings, see Budish (2011) and Budish et al. (2013). In addition to establishing the Second Welfare Theorem in their environments, we relax the modeling restrictions their analyses rely on. 5 The subtlety is caused by the failure of the Birkhoff-von Neumann property: in general random allocations whose expectations are feasible may fail to be implementable as a lottery over feasible deterministic assignments. Cf. Budish et al. (2013) and Nguyen et al. (2016) for a discussion of failures of the Birkhoff-von Neumann property. In all environments in which Birkhoff-von Neumann property obtains—in particular in environments studied by Budish et al. (2013)—our results shows that every Pareto efficient assignment may be supported in a Walrasian equilibrium. 6 Our Second Welfare Theorem implies as a corollary that whenever feasibility in expectation is the relevant feasibility concept, then the Second Welfare Theorem holds true for standard Pareto efficiency. This is of relevance in large markets as Nguyen et al. (2016) extended the Birkhoff-von Neumann Theorem to multi-unit assignment in large markets show- ing that the set of feasible-in-expectation random assignments is asymptotically equivalent to the set of implementable random assignments. Following on our analysis, Miralles and Pycia (2017) identify a sufficient condition for the Second Welfare Theorem to obtain in multi-unit-demand environments with divisible goods, possibly nonlinear preferences, and agents demanding goods up to a capacity quota (and hence possibly satiated). 7 For the school choice setting, the First Welfare Theorem was established by Hylland and Zeckhauser (1979). This result was further refined and extended by Mas-Colell (1992) and Budish et al. (2013). For instance, all equilibria are efficient if agents strictly rank any two objects. Note that the validity of the First Welfare Theorem in some of the settings we study does not imply the validity of the Second Welfare Theorem for these settings; indeed, there are environments in which the First Welfare Theorem holds true, and the Second Welfare Theorem fails, cf. Mas-Colell et al. (1995). 3 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 Whether the Second Welfare Theorem obtains in discrete settings was a puzzle, except for deterministic assignments in single-unit demand settings, for which Abdulkadiroglu and Son- mez (1998) established a version of the Second Welfare Theorem. We find it quite surprising that the insight of the Second Welfare Theorem holds true in discrete environments because the problems the received approaches to the Second Welfare Theorem run into in settings with non- divisibilities and locally satiated agents are well-known (Mas-Colell et al., 1995). The failure of local non-satiation implies that the Separating Hyperplane Theorem commonly used to prove the Second Welfare Theorem guarantees only the existence of a separating hyperplane that may have non-empty intersections with the set of Pareto-dominant aggregate assignments.8 Facing the re- sulting prices, some agents might afford to buy bundles they strictly prefer over their assignment; this situation is called a quasi-equilibrium. To surmount the problems that satiation causes for the standard proof approach, we develop a novel approach to constructing the separating hyperplane that leverages the polyhedral properties of discrete environments. As a key part of our proof, we establish a Full Separation Lemma for Polyhedra that might be useful beyond the confines of our Walrasian analysis.9 The lemma es- tablishes the existence of a separating hyperplane that is disjoint with the set of Pareto-dominant aggregate assignments. Facing the resulting prices, no agent can afford a bundle they would pre- fer over their assignment, and the prices support the assignment as an equilibrium. To the best of our knowledge, ours is the first paper to leverage the properties of the polyhedra to analyze Walrasian equilibria and prove the Second Welfare Theorem.10 Prior work on implementing efficient outcomes via pseudomarkets relied on additional strong requirements. In continuum economies, Thomson and Zhou (1993) related efficient, symmetric, and consistent mechanisms to Hylland and Zeckhauser’s pseudomarket mechanism with equal budgets, and Ashlagi and Shi (2016) showed that any efficient, symmetric, and strategy-proof random assignment can be expressed as the result of the equal-budget pseudomarket mecha- nism.11 In contrast, we do not rely on symmetry, consistency, or strategy-proofness, and we prove our results for all finite economies. Our paper also contributes to the literatures on constraints in market design—e.g., Budish et al. (2013) and He et al. (2018)—and on multi-unit assignment—e.g., Sonmez and Unver (2010), Budish (2011), and Budish and Cantillon (2012)—that extended the idea of using token money to allocate objects beyond the canonical Hylland and Zeckhauser setting.12 Our Second Welfare Theorem is complementary to these papers and provides a microfoundation for their focus on 8 While the full separation obtains if one of the separated sets is open, this assumption fails in our setting. Section 3 provides an example illustrating the failure of openness and a more detailed discussion of why the standard techniques do not work. 9 We also prove a complementary Polyhedral Lemma that shows that the set of Pareto dominant outcomes is a polyhe- dron, provided the resources being allocated are discrete. 10 For earlier uses of polyhedral ideas to study other questions in economics, see, e.g., McLennan (2002), Carroll (2010), Budish et al. (2013), Pycia and Unver (2015); none of these papers analyzes Walrasian equilibria. 11 Miralles and Pycia (2015) showed that the latter result hinges on the presence of the continuum of agents and Hafalir and Miralles’ (2015) study more demanding utilitarian welfare. Cf. also Makowski et al. (1999) for classical exchange economies. Subsequent to our work, Bogomolnaia et al. (2017, 2019) show that the utility profile of the equal-budget pseudomarket mechanisms maximize the Nash product of utilities; in particular the resulting profile is fully determined by the set of feasible utility profiles. 12 For analysis of market design constraints beyond the token money mechanisms, see also e.g. Pycia and Unver (2015), and Kamada and Kojima (2015). Beyond allocation, the token money ideas were used e.g. in Manjunath’s (2014) analysis of two-sided matching. 4 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 pseudomarkets; none of these earlier papers provided such a microfoundation. We also improve upon the First Welfare Theorems established in these papers by showing that pseudomarket equi- libria are not only Pareto efficient but also strongly efficient, and our general multi-unit demand setting goes beyond the settings studied in these papers: our analysis allows arbitrary utility pro- files over bundles of objects and arbitrary linear constraints. In particular, our Second Welfare Theorem does not hinge on the standard assumption that goods are substitutes, and it allows any mixture of substitutes and complementarities.13 Our paper provided a microfoundation for the focus on pseudomarkets in the analysis of effi- cient mechanisms also for the many papers that followed on our work. Papers that crucially rely on our Second Welfare Theorem include Miralles and Pycia (2015), who address the question which assignments are efficient and envy-free and show that the answer is qualitatively differ- ent in large finite markets than in a continuum economy limit, as well as Miralles (2017) and Schlegel and Mamageishvili (2020), who study He et al.’s (2018) pseudomarkets with weak priorities. Other papers that followed on our work and whose focus on pseudomarkets is mi- crofounded by our Second Welfare Theorem include Babaioff et al. (2021), McLennan (2018), Echenique et al. (2021a, 2021b), and Gul et al. (2019); the focus of these papers is on equilibrium existence, particularly in the context of fairness requirements or in the presence of constraints.14 Finally, we contribute to the literature on the Second Welfare Theorem, also known as the Second Fundamental Theorem of Welfare Economics. The theorem was conjectured by Pareto (1909), and subsequently refined and developed by many authors. Arrow (1951) proved the the- orem assuming strict concavity of preferences and Debreu (1951) proved it assuming weak con- cavity and local non-satiation. Anderson (1988) allowed nonconvex preferences but maintained the assumption of local non-satiation. Florig and Rivera (2010) established an almost-everywhere Second Welfare Theorem for large markets with a continuum of agents; in contrast, our analysis is valid in finite markets. Richter and Rubinstein (2015) proposed a general convex geometry approach to welfare economics based on the concept of “primitive equilibrium,” where a strict linear ordering arranges alternatives in order to create “budget” sets. They proved a Second Wel- fare Theorem for the primitive equilibrium concept; when preferences are strictly monotone, their primitive equilibrium concept corresponds to the standard equilibrium concept; however, when specialized to our setting, this equilibrium concept becomes equivalent to the quasi-equilibrium discussed above.15 13 In this sense we are also contributing to the literature extending the economic analysis of matching and allocation models beyond the standard substitutes assumption; cf. Sun and Yang (2006), Ostrovsky (2008), Pycia (2012), Baldwin and Klemperer (2019) for earlier analyses going beyond the substitute assumption. At the current still early stage of this literature and the literature on constraints, they focus primarily on existence results most closely related to our secondary result, the First Welfare Theorem. 14 Of interest is also Reny (2017), who extends the deterministic analysis of Budish (2011) beyond discrete outcomes spaces, as well as Baldwin et al. (2020), who study the First Welfare Theorem, and Vazirani and Yannakakis (2020), who study the complexity of pseudomarket mechanisms. 15 In Section 3 we provide an example of a quasi-equilibrium which is not an equilibrium; this quasi-equilibrium is a primitive equilibrium in the sense of Richter and Rubinstein. To the best of our knowledge the above discussion covers all extensions of the Second Welfare Theorem beyond Arrow and Debreu. Of course, the literature on Walrasian equilibria beyond this setting is richer, and—in addition to the papers cited above—includes, for instance, Bergstrom (1976), Manelli (1991), and Hara (2005) who focused on equilibrium existence and core convergence rather than on the Second Welfare Theorem. 5 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 2. Base model We study a finite economy with agents i, j ∈ I = {1, ..., |I |} and indivisible objects x, y ∈ X = {1, ..., |X|}. Each object x is represented by a number of identical copies |x| ∈ N. By S = (|x|)x∈X we denote the total supply of object copies in the economy.  If agents have outside options, we treat them as objects in X; in particular, this implies that x∈X |x| ≥ |I |. We assume initially that agents demand at most one copy of an object; we fully relax this assumption in Section 4. A canonical interpretation of the single-unit demand model is school choice, in which each student demands entry to at most one school. We allow random assignments and denote by qix ∈ [0, 1] the probability that agent i obtains |X| a copy of object x. Agent i’s randomassignment  qi = (qi1 , ..., qi ) is a probability distribution. The economy-wide assignment Q = qix i∈I, x∈X is feasible if the aggregate assignment (which  we will denote as A(Q)) is weakly lower that the supply vector: A(Q) ≡ i∈I qi ≤ S. Let A denote the set of economy-wide random assignments, and F ⊂ A denote the set of feasible random assignments. We call an assignment pure, or deterministic, if each of its elements qix is either 0 or 1. By the Birkhoff-von Neumann theorem, a feasible random assignment can be expressed as a lottery over feasible pure assignments. Agents are expected utility maximizers, and agent i’sutility from random assignment qi equals the scalar product ui (qi ) = vi · qi where vi = vix x∈X ∈ [0, ∞)X = RX + is the vector of agent i’s von Neumann-Morgenstein valuations for objects x ∈ X. We study the connection between two concepts: efficiency and equilibrium. A feasible random assignment Q∗ ∈ F is ex-ante Pareto efficient—or, simply, efficient—if no other feasible random assignment Q ∈ F is weakly preferred by all agents and strictly preferred by some agents. A random assignment Q∗ ∈ F and a price vector p ∗ ∈ RX + constitute an equilibrium (or ∗ ∗  ∗ Walrasian equilibrium) for a budget vector w ∈ R+ if Q = qi i∈I is feasible in the sense I p ∗ · qi∗ ≤ wi∗ for all i ∈ I , and ui (qi ) > ui (qi∗ ) =⇒ p ∗ · qi > wi∗ for all (qi )i∈I ∈ A. 3. The Second Welfare Theorem for single-unit demand We now develop the Second Welfare Theorem for agents with single-unit demand. The result is directly applicable to school choice. Furthermore, the analysis serves as an example illustrating the approach that in the next section we use to derive a general Second Welfare Theorem for assignment with multi-unit demand. Theorem 1 (The Second Welfare Theorem for Single-Unit Demand). If Q∗ ∈ F is efficient, then there is a vector of budgets w ∗ ∈ RI+ and a vector of prices p ∗ ∈ RX ∗ + such that Q and p ∗ ∗ constitute an equilibrium with budgets w . Before laying out the proof, let us compare our problem to the standard Second Welfare The- orem for agents whose preferences are convex and strictly monotonic. The well-known argument in the standard setting relies on the celebrated separating hyperplane theorem: for any two dis- joint convex sets Y, Z ⊆ Rn there exists a price vector p ∈ Rn and budget w ∈ R such that p · z ≥ w ≥ p · y for each z ∈ Z and y ∈ Y , thus achieving a partial separation of Y and Z; the separation is full if one of the inequalities can be assumed to be strict.16 In the standard proof, Y 16 See e.g. Boyd and Vandenberghe (2004). An alternative proof of the standard Second Welfare Theorem was offered by Maskin and Roberts (2008): their “revealed preference” approach is inapplicable in our setting because it relies on 6 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 is the set of aggregate feasible assignments and Z is the set of  (infeasible) aggregate assignments that Pareto dominate a fixed efficient assignment Q∗ = qi∗ i∈I we want to implement.17 If now   some agent i ∈ I strictly prefers some qi to qi∗ , then Q = qi , q−i ∗ Pareto dominates Q∗ and by     the partial separation inequality, p · qi + j ∈I \{i} qj∗ ≥ w ≥ p · j ∈I qj∗ , where the second inequality can be shown to be an equality. Setting wi = p · qi∗ we conclude that ui (qi ) > ui (qi∗ ) =⇒ p ∗ · qi > wi∗ , thus prices p and budgets wi give us a so-called quasi-equilibrium. The key step of the standard proof is then to show that the above quasi-equilibrium is in fact an equilibrium, that is ui (qi ) > ui (qi∗ ) =⇒ p ∗ · qi > wi∗ for all i ∈ I and for all (qi )i∈I ∈ A. This last step is by contradiction: we take an assignment Q = (qi )i∈I that Pareto dominates Q∗ while there is an agent i for whom qi costs the same as qi∗ ; in the neighborhood of Q we then find an assignment that still Pareto dominates Q∗ while being cheaper than it. This is a contradiction as in quasi-equilibrium no cheaper assignment can Pareto dominate Q∗ . It is this key step of the standard proof that fails in our setting. The standard separating hyper- plane theorem partially separates the Pareto dominating aggregate assignments from the feasible ones. In the standard argument this is sufficient because the set of Pareto dominating aggregate assignments is open; in contrast, in the setting we study, this set of aggregate assignments does not need to be open. In effect, while full separation follows from the partial one (and hence every quasi-equilibrium is an equilibrium) in the standard setting, in the discrete setting with locally satiated preferences that we study, the full separation does not follow from the partial one and not every quasi-equilibrium is an equilibrium. The standard argument breaks at the claim that there is a cheaper but still Pareto-dominant assignment; this step relies on the prices of goods being strictly positive, which obtains in the standard setting as otherwise agents would demand an infinite amount of zero-price goods. In contrast, zero prices are the staple of our setting as recognized already by Hylland and Zeckhauser (1979). In particular, in a quasi-equilibrium an agent may be assigned a zero-price object while he strictly prefers another zero-price object. As an illustration of these problems, consider the following example. Example 1. Consider an economy with four agents and three objects. Two of the agents have von Neumann-Morgenstern utility vector v = ( 12 , 0, 1), and the remaining two agents have the utility vector v = (0, 1, 12 ). Suppose that there are three copies of object 1, one copy of object 2, and one copy of object 3. The following allocation Q∗ is then Pareto-efficient: v-agents obtain q ∗ = ( 12 , 0, 12 ) and v -agents obtain q ∗ = ( 12 , 12 , 0). The resulting aggregate assignment A (Q∗ ) is (2, 1, 1). Fig. 1 places this point in the barycen- tric simplex of aggregate assignments in which exactly four units are assigned, that is such that endowing agents with initial shares in objects as opposed to token budgets. Pseudomarkets do not allow share endow- ments for reasons explicated in Hylland and Zeckhauser (1979). Furthermore, Maskin and Roberts (2008) rely on local non-satiation and the resulting property that any two bundles an agent is indifferent between have the same price; both local non-satiation and the same-price property fail in our setting. The failure of the latter is illustrated in footnote 26. 17 Note that these sets are convex and they are disjoint. 7 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303   Fig. 1. The simplex of “full-consumption” aggregate assignments. Aggregate assignment A Q∗ is on the intersection of the boundaries of sets Y and Z. for each agent the sum of probabilities of the three goods is 1 (the full-consumption simplex). Set Y represents feasible aggregate assignments in the simplex; it is the triangle spanned by (2, 1, 1), (3, 0, 1) and (3, 1, 0). Set Z represents all aggregate assignments A (Q) in the simplex such that there exists an assignment Q in which all agents are weakly better off than under Q∗ and at least one agent is strictly better off, and such that A (Q) is the aggregate assignment of Q (these assignments are, of course, not feasible). Set Z has five corners: • (2, 1, 1), the aggregate assignment corresponding to Q∗ , • (1, 2, 1), the aggregate assignment when v-agents obtain q ∗ and v -agents obtain (0, 1, 0), • (0, 2 12 , 1 12 ), the aggregate assignment when v-agents obtain 0, 14 , 34 and v -agents obtain (0, 1, 0), • (0, 0, 4), the aggregate assignment when each agent obtains good 3 • (1, 0, 3), the aggregate assignment when v-agents obtain q ∗ and v -agents obtain (0, 0, 1). Only the middle three corners belong to Z, and one of the borders of Z, the dashed line, is disjoint with Z. In particular, the set Z is neither open nor closed. Restricting attention to the assignments in the simplex, there is a horizontal hyperplane sepa- rating Y and Z. This hyperplane corresponds to prices p3 > p 2 = p 1 = 0. When v-agents have budget 21 p 3 and v -agents have budget zero, these prices support Q∗ as a quasi-equilibrium but not as an equilibrium. Indeed, v -agents would rather buy a sure copy of object 2 than the lottery q ∗ , and both these outcomes have the price of zero.18 18 As perceptively observed by a referee, this example has several features that might lead one to wonder whether the problems illustrated by the example can be avoided if we restrict attention to strictly positive valuations or require non-zero budgets. Such simple solutions would not address the problems illustrated by Example 1. For instance, we can add any constant to the valuations and multiple it by any scalar and in such modified example the problematic partially separating hyperplane would still be present even though all valuations are then strictly positive. We could endow v -type agents with any positive budget without otherwise changing the example, and the problematic hyperplane would still be there. We could also modify the example so that all agents have strictly positive budgets and fully spent them: e.g. we could enrich the example by adding a fourth good, which only has one unit available, and that types v like more than other goods (and types v do not want to buy); in such a modification of the example, the price of the fourth good would be strictly positive and equal to twice v types’ individual budgets and the problematic hyperplane would still be present. 8 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 We develop a new proof approach to establish the second welfare theorem and to address the difficulties discussed above and illustrated in Example 1. To understand our approach, observe that in Example 1, there are non-horizontal hyperplanes that fully separate Y and Z (in the full-consumption simplex). We show that this is always the case. A key step in the proof is the following new Full Separation Lemma that establishes that full separation is possible under conditions that—as we will shortly see—are always satisfied in the discrete assignment problems. The full separation relies on the assumption that some of the relevant sets are polyhedra, where a polyhedron is the intersection of a finite number of half spaces.19 Lemma 1 (Full Separation Lemma). Let Y ⊂ Rn be a closed and convex polyhedron. Let Z ⊂ Rn be convex, non-empty, and such that its closure Z̄ ⊂ Rn is a closed and convex polyhedron. Suppose that Z ∩ Y = ∅ and that for all y ∈ Y ∩ Z̄, δ ∈ Rn , and ε > 0 if y + δ ∈ Z, then y − εδ ∈ / Z̄. Then, there exists a price vector p ∈ Rn+ and a budget w ∈ R such that for any z ∈ Z and y ∈ Y we have p · z > w ≥ p · y and such that for any z̄ ∈ Z̄ and y ∈ Y we have p · z̄ ≥ w ≥ p · y. We provide the proof of the lemma in Appendix A. We can easily visualize the statement of the lemma in the context of Example 1. Both the set Y of feasible aggregate assignments and the set Z of (infeasible) aggregate assignments that Pareto dominate Q∗ are polyhedra. Our separation lemma states that if every line through Q∗ and a point in Z has points that belong to the closure of Z only on one side of Q∗ , then there exists a fully separating hyperplane. The line assumption is satisfied in our example. The rest of the proof of the second welfare theorem revolves around showing that indeed the assumption of the lemma is satisfied: no line through Q∗ can intersect the closure of Z on both sides of Q∗ (see the highlighted claim in the proof below). Proof of the Second Welfare Theorem. For any random  assignment Q ∈ A, we define the aggregate assignment A (Q) associated with Q to be i∈I qi , and we write Q  Q∗ when ui (qi ) ≥ ui (qi∗ ) for every i ∈ I with at least one strict inequality. Let Z = {A (Q) : Q  Q∗ , Q ∈ A}, and notice that the above assumption implies that Z is non-empty. Furthermore, Z is convex. Let Z̄ = Cl(Z) be the topological closure of Z, and notice that Z̄ is a non-empty convex polyhedron. Let Y = {A (Q) : Q ∈ F} be the set of aggregate feasible random assignments. This set is a closed and convex polyhedron, and the efficiency of Q∗ implies that Z ∩ Y = ∅. To use the full separation lemma, we need the following Claim. For any y ∈ Y ∩ Z̄, δ ∈ R|X| and ε > 0, if y + δ ∈ Z then y − εδ ∈ / Z̄. 19 The terminology varies in the literature, with most authors referring to this concept as polyhedra and reserving the term polytope for compact polyhedra. Our lemma does not rely on compactness. In the proof of our lemma we rely on an elegant Polyhedral Separation Lemma that McLennan (2002) developed in an ordinal context unrelated to the problems studied in our paper, and that was never previously used to analyze Walrasian equilibria. McLennan’s lemma cannot be substituted for our Full Separation Lemma in the simple proof of our Second Welfare Theorem presented below because his lemma establishes only partial separation between polyhedra, while our proof relies on full separation established by our lemma. (The December 2014 draft of our paper sketched an alternative direct proof of our Full Separation Lemma, and we would like to thank Andrew McLennan for directing us to his lemma as a basis for the current simplified version of our proof.) 9 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 Proof of the claim. If y + δ ∈ Z then there is a Q  Q∗ such that A (Q) = y + δ. By way of contradiction, assume y −εδ ∈ Z̄ = Cl(Z). Thus, there is a Q̃ = (q̃i )i∈I such that ui (q̃i ) ≥ ui (qi∗ ) for every i ∈ I and A Q̃ = y − εδ. Then, the random assignment Q̄ = 1+ε ε Q + 1+ε 1 Q̃ is feasible, and the choice of Q and Q̃ and the linearity of utility ui (·) in probabilities imply that Q̄  Q∗ . But this contradicts the fact that Q∗ is efficient, proving the claim. This claim and the full separation lemma imply that there exists a price vector p ∈ RX + and abudget w ∈ R such that p · z > w ≥ p · y, for any z ∈ Z and y ∈ Y . Since Q ∗ is feasible ∗   i∈I qi ∈ Y and thus p · i∈I qi∗ ≤ w. Furthermore, p · i∈I qi∗ ≥ w because Q∗ ∈ Cl (Z). We conclude p · i∈I qi∗ = w. Now, if we take some  qi that someagent i ∈ I strictly  ∗ prefers to q i,    then qi + j ∈I \{i} qj∗ ∈ Z, and we have p · qi + j ∈I \{i} qj∗ > w = p · qi∗ + j ∈I \{i} qj∗ . Consequently we have p ·qi > p ·qi∗ , proving that p and Q∗ constitute an equilibrium for budgets wi∗ = p · qi∗ . QED 4. Multi-unit demand: Second and First Welfare Theorems We now analyze the validity of our Second Welfare Theorem result in assignment economies in which participants demand multiple units of goods. As in the base model, we have a set of agents I and a set of objects X. Each object x ∈ X has a finite number of units (or copies) |x| ∈ {1, 2, ...} and S = (|x|)x∈X is the supply vector.20 We relax the restriction that each agent demands at most one unit of goods in total, and allow each agent to demand at most k ∈ {1, 2, ...} units of various goods in total. We impose no restrictions on the positive integer k; in particular, it can be larger than the total supply of objects. Let Bi ⊆ {0, 1, ..., k}X be the finite set of admissible individual bundles for agent i, and let bi1 , ..., bi|Bi | denote the elements of Bi . The set Bi can accommodate any restrictions such as, for instance, that the agent consumes at most quantity 1 of each object. Course allocation is an ex- ampleof a multi-unit demand setting  that satisfies this particular restriction: in course allocation, Bi = b ∈ {0, 1}X : x∈X bx ≤ k for each agent i. An individual random assignment qi ∈ (Bi ) of agent i ∈ I is a probability distribution over Bi . The agent’s expected utility is the scalar product qi · vi where vi ∈ R|Bi | is the vector of val- uations for each bundle in Bi . For the sake of linear algebra calculations, we represent the set of bundles Bi by the matrix βi = (βib x) x x∈X,b∈Bi in which βib is the quantity of object  x in bundle b. A deterministic assignment of bundles D = (bi )i∈I ∈ ×i∈I Bi is feasible if i∈I bi ≤ S, co- ordinatewise. We denote by D the (finite) set of all feasible deterministic assignments of bundles and by bi (D) the bundle that agent i obtains under the D ∈ D. We assume throughout that set D is non-empty. Denoting B = ∪i Bi , a random assignment of bundles Q = (qib )i∈I,b∈B ∈ [0, 1]I ×B is feasible in expectation if each qi· has support on Bi and the expected aggregate assignment  does not exceed supply for any good, i∈I,b∈B qib b ≤ S. A random assignment Q = (qib )i∈I,b∈B is feasible (or implementable) if there are nonnegative  weights (λD )D∈D ≥ 0 summing up to 1 and such that, for every i ∈ I and b ∈ B, bi (D)=b λD = qib . By F we denote the set of all feasible random assignments. Of course, every feasible assignment is feasible in expectation. A random assignment of bundles Q ex-ante Pareto-dominates a random assignment of bundles Q∗ if qi · vi ≥ qi∗ · vi for all i ∈ I , with at least one strict inequality. A feasible random assignment of bundles Q∗ = {qi∗ }i∈I is (ex-ante Pareto) efficient if it is not ex-ante Pareto-dominated by any 20 Without affecting the results, we can allow |x| = 0 for all but one object. 10 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 feasible random assignment of bundles. A random assignment of bundles Q∗ is an equilibrium assignment with prices p ∗ ∈ RX ∗ ∗ ∗ + and budgets (wi )i∈I ∈ R+ if, for every agent i ∈ I , p · βi qi ≤ I wi and if qi · vi > qi∗ · vi for some random assignment Q then p ∗ · βi qi > wi . Our single-unit demand Second Welfare Theorem immediately implies the multi-unit demand Second Welfare Theorem if we allowed separate prices for all bundles. Indeed, then we can think of agents as having a single-unit demand: each of them demands at most one bundle. The analysis becomes more subtle if we require—as in the definition of the competitive equi- librium above—that the price of a bundle is the sum of prices of the component goods of the bundle.21 We can then still apply our Full Separation Lemma and replicate the single-unit de- mand analysis provided every random assignment that is feasible in expectation is feasible. This property—established in the single-unit case in the Birkhoff-von Neumann Theorem—ensures that if we moved from an initial (feasible) aggregate assignment in some direction to a (non- feasible) Pareto-dominating aggregate assignment, then when moving in the opposite direction the assignments are not weakly Pareto dominant as otherwise a proper linear combination of both assignments would be feasible by the Birkhoff-von Neumann property and it would Pareto dominate the initial assignment. In consequence, in environments satisfying the Birkhoff-von Neumann property we can directly apply our Full Separation Lemma. There are multi-unit demand settings in which the Birkhoff-von Neumann property is true such as, for instance, the setting in which each agent buys up to some quantity cap of each object, and two lotteries over bundles are treated as equivalent when they are equivalent as lotteries over the quantities of objects; the equivalence which is natural if each agent i’s utility from a feasible bundle  of objects  is given by the sum of agent’s von Neumann-Morgenstern   ṽi = valuations |X| |X| ṽi1 , ..., ṽi for objects in the bundle, that is the utility from bundle qi = qi1 , ..., qi ∈ Xi is the scalar product qi ṽ; the utility from other bundles is zero (cf. Budish et al., 2013).22 At the same time, the Birkhoff-von Neumann Theorem does not in general extend to multi- unit assignments, as pointed out by Budish et al. (2013) in an example with three agents and three objects with unit supply. When each agent demands two objects, then the following ran- dom assignment is feasible in expectation but it is not feasible: each agent receiving a pair of objects (different pair for each agent) with probability 12 and receiving no objects with the re- maining probability 12 .23 The following example illustrates the same failure of the Birkhoff-von Neumann property; the example also illustrates our formalism and lays the ground for the proof of Proposition 1 as well as for Examples 3, 4, and 5. Example 2. There are four objects with unit supply, and there are two agents, each demanding two objects. Thus, the supply vector is S = (1, 1, 1, 1) and the set of admissible bundles is 21 For a taxonomy of bundle prices and discussion of the assumption that the price of the bundle is the sum of item prices, see Bikhchandani and Ostroy (2002). They refer to such prices as linear. We also maintain the standard assumption that all agents face the same prices, thus the prices we study are anonymous in their terminology. 22 Budish et al. (2013) discuss how any profile of random assignments (q ) i i∈I that satisfies the above constraints can be implemented as lotteries over deterministic assignments. They also prove the First Welfare Theorem for the case of equal budgets and additive utilities and showed how to use Milgrom’s (2009) integer assignment messages to reduce certain non-linear preferences to this linear setting. The single-unit demand setting is the special case of the multi-unit demand setting, in which |i| = 1 for each agent i. As implied by our discussion of Birkhoff-von Neumann’s property, our Second Welfare Theorem remains true for any type of consumption constraints Xi that satisfy Birkhoff-von Neumann’s property, e.g. because they satisfy Budish et al.’s hierarchy condition or Pycia and Unver’s (2015) decomposition conditions. 23 The failure of the Birkhoff-von Neumann property was further analyzed by Nguyen et al. (2016). 11 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 B1 = B2 = {(1, 1, 0, 0), (1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0), (0, 1, 0, 1), (0, 0, 1, 1)}. The random assignment Q = (q1 , q2 ) where  q1 = (1/2, 0, 0, 0, 0, 1/2) and q2 = (0, 0, 1/2, 1/2, 0, 0) is feasible in expectation because i∈{1,2},b∈B bqib = S. However, Q is not feasible. We can see this readily as in Q agent 1 receives either both “left objects” 1 and 2 or both “right objects” 3 and 4, while agent 2 receives either both “extremal” objects 1 and 4 or both “middle” objects 2 and 3. More formally, if there is (λD )D∈D ≥ 0, D∈D λD = 1 meeting the condition in the definition, then there must be D ∈ D such that b1 (D) = (1, 1, 0, 0) and λD > 0. However, λD > 0 implies that b2 (D) ∈ {(1, 0, 0, 1), (0, 1, 1, 0)}. In either case D generates excess demand for either object 1 or object 2, contradicting D ∈ D. In environments in which the Birkhoff-von Neumann property may fail, formulating the ana- logue of our Theorem 1 requires care. This is demonstrated by the following Proposition 1. Not every efficient feasible random assignment Q∗ is an equilibrium assignment. Proof. Consider again the two agents and four objects from Example 2, with the set of feasible bundles studied in this example.  Assume  that v1 = (1, 1 − ε, 0,0, 1 − ε, 1) and v2 = (0, 1 − ε, 1, 1, 1 − ε, 0) where ε ∈ 0, 12 . Consider assignment q1∗ , q2∗ such that q1∗ = (0, 1/2, 0, 0, 1/2, 0) and q2∗ = (0, 1/2, 0, 0, 1/2, 0) where the probabilities of bundles in B are listed in the same order as the bundles in Example 2. This assignment is feasible be- cause we can implement it as a 12 : 12 lottery between two feasible deterministic assignments: ((1, 0, 1, 0), (0, 1, 0,1)) and ((0, 1, 0, 1), (1, 0, 1, 0)). The assignment q1∗ , q2∗ is also efficient.  By  way of contradiction, suppose that some other assignment (q1 , q2 ) Pareto dominates q1∗ , q2∗ . As the expected utility from the assignment Q∗ is 1 − ε for both agents, we have   q11 + q16 + (1 − ) q12 + q15 ≥ 1 − ε,   q23 + q24 + (1 − ) q12 + q15 ≥ 1 − ε, where superscripts on probabilities qi1 , ..., qi6 denote the position in which the bundles are listed in B. Denoting ρ1 ≡ q11 + q16 = q21 + q26 , ρ2 ≡ q13 + q14 = q23 + q24 , and ρ3 ≡ q12 + q15 = q22 + q25 , and recognizing that 1 − ρ3 = ρ1 + ρ2 , we can rewrite the above inequalities as ρ1 ≥ (1 − ρ3 ) (1 − ) = (ρ1 + ρ2 ) (1 − ) , ρ2 ≥ (1 − ρ3 ) (1 − ) = (ρ1 + ρ2 ) (1 − ) . Because ε < 1/2, this system of inequalities cannot be satisfied unless ρ 1 = ρ2 = 0. Hence, (q1 , q2 ) must put all the weight on the second and fifth bundle, just like ∗ ∗ ∗ ∗  q1 , q2 , and we can conclude that no feasible random assignment  Pareto-dominating  q 1 , q2 . In spite of being feasible and efficient, q1∗ , q2∗ cannot be an equilibrium assignment. Indeed, |X| for any vector of prices p ∈ R+ the cost of each of the bundles q1∗ , q2∗ , q1 = (1/2, 0, 0, 0, 0, 1/2),  and q2 = (0, 0, 1/2, 1/2, 0, 0) is 12 x p x , while qi · vi > qi∗ · vi for both i ∈ {1, 2}. QED 4.1. Second Welfare Theorem In order to recover the Second Welfare Theorem we will strengthen the efficiency requirement. We say that a feasible random assignment of bundles Q∗ is strongly efficient if it is not ex-ante 12 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 Pareto-dominated by any feasible-in-expectation random assignment of bundles. Because every feasible assignment is feasible in expectation, strong efficiency is indeed more demanding than efficiency we studied so far. A positive feature of strong efficiency, and an advantage over the efficiency concept studied above, is that verifying it does not require the market participants to verify whether swaps of probabilities can be implemented; it is the natural concept when thinking in terms of marginal probabilities. In all settings that satisfy the Birkhoff-von Neumann Theorem, strong efficiency and efficiency are of course equivalent. The following result then holds24 Theorem 2 (Second Welfare Theorem for General Multi-unit Demands). If a feasible random assignment of bundles Q∗ is strongly efficient, then it is an equilibrium random assignment sup- ported by some vector of prices p ∗ ∈ RX ∗ ∗ + and some vector of budgets w = (wi )i∈I ∈ R+ . I We prove this theorem as an immediate corollary from the following Theorem 3. If a feasible-in-expectation random assignment of bundles Q∗ cannot be ex-ante Pareto-dominated by any other feasible-in-expectation random assignment of bundles, then Q∗ is an equilibrium random assignment supported by some prices p ∗ ∈ RX ∗ + and budgets (wi )i∈I ∈ I R+ . The latter result is more general because it only requires random assignment of bundles Q∗ to be feasible in expectation. Remark 1. In both of Theorems 2 and 3, we can add that the equilibrium we construct satisfies the following complementary slackness condition: p x∗ > 0 implies that there is no excess supply of object x, i∈I βix qi∗  = |x|. To see this suppose that there is an excess supply of object x at assignment Q∗ . If 0 < i∈I βix qi∗ < |x| then the set of feasible assignments contains assign- ments with more of object x than Q∗ as well as assignments with less of object x than Q∗ . In particular, the separating hyperplane between feasible assignments and dominant assignments contains a line parallel to x-axis. Hence, the resulting  price vector is orthogonal to x-axis and the price of good x is zero. In the remaining case, 0 = i∈I βix qi∗ , hence qi∗ = 0 for all agents i, and the efficiency of assignment Q∗ allows us to set the price of good x at zero without affecting the equilibrium demands of agents. To get a sense of the proof of Theorem 3, notice that each random assignment over bundles determines the expected assignment of agent i over the underlying goods, μi = βi qi . Because the prices are defined on the underlying goods, every lottery over bundles that leads to the same expected assignment over the underlying goods has the same price. We can also input utility to the expected assignment by recognizing that in the equilibrium an agent buys the lottery over bundles in Bi that maximizes the agent’s utility among all lotteries of the same price. For every expected assignment μi in the convex hull of Bi —the convex hull denoted by Co(Bi )—we thus define agent i’s utility Vi from μi as Vi (μi ) = max q · vi . {q∈(Bi )|βi q=μi } 24 Combining this result and the previous proposition, we can conclude that in the setting of Example 2 efficiency does not imply strong efficiency. 13 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 Fig. 2. Piece-wise linearity of preferences over expected allocations. The following property of this utility function allows us to apply the methods we developed for the single-demand case and prove the second welfare theorem. Lemma 2 (Polyhedral Lemma). For every μi ∈ Co(Bi ), the upper contour set Ui (μi ) = {μ ∈ Co(Bi ) : Vi (μ) ≥ Vi (μi )} of assignments better than μi for agent i is a convex polyhedron. The proof of this lemma is in Appendix B. The key claim of the lemma is that the upper contour set is a polyhedron. To get a sense for why this claim is true consider the example illustrated in Fig. 2. In the figure, agent i has four possible bundles, Bi = {bi1 , ..., bi4 }, and the convex hull Co (Bi ) takes the shape of the rhomboid. The highlighted dot represents an expected assignment μi . This expected assignment is a convex combination of {bi1, bi3 , bi4 } and it is also a convex combination of {bi2 , bi3 , bi4 }. Indeed, by the well-known Carathéodory’s theorem, any expected assignment in Co (Bi ) is a convex combination of just three extreme points in Bi .25 The weights in each of these two convex combinations are unique, and any other representation of μi as a convex combination of {bi1 , bi2 , bi3 , bi4 } can be decomposed as a convex combination of these two 3-point convex combinations. Taking into account that Vi (μi ) is the maximum of a linear function, to calculate Vi (μi ) we only need to know the utility V at these two 3-point convex combinations. This analysis remains valid for any expected assignment in the interior of the triangle span by points A, bi3 , and bi4 . Thus, the aforementioned triangle can be divided into a finite number (here: two) of regions on which the set of bundles implementing V is constant. Linearity of the objective function guarantees that there is a hyperplane separating these two regions. If—as in the figure—the expected assignment μi is not on this separating hyperplane, then there is a neighborhood of μi on which the maximizer convex combination comes from the same set, say {bi2 , bi3 , bi4 }. In the figure, this is true for all points in the interior of the triangle span by points A, C, and bi3 (note this is a smaller triangle than the one referred to previously). Thus the preferences are linear in a neighborhood of the expected assignment μi . The figure represents the neighborhood of μi by a ball, and it also illustrates the parallel linear indifference curves and the direction in which utility increases. 25 We thank Jordi Massó for directing us to the Carathéodory’s theorem. 14 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 Lemma 2 enables us to leverage the methods we developed in Section 3 to prove Theorem 3. The proof, similarly to the proof of Theorem 1, leverages our general Full Separation Lemma (Lemma 1).  Proof of Theorem 3. Let Y = {m ∈ i∈I Co(Bi ) : m ≤ S} be the set of feasible aggregate expected  allocations. Notice that Y is a polyhedron to which the expected assignment μ∗i = ∗ ∗ ∗ i∈I βi qi of Q = {qi }i∈I belongs. Denote the set of aggregate Pareto-improvements by   Z= m∈ Co(Bi )| (∃(μi )i∈I ) μi = m & (∀i ∈ I ) Vi (μi ) ≥ Vi μ∗i i∈I i∈I   & (∃i) Vi (μi ) > Vi μ∗i . Because Q∗ is not ex-ante Pareto-dominated by any other feasible-in-expectation  random assign- ment, Z ∩ Y = ∅. Furthermore, the aggregate upper contour set U = i∈I Ui (μi ) is a closure of Z and, by Lemma 2, U is a polyhedron. To be able to apply our Full Separation Lemma it remains to verify that for no z ∈ Z and y ∈ Y , there is ε > 0 such that y − ε(z − y) ∈ U . By way of contradiction suppose there are such z, y and ε. Then,   there is some μ = (μ i )i∈I such that i∈I μi =y − ε(z − y) and, for all i ∈ I , Vi (μi ) ≥ Vi μ∗i . Because z ∈ Z there is μ = (μi )i∈I such that i∈I μi = z and, for all i ∈ I , Vi (μi ) ≥   Vi μ∗i , with strictinequality for some i. Consider the expected assignment μ = 1+ε μ + 1+ε μ . 1 ε By construction, i∈I μi = y ≤ S, and, by convexity of Vi established in Lemma 2, for all i ∈ I   we have Vi (μi ) ≥ 1+ε 1 Vi (μi ) + 1+εε Vi (μi ) ≥ Vi μ∗i , with strict inequality for some i. This contradicts the fact that Q∗ is strongly efficient. Thus we can apply the Full Separation Lemma to conclude that there is a hyperplane that fully separates Y and Z. The rest of the proof is standard and follows the same step as the analogous part of Theorem 1 above. QED 4.2. First Welfare Theorem An immediate question is whether all equilibrium outcomes are strongly efficient? We address this question by proving the First Welfare Theorem for strong efficiency under two assumptions. We assume that every agent buys a lowest cost (cheapest) among all optimal affordable lotteries, a standard condition in the analysis of the pseudomarkets introduced and motivated by Hyl- land and Zeckhauser (1979). This lowest cost condition is, for instance, implied by the generic assumption that each agent has a unique favorite bundle, which immediately implies that each agent buys a cheapest favorite affordable bundle. We also restrict attention to equilibria satisfying thecomplementary slackness condition: p x∗ > 0 implies that there is no excess supply of good x, i∈I βix qi∗ = |x|.26 26 The assumption of complementary slackness is justified as we show that all strongly efficient assignments can be implemented via equilibria satisfying complementary slackness, cf. Remark 1. Complementary slackness is however a more substantive assumption than in environments with local non-satiation where it is trivially satisfied. The reason to impose the lowest cost condition can be seen in the following example with one unit of object x, two units of object y and three agents. Agent 1 strictly prefers x to y, agent 2 strictly prefers y to x, and agent 3 is indifferent. The following is an equilibrium in which each of these agents has budget of 1: the price of good x is 2, the price of good y is 0, agents 15 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 Theorem 4 (First Welfare Theorem). If an equilibrium satisfies the lowest cost and complemen- tary slackness conditions, then the equilibrium assignment is strongly efficient. Proof. Let p ∗ ∈ RX + be the vector of equilibrium prices. By way of contradiction, suppose that ∗ ∗ the equilibrium assignment Q  = {qi }i∈I is not strongly ∗efficient. Then there is an expected allocation (μi )i∈I such that i∈I μi ≤ S and Vi (μi ) ≥ qi · vi for all i ∈ I , with at least one inequality strict. If an agent i is not satiated under qi∗ —that is with positive probability her outcome is worse than her most preferred bundle—then p ∗ · μi ≥ p ∗ · βi qi∗ by the same argument that works in standard Walrasian equilibrium theory with non-satiated agents.27 If agent i is satiated then the same inequality holds provided she bought the least expensive most-preferred lottery. The same argument, gives us p ∗ · μi > p ∗ · βi qi∗ for agents i for whomthe inequality Vi (μi ) ≥ qi∗ · vi is strict. Summing up the inequalities over agents, we obtain i∈I p ∗ · μi >  ∗ ∗ i∈I p x · β x∗ > 0 and such that i qi . In particular, there is an object x with positive price p x ∗ x∗ i∈I μxi > i∈I βi qi . Because p > 0, the complementary slackness condition implies that β q ∗ = |x| (no excess supply). We thus obtain a contradiction with the assumption that i∈I i i i∈I μi ≤ S. QED 4.3. Existence The final question we address is whether strongly efficient assignments—and hence equilibria —exist. The potential subtlety is that strongly efficient feasible random assignment need to be favorable compared to both feasible and unfeasible random assignment of bundles. It turns out that in general a feasible random assignment of bundles that is strongly efficient might not exist. However, strongly efficient assignments exist in course allocation setting, the leading example of the multi-unit setting, provided agents’ preferences over bundles are strict; strict preferences are generic.28 Theorem 5 (Existence). In course allocation, if agents’ preferences over bundles are strict, then there exists a feasible deterministic assignment that is strongly efficient. Proof. We construct the strongly efficient assignment via a serial dictatorship mechanism. Fix an arbitrary ordering of agents, say 1, ..., |I |. Let 0 denote the bundle with 0 units of each object. Let B1∗ ⊆ B1 be the set of bundles b such that (b, 0, ..., 0) is feasible; we assign to agent 1 his or her most preferred bundle b1 in B1∗ . Let B2∗ ⊆ B2 be the set of bundles b such that (b1 , b, 0, ..., 0) is feasible; we assign to agent 2 his or her most preferred bundle b2 in B2∗ . Proceeding recursively, we define a feasible deterministic assignment. Note that the mechanism is well-defined because in the course allocation setting B1∗ , B2∗ , ..., B|I∗ | are non-empty and, thanks to the strict preference assumption, each agent i has the most preferred bundle in Bi∗ . 1 and 3 buy probability .5 in good x and probability .5 in good y, agent 2 buys probability 1 in good y. This equilibrium violates the lowest cost condition and it is inefficient as it is dominated by an allocation in which agent 1 buys probability 1 of good x, while each of the remaining agents buy probability 1 of good y. 27 Suppose p ∗ · μ < p ∗ · β q ∗ and let b be a most preferred bundle of agent i. We can then find a small weight α > 0 i i i i   such that Vi (αbi + (1 − α)μi ) > qi∗ · vi and p∗ · αbi∗ + (1 − α)μi ≤ p∗ · βi qi∗ , contradicting that qi∗ was an optimal choice in i’s budget set. 28 We illustrate the role of the course allocation and strict preference assumptions in Examples 4 and 5 below. The restriction to course allocation was missing in our 2017-2020 drafts. 16 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 It remains to verify that the resulting assignment is strongly efficient. By way of contradiction suppose that Q = (qi )i∈I is a strictly dominant random assignment that is feasible in expectation. Agent by agent, we show that qi put probability 1 on assignment bi constructed above. Consider agent 1. If bundle b̃ ∈ B1 − B1∗ then the failure of feasibility would imply that b̃x > |x| for some object x ∈ X; this cannot happen in course allocation where b̃x ≤ 1 and |x| ≥ 1. Thus, the support of the lottery q1 is contained in B1∗ . Furthermore, because b1 is 1’s the unique most favorite bundle in B1∗ and the support of q1 is contained in B1∗ , Pareto efficiency implies that q1 puts entire probability on b1 . Consider agent 2. If bundle b̃ ∈ B2 − B2∗ then b̃x > |x| − b1x for some object x ∈ X; this can only happen when b1x = 1 and |x| − b1x = 0. As Q is feasible in expectation, the expected number of units of x in q2 is zero, and we conclude that b̃x = 0 for all bundles in the support of q2 . Thus, the support of q2 is contained in B2∗ . Furthermore, because b2 is i2 ’s the unique most favorite bundle in B2∗ and the support of q2 is contained in B2∗ , Pareto efficiency implies that q2 puts entire probability on b2 . Proceeding recursively, we find that the analysis for agent 3 and for subsequent agents is anal- ogous to the analysis for agent 2. If bundle b̃ ∈ Bi − Bi∗ then b̃x > |x| − b1x − ... − bi−1 x for some object x ∈ X; this can only happen when bi = 1 and |x| − b1 − ... − bi−1 = 0. We conclude that x x x the support of qi is contained  in Bi∗ and hence that qi puts entire probability on bi . In effect, Q puts probability 1 on b1 , ..., b|I | which is the assignment of the serial dictatorship mechanism. Hence, Q does not strictly Pareto dominate the outcome of the mechanism; a contradiction that proves the assignment of the serial dictatorship is strongly efficient. QED Remark 2. The proof of Theorem 5 shows not only that there exists strongly efficient assign- ments but also that the serial dictatorships used in the proof always generate strongly efficient outcomes. The existence theorem is less straightforward than it might ex ante appear. First, not all Pareto efficient deterministic outcomes are strongly efficient, even in course allocation setting with strict preferences. Second, the strong efficiency of serial dictatorships is not guaranteed in general multi-unit environments. Third, the assumption of strict preferences is needed for the result. These three points are illustrated by the following examples. Example 3. To see that not all Pareto efficient deterministic outcomes are strongly efficient, con- sider the environment of Example 2 allowing that bundles in which agents receive fewer than two courses are also admissible.29 Suppose that—in the terminology from Example 2—agent 1 strictly prefers the left bundle (1, 1, 0, 0) to the right bundle (0, 0, 1, 1) and strictly prefers the latter to all other bundles. Suppose that agent 2 strictly prefers the extreme bundle (1, 0, 0, 1) to the middle bundle (0, 1, 1, 0), strictly prefers the middle bundle to the left bundle, and strictly prefers the latter to all other bundles. Then, the deterministic assignment in which agent 1 re- ceives the right bundle and agent 2 receives the left bundle is Pareto efficient. At the same time, this deterministic assignment is not strongly efficient because it is dominated by the feasible-in- expectation random assignment (q1 , q2 ) from Example 2, which gives the 50-50 lottery over left and right bundle to agent 1 and gives 50-50 lottery over extreme and middle bundle to agent 2. 29 The admissibility of these bundles plays no role in the argument but the course allocation model requires it. 17 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 Example 4. To see how some feasibility constraints may cause existence problems, let us modify Example 2 so that B1 = {(1, 1, 0, 0), (1, 0, 0, 1), (0, 0, 1, 1)}, B2 = {(1, 1, 0, 0), (1, 0, 0, 1), (0, 1, 1, 0)}. Then, only two deterministic assignments are feasible: either agent 1 receives (1, 0, 0, 1) while agent 2 receives (0, 1, 1, 0); or agent 1 receives (0, 0, 1, 1) while agent 2 receives (1, 1, 0, 0). (1,1,0,0) (0,0,1,1) (1,0,0,1) (1,0,0,1) (0,1,1,0) If the valuation vectors satisfy v1 > v1 > v1 and v2 > v2 > (1,1,0,0) v2 , then, for each agent, the value of any feasible deterministic assignment is strictly lower than the expected value of the random assignment (q1 , q2 ) from Example 2; the random assign- ment (q1 , q2 ) is feasible in expectation but it is not feasible. In effect, in this modification of Example 2, no feasible assignment is strongly efficient. Example 5. To see the need for the strict preference assumption, consider again Example 2 allowing  that bundles in which agents receive fewer than two courses are also admissible. Fix ε ∈ 0, 12 , and let the values of admissible bundles be equal to 0, except for (1,1,0,0) (0,0,1,1) (1,0,0,1) (0,1,1,0) v1 = v1 = v2 = v2 = 1, (1,0,1,0) (0,1,0,1) (1,0,1,0) (0,1,0,1) v1 = v1 = v2 = v2 = 1 − ε. As ε > 0, all deterministic assignments—and hence all feasible random assignments—are Pareto dominated by the feasible-in-expectation random assignment (q1, q2 ) from Example 2. Indeed, (q1 , q2 ) gives expected utility 1 to each agent, while any deterministic assignment either gives utility 1 − ε to both agents, or it gives utility 0 to both agents, or it gives utility 0 to one of the agents and 1 to the other. In particular, in this example no feasible assignment is strongly efficient.30 4.4. Constraints Our model allows for many design constraints such as e.g. reserving some seats in a school for a group of applicants, while allowing all applicants to compete for the remaining seats; to model such constraint we create an auxiliary object “reserved seats” and we define the sets Bi in such a way that individual allocations with copies of the reserved seats object are feasible only for the selected group of applicants. Furthermore, our First and Second Welfare Theorems (Theorems 1-4) remain valid—with no changes in proofs—under any conjunction of linear constraints imposed on random and deterministic assignments as long as the set of feasible assignments remains nonempty.31 Our existence result (Theorem 5) and its proof remain valid under any conjunction of nonnegative in- teger upper bounds on unweighted sums of probabilities of arbitrarily selected agents receiving arbitrarily selected objects. 30 This example hinges on indifferences and, unlike Example 3, it is non-generic; indeed, Theorem 5 implies that generically at least one deterministic assignment is strongly efficient. 31 Indeed, under any such conjunction of constraints the polyhedra in the proofs of our Second Welfare Theorems (Theorems 1, 2, and 3) remain polyhedra and all the steps of the proofs and all our lemmas, including our Full Separation Lemma, remain applicable. The proof of the First Welfare Theorem (Theorem 4) remains valid because imposing a conjunction of linear constraints preserves the convexity of sets we work with; for the role of convexity in this proof see footnote 27. 18 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 5. Conclusion We have established the Second Welfare Theorem for the general class of single-unit demand and multi-unit demand discrete allocation problems. We show that in large range of market de- sign settings—including school choice, course allocation, and refugee resettlement—efficient assignments can be implemented by token price mechanisms, thus providing the foundations for the literature’s focus on such mechanisms. Our Second Welfare Theorem has already played the role of a revelation principle for discrete mechanism design.32 In addition to this substantive insight, we developed a novel approach to analyzing Walrasian markets in which agents’ preferences fail the standard local non-satiation assumption; our ap- proach builds on the polyhedral properties of the Walrasian markets for discrete resources. Our analysis allows arbitrary utility profiles over bundles of objects and arbitrary linear con- straints, thus contributing both to the literature on constraints in market design as well as the literature on complementarities and substitutes discussed in the introduction. Appendix A. Proof of Lemma 1 (Full Separation Lemma) We say that Z̄ is partially separated (or simply, separated) from Y when there is scalar w ∈ R and price vector p ∈ Rn such that p · z̄ ≥ w ≥ p · y for all z̄ ∈ Z̄ and y ∈ Y . We say that Z is fully separated from Y when there is scalar w ∈ R and price vector p ∈ Rn such that p · z > w ≥ p · y for all z ∈ Z and y ∈ Y . Let P be a polyhedron in Rn that is the intersection of a finite number of half spaces; each half-space bounded by a hyperplane. Let H1 , ..., HK be the set of these hyperplanes; we refer to them as the hyperplanes defining P . A face of P is an intersection P ∩ (∩k∈J Hk ) for some J ⊆ {1, ..., K}, and we also call the empty set a face of P .33 The affine hull of a set, denoted aff, is the collection of all finite linear combinations of points in the set with weights adding up to 1 (with negative weights allowed, as opposed to a convex hull). In the proof we will use McLennan’s (2002) Separating Hyperplane Theorem, which states the following34 : Lemma 3 (McLennan’s Separating Hyperplane Theorem). Suppose Y ⊂ Rn and Z̄ ⊂ Rn are polyhedra. Let FY be the intersection of all faces of Y that contain Y ∩ Z̄ and let FZ̄ be the intersection of all faces of Z̄ that contain Y ∩ Z̄. If aff(FY ∪ FZ̄ ) = Rn , then there is a hyperplane H that separates Rn into two half spaces H + and H − where Y ⊆ H − and Z̄ ⊆ H + such that Y ∩ H = FY and Z̄ ∩ H = FZ̄ . As a consequence we conclude Lemma 4. Suppose Y ⊂ Rn and Z̄ ⊂ Rn are polyhedra. Let FY be the intersection of all faces of Y that contain Y ∩ Z̄ and let FZ̄ be the intersection of all faces of Z̄ that contain Y ∩ Z̄. Either there exists a hyperplane H that separates Rn into two half spaces H + and H − where Y ⊆ H − 32 Cf. Miralles and Pycia (2015), Miralles (2017) and Schlegel and Mamageishvili (2020), as well as other papers discussed in the introduction. 33 Notice that we allow J = ∅ and hence P is a face of itself. 34 McLennan developed this theorem in an ordinal context unrelated to the problems studied in our paper, and it was never previously used to analyze Walrasian equilibria. 19 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 and Z̄ ⊆ H + such that Y ∩ H = FY and Z̄ ∩ H = FZ̄ , or else aff(FY ∪ FZ̄ ) = Rn and Y = FY and Z̄ = FZ̄ . Proof of Lemma 4. If aff(FY ∪ FZ̄ ) = Rn then the claim follows from McLennan’s Lemma. It remains to consider the case when aff(FY ∪ FZ̄ ) = Rn . Suppose we embed Y and Z̄ in Rn × R as Y × {0} and Z̄ × {0}, respectively. Then, McLennan’s Lemma implies the existence of a hyperplane H that separates Rn+1 into two half spaces H + and H − where Y × {0} ⊆ H − and Z̄ × {0} ⊆ H + such that Y × {0} ∩ H = FY × {0} and Z̄ × {0} ∩ H = FZ̄ × {0}. The two inclusions allow us to infer that Y × {0} ⊆ H and Z̄ × {0} ⊆ H . Furthermore, the two equalities and aff(FY ∪ FZ̄ ) = Rn allows us to conclude that H = Rn × {0}. The claim of Lemma 5 then follows. QED We now turn to the proof of our Full Separation Lemma. We may assume that Y ∩ Z̄ is non-empty as otherwise the lemma follows from the standard separating hyperplane theorem for closed convex sets.35 Let S be the affine hull of Y ∩ Z̄. Being an affine hull, S is a linear subspace of Rn . Furthermore, S is a linear subspace of dimension lower than n. Indeed, if not then the convexity of Y ∩ Z̄ would imply that there is an open ball B ⊂ Y ∩ Z̄ around some point y ∗ ∈ Y ∩ Z̄. But then, taking any z ∈ Z and setting δ = z − y ∗ , we would find an  > 0 such that y ∗ − δ ∈ B contrary to y ∗ − δ ∈ / Z̄. Let FZ̄ be the intersection of all faces of Z̄ that contain Y ∩ Z̄, that is FZ̄ is the intersection of Z̄ with all hyperplanes that define faces of Z̄ and contain Z̄ ∩ Y . Similarly, let FY be the intersection of all faces of Y that contain Y ∩ Z̄. From Lemma 4, we know that either (i) there exists a hyperplane H that separates Rn into two half spaces H + and H − where Y ⊆ H − and Z̄ ⊆ H + such that Y ∩ H = FY and Z̄ ∩ H = FZ̄ , or else (ii) aff(FY ∪ FZ̄ ) = Rn and Y = FY and Z̄ = FZ̄ . Consider case (i). Because Z ∩ H ⊆ Z ∩ FZ̄ , to prove that H fully separates Z and Y , it is sufficient to show that Z ∩ FZ̄ = ∅. Suppose not. FZ̄ is non-empty. If FZ̄ is a singleton then let z be the only point contained in FZ̄ . Because Z̄ ∩ Y = FZ̄ ∩ Y is nonempty, we conclude that z ∈ Y and because Z ∩ FZ̄ is non-empty we conclude that z ∈ Z. But this contradicts Z ∩ Y = ∅. We can thus assume that FZ̄ contains at least two points. Define the relative interior of a set to be the interior of this set in the linear space spanned by the affine hull of this set. Because FZ̄ is a convex polyhedron, its relative interior, denoted ri(FZ̄ ), is nonempty. Because FZ̄ is the intersection of Z̄ and all the hyperplanes Hk defining Z̄ and containing Y ∩ Z̄, we can infer that Y ∩ ri(FZ̄ ) = ∅. Indeed, if Y ∩ ri(FZ̄ ) = ∅ then the intersection Y ∩ Z̄ = Y ∩ FZ̄ of the polyhedra Y and Z̄ would be disjoint with the relative interior of FZ̄ and hence, being convex, this intersection would be contained in a face of FZ̄ that is a proper subset of FZ̄ . But this is a contradiction as FZ̄ is the smallest face of Z̄ containing Y ∩ Z̄. Let thus a ∈ Y ∩ ri(FZ̄ ), and, by way of contradiction, assume that there is z∗ ∈ Z ∩ FZ̄ . Because z∗ ∈ FZ̄ and a ∈ ri(FZ̄ ), we infer that a − ε[z∗ − a] ∈ FZ̄ ⊆ Z̄ for any ε > 0 small enough, and the assumptions of our lemma imply that a + [z∗ − a] ∈ / Z, a contradiction. Finally, we show that case (ii) cannot happen. If it did then Z̄ = FZ̄ and hence Z̄ itself would be the only face of Z̄ that contains Y ∩ Z̄. Because Y is convex, this would imply that Y has a non-empty intersection with the relative interior of Z̄. Let a ∈ Y ∩ ri(Z̄) and let z∗ ∈ Z. Because z∗ ∈ Z̄ and a ∈ ri(Z̄), we infer that a − ε[z∗ − a] ∈ Z̄ for any ε > 0 small enough, and the 35 The theorem says that there is a fully separating hyperplane for any two disjoint convex closed sets in Rn , see e.g. Boyd and Vandenberghe (2004). 20 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 assumptions of our lemma imply that a + [z∗ − a] ∈ / Z, a contradiction that concludes the proof of the Full Separation Lemma. QED Appendix B. Proof of Lemma 2 (Polyhedral Lemma) The next two lemmas jointly imply the result. Lemma 5 (Convexity). Preferences represented by Vi are convex. Proof.  Take λ ∈ [0, 1] and μi , μi ∈ Co(Bi ). We need to show that λVi (μi ) + (1 − λ)Vi (μi ) ≤ Vi λμi + (1 − λ)μi . By the definition of V , there is q ∈ (Bi ) such that βi q = μi and Vi (μi ) = q · vi . Similarly, there is q ∈ (Bi ) such that βi q = μi and Vi (μi ) = q · vi . Then, λVi (μi ) + (1 − λ)Vi (μi ) = [λq + (1 − λ)q ] · vi ≤ max q · vi q ∈(Bi )|βi q =λμi +(1−λ)μi = Vi (λμi + (1 − λ)μi ) where the inequality follows because βi [λq + (1 − λ)q ] = λμi + (1 − λ)μi , and hence q = λq + (1 − λ)q is in the set the maximum above is taken over. QED Lemma 6 (Piecewise Affinity). Let i be an agent. Let L be the linear space spanned by Bi and let d be its dimension. There is a finite number of L-open and convex sets M ⊆ Co(Bi ) such that almost every μi ∈ Co(Bi ) belongs to one of these sets and Vi is an affine function of μ  M; that is, for all μ, μ ∈ M and λ ∈ [0, 1], Vi λμ + (1 − λ) μ = λVi (μ) + on each ofthese (1 − λ) Vi μ . Proof. The set D of expected assignments in Co (Bi ) that can be represented as a convex combination of d or fewer points in Bi is of measure zero in L. This claim follows from two observations. First, the convex hull of any d or fewer points is of dimension at most d − 1, and hence of measure zero in the d-dimensional space L. Second, there is only a finite number of subsets in Bi because Bi itself is finite. Let us fix an expected assignment μi ∈ Co(Bi ) − D. Let Bi (μi ) be the set of all B ⊆ Bi such that |B| ≤ d + 1 and μi is a convex combination of elements from B. Because μi ∈ /D we infer that each B ∈ Bi (μi ) has exactly d + 1 elements. Bi (μi ) is finite because Bi is finite. Bi (μi ) is nonempty because Carathéodory’s Theorem tells us that μi can be represented as a convex combination of d + 1 elements of Bi . Furthermore, for any B ∈ Bi (μi ) there is exactly one convex combination of elements of B that gives μi . Indeed, if there were two such convex combinations then μi would also be a convex combination of elements from a proper subset of B; a contradiction because |B| = d + 1 and μi ∈ / D. By definition of Vi , there is B ∈ Bi (μi ) such that Vi (μi )= q · vi for  some  q ∈ (Bi ) such that μi = βi qi , and q b > 0 iff b ∈ B. For any ε ∈ 0, min q b |b ∈ B ∪ 1 − q b |b ∈ B , the ε  b B (μi )b of convex set  combinations of elements of B with weight on each b ∈ B taken from q − ε, q + ε is a convex full-dimensional open subset of Co (Bi ), and hence a convex L- neighborhood of μi . We claim that for sufficiently small ε > 0, all expected assignments in B ε (μi ) have a unique decomposition as a convex combination over a subset of Bi (μi ), and this unique decomposition 21 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 is over B. Indeed, if not then there is a sequence of μi ∈ Co (Bi ) that tends to μi as → ∞ and such that all μi have at least two convex decompositions over subsets of Bi (μi ). Same argument as above shows that then all μi ∈ D and we can select a subsequence n such that all μi n are convex combinations of the same d (or fewer) points in B. But then μi = limn→∞ μi n would also be a convex combination of the same d (or fewer) points in B, a contradiction. Take ε that is sufficiently small in the sense of the above claim. Then, μi is an arbitrary el- ement of the full measure subset of Co (Bi ), and the uniqueness of the convex decomposition implies that for all q ∈ (Bi ) such that q b > 0 iff b ∈ B and βi q belongs to the convex neigh- borhood B ε (μi ) of μi , the utility Vi (βi q) = q · vi . Thus, Vi is affine on B ε (μi ). There is a finite number of different sets B of d + 1 bundles from Bi . For any such B, the convexity of Vi established in Lemma 5 and the local validity of the affine representation of Vi that we just derived imply that the affine representation is valid on the convex hull of all aggregate assignments spanned by B, which concludes the proof. QED References Abdulkadiroglu, Atila, Agarwal, Nikhil, Pathak, Parag A., 2017. The welfare effects of coordinated assignment: evidence from the New York city high school match. Am. Econ. Rev. 107 (12), 3635–3689. Abdulkadiroglu, Atila, Yeon-Koo, Che, Yasuda, Yasuke, 2011. Resolving conflicting preferences in school choice: the Boston mechanism reconsidered. Am. Econ. Rev. 101 (1), 399–410. Abdulkadiroglu, Atila, Pathak, Parag A., Roth, Alvin E., 2009. Strategy-proofness versus efficiency in matching with indifferences: redesigning the NYC high school match. Am. Econ. Rev. 99 (5), 1954–1978. Abdulkadiroglu, Atila, Sonmez, Tayfun, 1998. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66, 689–701. Abdulkadiroglu, Atila, Sonmez, Tayfun, 2003. School choice: a mechanism design approach. Am. Econ. Rev. 93 (3), 729–747. Anderson, Robert M., 1988. The second welfare theorem with nonconvex preferences. Econometrica 56 (2), 361–382. Andersson, Tommy, Ehlers, Lars, 2020. Assigning refugees to landlords in Sweden: efficient stable maximum matchings. Scand. J. Econ. 122 (3), 937–965. Arrow, Kenneth, 1951. An extension of the basic theorems of classical welfare economics. In: Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability. University of California Press. Ashlagi, Itai, Shi, Peng, 2016. Optimal allocation without money: an engineering approach. Manag. Sci. 62 (4), 1078–1097. Azevedo, E., Budish, E., 2019. Strategyproofness in the large. Rev. Econ. Stud. 86 (1), 81–116. Babaioff, Moshe, Nisan, Noam, Talgam-Cohen, Inbal, 2021. Competitive equilibrium with indivisible goods and generic budgets. Math. Oper. Res. 46 (1), 382–403. Baldwin, Elizabeth, Klemperer, Paul, 2019. Understanding preferences: “demand types”, and the existence of equilibrium with indivisibilities. Econometrica 87 (3), 867–932. Baldwin, Elizabeth, Edhan, Omer, Jagadeesan, Ravi, Klemperer, Paul, Teytelboym, Alexander, 2020. The Equilibrium Existence Duality: Equilibrium with Indivisibilities and Income Effects. Working Paper. Bergstrom, Ted C., 1976. How to discard ‘free disposability’—at no cost. J. Math. Econ. 3, 131–134. Bikhchandani, Sushil, Ostroy, Joseph M., 2002. The package assignment model. J. Econ. Theory 107 (2), 377–406. Bogomolnaia, A., Moulin, H., 2001. A new solution to the random assignment problem. J. Econ. Theory 100, 295–328. Bogomolnaia, A., Moulin, H., Sandomirskiy, F., Yanovskaya, E., 2017. Competitive division of a mixed Manna. Econo- metrica 85 (6), 1847–1871. Bogomolnaia, A., Moulin, H., Sandomirskiy, F., Yanovskaya, E., 2019. Dividing bads under additive utilities. Soc. Choice Welf. 52 (3), 395–417. Boyd, S., Vandenberghe, L., 2004. Convex Optimization. Cambridge University Press. Budish, E., 2011. The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119, 1061–1103. 22 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 Budish, E., Cantillon, E., 2012. The multi-unit assignment problem: theory and evidence from course allocation at Har- vard. Am. Econ. Rev. 102, 2237–2271. Budish, E., Che, Y.K., Kojima, F., Milgrom, P., 2013. Designing random allocation mechanisms: theory and applications. Am. Econ. Rev. 103, 585–623. Carroll, Gabriel, 2010. An efficiency theorem for incompletely known preferences. J. Econ. Theory 145, 2463–2470. Debreu, Gerard, 1951. The coefficient of resource utilization. Econometrica 19 (3), 273–292. Delacretaz, David, Duke Kominers, Scott, Teytelboym, Alexander, 2020. Matching Mechanisms for Refugee Resettle- ment. Working Paper. Echenique, Federico, Miralles, Antonio, Zhang, Jun, 2021a. Fairness and efficiency for probabilistic allocations with participation constraints. J. Econ. Theory. Forthcoming. Echenique, Federico, Miralles, Antonio, Zhang, Jun, 2021b. Constrained pseudo-market equilibrium. Am. Econ. Rev. Forthcoming. Featherstone, Clayton, Niederle, Muriel, 2016. Improving on strategy-proof school choice mechanisms: an experimental investigation. Games Econ. Behav. 100, 353–375. Florig, M., Rivera, J., 2010. Core equivalence and welfare properties without divisible goods. J. Math. Econ. 46, 467–474. Gul, F., Pesendorfer, W., Zhang, M., 2019. Market Design and Walrasian Equilibrium. Working Paper. Hafalir, I., Miralles, A., 2015. Welfare maximizing assignment of agents to hierarchical positions. J. Math. Econ. 61, 253–270. Hara, Chiaki, 2005. Existence of equilibria in economies with bads. Econometrica 73 (2), 647–658. He, Y., Miralles, A., Pycia, M., Yan, J., 2018. A pseudo-market approach to assignment with priorities. Am. Econ. J. Microecon. 10 (3), 272–314. Hylland, A., Zeckhauser, R., 1979. The efficient allocation of individuals to positions. J. Polit. Econ. 87, 293–314. Kamada, Yuichiro, Kojima, Fuhito, 2015. Efficient matching under distributional constraints: theory and applications. Am. Econ. Rev. 105, 67–99. Makowski, L., Ostroy, J.M., Segal, U., 1999. Efficient incentive compatible economies are perfectly competitive. J. Econ. Theory 85, 169–225. Manelli, Alejandro M., 1991. Monotonic preferences and core equivalence. Econometrica 59 (1), 123–138. Manjunath, Vikram, 2014. Markets for Fractional Partnerships. Working Paper. Mas-Colell, Andreu, 1992. Equilibrium theory with possibly satiated preferences. In: Majumdar, Mukul (Ed.), Equilib- rium and Dynamics, Essays in Honor of David Gale. St. Martins’ Press, New York, pp. 201–213. Mas-Colell, A., Whinston, M.D., Green, J., 1995. Microeconomic Theory. Oxford University Press. Maskin, Eric S., Roberts, Kevin W.S., 2008. On the fundamental theorems of general equilibrium. Econ. Theory 35, 233–240. McLennan, Andrew, 2002. Ordinal efficiency and the polyhedral separating hyperplane theorem. J. Econ. Theory 105, 435–449. McLennan, Andrew, 2018. Efficient Disposal Equilibria of Pseudomarkets. Working Paper. Milgrom, Paul R., 2009. Assignment messages and exchanges. Am. Econ. J. Microecon. 1 (2), 95–113. Miralles, Antonio, 2008. School Choice: the Case for the Boston Mechanism. Working Paper. Miralles, Antonio, 2017. Ex-ante efficiency in assignments with seniority rights. Rev. Econ. Des. 21, 33–48. Miralles, Antonio, Pycia, Marek, 2015. Large vs. Continuum Assignment Economies. Working Paper. Miralles, Antonio, Pycia, Marek, 2017. Prices and Efficient Assignments Without Transfers. Online Appendix. Working Paper. Nguyen, T., Peivandi, A., Vohra, R., 2016. Assignment problems with complementarities. J. Econ. Theory 165, 209–241. Ostrovsky, Michael, 2008. Stability in supply chain networks. Am. Econ. Rev. 98 (3), 897–923. Pareto, Vilfredo, 1909. Manuel d’Economie Politique. M. Giard, Paris. Pycia, Marek, 2012. Stability and preference alignment in matching and coalition formation. Econometrica 80 (1), 323–362. Pycia, Marek, 2014. The Cost of Ordinality. Working Paper. Pycia, Marek, 2019. Evaluating with Statistics: Which Outcome Measures Differentiate Among Matching Mechanisms? Working Paper. Pycia, M., Unver, U., 2015. Decomposing random mechanisms. J. Math. Econ. 61, 21–33. Reny, Philip J., 2017. Assignment problems. J. Polit. Econ. 125 (6), 1903–1914. Richter, Michael, Rubinstein, Ariel, 2015. Back to fundamentals: equilibrium in abstract economies. Am. Econ. Rev. 105 (8), 2570–2594. Schlegel, Christoph Jan, Mamageishvili, Akaki, 2020. Welfare theorems for random assignments with priorities. Games Econ. Behav. 124, 62–81. Sonmez, Tayfun, Unver, Utku, 2010. Course bidding at business schools. Int. Econ. Rev. 51 (1), 99–123. 23 A. Miralles and M. Pycia Journal of Economic Theory 196 (2021) 105303 Sun, Ning, Yang, Zaifu, 2006. Equilibria and indivisibilities: Gross substitutes and complements. Econometrica 74, 1385–1402. Thomson, William, Zhou, Lin, 1993. Consistent solutions in atomless economies. Econometrica 61 (3), 575–587. Vazirani, Vijay V., Yannakakis, Mihalis, 2020. Computational Complexity of the Hylland-Zeckhauser Scheme for One- Sided Matching Markets. Working Paper. 24