JEL Classification: D82, L51
Introduction
In many labor markets, firms hire teams of workers, and the surplus generated by a team of workers exhibit complementarity. Such complementarities lead to settings where a stable outcome may not exist, a fundamental desiderata in matching theory. In the many-to-one job-matching model, stability was first studied by Kelso and Crawford [9 ] , who showed the existence of a stable outcome when utility functions of firms over workers satisfy the gross substitutes condition – see [6 , 11 ] for recent generalizations of this result.
In this paper, we seek an alternate solution: the vNM stable set, which was introduced as a set-valued solution concept in their seminal book by von Neumann and Morgenstern [20 ] . Unlike core, where each outcome in the core is stable, individual outcomes in a vNM stable set have no meaning. It is the entire set that is stable. This is the reason von Neumann and Morgenstern [20 ] interpret stable sets as “standards of behavior”. A vNM stable set is a set of individually rational (IR) outcomes (an outcome is a matching and payoffs to firms and workers), which are required to be consistent using a domination relation over the set of all IR outcomes.3 vNM stability requires two consistency properties: (a) internal stability – outcomes inside the vNM stable set do not dominate each other; (b) external stability – each IR outcome not in the vNM stable set is dominated by some outcome inside.
In the job-matching model, a vNM stable set could be interpreted as a menu of IR outcomes/contracts (matching and non-negative payoff splits) that firms and workers may choose from. This menu does not undermine itself (internal stability) and anything not on the menu has a counter-contract on the menu.
Our main result shows that a vNM stable set in the job-matching model exists whenever the efficient matching is unique. The set of all IR and efficient outcomes forms a vNM stable set in that case. Thus, even when teams of workers exhibit significant complementarities, a vNM stable set exists, though a stable outcome may not exist. We show that if there are multiple efficient matchings, then (a) the vNM stable set may not exist; and (b) even when it exists, it may contain inefficient outcomes. However, by requiring the vNM stable set to be rich in a certain sense, we establish that the set of IR and efficient outcomes is essentially the unique vNM stable set. Hence, a rich vNM stable set mandates firms and workers to agree on a menu of contracts that contains only efficient matchings but leaves the division of surplus completely flexible.
Our richness is the following requirement. Call a vNM stable set V \mathcal{V} V rich if for every outcome (with matching, say, μ \mu μ ) in V \mathcal{V} V , the firm-optimal IR outcome and the worker-maximal IR outcomes corresponding to μ \mu μ belong to V \mathcal{V} V .4 A rich vNM stable set exists if and only if the set of efficient matchings is essentially unique . In that case, the set of all IR and efficient outcomes forms the unique rich vNM stable set. Unlike vNM stable sets, rich vNM stable sets exhibit simpler structure, and are easier to analyze. In general, vNM stable sets are known to be difficult to exist and analyze. Quoting Aumann [1 ] :
What has prevented the (vNM stable set) theory from being more successful is that it is so difficult to work with. Finding stable sets involves a new tour de force of mathematical reasoning for each game or class of games that is considered.
Our results contrast with the results in the matching literature without transfer, where a unique vNM stable set exists in the one-to-one matching model [5 , 21 ] .5
The job-matching model induces a transferrable utility (TU) cooperative game. The study of vNM stable sets in general cooperative games has a long history – see Aumann [1 ] for a very early survey and Subiza et al. [19 ] for a recent contribution. This literature defines outcomes to be imputations (IR and efficient outcomes) of the cooperative game. In the job-matching model, this will loosely translate to finding a vNM stable set in the set of efficient and individually rational outcomes. This approach is taken in Núñez and Rafels [15 ] , who analyze the assignment game (one-to-one job-matching model of Shapley and Shubik [18 ] ) and identify vNM stable sets. We allow for inefficient outcomes to be included in the vNM stable sets. Indeed, we show that vNM stable sets may contain inefficient outcomes. However, our partial converse result establishes that we get efficiency as a consequence of rich vNM stability.6
The domination relation used to define the vNM stable set reflects a myopic notion of blocking in the job-matching problem. An interesting direction of further research is to consider a farsighted notion of blocking. Farsighted notions of blocking and related vNM stable sets have been studied in matching literature without transfers by Mauleon et al. [14 ] ; Klaus et al. [10 ] ; Herings et al. (2020); Doğan and Ehlers [4 ] . The nature of dominance relation used to define vNM farsighted stable set considers a sequence of blockings, and has different implications on the structure of stable sets. In the future, we plan to investigate the structure of vNM farsighted stable set of the job-matching problem.
Set-valued stability notions have been recently used in matching with incomplete information. In an important paper, Liu et al. [13 ] introduce the notion of a self-stabilizing set and show its existence in the one-to-one matching model of Shapley and Shubik [18 ] with one-sided incomplete information. Their notion is similar to the rationalizability (iterated elimination) idea in game theory but applied to their model with incomplete information. Liu [12 ] is a recent survey of this growing literature. Pourpouneh et al. [17 ] study a similar set-valued concept of stability in the one-to-one matching model of Shapley and Shubik [18 ] where agents do not observe the outcomes of the other agents. They show that a subset of efficient and IR outcomes containing the core forms the largest self-stabilizing set. While this literature and our paper look at set-valued stability solutions, there are significant differences. First, as emphasized earlier, individual outcomes have no meaning in our solution and it is only the collection that is stable. This is not the case in this literature. Second, the set-valued stability is driven by incomplete information in these papers, but we have complete information. Third, the main method to reach a stable set in these papers is an iterated elimination procedure using the uncertainty in these models. This is not the case for us.
The paper is organized as follows. § 2 introduces the job-matching model. § 3 defines stability, a domination relation among IR outcomes, and vNM stable set. § 4 proves our first result on existence of vNM stable sets. § 6 introduces rich vNM stable sets and proves our second result on uniqueness of rich vNM stable sets. Appendix § 8 provides a detailed proof of this result, but all other omitted proofs are in Appendix § 9 . We conclude in § 7 with a discussion on our results.
Model
We study the standard model of job-matching due to Kelso and Crawford [9 ] . Let F F F be the set of firms and W W W be the set of workers. A matching is a map μ : W → F ∪ { ∅ } \mu: W \to F \cup\{\emptyset\} μ : W → F ∪ { ∅ } , where μ ( w ) \mu(w) μ ( w ) denotes the firm worker w w w is matched to – if μ ( w ) = ∅ \mu(w) = \emptyset μ ( w ) = ∅ , then it denotes an unmatched worker. For every f ∈ F f \in F f ∈ F , we denote by μ ( f ) : = { w : μ ( w ) = f } \mu(f) := \{w : \mu(w) = f\} μ ( f ) := { w : μ ( w ) = f } the set of workers matched to firm f f f in μ \mu μ .
For every f ∈ F f \in F f ∈ F and every S ⊂ W S \subset W S ⊂ W , let V f ( S ) V_f(S) V f ( S ) denote the surplus generated by matching workers in S S S to firm f f f . The surplus function V f V_f V f may be generated from value function v f : 2 W → R + v_f : 2^W \to\mathbb{R}_+ v f : 2 W → R + of the firm (with v f ( ∅ ) = 0 v_f(\emptyset) = 0 v f ( ∅ ) = 0 ) and disutility function v w : F ∪ { ∅ } → R + v_w : F \cup\{\emptyset\} \to\mathbb{R}_+ v w : F ∪ { ∅ } → R + of each worker w w w :
V f ( S ) = v f ( S ) − ∑ w ∈ S v w ( f ) V_f(S) = v_f(S) - \sum_{w \in S} v_w(f) V f ( S ) = v f ( S ) − w ∈ S ∑ v w ( f )
where v w ( ∅ ) = 0 v_w(\emptyset) = 0 v w ( ∅ ) = 0 . Combined with salaries, this generates utilities for firms and workers as in Kelso and Crawford [9 ] . However, the surplus function V f V_f V f of each firm f f f is a sufficient reduced form for our purposes. At the same time, it is important to keep in mind that since the surplus function is generated from value of firm and disutilities of workers, (a) it can take negative values; (b) it need not be monotone.
An outcome is a pair ( μ , u ) (\mu, u) ( μ , u ) , where μ \mu μ is a matching and u : W → R u : W \to\mathbb{R} u : W → R corresponds to the utility assigned to workers. An outcome specifies the utility assigned to each firm indirectly. In particular, in outcome ( μ , u ) (\mu, u) ( μ , u ) , each firm f f f receives utility equal to
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ( w ) V_f(\mu(f)) - \sum_{w \in\mu(f)} u(w) V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ( w )
Such a division of surplus is possible because utility is transferrable (using salaries) in this model. This also explicitly assumes budget-balance among a firm f f f and its matched workers μ ( f ) \mu(f) μ ( f ) . That is, transferring surplus across firms is not possible in our model. This is consistent with much of the literature on job-matching, and makes sense because firms are independent financial entities.
An economy consists of the set of firms, the set of workers, and the surplus functions:
( F , W , { V f } f ∈ F ) \left(F, W, \{V_f\}_{f \in F}\right) ( F , W , { V f } f ∈ F )
An outcome ( μ , u ) (\mu, u) ( μ , u ) is individually rational (IR) if
u ( w ) ≥ 0 ∀ w ∈ W u(w) \ge0 \qquad\forall\ w \in W u ( w ) ≥ 0 ∀ w ∈ W
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ( w ) ≥ 0 ∀ f ∈ F , V_f(\mu(f))-\sum_{w\in\mu(f)}u(w)\ge0 \qquad\forall f\in F, V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ( w ) ≥ 0 ∀ f ∈ F ,
with the first inequality an equality whenever μ ( w ) = ∅ \mu(w)=\varnothing μ ( w ) = ∅ . The two constraints correspond to IR of workers and firms respectively. Let I \mathcal{I} I be the set of all IR outcomes.
A matching μ ⋆ \mu^\star μ ⋆ is efficient if
μ ⋆ ∈ arg max μ ∑ f ∈ F V f ( μ ( f ) ) \mu^\star\in\arg\max_{\mu}\sum_{f\in F}V_f(\mu(f)) μ ⋆ ∈ arg μ max f ∈ F ∑ V f ( μ ( f ))
Clearly, in an efficient matching V f ( μ ⋆ ( f ) ) ≥ 0 V_f(\mu^\star(f))\ge0 V f ( μ ⋆ ( f )) ≥ 0 for all firms f ∈ F f\in F f ∈ F . An outcome ( μ , u ) (\mu,u) ( μ , u ) is efficient if μ \mu μ is efficient.
Stable outcomes, domination, and vNM stable sets
In this section, we define the notion of vNM stable sets. It will require us to define a relation over the set of IR outcomes. To do so, it is useful to remind the notion of blocking and stability first.
Stable outcomes
A firm f ∈ F f\in F f ∈ F and a subset of workers S ⊆ W S\subseteq W S ⊆ W block an outcome ( μ , u ) (\mu,u) ( μ , u ) if there exists a utility vector u ^ : S → R + \hat{u}:S\to\mathbb{R}_{+} u ^ : S → R + such that
u ^ ( w ) ≥ u ( w ) ∀ w ∈ S \hat{u}(w)\ge u(w)\qquad\forall w\in S u ^ ( w ) ≥ u ( w ) ∀ w ∈ S
V f ( S ) − ∑ w ∈ S u ^ ( w ) ≥ V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ( w ) V_f(S)-\sum_{w\in S}\hat{u}(w)\ge V_f(\mu(f))-\sum_{w\in\mu(f)}u(w) V f ( S ) − w ∈ S ∑ u ^ ( w ) ≥ V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ( w )
with at least one inequality strict. In other words, firm f f f and workers in S S S can be better off sharing the surplus V f ( S ) V_f(S) V f ( S ) using u ^ \hat{u} u ^ than the current outcome ( μ , u ) (\mu,u) ( μ , u ) . An outcome ( μ , u ) ∈ I (\mu,u)\in\mathcal{I} ( μ , u ) ∈ I is stable if it is not blocked by any ( f , S ) (f,S) ( f , S ) pair where f ∈ F f\in F f ∈ F and S ⊆ W S\subseteq W S ⊆ W and it is individually rational. As is well known, a stable outcome may not exist. In this model, the set of stable outcomes is also the core of the induced transferable utility cooperative game.
A domination relation among IR outcomes
The following relation among outcomes in I \mathcal{I} I is used to define vNM stability.
Definition 1. An outcome ( μ , u ) ∈ I (\mu,u) \in\mathcal{I} ( μ , u ) ∈ I is dominated by an outcome ( μ ′ , u ′ ) ∈ I (\mu',u') \in\mathcal{I} ( μ ′ , u ′ ) ∈ I , written as ( μ ′ , u ′ ) → ( μ , u ) (\mu',u') \to(\mu,u) ( μ ′ , u ′ ) → ( μ , u ) , if there exists a firm f f f such that
u ′ ( w ) ≥ u ( w ) ∀ w ∈ μ ′ ( f ) u'(w) \ge u(w) \qquad\forall w \in\mu'(f) u ′ ( w ) ≥ u ( w ) ∀ w ∈ μ ′ ( f ) V f ( μ ′ ( f ) ) − ∑ w ∈ μ ′ ( f ) u ′ ( w ) ≥ V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ( w ) V_f(\mu'(f))-\sum_{w\in\mu'(f)}u'(w) \ge V_f(\mu(f))-\sum_{w\in\mu(f)}u(w) V f ( μ ′ ( f )) − w ∈ μ ′ ( f ) ∑ u ′ ( w ) ≥ V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ( w ) with one inequality strict. We denote this as ( μ ′ , u ′ ) → f ( μ , u ) (\mu',u') \xrightarrow{f} (\mu,u) ( μ ′ , u ′ ) f ( μ , u ) .
Hence, ( μ ′ , u ′ ) → ( μ , u ) (\mu',u') \to(\mu,u) ( μ ′ , u ′ ) → ( μ , u ) requires that some firm f f f and workers μ ′ ( f ) \mu'(f) μ ′ ( f ) , who are matched to f f f in μ ′ \mu' μ ′ , block ( μ , u ) (\mu,u) ( μ , u ) (using u ′ u' u ′ ). Since it is possible that two different firms evaluate these two outcomes differently, the relation → \to → is not necessarily anti-symmetric. It also does not define a complete relation on I \mathcal{I} I . If two outcomes ( μ , u ) (\mu,u) ( μ , u ) and ( μ ′ , u ′ ) (\mu',u') ( μ ′ , u ′ ) are not comparable under → \to → , we write ( μ , u ) ↔ ( μ ′ , u ′ ) (\mu,u) \leftrightarrow( \mu',u') ( μ , u ) ↔ ( μ ′ , u ′ ) .
For every matching μ \mu μ , let I μ \mathcal{I}_{\mu} I μ denote the set of all IR outcomes associated with μ \mu μ :
I μ : = { ( μ , u ) : ( μ , u ) ∈ I } \mathcal{I}_{\mu}:=\{(\mu,u):(\mu,u)\in\mathcal{I}\} I μ := {( μ , u ) : ( μ , u ) ∈ I }
Since surplus function V f V_f V f of each firm f f f need not be non-negative, I μ \mathcal{I}_{\mu} I μ may be empty. For instance, consider an economy with only one firm and one worker and suppose the disutility of worker is larger than the value it generates for the firm, i.e., the surplus is negative. Then the matching μ \mu μ that matches the worker to the firm has no IR outcome ( μ , u ) (\mu,u) ( μ , u ) . Hence, I μ = ∅ \mathcal{I}_{\mu}=\varnothing I μ = ∅ . Here, the efficient matching is to not match the worker to the firm, in which everyone getting zero payoff is IR. In general, if μ ∗ \mu^{*} μ ∗ is an efficient matching, V f ( μ ∗ ( f ) ) ≥ 0 V_f(\mu^{*}(f)) \ge0 V f ( μ ∗ ( f )) ≥ 0 for all f f f and hence, the zero payoff vector 0 \mathbf{0} 0 (u w = 0 u_w=0 u w = 0 for all w w w ) generates the IR outcome ( μ ∗ , 0 ) (\mu^{*},\mathbf{0}) ( μ ∗ , 0 ) . Hence, I μ ∗ \mathcal{I}_{\mu^{*}} I μ ∗ is always non-empty.
Two outcomes with the same matching are not comparable according to relation → \to → . This follows immediately because for blocking the matching needs to change. We record this as an observation.
Observation 1. For every matching μ \mu μ , ( μ , u ) ↔ ( μ , u ′ ) (\mu,u) \leftrightarrow(\mu,u') ( μ , u ) ↔ ( μ , u ′ ) for all ( μ , u ) , ( μ , u ′ ) ∈ I μ (\mu,u),(\mu,u') \in\mathcal{I}_{\mu} ( μ , u ) , ( μ , u ′ ) ∈ I μ .
vNM stable sets
We now define vNM stability using the relation → \to → .
Definition 2. A set of outcomes V ⊆ I \mathcal{V} \subseteq\mathcal{I} V ⊆ I is a vNM stable set if
no outcome in V \mathcal{V} V is dominated by another outcome in V \mathcal{V} V : for every ( μ , u ) , ( μ ′ , u ′ ) ∈ V (\mu,u),(\mu',u') \in\mathcal{V} ( μ , u ) , ( μ ′ , u ′ ) ∈ V ,
( μ , u ) ↔ ( μ ′ , u ′ ) (\mu,u) \leftrightarrow(\mu',u') ( μ , u ) ↔ ( μ ′ , u ′ ) (Internal stability)
every outcome not in V \mathcal{V} V is dominated by some outcome in V \mathcal{V} V : for every ( μ , u ) ∈ I ∖ V (\mu,u) \in\mathcal{I} \setminus\mathcal{V} ( μ , u ) ∈ I ∖ V , there exists ( μ ′ , u ′ ) ∈ V (\mu',u') \in\mathcal{V} ( μ ′ , u ′ ) ∈ V such that
( μ ′ , u ′ ) → ( μ , u ) (\mu',u') \to(\mu,u) ( μ ′ , u ′ ) → ( μ , u ) (External stability)
Remark 1. We have chosen to consider the set of IR outcomes as the set of feasible outcomes. This set will include inefficient outcomes too. This is a departure from how the TU cooperative game theory literature studies vNM stable sets. In TU games studying vNM stable sets, an outcome is an imputation vector of players in the game, where an imputation vector is defined to be efficient (sum of imputations of players gives the value of the grand coalition of the TU game) and IR [16 , 15 , 19 ] . We find no reason to restrict attention to efficient outcomes in our model. Indeed, Appendix § 10 contains an example that has a vNM stable set with only inefficient outcomes. Further, the study of vNM stable sets in the matching literature considers inefficient matchings – see Ehlers [5 ] . Also, even our IR and efficient outcomes are different from imputations in TU games because we require budget-balance between every firm and its matched workers – cross-subsidizing payoffs across firms is not allowed in our outcomes, which is consistent with Kelso and Crawford [9 ] . ■
If the set of stable outcomes is non-empty, it is contained in every vNM stable set. This is a standard fact but we document it as an observation.
Observation 2. If ( μ ⋆ , u ⋆ ) (\mu^\star,u^\star) ( μ ⋆ , u ⋆ ) is a stable outcome, then ( μ ⋆ , u ⋆ ) ∈ V (\mu^\star,u^\star) \in\mathcal{V} ( μ ⋆ , u ⋆ ) ∈ V for any vNM stable set V \mathcal{V} V .
The proof of this observation follows from external stability: if ( μ ⋆ , u ⋆ ) ∉ V (\mu^\star,u^\star) \notin\mathcal{V} ( μ ⋆ , u ⋆ ) ∈ / V , then external stability will mean some outcome ( μ , u ) ∈ V (\mu,u) \in\mathcal{V} ( μ , u ) ∈ V will dominate ( μ ⋆ , u ⋆ ) (\mu^\star,u^\star) ( μ ⋆ , u ⋆ ) ; but that will mean a firm f f f and the subset of workers μ ( f ) \mu(f) μ ( f ) will block ( μ ⋆ , u ⋆ ) (\mu^\star,u^\star) ( μ ⋆ , u ⋆ ) , a contradiction to stability of ( μ ⋆ , u ⋆ ) (\mu^\star,u^\star) ( μ ⋆ , u ⋆ ) .
Existence of vNM stable sets
A vNM stable set may not exist as the following example shows.
Example 1 (vNM stable set may not exist). Consider the following economy. There are three firms F = { f 1 , f 2 , f 3 } F = \{f_1, f_2, f_3\} F = { f 1 , f 2 , f 3 } and three workers W = { w 1 , w 2 , w 3 } W = \{w_1, w_2, w_3\} W = { w 1 , w 2 , w 3 } . Firms are single-minded: firm f 1 f_1 f 1 can generate positive (equal to 1) surplus with workers { w 1 , w 2 } \{w_1, w_2\} { w 1 , w 2 } only; firm f 2 f_2 f 2 can generate positive (equal to 1) surplus with workers { w 2 , w 3 } \{w_2, w_3\} { w 2 , w 3 } only; and firm f 3 f_3 f 3 can generate positive (equal to 1) surplus with workers { w 3 , w 1 } \{w_3, w_1\} { w 3 , w 1 } only. This is given in Table 1 .7 There
Table 1. Surplus of firms and workers
are three efficient matchings: μ 1 \mu_1 μ 1 matches f 1 f_1 f 1 to workers { w 1 , w 2 } \{w_1, w_2\} { w 1 , w 2 } ; μ 2 \mu_2 μ 2 matches f 2 f_2 f 2 to workers { w 2 , w 3 } \{w_2, w_3\} { w 2 , w 3 } and μ 3 \mu_3 μ 3 matches f 3 f_3 f 3 to workers { w 3 , w 1 } \{w_3, w_1\} { w 3 , w 1 } . In any other matching the total surplus generated is less than or equal to zero and IR requires that all the firms and workers must get zero payoff in any outcome corresponding to such matchings. So, if μ ∉ { μ 1 , μ 2 , μ 3 } \mu\notin\{\mu_1, \mu_2, \mu_3\} μ ∈ / { μ 1 , μ 2 , μ 3 } , then ( μ , u w 1 , u w 2 , u w 3 ) ∈ I (\mu, u_{w_1}, u_{w_2}, u_{w_3}) \in\mathcal{I} ( μ , u w 1 , u w 2 , u w 3 ) ∈ I implies u w k = 0 u_{w_k} = 0 u w k = 0 for all k ∈ { 1 , 2 , 3 } k \in\{1, 2, 3\} k ∈ { 1 , 2 , 3 } . We show that no vNM stable set exists for this example.
Lemma 1. A vNM stable set does not exist for the economy in Example 1.
While vNM stable set does not exist in Example 1, it is a non-generic example in the sense that there are multiple efficient matchings. We now show that if a unique efficient matching exists, a vNM stable set always exists: the set of all efficient and IR outcomes is one such set.8
Theorem 1. If there is a unique efficient matching, then the set of all IR and efficient outcomes is a vNM stable set.
Proof. Internal stability of I μ ⋆ \mathcal{I}_{\mu^\star} I μ ⋆ follows from Observation 1. The following lemma, whose proof is given in Appendix § 9 , establishes external stability.
Lemma 2. Suppose μ \mu μ is not an efficient matching and ( μ , u ) ∈ I (\mu,u) \in\mathcal{I} ( μ , u ) ∈ I . Then, there exists ( μ ⋆ , u ⋆ ) ∈ I μ ⋆ (\mu^\star,u^\star) \in\mathcal{I}_{\mu^\star} ( μ ⋆ , u ⋆ ) ∈ I μ ⋆ such that μ ⋆ \mu^\star μ ⋆ is efficient and ( μ ⋆ , u ⋆ ) → ( μ , u ) (\mu^\star,u^\star) \to(\mu,u) ( μ ⋆ , u ⋆ ) → ( μ , u ) .
Since the unique efficient matching is μ ⋆ \mu^\star μ ⋆ , any ( μ , u ) ∉ I μ ⋆ (\mu,u) \notin\mathcal{I}_{\mu^\star} ( μ , u ) ∈ / I μ ⋆ is inefficient. Hence, Lemma 2 implies there exists ( μ ⋆ , u ⋆ ) ∈ I μ ⋆ (\mu^\star,u^\star) \in\mathcal{I}_{\mu^\star} ( μ ⋆ , u ⋆ ) ∈ I μ ⋆ such that ( μ ⋆ , u ⋆ ) → ( μ , u ) (\mu^\star,u^\star) \to(\mu,u) ( μ ⋆ , u ⋆ ) → ( μ , u ) . □
Stable outcomes and vNM stable sets
By Observation 2, whenever the core is non-empty, it is included in every vNM stable set. We now share two observations about vNM stable sets when core is non-empty: (a) core may not be a vNM stable set; (b) a vNM stable set may contain inefficient outcomes along with core.
Corollary 1. Suppose μ ⋆ \mu^\star μ ⋆ is the unique efficient matching and the core C \mathcal{C} C is non-empty. Then, C \mathcal{C} C is a vNM stable set if and only if C = I μ ⋆ \mathcal{C} = \mathcal{I}_{\mu^\star} C = I μ ⋆ .
Proof. The fact that I μ ⋆ \mathcal{I}_{\mu^\star} I μ ⋆ is a vNM stable set follows from Theorem 1. For the other direction, suppose C \mathcal{C} C is a vNM stable set. Since every outcome in C \mathcal{C} C is efficient, we have C ⊆ I μ ⋆ \mathcal{C} \subseteq\mathcal{I}_{\mu^\star} C ⊆ I μ ⋆ . Assume for contradiction C ⊊ I μ ⋆ \mathcal{C} \subsetneq\mathcal{I}_{\mu^\star} C ⊊ I μ ⋆ . Now, pick ( μ ⋆ , u ⋆ ) ∈ I μ ⋆ ∖ C (\mu^\star,u^\star) \in\mathcal{I}_{\mu^\star} \setminus\mathcal{C} ( μ ⋆ , u ⋆ ) ∈ I μ ⋆ ∖ C . By Observation 1, for every ( μ ⋆ , u ) ∈ C (\mu^\star,u) \in\mathcal{C} ( μ ⋆ , u ) ∈ C , we have ( μ ⋆ , u ) ↛ ( μ ⋆ , u ⋆ ) (\mu^\star,u) \not\to(\mu^\star,u^\star) ( μ ⋆ , u ) → ( μ ⋆ , u ⋆ ) . Hence, C \mathcal{C} C violates external stability, a contradiction. □
Usually core is a strict subset of the set of IR outcomes corresponding to efficient matchings. Hence, when there is a unique efficient matching, core is not usually vNM stable. The following example shows that even when there are multiple efficient matchings, the core may be a strict subset of a vNM stable set and the vNM stable set may contain inefficient matchings.
Example 2 (vNM stable set with inefficient outcomes). Let F = { f } F = \{f\} F = { f } and W = { w 1 , w 2 } W = \{w_1,w_2\} W = { w 1 , w 2 } . Let
V f ( { w 1 , w 2 } ) = 1 , V f ( { w 1 } ) = V f ( { w 2 } ) = 2. V_f(\{w_1,w_2\}) = 1, \quad V_f(\{w_1\}) = V_f(\{w_2\}) = 2. V f ({ w 1 , w 2 }) = 1 , V f ({ w 1 }) = V f ({ w 2 }) = 2. Consider the four possible matchings:
μ 1 : μ 1 ( f ) = { w 1 } ; μ 2 : μ 2 ( f ) = { w 2 } ; μ 3 : μ 3 ( f ) = { w 1 , w 2 } ; μ 4 : μ 4 ( f ) = ∅ \mu_1 : \mu_1(f) = \{w_1\}; \quad\mu_2 : \mu_2(f) = \{w_2\}; \quad\mu_3 : \mu_3(f) = \{w_1,w_2\}; \quad\mu_4 : \mu_4(f) = \varnothing μ 1 : μ 1 ( f ) = { w 1 } ; μ 2 : μ 2 ( f ) = { w 2 } ; μ 3 : μ 3 ( f ) = { w 1 , w 2 } ; μ 4 : μ 4 ( f ) = ∅ Out of these, μ 1 \mu_1 μ 1 and μ 2 \mu_2 μ 2 are efficient. There are exactly two stable outcomes: ( μ 1 , 0 , 0 ) (\mu_1,0,0) ( μ 1 , 0 , 0 ) and ( μ 2 , 0 , 0 ) (\mu_2,0,0) ( μ 2 , 0 , 0 ) . So core consists of C : = { ( μ 1 , 0 , 0 ) , ( μ 2 , 0 , 0 ) } \mathcal{C} := \{(\mu_1,0,0),(\mu_2,0,0)\} C := {( μ 1 , 0 , 0 ) , ( μ 2 , 0 , 0 )} . Consider the following set of
inefficient outcomes.
I μ 3 + : = { ( μ 3 , x , y ) : x > 0 , y > 0 , x + y ≤ 1 } \mathcal{I}_{\mu_3}^{+}:=\{(\mu_3,x,y):x>0,y>0,x+y\leq1\} I μ 3 + := {( μ 3 , x , y ) : x > 0 , y > 0 , x + y ≤ 1 }
We argue that C ∪ I μ 3 + C\cup\mathcal{I}_{\mu_3}^{+} C ∪ I μ 3 + is a vNM stable set. By Observation 2, outcomes in C C C do not dominate each other. By Observation 1, outcomes in I μ 3 + \mathcal{I}_{\mu_3}^{+} I μ 3 + do not dominate each other. Since firm f f f gets payoff 2 in outcomes in C C C and gets a maximum payoff of 1 in outcomes in I μ 3 + \mathcal{I}_{\mu_3}^{+} I μ 3 + , no outcome in C C C can be dominated by outcomes in I μ 3 + \mathcal{I}_{\mu_3}^{+} I μ 3 + . Finally, both workers get zero payoff in outcomes in C C C but get positive payoff in outcomes in I μ 3 + \mathcal{I}_{\mu_3}^{+} I μ 3 + . Hence, outcomes in I μ 3 + \mathcal{I}_{\mu_3}^{+} I μ 3 + cannot be dominated by outcomes in C C C .
Next, we argue external stability. Outcomes corresponding to μ 4 \mu_4 μ 4 are clearly dominated by ( μ 1 , 0 , 0 ) (\mu_1,0,0) ( μ 1 , 0 , 0 ) (or any other outcome in C ∪ I μ 3 + C\cup\mathcal{I}_{\mu_3}^{+} C ∪ I μ 3 + ). Outcomes of the form ( μ 3 , x , y ) (\mu_3,x,y) ( μ 3 , x , y ) , where x y = 0 xy=0 x y = 0 , is dominated by ( μ 1 , 0 , 0 ) (\mu_1,0,0) ( μ 1 , 0 , 0 ) if x = 0 x=0 x = 0 and by ( μ 2 , 0 , 0 ) (\mu_2,0,0) ( μ 2 , 0 , 0 ) if y = 0 y=0 y = 0 .
Appendix C contains another example in which the corresponding economy has an empty core but a vNM stable set containing only inefficient outcomes exist.
Rich vNM stable sets
Example 1 shows that vNM stable sets may not exist with multiple efficient matchings. The following example shows that if there are multiple efficient matchings, I μ \mathcal{I}_{\mu} I μ need not be vNM stable for any efficient matching μ \mu μ . However, a vNM stable set exists in this example.
Example 3 (Multiple efficient matchings). Consider the following economy. There is one firm f f f and two workers w w w and w ′ w^{\prime} w ′ . The surplus function of the firm is V f ( { w } ) = V f ( { w ′ } ) = 1 V_f(\{w\})=V_f(\{w^{\prime}\})=1 V f ({ w }) = V f ({ w ′ }) = 1 and V f ( { w , w ′ } ) = 0 V_f(\{w,w^{\prime}\})=0 V f ({ w , w ′ }) = 0 . There are two efficient matchings μ \mu μ : matches the firm to worker w w w and μ ′ \mu^{\prime} μ ′ : matches the firm to worker w ′ w^{\prime} w ′ . Then, it is not difficult to see that
I μ = { ( μ , u ( w ) , u ( w ′ ) ) : u ( w ′ ) = 0 , 0 ≤ u ( w ) ≤ 1 } \mathcal{I}_{\mu}=\{(\mu,u(w),u(w^{\prime})):u(w^{\prime})=0,0\leq u(w)\leq1\} I μ = {( μ , u ( w ) , u ( w ′ )) : u ( w ′ ) = 0 , 0 ≤ u ( w ) ≤ 1 } I μ ′ = { ( μ ′ , u ( w ) , u ( w ′ ) ) : u ( w ) = 0 , 0 ≤ u ( w ′ ) ≤ 1 } \mathcal{I}_{\mu^{\prime}}=\{(\mu^{\prime},u(w),u(w^{\prime})):u(w)=0,0\leq u(w^{\prime})\leq1\} I μ ′ = {( μ ′ , u ( w ) , u ( w ′ )) : u ( w ) = 0 , 0 ≤ u ( w ′ ) ≤ 1 } We first argue that I μ \mathcal{I}_{\mu} I μ is not a vNM stable set. Indeed, the outcome ( μ ′ , 0 , 0 ) (\mu^{\prime},0,0) ( μ ′ , 0 , 0 ) cannot be dominated by any outcome in I μ \mathcal{I}_{\mu} I μ . To see this, if ( μ , x , 0 ) (\mu,x,0) ( μ , x , 0 ) dominates ( μ ′ , 0 , 0 ) (\mu^{\prime},0,0) ( μ ′ , 0 , 0 ) , then we see that the payoff of firm is 1 − x ≤ 1 1-x\leq1 1 − x ≤ 1 , where 1 is its payoff in ( μ ′ , 0 , 0 ) (\mu^{\prime},0,0) ( μ ′ , 0 , 0 ) . Hence, for domination, we must have x = 0 x=0 x = 0 which gives equal payoff to firm f f f in both outcomes. Hence, all the
workers are also indifferent between the two outcomes. Hence, I μ \mathcal{I}_{\mu} I μ is not a vNM stable set. An analogous argument shows I μ ′ \mathcal{I}_{\mu'} I μ ′ is also not a vNM stable set.
Is I μ ∪ I μ ′ \mathcal{I}_{\mu}\cup\mathcal{I}_{\mu'} I μ ∪ I μ ′ a vNM stable set? No. Consider ( μ , 0 , 0 ) (\mu,0,0) ( μ , 0 , 0 ) and ( μ ′ , 0 , 1 2 ) (\mu',0,\frac{1}{2}) ( μ ′ , 0 , 2 1 ) . Worker w w w gets the same payoff in both outcomes and firm f f f is strictly better in ( μ , 0 , 0 ) (\mu,0,0) ( μ , 0 , 0 ) . Hence, ( μ , 0 , 0 ) (\mu,0,0) ( μ , 0 , 0 ) dominates ( μ ′ , 0 , 1 2 ) (\mu',0,\frac{1}{2}) ( μ ′ , 0 , 2 1 ) , violating internal stability.
Is anything vNM stable? Consider the set of two outcomes { ( μ , 0 , 0 ) , ( μ ′ , 0 , 0 ) } \{(\mu,0,0),(\mu',0,0)\} {( μ , 0 , 0 ) , ( μ ′ , 0 , 0 )} . The firm and the workers are all indifferent between the outcomes. So, they are not comparable, and internally stable. For external stability, any other matching μ ′ ′ \mu'' μ ′′ has only zero payoffs for firm and two workers.9 Now, outcome ( μ , 0 , 0 ) (\mu,0,0) ( μ , 0 , 0 ) dominates any such outcome. Also, ( μ ′ , 0 , 0 ) (\mu',0,0) ( μ ′ , 0 , 0 ) dominates any outcome ( μ , x , 0 ) (\mu,x,0) ( μ , x , 0 ) with 0 < x ≤ 1 0<x\leq1 0 < x ≤ 1 . Similarly, ( μ , 0 , 0 ) (\mu,0,0) ( μ , 0 , 0 ) dominates any outcome ( μ ′ , 0 , x ) (\mu',0,x) ( μ ′ , 0 , x ) with 0 < x ≤ 1 0<x\leq1 0 < x ≤ 1 . Hence, { ( μ , 0 , 0 ) , ( μ ′ , 0 , 0 ) } \{(\mu,0,0),(\mu',0,0)\} {( μ , 0 , 0 ) , ( μ ′ , 0 , 0 )} is a vNM stable set. ■
We now impose a richness on vNM stable sets. We want our vNM stable sets to be rich in the sense that if an outcome ( μ , u ) (\mu,u) ( μ , u ) is part of a vNM stable set then certain other outcomes corresponding to μ \mu μ should be part of the vNM stable set. As Example 1 shows if there are multiple efficient matchings the union of IR outcomes of efficient matchings need not be vNM stable.
Formally, rich vNM stable sets are defined as follows. We say a matching μ \mu μ is IR-feasible if I μ \mathcal{I}_{\mu} I μ is non-empty. For any set of outcomes V ⊂ I \mathcal{V}\subset\mathcal{I} V ⊂ I , denote by M ( V ) \mathcal{M}(\mathcal{V}) M ( V ) the set of matchings involved in V \mathcal{V} V :
M ( V ) : = { μ : ( μ , u ) ∈ V } \mathcal{M}(\mathcal{V}) := \{\mu: (\mu,u)\in\mathcal{V}\} M ( V ) := { μ : ( μ , u ) ∈ V }
For any IR-feasible matching μ \mu μ , the outcome that assigns zero payoff to all workers ( μ , 0 ) (\mu,0) ( μ , 0 ) is IR-feasible, i.e., belongs to I μ \mathcal{I}_{\mu} I μ . We refer to this outcome as firm-IR-optimal outcome for μ \mu μ . The following claim clarifies the role of such outcomes being included in a vNM stable set.
Lemma 3. Suppose V \mathcal{V} V is a vNM-stable set such that for every μ ∈ M ( V ) \mu\in\mathcal{M}(\mathcal{V}) μ ∈ M ( V ) , the firm-IR-optimal outcome for μ \mu μ belongs to V \mathcal{V} V . Then, for every μ , μ ′ ∈ M ( V ) \mu,\mu'\in\mathcal{M}(\mathcal{V}) μ , μ ′ ∈ M ( V ) , we have
V f ( μ ( f ) ) = V f ( μ ′ ( f ) ) ∀ f ∈ F (1) V_f(\mu(f)) = V_f(\mu'(f)) \qquad\forall f\in F \tag*{(1)} V f ( μ ( f )) = V f ( μ ′ ( f )) ∀ f ∈ F (1) :::@references
Proof. Suppose V \mathcal{V} V is a vNM-stable set such that for every μ ∈ M ( V ) \mu\in\mathcal{M}(\mathcal{V}) μ ∈ M ( V ) , the firm-IR-optimal outcome for μ \mu μ belongs to V \mathcal{V} V . Consider two distinct matchings μ , μ ′ ∈ M ( V ) \mu,\mu' \in\mathcal{M}(\mathcal{V}) μ , μ ′ ∈ M ( V ) . Since I μ \mathcal{I}_{\mu} I μ and I μ ′ \mathcal{I}_{\mu'} I μ ′ are non-empty, individual rationality implies V f ( μ ( f ) ) ≥ 0 V_f(\mu(f)) \ge0 V f ( μ ( f )) ≥ 0 and V f ( μ ′ ( f ) ) ≥ 0 V_f(\mu'(f)) \ge0 V f ( μ ′ ( f )) ≥ 0 for every f ∈ F f \in F f ∈ F . Consider u u u and u ′ u' u ′ such that u ( w ) = u ′ ( w ) = 0 u(w)=u'(w)=0 u ( w ) = u ′ ( w ) = 0 for every w ∈ W w \in W w ∈ W . Note that u u u is firm-IR-optimal for μ \mu μ and u ′ u' u ′ is firm-IR-optimal for μ ′ \mu' μ ′ . Hence, we have ( μ , u ) , ( μ ′ , u ′ ) ∈ V (\mu,u),(\mu',u') \in\mathcal{V} ( μ , u ) , ( μ ′ , u ′ ) ∈ V . If for some f ∈ F f \in F f ∈ F , V f ( μ ( f ) ) > V f ( μ ′ ( f ) ) V_f(\mu(f)) > V_f(\mu'(f)) V f ( μ ( f )) > V f ( μ ′ ( f )) , then ( μ , u ) → f ( μ ′ , u ′ ) (\mu,u) \xrightarrow{f} (\mu',u') ( μ , u ) f ( μ ′ , u ′ ) , contradicting internal stability. Hence, V f ( μ ( f ) ) ≤ V f ( μ ′ ( f ) ) V_f(\mu(f)) \le V_f(\mu'(f)) V f ( μ ( f )) ≤ V f ( μ ′ ( f )) for all f ∈ F f \in F f ∈ F . By interchanging the roles of ( μ , u ) (\mu,u) ( μ , u ) and ( μ ′ , u ′ ) (\mu',u') ( μ ′ , u ′ ) , we obtain V f ( μ ′ ( f ) ) ≤ V f ( μ ( f ) ) V_f(\mu'(f)) \le V_f(\mu(f)) V f ( μ ′ ( f )) ≤ V f ( μ ( f )) for all f ∈ F f \in F f ∈ F . Therefore, (1) holds. □ \square □
We can similarly look at worker-IR-maximal outcomes, and the consequence of including them in vNM stable sets. For every worker w w w , let
u ( w ) : = { V μ ( w ) ( μ ( μ ( w ) ) ) if μ ( w ) ≠ ∅ 0 otherwise u(w) :=
\begin{cases}
V_{\mu(w)}(\mu(\mu(w))) & \text{if }\mu(w) \ne\varnothing\\
0 & \text{otherwise}
\end{cases} u ( w ) := { V μ ( w ) ( μ ( μ ( w ))) 0 if μ ( w ) = ∅ otherwise
and u ( w ′ ) : = 0 u(w') := 0 u ( w ′ ) := 0 for all w ′ ≠ w w' \ne w w ′ = w . Clearly, ( μ , u ) ∈ I μ (\mu,u) \in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ . We refer to ( μ , u ) (\mu,u) ( μ , u ) as w w w -IR-maximal outcome for $\mu.10 $
Definition 3. A set of outcomes V ⊂ I \mathcal{V} \subset\mathcal{I} V ⊂ I is rich if for every μ ∈ M ( V ) \mu\in\mathcal{M}(\mathcal{V}) μ ∈ M ( V ) , we have
firm-IR-optimal outcome for μ \mu μ belongs to V \mathcal{V} V ,
for every worker w w w , the w w w -IR-maximal outcome for μ \mu μ belongs to V \mathcal{V} V .
One reason why we investigate rich vNM stable sets is that it allows us to establish a partial converse of Theorem 1, and thus showing the salience of the rich vNM stable set identified in Theorem 1. The other reason to investigate rich vNM stable sets is methodological. As we show below, rich vNM stable sets are much easier to analyze. Indeed, the sufficient condition in Theorem 1 is almost necessary and the rich vNM stable set identified in Theorem 1 is almost unique.
Definition 4. A set of IR-feasible matchings M ′ \mathcal{M}' M ′ is essentially unique if for all μ , μ ′ ∈ M ′ \mu,\mu' \in\mathcal{M}' μ , μ ′ ∈ M ′ and for all f ∈ F f \in F f ∈ F ,
[ μ ( f ) ≠ μ ′ ( f ) ] ⟹ [ V f ( μ ( f ) ) = V f ( μ ′ ( f ) ) = 0 ] \left[\mu(f) \ne\mu'(f)\right] \Longrightarrow\left[V_f(\mu(f))=V_f(\mu'(f))=0\right] [ μ ( f ) = μ ′ ( f ) ] ⟹ [ V f ( μ ( f )) = V f ( μ ′ ( f )) = 0 ]
For any matching μ \mu μ , let V ( μ ) : = ∑ f ∈ F V f ( μ ( f ) ) V(\mu) := \sum_{f \in F} V_f(\mu(f)) V ( μ ) := ∑ f ∈ F V f ( μ ( f )) denote the total surplus generated from μ \mu μ . Note that if M ′ \mathcal{M}' M ′ is essentially unique, then for all μ , μ ′ ∈ M ′ \mu,\mu' \in\mathcal{M}' μ , μ ′ ∈ M ′ , we have V ( μ ) = V ( μ ′ ) V(\mu) = V(\mu') V ( μ ) = V ( μ ′ ) . Let M e f f \mathcal{M}^{\mathrm{eff}} M eff be the set of efficient matchings.
Theorem 2. Suppose V ⊆ I \mathcal{V} \subseteq\mathcal{I} V ⊆ I is rich set of I R IR I R -feasible outcomes. Then, V \mathcal{V} V is a vNM stable set if and only if (a) M ( V ) \mathcal{M}(\mathcal{V}) M ( V ) is essentially unique and (b) V \mathcal{V} V is the set of all efficient and I R IR I R outcomes.
The proof of Theorem 2 is in Appendix § 8 . The following is an immediate corollary of Theorem 2.
Corollary 2. Suppose μ \mu μ is an I R IR I R -feasible matching. Then, V ⊆ I μ \mathcal{V} \subseteq\mathcal{I}_{\mu} V ⊆ I μ is vNM stable if and only if μ \mu μ is the unique efficient matching and V = I μ \mathcal{V} = \mathcal{I}_{\mu} V = I μ .
Remark 2. Richness requires inclusion of extreme outcomes in the vNM stable set. As a result, we show the almost necessity of unique efficient outcomes in vNM stable sets and an almost unique characterization of the vNM stable set identified in Theorem 1. However, it is arguable that such extreme outcomes should not be included in a vNM stable set, given that it is supposed to reflect “standard social behavior” (in the language of von Neumann and Morgenstern [20 ] ). While it is difficult to characterize vNM stable sets without these outcomes, we comment on a weakening of richness. Call an economy without-ties (generic) if for all f ∈ F f \in F f ∈ F and all distinct S , T ⊆ W S,T \subseteq W S , T ⊆ W , we have V f ( S ) ≠ V f ( T ) V_f(S) \ne V_f(T) V f ( S ) = V f ( T ) . In an economy without-ties, we can consider weakening our richness to the requirement in Lemma 3: for every μ ∈ M ( V ) \mu\in\mathcal{M}(\mathcal{V}) μ ∈ M ( V ) , firm-I R IR I R -optimal outcome for μ \mu μ belongs to V \mathcal{V} V . By Lemma 3, M ( V ) \mathcal{M}(\mathcal{V}) M ( V ) is singleton, and hence, it is essentially unique. As the proof of Theorem 2 shows, that if M ( V ) \mathcal{M}(\mathcal{V}) M ( V ) is essentially unique, then V \mathcal{V} V is the set of all efficient and I R IR I R outcomes – this part does not require any further richness. Hence, a sharper version of Theorem 2 can be established under weaker richness but in economies without-ties.
Conclusion
Our main motivation for studying vNM stable sets was that stable outcomes are not guaranteed to exist in this model, specially in a large class of economically meaningful settings where teams of workers exhibit strong complementarities. By extending this to a collective stability notion, we have almost resolved the existence issue. Our results suggest that in this model, if firms and workers were to choose a collection of outcomes (contracts) using the principles of vNM stability, they are almost forced to choose only efficient outcomes but have complete flexibility in the division of surplus.
Proof of Theorem 2
We give a proof of Theorem 2 here. The main ingredient of the proof is the following proposition about the domination relation.
Proposition 1. Suppose μ ⋆ \mu^{\star} μ ⋆ is an efficient matching and μ \mu μ is an IR-feasible matching. Then, there exists ( μ ⋆ , u ⋆ ) ∈ I μ ⋆ (\mu^{\star},u^{\star}) \in\mathcal{I}_{\mu^{\star}} ( μ ⋆ , u ⋆ ) ∈ I μ ⋆ such that
( μ , u ) ↛ ( μ ⋆ , u ⋆ ) ∀ ( μ , u ) ∈ I μ (\mu,u) \not\to(\mu^{\star},u^{\star}) \qquad\forall\,(\mu,u) \in\mathcal{I}_{\mu} ( μ , u ) → ( μ ⋆ , u ⋆ ) ∀ ( μ , u ) ∈ I μ
Note that Proposition 1 does not require any richness mentioned in Theorem 2. The proof of Proposition 1, which is given below after some preparations for the proof is done, hinges on a characterization of the conditions under which an outcome ( μ ′ , u ′ ) ∈ I (\mu',u') \in\mathcal{I} ( μ ′ , u ′ ) ∈ I is not dominated by any outcome ( μ , u ) ∈ I μ (\mu,u) \in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ , where μ ≠ μ ′ \mu\ne\mu' μ = μ ′ . This is done in Lemma 4, whose proof is in Appendix B.
Lemma 4. Let μ ′ \mu' μ ′ and μ \mu μ be two distinct IR-feasible matchings. Suppose ( μ ′ , u ′ ) ∈ I μ ′ (\mu',u') \in\mathcal{I}_{\mu'} ( μ ′ , u ′ ) ∈ I μ ′ . Then, the following are equivalent:
( μ , u ) ↛ ( μ ′ , u ′ ) (\mu,u) \not\to(\mu',u') ( μ , u ) → ( μ ′ , u ′ ) for all ( μ , u ) ∈ I μ (\mu,u) \in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ
For all f ∈ F f \in F f ∈ F ,
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ′ ( w ) ≤ V f ( μ ′ ( f ) ) − ∑ w ∈ μ ′ ( f ) u ′ ( w ) (2) V_f(\mu(f))-\sum_{w\in\mu(f)}u'(w) \le V_f(\mu'(f))-\sum_{w\in\mu'(f)}u'(w) \tag*{(2)} V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ′ ( w ) ≤ V f ( μ ′ ( f )) − w ∈ μ ′ ( f ) ∑ u ′ ( w ) (2)
Fix any matching μ ′ \mu' μ ′ . Lemma 4 gives a clean linear system to verify when there exists u ′ u' u ′ such that ( μ ′ , u ′ ) ∈ I μ ′ (\mu',u') \in\mathcal{I}_{\mu'} ( μ ′ , u ′ ) ∈ I μ ′ and for every ( μ , u ) ∈ I μ (\mu,u) \in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ , we have ( μ , u ) ↛ ( μ ′ , u ′ ) (\mu,u) \not\to(\mu',u') ( μ , u ) → ( μ ′ , u ′ ) . We rewrite this linear system below.
To do so, we introduce a dummy firm f 0 f_0 f 0 such that V f 0 ( S ) = 0 V_{f_0}(S)=0 V f 0 ( S ) = 0 for all S ⊂ W S\subset W S ⊂ W . We assume that any worker who is unmatched in a matching is matched to f 0 f_0 f 0 . Without loss of generality, we assume that f 0 ∈ F f_0\in F f 0 ∈ F and each worker is matched to some firm in F F F (possibly to f 0 f_0 f 0 ) in every matching, where μ ( w ) = f 0 \mu(w)=f_0 μ ( w ) = f 0 for a matching μ \mu μ would indicate that worker w w w is unmatched. Now, consider the following system of inequalities.
∑ w ∈ μ ′ ( f ) u ′ ( w ) − ∑ w ∈ μ ( f ) u ′ ( w ) ≤ V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) ∀ f ∈ F (ES) \sum_{w\in\mu'(f)}u'(w)-\sum_{w\in\mu(f)}u'(w)\le V_f(\mu'(f))-V_f(\mu(f)) \qquad\forall\,f\in F
\quad\text{(ES)} w ∈ μ ′ ( f ) ∑ u ′ ( w ) − w ∈ μ ( f ) ∑ u ′ ( w ) ≤ V f ( μ ′ ( f )) − V f ( μ ( f )) ∀ f ∈ F (ES)
∑ w ∈ μ ′ ( f ) u ′ ( w ) ≤ V f ( μ ′ ( f ) ) ∀ f ∈ F (3) \sum_{w\in\mu'(f)} u'(w) \le V_f(\mu'(f)) \qquad\forall f\in F \tag*{(3)} w ∈ μ ′ ( f ) ∑ u ′ ( w ) ≤ V f ( μ ′ ( f )) ∀ f ∈ F (3)
u ′ ( w ) ≥ 0 ∀ w ∈ W u'(w) \ge0 \qquad\forall w\in W u ′ ( w ) ≥ 0 ∀ w ∈ W
Constraints (IR) ensures that a feasible u ′ u' u ′ satisfies ( μ ′ , u ′ ) ∈ I (\mu',u')\in\mathcal{I} ( μ ′ , u ′ ) ∈ I . Constraints (ES) is the same as the constraints in Lemma 4. Note that if a worker w w w is unmatched in μ ′ \mu' μ ′ (that is matched to f 0 f_0 f 0 ), then u ′ ( w ) ≥ 0 u'(w)\ge0 u ′ ( w ) ≥ 0 and (IR) along with the fact that V f 0 ( μ ′ ( f 0 ) ) = 0 V_{f_0}(\mu'(f_0))=0 V f 0 ( μ ′ ( f 0 )) = 0 implies that u ′ ( w ) = 0 u'(w)=0 u ′ ( w ) = 0 .
If u ′ u' u ′ is a feasible solution to (ES) and (IR), then there exists ( μ ′ , u ′ ) ∈ I μ ′ (\mu',u')\in\mathcal{I}_{\mu'} ( μ ′ , u ′ ) ∈ I μ ′ such that ( μ , u ) ⇝ ( μ ′ , u ′ ) (\mu,u)\rightsquigarrow(\mu',u') ( μ , u ) ⇝ ( μ ′ , u ′ ) for all ( μ , u ) ∈ I μ (\mu,u)\in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ . Conversely, if there exists ( μ ′ , u ′ ) ∈ I μ ′ (\mu',u')\in\mathcal{I}_{\mu'} ( μ ′ , u ′ ) ∈ I μ ′ , it is already a feasible solution to (IR) and if it is such that ( μ , u ) ⇝ ( μ ′ , u ′ ) (\mu,u)\rightsquigarrow(\mu',u') ( μ , u ) ⇝ ( μ ′ , u ′ ) for all ( μ , u ) ∈ I μ (\mu,u)\in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ , then by Lemma 4, it is a feasible solution to (ES).
To verify feasibility of (ES) and (IR) we represent this as a demand graph , whose flows will represent a feasible solution. Our demand graph G \mathcal{G} G has the following components: G ≡ ( V , E , c , b ) \mathcal{G}\equiv(V,E,c,b) G ≡ ( V , E , c , b ) is a demand graph , where
V V V is a finite set of vertices
E ⊆ { ( x , y ) : x , y ∈ V } E\subseteq\{(x,y):x,y\in V\} E ⊆ {( x , y ) : x , y ∈ V } is a finite set of directed edges
c : E → R + c:E\to\mathbb{R}_+ c : E → R + specifies a non-negative capacity for each edge in E E E
b : V → R b:V\to\mathbb{R} b : V → R specifies divergence at each vertex – if b ( x ) > 0 b(x)>0 b ( x ) > 0 , then x x x is a demand vertex and if b ( x ) < 0 b(x)<0 b ( x ) < 0 , then x x x is a supply vertex
A flow in G \mathcal{G} G is a map ϕ : E → R + \phi:E\to\mathbb{R}_+ ϕ : E → R + satisfying the following feasibility constraints:
ϕ ( x , y ) ≤ c ( x , y ) ∀ ( x , y ) ∈ E \phi(x,y)\le c(x,y) \qquad\forall(x,y)\in E ϕ ( x , y ) ≤ c ( x , y ) ∀ ( x , y ) ∈ E
∑ ( y , x ) ∈ E ϕ ( y , x ) − ∑ ( x , y ) ∈ E ϕ ( x , y ) = b ( x ) ∀ x ∈ V \sum_{(y,x)\in E}\phi(y,x)-\sum_{(x,y)\in E}\phi(x,y)=b(x) \qquad\forall x\in V ( y , x ) ∈ E ∑ ϕ ( y , x ) − ( x , y ) ∈ E ∑ ϕ ( x , y ) = b ( x ) ∀ x ∈ V
We fix matchings μ \mu μ and μ ′ \mu' μ ′ and construct the specific demand graph G \mathcal{G} G as follows:
Vertices. There is a vertex for each worker w ∈ W w\in W w ∈ W . Denote such a vertex as w w w itself for each w ∈ W w\in W w ∈ W . There is a pair of vertices for each firm f ∈ F f\in F f ∈ F . Denote such vertices as f , f ^ f,\hat{f} f , f ^ for each firm f ∈ F f\in F f ∈ F . The set of vertices f ^ \hat{f} f ^ for each f f f will be referred to as
the auxiliary vertices corresponding to firms. We will denote the set of all auxiliary vertices as F ^ \hat{F} F ^ . There is another vertex v 0 v_0 v 0 for handling slacks in constraints (ES). So, in total there are ∣ W ∣ + 2 ∣ F ∣ + 1 |W| + 2|F| + 1 ∣ W ∣ + 2∣ F ∣ + 1 vertices.
Edges. For every w ∈ W w \in W w ∈ W , there is an edge from w w w to f f f if μ ′ ( w ) = f \mu'(w) = f μ ′ ( w ) = f . There is an edge from f f f to f ^ \hat{f} f ^ for each f ∈ F f \in F f ∈ F . For each f ∈ F f \in F f ∈ F , there is an edge from f ^ \hat{f} f ^ to w w w if μ ( w ) = f \mu(w) = f μ ( w ) = f . There is an edge from v 0 v_0 v 0 to f ^ \hat{f} f ^ for every f ∈ F f \in F f ∈ F . Note that each vertex w w w has exactly one outgoing edge (to μ ′ ( w ) \mu'(w) μ ′ ( w ) ) and exactly one incoming edge (from μ ( w ) \mu(w) μ ( w ) ).11
Capacities. All edges have very high capacity (to be precise more than V ( μ ′ ) V(\mu') V ( μ ′ ) ) except edges ( f , f ^ ) (f,\hat{f}) ( f , f ^ ) for each f ∈ F f \in F f ∈ F :
c ( f , f ^ ) : = V f ( μ ′ ( f ) ) c(f,\hat{f}) := V_f(\mu'(f)) c ( f , f ^ ) := V f ( μ ′ ( f ))
b ( f ^ ) : = V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) b(\hat{f}) := V_f(\mu'(f)) - V_f(\mu(f)) b ( f ^ ) := V f ( μ ′ ( f )) − V f ( μ ( f ))
Divergence at v 0 v_0 v 0 is
b ( v 0 ) : = V ( μ ) − V ( μ ′ ) b(v_0) := V(\mu) - V(\mu') b ( v 0 ) := V ( μ ) − V ( μ ′ )
where for any matching μ ^ \hat{\mu} μ ^ , V ( μ ^ ) ≡ ∑ f ∈ F V f ( μ ^ ( f ) ) V(\hat{\mu}) \equiv\sum_{f \in F} V_f(\hat{\mu}(f)) V ( μ ^ ) ≡ ∑ f ∈ F V f ( μ ^ ( f )) .
Note that ∑ x ∈ V b ( x ) = 0 \sum_{x \in V} b(x) = 0 ∑ x ∈ V b ( x ) = 0 .
As an example consider W = { w 1 , w 2 , w 3 , w 4 } W = \{w_1,w_2,w_3,w_4\} W = { w 1 , w 2 , w 3 , w 4 } and F = { f 1 , f 2 , f 3 } F = \{f_1,f_2,f_3\} F = { f 1 , f 2 , f 3 } . Suppose μ \mu μ and μ ′ \mu' μ ′ are as follows:
μ ′ ( w 1 ) = f 1 , μ ′ ( w 2 ) = f 1 , μ ′ ( w 3 ) = f 2 , μ ′ ( w 4 ) = f 3 \mu'(w_1) = f_1,\mu'(w_2) = f_1,\mu'(w_3) = f_2,\mu'(w_4) = f_3 μ ′ ( w 1 ) = f 1 , μ ′ ( w 2 ) = f 1 , μ ′ ( w 3 ) = f 2 , μ ′ ( w 4 ) = f 3
μ ( w 1 ) = f 3 , μ ( w 2 ) = f 2 , μ ( w 3 ) = f 1 , μ ( w 4 ) = f 2 \mu(w_1) = f_3,\mu(w_2) = f_2,\mu(w_3) = f_1,\mu(w_4) = f_2 μ ( w 1 ) = f 3 , μ ( w 2 ) = f 2 , μ ( w 3 ) = f 1 , μ ( w 4 ) = f 2
The corresponding demand graph is shown in Figure 1
Figure 1. Demand network
The following lemma makes the connection between demand graph and the system of inequalities in (ES) and (IR) precise.
Lemma 5. Suppose μ \mu μ and μ ′ \mu' μ ′ are two IR-feasible matchings. A feasible solution to (E S ES E S ) and (I R IR I R ) exists if and only if a flow in the demand graph G \mathcal{G} G exists.
We use Lemma 5, which is proved in Appendix § 9 , to show sufficiency of efficient matching for (E S ES E S ) and (I R IR I R ) to be feasible. The proof of Proposition 1 can now be completed using a celebrated theorem of David Gale on existence of flows in a demand graph.12
Proof of Proposition 1. Let μ \mu μ and μ ⋆ ≡ μ ′ \mu^{\star}\equiv\mu' μ ⋆ ≡ μ ′ be two IR-feasible matchings (to be consistent with the notation in the earlier lemmas, we will denote μ ′ ≡ μ ⋆ \mu'\equiv\mu^{\star} μ ′ ≡ μ ⋆ ). We show that if μ ′ \mu' μ ′ is an efficient matching, then a flow in directed graph G \mathcal{G} G (corresponding to μ \mu μ and μ ⋆ \mu^{\star} μ ⋆ ) exists. Lemma 5 will then imply that a feasible solution to (E S ES E S ) and (I R IR I R ) exists. Denote this solution as ( μ ⋆ , u ⋆ ) (\mu^{\star},u^{\star}) ( μ ⋆ , u ⋆ ) . and Lemma 4 will imply that for all ( μ , u ) ∈ I μ (\mu,u)\in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ , we have ( μ , u ) ⇝̸ ( μ ⋆ , u ⋆ ) (\mu,u)\not\leadsto(\mu^{\star},u^{\star}) ( μ , u ) ⇝ ( μ ⋆ , u ⋆ ) . This will complete the proof.
To show that a flow in directed graph G \mathcal{G} G exists, we invoke a seminal result due to David Gale for this. We introduce some notations first. A cut in G \mathcal{G} G is a partitioning of the set of vertices into two parts: ( S , V ∖ S ) (S,V\setminus S) ( S , V ∖ S ) . Without loss of generality, we denote a cut by S ⊆ V S\subseteq V S ⊆ V .
The capacity of a cut is the sum of capacities of all incoming edges to the cut:
c ( S ) : = ∑ ( x , y ) ∈ E : x ∉ S , y ∈ S c ( x , y ) ∀ S ⊆ V c(S) := \sum_{\substack{(x,y)\in E:x\notin S,y\in S}} c(x,y) \qquad\forall\ S\subseteq V c ( S ) := ( x , y ) ∈ E : x ∈ / S , y ∈ S ∑ c ( x , y ) ∀ S ⊆ V
The divergence of a cut is the sum of divergences of vertices in the cut:
b ( S ) : = ∑ x ∈ S b ( x ) ∀ S ⊆ V b(S) := \sum_{x\in S} b(x) \qquad\forall\ S\subseteq V b ( S ) := x ∈ S ∑ b ( x ) ∀ S ⊆ V
Theorem 3 (David Gale’s Demand Theorem). Suppose G G G is a directed graph such that b ( V ) = 0 b(V)=0 b ( V ) = 0 . Then, a flow exists in G G G if and only if for every cut S ⊆ V S\subseteq V S ⊆ V , we have
b ( S ) ≤ c ( S ) b(S) \le c(S) b ( S ) ≤ c ( S )
By David Gale’s theorem, it is enough to show that for any cut S ⊆ V S\subseteq V S ⊆ V in G G G , we have b ( S ) ≤ c ( S ) b(S) \le c(S) b ( S ) ≤ c ( S ) . We will consider three kinds of cuts.
Case 1. This is the case where there is some incoming edge to S S S with high capacity. Hence, c ( S ) c(S) c ( S ) is a very high number and c ( S ) ≥ b ( S ) c(S) \ge b(S) c ( S ) ≥ b ( S ) .
Case 2. There is no high capacity edge incoming to S S S and v 0 ∉ S v_0\notin S v 0 ∈ / S . In that case, each auxiliary vertex f ^ ∉ S \hat{f}\notin S f ^ ∈ / S – else there would be a high capacity edge ( v 0 , f ^ ) (v_0,\hat{f}) ( v 0 , f ^ ) into S S S . Since divergence is non-zero only for vertices in F ^ ∪ { v 0 } \hat{F}\cup\{v_0\} F ^ ∪ { v 0 } , we conclude that b ( S ) = 0 b(S)=0 b ( S ) = 0 . Since capacities are non-negative, c ( S ) ≥ b ( S ) c(S)\ge b(S) c ( S ) ≥ b ( S ) .
Case 3. There is no high capacity edge incoming to S S S and v 0 ∈ S v_0\in S v 0 ∈ S . We are going to partition auxiliary (firm)-vertices in S S S into two parts: ( F ^ ′ ∪ F ^ ′ ′ ) ⊂ S (\hat{F}'\cup\hat{F}'')\subset S ( F ^ ′ ∪ F ^ ′′ ) ⊂ S with F ^ ′ ∩ F ^ ′ ′ = ∅ \hat{F}'\cap\hat{F}''=\varnothing F ^ ′ ∩ F ^ ′′ = ∅ . For every f ^ ∈ F ^ ′ \hat{f}\in\hat{F}' f ^ ∈ F ^ ′ , the vertex f ∈ S f\in S f ∈ S , and hence, edge ( f , f ^ ) (f,\hat{f}) ( f , f ^ ) is not incoming to S S S . For every f ^ ∈ F ^ ′ ′ \hat{f}\in\hat{F}'' f ^ ∈ F ^ ′′ , vertex f ∉ S f\notin S f ∈ / S , and hence, edge ( f , f ^ ) (f,\hat{f}) ( f , f ^ ) is incoming to $S.13 T h a t i s That is T ha t i s \hat{F}''\subset Sa n d and an d F''\subset V\setminus S$. Partition the set of workers also:
W ′ : = ⋃ f ′ ∈ F ′ μ ′ ( f ′ ) , W ′ ′ : = ⋃ f ′ ′ ∈ F ′ ′ μ ′ ( f ′ ′ ) , W ∖ ( W ′ ∪ W ′ ′ ) W' := \bigcup_{f'\in F'}\mu'(f'), \qquad W'' := \bigcup_{f''\in F''}\mu'(f''), \qquad W\setminus(W'\cup W'') W ′ := f ′ ∈ F ′ ⋃ μ ′ ( f ′ ) , W ′′ := f ′′ ∈ F ′′ ⋃ μ ′ ( f ′′ ) , W ∖ ( W ′ ∪ W ′′ )
Since S S S has no incoming-edge with high capacity, two things must hold true:
An illustration of cut S S S is shown in Figure 2 .
Figure 2. Representation of cut S S S
The divergence of S S S equals
b ( S ) = b ( v 0 ) + ∑ f ^ ∈ F ^ ′ b ( f ^ ) + ∑ f ^ ∈ F ^ ′ ′ b ( f ^ ) = b ( v 0 ) + ∑ f ∈ F ′ [ V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) ] + ∑ f ∈ F ′ ′ [ V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) ] = [ V ( μ ) − V ( μ ′ ) ] + ∑ f ∈ F ′ [ V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) ] + ∑ f ∈ F ′ ′ [ V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) ] = ∑ f ∈ F ∖ ( F ′ ∪ F ′ ′ ) [ V f ( μ ( f ) ) − V f ( μ ′ ( f ) ) ] . \begin{aligned}
b(S) &= b(v_0) + \sum_{\hat{f}\in\hat{F}'} b(\hat{f}) + \sum_{\hat{f}\in\hat{F}''} b(\hat{f}) \\
&= b(v_0) + \sum_{f\in F'} [V_f(\mu'(f)) - V_f(\mu(f))] + \sum_{f\in F''} [V_f(\mu'(f)) - V_f(\mu(f))] \\
&= [V(\mu) - V(\mu')] + \sum_{f\in F'} [V_f(\mu'(f)) - V_f(\mu(f))] + \sum_{f\in F''} [V_f(\mu'(f)) - V_f(\mu(f))] \\
&= \sum_{f\in F\setminus(F'\cup F'')} [V_f(\mu(f)) - V_f(\mu'(f))].
\end{aligned} b ( S ) = b ( v 0 ) + f ^ ∈ F ^ ′ ∑ b ( f ^ ) + f ^ ∈ F ^ ′′ ∑ b ( f ^ ) = b ( v 0 ) + f ∈ F ′ ∑ [ V f ( μ ′ ( f )) − V f ( μ ( f ))] + f ∈ F ′′ ∑ [ V f ( μ ′ ( f )) − V f ( μ ( f ))] = [ V ( μ ) − V ( μ ′ )] + f ∈ F ′ ∑ [ V f ( μ ′ ( f )) − V f ( μ ( f ))] + f ∈ F ′′ ∑ [ V f ( μ ′ ( f )) − V f ( μ ( f ))] = f ∈ F ∖ ( F ′ ∪ F ′′ ) ∑ [ V f ( μ ( f )) − V f ( μ ′ ( f ))] .
The capacity of S S S equals c ( S ) = ∑ f ∈ F ′ ′ c ( f , f ^ ) = ∑ f ∈ F ′ ′ V f ( μ ′ ( f ) ) c(S) = \sum_{f\in F''} c(f,\hat{f}) = \sum_{f\in F''} V_f(\mu'(f)) c ( S ) = ∑ f ∈ F ′′ c ( f , f ^ ) = ∑ f ∈ F ′′ V f ( μ ′ ( f )) as the only incoming edges to S S S are of the form ( f , f ^ ) (f,\hat{f}) ( f , f ^ ) where f ∈ F ′ ′ f \in F'' f ∈ F ′′ .
Consider a candidate matching μ ^ \hat{\mu} μ ^ defined as follows. For every f ∈ F ∖ { f 0 } f \in F \setminus\{f_0\} f ∈ F ∖ { f 0 } , let
μ ^ ( f ) = { μ ′ ( f ) if f ∈ F ′ , ∅ if f ∈ F ′ ′ , μ ( f ) otherwise. \hat{\mu}(f) =
\begin{cases}
\mu'(f) & \text{if } f \in F', \\
\varnothing& \text{if } f \in F'', \\
\mu(f) & \text{otherwise.}
\end{cases} μ ^ ( f ) = ⎩ ⎨ ⎧ μ ′ ( f ) ∅ μ ( f ) if f ∈ F ′ , if f ∈ F ′′ , otherwise.
All remaining workers are matched to the dummy firm f 0 f_0 f 0 , that is, μ ^ ( f 0 ) = W ∖ ( ⋃ f ∈ F ∖ { f 0 } μ ^ ( f ) ) \hat{\mu}(f_0) = W \setminus\left(\bigcup_{f \in F \setminus\{f_0\}} \hat{\mu}(f)\right) μ ^ ( f 0 ) = W ∖ ( ⋃ f ∈ F ∖ { f 0 } μ ^ ( f ) ) .
Since for every w ∈ W ′ w \in W' w ∈ W ′ , μ ( w ) ∈ F ′ ∪ F ′ ′ \mu(w) \in F' \cup F'' μ ( w ) ∈ F ′ ∪ F ′′ , the matching μ ^ \hat{\mu} μ ^ is well-defined. As μ ′ \mu' μ ′ is efficient,
0 ≥ V ( μ ^ ) − V ( μ ′ ) = ∑ f ∈ F ∖ ( F ′ ∪ F ′ ′ ) [ V f ( μ ( f ) ) − V f ( μ ′ ( f ) ) ] − ∑ f ∈ F ′ ′ V f ( μ ′ ( f ) ) = b ( S ) − c ( S ) . 0 \ge V(\hat{\mu}) - V(\mu') = \sum_{f \in F \setminus(F' \cup F'')} \left[V_f(\mu(f)) - V_f(\mu'(f))\right] - \sum_{f \in F''} V_f(\mu'(f)) = b(S) - c(S). 0 ≥ V ( μ ^ ) − V ( μ ′ ) = f ∈ F ∖ ( F ′ ∪ F ′′ ) ∑ [ V f ( μ ( f )) − V f ( μ ′ ( f )) ] − f ∈ F ′′ ∑ V f ( μ ′ ( f )) = b ( S ) − c ( S ) .
Hence, it follows that b ( S ) ≤ c ( S ) b(S) \le c(S) b ( S ) ≤ c ( S ) .
We now have all the tools to prove Theorem 2.
Proof of Theorem 2. Sufficiency: Suppose M e f f \mathcal{M}^{\mathrm{eff}} M eff is essentially unique, and let
V : = ⋃ μ ∈ M e f f I μ \mathcal{V} := \bigcup_{\mu\in\mathcal{M}^{\mathrm{eff}}} \mathcal{I}_{\mu} V := μ ∈ M eff ⋃ I μ
We show V \mathcal{V} V is a vNM stable set in two steps.
Internal stability. Consider any two efficient matchings μ , μ ′ ∈ M e f f \mu, \mu' \in\mathcal{M}^{\mathrm{eff}} μ , μ ′ ∈ M eff . Consider any f ∈ F f \in F f ∈ F . Since M e f f \mathcal{M}^{\mathrm{eff}} M eff is essentially unique, V f ( μ ( f ) ) = V f ( μ ′ ( f ) ) V_f(\mu(f)) = V_f(\mu'(f)) V f ( μ ( f )) = V f ( μ ′ ( f )) . If μ ( f ) = μ ′ ( f ) \mu(f) = \mu'(f) μ ( f ) = μ ′ ( f ) , then for every ( μ ′ , u ′ ) ∈ I μ ′ (\mu',u') \in\mathcal{I}_{\mu'} ( μ ′ , u ′ ) ∈ I μ ′ , we have
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ′ ( w ) = V f ( μ ′ ( f ) ) − ∑ w ∈ μ ′ ( f ) u ′ ( w ) (4) V_f(\mu(f)) - \sum_{w \in\mu(f)} u'(w) = V_f(\mu'(f)) - \sum_{w \in\mu'(f)} u'(w) \tag*{(4)} V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ′ ( w ) = V f ( μ ′ ( f )) − w ∈ μ ′ ( f ) ∑ u ′ ( w ) (4)
Lemma 4 implies ( μ , u ) ↛ ( μ ′ , u ′ ) (\mu,u) \not\to(\mu',u') ( μ , u ) → ( μ ′ , u ′ ) for all ( μ , u ) ∈ I μ (\mu,u) \in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ . If μ ( f ) ≠ μ ′ ( f ) \mu(f) \ne\mu'(f) μ ( f ) = μ ′ ( f ) , then V f ( μ ( f ) ) = V f ( μ ′ ( f ) ) = 0 V_f(\mu(f)) = V_f(\mu'(f)) = 0 V f ( μ ( f )) = V f ( μ ′ ( f )) = 0 (by essential uniqueness). Hence, for every ( μ ′ , u ′ ) ∈ I μ ′ (\mu',u') \in\mathcal{I}_{\mu'} ( μ ′ , u ′ ) ∈ I μ ′ , we have u ′ ( w ) = 0 u'(w) = 0 u ′ ( w ) = 0 for all w ∈ μ ′ ( f ) w \in\mu'(f) w ∈ μ ′ ( f ) and using the fact that u ′ ( w ) ≥ 0 u'(w) \ge0 u ′ ( w ) ≥ 0 for all w w w , equation (3) holds with inequality (LHS ≤ \le ≤ RHS). Hence, Lemma 4 implies ( μ , u ) ↛ ( μ ′ , u ′ ) (\mu,u) \not\to(\mu',u') ( μ , u ) → ( μ ′ , u ′ ) for all ( μ , u ) ∈ I μ (\mu,u) \in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ . Finally, if μ = μ ′ \mu= \mu' μ = μ ′ , Observation 1 implies ( μ , u ) ↛ ( μ ′ , u ′ ) (\mu,u) \not\to(\mu',u') ( μ , u ) → ( μ ′ , u ′ ) for all ( μ , u ) ∈ I μ (\mu,u) \in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ . This shows that V \mathcal{V} V is internally stable.
External stability. Consider any outcome ( μ , u ) ∈ I ∖ V (\mu,u)\in\mathcal{I}\setminus\mathcal{V} ( μ , u ) ∈ I ∖ V . Hence, μ ∉ M e f f \mu\notin\mathcal{M}^{\mathrm{eff}} μ ∈ / M eff . By Lemma 2, there exists an efficient matching μ ∗ ∈ M e f f \mu^{\ast}\in\mathcal{M}^{\mathrm{eff}} μ ∗ ∈ M eff and an outcome ( μ ∗ , u ∗ ) ∈ I μ ∗ (\mu^{\ast},u^{\ast})\in\mathcal{I}_{\mu^{\ast}} ( μ ∗ , u ∗ ) ∈ I μ ∗ such that ( μ ∗ , u ∗ ) ⟶ ( μ , u ) (\mu^{\ast},u^{\ast})\longrightarrow(\mu,u) ( μ ∗ , u ∗ ) ⟶ ( μ , u ) . Hence, external stability follows.
Necessity: Suppose V \mathcal{V} V is a rich vNM-stable set. By Lemma 3, for every μ , μ ′ ∈ M ( V ) \mu,\mu'\in\mathcal{M}(\mathcal{V}) μ , μ ′ ∈ M ( V ) , we have
V f ( μ ( f ) ) = V f ( μ ′ ( f ) ) ∀ f ∈ F (5) V_f(\mu(f))=V_f(\mu'(f)) \qquad\forall f\in F \tag*{(5)} V f ( μ ( f )) = V f ( μ ′ ( f )) ∀ f ∈ F (5)
Suppose now that for some f ∈ F f\in F f ∈ F we have V f ( μ ( f ) ) = V f ( μ ′ ( f ) ) = p > 0 V_f(\mu(f))=V_f(\mu'(f))=p>0 V f ( μ ( f )) = V f ( μ ′ ( f )) = p > 0 but μ ( f ) ≠ μ ′ ( f ) \mu(f)\ne\mu'(f) μ ( f ) = μ ′ ( f ) .14 Without loss of generality, suppose there is some w ~ ∈ μ ( f ) ∖ μ ′ ( f ) \widetilde{w}\in\mu(f)\setminus\mu'(f) w ∈ μ ( f ) ∖ μ ′ ( f ) . Let u ~ \widetilde{u} u be a utility vector such that u ~ ( w ~ ) = p , u ~ ( w ) = 0 \widetilde{u}(\widetilde{w})=p,\widetilde{u}(w)=0 u ( w ) = p , u ( w ) = 0 for all w ≠ w ~ w\ne\widetilde{w} w = w . Clearly, u ~ \widetilde{u} u is such that ( μ , u ~ ) ∈ I μ (\mu,\widetilde{u})\in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ . Further, ( μ , u ~ ) (\mu,\widetilde{u}) ( μ , u ) is w ~ \widetilde{w} w -IR-maximal for μ \mu μ . Hence, by richness, ( μ , u ~ ) ∈ V (\mu,\widetilde{u})\in\mathcal{V} ( μ , u ) ∈ V . Moreover, all workers in μ ′ ( f ) \mu'(f) μ ′ ( f ) receive zero payoff in ( μ ′ , u ′ ) (\mu',u') ( μ ′ , u ′ ) , while firm f f f receives payoff p p p at ( μ ′ , u ′ ) (\mu',u') ( μ ′ , u ′ ) and payoff zero at ( μ , u ~ ) (\mu,\widetilde{u}) ( μ , u ) . Hence, ( μ ′ , u ′ ) ⟶ ( μ , u ~ ) (\mu',u')\longrightarrow(\mu,\widetilde{u}) ( μ ′ , u ′ ) ⟶ ( μ , u ) , contradicting internal stability (since both ( μ ′ , u ′ ) , ( μ , u ~ ) ∈ V (\mu',u'),(\mu,\widetilde{u})\in\mathcal{V} ( μ ′ , u ′ ) , ( μ , u ) ∈ V ). Thus, V f ( μ ( f ) ) = V f ( μ ′ ( f ) ) > 0 V_f(\mu(f))=V_f(\mu'(f))>0 V f ( μ ( f )) = V f ( μ ′ ( f )) > 0 implies that μ ( f ) = μ ′ ( f ) \mu(f)=\mu'(f) μ ( f ) = μ ′ ( f ) . Along with (4), this proves that M ( V ) \mathcal{M}(\mathcal{V}) M ( V ) is essentially unique.
It remains to show that M ( V ) = M e f f \mathcal{M}(\mathcal{V})=\mathcal{M}^{\mathrm{eff}} M ( V ) = M eff . First, note that by adding (4) for all f ∈ F f\in F f ∈ F , we see that
V ( μ ) = V ( μ ′ ) ∀ μ , μ ′ ∈ M ( V ) (6) V(\mu)=V(\mu') \qquad\forall\mu,\mu'\in\mathcal{M}(\mathcal{V}) \tag*{(6)} V ( μ ) = V ( μ ′ ) ∀ μ , μ ′ ∈ M ( V ) (6)
In other words, all matchings in M ( V ) \mathcal{M}(\mathcal{V}) M ( V ) generate the same surplus.
Suppose that there exists μ ∗ ∈ M e f f ∖ M ( V ) \mu^{\ast}\in\mathcal{M}^{\mathrm{eff}}\setminus\mathcal{M}(\mathcal{V}) μ ∗ ∈ M eff ∖ M ( V ) . Consider μ ˉ ∈ M ( V ) \bar{\mu}\in\mathcal{M}(\mathcal{V}) μ ˉ ∈ M ( V ) . By Proposition 1, there exists ( μ ∗ , u ∗ ) ∈ I μ ∗ (\mu^{\ast},u^{\ast})\in\mathcal{I}_{\mu^{\ast}} ( μ ∗ , u ∗ ) ∈ I μ ∗ such that ( μ ˉ , u ˉ ) ⟶̸ ( μ ∗ , u ∗ ) (\bar{\mu},\bar{u})\not\longrightarrow(\mu^{\ast},u^{\ast}) ( μ ˉ , u ˉ ) ⟶ ( μ ∗ , u ∗ ) for all ( μ ˉ , u ˉ ) ∈ I μ ˉ (\bar{\mu},\bar{u})\in\mathcal{I}_{\bar{\mu}} ( μ ˉ , u ˉ ) ∈ I μ ˉ .
We now show that this implication spreads to all μ ∈ M ( V ) \mu\in\mathcal{M}(\mathcal{V}) μ ∈ M ( V ) since M ( V ) \mathcal{M}(\mathcal{V}) M ( V ) is essentially unique. To see this, consider any μ ∈ M ( V ) \mu\in\mathcal{M}(\mathcal{V}) μ ∈ M ( V ) . Since ( μ ˉ , u ˉ ) ⟶̸ ( μ ∗ , u ∗ ) (\bar{\mu},\bar{u})\not\longrightarrow(\mu^{\ast},u^{\ast}) ( μ ˉ , u ˉ ) ⟶ ( μ ∗ , u ∗ ) for all ( μ ˉ , u ˉ ) ∈ I μ ˉ (\bar{\mu},\bar{u})\in\mathcal{I}_{\bar{\mu}} ( μ ˉ , u ˉ ) ∈ I μ ˉ , by Lemma 4, for all f ∈ F f\in F f ∈ F ,
V f ( μ ˉ ( f ) ) − ∑ w ∈ μ ˉ ( f ) u ∗ ( w ) ≤ V f ( μ ∗ ( f ) ) − ∑ w ∈ μ ∗ ( f ) u ∗ ( w ) V_f(\bar{\mu}(f))-\sum_{w\in\bar{\mu}(f)}u^{\ast}(w)\le V_f(\mu^{\ast}(f))-\sum_{w\in\mu^{\ast}(f)}u^{\ast}(w) V f ( μ ˉ ( f )) − w ∈ μ ˉ ( f ) ∑ u ∗ ( w ) ≤ V f ( μ ∗ ( f )) − w ∈ μ ∗ ( f ) ∑ u ∗ ( w )
Consider any f ∈ F f \in F f ∈ F . If μ ( f ) = μ ˉ ( f ) \mu(f) = \bar{\mu}(f) μ ( f ) = μ ˉ ( f ) , then
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ∗ ( w ) = V f ( μ ˉ ( f ) ) − ∑ w ∈ μ ˉ ( f ) u ∗ ( w ) ≤ V f ( μ ∗ ( f ) ) − ∑ w ∈ μ ∗ ( f ) u ∗ ( w ) V_f(\mu(f))-\sum_{w\in\mu(f)}u^*(w)=V_f(\bar{\mu}(f))-\sum_{w\in\bar{\mu}(f)}u^*(w)\le V_f(\mu^*(f))-\sum_{w\in\mu^*(f)}u^*(w) V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ∗ ( w ) = V f ( μ ˉ ( f )) − w ∈ μ ˉ ( f ) ∑ u ∗ ( w ) ≤ V f ( μ ∗ ( f )) − w ∈ μ ∗ ( f ) ∑ u ∗ ( w )
If μ ( f ) ≠ μ ˉ ( f ) \mu(f) \ne\bar{\mu}(f) μ ( f ) = μ ˉ ( f ) , then essential uniqueness implies V f ( μ ( f ) ) = V f ( μ ˉ ( f ) ) = 0 V_f(\mu(f)) = V_f(\bar{\mu}(f)) = 0 V f ( μ ( f )) = V f ( μ ˉ ( f )) = 0 . Hence,
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ∗ ( w ) = − ∑ w ∈ μ ( f ) u ∗ ( w ) ≤ 0 V_f(\mu(f))-\sum_{w\in\mu(f)}u^*(w)=-\sum_{w\in\mu(f)}u^*(w)\le0 V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ∗ ( w ) = − w ∈ μ ( f ) ∑ u ∗ ( w ) ≤ 0
whereas individual rationality of ( μ ∗ , u ∗ ) (\mu^*,u^*) ( μ ∗ , u ∗ ) implies
V f ( μ ∗ ( f ) ) − ∑ w ∈ μ ∗ ( f ) u ∗ ( w ) ≥ 0 V_f(\mu^*(f))-\sum_{w\in\mu^*(f)}u^*(w)\ge0 V f ( μ ∗ ( f )) − w ∈ μ ∗ ( f ) ∑ u ∗ ( w ) ≥ 0
Thus, in either case,
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ∗ ( w ) ≤ V f ( μ ∗ ( f ) ) − ∑ w ∈ μ ∗ ( f ) u ∗ ( w ) V_f(\mu(f))-\sum_{w\in\mu(f)}u^*(w)\le V_f(\mu^*(f))-\sum_{w\in\mu^*(f)}u^*(w) V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ∗ ( w ) ≤ V f ( μ ∗ ( f )) − w ∈ μ ∗ ( f ) ∑ u ∗ ( w )
By Lemma 4, no outcome in I μ \mathcal{I}_\mu I μ dominates ( μ ∗ , u ∗ ) (\mu^*,u^*) ( μ ∗ , u ∗ ) . Since this is true for every μ ∈ M ( V ) \mu\in\mathcal{M}(\mathcal{V}) μ ∈ M ( V ) , no outcome in V \mathcal{V} V dominates ( μ ∗ , u ∗ ) (\mu^*,u^*) ( μ ∗ , u ∗ ) :
( μ , u ) ↛ ( μ ∗ , u ∗ ) ∀ ( μ , u ) ∈ V (\mu,u)\not\to(\mu^*,u^*) \qquad\forall\,(\mu,u)\in\mathcal{V} ( μ , u ) → ( μ ∗ , u ∗ ) ∀ ( μ , u ) ∈ V
Since ( μ ∗ , u ∗ ) ∉ V (\mu^*,u^*)\notin\mathcal{V} ( μ ∗ , u ∗ ) ∈ / V , this contradicts external stability. Hence, every efficient matching belongs to M ( V ) \mathcal{M}(\mathcal{V}) M ( V ) . Using (6) , we conclude that M ( V ) = M e f f \mathcal{M}(\mathcal{V})=\mathcal{M}^{\mathrm{eff}} M ( V ) = M eff .
Finally, we argue that V = ⋃ μ ∈ M e f f I μ \mathcal{V}=\bigcup_{\mu\in\mathcal{M}^{\mathrm{eff}}}\mathcal{I}_\mu V = ⋃ μ ∈ M eff I μ . We have already established that V ⊂ ⋃ μ ∈ M e f f I μ \mathcal{V}\subset\bigcup_{\mu\in\mathcal{M}^{\mathrm{eff}}}\mathcal{I}_\mu V ⊂ ⋃ μ ∈ M eff I μ . Assume for contradiction that some efficient outcome ( μ ∗ , u ∗ ) ∉ V (\mu^*,u^*)\notin\mathcal{V} ( μ ∗ , u ∗ ) ∈ / V . Then, by external stability, there is some efficient outcome ( μ , u ) ∈ V (\mu,u)\in\mathcal{V} ( μ , u ) ∈ V and a firm f f f such that ( μ , u ) → f ( μ ∗ , u ∗ ) (\mu,u)\xrightarrow{f}(\mu^*,u^*) ( μ , u ) f ( μ ∗ , u ∗ ) :
u ( w ) ≥ u ∗ ( w ) ∀ w ∈ μ ( f ) u(w)\ge u^*(w)\qquad\forall\,w\in\mu(f) u ( w ) ≥ u ∗ ( w ) ∀ w ∈ μ ( f )
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ( w ) ≥ V f ( μ ∗ ( f ) ) − ∑ w ∈ μ ∗ ( f ) u ∗ ( w ) V_f(\mu(f))-\sum_{w\in\mu(f)}u(w)\ge V_f(\mu^*(f))-\sum_{w\in\mu^*(f)}u^*(w) V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ( w ) ≥ V f ( μ ∗ ( f )) − w ∈ μ ∗ ( f ) ∑ u ∗ ( w )
with one inequality strict. Since M e f f \mathcal{M}^{\mathrm{eff}} M eff is essentially unique, we get V f ( μ ( f ) ) = V f ( μ ∗ ( f ) ) V_f(\mu(f))=V_f(\mu^*(f)) V f ( μ ( f )) = V f ( μ ∗ ( f )) . Using this and adding all the previous inequalities, we get
∑ w ∈ μ ⋆ ( f ) u ⋆ ( w ) > ∑ w ∈ μ ( f ) u ⋆ ( w ) \sum_{w\in\mu^\star(f)} u^\star(w) > \sum_{w\in\mu(f)} u^\star(w) w ∈ μ ⋆ ( f ) ∑ u ⋆ ( w ) > w ∈ μ ( f ) ∑ u ⋆ ( w )
If μ ( f ) = μ ⋆ ( f ) \mu(f)=\mu^\star(f) μ ( f ) = μ ⋆ ( f ) , this is a contradiction. Else, by essential uniqueness, we have V f ( μ ( f ) ) = V f ( μ ⋆ ( f ) ) = 0 V_f(\mu(f))=V_f(\mu^\star(f))=0 V f ( μ ( f )) = V f ( μ ⋆ ( f )) = 0 . But then, IR implies that u ⋆ ( w ) = 0 u^\star(w)=0 u ⋆ ( w ) = 0 for all w ∈ μ ( f ) w\in\mu(f) w ∈ μ ( f ) and for all w ∈ μ ⋆ ( f ) w\in\mu^\star(f) w ∈ μ ⋆ ( f ) . This will again contradict the previous inequality. ■
Omitted Proofs of Lemmas
Proof of Lemma 1: Let V ⊆ I \mathcal{V}\subseteq\mathcal{I} V ⊆ I be a candidate vNM stable set. We consider multiple steps.
Step 1. Consider a matching μ ∉ { μ 1 , μ 2 , μ 3 } \mu\notin\{\mu_1,\mu_2,\mu_3\} μ ∈ / { μ 1 , μ 2 , μ 3 } . We know that if μ ∉ { μ 1 , μ 2 , μ 3 } \mu\notin\{\mu_1,\mu_2,\mu_3\} μ ∈ / { μ 1 , μ 2 , μ 3 } and ( μ , u w 1 , u w 2 , u w 3 ) ∈ I (\mu,u_{w_1},u_{w_2},u_{w_3})\in\mathcal{I} ( μ , u w 1 , u w 2 , u w 3 ) ∈ I , then u w k = 0 u_{w_k}=0 u w k = 0 for all k ∈ { 1 , 2 , 3 } k\in\{1,2,3\} k ∈ { 1 , 2 , 3 } . Hence, the only outcome corresponding to μ \mu μ which may belong to V \mathcal{V} V is ( μ , 0 , 0 , 0 ) (\mu,0,0,0) ( μ , 0 , 0 , 0 ) . Consider ( μ 1 , x , y , 0 ) ∈ I (\mu_1,x,y,0)\in\mathcal{I} ( μ 1 , x , y , 0 ) ∈ I where x + y ≤ 1 x+y\le1 x + y ≤ 1 and x , y ≥ 0 x,y\ge0 x , y ≥ 0 . In this case, ( μ 1 , x , y , 0 ) → f 1 ( μ , 0 , 0 , 0 ) (\mu_1,x,y,0)\xrightarrow{f_1}(\mu,0,0,0) ( μ 1 , x , y , 0 ) f 1 ( μ , 0 , 0 , 0 ) . A similar argument shows that ( μ 2 , 0 , x , y ) → f 2 ( μ , 0 , 0 , 0 ) (\mu_2,0,x,y)\xrightarrow{f_2}(\mu,0,0,0) ( μ 2 , 0 , x , y ) f 2 ( μ , 0 , 0 , 0 ) and ( μ 3 , x , 0 , y ) → f 3 ( μ , 0 , 0 , 0 ) (\mu_3,x,0,y)\xrightarrow{f_3}(\mu,0,0,0) ( μ 3 , x , 0 , y ) f 3 ( μ , 0 , 0 , 0 ) . Hence, if ( μ , 0 , 0 , 0 ) ∈ V (\mu,0,0,0)\in\mathcal{V} ( μ , 0 , 0 , 0 ) ∈ V for some μ ∉ { μ 1 , μ 2 , μ 3 } \mu\notin\{\mu_1,\mu_2,\mu_3\} μ ∈ / { μ 1 , μ 2 , μ 3 } , internal stability requires that no outcomes involving μ 1 , μ 2 , μ 3 \mu_1,\mu_2,\mu_3 μ 1 , μ 2 , μ 3 can be in V \mathcal{V} V . Hence, external stability requires that some ( μ , 0 , 0 , 0 ) (\mu,0,0,0) ( μ , 0 , 0 , 0 ) , where μ ∉ { μ 1 , μ 2 , μ 3 } \mu\notin\{\mu_1,\mu_2,\mu_3\} μ ∈ / { μ 1 , μ 2 , μ 3 } , must dominate ( μ 1 , x , y , 0 ) (\mu_1,x,y,0) ( μ 1 , x , y , 0 ) , which is not possible. Thus, V \mathcal{V} V only contains outcomes corresponding to efficient matchings μ 1 , μ 2 , μ 3 \mu_1,\mu_2,\mu_3 μ 1 , μ 2 , μ 3 .
Step 2. The outcome ( μ 1 , 1 , 0 , 0 ) (\mu_1,1,0,0) ( μ 1 , 1 , 0 , 0 ) cannot be dominated by ( μ 3 , x , 0 , y ) (\mu_3,x,0,y) ( μ 3 , x , 0 , y ) . This is because if ( μ 3 , x , 0 , y ) (\mu_3,x,0,y) ( μ 3 , x , 0 , y ) were to dominate ( μ 1 , 1 , 0 , 0 ) (\mu_1,1,0,0) ( μ 1 , 1 , 0 , 0 ) , then x = 1 x=1 x = 1 and hence, y = 0 y=0 y = 0 , So, ( μ 3 , 1 , 0 , 0 ) (\mu_3,1,0,0) ( μ 3 , 1 , 0 , 0 ) needs to dominate ( μ 1 , 1 , 0 , 0 ) (\mu_1,1,0,0) ( μ 1 , 1 , 0 , 0 ) , which is not possible because all firms get zero payoff in both the outcomes. Hence, it is not possible V = I μ 3 \mathcal{V}=\mathcal{I}_{\mu_3} V = I μ 3 . A similar argument extends this conclusion: it is not possible that V = I μ i \mathcal{V}=\mathcal{I}_{\mu_i} V = I μ i for any i ∈ { 1 , 2 , 3 } i\in\{1,2,3\} i ∈ { 1 , 2 , 3 } . By Observation 1, V ⊈ I μ i \mathcal{V}\not\subseteq\mathcal{I}_{\mu_i} V ⊆ I μ i for any i ∈ { 1 , 2 , 3 } i\in\{1,2,3\} i ∈ { 1 , 2 , 3 } .
Step 3. So, V \mathcal{V} V must contain an outcome each from I μ i \mathcal{I}_{\mu_i} I μ i for at least two values of i i i . Consider, without loss of generality, two outcomes a 1 ≡ ( μ 1 , x , y , 0 ) ∈ I a_1\equiv(\mu_1,x,y,0)\in\mathcal{I} a 1 ≡ ( μ 1 , x , y , 0 ) ∈ I and a 2 ≡ ( μ 2 , 0 , y ′ , z ′ ) ∈ I a_2\equiv(\mu_2,0,y',z')\in\mathcal{I} a 2 ≡ ( μ 2 , 0 , y ′ , z ′ ) ∈ I . Note that if y > y ′ y>y' y > y ′ , then a 1 → a 2 a_1\to a_2 a 1 → a 2 and if y ′ > y y'>y y ′ > y , then a 2 → a 1 a_2\to a_1 a 2 → a 1 . So, for internal stability, y = y ′ y=y' y = y ′ , i.e., a 2 = ( μ 2 , 0 , y , z ′ ) a_2=(\mu_2,0,y,z') a 2 = ( μ 2 , 0 , y , z ′ ) . But if z ′ > 0 z'>0 z ′ > 0 , we have a 2 → a 1 a_2\to a_1 a 2 → a 1 . Hence, internal stability forces z ′ = 0 z' = 0 z ′ = 0 . Similarly, x = 0 x = 0 x = 0 . So, a 1 = ( μ 1 , 0 , y , 0 ) a_1 = (\mu_1, 0, y, 0) a 1 = ( μ 1 , 0 , y , 0 ) and a 2 = ( μ 2 , 0 , y , 0 ) a_2 = (\mu_2, 0, y, 0) a 2 = ( μ 2 , 0 , y , 0 ) . If y < 1 y < 1 y < 1 , then firm 1 gets positive payoff in a 1 a_1 a 1 (and firm 2 gets positive payoff in a 2 a_2 a 2 ), and a 1 → a 2 a_1 \to a_2 a 1 → a 2 in that case. So, internal stability forces y = 1 y = 1 y = 1 . Hence, for internal stability, the only outcomes in I μ 1 \mathcal{I}_{\mu_1} I μ 1 and I μ 2 \mathcal{I}_{\mu_2} I μ 2 that can be in V \mathcal{V} V are ( μ 1 , 0 , 1 , 0 ) (\mu_1, 0, 1, 0) ( μ 1 , 0 , 1 , 0 ) and ( μ 2 , 0 , 1 , 0 ) (\mu_2, 0, 1, 0) ( μ 2 , 0 , 1 , 0 ) .
Now, consider a 3 ≡ ( μ 3 , x ′ ′ , 0 , z ′ ′ ) a_3 \equiv(\mu_3, x'', 0, z'') a 3 ≡ ( μ 3 , x ′′ , 0 , z ′′ ) . Can a 3 ∈ V a_3 \in\mathcal{V} a 3 ∈ V ? Since a 1 ∈ V a_1 \in\mathcal{V} a 1 ∈ V , we argue that a 3 ∉ V a_3 \notin\mathcal{V} a 3 ∈ / V due to internal stability. This is because a 3 → a 1 a_3 \to a_1 a 3 → a 1 (since firm 3, and workers 1 and 3 get zero payoff in a 1 a_1 a 1 , and at least one of them must get positive payoff in a 3 a_3 a 3 ). Hence a 3 ∉ V a_3 \notin\mathcal{V} a 3 ∈ / V for any values of 1 ≥ x ′ ′ ≥ 0 1 \ge x'' \ge0 1 ≥ x ′′ ≥ 0 and 1 ≥ z ′ ′ ≥ 0 1 \ge z'' \ge0 1 ≥ z ′′ ≥ 0 . So, the only kind of outcomes in V \mathcal{V} V has one of the matchings in { μ 1 , μ 2 , μ 3 } \{\mu_1, \mu_2, \mu_3\} { μ 1 , μ 2 , μ 3 } and assigns the total surplus 1 to one of the workers matched.
But then, consider a ^ 3 ≡ ( μ 3 , 1 2 , 0 , 1 2 ) \hat{a}_3 \equiv(\mu_3, \frac{1}{2}, 0, \frac{1}{2}) a ^ 3 ≡ ( μ 3 , 2 1 , 0 , 2 1 ) . For external stability, either a 1 a_1 a 1 or a 2 a_2 a 2 must dominate a ^ 3 \hat{a}_3 a ^ 3 . But a 1 a_1 a 1 cannot dominate a ^ 3 \hat{a}_3 a ^ 3 because worker 1 gets positive payoff in a ^ 3 \hat{a}_3 a ^ 3 but gets zero in a 1 a_1 a 1 . Similarly, a 2 a_2 a 2 cannot dominate a ^ 3 \hat{a}_3 a ^ 3 because worker 3 gets positive payoff in a ^ 3 \hat{a}_3 a ^ 3 but gets zero in a 2 a_2 a 2 . By Observation 1, no outcome involving μ 3 \mu_3 μ 3 can dominate a ^ 3 \hat{a}_3 a ^ 3 . This implies that V \mathcal{V} V fails to satisfy external stability.
Proof of Lemma 2: We do the proof in two steps.
Step 1. We show that there exists some firm f f f such that μ ( f ) ≠ μ ∗ ( f ) \mu(f) \ne\mu^*(f) μ ( f ) = μ ∗ ( f ) and
V f ( μ ∗ ( f ) ) > V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ( w ) + ∑ w ∈ μ ∗ ( f ) u ( w ) (7) V_f(\mu^*(f)) > V_f(\mu(f)) - \sum_{w \in\mu(f)} u(w) + \sum_{w \in\mu^*(f)} u(w) \tag*{(7)} V f ( μ ∗ ( f )) > V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ( w ) + w ∈ μ ∗ ( f ) ∑ u ( w ) (7)
If this is not true, the reverse inequality holds for all firms whose matchings differ in μ \mu μ and μ ∗ \mu^* μ ∗ . Adding them together along with the firms whose matchings coincide (note the inequality (6) is an equality if μ ( f ) = μ ∗ ( f ) \mu(f) = \mu^*(f) μ ( f ) = μ ∗ ( f ) ) gives
∑ f ∈ F V f ( μ ∗ ( f ) ) ≤ ∑ f ∈ F V f ( μ ( f ) ) − ∑ f ∈ F ∑ w ∈ μ ( f ) u ( w ) + ∑ f ∈ F ∑ w ∈ μ ∗ ( f ) u ( w ) = ∑ f ∈ F V f ( μ ( f ) ) − ∑ w ∈ W u ( w ) + ∑ f ∈ F ∑ w ∈ μ ∗ ( f ) u ( w ) ≤ ∑ f ∈ F V f ( μ ( f ) ) − ∑ w ∈ W u ( w ) + ∑ w ∈ W u ( w ) = ∑ f ∈ F V f ( μ ( f ) ) , \begin{aligned}
\sum_{f \in F} V_f(\mu^*(f)) &\le\sum_{f \in F} V_f(\mu(f)) - \sum_{f \in F}\sum_{w \in\mu(f)} u(w) + \sum_{f \in F}\sum_{w \in\mu^*(f)} u(w) \\
&= \sum_{f \in F} V_f(\mu(f)) - \sum_{w \in W} u(w) + \sum_{f \in F}\sum_{w \in\mu^*(f)} u(w) \\
&\le\sum_{f \in F} V_f(\mu(f)) - \sum_{w \in W} u(w) + \sum_{w \in W} u(w) \\
&= \sum_{f \in F} V_f(\mu(f)),
\end{aligned} f ∈ F ∑ V f ( μ ∗ ( f )) ≤ f ∈ F ∑ V f ( μ ( f )) − f ∈ F ∑ w ∈ μ ( f ) ∑ u ( w ) + f ∈ F ∑ w ∈ μ ∗ ( f ) ∑ u ( w ) = f ∈ F ∑ V f ( μ ( f )) − w ∈ W ∑ u ( w ) + f ∈ F ∑ w ∈ μ ∗ ( f ) ∑ u ( w ) ≤ f ∈ F ∑ V f ( μ ( f )) − w ∈ W ∑ u ( w ) + w ∈ W ∑ u ( w ) = f ∈ F ∑ V f ( μ ( f )) ,
where the first equality follows from the fact that unmatched workers in ( μ , u ) (\mu, u) ( μ , u ) must get zero payoff (IR) and the second inequality follows because u ( w ) ≥ 0 u(w) \ge0 u ( w ) ≥ 0 for all w ∈ W w \in W w ∈ W (again IR). But this contradicts the fact that μ \mu μ is not an efficient matching and μ ∗ \mu^{*} μ ∗ is efficient. Hence, there exists a firm f f f such that μ ( f ) ≠ μ ∗ ( f ) \mu(f) \ne\mu^{*}(f) μ ( f ) = μ ∗ ( f ) and Inequality (7) holds. Let
Δ : = V f ( μ ∗ ( f ) ) − V f ( μ ( f ) ) + ∑ w ∈ μ ( f ) u ( w ) − ∑ w ∈ μ ∗ ( f ) u ( w ) (8) \Delta:= V_f(\mu^{*}(f)) - V_f(\mu(f)) + \sum_{w \in\mu(f)} u(w) - \sum_{w \in\mu^{*}(f)} u(w) \tag*{(8)} Δ := V f ( μ ∗ ( f )) − V f ( μ ( f )) + w ∈ μ ( f ) ∑ u ( w ) − w ∈ μ ∗ ( f ) ∑ u ( w ) (8)
By Inequality (7) , we have Δ > 0 \Delta> 0 Δ > 0 .
Step 2. We construct u ∗ u^{*} u ∗ such that ( μ ∗ , u ∗ ) ∈ I μ ∗ (\mu^{*}, u^{*}) \in\mathcal{I}_{\mu^{*}} ( μ ∗ , u ∗ ) ∈ I μ ∗ and ( μ ∗ , u ∗ ) → f ( μ , u ) (\mu^{*}, u^{*}) \xrightarrow{f} (\mu, u) ( μ ∗ , u ∗ ) f ( μ , u ) , where f f f is the identified firm in Step 1. The u ∗ u^{*} u ∗ is defined as follows:
u ∗ ( w ) = { u ( w ) + Δ ∣ μ ∗ ( f ) ∣ if w ∈ μ ∗ ( f ) 0 otherwise u^{*}(w) =
\begin{cases}
u(w) + \dfrac{\Delta}{\lvert\mu^{*}(f) \rvert} & \text{if } w \in\mu^{*}(f) \\
0 & \text{otherwise}
\end{cases} u ∗ ( w ) = ⎩ ⎨ ⎧ u ( w ) + ∣ μ ∗ ( f )∣ Δ 0 if w ∈ μ ∗ ( f ) otherwise
Since u ( w ) ≥ 0 u(w) \ge0 u ( w ) ≥ 0 , we have u ∗ ( w ) ≥ 0 u^{*}(w) \ge0 u ∗ ( w ) ≥ 0 . Further, u ∗ ( w ) > u ( w ) u^{*}(w) > u(w) u ∗ ( w ) > u ( w ) for all w ∈ μ ∗ ( f ) w \in\mu^{*}(f) w ∈ μ ∗ ( f ) . The utility of every firm f ′ ≠ f f^{\prime} \ne f f ′ = f from the outcome ( μ ∗ , u ∗ ) (\mu^{*}, u^{*}) ( μ ∗ , u ∗ ) is V f ′ ( μ ∗ ( f ′ ) ) V_{f^{\prime}}(\mu^{*}(f^{\prime})) V f ′ ( μ ∗ ( f ′ )) (since u ∗ ( w ) = 0 u^{*}(w) = 0 u ∗ ( w ) = 0 for all w ∈ μ ∗ ( f ′ ) w \in\mu^{*}(f^{\prime}) w ∈ μ ∗ ( f ′ ) ), which is non-negative.15 Finally, the utility of firm f f f from outcome ( μ ∗ , u ∗ ) (\mu^{*}, u^{*}) ( μ ∗ , u ∗ ) is
V f ( μ ∗ ( f ) ) − ∑ w ∈ μ ∗ ( f ) u ∗ ( w ) = V f ( μ ∗ ( f ) ) − ∑ w ∈ μ ∗ ( f ) u ( w ) − Δ = V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ( w ) (9) V_f(\mu^{*}(f)) - \sum_{w \in\mu^{*}(f)} u^{*}(w) = V_f(\mu^{*}(f)) - \sum_{w \in\mu^{*}(f)} u(w) - \Delta= V_f(\mu(f)) - \sum_{w \in\mu(f)} u(w) \tag*{(9)} V f ( μ ∗ ( f )) − w ∈ μ ∗ ( f ) ∑ u ∗ ( w ) = V f ( μ ∗ ( f )) − w ∈ μ ∗ ( f ) ∑ u ( w ) − Δ = V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ( w ) (9)
where the last equality follows from (8) . Hence, the payoff of firm f f f is the same in the two outcomes: ( μ , u ) (\mu, u) ( μ , u ) and ( μ ∗ , u ∗ ) (\mu^{*}, u^{*}) ( μ ∗ , u ∗ ) . Since ( μ , u ) ∈ I (\mu, u) \in\mathcal{I} ( μ , u ) ∈ I , we thus conclude that ( μ ∗ , u ∗ ) ∈ I (\mu^{*}, u^{*}) \in\mathcal{I} ( μ ∗ , u ∗ ) ∈ I . Further, since each worker in μ ∗ ( f ) \mu^{*}(f) μ ∗ ( f ) is better off in ( μ ∗ , u ∗ ) (\mu^{*}, u^{*}) ( μ ∗ , u ∗ ) than ( μ , u ) (\mu, u) ( μ , u ) , we conclude that ( μ ∗ , u ∗ ) → f ( μ , u ) (\mu^{*}, u^{*}) \xrightarrow{f} (\mu, u) ( μ ∗ , u ∗ ) f ( μ , u ) . ■
Proof of Lemma 4. (2) ⇒ \Rightarrow ⇒ (1). Suppose for some ( μ , u ) ∈ I μ (\mu, u) \in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ , we have ( μ , u ) → f ( μ ′ , u ′ ) (\mu, u) \xrightarrow{f} (\mu^{\prime}, u^{\prime}) ( μ , u ) f ( μ ′ , u ′ ) for some firm f f f . Then,
u ( w ) ≥ u ′ ( w ) ∀ w ∈ μ ( f ) u(w) \ge u^{\prime}(w) \qquad\forall\, w \in\mu(f) u ( w ) ≥ u ′ ( w ) ∀ w ∈ μ ( f )
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ( w ) ≥ V f ( μ ′ ( f ) ) − ∑ w ∈ μ ′ ( f ) u ′ ( w ) V_f(\mu(f)) - \sum_{w \in\mu(f)} u(w) \ge V_f(\mu^{\prime}(f)) - \sum_{w \in\mu^{\prime}(f)} u^{\prime}(w) V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ( w ) ≥ V f ( μ ′ ( f )) − w ∈ μ ′ ( f ) ∑ u ′ ( w )
with one inequality strict. Adding these inequalities contradicts (2) for f f f . Hence (2) ⇒ \Rightarrow ⇒ (1).
(1) ⇒ \Rightarrow ⇒ (2). Suppose (2) does not hold for firm f f f . That is,
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ′ ( w ) > V f ( μ ′ ( f ) ) − ∑ w ∈ μ ′ ( f ) u ′ ( w ) (10) V_f(\mu(f))-\sum_{w\in\mu(f)}u'(w)>V_f(\mu'(f))-\sum_{w\in\mu'(f)}u'(w) \tag*{(10)} V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ′ ( w ) > V f ( μ ′ ( f )) − w ∈ μ ′ ( f ) ∑ u ′ ( w ) (10)
Let ( μ , u ^ ) ∈ I μ (\mu,\hat{u})\in\mathcal{I}_{\mu} ( μ , u ^ ) ∈ I μ (such an outcome exists since μ \mu μ is IR-feasible). Define the outcome ( μ , u ) (\mu,u) ( μ , u ) as follows
u ( w ) = { u ′ ( w ) if w ∈ μ ( f ) u ^ ( w ) otherwise u(w)=
\begin{cases}
u'(w) & \text{if } w\in\mu(f)\\
\hat{u}(w) & \text{otherwise}
\end{cases} u ( w ) = { u ′ ( w ) u ^ ( w ) if w ∈ μ ( f ) otherwise
We first show that ( μ , u ) ∈ I μ (\mu,u)\in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ . Since ( μ ′ , u ′ ) , ( μ , u ^ ) ∈ I (\mu',u'),(\mu,\hat{u})\in\mathcal{I} ( μ ′ , u ′ ) , ( μ , u ^ ) ∈ I , u ( w ) ≥ 0 u(w)\geq0 u ( w ) ≥ 0 for all w ∈ W w\in W w ∈ W and for all f ′ ≠ f f'\ne f f ′ = f ,
0 ≤ V f ′ ( μ ( f ′ ) ) − ∑ w ∈ μ ( f ′ ) u ^ ( w ) = V f ′ ( μ ( f ′ ) ) − ∑ w ∈ μ ( f ′ ) u ( w ) 0\leq V_{f'}(\mu(f'))-\sum_{w\in\mu(f')}\hat{u}(w)=V_{f'}(\mu(f'))-\sum_{w\in\mu(f')}u(w) 0 ≤ V f ′ ( μ ( f ′ )) − w ∈ μ ( f ′ ) ∑ u ^ ( w ) = V f ′ ( μ ( f ′ )) − w ∈ μ ( f ′ ) ∑ u ( w )
where the inequality follows from ( μ , u ^ ) ∈ I (\mu,\hat{u})\in\mathcal{I} ( μ , u ^ ) ∈ I and the equality follows from definition of u u u . For firm f f f ,
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ( w ) = V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ′ ( w ) > V f ( μ ′ ( f ) ) − ∑ w ∈ μ ′ ( f ) u ′ ( w ) ≥ 0 V_f(\mu(f))-\sum_{w\in\mu(f)}u(w)=V_f(\mu(f))-\sum_{w\in\mu(f)}u'(w)>V_f(\mu'(f))-\sum_{w\in\mu'(f)}u'(w)\geq0 V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ( w ) = V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ′ ( w ) > V f ( μ ′ ( f )) − w ∈ μ ′ ( f ) ∑ u ′ ( w ) ≥ 0
where the strict inequality is due to (10) and last inequality is true because ( μ ′ , u ′ ) ∈ I (\mu',u')\in\mathcal{I} ( μ ′ , u ′ ) ∈ I . Hence, ( μ , u ) ∈ I μ (\mu,u)\in\mathcal{I}_{\mu} ( μ , u ) ∈ I μ .
Further, by construction of u u u , u ( w ) = u ′ ( w ) u(w)=u'(w) u ( w ) = u ′ ( w ) for all w ∈ μ ( f ) w\in\mu(f) w ∈ μ ( f ) and (10) ensures that
V f ( μ ( f ) ) − ∑ w ∈ μ ( f ) u ( w ) > V f ( μ ′ ( f ) ) − ∑ w ∈ μ ′ ( f ) u ′ ( w ) V_f(\mu(f))-\sum_{w\in\mu(f)}u(w)>V_f(\mu'(f))-\sum_{w\in\mu'(f)}u'(w) V f ( μ ( f )) − w ∈ μ ( f ) ∑ u ( w ) > V f ( μ ′ ( f )) − w ∈ μ ′ ( f ) ∑ u ′ ( w )
Thus, ( μ , u ) → f ( μ ′ , u ′ ) (\mu,u)\xrightarrow{f}(\mu',u') ( μ , u ) f ( μ ′ , u ′ ) . Hence, (1) ⇒ \Rightarrow ⇒ (2). ■ \blacksquare ■
Proof of Lemma 5. Suppose there exists a flow ϕ \phi ϕ in the directed graph. Fix w ∈ W w\in W w ∈ W . Suppose there is an incoming edge from f ^ \hat{f} f ^ (i.e., f ≡ μ ( w ) f\equiv\mu(w) f ≡ μ ( w ) ) and an outgoing edge to f ′ ≡ μ ′ ( w ) f'\equiv\mu'(w) f ′ ≡ μ ′ ( w ) at w w w , then flow balancing will imply ϕ ( w , f ′ ) = ϕ ( f ^ , w ) \phi(w,f')=\phi(\hat{f},w) ϕ ( w , f ′ ) = ϕ ( f ^ , w ) , and then set u ′ ( w ) = ϕ ( w , f ′ ) = ϕ ( f ^ , w ) u'(w)=\phi(w,f')=\phi(\hat{f},w) u ′ ( w ) = ϕ ( w , f ′ ) = ϕ ( f ^ , w ) . We show that this u ′ u' u ′ satisfies (ES) and (IR). To see this, pick f ∈ F f \in F f ∈ F . The inflow to vertex f f f is equal to the flow from f f f to f ^ \hat{f} f ^ (since b ( f ) = 0 b(f)=0 b ( f ) = 0 and flow balancing must hold), and inflow (and outflow) is equal to
∑ ( w , f ) ∈ E ϕ ( w , f ) = ∑ w ∈ μ ′ ( f ) u ′ ( w ) ≤ c ( f , f ^ ) = V f ( μ ′ ( f ) ) \sum_{(w,f)\in E}\phi(w,f)=\sum_{w\in\mu'(f)}u'(w)\leq c(f,\hat{f})=V_f(\mu'(f)) ( w , f ) ∈ E ∑ ϕ ( w , f ) = w ∈ μ ′ ( f ) ∑ u ′ ( w ) ≤ c ( f , f ^ ) = V f ( μ ′ ( f ))
where the inequality follows because flow satisfies capacity constraint. Hence, (IR) holds.
Now, consider vertex f ^ \hat{f} f ^ and flow balancing at this vertex. Total inflow is equal to sum of inflows from f f f and from v 0 v_0 v 0 . Flow from f f f to f ^ \hat{f} f ^ is equal to the inflow to vertex f f f , which in turn is equal to ∑ w ∈ μ ′ ( f ) u ′ ( w ) \sum_{w\in\mu'(f)}u'(w) ∑ w ∈ μ ′ ( f ) u ′ ( w ) . Hence, total inflow to f ^ \hat{f} f ^ is equal to
∑ w ∈ μ ′ ( f ) u ′ ( w ) + ϕ ( v 0 , f ^ ) \sum_{w\in\mu'(f)}u'(w)+\phi(v_0,\hat{f}) w ∈ μ ′ ( f ) ∑ u ′ ( w ) + ϕ ( v 0 , f ^ )
Total outflow from f ^ \hat{f} f ^ is
∑ ( f ^ , w ) ∈ E ϕ ( f ^ , w ) = ∑ w ∈ μ ( f ) ϕ ( f ^ , w ) = ∑ w ∈ μ ( f ) u ′ ( w ) \sum_{(\hat{f},w)\in E}\phi(\hat{f},w)=\sum_{w\in\mu(f)}\phi(\hat{f},w)=\sum_{w\in\mu(f)}u'(w) ( f ^ , w ) ∈ E ∑ ϕ ( f ^ , w ) = w ∈ μ ( f ) ∑ ϕ ( f ^ , w ) = w ∈ μ ( f ) ∑ u ′ ( w )
Using the fact that b ( f ^ ) = V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) b(\hat{f})=V_f(\mu'(f))-V_f(\mu(f)) b ( f ^ ) = V f ( μ ′ ( f )) − V f ( μ ( f )) , flow balancing at f ^ \hat{f} f ^ gives us
∑ w ∈ μ ′ ( f ) u ′ ( w ) + ϕ ( v 0 , f ^ ) − ∑ w ∈ μ ( f ) u ′ ( w ) = V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) \sum_{w\in\mu'(f)}u'(w)+\phi(v_0,\hat{f})-\sum_{w\in\mu(f)}u'(w)=V_f(\mu'(f))-V_f(\mu(f)) w ∈ μ ′ ( f ) ∑ u ′ ( w ) + ϕ ( v 0 , f ^ ) − w ∈ μ ( f ) ∑ u ′ ( w ) = V f ( μ ′ ( f )) − V f ( μ ( f ))
Since ϕ ( v 0 , f ^ ) ≥ 0 \phi(v_0,\hat{f})\geq0 ϕ ( v 0 , f ^ ) ≥ 0 , we get
∑ w ∈ μ ′ ( f ) u ′ ( w ) − ∑ w ∈ μ ( f ) u ′ ( w ) ≤ V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) \sum_{w\in\mu'(f)}u'(w)-\sum_{w\in\mu(f)}u'(w)\leq V_f(\mu'(f))-V_f(\mu(f)) w ∈ μ ′ ( f ) ∑ u ′ ( w ) − w ∈ μ ( f ) ∑ u ′ ( w ) ≤ V f ( μ ′ ( f )) − V f ( μ ( f ))
Hence, (ES) holds for firm f f f .
The converse proof follows similar arguments. Suppose u ′ u' u ′ is a feasible solution to (ES) and (IR). Then, we can construct a flow in G \mathcal{G} G from it. For every w ∈ W w\in W w ∈ W , since μ ′ ( w ) ≠ ∅ \mu'(w)\neq\varnothing μ ′ ( w ) = ∅ and μ ( w ) ≠ ∅ \mu(w)\neq\varnothing μ ( w ) = ∅ , we can set ϕ ( w , μ ′ ( w ) ) = ϕ ( f ^ , w ) : = u ′ ( w ) \phi(w,\mu'(w))=\phi(\hat{f},w):=u'(w) ϕ ( w , μ ′ ( w )) = ϕ ( f ^ , w ) := u ′ ( w ) , where μ ( w ) = f \mu(w)=f μ ( w ) = f . This balances flow at w w w . Now, at any f ∈ F f\in F f ∈ F , let
ϕ ( f , f ^ ) : = ∑ w ∈ μ ′ ( f ) u ′ ( w ) = ∑ w ∈ μ ′ ( f ) ϕ ( w , f ) \phi(f,\hat{f}):=\sum_{w\in\mu'(f)}u'(w)=\sum_{w\in\mu'(f)}\phi(w,f) ϕ ( f , f ^ ) := w ∈ μ ′ ( f ) ∑ u ′ ( w ) = w ∈ μ ′ ( f ) ∑ ϕ ( w , f )
This balances flow at f f f . Further, since u ′ u' u ′ satisfies (IR ), this means
ϕ ( f , f ^ ) = ∑ w ∈ μ ′ ( f ) u ′ ( w ) ≤ V f ( μ ′ ( f ) ) = c ( f , f ^ ) \phi(f,\hat{f})=\sum_{w\in\mu'(f)}u'(w)\le V_f(\mu'(f))=c(f,\hat{f}) ϕ ( f , f ^ ) = w ∈ μ ′ ( f ) ∑ u ′ ( w ) ≤ V f ( μ ′ ( f )) = c ( f , f ^ )
Hence, capacity constraint on edge ( f , f ^ ) (f,\hat{f}) ( f , f ^ ) holds.16
Now to define the flow ( v 0 , f ^ ) (v_0,\hat{f}) ( v 0 , f ^ ) , let
ϕ ( v 0 , f ^ ) : = [ V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) ] − [ ∑ w ∈ μ ′ ( f ) u ′ ( w ) − ∑ w ∈ μ ( f ) u ′ ( w ) ] \phi(v_0,\hat{f}):=\left[V_f(\mu'(f))-V_f(\mu(f))\right]-\left[\sum_{w\in\mu'(f)}u'(w)-\sum_{w\in\mu(f)}u'(w)\right] ϕ ( v 0 , f ^ ) := [ V f ( μ ′ ( f )) − V f ( μ ( f )) ] − w ∈ μ ′ ( f ) ∑ u ′ ( w ) − w ∈ μ ( f ) ∑ u ′ ( w )
Since u ′ u' u ′ satisfies (ES ), this is non-negative. Also,
ϕ ( v 0 , f ^ ) ≤ V f ( μ ′ ( f ) ) + ∑ w ∈ μ ( f ) ∖ μ ′ ( f ) u ′ ( w ) ≤ V f ( μ ′ ( f ) ) + ∑ f ′ ≠ f V f ′ ( μ ′ ( f ′ ) ) ≤ V ( μ ′ ) < c ( v 0 , f ^ ) , \phi(v_0,\hat{f})\le V_f(\mu'(f))+\sum_{w\in\mu(f)\setminus\mu'(f)}u'(w)\le V_f(\mu'(f))+\sum_{f'\ne f}V_{f'}(\mu'(f'))\le V(\mu')<c(v_0,\hat{f}), ϕ ( v 0 , f ^ ) ≤ V f ( μ ′ ( f )) + w ∈ μ ( f ) ∖ μ ′ ( f ) ∑ u ′ ( w ) ≤ V f ( μ ′ ( f )) + f ′ = f ∑ V f ′ ( μ ′ ( f ′ )) ≤ V ( μ ′ ) < c ( v 0 , f ^ ) ,
where the second inequality uses the fact that ( μ ′ , u ′ ) (\mu',u') ( μ ′ , u ′ ) is an IR outcome and the last inequality uses the fact that the capacity of edge ( v 0 , f ^ ) (v_0,\hat{f}) ( v 0 , f ^ ) is sufficiently large. Hence, capacity constraint of edge ( v 0 , f ^ ) (v_0,\hat{f}) ( v 0 , f ^ ) holds for each f ∈ F f\in F f ∈ F .
Next,
ϕ ( v 0 , f ^ ) = [ V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) ] − [ ∑ w ∈ μ ′ ( f ) u ′ ( w ) − ∑ w ∈ μ ( f ) u ′ ( w ) ] = b ( f ^ ) − [ ϕ ( f , f ^ ) − ∑ w ∈ μ ( f ) ϕ ( f ^ , w ) ] \phi(v_0,\hat{f})=\left[V_f(\mu'(f))-V_f(\mu(f))\right]-\left[\sum_{w\in\mu'(f)}u'(w)-\sum_{w\in\mu(f)}u'(w)\right]=b(\hat{f})-\left[\phi(f,\hat{f})-\sum_{w\in\mu(f)}\phi(\hat{f},w)\right] ϕ ( v 0 , f ^ ) = [ V f ( μ ′ ( f )) − V f ( μ ( f )) ] − w ∈ μ ′ ( f ) ∑ u ′ ( w ) − w ∈ μ ( f ) ∑ u ′ ( w ) = b ( f ^ ) − ϕ ( f , f ^ ) − w ∈ μ ( f ) ∑ ϕ ( f ^ , w )
⟹ ϕ ( v 0 , f ^ ) + ϕ ( f , f ^ ) − ∑ w ∈ μ ( f ) ϕ ( f ^ , w ) = b ( f ^ ) \Longrightarrow\phi(v_0,\hat{f})+\phi(f,\hat{f})-\sum_{w\in\mu(f)}\phi(\hat{f},w)=b(\hat{f}) ⟹ ϕ ( v 0 , f ^ ) + ϕ ( f , f ^ ) − w ∈ μ ( f ) ∑ ϕ ( f ^ , w ) = b ( f ^ )
This means flow balancing holds at f ^ \hat{f} f ^ .
Finally, at vertex v 0 v_0 v 0 ,
∑ f ∈ F ϕ ( v 0 , f ^ ) = ∑ f ∈ F [ V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) ] − ∑ f ∈ F [ ∑ w ∈ μ ′ ( f ) u ′ ( w ) − ∑ w ∈ μ ( f ) u ′ ( w ) ] = ∑ f ∈ F [ V f ( μ ′ ( f ) ) − V f ( μ ( f ) ) ] = − b ( v 0 ) \begin{aligned}
\sum_{f\in F}\phi(v_0,\hat{f})=\sum_{f\in F}\left[V_f(\mu'(f))-V_f(\mu(f))\right]-\sum_{f\in F}\left[\sum_{w\in\mu'(f)}u'(w)-\sum_{w\in\mu(f)}u'(w)\right] \\
&=\sum_{f\in F}\left[V_f(\mu'(f))-V_f(\mu(f))\right]=-b(v_0)
\end{aligned} f ∈ F ∑ ϕ ( v 0 , f ^ ) = f ∈ F ∑ [ V f ( μ ′ ( f )) − V f ( μ ( f )) ] − f ∈ F ∑ w ∈ μ ′ ( f ) ∑ u ′ ( w ) − w ∈ μ ( f ) ∑ u ′ ( w ) = f ∈ F ∑ [ V f ( μ ′ ( f )) − V f ( μ ( f )) ] = − b ( v 0 )
where the second equality follows because all workers are matched in μ ′ \mu' μ ′ and μ \mu μ , and hence,
∑ f ∈ F [ ∑ w ∈ μ ′ ( f ) u ′ ( w ) − ∑ w ∈ μ ( f ) u ′ ( w ) ] = 0 \sum_{f\in F}\left[\sum_{w\in\mu'(f)}u'(w)-\sum_{w\in\mu(f)}u'(w)\right]=0 f ∈ F ∑ w ∈ μ ′ ( f ) ∑ u ′ ( w ) − w ∈ μ ( f ) ∑ u ′ ( w ) = 0
Since there are no incoming edges to v 0 v_0 v 0 , this shows that flow balancing holds at v 0 v_0 v 0 also. ■
A vNM stable set with only inefficient outcomes
Example 4 (a vNM stable set with only inefficient outcomes). Consider the following economy. There are three firms F = { f 1 , f 2 , f 3 } F=\{f_1,f_2,f_3\} F = { f 1 , f 2 , f 3 } and three workers W = { w 1 , w 2 , w 3 } W=\{w_1,w_2,w_3\} W = { w 1 , w 2 , w 3 } . The surplus generated by each firm is summarized in Table 2 .
Table 2. Surplus of firms and workers
There is a unique efficient matching μ ⋆ \mu^\star μ ⋆ given by μ ⋆ ( f 1 ) = { w 1 , w 2 } \mu^\star(f_1)=\{w_1,w_2\} μ ⋆ ( f 1 ) = { w 1 , w 2 } , μ ⋆ ( f 2 ) = ∅ \mu^\star(f_2)=\varnothing μ ⋆ ( f 2 ) = ∅ , and μ ⋆ ( f 3 ) = { w 3 } \mu^\star(f_3)=\{w_3\} μ ⋆ ( f 3 ) = { w 3 } . The core is empty for this economy.
Consider the following three inefficient matchings:
μ 1 : μ 1 ( f 1 ) = { w 1 , w 3 } μ 1 ( f 2 ) = { w 2 } μ 1 ( f 3 ) = ∅ μ 2 : μ 2 ( f 1 ) = { w 1 , w 2 } μ 2 ( f 2 ) = { w 3 } μ 2 ( f 3 ) = ∅ μ 3 : μ 3 ( f 1 ) = ∅ μ 3 ( f 2 ) = { w 1 } μ 3 ( f 3 ) = { w 2 , w 3 } \begin{aligned}
\mu_1:\quad&\mu_1(f_1)=\{w_1,w_3\} \qquad\mu_1(f_2)=\{w_2\} \qquad\mu_1(f_3)=\varnothing\\
\mu_2:\quad&\mu_2(f_1)=\{w_1,w_2\} \qquad\mu_2(f_2)=\{w_3\} \qquad\mu_2(f_3)=\varnothing\\
\mu_3:\quad&\mu_3(f_1)=\varnothing\qquad\mu_3(f_2)=\{w_1\} \qquad\mu_3(f_3)=\{w_2,w_3\}
\end{aligned} μ 1 : μ 2 : μ 3 : μ 1 ( f 1 ) = { w 1 , w 3 } μ 1 ( f 2 ) = { w 2 } μ 1 ( f 3 ) = ∅ μ 2 ( f 1 ) = { w 1 , w 2 } μ 2 ( f 2 ) = { w 3 } μ 2 ( f 3 ) = ∅ μ 3 ( f 1 ) = ∅ μ 3 ( f 2 ) = { w 1 } μ 3 ( f 3 ) = { w 2 , w 3 } Let u ˉ \bar{u} u ˉ be given by u ˉ ( w 1 ) = u ˉ ( w 2 ) = 2 \bar{u}(w_1)=\bar{u}(w_2)=2 u ˉ ( w 1 ) = u ˉ ( w 2 ) = 2 and u ˉ ( w 3 ) = 0 \bar{u}(w_3)=0 u ˉ ( w 3 ) = 0 . For every i ∈ { 1 , 2 , 3 } i\in\{1,2,3\} i ∈ { 1 , 2 , 3 } , define the outcome a i = ( μ i , u ˉ ) a_i=(\mu_i,\bar{u}) a i = ( μ i , u ˉ ) . At each of the outcomes a 1 a_1 a 1 , a 2 a_2 a 2 , and a 3 a_3 a 3 , firms f 1 f_1 f 1 and f 3 f_3 f 3 receive payoff 0, while firm f 2 f_2 f 2 receives payoff 1. Moreover, workers w 1 w_1 w 1 and w 2 w_2 w 2 receive payoff 2, while worker w 3 w_3 w 3 receives payoff 0. Now define the set of outcomes
U = { ( μ 1 , u ) ∈ I μ 1 : u ( w 3 ) > 0 , u ( w 1 ) + u ( w 3 ) < 2 , u ( w 2 ) < 2 } . \mathcal{U}=\{(\mu_1,u)\in\mathcal{I}_{\mu_1}:u(w_3)>0,\ u(w_1)+u(w_3)<2,\ u(w_2)<2\}. U = {( μ 1 , u ) ∈ I μ 1 : u ( w 3 ) > 0 , u ( w 1 ) + u ( w 3 ) < 2 , u ( w 2 ) < 2 } . Let V = U ∪ { a 1 , a 2 , a 3 } \mathcal{V}=\mathcal{U}\cup\{a_1,a_2,a_3\} V = U ∪ { a 1 , a 2 , a 3 } . By construction, V ⊆ I \mathcal{V}\subseteq\mathcal{I} V ⊆ I . We show that V \mathcal{V} V is a vNM stable set.
Internal stability: By Observation 1, no two outcomes in U ∪ { a 1 } \mathcal{U} \cup\{a_1\} U ∪ { a 1 } can dominate one another. Moreover, the payoff of each worker and firm is the same at a 1 a_1 a 1 , a 2 a_2 a 2 and a 3 a_3 a 3 . Hence, none of these outcomes dominates another. It remains to compare outcomes in U \mathcal{U} U with a 2 a_2 a 2 and a 3 a_3 a 3 . Consider any ( μ 1 , u ) ∈ U (\mu_1,u) \in\mathcal{U} ( μ 1 , u ) ∈ U , and let u ( w 1 ) = x u(w_1)=x u ( w 1 ) = x , u ( w 2 ) = y u(w_2)=y u ( w 2 ) = y , and u ( w 3 ) = z u(w_3)=z u ( w 3 ) = z . By the definition of U \mathcal{U} U , z > 0 z>0 z > 0 , x + z < 2 x+z<2 x + z < 2 , and y < 2 y<2 y < 2 . Hence, the payoffs of firms f 1 f_1 f 1 , f 2 f_2 f 2 and f 3 f_3 f 3 at ( μ 1 , u ) (\mu_1,u) ( μ 1 , u ) are 2 − x − z > 0 2-x-z>0 2 − x − z > 0 , 3 − y > 1 3-y>1 3 − y > 1 and 0 0 0 , respectively.
Since a 1 a_1 a 1 , a 2 a_2 a 2 , and a 3 a_3 a 3 give the firms and workers the same payoff, if ( μ 1 , u ) (\mu_1,u) ( μ 1 , u ) dominates either a 2 a_2 a 2 or a 3 a_3 a 3 , it would also dominate a 1 a_1 a 1 . This contradicts Observation 1. Hence, ( μ 1 , u ) ↛ a 2 (\mu_1,u) \not\to a_2 ( μ 1 , u ) → a 2 and ( μ 1 , u ) ↛ a 3 (\mu_1,u) \not\to a_3 ( μ 1 , u ) → a 3 .
At a 2 a_2 a 2 and a 3 a_3 a 3 , firm f 1 f_1 f 1 receives payoff 0, so neither outcome can dominate ( μ 1 , u ) (\mu_1,u) ( μ 1 , u ) through f 1 f_1 f 1 . At a 3 a_3 a 3 , firm f 2 f_2 f 2 receives payoff 1, whereas its payoff at ( μ 1 , u ) (\mu_1,u) ( μ 1 , u ) is strictly greater than 1. Hence, a 3 a_3 a 3 cannot dominate ( μ 1 , u ) (\mu_1,u) ( μ 1 , u ) through f 2 f_2 f 2 . At a 2 a_2 a 2 , firm f 2 f_2 f 2 is matched to w 3 w_3 w 3 , but w 3 w_3 w 3 receives payoff 0 at a 2 a_2 a 2 and z > 0 z>0 z > 0 at ( μ 1 , u ) (\mu_1,u) ( μ 1 , u ) . Thus, a 2 a_2 a 2 cannot dominate ( μ 1 , u ) (\mu_1,u) ( μ 1 , u ) through f 2 f_2 f 2 . At a 2 a_2 a 2 and ( μ 1 , u ) (\mu_1,u) ( μ 1 , u ) , f 3 f_3 f 3 is unmatched and receives payoff 0 at both outcomes, so there is no strict improvement. At a 3 a_3 a 3 , f 3 f_3 f 3 is matched to { w 2 , w 3 } \{w_2,w_3\} { w 2 , w 3 } , but w 3 w_3 w 3 receives 0 at a 3 a_3 a 3 and z > 0 z>0 z > 0 at ( μ 1 , u ) (\mu_1,u) ( μ 1 , u ) . Hence, a 2 ↛ ( μ 1 , u ) a_2 \not\to(\mu_1,u) a 2 → ( μ 1 , u ) and a 3 ↛ ( μ 1 , u ) a_3 \not\to(\mu_1,u) a 3 → ( μ 1 , u ) . Thus, no two outcomes in V \mathcal{V} V dominate one another, and V \mathcal{V} V satisfies internal stability.
External stability: Consider any ( μ , u ) ∈ I ∖ V (\mu,u) \in\mathcal{I} \setminus\mathcal{V} ( μ , u ) ∈ I ∖ V . Since ( μ , u ) (\mu,u) ( μ , u ) is individually rational, f 2 f_2 f 2 can only be matched to ∅ \varnothing ∅ , { w 1 } \{w_1\} { w 1 } , { w 2 } \{w_2\} { w 2 } , or { w 3 } \{w_3\} { w 3 } . We consider these four cases.
Case 1: μ ( f 2 ) = ∅ \mu(f_2)=\varnothing μ ( f 2 ) = ∅ .
In this case the payoff of f 2 f_2 f 2 is zero. If u ( w 2 ) ≤ 2 u(w_2)\leq2 u ( w 2 ) ≤ 2 , then a 1 → f 2 ( μ , u ) a_1 \xrightarrow{f_2}(\mu,u) a 1 f 2 ( μ , u ) . If u ( w 2 ) > 2 u(w_2)>2 u ( w 2 ) > 2 , then w 2 w_2 w 2 cannot be unmatched. Moreover, since ( μ , u ) ∈ I (\mu,u)\in\mathcal{I} ( μ , u ) ∈ I and μ ( f 2 ) = ∅ \mu(f_2)=\varnothing μ ( f 2 ) = ∅ , we must have μ ( f 1 ) = { w 1 , w 2 } \mu(f_1)=\{w_1,w_2\} μ ( f 1 ) = { w 1 , w 2 } (μ ( f 3 ) = { w 2 , w 3 } \mu(f_3)=\{w_2,w_3\} μ ( f 3 ) = { w 2 , w 3 } is not possible since V f 3 ( { w 2 , w 3 } ) = 2 < u ( w 2 ) V_{f_3}(\{w_2,w_3\})=2<u(w_2) V f 3 ({ w 2 , w 3 }) = 2 < u ( w 2 ) , which will contradict IR for firm f 3 f_3 f 3 ). Since V f 1 ( { w 1 , w 2 } ) = 4 V_{f_1}(\{w_1,w_2\})=4 V f 1 ({ w 1 , w 2 }) = 4 and u ( w 2 ) > 2 u(w_2)>2 u ( w 2 ) > 2 , it follows that u ( w 1 ) < 2 u(w_1)<2 u ( w 1 ) < 2 . Hence, a 3 → f 2 ( μ , u ) a_3 \xrightarrow{f_2}(\mu,u) a 3 f 2 ( μ , u ) .
Case 2: μ ( f 2 ) = { w 1 } \mu(f_2)=\{w_1\} μ ( f 2 ) = { w 1 } .
Since ( μ , u ) ∈ I (\mu,u)\in\mathcal{I} ( μ , u ) ∈ I , we must have μ ( f 1 ) = ∅ \mu(f_1)=\varnothing μ ( f 1 ) = ∅ and u ( w 2 ) ≤ 2 u(w_2)\leq2 u ( w 2 ) ≤ 2 . If u ( w 1 ) < 2 u(w_1)<2 u ( w 1 ) < 2 , then a 2 → f 1 ( μ , u ) a_2 \xrightarrow{f_1}(\mu,u) a 2 f 1 ( μ , u ) . If u ( w 1 ) > 2 u(w_1)>2 u ( w 1 ) > 2 , then the payoff of f 2 f_2 f 2 is strictly less than 1. Combining this with the fact that u ( w 2 ) ≤ 2 u(w_2)\leq2 u ( w 2 ) ≤ 2 , a 1 → f 2 ( μ , u ) a_1 \xrightarrow{f_2}(\mu,u) a 1 f 2 ( μ , u ) . If u ( w 1 ) = 2 u(w_1)=2 u ( w 1 ) = 2 , the payoff of f 2 f_2 f 2 is 1. Hence, if u ( w 2 ) < 2 u(w_2)<2 u ( w 2 ) < 2 , then a 1 → f 2 ( μ , u ) a_1 \xrightarrow{f_2}(\mu,u) a 1 f 2 ( μ , u ) . However, if u ( w 2 ) = 2 u(w_2)=2 u ( w 2 ) = 2 , by IR of ( μ , u ) (\mu,u) ( μ , u ) , μ ( f 3 ) = { w 2 , w 3 } \mu(f_3)=\{w_2,w_3\} μ ( f 3 ) = { w 2 , w 3 } and u ( w 3 ) = 0 u(w_3)=0 u ( w 3 ) = 0 . But, then ( μ , u ) = a 3 (\mu,u)=a_3 ( μ , u ) = a 3 , contradicting ( μ , u ) ∉ V (\mu,u)\notin\mathcal{V} ( μ , u ) ∈ / V .
*Case 3: μ ( f 2 ) = { w 2 } \mu(f_2)=\{w_2\} μ ( f 2 ) = { w 2 } . Since ( μ , u ) ∈ I (\mu,u) \in\mathcal{I} ( μ , u ) ∈ I , in this case either μ ( f 1 ) = ∅ \mu(f_1)=\varnothing μ ( f 1 ) = ∅ or μ ( f 1 ) = { w 1 , w 3 } \mu(f_1)=\{w_1,w_3\} μ ( f 1 ) = { w 1 , w 3 } . Suppose μ ( f 1 ) = ∅ \mu(f_1)=\varnothing μ ( f 1 ) = ∅ . Then, the payoff of f 1 f_1 f 1 is zero. Since w 1 w_1 w 1 cannot be matched to f 3 f_3 f 3 at an IR outcome, w 1 w_1 w 1 is unmatched and hence u ( w 1 ) = 0 u(w_1)=0 u ( w 1 ) = 0 . If u ( w 2 ) < 2 u(w_2)<2 u ( w 2 ) < 2 , then a 2 → f 1 ( μ , u ) a_2 \xrightarrow{f_1}(\mu,u) a 2 f 1 ( μ , u ) . If u ( w 2 ) ≥ 2 u(w_2)\ge2 u ( w 2 ) ≥ 2 , then the payoff of f 2 f_2 f 2 is weakly less than 1. Hence, a 3 → f 2 ( μ , u ) a_3 \xrightarrow{f_2}(\mu,u) a 3 f 2 ( μ , u ) . Now suppose μ ( f 1 ) = { w 1 , w 3 } \mu(f_1)=\{w_1,w_3\} μ ( f 1 ) = { w 1 , w 3 } . By IR of ( μ , u ) (\mu,u) ( μ , u ) , u ( w 1 ) + u ( w 3 ) ≤ 2 u(w_1)+u(w_3)\le2 u ( w 1 ) + u ( w 3 ) ≤ 2 . If u ( w 2 ) > 2 u(w_2)>2 u ( w 2 ) > 2 , then a 3 → f 2 ( μ , u ) a_3 \xrightarrow{f_2}(\mu,u) a 3 f 2 ( μ , u ) . Suppose u ( w 2 ) = 2 u(w_2)=2 u ( w 2 ) = 2 . If u ( w 1 ) < 2 u(w_1)<2 u ( w 1 ) < 2 , then a 3 → f 2 ( μ , u ) a_3 \xrightarrow{f_2}(\mu,u) a 3 f 2 ( μ , u ) . If u ( w 1 ) = 2 u(w_1)=2 u ( w 1 ) = 2 , then IR implies u ( w 3 ) = 0 u(w_3)=0 u ( w 3 ) = 0 , so ( μ , u ) = a 1 (\mu,u)=a_1 ( μ , u ) = a 1 , contradicting ( μ , u ) ∉ V (\mu,u)\notin\mathcal{V} ( μ , u ) ∈ / V . Finally, suppose u ( w 2 ) < 2 u(w_2)<2 u ( w 2 ) < 2 . If u ( w 3 ) = 0 u(w_3)=0 u ( w 3 ) = 0 , then a 3 → f 3 ( μ , u ) a_3 \xrightarrow{f_3}(\mu,u) a 3 f 3 ( μ , u ) . If u ( w 3 ) > 0 u(w_3)>0 u ( w 3 ) > 0 , then, since ( μ , u ) ∉ U (\mu,u)\notin\mathcal{U} ( μ , u ) ∈ / U , we must have u ( w 1 ) + u ( w 3 ) = 2 u(w_1)+u(w_3)=2 u ( w 1 ) + u ( w 3 ) = 2 . Hence, a 2 → f 1 ( μ , u ) a_2 \xrightarrow{f_1}(\mu,u) a 2 f 1 ( μ , u ) .
Case 4: μ ( f 2 ) = { w 3 } \mu(f_2)=\{w_3\} μ ( f 2 ) = { w 3 } .
Since ( μ , u ) ∈ I (\mu,u)\in\mathcal{I} ( μ , u ) ∈ I , in this case μ ( f 3 ) = ∅ \mu(f_3)=\varnothing μ ( f 3 ) = ∅ and either μ ( f 1 ) = ∅ \mu(f_1)=\varnothing μ ( f 1 ) = ∅ or μ ( f 1 ) = { w 1 , w 2 } \mu(f_1)=\{w_1,w_2\} μ ( f 1 ) = { w 1 , w 2 } . Moreover, u ( w 3 ) ≤ 1 u(w_3)\le1 u ( w 3 ) ≤ 1 and hence the payoff of f 2 f_2 f 2 is at most 1. If μ ( f 1 ) = ∅ \mu(f_1)=\varnothing μ ( f 1 ) = ∅ , then a 2 → f 1 ( μ , u ) a_2 \xrightarrow{f_1}(\mu,u) a 2 f 1 ( μ , u ) . Suppose μ ( f 1 ) = { w 1 , w 2 } \mu(f_1)=\{w_1,w_2\} μ ( f 1 ) = { w 1 , w 2 } . Since V f 1 ( { w 1 , w 2 } ) = 4 V_{f_1}(\{w_1,w_2\})=4 V f 1 ({ w 1 , w 2 }) = 4 , IR implies u ( w 1 ) + u ( w 2 ) ≤ 4 u(w_1)+u(w_2)\le4 u ( w 1 ) + u ( w 2 ) ≤ 4 . If u ( w 1 ) < 2 u(w_1)<2 u ( w 1 ) < 2 , then a 3 → f 2 ( μ , u ) a_3 \xrightarrow{f_2}(\mu,u) a 3 f 2 ( μ , u ) and if u ( w 2 ) < 2 u(w_2)<2 u ( w 2 ) < 2 , then a 1 → f 2 ( μ , u ) a_1 \xrightarrow{f_2}(\mu,u) a 1 f 2 ( μ , u ) . The only remaining case is u ( w 1 ) = u ( w 2 ) = 2 u(w_1)=u(w_2)=2 u ( w 1 ) = u ( w 2 ) = 2 . If u ( w 3 ) > 0 u(w_3)>0 u ( w 3 ) > 0 , then a 1 → f 2 ( μ , u ) a_1 \xrightarrow{f_2}(\mu,u) a 1 f 2 ( μ , u ) and a 3 → f 2 ( μ , u ) a_3 \xrightarrow{f_2}(\mu,u) a 3 f 2 ( μ , u ) . If u ( w 3 ) = 0 u(w_3)=0 u ( w 3 ) = 0 , then ( μ , u ) = a 2 (\mu,u)=a_2 ( μ , u ) = a 2 , contradicting ( μ , u ) ∉ V (\mu,u)\notin\mathcal{V} ( μ , u ) ∈ / V .
Thus, every outcome in I ∖ V \mathcal{I}\setminus\mathcal{V} I ∖ V is dominated by an outcome in V \mathcal{V} V . Hence, V \mathcal{V} V satisfies external stability.