Pseudomarkets with priorities in large random assignment economies

Pseudomarkets with Priorities in Large Random Assignment Economies Antonio Miralles Universitat Autonoma de Barcelona Barcelona Graduate School of Economics and European University Institute First version, May 2010. This version, March 2011. Abstract I study large random assignment economies with a continuum of agents and a …nite number of object types. I consider the existence of weak priorities discriminating among agents with respect to their rights concerning the …nal assignment. The respect for priorities ex ante (ex-ante stability) usually precludes ex-ante envy-freeness. Therefore I de…ne a new concept of fairness, called no unjusti…ed lower chances: priorities with respect to one object type cannot justify di¤erent achievable chances regarding another object type. This concept, which applies to the assignment mechanism rather than to the assignment itself, implies ex-ante envy-freeness among agents of the same priority type. I propose a variation of Hylland and Zeckhauser’s (1979) pseudomarket that meets ex-ante stability, no unjusti…ed lower chances and ex-ante e¢ ciency among agents of the same priority type. Assuming enough richness in preferences and priorities, the converse is also true: any random assignment with these properties could be achieved through an equilibrium in a pseudomarket with priorities. If priorities are acyclical (the ordering an[email protected]. I am grateful to Yeon-Koo Che, Piero Gottardi, Jordi Massó, Massimo Morelli and Fernando Vega-Redondo for previous comments and suggestions. For the same reason, I would also like to thank the attendants at seminars at the European University Institute, the University of Barcelona and the University of Siena. I also acknowledge the …nancial support provided by the Spanish Ministry of Science and Innovation (ECO2009-06946 and ECO2008-04756). 1 of agents is the same for each object type), this pseudomarket achieves ex-ante e¢ cient random assignments. Keywords: Random Assignment; Fairness; Stability; School Choice. 1 Introduction In 1979, Hylland and Zeckhauser proposed a pseudomarket mechanism that solved the ex-ante e¢ cient random assignment problem. This result could be compatible with ex-ante envy-freeness should the agents face identical budgets. From Thomson and Zhou (1993) it was understood that any ex-ante e¢ cient and envy-free random assignment could be obtained through a pseudomarket with identical budgets in large economies (continnum of agents). This paper constitutes an extension of pseudomarkets to environments where priorities, or agents’rights concerning the …nal assignment, exist that have to be respected. Concerns about justice and e¢ ciency arise in many assignment problems. Examples include the assignment of children to public schools, students to college residences, patients to public health care services, etc. In this paper, I consider the fact that the existence of priorities in many assignment problems precludes standard fairness desiderata such as the absence of ex-ante envy (i.e. no agent should prefer any other agent’s assignment probabilities to her own) from being achievable. Therefore I construct a weaker notion of fairness that is compatible with the respect for priorities. It is based on the idea that priorities with respect to one object type cannot justify di¤erences in chances with respect to another object type. I call it no unjusti…ed lower chances. I propose a variation of the pseudomarket mechanism à la Hylland and Zeckhauser (1979) that respects priorities while meeting the new fairness condition. Under acyclical priority structures, that is, when agents are equally priority-ordered with respect to every object type, this pseudomarket achieves ex-ante e¢ cient random assignments. The presence of priorities is a recurrent feature in assignment problems. An agent has priority over another agent with respect to an object type when a unit of this object type must be given to the former rather than the latter if both agents claim for the same unit. Examples of priorities are those given by the presence of a sibling at and living at walking distance from the school in children-to-school assignment problems, seniority and existing tenants in residence assignment and medical emergency in health care services. Respect for priorities is understood as the stability of any ex-post (or …nal) assignment. The term stability, from the marriage market literature (Gale and 2 Shapley, 1962), indicates that an agent with priority over another agent for some object type must obtain a unit of that object type or a preferred one in the case that the latter agent obtains a unit of that object. Since priorities could be regarded as privileges with regard to the …nal assignment, ex-ante envy-freeness cannot be guaranteed. The new concept of fairness I propose here, no unjusti…ed lower chances, a¤ects the assignment mechanism itself rather than the random assignment. It states that any agent should be able to obtain, if she wishes, at least the assignment probabilities of any other agent, ignoring those object types for which the latter has priority over the former. More formally, for each feasible random assignment, the assignment mechanism provides each agent with a menu of assignment probability vectors from which the agent freely chooses. According to the proposed concept, this menu should include any other agent’s assigned probabilities (or higher), ignoring the object types for which the latter has priority over the former. This concept implies ex-ante envy-freeness among agents of the same priority type (i.e. those who have equal priority levels for each object type). In this paper, I propose a pseudomarket with priorities, a variation of Hylland and Zeckhauser’s suggested mechanism where the prices each agent pays depending on her priority type. For each object type, the priority type of an agent can be summarized into one of the following three statuses: guaranteed, pivotal and banned. Guaranteed agents pay zero price, pivotal agents pay the market price and banned agents pay an in…nite price. A stable …nal assignment always arises from any equilibrium in a pseudomarket with priorities. Moreover, a pseudomarket with priorities guarantees no unjusti…ed lower chances. It also obtains ex-ante e¢ cient random assignments among agents of the same priority type. In some scenarios, priority orderings coincide across object types. That is, priorities are acyclical. Seniority rights in residence assignment, or low-income priorities in school choice, are examples of such a priority structure. In such cases, a pseudomarket with priorities can be understood as a sequential pseudomarket: those agents with the highest priority level attend the pseudomarket, buy their assignment probabilities and leave; then those with the second-highest priority level attend the pseudomarket for the remaining object units, and so on. A sequential pseudomarket obtains ex-ante e¢ cient random assignments. The reason is that the price discrimination is such that no agent of a higher priority type would have an incentive to trade with agents of lower types. Related literature and comments. The debate: Since the seminal paper by Abdulkadiro¼ glu and Sönmez (2003), there has been a lively debate on the relative value of the assignment mechanisms that are used in practice. Most 3 of the interest has been centered on school choice mechanisms (i.e. the assignment of children to public schools), and more speci…cally on the comparison between strategy-proof mechanisms (with truth-telling as weakly dominant strategy) such as Deferred Acceptance and non-strategyproof mechanisms such as the Boston Mechanism.1The strategic simplicity of Deferred Acceptance inspires both a justice argument (protection of naïve agents, see Abdulkadiro¼ glu, Pathak, Roth and Sömez, 2006, and Pathak and Sönmez, 2008) and also an e¢ ciency argument (avoiding coordination failures, see Ergin and Sönmez, 2006) against non-strategy-proof mechanisms.2However, strategyproofness may come at too high a cost in terms of ex-ante e¢ ciency, as evidenced in Abdulkadiro¼ glu, Che and Yasuda (2008), Miralles (2008) and Abdulkadiro¼ glu, Che and Yasuda (2009). Some nonstrategy-proof mechanisms such as the Boston Mechanism and related mechanisms achieve better qualitative ex-ante e¢ ciency results because they impose some market (or trade-o¤) incentives. Inspired by this idea, I consider here how we can combine market incentives with respect for priorities. Justice and e¢ ciency: The main recent reference is the survey by Thomson (2007). For large economies with a continuum of agents, Varian (1976) and Zhou (1992) provide general results relating fairness and e¢ ciency to Walrasian markets with equal endowments. Varian assumes strictly concave preferences and Zhou analyzes strictly positive consumption sets. Both authors conclude that the set of fair allocations coincides with the set of allocations arising from Walrasian market equilibria with equal endowments. The no-envy requirement is one of several concepts of justice that one could use. Egalitarian equivalence (Pazner and Schmeidler, 1978), that is, everyone’s indi¤erence to some (not necessarily feasible) equal split allocation, could alternatively have been chosen among other concepts. Thomson and Zhou (1993) give a wide result on that subject: all egalitarian (with respect to equal split), consistent (i.e. holding for any subset of agents) and e¢ cient allocations are obtained by Walrasian markets with equal endowments, even if preferences are satiated. I easily extend that result to the kind of assignment problems I analyze. Assignment probabilities are the goods in this economy. The fact that probabilities must add up to one could be modeled as a case of satiation. In this 1Both mechanisms are ranking mechanisms in that parents (the agents) are …rst requested to submit a ranking over the schools (the object types). The assignment algorithm uses the provided information in several rounds. In the …rst round, students are considered for the schools parents ranked …rst. In schools with excess demand some students are rejected (following priority criteria and tie-breaking lotteries) and go to the next round, where they are considered for the schools that were ranked in second position. Accepted students are de…nitely accepted in the Boston Mechanism, whereas in Deferred Acceptance they are only reconsidered for that school in the next round. The algorithms likewise follow a …nite number of rounds until all students are …nally accepted at some school. 2For these reasons, the Boston Mechanism was replaced by Deferred Acceptance in Boston (!). 4 economy, ex-ante envy-freeness is equivalent to consistency and egalitarian equivalence with respect to equal split. Thus, among agents of the same priority type, ex-ante envy-freeness and e¢ ciency are obtained through a Walrasian market with equal endowment and priority-dependent prices. The pseudomarket with priorities I propose meets these properties. Ex ante and ex post: The importance of ex-ante e¢ ciency (in which random assignments are compared to each other) compared to ex-post e¢ ciency (where …nal assignments are compared) is stressed when priorities are rather coarse, that is, when massive sets of agents belong to the same priority type. An example is the case of elementary school choice in Boston, where there are only four priority categories (combining sibling and walking zone priorities) for more than one thousand new entrants a year. Priority ties are typically solved by some sort of lottery and thus we talk about random assignments when this uncertainty has not yet been resolved. In this context, exante e¢ ciency is a re…nement of ex-post e¢ ciency. Since any feasible random assignment could be understood as a lottery over feasible sure assignments, it is easy to see that no ex-post e¢ ciency implies no ex-ante e¢ ciency. The converse is not true. An example is the mechanism known as random serial dictatorship, in which agents are strictly ranked according to an even lottery, and then the top-ranked agent picks a unit from her most-preferred object type, the second-ranked agent picks among the available units, and so on. This mechanism always obtains ex-post e¢ cient assignments. However, it can be shown that it is ex-ante ine¢ cient (see for instance Bogomolnaia and Moulin, 2001). Ex-ante envy-freeness is however a weaker concept than ex-post envy-freeness. In e¤ect, a random assignment could be ex-ante, yet not ex-post, envy-free, whereas the absence of ex-post envy implies its absence ex ante. However, the concept of ex-post envy-freeness is so tight that it could either be unattainable or yield non-sensible assignments. For instance, if an object type is popular (i.e. the number of agents who prefer it over every other object type exceeds the number of units of this type), then ex-post envy-freeness implies that no unit of that object type could be assigned to any agent who prefers it. In a similar way, the concept of no unjusti…ed lower chances makes sense only when applied to assignment probabilities. In conclusion, the ex-ante approach to e¢ ciency and no envy seems recommendable, and this motivates my focus on random assignments. Priorities and fairness: In several cases, priority structures are designed to provide agents with a chance to prove the intensity of their preferences. In school choice, having a sibling at the school and living nearby is positively correlated with the parents’preference for the school, and this justi…es giving priority on the basis of these variables for the sake of a more e¢ cient allocation. 5 Similarly, previous tenants may have a preference for staying where they are, concerning residence allocation. Nevertheless, in many other cases priorities arise for other reasons. As an example, the San Francisco school authority gives priority to those applicants who "depart more" from the average pool with respect to some socioeconomic indicators, in order to lessen the concentration of minority students in a few schools. My results in this paper indicate that when priorities are single-ordered (e.g. seniority rights), it is possible to obtain a random assignment satisfying ex-post stability, no unjusti…ed lower chances and ex-ante e¢ ciency. In the literature on ex-post assignments (e.g. Ergin, 2002), single-ordered priority rules or similar requirements (e.g. "one step away from single ordering") are also needed to satisfy justice and e¢ ciency properties. More centrally related to the present paper is the recent work by Kesten and Ünver (2010). Acknowledging the need to respect priorities, they conceive a weak notion of fairness which they call no ex-ante discrimination. There is ex-ante discrimination of an agent with respect to another agent and a certain object type if: 1) both agents are at the same priority level concerning that object type, 2) the former agent obtains lower chances than the latter to be assigned an unit of that object type, and 3) the former agent has positive probability to be assigned an unit of an object type that is less preferred to the previous object type. It is a sound concept of fairness in that agents with same priority level for some object type should have the same chances with respect to that object type unless there is "enough" compensation. Moreover, it implies ex-ante envy-freeness among agents of the same priority type. Based on that concept, the authors propose a modi…cation of the Deferred Acceptance algorithm that meets ex-ante stability and no ex-ante discrimination while Pareto-dominating all other assignments meeting the same conditions. Nevertheless, the concept of no ex-ante discrimination is not exempt of discussion. A …rst point is, what they understand as "enough compensation" (not being possibly assigned a worst object type) is not the only way to conceive it. For instance, "enough compensation" could just mean that the probability of being assigned to the considered object type or a preferred one should not be less that the probability that the other agent has to be assigned to that object type. A second point is that this concept of justice could come at a high price in terms of (ex-ante) e¢ ciency. Consider the extreme case where there is only one priority level for all schools, that is, the no-priority case. In such an environment, and with a continuum of agents, any ex-ante envyfree and e¢ cient random assignment is obtained through a pseudomarket with equal budgets (once again citing Thomson and Zhou, 1993). However, no ex-ante discrimination is tighter than no ex-ante envy, thus in many cases the pseudomarket assignments are precluded and ex-ante e¢ ciency is not 6 achievable. A simple example contains three object types a; b; c with equilibrium prices 3=2;1=2;0 respectively. Agents have unit budgets. Depending on preferences, some agents would buy 2=3 probability at aand 1=3at c, and some others would buy 1=2probability at aand 1=2at b. The latter agents prefer ato b, otherwise buying sure assignment at bwould have been a better option. Consequently, the latter agents would be ex-ante discriminated with respect to the former agents and object type a. The alternative notion of fairness proposed here, no unjusti…ed lower chances, is intead compatible with these pseudomarkets. Priorities and property rights: A last observation concerning the presence of priorities is the fact that they could be considered as externalities. It could then be conceivable, à la Coase, to convert the priorities into property rights and to let then the agents trade them (Abdulkadiro¼ glu and Sönmez, 2003). However, apart from legal issues (this procedure does not guarantee ex-post stability, and unstable assignments have been legaly disputed), other theoretical concerns arise here. First of all is the question on how priorities are converted into property rights, that is, into probability endowments that agents trade. Even thoguh a satisfactory answer is possible, a second concern arises when assignment probabilities are traded instead of bought using "fake" monetary income. Hylland and Zeckhauser (1979) have argued that a pseudomarket equilibrium may not exist if agents trade probability endowments. Key in their argument is the fact that each agent ends up with a probability bundle that must add up to one. As an example, consider an environment with two object types aand bwhere a set of agents who prefer ato bare given an endowment of a sure assignment (probability 1) to b. As long as the price of blies below the price of a, these agents cannot trade probabilities of bfor probabilities of a(demanded probabilities would not add up to one). As soon as the prices equal each other, however, these agents trade all their endowment for a sure assignment at a. This generates an hemi-discontinuity in aggregrate demand, thus Kakutani’s …xed-point theorem may not apply. The example could be easily extended to scenarios with more than two object types. The paper is structured as follows. The second section presents the assignment problem with and without priorities, and the concepts of justice and e¢ ciency are brought into play. The third section introduces and analyzes an extended version of Hylland and Zeckhauser’s (1979) pseudomarkets. The fourth section presents the results and discussion. The last section concludes. 7 2 The (random) assignment problem There is a …nite set Sof J > 2object types S=f1; :::; Jg. For simplicity I assume that there is no outside option.3Each object type jhas capacity mass j>0. The total sum of capacities across object types is at least 1. Let ~ = (1; :::; J). There is a mass 1 of agents x2X[0;1] where Xis the set of agents endowed with the Lebesgue (uniform) measure . There is a measurable von Neumann-Morgenstein (vNM) valuation function v:X!VRJ +, where v(x)=(v1(x); :::; vJ(x)) denotes agent x’s valuations for object types 1 to J. Each agent is indi¤erent between any two units of the same object type. The function is assumed to have a range that intersects with any positive ray from the origin (i.e. all relative preferences belong to the image). It is also assumed that (fx2X:v(x)2V0g) = 0 whenever dim(V0)<dim(V).4 Arandom assignment is a measurable function q:X!(S), where q(x)=(q1(x); :::; qJ(x)) denotes agent x’s assignment chances for object types 1 to J. A random assignment qis feasible at (v;~)if RXq(x)d ~. An (ex-post or …nal)assignment is a measurable function a:X!S. Let A be the family of all feasible …nal assignments (i.e. the mass of agents who are assigned to each object type jdoes not exceed j). By the Birkho¤- von Neumann theorem, any feasible random assignment can be implemented as a (not necessarily unique) lottery l2(A)over feasible assignments. In some results, we select lsuch that it puts positive weight only on those …nal assignments awhose assignment frequencies coincide with the random assignment probabilities: 8X0X; (X0)>0; RX0a(x)d =RX0q(x)d. This is regarded as the frequency-probability condition. Let Fdenote the set of all feasible random assignments (which obviously depends on ~). Each agent x’s expected payo¤ from the random assignment qis equal to q(x)v(x). A feasible random assignment is ex-post e¢ cient at (v;~)if it can be implemented as a lottery over Paretooptimal assignments. That is, for any possible lottery outcome, the resulting assignment is Paretooptimal. A feasible random assignment is ex-ante e¢ cient at (v;~)if there is no other feasible random assignment at (v;~)that provides each agent with a weakly higher expected payo¤ and a positive-measure set of agents obtains a strictly higher payo¤. Ex-ante e¢ ciency implies ex-post e¢ ciency, but the converse may not be true. The concept could be extended to groups: for instance, qis ex-ante e¢ cient within X0Xif there is no feasible reassignment a¤ecting only agents in X0 such that there is a Pareto-improvement. A random assignment qis ex-ante envy-free if for any x; y 2X; q(x)v(x)q(y)v(x). An 3The results presented here could easily be extended to include that option. 4I am abusing notation: the dimension of a set is in reality taken with respect to the closure of its interior. 8 assignment is envy-free if for any x; y 2X; va(x)(x)va(y)(x). A random assignment is ex-post envy free if for any lottery outcome, any …nal assignment is envy-free. Ex-post envy-freeness implies exante envy-freeness. However, it is easy to see that ex-post absence of envy is too a harsh condition. For any set of agents preferring the same object, either none or all of them have to be assigned to that object type. A within-groups version of the envy-freeness de…nition could also apply here. Apriority structure is a function P:X!Yj2Sf0; :::; Gjg, where P(x) = (P1(x); :::; PJ(x)) denotes agent x’s priority type with respect to object types 1 to J, and Gj2Nis arbitrarily large. We say that agent xhas priority over agent ywith respect to object type jif Pj(x)> Pj(y). The triple (v;~; P)de…nes the economy. Let 2denote a generic priority type, = (1; :::; J), and let Xbe the set of agents of priority type . In some result we will use the following assumption: De…nition 1 The priority structure Psatis…es the priority-bridge condition if for any pair ; 02 ; (X); (X0)>0;and for any triple i; j; k 2Ssuch that i> 0 i; j=0 jand k< 0 k;there exists 00 2; (X00 )>0;such that i=00 i; j=0 j=00 jand 0 k=00 k. So if two priority types are tied with respect to some object type, and one priority type has higher priority with respect to a second object type while the other priority type has higher priority with respect to a third object type, then there is a "bridge" priority type which has the highest priority of the two in both three object types. The priority structure is required to be rich in that sense. A particular case of a priority structure satisfying the priority-bridge condition would be the join-semilattice structure: for any pair ; 02; (X); (X0)>0;we have (X_0)>0. Furthermore, we will impose an assumption on the preference pro…le in some of the results. In words, the assumption states that all preferences are possible regardless the priority type. De…nition 2 The economy (v;~; P)satis…es the preference-richness condition if for any 2 such that (X)>0;we have v(X) = V. We say that an assignment ais stable (or it respects priorities) given Pif 8x; y 2X; Pj(x)> Pj(y) and a(y) = j=)va(x)(x)vj(x). A random assignment is ex-post stable if it can be de…ned as a lottery l2(A)whose support is constituted by stable assignments. Following Kesten and Ünver (2010), a random assignment qis de…ned as ex-ante stable given Pif and only if 8x; y 2X; fPj(x)> Pj(y)and qj(y)>0g=) fqi(x)=08i2S:vi(x)< vj(x)g. That is, if agent xhas priority over agent ywith respect to object type jand yobtains chances of being assigned to j, then xcannot be possibly assigned to an object type that is less preferred than j. Ex-ante stability implies ex-post stability. For the converse, the frequency-probability condition is needed. 9 In the next two paragraphs, I show that for any school j2Sand any two priority types ; 02Xsuch that j=0 j, we must have (WLOG) pj() = pj(0). Let us suppose pj()> pj(0). If pj()>1, some agent x2Xthat prefers jto any other object type will be able to buy less assignment probability at jthan some agent y2X0who optimally chooses to spend her budget on jand completes her bundle with w(the "worst" object type, with zero price). This violates no unjusti…ed lower chances. If pj()1, I consider several cases. First, if either xor y(or both) is facing prices that are either not higher than 1 or 1, then these not-above-one prices could be normalized making pj() = pj(0)with no alteration of the budget set (WLOG). Second, if there is another object type h:h=0 h,ph() = ph(0)>1, (we must have ph() = ph(0)as seen before in the case pj()>1) then pj()> pj(0)implies, under the preference-richness assumption, that some agent y2X0optimally buys a bundle with 1pj(0) ph()pj(0)>1pj() ph()pj()probability units of being assigned at hand the remaining probability at j. This bundle does not belong to the budget set of agents in X, hence violating no unjusti…ed lower chances. Thus I consider a last set of scenarios where j=0 jand 9i; k 2SnE0:1> pi()>1; 1> pk(0)>1, where E0 fh2S:0 h=hg. Here I use the priority-bridge condition imbedded in the richness condition. There is a priority type 00 such that i; j 2E00  fh2S:00 h=hg and j; k 2E000  fh2S:0 h=00 hgwith a positive mass of agents of that type. By the previous paragraph we must have both pj(00) = pj(0)and pj(00) = pj(0), contradicting pj()> pj(0). The necessity argument is also seen here: if there were no such a 00, there would be a preference pro…le vsuch that a vector of equilibrium prices exists satis…ng pj()> pj(0)(while all the stated properties are met). A second question here is whether the frequency-probability condition is relevant. This condition provides some structure to ex-post assignments. It has to be said, though, that this condition reduces the set of ex-ante assignments that are ex-post stable under a propery designed lottery over …nal assignments. Consider the following example with three object types a; b; c where a(with capacity 1/2) is preferred to b(with capacity 1/4) and bto c(with capacity 1/4) by every agent. There is a measure 1/2 of agents of priority type and another measure 1/2 of agents of priority type 0. The only di¤erence between and 0is that those agents of type have priority over those of type 0with respect to object type b. Consider a random assignment in which all agents obtain the same assignment probabilities 1/2,1/4,1/4 for a; b and crespectively. According to the frequencyprobability condition, this random assignment is not ex-post stable. However, consider an ex-post implementation where with probability 1/2, all agents of type are assigned to aand the other agents 16 are randomly split between band c, and with probability 1/2 all agents of type 0are assigned to awhereas those of type are randomly split between band c. All the ex-post assignments here are stable. The example could be slightly modi…ed to acommodate the richness assumption. This suggests that a relaxation of the frequency-probability condition could enrich the analysis of ex-post stable random assignments. 4.2 Acyclical priorities Consider a speci…c priority structure Psuch that for any x; y 2X; i; j 2S; Pi(x)> Pi(y),Pj(x)> Pj(y). This would be regarded as acyclical priorities, since there is a unique ordering among agents that applies to all object types. One example in real scenarios could be the assignment of college students to residences, where seniority may give priority. In these cases, I could then generally talk about top-ranked agents, second-ranked agents and so on, with no mention of object types. Let us de…ne a sequential pseudomarket in the following way: …rst, top-ranked agents attend a pseudomarket with equal budgets, buy their assignment probabilities at equilibrium prices and leave; then, second-ranked agents attend a pseudomarket with equal budgets for the remaining object units; and so on. It is easy to see that the sequential pseudomarket is equivalent to the more general pseudomarket with priorities when these are acyclical. Theorem 3 Fix an acyclical priority structure P. Under the frequency-probability condition, a sequential pseudomarket guarantees stability and obtains ex-ante e¢ cient random assignments. Proof. Let 0, and consider any x2Xand any y2X0. Consider any object type jfrom which ybuys assignment probabilities in the market equilibrium. Then it must be the case that pj(x) = 0, since that object type was necessarily oversupplied for ranked agents. This guarantees ex-post stability, since xwill optimally buy assignment probabilities from object types that are at least as preferred as j. Since ex-ante e¢ ciency is guaranteed among agents of the same priority type, potentially mutually bene…cial trade could only arise between priority groups. Once again, however, no set of agents x2Xcould have an interest in trading with any set of agents y2X0. All object types from which any such ybuys are (weakly) less preferred for xthan the object types from which xbuys, since xis facing a zero price for the former goods. Note that any trade has to keep every agent with assignment probabilities adding up to one. Notice here that we have not mentioned the fairness condition proposed in this paper, no unjusti…ed lower chances. It turns out that this property is not informative here, since it holds only 17 trivially. In fact, for  > 0, this property just implies that agents in 0obtain a non-negative assignment probability vector in the menu o¤ered, which is the budget set. 5 Conclusion In this paper, I have analyzed large random assignment economies with a continuum of agents and a …nite number of object types. I have introduced the realistic assumption that some priority criteria might alter the symmetry of agents in their rights regarding the …nal assignment. Without these priorities, ex-ante e¢ ciency and envy-freeness is characterized by the equilibrium outcomes from a pseudomarket with equal budgets, à la Hylland and Zeckhauser (1979), as pointed out by Thomson and Zhou (1993). In a pseudomarket, each agent is endowed with a …ctitious budget that allows her to buy assignment probabilities, where each object type has its own price. In this paper, I have proposed an extension of this pseudomarket mechanism that takes the existence of priorities into account. For each object type, there is a priority level that is pivotal, that is, agents at that level pay the market price. Agents at a higher priority level (guaranteed) pay zero price, and those at lower levels (banned) pay in…nite price. Once priorities are considered, ex-ante envy-freeness is typically not achievable. I have alternatively searched for a notion of "maximal fairness" subject to respect for priorities. I have based this notion on the fact that priorities regarding one object type cannot justify any privileges concerning another object type, and I have named the observation of this desideratum no unjusti…ed lower chances. This property implies ex-ante envy freeness among agents of the same priority type. It states that, for any feasible random assignment, each agent must be o¤ered a menu of assignment probability vectors such that each other agent’s assignment probabilities (or higher) are included in that menu, ignoring the objects for which the latter agent has priority over the former. It will be noticed that this fairness condition not only a¤ects random assignment but also the process (the mechanism) generating it. The menu is a reduced form of the assignment probabilities that the agent can obtain given her strategy space and the other agents’strategy pro…le. In general scenarios where I do not impose any structure on priorities, I show that a pseudomarket with priorities respects priorities (it is ex-post stable), guarantees no unjusti…ed lower chances and obtains ex-ante e¢ cient allocations among agents of the same priority type. Assuming enough richness in preferences and priorities, the converse is also true: any random assignment with these properties could be achieved through an equilibrium in a pseudomarket with priorities. If priorities 18 are constrained to be acyclical, that is, the ranking of agents’priority levels does not vary across object types, then the pseudomarket with priorities can be implemented via a sequential pseudomarket. In such a mechanism, agents with the highest priority level attend the pseudomarket, buy their assignment probabilities and leave. Agents at the second-highest priority level attend the pseudomarket for the remaining slots and leave. And so on. This sequential pseudomarket obtains in equilibrium overall ex-ante e¢ cient random assignments, since agents from a higher priority type would never have an incentive to trade their assigned probabilities with agents in lower priority levels. There are several other interesting features in assignment problems that have been skipped here in order to obtain more concise results. Among them, the …niteness of the number of agents, and the presence of peer-group e¤ects on agents’preferences. The …rst element is often found in the theoretical literature. Following Hylland and Zeckhauser’s (1979) seminal work, the results found in the present paper do not substantially di¤er from what we could expect in environments with su¢ ciently many agents per object type. However, interesting departures from competitive market behavior deserve more careful analysis, when the number of agents per object type is low enough. For instance, in the children-to-school assignment problem, is the reasonable 25-30 new students per school and year ratio su¢ ciently high? The answer will come from empirical evidence. The second element I mention is specially interesting in that it has not received proper attention from the theoretical literature despite the empirical evidence. It could be argued that a model that incorporates peer-group e¤ects adds much more complexity to already cumbersome problems. However, further inclusion of this feature is relevant since it may a¤ect what we know from the mechanism I suggest in this paper and other mechanisms that have been suggested in the literature. References [1] Abdulkadiro¼ glu A., Che Y. and Yasuda Y. (2008) Expanding "Choice" in School Choice, unpublished manuscript. [2] Abdulkadiro¼ glu A., Che Y. and Yasuda Y. (2009) “Resolving Con‡icting Preferences in School Choice: The ‘Boston’Mechanism Reconsidered”, forthcoming in American Economic Review. [3] Abdulkadiro¼ glu A., Pathak P.A., Roth A.E. and Sönmez T. (2006) Changing the Boston School Choice Mechanism: Strategy-proofness as Equal Access, unpublished manuscript. 19 [4] Abdulkadiro¼ glu A. and Sönmez T. (2003) "School Choice, a Mechanism Design Approach", American Economic Review 93, 729-747. [5] Bogomolnaia A. and Moulin H. (2001) "A New Solution to the Random Assignment Problem", Journal of Economic Theory 100, 295-328. [6] Ergin H. (2002) “E¢ cient Resource Allocation on the Basis of Priorities,” Econometrica 70, 2489-2497. [7] Ergin H. and Sönmez T. (2006) "Games of School Choice under the Boston Mechanism", Journal of Public Economics 90, 215-237. [8] Gale D. and Shapley L.S. (1962) "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14. [9] Hylland A. and Zeckhauser R. (1979) "The E¢ cient Allocation of Individuals to Positions", Journal of Political Economy 87, 293-314. [10] Kesten O. and Ünver M.U. (2010) A Theory of School-Choice Lotteries, unpublished manuscript. [11] Mas-Colell A. (1984) "On a Theorem of Schmeidler", Journal of Mathematical Economics 13, 201-206. [12] Miralles A. (2008) School Choice: the Case for the Boston Mechanism, unpublished manuscript. [13] Pathak P. and Sönmez T. (2008) "Leveling the Playing Field: Sincere and Sophisticated Players in the Boston Mechanism", American Economic Review 98, 1636-52. [14] Pazner E.A. and Schmeidler D. (1978), “Egalitarian equivalent allocations: A new concept of economic equity”, Quarterly Journal of Economics 92, 671–687. [15] Thomson W. (2007) Fair Allocation Rules, unpublished manuscript. [16] Thomson W. and Zhou L. (1993) “Consistent allocation rules in atomless economies”, Econometrica 61, 575-587. [17] Varian H.R. (1976) "Two problems in the theory of fairness", Journal of Public Economics 5, 249-260. [18] Zhou L. (1992) "Strictly fair allocations in large exchange economies", Journal of Economic Theory 57, 158-175. 20