Von Neumann-Morgenstern farsightedly stable sets in two-sided matching
Abstract
EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.
Full text
Vannetelbosch, Vincent J.; Mauleon, Ana; Vergote, Wouter Article Von Neumann-Morgenstern farsightedly stable sets in two-sided matching Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Vannetelbosch, Vincent J.; Mauleon, Ana; Vergote, Wouter (2011) : Von Neumann-Morgenstern farsightedly stable sets in two-sided matching, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 6, Iss. 3, pp. 499-521, https://doi.org/10.3982/TE527 This Version is available at: https://hdl.handle.net/10419/150162 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/3.0/
Theoretical Economics 6 (2011), 499–521 1555-7561/20110499 von Neumann–Morgenstern farsightedly stable sets in two-sided matching Ana Mauleon CEREC, Facultés universitaires Saint-Louis Vincent J. Vannetelbosch CORE, Université catholique de Louvain Wouter Vergote CEREC, Facultés universitaires Saint-Louis We adopt the notion of von Neumann–Morgenstern (vNM) farsightedly stable sets to determine which matchings are possibly stable when agents are farsighted in one-to-one matching problems. We provide the characterization of vNM farsightedly stable sets: a set of matchings is a vNM farsightedly stable set if and only if it is a singleton subset of the core. Thus, contrary to the vNM (myopically) stable sets (Ehlers 2007), vNM farsightedly stable sets cannot include matchings that are not in the core. Moreover, we show that our main result is robust to many-to-one matching problems with substitutable preferences: a set of matchings is a vNM farsightedly stable set if and only if it is a singleton set and its element is in the strong core. Keywords. Matching problem, von Neumann–Morgenstern stable sets, farsighted stability. JEL classification. C70, C78. 1. Introduction Gale and Shapley (1962) propose the simple two-sided matching model, known as the marriage problem, in which matchings are one-to-one. There are two disjoint sets of agents—men and women—and the problem is to match agents from one side of the market with agents from the other side, where each agent has the possibility to remain Ana Mauleon: [email protected] Vincent J. Vannetelbosch: [email protected] Wouter Vergote: [email protected] We thank three anonymous referees, the co-editor, Debraj Ray, and Elena Molis for helpful comments. Ana Mauleon and Vincent Vannetelbosch are Research Associates of the National Fund for Scientific Research (FNRS), Belgium. Financial support from the Spanish Ministry of Sciences and Innovation under project ECO2009-09120, support from the Belgian French Community’s program Action de Recherches Concertée 05/10-331 (UCL), and support of a SSTC grant from the Belgian State–Belgian Science Policy under IAP contract P6/09 are gratefully acknowledged. Copyright ©2011 Ana Mauleon, Vincent J. Vannetelbosch, and Wouter Vergote. Licensed under the Creative Commons Attribution-NonCommercial License 3.0. Available at http://econtheory.org. DOI: 10.3982/TE527
500 Mauleon, Vannetelbosch, and Vergote Theoretical Economics 6 (2011) single. They show that the core is nonempty. A matching is in the core if there is no subset of agents who, by forming all their partnerships only among themselves (and having the possibility of becoming single), can all obtain a strictly preferred set of partners.1 Recently, Ehlers (2007) characterizes the von Neumann–Morgenstern (hereafter, vNM) stable sets in one-to-one matching problems. A set of matchings is a vNM stable set if this set satisfies two conditions: (internal stability) no matching inside the set is dominated by a matching belonging to the set; (external stability) any matching outside the set is dominated by some matching belonging to the set. Ehlers (2007) shows that the set of matchings in the core is a subset of any vNM stable set. The notions of core and of vNM stable set are myopic notions since the agents cannot be farsighted in the sense that individual and coalitional deviations cannot be countered by subsequent deviations.2An interesting contribution is Diamantoudi and Xue (2003), who investigate farsighted stability in hedonic games (of which one-toone matching problems are a special case) by introducing the notion of the coalitional largest farsighted conservative stable set, which coincides with the largest consistent set of Chwe (1994).3The largest consistent set is based on the indirect dominance relation, which captures the fact that farsighted agents consider the end matching that their move(s) may lead to. Diamantoudi and Xue (2003) show that in hedonic games with strict preferences, core partitions are always contained in the largest consistent set. However, we show by means of an example that the largest consistent set may contain more matchings than those matchings that are in the core. Based on the indirect dominance relation, Diamantoudi and Xue (2003) define the farsighted (or abstract) core as the set of matchings that are not indirectly dominated. But the farsighted core is too exclusive because it does not take into account the credibility of the dominating matching and, hence, it can often be empty. The farsighted core exists only when the core contains a unique matching and no other matching indirectly dominates the matching in the core. In this paper, we adopt the notion of von Neumann–Morgenstern farsightedly stable sets to determine which matchings are possibly stable when agents are farsighted. This concept is studied by Chwe (1994), who introduces the notion of indirect dominance into the standard definition of vNM stable sets. Thus, a set of matchings is a vNM farsightedly stable set if no matching inside the set is indirectly dominated by a matching belonging to the set (internal stability) and any matching outside the set is indirectly dominated by some matching belonging to the set (external stability). Our main result is the characterization of vNM farsightedly stable sets in one-to-one matching problems. We show that a set of matchings is a vNM farsightedly stable set if and only if it is a singleton set and its element is in the core. Thus, contrary to the vNM (myopically) stable sets, vNM farsightedly stable sets cannot include matchings that are not in the core. In other words, we provide an alternative characterization of the core in 1We refer to Roth and Sotomayor (1990) for a comprehensive overview on two-sided matching problems. 2Harsanyi (1974) argues that the von Neumann–Morgenstern definition of stable sets is unsatisfactory because it neglects the destabilizing effect of indirect dominance relations. 3Other approaches to farsightedness in coalition and/or network formation are suggested by the work of Xue (1998)orHerings et al. (2004, 2009).
Theoretical Economics 6 (2011) vNM farsightedly stable sets 501 one-to-one matching problems. We also show that our main result is robust to manyto-one matching problems with substitutable preferences: a set of matchings is a vNM farsightedly stable set if and only if it is a singleton set and its element is in the strong core. Finally, we show that if the preferences satisfy the top coalition property, then the unique vNM farsightedly stable set, the farsighted core, and the largest consistent set consist of the unique core element. It is straightforward to see that if a matching belongs to the core, then it indirectly dominates all other matchings and hence it must be a vNM farsightedly stable set. This by itself does not characterize the vNM stable sets in a matching problem. Indeed, we need to tackle the question of whether there can be matchings that do not belong to the core, but do belong to some vNM farsightedly stable set. This question is not trivial, as in general the core matchings can be indirectly dominated by matchings that do not belong to the core. Our characterization raises the question of why the idea of vNM farsightedly stable sets makes sense in the case where the core contains more than one element, as any vNM farsightedly stable set is indirectly dominated by any other vNM farsightedly stable set. We should keep in mind that the idea of a vNM (farsightedly) stable set is a set-valued concept and, as such, is fundamentally different from a non-cooperative equilibrium concept: any deviation from a vNM farsightedly stable set, even to another stable set, is deterred because there is a (farsighted) path leading back to the initial stable set. As Diamantoudi and Xue (2007) write, a vNM (farsightedly) stable set of matchings is “free from inner contradictions and accounts for every element it excludes.” In fact, vNM farsightedly stable sets can be interpreted as the set of social outcomes consistent with a certain stable standard of behavior (Greenberg 1990). In particular, agents do not deviate if there exists a path leading back to the solution set in which the deviators are not better off and, as such, they behave optimistically in the face of (Knightian) uncertainty (Xue 1998). We show that any matching that belongs to the core, and no other set of matchings, satisfies the requirements of an optimistic stable standard of behavior: for any deviation there is a path leading back to this core matching. If the core contains more than one element, each one of them is then a stable standard of behavior. The paper is organized as follows. Section 2 introduces one-to-one matching problems and standard notions of stability. Section 3 defines vNM farsightedly stable sets. Section 4 provides the characterization of vNM farsightedly stable sets in one-to-one matching problems. Section 5 deals with many-to-one matching problems. Section 6 concludes. 2. One-to-one matching problems A one-to-one matching problem consists of a set of Nagents divided into a set of men, M={m1mr}, and a set of women, W={w1ws}, where possibly r= s.Wesometimes denote a generic agent by i,agenericmanbym, and a generic woman by w.Each agent has a complete and transitive preference ordering over the agents on the other side of the market and the prospect of being alone. Preferences are assumed to be strict. Let Pbeapreferenceprofilespecifyingforeachmanm∈Ma strict preference ordering
502 Mauleon, Vannetelbosch, and Vergote Theoretical Economics 6 (2011) over W∪{m}and for each woman w∈Wa strict preference ordering over M∪{w}: P={P(m1) P(mr)P(w1) P(ws)},whereP(i) is agent i’s strict preference ordering over the agents on the other side of the market and himself (or herself). For instance, P(w) =m4m1wm2m3mrindicates that woman wprefers m4to m1and she prefers to remain single rather than to marry anyone else. We denote by Rthe weak orders associated with P.Wewritemwmif woman wstrictly prefers mto m,write m∼wmif wis indifferent between mand m, and write mwmif mwmor m∼wm. Similarly, we write wmw,w∼mw,andwmw. A one-to-one matching problem is simply a triple (MWP). Amatching is a function μ:N→Nsatisfying the following properties: (i) ∀m∈M, μ(m) ∈W∪{m}; (ii) ∀w∈W,μ(w) ∈M∪{w}; and (iii) ∀i∈N,μ(μ(i)) =i. We denote by Mthe set of all matchings. Given a matching μ,anagentiis said to be unmatched or single if μ(i) =i. A matching μis individually rational if each agent is acceptable to his or her mate, i.e., μ(i) iifor all i∈N. For a given matching μ,apair{mw}(possibly m=w)issaidtoformablocking pair if they are not matched to one another but prefer one another to their mates at μ, i.e., wmμ(m) and mwμ(w). A matching μis stable (or pairwise stable) if it is not blocked by any individual or any pair of agents. We extend each agent’s preference over the agent’s potential partners to the set of matchings in the following way. We say that agent iprefers μto μif and only if agent i prefers his or her mate at μto his or her mate at μ,μ(i) iμ(i). Abusing notation, we write this as μiμ. A coalition Sis a subset of the set of agents N.4For S⊆N, μ(S) ={μ(i):i∈S}denotes the set of mates of agents in Sat μ. A matching μis blocked by a coalition S⊆Nif there exists a matching μsuch that μ(S) =Sand for all i∈S, μiμ.IfSblocks μ, then Sis called a blocking coalition for μ. Note that if a coalition S⊆Nblocks a matching μ, then there exists a pair {m w}(possibly m=w) that blocks μ. The core of a matching problem consists of all matchings that are not blocked by any coalition. An alternative way to define the core of a matching problem is by means of the domination relation. Definition 1. Given a matching μ, a coalition S⊆Nis said to be able to enforce a matching μover μif the following conditions hold: (i) μ(i) /∈{μ(i)i}implies {i μ(i)}⊆Sand (ii) μ(i) =i= μ(i) implies {i μ(i)}∩S= ∅. In other words, this enforceability condition implies both that any new match in μ that does not exist in μshould be between players in S, and that to destroy an existing match in μ, one of the two players involved in that match should belong to coalition S.5 Notice that the concept of enforceability is independent of preferences. Furthermore, the fact that coalition S⊆Ncan enforce a matching μover μimplies that there exists a sequence of matchings μ0μ1μK(where μ0=μand μK=μ) and a sequence of disjoint pairs {m0w0}{mK−1wK−1}(possibly for some k∈{01K −1}, 4Throughout the paper, we use the notation ⊆for weak inclusion and for strict inclusion. 5Notice that this enforceability condition is similar to the enforceability condition defined in Roth and Sotomayor (1990). That is, a coalition Scan enforce the set of marriages in the matching μthat concerns its members if and only if every man in Sis married to a woman in Sand vice versa.
Theoretical Economics 6 (2011) vNM farsightedly stable sets 503 mk=wk)suchthatforanyk∈{1K},thepair{mk−1wk−1}∈Scan enforce the matching μkover μk−1. Definition 2. A matching μis directly dominated by μ,orμ<μ ,ifthereexistsa coalition S⊆Nof agents such that μiμ∀i∈Sand Scan enforce μover μ. Definition 2 gives us the definition of direct dominance. The direct dominance relation is denoted by <. A matching μis in the core if there is no subset of agents who, by rearranging their partnerships only among themselves and possibly dissolving some partnerships of μ, can all obtain a strictly preferred set of partners. Formally, a matching μis in the core if μis not directly dominated by any other matching μ∈M.6Given a profile P, we denote the set of matchings in the core by C(P).Gale and Shapley (1962) prove that the core is nonempty. Sotomayor (1996) provides a nonconstructive elementary proof of the existence of stable marriages. Another concept used to study one-to-one matching problems is the vNM stable set (von Neumann and Morgenstern 1944), a set-valued concept that imposes both internal and external stability. A set of matchings is a vNM stable set if (internal stability) no matching inside the set is directly dominated by a matching belonging to the set, and (external stability) any matching outside the set is directly dominated by some matching belonging to the set. Definition 3. A set of matchings V⊆Mis a vNM stable set if the following conditions are met: (i) For all μ∈V, there does not exist μ∈Vsuch that μ>μ. (ii) For all μ/∈V,thereexistsμ∈Vsuch that μ>μ . Definition 3 gives us the definition of a vNM stable set V(<).Ehlers (2007)studies the properties of the vNM stable sets in one-to-one matching problems using a different enforceability notion. Given a matching μ, a coalition S⊆Nis said to be able to enforce a matching μover μif μ(S) =S. He shows that the core is a subset of any vNM stable set when using this last enforceability notion.7Example 1 illustrates his main result. 6Setting |S|≤2in the definition of the core, we obtain the concept of pairwise stability defined in Gale and Shapley (1962) that is equivalent to the core in one-to-one matchings (due to the fact that the existence of any blocking coalition induces the existence of a blocking pair as already mentioned before). 7The notion of enforceability used by Ehlers (2007) is very strong. Let μbe the matching where all agents are single and let μbe the matching where μ(m1)=w1,μ(m2)=w2,μ(m3)=w3, (assuming |M|=|W|). Let S={m1w1}. Then, according to the enforceability notion of Ehlers (2007), Scan enforce μover μ.Inparticular,Snot only enforces being matched together, but its members can also change the matching structure for all other agents in an arbitrary way. To avoid this arbitrariness, we use another enforceability notion. Notice that under our enforceability notion, the vNM stable set in Definition 3 contains the vNM stable set defined in Ehlers (2007).
504 Mauleon, Vannetelbosch, and Vergote Theoretical Economics 6 (2011) Example 1(Ehlers 2005). Let M={m1m2m3}and W={w1w2w3}.LetPbe such that P(m1)P(m 2)P(m 3)P(w1)P(w 2)P(w 3) w1w2w3m2m3m1 w2w3w1m3m1m2 m1m2m3w1w2w3 w3w1w2m1m2m3 Let μ=m1m2m3 w1w2w3μ =m1m2m3 w2w3w1μ =m1m2m3 w3w1w2 It can be shown that the core contains a unique matching C(P) ={μ}and that the unique vNM stable set (when using the notion of enforceability of Ehlers 2007)is V(<)={μμμ}.♦ In Example 1, the matchings μand μ belong to the unique vNM stable set because μdoes not directly dominate either μor μ even though μand μ are not individually rational matchings (either all women or all men prefer to become single). However, farsighted women may decide first to become single in the expectation that further marriages form, leading to μ. Women prefer μto μand once everybody is divorced, men and women prefer μto the situation where everybody is single. A similar reasoning can be made for μ with the roles of men and women reversed. Then we may say that (i) μ farsightedly dominates μ, (ii) μfarsightedly dominates μ, and (iii) V(<)={μμμ} is not a reasonable candidate for being a vNM farsightedly stable set. In what follows, we use the notion of enforceability given in Definition 1 unless otherwise mentioned. 3. von Neumann–Morgenstern farsighted stability The indirect dominance relation is first introduced by Harsanyi (1974), but is later formalized by Chwe (1994). It captures the idea that coalitions of agents can anticipate the actions of other coalitions. In other words, the indirect dominance relation captures the fact that farsighted coalitions consider the end matching that their deviations may lead to. A matching μindirectly dominates μif μcan replace μin a sequence of matchings, such that at each matching along the sequence, all deviators are strictly better off at the end matching μcompared to the status quo they face. Formally, indirect dominance is defined as follows. Definition 4. A matching μis indirectly dominated by μ,orμμ,ifthereexistsa sequence of matchings μ0μ1μK(where μ0=μand μK=μ) and a sequence of coalitions S0S1SK−1such that for any k∈{1K}, the following conditions are met: (i) For all i∈Sk−1,μKiμk−1.
Theoretical Economics 6 (2011) vNM farsightedly stable sets 505 (ii) Coalition Sk−1can enforce the matching μkover μk−1. Definition 4 gives us the definition of indirect dominance. The indirect dominance relation is denoted by . Direct dominance is obtained by setting K=1in Definition 4. Obviously, if μ<μ , then μμ. Diamantoudi and Xue (2003) investigate farsighted stability in hedonic games (of which one-to-one matching problems are a special case), introducing the notion of the coalitional largest farsighted conservative stable set, which coincides with the largest consistent set of Chwe (1994). Definition 5. The set Z()⊆Mis a consistent set if μ∈Z()if and only if ∀μS such that Scan enforce μover μ,∃μ ∈Z(),whereμ=μ or μμ such that μ(i) ≺iμ(i) for some i∈S. The largest consistent set (P) is the consistent set that contains any consistent set. Interestingly, Diamantoudi and Xue (2003) show that in hedonic games with strict preferences, (i) any partition belonging to the core indirectly dominates any other partition and (ii) core partitions are always contained in the largest consistent set.8Thus, in one-to-one matching markets, for all μ= μwith μ∈C(P),wehavethatμμand C(P) ⊆(P). However, the largest consistent set may contain more matchings than those matchings that are in the core as is shown in Example 2. Example 2. Let M={m1m2m3}and W={w1w2w3}.LetPbe such that P(m1)P(m 2)P(m 3)P(w1)P(w 2)P(w 3) w1w2w2m2m1m3 w2w1w1m3m2m1 w3w3w3m1m3m2 m1m2m3w1w2w3 Let μ1=m1m2m3 w2w1w3μ 2=m1m2m3 w1w2w3 Note that μ1is the unique element in the core of this matching problem and it belongs to the largest consistent set, (P). Indeed, since μ1∈C(P),wehavethatμ1μfor all μ= μ1.Weshownowthat{μ1μ2}is a consistent set and hence μ2also belongs to (P). To do so, we have to show that ∀μS such that Scan enforce μover μ2,∃μ∈{μ1μ2}, where μ=μor μμ, such that μ2(i) ≺iμ(i) for some i∈S. The only profitable deviation from μ2is the one in which {m3w1}get married at μ, leaving w3and m1single. Since μ1∈C(P),wehaveμ1μ, and note that one of the deviating players, m3,isnot 8The largest consistent set always exists, is nonempty, and satisfies external stability (i.e., any matching outside the set is indirectly dominated by some matching belonging to the set). But a consistent set does not necessarily satisfy the external stability condition. Only the largest consistent set is guaranteed to satisfy external stability.
506 Mauleon, Vannetelbosch, and Vergote Theoretical Economics 6 (2011) better off at μ1compared to μ2; i.e., μ1(m3)∼m3μ2(m3). Consequently, {μ1μ2}is a consistent set and the largest consistent set may contain matchings that do not belong to the core. ♦ Another way to introduce farsighted stability is to replace direct by indirect dominance in the definition of the core. Diamantoudi and Xue (2003)definethefarsighted core (or abstract core) as C(P)={μ∈M|μ∈Msuch that μμ} Since μ<μ implies μμ,itmustbethatC(P)⊆C(P). The farsighted core C(P)is too exclusive because it does not consider the credibility of the dominating alternative and, hence, it can often be empty. For instance, it follows immediately from the result that any partition belonging to the core indirectly dominates any other partition, that C(P)is empty when there are at least two elements in C(P). But even when C(P)is a singleton, C(P)can be empty. In Example 2, the matching in which the men (m1m2m3)are matched to (w1w2w3)indirectly dominates the core stable matching where the men (m1m2m3)are matched to (w2w1w3)and hence the farsighted core is empty. The farsighted core exists only when the core is unique and no other matching indirectly dominates the core. But this requires that one needs to restrict the preferences for the farsighted core to exist, and this severely limits its usefulness for general (strict) preferences. Now we give the definition of a vNM farsightedly stable set put forth by Chwe (1994). Definition 6. A set of matchings V⊆Mis a vNM farsightedly stable set with respect to Pif the following conditions are met: (i) For all μ∈V, there does not exist μ∈Vsuch that μμ. (ii) For all μ/∈V,thereexistsμ∈Vsuch that μμ. Definition 6 introduces the notion of a vNM farsightedly stable set V().Part(i) in Definition 6 is the internal stability condition: no matching inside the set is indirectly dominated by a matching belonging to the set. Part (ii) is the external stability condition: any matching outside the set is indirectly dominated by some matching belonging to the set.9 As shown in Greenberg (1990)andXue (1998), the vNM farsightedly stable set assumes optimistic behavior. To see this, suppose that players behave consistently with indirect dominance and start bargaining, given a matching μ∈Mas the status quo. Let M(μ) ={μ}∪{μ∈M|μμ}denote the set of all possible matchings that can be 9Diamantoudi and Xue (2007) extend the notion of the equilibrium binding agreement (EBA) (see Ray and Vohra 1997) with unrestricted coalitional deviations by using the vNM stable set with the indirect dominance relationship. They study whether the agents reach efficient agreements when they can negotiate openly and form coalitions. They show that, while the extended notion of the EBA facilitates the attainment of efficient agreements, inefficient agreements can arise, even if utility transfers are possible. However, no characterization of the vNM stable set with the indirect dominance relationship is provided.
Theoretical Economics 6 (2011) vNM farsightedly stable sets 513 Definition 7. A hospital h’s preference ordering P(h)satisfies substitutability if for any set S⊆Icontaining students iand i(i= i), if i∈Ch(SP(h)), then i∈Ch(S \{i}P(h)). A preference profile Pis substitutable if, for each hospital h, the preference ordering P(h) satisfies substitutability. That is, if hhas substitutable preferences, then if its preferred set of students from S includes i, so does its preferred set of students from any subset of Sthat still includes i. We assume that hospitals’ preferences satisfy the property of substitutability.15 Let Pbeapreferenceprofileandletμbe a matching. We say that μis individually rational if μ(i) iifor all i∈Iand if μ(h) =Ch(μ(h)P(h)) for all h∈H.Thatis, μis individually rational if no agent can unilaterally improve over its assignment in μ (students by choosing to remain unemployed and hospitals by firing some of their students). A student–hospital pair (ih) blocks μif i/∈μ(h),i∈Ch(μ(h) ∪{i}P(h)),and hiμ(i); i.e., if iand hare not matched through μ, hospital hwants to enroll i(possibly after firing some of its current students in μ(h))andstudentiprefers hospital hover her current match μ(i).Apair(Sh) ∈2I×Hblocks∗μif hiμ(i) for all i∈Sand there is S⊆μ(h) such that [S∪S] hμ(h).Inwords,(S h) blocks∗μif hospital his willing to enroll the students in S(possibly after firing some of its current students in μ(h))andall students iin Sprefer hover their current match μ(i). This notion of blocking was used by Echenique and Oviedo (2004). Definition 8. A matching μis stable if it is individually rational and there is no student–hospital pair that blocks μ. A matching μis stable∗if it is individually rational and there is no pair (S h) that blocks∗μ. Given a preference profile P, we denote the set of stable matchings by (P) and denote the set of stable∗matchings by ∗(P).Echenique and Oviedo (2004) show that ∗(P) ⊆(P). Given a preference profile P,thestrong core is the set of matchings μ for which there is no H⊆H,I⊆Iwith H∪I= ∅,andμ∈Msuch that (i) for all i∈Iand h∈H,μ(i) ∈Hand μ(h) ⊆I; (ii) for all i∈Iand h∈H,μ(i) iμ(i) and μ(h) hμ(h); and (iii) there is j∈H∪Iwith μ(j) jμ(j). We denote by Cw(P) the strong core. According to this definition, members of the deviating coalition need only to be weakly better off and one member needs to be strictly better off.16 Echenique and Oviedo (2004) show that the set of stable∗matchings equals the strong core: ∗(P) =Cw(P). However, the strong core may not coincide with the core (see Roth and Sotomayor 1990).17 Let Sμ(h) denote the power set of the set μ(h). We now adapt the definition of enforceability to many-to-one matching problems. 15A hospital’s preferences over group of students are responsive if, for any two assignments that differ in only one student, it prefers the assignment containing the more preferred student. Note that responsive preferences have the substitutability property. 16On the contrary, in the definition of the core, all members of the deviating coalition should be strictly better off. 17Roth and Sotomayor (1990) show that if hospitals’ preferences are substitutable, then the set of stable matchings, (P), equals the strong core. In one-to-one matching problems with strict preferences, the set of stable matchings coincides with the core, which is equal to the strong core.
514 Mauleon, Vannetelbosch, and Vergote Theoretical Economics 6 (2011) Definition 9. Given a matching μ, a coalition S⊆Nis said to be able to enforce a matching μover μif the following conditions hold: (i) μ(h) /∈Sμ(h) ∪{h}implies μ(h)\ μ(h) ∪{h}⊂Sand (ii) μ(h) ∈Sμ(h) ∪{h},μ(h) = μ(h), implies either hor μ(h) \μ(h) or htogether with a nonempty subset of μ(h) \μ(h) should be in S. Condition (i) says that any new match in μthat contains different partners than in μ should be such that hand the different partners of hbelong to S. Condition (ii) states that so as to leave some (or all) positions of one existing match in μunfilled, either h or the students leaving such positions or hand some nonempty subset of such students should be in S.18 We now provide a condition that characterizes indirect dominance in many-to-one matching problems. Similarly to one-to-one matching problems, we have that an individually rational matching μindirectly dominates μif and only if there does not exist apair(Sh) ∈2I×H,withS⊆μ(h),thatblocks∗μ. In other words, an individually rational matching μdoes not indirectly dominate another matching μif and only if there exists a pair (Sh) that blocks∗μ. Lemma 4. Consider any two individually rational matchings μμ∈M.Thenμμif and only if there does not exist a pair (S h) ∈2I×H,withS⊆μ(h),thatblocks ∗μ; i.e., such that hiμ(i) for all i∈Sand there is S⊆μ(h) such that [S∪S] hμ(h). In the following discussion, we extend our characterization of the vNM farsightedly stable set for one-to-one matching problems to many-to-one matching problems with substitutable preferences. Indeed, when preferences are substitutable, Roth and Sotomayor (1990) show that the set of stable matchings (that coincides with the strong core and with the set of stable∗matchings) is always nonempty. We now show that the only possible vNM farsightedly stable sets are singleton sets whose elements are the stable∗ matchings. Theorem 3. In a many-to-one matching problem with substitutable preferences, a set of matchings is a vNM farsightedly stable set if and only if it is a singleton set and its element belongs to the strong core Cw(P). The proof of Theorem 3 follows the proof of Theorem 2 but replacing now Lemma 1 by Lemma 4 and proving that μ 1always exists. Thus, our characterization of the vNM farsightedly stable set for one-to-one matching problems extends to many-to-one matching problems with substitutable preferences. This result contrasts with Ehlers (2007), who shows that there need not be any relationship between the vNM stable sets of a many-to-one matching problem with responsive preferences and its associated 18Roth and Sotomayor (1990) use another definition of enforceability so as to define when a matching weakly dominates another matching. The only difference is that Condition (i) in Roth and Sotomayor (1990) says that any new match in μthat contains different partners than in μshould be such that hand the partners of hin μ(that is, μ(h) instead μ(h)\μ(h))belongtoS. Since in the definition of indirect dominance, we impose that all the deviators are strictly better off, here we require only the different partners of hto belong to S.
Theoretical Economics 6 (2011) vNM farsightedly stable sets 515 one-to-one matching problem. We also show that if there is a matching of a many-toone matching problem with substitutable preferences that is in the core but not in the strong core, then this matching is never a vNM farsightedly stable set. 6. Conclusion We characterize the vNM farsightedly stable sets in one-to-one matching problems: a set of matchings is a vNM farsightedly stable set if and only if it is a singleton set and its element is in the core. Thus, we provide an alternative characterization of the core in one-to-one matching problems. Finally, we show that our main result is robust to manyto-one matching problems with substitutable preferences: a set of matchings is a vNM farsightedly stable set if and only if it is a singleton set and its element is in the strong core. Appendix Proof of Lemma 1.LetB(μμ) be the set of men and women who are strictly better off in μthan in μ. Accordingly, let I(μμ)and W(μ μ)be the set of men and women who are indifferent between μand μ, and worse off in μthan in μ, respectively. (⇒) Assume, to the contrary, that μμand that there is a pair {i μ(i)}such that both prefer μto μ.Forμto indirectly dominate μ,itmustbethatior μ(i) get divorced along the path from μto μ. But both iand μ(i) belong to W(μ μ), and then they never divorce. Hence μ μ, a contradiction. (⇐)Weprove⇐by showing that μμif the above condition is satisfied. Assume that for all pairs {i μ(i)}such that μ(i) = μ(i), either ior μ(i) or both belong to B(μμ). Notice that every agent isingle in μthat accepts a match with someone else in μalso belongs to B(μμ)since μis individually rational. Next construct the following sequence of matchings from μto μ:μ0μ1μ2(where μ0=μ, μ1={μ1(i) =i,μ1(μ(i)) =μ(i) for all i∈B(μμ),andμ1(j) =μ(j) otherwise}, and μ2=μ). Also construct the following sequence of coalitions S0S1with S0=B(μμ) and S1=B(μμ)∪{μ(i) for i∈B(μμ)}. Then coalition S0can enforce μ1over μ0and coalition S1can enforce μ2over μ1.Moreover,μ2μ0for S0and μ2μ1for S1because every mate of i∈B(μμ)in μ2(in μ)alsoprefers his or her mate in μ2to being single in μ1. Indeed, for every i∈B(μμ), either μ2(i) ∈B(μμ), and hence both prefer μ2to μ1,orμ2(i) ∈W(μ μ).Inthislast case, μ2(i) must have lost his or her mate in μ0and μ0(μ2(i)) must belong to B(μμ) since otherwise μ0(μ2(i)) and μ2(i) would form a blocking pair of μ2, and this, by assumption, is not possible. Hence μ2(i) must be single in μ1.Then since μ2is individually rational, μ2(i) must prefer accepting his or her mate in μ2 to remaining single at μ1.So,wehavethatμμ. Proof of Lemma 2. Suppose not. Then there exists i∈Nthat prefers to be single than to be married to μ(i) in μ. Since μμand μis individually rational, we have that iwas
516 Mauleon, Vannetelbosch, and Vergote Theoretical Economics 6 (2011) either single at μor matched to μ(i) ii. But then in the sequence of moves between μand μ,thefirsttimeihas to move she/he was either matched with μ(i) or single and, hence, icannot belong to a coalition Sk−1that can enforce the matching μkover μk−1and such that all members of Sk−1prefer μto μk−1, contradicting the fact that μμ. Proof of Theorem 1. We only need to verify condition (ii) in Definition 6: for all μ= μ,wehavethatμμ. Since μ∈C(P), we know that ∀μ= μ,i∈Mand j∈W such that μ(i) =jand μμfor both iand j. Since μis individually rational, we have from Lemma 1 that μμ. Proof of Theorem 2. Notice that if V()⊆C(P),thenV()is a vNM farsightedly stable set only if V()is a singleton set {μ}with μ∈C(P).FromTheorem 1, we know that for all μ= μ,μμ. Suppose now that V()C(P). Then, either V()∩C(P)= ∅or V()∩C(P)=∅. Suppose first that V()∩C(P) = ∅.Letμ∈V()∩C(P),andμ∈V()with μ/∈C(P).Then,byTheorem 1,wehavethatμμ, violating the internal stability condition. Suppose now that V()∩C(P) =∅. Then we show that V()is not a vNM farsightedly stable set because either the internal stability condition (condition (i) in Definition 6) or the external stability condition (condition (ii) in Definition 6) is violated. Assume first that V()={μ}is a singleton. Since μ/∈C(P), there exists a deviating coalition Sin μand a matching μ∈Msuch that μiμfor all i∈Sand Scan enforce μover μ.Thenμ μand the external stability condition is violated. Assume now that V()contains more than one matching that does not belong to C(P). Take any matching μ1∈V(). Since μ1/∈C(P), there exists at least a pair of agents {i j}such that μ1(j) = i(or a single agent {i}) and a matching μ 1∈Msuch that μ 1μ1for both iand j(or μ 1μ1for i), and {i j}(or i) can enforce μ 1over μ1, i.e., such that μ 1(j) =i(or μ 1(i) =i). Let S(μ1)be the set of blocking pairs of μ1.Consider the deviation from μ1to μ 1of the subset of blocking pairs S(μ1)⊆S(μ1),whereS(μ1) contains the maximum number of blocking pairs and is such that the subset S(μ1)\ S(μ1)does not contain any blocking pair of μ 1. Wefirstprovethatsuchamatching always exists. Claim 1. For any matching μ1/∈C(P), there always exists a matching μ 1∈Mthat directly dominates μ1and that can be enforced over μ1by the blocking pairs S(μ1),and such that μ 1is not blocked by any pair in S(μ1)\S(μ1). Proof. We prove the existence of μ 1by construction. Define Mto be the set of men who belong to some blocking pair of μ:M={i∈M|∃j∈W∪{i}such that {i j}∈S(μ1)}. Equally, define Wto be the set of women who belong to some blocking pair of μ1:W= {j∈W|∃i∈M∪{j}such that {i j}∈S(μ1)}. Consider the following restricted matching problem in which each agent only ranks those agents with whom he or she can form a deviating blocking pair. That is, the preferences of each i∈Mare only over the set W i={j∈W∪{i}such that {i j}∈S(μ1)}.
Theoretical Economics 6 (2011) vNM farsightedly stable sets 517 For each j∈W, her preferences are restricted to the set M j={i∈M∪{j}such that {i j}∈S(μ1)}.LetP(μ1)denote these restricted preferences. Then the matching problem {MWP(μ1)}has at least one stable matching (since it is a marriage market), call it μ. We define μ 1and S(μ1)as follows. Consider first the agents in Mand W.Everypair {i μ(i)}in μ(possibly i=μ(i)) such that both prefer their partner in μto their partner in μ1belongs to S(μ1)and, hence, both iand μ(i) move from μ1to μ 1becoming a couple (as in μ). Every single agent at μpreferring being married at μ1rather than being single at μdoes not belong to S(μ1),buttoS(μ1)\S(μ1).Everypair{i μ1(i)}in μ1with μ1(i) =μ(i) is such that i(and/or μ1(i)) belongs to S(μ1)\S(μ1)when i(and/or μ1(i)) belongs to M(belongs to W). Consider now all agents who do not belong to either Mor W. They do not belong to a pair of S(μ1)(they do not move themselves, although they can lose their match in the move from μ1to μ 1if they were initially matched to some of the deviating players in some of the pairs of S(μ1)). Clearly, the subset S(μ1)\S(μ1) does not contain any blocking pair of μ 1, because otherwise μwould not be a stable matching for the restricted matching problem {MWP(μ1)}. Since the set of single agents in any stable matching is always the same, then S(μ1)contains the maximum possible number of blocking pairs such that S(μ1)\S(μ1)does not contain any blocking pair of μ 1. Now, for V()to be a vNM farsightedly stable set, we need the following conditions to be satisfied: (i) For any other matching μ2∈V(),μ2= μ1, it should be that μ1 μ2and μ2 μ1. (ii) For all μ/∈V(), there should exist μ∈V()such that μμ(in particular, we need that there exists a matching μ2∈V()such that μ2μ 1for each matching, like μ 1, that can be enforced by any subset of blocking pairs of any matching in V()). We show that a V()containing more than one matching, none of them in C(P),is not a vNM farsightedly stable set because one of the above conditions is not satisfied. Let μ1∈V(). We know by Claim 1 that there exists a matching μ 1that can be enforced from μ1by the blocking pairs in S(μ1)and such that μ 1>μ 1(and μ1 μ 1). Notice that μ 1/∈V(). By condition (ii) in Definition 6, there exists a matching μ2∈ V()such that μ2μ 1. Condition (i) in Definition 6 implies that μ1 μ2and μ2 μ1. We prove that condition (i) is violated. Two cases should be considered. 1. Assume that μ2does not contain any blocking pair of μ1; i.e., {i μ2(i)}such that {i μ2(i)}∈S(μ1).Ifμ1is individually rational, we have by Lemma 1 that μ1μ2, violating condition (i) in Definition 6.Otherwise,ifμ1is not individually rational, consider the deviation from μ1to μ 1,whereanyagentiwho prefers being single to being married to μ1(i),divorcesfromμ1(i), while the other agents do not move. Then μ 1>μ 1(and μ1 μ 1). By condition (ii) in Definition 6,thereexistsamatching μ2∈V()such that μ2μ 1. But then we also have that μ2μ1, since the
518 Mauleon, Vannetelbosch, and Vergote Theoretical Economics 6 (2011) agents who divorce from μ1to μ 1never marry someone else and become worse off than being single. Hence, the internal stability condition is violated and V()is not a vNM farsightedly stable set. So V()cannot contain nonindividually rational matchings. 2. Assume that μ2contains some blocking pair(s) of μ1;thatis,∃{i μ2(i)}such that {i μ2(i)}∈S(μ1). Notice that, in this case, we have by Lemma 1 that μ1 μ2.Let S(μ1)⊆S(μ1)be the set of blocking pairs of μ1that are still matched in μ2.Consider the deviation from μ1to μ 1, where only the blocking pairs {i j}∈S(μ1)⊆ S(μ1)get married. Then μ 1>μ 1(and μ1 μ 1)andμ 1>μ 1(if μ 1= μ 1). Since μ2μ 1,wealsohavethatμ2μ 1, because the only difference between μ 1and μ 1 is that at μ 1, the rest of the blocking pairs of μ1(who are not still matched at μ 1and who divorce from μ 1to μ2) get married. Hence, μ 1does not contain any blocking pair of μ2. Then, since μ2μ 1, we also have that μ2μ1, violating condition (i) in Definition 6. Proof of Lemma 3. Suppose to the contrary that there exists a matching μwith μ= μ∗ andsuchthatμμ∗. Take the lowest jsuch that Sjis the top coalition of N\l<j Sland mjis better off in μ.Thenmjmust be matched in μto μ∗(ml)for some l<j.Otherwise Sjwould not be a top coalition of N\l<j Sl.Moreover,μ∗(ml)must be worse off in μ compared to μ∗, because, otherwise, (mjμ∗(ml)) would be a blocking pair of μ∗.But then mlmust be better off in μ, because, otherwise, (mlμ∗(ml)) =Slblocks μ.Butthen mlis better off in μand l<j, a contradiction. Proof of Lemma 4.(⇒) Assume to the contrary that μμand that there exists a pair (Sh) ∈2I×Hthat blocks∗μ.Thatis,thepair(Sh) is such that hiμ(i) for all i∈S,S⊆μ(h),andthereisS⊆μ(h) (S⊆μ(h))suchthat[S∪S] hμ(h).At no step along the path between μand μdoes any i∈[S∪S]leave h.So,along the path between μand μ, hospital hmust at some point get rid of any i∈S. Since μis individually rational and [S∪S] hμ(h),thenμ(h) hμ(h) and h never initiates a move at μso as to go to μ. Hence, some or all of the students in μ(h) \[S∪S]who prefer μto μleave h. Since μis individually rational, any intermediate matching obtained once some students in μ(h) \[S∪S]leave hbetween μand the matching in which his only matched to [S∪S],areall preferred by hto this last matching in which his matched to [S∪S]. Soatany step along the path between μand the matching in which his only matched to [S∪S],his in a better position compared to μ.Butthenhnever has an incentive to get rid of any i∈S.Henceμ μ, a contradiction. (⇐)Weprove⇐by construction. In the first step, let anyone (student or hospital) get rid of all matches in μif they are better off at μ. After this step, only hospitals that are (weakly) worse off at μcompared to μmay still have some students they are matched to (called it Shwith Sh⊆μ(h) for some h). In the second step, let these hospitals get rid of all their matches (all i∈Sh). They want to do so, since, by assumption, they are better off at μcompared to being matched only to Sh.After
Theoretical Economics 6 (2011) vNM farsightedly stable sets 519 the second step, everyone is alone. In the third step, allow all matches necessary to obtain μ. This is possible since μis individually rational. Proof of Theorem 3. First, we prove that (i) if μis in the strong core, μ∈Cw(P), then {μ}is a vNM farsightedly stable set, {μ}=V(). Second, we prove that (ii) if V()⊆M is a vNM farsightedly stable set of matchings, then V()={μ}with μ∈Cw(P). (i) We only need to verify condition (ii) in Definition 6: for all μ= μ,wehavethat μμ. Since μ∈Cw(P) =∗(P), we know that ∀μ= μ, there does not exist a pair (Sh) ∈2I×H,withS⊆μ(h),suchthathiμ(i) for all i∈S,andthereis S⊆μ(h) (S⊆μ(h))suchthat[S∪S] hμ(h). Since μis individually rational, we have from Lemma 4 that μμ. (ii) The proof runs exactly along the same lines as the proof of Theorem 2 by simply proving that V()cannot contain only matchings that do not belong to the strong core. Indeed, assume now that V()contains more than one matching19 that does not belong to the strong core Cw(P). Take any matching μ1∈V(),whereμ1/∈Cw(P).Let S(μ1)be the set of blocking∗pairs of μ1.Thatis,S(μ1)contains the pairs (S h) ∈2I×H, such that hiμ1(i) for all i∈S,andthereisS⊆μ1(h) such that [S∪S] hμ1(h).Consider the deviation from μ1to μ 1of the subset of blocking∗pairs S(μ1)⊆S(μ1),where S(μ1)contains the maximum number of blocking∗pairs and is such that the subset S(μ1)\S(μ1)does not contain any blocking∗pair of μ 1. We now establish formally that μ 1exists. We do so by making use of the property of substitutable preferences, which allows us to make use of the fact that a stable matching exists. Claim 2. For any matching μ1/∈Cw(P), there always exists a matching μ 1∈M,which directly dominates μ1, that can be enforced over μ1by the blocking∗pairs S(μ1)and such that μ 1is not blocked∗by any pair in S(μ1)\S(μ1). Proof.DefineHto be the set of hospitals that belong to some blocking∗pair of μ: H={h∈H|either μ1(h) /∈Ch(μ1(h)P(h)) or ∃S⊆Isuch that (hS) ∈S(μ1)}. Equally, define Ito be the set of students who belong to some blocking∗pair of μ:I={i∈I| either iμ1(i) or ∃h∈Hsuch that (hS) ∈S(μ1)with i∈S}. Consider the following restricted matching problem in which each agent ranks only those agents with whom she can form a deviating blocking∗pair. That is, the preferences of each h∈Hare only over the set I h={S⊆Isuch that (hS) ∈S(μ1)}.Foreach i∈I, her preferences are restricted to the set H i={h∈H∪{i}such that (hS) ∈S(μ1) with i∈S}.LetP(μ1)denote these restricted preferences. Notice that the restricted preferences P(μ1)also satisfy the substitutability property and, therefore, the matching problem {HIP(μ1)}has at least one stable matching, call it μ.Thendefineμ 1and 19Of course, if V()={μ}with μ/∈Cw(P), then there exists a matching μand a pair (Sh) ∈2I×H, with S⊆μ(h),suchthathiμ(i) for all i∈S, and there is S⊆μ(h) such that [S∪S] hμ(h).Thenμ μ and the external stability condition is violated.
520 Mauleon, Vannetelbosch, and Vergote Theoretical Economics 6 (2011) S(μ1)as follows. All agents who do not belong to either Hor Ido not belong to S(μ1) (they do not move themselves, although they can lose their match in the move from μ1 to μ 1if they were initially matched to some of the deviating players in some blocking pair of S(μ1)). Now consider the people in Hand I.Everypair{hμ(h)}of μbelongs to S(μ1)and, hence, both hand μ(h) move from μ1to μ 1to their match in μ,with μ 1(h) =[S∪μ(h)]and S⊆μ1(h) such that [S∪μ(h)] hμ1(h). Every single student (every hospital that has some places unfilled) at μwho prefers to be unemployed (that have some places unfilled) at μrather than to be in a hospital (hiring some students) at μ1belongs to S(μ1)and we let them become unemployed (leaving some places unfilled) in the move from μ1to μ 1. Every single student (hospital) at μwho prefers to be employed (prefers hiring some students) at μ1rather than to be unemployed (to have some places unfilled) at μdoes not belong to S(μ1),buttoS(μ1)\S(μ1).Everypair {hμ1(h)}of μ1with μ1(h) =μ(h) is such that h(and/or μ1(h)) belongs to S(μ1)\S(μ1) when h(and/or μ1(h)) belongs to H(belongs to I). Clearly, the subset S(μ1)\S(μ1) does not contain any blocking∗pair of μ 1, because, otherwise, μwould not be a stable matching for the matching problem {HIP(μ1)}. Once we show the existence of μ 1, the proof follows the proof of Theorem 2,butnow Lemma 1 is replaced by Lemma 4. References Banerjee, Suryapratim, Hideo Konishi, and Tayfun Sönmez (2001), “Core in a simple coalition formation game.” Social Choice and Welfare, 18, 135–153. [511] Chwe, Michael S. Y. (1994), “Farsighted coalitional stability.” Journal of Economic Theory, 63, 299–325. [500,504,505,506,507] Diamantoudi, Effrosyni and Licun Xue (2003), “Farsighted stability in hedonic games.” Social Choice and Welfare, 21, 39–61. [500,505,506,508] Diamantoudi, Effrosyni and Licun Xue (2007), “Coalitions, agreements and efficiency.” Journal of Economic Theory, 136, 105–125. [501,506] Echenique, Federico and Jorge Oviedo (2004), “Core many-to-one matchings by fixedpoint methods.” Journal of Economic Theory, 115, 358–376. [513] Ehlers, Lars (2005), “von Neumann–Morgenstern stable sets in matching problems.” Discussion Paper 12-2005, CIREQ. [504] Ehlers, Lars (2007), “von Neumann–Morgenstern stable sets in matching problems.” Journal of Economic Theory, 134, 537–547. [499,500,503,504,507,509,512,514] Gale, David and Lloyd S. Shapley (1962), “College admissions and the stability of marriage.” American Mathematical Monthly, 69, 9–15. [499,503] Greenberg, Joseph (1990), TheTheoryofSocialSituations. Cambridge University Press, Cambridge. [501,506,507]
Theoretical Economics 6 (2011) vNM farsightedly stable sets 521 Harsanyi, John C. (1974), “An equilibrium-point interpretation of stable sets and a proposed alternative definition.” Management Science, 20, 1472–1495. [500,504] Herings, P. Jean Jacques, Ana Mauleon, and Vincent J. Vannetelbosch (2004), “Rationalizability for social environments.” Games and Economic Behavior, 49, 135–156. [500] Herings, P. Jean Jacques, Ana Mauleon, and Vincent J. Vannetelbosch (2009), “Farsightedly stable networks.” Games and Economic Behavior, 67, 526–541. [500] Jackson, Matthew O. and Alison Watts (2002), “The evolution of social and economic networks.” Journal of Economic Theory, 106, 265–295. [510] Klijn, Flip and Jordi Massó (2003), “Weak stability and a bargaining set for the marriage model.” Games and Economic Behavior, 42, 91–100. [509] Konishi, Hideo and Debraj Ray (2003), “Coalition formation as a dynamic process.” Journal of Economic Theory, 110, 1–41. [509,510] Ray, Debraj and Rajiv Vohra (1997), “Equilibrium binding agreements.” Journal of Economic Theory, 73, 30–78. [506] Roth, Alvin E. and Marilda Sotomayor (1990), Two-Sided Matching: A Study in GameTheoretic Modelling and Analysis, volume 18 of Econometric Society Monographs. Cambridge University Press, Cambridge. [500,502,513,514] Roth, Alvin E. and John H. Vande Vate (1990), “Random paths to stability in two-sided matching.” Econometrica, 58, 1475–1480. [510] Sotomayor, Marilda (1996), “A non-constructive elementary proof of the existence of stable marriages.” Games and Economic Behavior, 13, 135–137. [503] von Neumann, John and Oskar Morgenstern (1944), Theory of Games and Economic Behavior. Princeton University Press, Princeton. [503] Xue, Licun (1998), “Coalitional stability under perfect foresight.” Economic Theory, 11, 603–627. [500,501,506,507] Submitted 2009-2-13. Final version accepted 2010-11-28. Available online 2010-11-28.