## Random Matching under Dichotomous Preferences

by
Anna Bogomolnaia, Herve Moulin

Citation

Title:

Random Matching under Dichotomous Preferences

Author:

Anna Bogomolnaia, Herve Moulin

Year:

2004

Publication:

Econometrica

Volume:

72

Issue:

1

Start Page:

257

End Page:

279

Publisher:

Language:

English

URL:

Select license:

Select License

DOI:

PMID:

ISSN:

**Updated:**November 25th, 2012

Abstract:

RANDOM MATCHING UNDER DICHOTOMOUS PREFERENCES

BYANNABOGOMOLNAIA MOULIN'

AND HERVE

We consider bilateral matching problems where each person views those on the other side of the market as either acceptable or unacceptable: an acceptable mate is preferred to remaining single, and the latter to an unacceptable mate: all acceptable mates are welfare-wise identical.

Using randomization, many efficient and fair matching methods define strategyproof revelation mechanisms. Randomly selecting a priority ordering of the participants is a simple example. Equalizing as much as possible the probability of getting an acceptable mate across all participants stands out for its normative and incentives properties: the profile of probabilities is Lorenz dominant, and the revelation mechanism is group- strategyproof for each side of the market.

Our results apply to the random assignment problem as well.

KEYWORDS:Matching, randomization. strategyproofness, dichotomous preferences.

1. INTRODUCTION

THE BILATERAL MATCHING PROBLEM occupies a special place in the mech- anism design literature, combining strong empirical relevance and an interesting mathematical structure (see Roth and Sotomayor (1990)). The celebrated Gale-Shapley algorithm selects an efficient matching with strong incentive properties: it is stable in the sense of the core, and strategyproof with respect to the side of the market actively proposing to the other side (though not with respect to the passive side).

We consider the important special case of the bilateral matching problem where each man (resp. woman) evaluates each woman (resp. man) as accept- able or unacceptable: being matched with an acceptable (resp, unacceptable) mate is better (resp. worse) than remaining single, and acceptable mates yield the same welfare. Abusing language slightly, we speak of dichotomous pref- erences, to capture the idea that the preferences of an individual are entirely described by the subset of his or her acceptable mates.'

For convenience we use the marriage terminology, but we have in mind other kinds of matching than sharing a life-for which a single binary criterion is an utterly insufficient model! Examples relevant to our model include matching managers to support staff, when a staff person is acceptable to a manager if and

'We are grateful to seminar and conference participants in the Universite de Paris, Seoul Na- tional University. the State University of New York at Stony Brook. and Michigan State Uni- versity. The detailed comments of three referees and the Editor have been especially helpful. Moulin's research is supported by the NSF under Grant SES-0112032.

'Yet individual's preferences have three indifference classes corresponding to being matched with an acceptable mate. or an unacceptable one, or remaining single. Note that preferences among unacceptable mates do not matter, as we only consider voluntary (individually rational) matchings.

A. BOGOMOLNAIA AND H. MOULIN

only if he has certain skills, and a manager is acceptable to a staff person if and only if she is not requesting "hard" tasks; or matching professors to research assistants, pilots to copilots, nurses to doctors, and so on. Time sharing is the simplest way to deal fairly with the indivisibilities of matching markets: think of a set of workers sharing their time among a set of employers (Baiou and Balinski (2002), Alkan and Gale (2001)). In our model randomization over matchings is formally equivalent to time-sharing, and to fix ideas we use the former terminology.

When one side of the market finds all agents on the other side acceptable, we can think of these agents as passive objects and speak of an assignment problem, an interesting special case of our general model.

Dichotomous preferences are equally natural in the assignment problems. Think of housemates distributing single rooms, when a "good" room may be one with a private bath for some agent, one with a private phone for another agent, and so on; another example is the assignment of softwares to workers when a given software can be compatible or not with a worker's own machine; or the scheduling of a list of jobs by a single server among a given set of time- slots: each customer requesting one job finds only certain time-slots acceptable (e.g., the job is useless after next Tuesday, or can only be done on weekends, and so on).

The dichotomous domain is much smaller in size than-yet not contained in-the strict preferences domain. The first simplification is that a (determin- istic or random) matching is core stable if and only if it is efficient and voluntary (no one is matched to an unacceptable partner). Among voluntary matchings, the efficient ones are the (inclusion) maximal ones, and in all maximal match- ings the number of matched men (or women) is the same. We call this number e the efficiency size of the matching problem.'

For a randomized matching we use the probability of an acceptable match as the canonical utility representation. Then a voluntary random matching is efficient if and only if its total utility is e, namely with probability one it matches e women to e men. In particular, the notions of ex ante and ex post efficiency coincide.

The Gallai-Edmonds decomposition of bipartite graphs, a well-known re- sult in graph theory, gives further details on the structure of core-stable de- terministic matchings. There is a set of Md of disposable men competing for the set WOof overdemanded women: all o~!erdemandedwomen are matched to a strict subset of disposable men. There is similarly a set W%f disposable women competing for the set M0 of overdemanded men. And the remaining men (in M\M0 U Md) can be perfectly matched to the remaining women (in W\W" U W"). This bipartition of M and W is unique for each profile of di- chotomous preferences: see Section 3.

'Interestingly a similar result holds in the strict preference domain: the set of men and women matched is the same in any core stable matching (Theorem 2.22 in Rot11 and Sotomayor (1990)).

The particularly simple structure of the core in our model makes it easy to achieve at the same time the three enduring goals of mechanism design, i.e., efficiency, incentive-compatibility (interpreted here as strategyproofness), and fairness.

The simplest example uses the familiar idea of selecting randomly, and with uniform probability, a priority ordering of the participants. We call it the random priority solution. For any fixed ordering of the set of men and women, the corresponding lexicographic maximization of utilities over voluntary matchings yields an efficient deterministic matching (unique utility-wise): this matching method is clearly strategyproof. When we randomize with fixed probabilities over all orderings of the set of agents, strategyproofness is preserved, and so is efficiency. The former statement does not depend upon the assumption of dichotomous preferences, the latter one does.

Recall that in the classical domain of strict preferences, strategyproofness for both men and women is incompatible with core stability (Roth (1982)). Our main results (Theorems 1and 2) show that in the dichotomous domain, we can achieve much more than strategyproofness on both sides of the market. To this end, we introduce a natural randomized solution of our matching problem that stands out for its normative and incentive properties.

The egalitarian solution equalizes as much as possible the individual prob- abilities of being matched. We show that the corresponding profile of utili- ties first-order stochastically dominates any other feasible profile of utilities arranged increasingly, a property known as Lorenz-dominance. Thus the egal- itarian solution uniquely maximizes any additively separable strictly concave collective utility function, for instance, the Nash collective utility function. It also admits a competitive interpretation and is easily computed: Theorem 1.

On the incentive front, the egalitarian solution is no less remarkable, as it is robust against potential manipulations by any all-male or all-female coalition: Theorem 2. We call this property group-strategyproofness with respect to one side of the market.

We do not provide an axiomatic characterization of the egalitarian solution. We state instead two results showing that this solution reaches the possibility frontier. First, no deterministic core-stable solution is group-strategyproofwith respect to every all-male coalition, or to every all-female coalition: Lemma 5. This result stands in contrast to the situation in the classical domain of strict preferences, where the Gale-Shapley algorithm delivers a deterministic so- lution that is group-strategyproof with respect to one side of the market. In the dichotomous domain, randomization is essential to achieve group- strategyproofness and core stability; on the other hand we can guarantee group-strategyproofness with respect to both sides of the market.

When we allow for manipulations by coalitions mixing some men and some women, strong impossibility results obtain. No core-stable solution treating equals equally is even weakly group-strategyproof; the same is true of any so- lution selecting a utility profile without specifying the probabilistic matching to implement it: Theorem 3.

A. BOGOMOLNAIA AND H. MOULlN

The paper is organized as follows. After a review of the small related liter- ature in Section 2, the model is defined in Section 3. Efficient voluntary (i.e., core-stable) matching, deterministic as well as random, are characterized in Section 4. The egalitarian solution is defined and characterized in Section 5. Strategyproofness and group-strategyproofness are the subject of Section 6. Section 7 gathers some concluding comments. All proofs are in the Appendix.

2. RELATION TO THE LITERATURE

The economic theory of bilateral matching under strict preferences- surveyed in the classic book by Roth and Sotomayor (1990)-does not address fairness by randomization, but examines in great detail strategyproofness and core stability.

The small literature on random assignment under strict preferences is very relevant to our work. Hylland and Zeckhauser (1979) defined a fair and effi- cient solution, adapting to the random assignment problem the familiar com- petitive equilibrium with equal incomes. Yet this competitive solution is not incentive ~ompatible.~

Our results show that, on the contrary, in the dichoto- mous domain the randomizationltime-sharing approach succesfully achieves efficiency, incentive compatibility. and fairness. And the egalitarian solution that we recommend is precisely equal income competitive (Theorem 1).

A recent flurry of papers on the deterministic assignment of indivisible goods bears some relation to our work. The central question of that literature is to characterize the set of efficient and incentive compatible (strategyproof) as- signment mechanisms: Papai (2000), Ehlers and Klaus (2000). Ehlers. Klaus, and Papai (2000). Most papers work in the strict preference domain, but three exceptions are Svensson (1994, 1999) and Bogomolnaia, Ehler~ and Deb (2000). These authors consider the deterministic assignment in the full do- main of complete and transitive preference relations, allowilig for strict and for dichotomous preferences. Fixed priority mechanisms are strategyproof and nonbossy. Conversely, these two properties force the mechaliism to resemble closely a fixed priority one; the additional property of neutrality captures pre- cisely the fixed priority mechanisms.

Finally our egalitarian solution is closely related to the solution with the same name for supermodular cooperative games. due to Dutta and Ray (1989). We can interpret our solution as the egalitarian solution of a certain coopera- tive game derived from the matching problem (Section 5).

'Zhou (1990) establishes the general impossibility of achieving ex ante efficiency (when prefer- ences over lotteries are described by von Neumann-Morgenstern utilities). fairness (in the mini- mal sense of equal treatment of equals). and strategproofness.

3. THE MODEL

A matching problem consists of a finite set M of "men," a finite set W of "women," and two M x W zero-one matrices RM and RW, representing di- chotomous preferences of men over women and of women over men, respec- tively. An entry RM,,,, = 1if woman w is acceptable for man m, and RM,,,, = 0 if she is not acceptable for him (and similarly for RW). Thus, each row RM,, of RM represents the preferences of a man m, and each column RW" of RW represents the preferences of a woman w.

Each person prefers to be matched to an acceptable person of the opposite gender to being unmatched, but would rather be alone than matched to an unacceptable person.

We assume throughout the paper that matching is voluntary, namely two individuals can be matched only if they like each other. We refer to this im- portant assumption as the individual rationaliy restriction. It implies that all the information about feasible matchings and relevant preferences is conveyed by a single M x W zero-one matrix R, equal to the entry by entry product of RM and RW: R ,,,, = 1 if and only if RM,,,, = 1 and RW,,,,, = 1, i.e., if and only if man m and woman w are mutually acceptable (we then say that they are "compatible"). We call the triple (M, W, R) the individually rational (ir) reduced problem of the problem (M, W, RM, RW).

Thus we work most of the time with the ir-reduced model (M, W, R). The only exception is Section 6 devoted to strategic behavior: there the matching mechanism computes the ir-reduced problem from the reported preferences RM and RW.

As this will cause no confusion, we use the notation R,,, (resp. R") both for the row (resp, the column) of R and for the subset of women (resp. men) who are compatible with man m (resp. woman w). For any subset S of men (resp. subset B ofwomen)-also called a coalition-we write R5 = U, R,,, (resp. RB = U, RIL) for the set of people of the opposite gender, compatible with at least one person in S (resp. B).

When all agents on one side of the market find all agents on the other side acceptable, we speak of an assignment problem, and of the passive agents as ob- jects. For instance RM = 1implies R =RW and the objects in M are allocated to agents in W.

A deterministic matching p of the ir-reduced problem (M, W, R) is a subset of M x W, such that (m, w) E p only if R,,,,,, = 1,and any person appears there at most once: for any m E M (resp. w E W) there exists at most one G E W (resp. & E M) such that (m, G) E p (resp. (&, w) Ep). Persons who appear as a component of a pair from p, and only those, are matched by p. We write A(M, W, R) for the set of voluntary deterministic matchings.

A random matching is a lottery n-on A(M, W, R). For all our results, the only relevant information about a random matching n-is the random allocation matrix 2,giving for all m and w the probability z,,,, that man m and woman w are matched, i.e., the probability that n-selects a deterministic matching p such

A. BOGOMOLNAIA AND H. MOULIN

that (rn, W)E p. Thus the M x W matrix Z is substochastic, that is to say it is nonnegative and the sum of each row and each column is at most 1; moreover z,,,, is positive only if man rn and woman w are compatible.

The mapping from a random matching .rr to its allocation matrix Z is clearly not one-to-one. A variant of the Von Neumann-Birkhof theorem on bistochas- tic matrices (see Lemma 2.1 in Bogomolnaia and Moulin (2002)), implies that it is onto the following set of M x W matrices:

Z(M, W, R) = {Z I Z is substochastic and R ,,,,,= 0 +z,,,,, = 0).

(1)

For agent rn with dichotomous preferences RM,,, stochastic dominance is a complete relation among the feasible m-rows Z,,; therefore the sum of the entries in this row is the canonical utility representation of his preferences over random matchings. It is simply the probability that he gets an acceptable match. Denoting similarly Zu for the w-column of Z, our utility functions are

We denote by UV(M, W, R) the set of feasible utility vectors (of length \MI+ I WI), namely the image of Z(M, W, R) under the utility functions (2).

A solution is a mapping (M,W, R) -+ Z associating a random allocation matrix to any problem. A welfarist solution only keeps track of the utility profile. It does not specify which particular allocation matrix Z implements the utility profile. Formally it is a mapping (M, W, R) + (u,v) E UV(M, W, R).

4.EFFICIENCY

A person who is not compatible with anybody (R,, = 64 or Ru = VI) has no bearing on efficiency, and can simply be ignored. We assume R,, # 63 and R" # V) for all rn, w in this section and the following one. For future reference, note that such a "null" person could play a strategic role in a group manipula- tion of the kind we discuss in Section 6 (by sending a non-null report).

We discuss first the structure of efficient matchings in the ir-reduced prob- lem (M, W, R). Any such matching p is core-stable because a pair (m, w), has a blocking objection only if m and ware mutually acceptable and neither is matched at p: this would contradict the efficiency of p. The converse state- ment is just as obvious, therefore for deterministic matchings core-stability and efficiency plus individual rationality are identical properties.

In the following statement, {S,, Sz, S:) is called apartition of S if S1, S?.Si are disjoint subsets of S, their union is S, and at least one of S,, S1, Si is nonempty. Also, we say that an ir-reduced problem (M, W, R) is a perj+iect match if there is p E A(M, W, R) at which all men and all women are matched.

LEMMA1 (Gallai-Edmonds Decomposition): Given a matching problem (M, W, R) with R, # O,R" # fl for all m, w, there is a unique pair ofpartitions {MO,MP, Md} of M and (WO, WP, Wd} of W such that:

(i) Wd is only compatible with MU, and Mu is overdemanded by Wd: R"~=Mu and

(ii) the restricted problem (Mp, Wp, R) is a pegect match;

(iii) Md is only compatible with W", and WO is overdemanded by Md: RWd= W0 and

(4) lRBnMdl>IBI forallBS W".

We call MO, W" the sets of overdemanded persons, MP, WP the sets of pefect persons, and Md, Wd the sets of disposable persons.

Note in particular that IMOI < lWdl, IMP1 = IWp, and lMdl > IW0I. The problem is trivial when the only nonempty sets are MP and WP.

The women in Wd are compatible only with men in MO and are enough to make everyone in M" happy: we can assign MOto Wd.In fact (3) implies IRs n Wlf\{w]J SI for any w in Wd;hence by Hall's theorem applied to the assignment of overdemanded men, MOcan be assigned to Wd\{w}. This justifies our "disposable" terminology for the women in Wd.

Figure 1depicts the compatibility matrix R of a 10men-10 women example. One checks easily:

A matching p u. A(M, W, R) is efficient if and only if the subset of M U W that it matches is inclusion maximal: by Lemma 1all inclusion maximal match- ings in A(M, W, R) match the same number of agents.

LEMMA2: Notations are as in Lemma 1. Define the efficiency size ofproblem (M, W, R) as

A deterministic matching p E A(M, W, R) is efficient (Pareto optimal with re- spect to the utilities (2))ifand only if exactly 2e agents (e men and e women) are matched by kcL.

In all efJicient matchings, Mu is matched to a proper subset of Wd, WO is matched to a proper subset of M", and MP and WP arepe$ectly matched.

A. BOGOMOLNAIA AND H. MOULIN

over-demanded perfect disposable W0 wp wd

,2-/\--dL7

overdemandedM" <> mz I 1 0 1 0 0 1 1 0 0

1 1 1

perfect M~ < m5 / o 1 / 0 o II I

mro / 0 I1

From the point of view of welfare, all that matters is which pairs of coalitions (S,B) of size e, where S c M, B c W, can be matched and which cannot. We call the former pairs eficient and denote their set by E(M, W, R).A person is disposable if and only if there is an efficient coalition (S,B) to which he or she does not belong. Note that, by Lemma 2, there is also an efficient coalition to which he or she belongs (recall our assumption R,, ,R,, # (il).

The only aspect of the efficiency frontier not determined by the partition of Lemma 1 is this: which coalitions from Mli can be (simultaneously) matched and which coalitions from W" can be matched? In the example of Figure 1 the answer is, respectively, every pair of M" = {m,,nzb,mg, mlo} and seven triples from Wli = {w6,w7,WS,wh ,111,,,) (the three triples containing w, and wh are excluded).

We turn our attention to efficient and individually rational random match- ings. Let n be a lottery over A(M, W. R), the set of deterministic matchings. A necessary condition for the Pareto optimality (efficiency) of .rr with respect to the utilities (2) is that its support contains only efficient matchings (this is the familiar ex-post efficiency property). This condition is sufficient as well: by Lemma 2 every efficient deterministic matching p maximizes the joint utility C,,u,, + C,,v,,=2e(M, W,R),and so does every lottery over these match- ings.

LEMMA3: Notations are us in Lemmas 1, 2.

- (i)
- A random matching is ejficient in the ir-reduced problem if arzcl only if, with probability one, it matches 2e(M, W,R)persons.
- (ii)
- A lurzdor~zailocatiorz r7zatr.k Z is eficierzt ifnrzd orzb ifthe sum of it^ entries is e(M, W, R).

(iii) A random allocation matrix Z for a matching problem is efficient if and only if z,~> 0 only for (m,w)E (MO, Wd) U (MP, WP) U (Md, WO), and its restriction to (MP, WP) is bistochastic, to (MO, Wd) is row-stochastic, and to (Md, WO ) is col~lmn-stochastic.

A consequence of Lemma 3 is that a random matching is core-stable if and only if its allocation matrix is efficient. Indeed the only agents whose utility may be smaller than 1are those in Md and W" but there is no mutually acceptable match between these agents (statement (i) in Lemma 1).

The efficiency size e(M, W, R) has some sub- and supermodularity prop- erties that play a crucial role in the sequel. In what follows we consider the efficiency size e(S, B, R) of the restriction of our original problem (M,W, R) to subsets S GM and B GW.We abuse notation slightly by writing the restric- tion of R to S x B simply as R. The set of disposable men, or women, has a simple characterization by means of the efficiency size function:

m E MOUMPee(M\m, W, R) =e(M, W, R) -1,

(6)

(7) m EM^ +e(M\m, W, R) =e(M, W, R).

The efficiency size e(M, W, R) is submodular in M and in W, and super- modular in M x W. In the following inequalities, we write e(S, B) instead of e(S, B, R):

e(S, W) +e(T, W) e(S U T, W)+e(S n T, W), for all S, T & M, e(M, B) +e(M,C)2 e(M, B U C) +e(M, B nC), for all B, CGW, e(S, B) +e(S', B') ? e(S, B') + e(S', B), for all S gSf and all B S B'.

Finally, the efficiency size function allows a compact description of the effi- cient utility profiles in the ir-reduced problem. These are the utility profiles of the core-stable random matchings.

LEMMA4: Given an ir-reduced problem (M, W, R), a utility vector (u, v) E [0,l].M+"is feasible and efficient if and only if it is a solution of the following system:

xun,= xv,.=e(~, W, R);

'\f W

(8) x u,, je(S, W, R) for all S GM,

S

We denote by UVe(M, W, R) the set of eficient feasible utility vectors.

A. BOGOMOLNAIA AND H. MOULIN

5. THE EGALITARIAN SOLUTION

The egalitarian solution picks an efficient matching equalizing as much as possible the individual utilities, i.e., the probabilities of an acceptable match. When full equality is not compatible with efficiency, the solution maximizes the familiar leximin ordering.

In the example of Figure 1, women w, and w8 are only compatible with ml, therefore min{v,, vh} 0.5 for any feasible utility profile (u,v). Men YIZ,, m8, mq, and nzlohave to share w, and w2, so min{rk,, 4,ug,~1,~)

5 0.5 as well. If we reserve m2, w,, and w2for these six disposable persons, they each end up with a probability f to be matched. The remaining disposable women

wb, lny, and wlo can share men ml and m;, so as to get utility each (give of m3 to wlo, of m3and of ml to wg, and $ of ml to w6). All other persons get utility 1.This is the egalitarian solution. We define first the solution by means of a simple algorithm, before deriving its equalizing properties in Theorem 1below. We use the notations r(T) = IRT1 and r(T, B) = IRTf' BI for T M, B 2 W. For any real valued function h, the expression argmin, h(T)stands for the subset T of S minimizing h over all subsets of S: if several subsets of S reach the minimum, T is the largest one in the sense of inclusion: this is well-defined in our case, because, for our choice of the function h, if two subsets minimize h on 25,SO will their union. The last piece of notation concerns the sequence T,, k = 1,2,. . . , of disjoint subsets of M constructed in the definition. We write T, , for the union of T,, Tz,. . . , T,. Given an ir-reduced problem (M, W, R), and an efficient (core-stable) util- ity profile, the only agents whose utility may be less than 1 are the disposable men M" and women Wd. In view of Lemma 1, we can leave aside the per- fectly matched agents in M" and WCi and solve two separate matching sub- problems (Md, Wri, R) and (M", W", R). Since overdemanded agents always get a match, we can think of W" and M" as objects and of these subproblems as, respectively, the assignment of W" to the agents in M", and of M" to the agents in Wli. The algorithm defining the egalitarian solution is only given for the subproblem (M",W",R); for the subproblem (M", W",R) we simply ex- change the roles of men and women.

DEFINITION

1: Given the subproblem (M", W", R) of the ir-reduced prob- lem (M, W, R), we define recursively an increasing sequence of numbers ah, k = 1,.. . , K, where 0 < ah< 1, and a partition of Md by a sequence Tk, k = 1, . . . , K, of nonempty coalitions:

r(T, Wh-I 1,

(9) ak= min

11,-i IT1

Tk= arg min r(T, Wk-1)

lfk-1

The sequences ak, Tk stop at K where TI,,,,k =Md.The egalitarian utility pro- file is: uR, =a,, if m E Tk,for k =1,.. .,K.

The egalitarian solution is welfarist: we only define its utility profile without specifying which random allocation matrix should be used to implement it. For instance, the perfectly matched agents in M*, WP receive utility 1,and there may be a number of ways to match them.

Yet the matrices Z E Z(Md, W", R) implementing the egalitarian utility pro- file uQre largely determined by the algorithm (9). The matrix Z must as- sign all the objects in RT, to coalition TI in order to achieve the total utility C,, IL;, = r(Tl)= IRT,I. All the objects in RT2 n Wl = RT7\RT1 must be as- signed to coalition T2 to secure the utility CT2u;, = r(T2,W) = IRT2n Wl, given that RT1 is not available. The key fact is that the new maximum utility a2 is greater than crl; thus the decision to reserve RT1 to TI is vindicated on egalitarian grounds. By repeating this argument we see that Z must assign pre- cisely the objects RTk nWk-I=RTk\RTI i-, to coalition Tk for k = 1,...,K. In short, coalition Tk receives at stage k all the objects it likes among those not assigned in earlier stages.

Our next result states two distinct characterizations of the egalitarian solu- tion, justifying its normative appeal as a fair outcome of our matching problem. Recall that the Lorenz dominance is the following partial orderings of vectors in

RMLLV. . (u,v) dominates (t,w) if upon rearranging their p = 1 MI +I W I coordi

nates increasingly as x* and yx,we have ~:=,(n;-y;) >0for all k = 1,... ,p.

THEOREM1: (i) Given an ir-reducedproblem (M, W, R), the egalitarian util- ity profile is Lorenz dominant in the feasible utility set W(M, W, R).

(ii) Given positive prices p,, for each woman and pm for each man, we say that an eficient allocation matrix Z EZ(M,W, R) is competitive at p with equal income of one if we have for all m, w

zmu,> 0+pU =min p, , pm =min px and

1€Rm rcRU

The allocation matrix Z is equal income competitive if and only if it implements the egalitarian profile.

We interpret statement (i) first. If the arbitrary convex set Li of utility pro- files contains a Lorenz dominant element u*, this profile has a very strong claim to fairness within the efficiency frontier. Indeed, it achieves the maxi- mum over Uof any collective utility function averse to inequality (in the sense of the Pigou-Dalton transfer principle); it is the unique maximum if the col- lective utility is strictly averse to inequality. Thus u* maximizes not only the leximin ordering but also the Nash collective utility C,,log u,,, and any collec-

A. BOGOMOLNAIA AND H. MOULIN

tive utility EL,

f (u,,)for any increasing and concave function f (if f is strictly concave, u" is the unique maximum), and more. Turning to statement (ii), we note that an allocation Z implementing the egalitarian profile 14' is equal income competitive for the following prices:

y,, =p"' = 1 if nz E M" U MIJ and w E W" U W",

where an,Tk,Wkis the sequence constructed in (9), so that RT1.n Wk_, covers W" as k varies from 1 to K. The sequence P,, S1,M, is the similar sequence when the algorithm is used to assign the agents W" to Mu (upon exchanging the roles of men and women).

Consider the competitive demand at the above prices p, for an agent rn in Tk with income of 1.This agent will buy only (a fraction of) the cheapest objects in R,,,.The discussion following Definition 1shows that these are precisely the objects in the nonempty set R,,,n RILf' Wx-,. They all cost l/wx; therefore with a budget of one, agent m buys a fraction (probability or time-share) ax of his good objects. Thus every matrix Z implementing 11' is equal income competitive. Statement (ii) says that the converse holds true as well.

The main result in Dutta and Ray (19891, is related to-and used in the proof of-our Theorem 1. By Lemma 1 we can interpret the set U'(Mi',W",R) of efficient utility vectors for M" as the core of the submodular coopera- tive game S + e(S,W, R).Theorem 3 in Dutta and Ray (1989) implies that Uf(M". W", R) contains a Lorenz dominant element (the first statement of our Theorem 1) and computes it by an algorithm identical to (9). except that r(T, B) is replaced evelywhere by e(T.B), the efficiency size of the reduced problem (T,B, R). See the proof of Theorem 1. Note that r(T.B) is com- puted by direct inspection of the matrix R, whereas computing e(T,B) is the harder task of discovering the Gallai-Edmonds decomposition of the subprob- lem (T. B. R).

6. STRATEGYPROOFNESS AND GROUP-STRATEGYPROOFNESS

We investigate in this section the strategic opportunities in the direct rev- elation mechanisms associated with solutions (or welfarist solutions) of the matching problems. Recall that a solution g maps every problem (M, W, R) into a random allocation matrix 2, whereas a welfarist solution f maps (M, W, R) into a utility profile LL (or (~1,v)). Thus every solution g projects onto the following welfarist solution f (M,W, R) = u(g(M,W, R)).

Strategyproofness is not a welfarist concept: its definition requires specifi- cation of how the allocation matrix is affected when the reported preferences

change. When we speak below of a welfarist solution (such as the egalitarian and priority solutions) being strategyproof (or any group variant of this property) we always refer to the most demanding interpretation, namely "f is strategyproof" means that "every solution g projecting onto f is strategyproof."

Given a (nonwelfarist) solution g (Section 2), the associated direct revelation mechanism works as follows. Men and women report their preferences RM and RW, respectively, and the solution g applied to the ir-reduced problem RM RW implements the random allocation matrix Z. Here the notation

A. B stands for the entry-by-entry product of the matrices A, B of the same size.

DEFINITION

2: The solution g is called male-strategyproof if for all m E M, and any three matrices RM, RM',and RW with g(RM RW) = Z and g(RM1 RW) = Z':

(RM,,, = RMI,, for all m' # m) =. u,,,(Z,) 2u,,,(Z:,).

The solution is called strategyproof if it is both male-and female-strategyproof. The solution is called mule-group-strategyproof if for all S M, and any three matrices RM, RM', and RW, with g(RM R W)= Z and g(RM1 RW) = Z':

{RMm1= RM;, for all m' $ S and u,,(Z,,,) u,,(Z;,)for all m ES}

j{u,,(Z,) = u,,(ZL) for all m ES}.

The simplest example of a strategyproof and core-stable solution is apriority solution. Given a priority ordering + of M u W, we define the >priority utility profile as the + lexicographic maximum over the utility set UV. Thus the highest priority person i, gets utility 1 because he or she is compatible with at least one person; the next person in the priority line, i2,gets utility 1if there is a way to match him or her without affecting the utility of person i,; otherwise this person's utility is 0, and so on.

It is easy to check that a priority solution is core-stable, as well as strategyproof. As both properties are preserved by convex combinations with fixed weights (Lemma 3), a natural idea is to randomly select a priority solution, with uniform probability over all orderings of M U W.The resulting random priority solcition is fair, core-stable, and strategyproof for both sides of the market.

Thus in the dichotomous domain, core stability and strategyproofness are satisfied by a large class of solutions (including all convex combinations of priority solutions, the egalitarian solution, and more). This stands in sharp contrast with the situation in the classic domain of strict preferences where core stability is only compatible with strategyproofness on one side of the market (Roth (1982)). For instance, a priority solution in the classic domain is strategyproof on both sides, but it does not always pick a matching in the core.

A. BOGOMOLNAIA AND H. MOULIN

Back to the dichotomous domain, it is a much taller order to discover a solu- tion in the core that is also strategyproof with respect to one-gender coalitions. For instance, a priority solution is not male-group-strategyproof. Consider the problem with three men and two women where each woman finds all men ac- ceptable, ml finds both women acceptable whereas wlis the only acceptable woman for m2 and w2the only acceptable woman for m?.Given the priority or- dering m, + m7 + m3,the truthful outcome matches ml and m2.However m, can help m3 at no cost to himself by announcing that wlis his only acceptable mate.

Our next result says that every deterministic and core-stable solution is sim- ilarly vulnerable.

LEMMA5: With three or more agents and two or more objects, no deterministic core-stable sol~ltion is either male- or female-group-strategyproof.

On the other hand, if randomization is feasible, this incompatibility disap- pears.

THEOREM2: The egalitarian solution is both male-group-strategyproof and female-group-strategyproof.

We are not aware of another mechanism design problem where random- ization is necessaT to combine efficiency and strong incentive compatibility properties.

We note that the random priority solution is not even weakly-groupstrategyproof with respect to all male or all female coalitions. That is to say. there are profiles where a coalition of men, say, can strictly improve upon every member's utility by jointly misreporting their preferences. An example is given in Bogomolnaia and Moulin (2001) (see the proof of Lemma 8).

Finally, we turn to joint misreports by coalitions mixing some men and some women. A simple example shows that no core-stable solution is group- strategyproof.

Assume M = {m),W= {wl,

wZ}, and both women are compatible with the unique man. Here m can enforce matching (m, w)by reporting that he only likes w, so if a matching mechanism chooses (m,w,) with positive probability, the coalition In,w,, j # i, can manipulate to the benefit of woman w,.

Thus the strong form of group-strategyproofness is out of reach in our model, given our primary concern with core stability. However, there is some hope to find a reasonable solution meeting the weaker version of this prop- erty where we only rule out joint misreports from which all members of the group strictly benefit. For instance. a priority solution is thus weakly group- strategyproof (Definition 3). Indeed, consider a member of the deviating coali- tion with the highest priority. He or she can improve only if somebody with higher priority, who was matched initially, does not get a match after manipu- lation. The only way this can happen is when another member of the deviating coalition pretends to like such a person, is matched to this person by some implementation of the priority solution, but refuses this match ex post. But this means that under the manipulation the utility of this last member of the deviating coalition is zero, so this person does not improve.

DEFINITION 3: The solution g is called weakly group-strategyproof if for all S c M, all B E W, and any four matrices RM, RW, RM', RW', with Z = g(RM lRW) and Z' =g(RM1lRW') eRM RW:

{RM,,, =RML,, for all m' $ S and RW,,,,=RW:,,, for all w' $ B}

+{u,,(z,) > u,(Z,,) for some m E B or v,,,(ZU')3v,(Zt")

for some w E B}.

Definition 3 uses the full force of the individual rationality assumption. Following the misreport RM', R_W' by coalitions S and B, the solution g implements the allocation matrix Z =g(RM1lRW'). The pair (m, w) is incompatible if RM,,, . RW,, =0; if t,,, > 0 for such a pair, the match (m, w) will be implemented by g with positive probability, given the reported preferences, yet it will not happen ex post because it is not voluntary for at least one of the two persons. Thus the allocation matrix actually implemented under individual rationality is Z lRM lRW, as shown in Definition 3.

Unfortunately, weak group-strategyproofness is not compatible with even the elementary test of horizontal equity known as equal treatment of equals.

Consider the following example with four men and four women. Let ml and wl like persons of the opposite gender numbered 2, 3, and 4, m2 and w2 like persons 1,3, and 4, while m3,mj and w3,WJ only like person 1.We have:

Suppose now all men in S = {m3,m4,w3,w4}pretend to also like person 2. We get:

A. BOGOMOLNAIA AND H. MOULIN

Note that the preference matrix R' allows a perfect match.

Consider an efficient solution g that also treats equals equally, namely for all problems (M, W, R)with g(M, W. R) =Z and all m, m', w, w':

The above property plus efficiency determine g at R and R':

Because persons 3, 4 reject, ex post, a match with person 2, the allocation matrix actually implemented is

thus the misreport strictly benefits everyone in S. We conclude that g violates weak group-strategyproofness.

A welfarist solution is WGSP if all solutions projecting onto it are WGSP.In the Appendix, we use the same 4 x4 example to prove the second statement in our next result.

THEOREM3: Assume at least 4 men and 4 women. No core-stable solution treating equals equally is weakly group-strategyproof. No core-stable welfarist so- lution is weakly group-strategyproof.

7. TWO CONCLUDING COMMENTS

- Beyond horizontal equity (equal treatment of equals), we can evaluate the normative appeal of a solution by several tests familiar to the fair division literature. The no envy test requires u,,(Z,,) 1u,,(Z,, )for all m, m', and a sim- ilar statement among women. Another popular test ispopzllation monotonicity, stating that when a new woman is added to W, the utility of no man should de- crease and that of no woman should increase, and a symmetrical statement by exchanging the roles of men and women. By its competitive interpretation, the egalitarian solution meets no envy, and it is easy to deduce from the properties of the efficiency function in Section 4 that population monotonicity is true as well. In fact these two tests prove relatively easy to meet in our model. Exam- ples include the random priority solution (Section 6) and a number of other solutions. See Bogomolnaia and Moulin (2001) for a detailed discussion.
- The roommate problem is the natural generalization of bilateral match- ing where the (gender neutral) agents must form pairs (to share a hypo- thetical room). Under the assumption of dichotomous preferences and the restriction to voluntary (individually rational) matching, an ir-reduced prob- lem is described by a general matching problem, namely a pair (N, G) where N is the set of agents, G is an undirected graph on N, and an edge between two agents means that they are mutually compatible. The Gallai-Edmonds de- composition generalizes to the matching problem (N, G): see Theorem 3.2.1 in Lovasz and Plummer (1986). In particular all inclusion maximal matchings compatible with G have the same cardinality, so we can still speak of the ef- ficiency size e of an arbitrary problem. Hence for random matchings, it is still true that ex post and ex ante efficiency coincide: a random matching is efficient if and only if, with probability one, it matches exactly 2e agents.

It is straightforward to extend the definition of fixed priority and random pri- ority solutions to the roommate problem. One checks just as easily that these solutions are strategyproof. Therefore, the latter two solutions are efficient, strategyproof and treat equals equally.

As in bilateral matching, weak group-strategyproofness is out of reach in the roommate problem, if we also insist on efficiency and fairness. Unlike in bilateral matching, this fact does not depend upon the ex post rejection of matches. Consider the three person problem where each one of agents 1, 2, and 3 like the other two, so that G is the complete graph. An efficient solution treating equals equally must match each pair {i, j}with probability f, resulting in the utility $ for each. Now if 1 and 2 both report that they only like each other, they are matched with probability 1(by efficiency).

Department of Economics, MS 22, Rice University, PO. Box 1892, Houston, TX 77251-1 892, U.S.A.; annab @ rice.edu; http:l/www.n~j rice.edu/-econl and

Department of Economics, MS 22, Rice University, PO. Box 1892, Houston, TX 77251 -1892, U. S.A.; moulin@rice.edu; http://www. rujrice. edul-econlfacultyl PagesIMoulin, htm

Marzuscript received October; 2001; final revision received April, 2003.

APPENDIX: PROOFS

A. Proofs for Section 4

A bipartite graph between a set of men and a set of women connects some men to some women by edges. A matching is a subset of edges of the graph such that each point (man or woman) is in at most one edge. Matching theory explores the properties of inclusion maximal matchings, simply called ntavimal matchings. If we interpret the presence (resp. absence) of an edge in the graph joining m to w as "man m and woman w are mutually acceptable," then a maximal matching is precisely an efficient and voluntary matching. The decomposition of efficient matchings in two disjoint efficient assignments is then a simple reinterpretation of the well known Gallai-Edmonds decomposition of bipartite matching graphs.

A. BOGOMOLNAIA AND H. MOULIN

Lemmas 1-3 can thus be easily retrieved from matching theory upon translating our economic terminology Into the graph-theoretical terminology of matching. An excellent survey of matching theory is Lovasz and Plummer (1986), in particular, Chapter 3. More direct proofs can be found in Ore (1962. Theorem 7.6.1).

Sub- and supermodularity properties 5tated in the section are the submodularity of the rank function of a matroid (~ee, for example, Korte and Vygen (1991, Theorem 13.10)).

PROOF OF LEMMA 4: It is enough to check the statement for the assignment of Wo to Md.For any coalition S and any deterministic assignment p, p 6A(M0.W", R), with associated utility profile u, the sum C,u,,, is the number of agents in S assigned by p. Therefore if p is efficient, its utility profile meets system (8). By linearity, so does the utility profile of any efficient random assignment.

To prove the converse statement, let u E [0, l]."" be a solution of system (8). By a classical re- sult about submodular (concave) cooperative games (Shapley (1971)) u is a convex combination of marginal contribution profiles u'. For a strict ordering > of Md,this vector is defined by

LL~,= e(T Li {m},W".R) -c(T,W".R) for all nz,

where T is the set of agents preceding m in >. It is easy to see that u' is the utility profile of the (efficient) >priority assignment, as defined in Section 6. Thus u is the utility profile of an efficient random assignment.

B. Proofs for Section 5: Theorem 1

It is enough to check statement (i) for the assignment subproblem (Md,Wo, R),In what follows we write M and W instead of .&Idand W".

The straightforward proof of statement (ii) is omitted for brevity.

Step 1:Prelimina~ result.

Let f be a nonnegative submodular function defined over the nonempty subsets of M. Fix a coalition S, S E M. and consider the program of minimizing f (T)/ITI over all nonempty subsets of S. It is easy to check that the set of its solutions is stable by union. therefore the largest solution is well-defined; this set is denoted argmin, f(T)/ITI.

For any subset B of W,the function T -t r(T,B) = lRTnB(is obviously submodular: therefore the sequence Tk,k = 1,2. . . . , is well-defined by (9).

Step 2: Another algorithm

We apply the above result to the submodular function T 4 e(T. W,R) denoted simply e(T). We construct inductively two sequences Pi, Si , k = 1.2. . . . , by an algorithm similar to (9), introduced by Dutta and Ray (1989):

No= M. e,,= r: next for k= 1.2.. . . ,

By construction, the sets SLare disjoint and there is a step L such that S,. . . . . SL partition M. at which point the sequence stops.

Dutta and Ray's egalitarian solution for the submodular (concave) cooperative game T + e(T) is the utility profile I,x,, = PAif n1 E Sk,k = 1... . . L. They show that .-iis in the core of the game (M,e), and Lorenz dominates every other utility profile in the corc. Translated with our terminology, the core property is system (8); thus the result says that x is an efficient profile,

x E Ue(M,W, R), and it Lorenz dominates every other feasible utility profile (even inefficient ones).

For the sake of completeness, we prove below that x is in Ue(M, W, R), and that it maximizes the leximin ordering over this set. We also show that the sequence Pk is strictly increasing. Then we proceed to check that (Pk, Sk) and (ah, Tn)are two sequences of the same length, K =L, and that they coincide with the possible exception of the last term.

The equality C, x,, = e(M) is clear from (B.l). Feasibility of x requires 1,x, 5 e(S) for all S. Suppose S cS1; then C, x, = IS/ . PI 5e(S) by definition of PI. Suppose S cS1*,and set S' = S nS,, i = 1,2. By definition of P? and submodularity of e:

Combining this with PI 5e(S1)/IS'I gives PI . IS1/+ P2 . IS2(5 e(S), as desired. And so on inductively.

Next we check that Pkis strictly increasing. Note first that e(T) 5 IT/ for all T, implying Pk 51 for all k. The inequality Pk < Pktl means Pk < ek(T)/ITI for all T 2Nh. Assume the latter fails for some T, namely:

Both ratios above are at most 1;therefore,

But Sk is the largest solution of minek-l(T)/iTi, a contradiction. It is now easy to check that x maximizes the leximin ordering over UY. Suppose y, another profile in Up, is leximin preferred to x. Then for all m E S,. y,,, 1x; = x,,, and moreover

therefore y and x coincide on S1. Next,

for all mE S: y,, 1yI;,+, 1x;,l,+l=x,,,

and moreover

so that y and x coincide on S1 U S2. And so on. For the sake of brevity, we refer the reader to Theorem 3 in Dutta and Ray (1989) for a proof of the fact that x is Lorenz dominant in U'.

Step 3: Equality of the two sequences.

We check by induction that, as long as PAremains strictly below 1, the two algorithms (9) and (B.l) coincide. More precisely we prove the following property P(k)by induction on k:

A. BOGOMOLNAIA AND H. MOULIN

Step 3.a:Proof of P( 1).

Assume we know ciSl)= riSl1. This implies PI =r(SI)/I(SI

); >a,.On the other hand e(T)5 r(T)for all T implies PI 5 a,,so that PI=ul and SI5TI.Next we have

implying TI& SI.Thus the equality e(SI) =riSI) is enough to conclude a,=PI, SI = TI.

We assume c(S1)< riSI)and show a contradiction of the assumption PI < 1. In the Gallai- Edmonds decomposition of (Sl,1Y.R),S; = SI\\S;' is nonempty (otherwise e(Slj = r(SI):see Lemmas 1. 2). If 5;'is empty, e(SI)= lSli+PI = 1. Thus both S;'and Sf are nonempty and we have, with the notations of Lemmas 1, 2.

where the inequality follows from 1M"I i1S:l. namely the overdemanded character of Wo.We have reached a contradiction of the definition of PI.

Step3.0:Irlduction step.

Assume 'P(k-I) and Pi < 1. Consider an arbitrarq coalition T c M,-,. By Pik -1). c(TI, A = r(TI.,i-l), which means that all objects in RT, &-, can be assigned to TI, ,A-,. Clearly this implies

We see now that the kth steps in our two algorithms are to minimize, respectively, e(T. Wi-I)/TI and r(T. Wi-,)/TI. Upon changing Wto Wi-,,the same argument as in Step 3.21 shows now: cu, = pi. Ti = Si. as well as e(Ti. Wk. ,) =r(Ti,Wk-,).Conibining this with (B.?) and P(k -1).we get

Step 4: Proofof Tlleorenl I (Stutenlerlrii)).

The sequence pa increascs. and PA5 1.

We show first that pX < 1. Indeed, if PK,< 1= PX. then (B.2) is valid and Pti = 1 reads e(T,I.ZTh-,) = T for all T iYK-,.Thus SX=MKIand the algorithm (B.l) stops there. More- over IV,, ='v,?..,can be assigned to I.t/h. l, and on the other hand only the agents in MA,like L.t;-l:

But this means that AfX_,cannot contain disposable agents. Thus. MX-]= 0= Wh-l. TI =M", SK=Pi: thus the algorithm stopped before the Kth step. Now, if TI ti =M and pX < 1. PiK) establishes the full equality of the two algorithms, and we are done.

C. Proqfr for Sect~otl h

PROOF OF LEMMA5: It is enough to consider .ZIi = 3. IW1= 2, and restrict our attention to profiles where each woman likes all three men. Let a deterministic mechanism among ,2f = 1.2.3

and W = a, bbe male-group-strategyproof and efficient. We derive a contradiction by considering the following eight different preference matrices RM = R:

[I] 6:

-1

71. 81.

1

11 0 1 0 1

The efficiency size of all eight problems is 2. We write an assignment (i, j) to indicate that object a goes to agent i and b to j. We write a two-person coalition simply as ij.

Suppose, without loss of generality, that our mechanism chooses (1,2)at [I]. Then it must choose (1,2)at [2]:if u, = 0or 11, = 0 at [2].coalition 12 can manipulate at [2]by R' = [I]. Consider [3]next: the only two efficient assignments are (1,3)and (2.3);if (2.3)is selected, 23 manipulates at [2]by R' = [3],hence (1,3)is chosen at 131.Then (1,3)is chosen at (41as well: the other efficient choice (2.3)allows 13 to manipulate at [4]by reporting [3](and 23 to manipulate at [3]by [4]!).Now at [I]the efficient coalition 13 must be chosen (by way of (1.3)or (3,1)) or 13 could manipulate at [5]by R' = 141.

Consider [6]: if (2.1) is selected, 12 manipulates at [5]by [6]:if (2.3)is selected, 13 manipulates at [6]by R' = [4].Thus (3, 1) is selected. Now if (2,3)is selected at [7]. 23 manipulates at (61 by [7];therefore, by efficiency, (2,1) is chosen at [7].Consider 181:if (1.3)or (2,3)is selected. 12 manipulates at 181 by 171, thus (2,1)is chosen at [8]as well. Recall that (1,3)is chosen at [3]: therefore 13 manipulates at [8] by [3],and we have reached a contradiction.

PROOFOF THEOREM2: We assume that RE',,,, = 1 for all rn, ~u,and thus R =RM. Clearly, under profiles where some women dislike some men, men' possibilities to manipulate can only diminish.

We fix two profiles R. R'. respectively the true and the false profile, and two allocation matrices Z E q(M.W,R), Z' E (F(MW,R').We define the sets of losers, winners, and indifferent agents in the manipulation at R by R':

tn E W iff u,,(Z,',,)= xz:,,,,, > u,,,(Z,,,):

K,,

rn~Z iff u,,,(Zb,)=~l~(Z,,):

m E L: iff u,,~( Zit31 < (Z,,,).

We assume R,,, = R:,,for all m E L (the losers cannot be part of the deviating coalition) and prove by induction W = I.1. This establishes group-strategyproofness because R. R' are arbitrary. We write ak.TL,E';.and a;,T,',W,',for the sequences corresponding to R and R'. respectively. We prove by induction the property %'(k):

We assume P(k -1j and pro\e P(k).In the case k = 1, P(0) is void. We aswme k 5 K -1, so that 11,,,(Z,,)= akfor all rn E TL.We set T; = TknL. T; = Tkn (M;UZ), either of which can be empty. For any m' E Ti. 171 E T;, we have:

where the first equality comes from R,,, = R;,,and the last inequality holds because the support of z;,, set

is contained in R:,.Therefore m' belongs to an "earlier" member of the partition T,'-a with a smaller index I-than m,implying that no object that rn' likes (at R,,,' = R;,,,)is assigned

A. BOGOMOLNAIA AND H. MOULIN

to nz at R' : th,,.= 0 for 10E R,,,,.By the assumption P(k -I). Z' does not give to many share of an object from R,, ,-,either. Therefore:

(C.2) {wE R,, and ti,,,,> 0) + {wE RTLn Wk-l\R7r] for all m E T,f

Now we define an allocation matrix Z* restricted to Tk,RTLn Wk-lrwhere Z + p(Z) simply deletes the coordinates outside RI, n Wk-1:

Z,',, = p(Z,,, ) for rn' E T;. Z,:,=p(Zi,,) forrncT:.

By the definitions of Tk and Wk-,, u,,,(Z,:,)= akfor all m' c Ti. and by (C.l) u,,,(Zk)= u,,,(Z;,,)2nk for all m E T;. Next the support of any Z;,and that of any Zf,, are disjoint: see (C.2). Therefore Z* is feasible. By definition of Tk, all inequalities u,,(Z,",)> cuk must be equalities, which proves T; c2,and the first statement in P(k).

Moreover Z* must exhaust all objects of RTkn Wk-l. Among these, those in R7, n Wk-I\R,L

are assigned in full by Z' to the agents of T:: no fraction of those objects goes to anyone in Tk_,,,,^..To complete the proof of P(k)we must check that the objects in RTi are not assigned at all to any agent n in (M;U Z) f' Tk ,K by Z'. For such an agent n we have:

therefore (C.1) implies ~c;(Zk)> u:,.(Zm,)for all m' E T;. Thus nz' appears in the sequence T,' earlier than n, implying that all objects he likes (at R,,, = Ri,.)are allocated before n is served, i.e., 11 gets none of RTr.

The proof of P(K -1) is now complete. If a, 5 1.then u,,( Z,) = a, for m E Tti and the above argument shows P(K).If ati11,then u,,(Z,,,)= 1 implies TKnW = O.Thus W is empty in both cases. Note that even nondisposable men can participate in the deviation; therefore cu~> 1 is possible.

PROOF OF THEOREM

3: The first statement is proven by means of the 4 x 4 examplejust before the theorem. To prove the second statement, fix an efficient welfarist solution f.and consider the same 4 x 4 example. We write LL = f (R) for the utility profile chosen by f. Without loss of generality we can assume u,,,, 3u,,; 2u,,,, and v,,,: r v,,,; 2v,,.,: as rn, and w,are overdemanded, u,,,,= v,,.,= 1. This implies u,,,?,v,; 5 $ and LL,,,,. v,., 5 !.

Consider the same manipulation RM', RW' by the coalition S = {mi,UI~].

m4,w3,By efficiency, f (R')= (1, 1, 1. I). Let g be a solution projecting on f and such that g(R')is the allocation matrix:

Then Z' = g(R') R is

and the (true) utility profile of S after the misreport is ui,,: = v:,,; = ,> i,~4:,,~= v;,= 6 > i. Therefore g is not weakly group-strategyproof, and neither is f.

REFERENCES

ALKAN,A,, AND D. GALE (2001): "Stable Schedule Matching under Revealed Preferences," forthcoming, Journal of Economic Theory. BAiOU, M., AND M. BALINSKI (2002): "The Stable Allocation (or Ordinal Transportation) Prob- lem," Matl~ematics of Operations Research, 27,485-503. BOGOMOLNAIA,

A., L. EHLERS,AND R. DEB (2000): "Housing Market with Indifferences: the Priority Method," Mimeo, Southern Methodist University. BOGOMOLNAIA,

A,, AND H. MOULIN (2001): "Random Matching and Assignment under Di- chotomous Preferences," www.r~frice.edu/~econipapersiindex.html. -(2002): "A Simple Random Assignment Problem with a Unique Solution." Economic Theory, 19,623-635. DUTTA, B., AND D. RAY(1989): "A Concept of Egalitarianism under Participation Constraints," Econometrica,57,615-635. EHLERS,L., AND B. KLAUS (2003): "Coalitional Strategyproofness, Resource Monotonicity and Separability for Multiple Assignment Problems," forthcoming, Social Choice and Welfare. EHLERS,L., B. KLAUS, AND S. PAPAI (2000): "Strategyproofness and Population Monotonicity for House Allocation Problems," Journal ofMathematica1 Economics, 83, 329-339. HYLLAND, A,, AND R. ZECKHAUSER (1979): "The Efficient Allocation of Individuals to Posi- tions," Journal of Political Economy, 91,293-313. KORTE,B., AND J. VYGEN (1991): Combinatonal Optimization. Theory and Algorithms, Algorithms and Combinatorics, Vol. 21. New York: Springer. LOVASZ.L., AND M. D. PLUMMER (1986): Matching Theory, Annals of Discrete Mathematics, Vol. 29. Amsterdam: North-Holland. ORE, 0.(1962): Theory of Graphs, American Mathematical Society Colloquium Publications, Vol. XXXVIII. Providence. R.I.: American Mathematical Societv. PAPAI. S. (2000): "Strategyproof Assignment by Hierarchical Exchange." Econometrica,68,14031434. ROTH,A. (1982): "The Economics of Matching: Stability and Incentives," Mathematics of Opera- tions Research, 7, 617-628. ROTH,A,, AND M. SOTOMAYOR(1990): Two-Sided Matching. Cambridge: Cambridge University Press.

SHAPLEY, L. (1971): "Core of Convex Games," International Journal of Game Theov, 1.11-26.

SVENSSON,L. G. (1994): "Queue Allocation of Indivisible Goods," Social Choice and Welfare, 11. 323-330. -(1999): "Strategy-Proof Allocation of Indivisible Goods," Social Choice and Welfare, 16. 557-567. ZHOU,L. (1990): "On a Conjecture by Gale about One-Sided Matching Problems," Journal of Economic Theoiy, 52,123-135.

Comments