betaFeedback

WorksEconomics, Econometrics and Finance

von Neumann-Morgenstern stable sets in job matching problems

Abstract

We show that a von Neumann-Morgenstern (vNM) stable set generically exists in the many-to-one job-matching model. Unlike the core, which can be empty in this model, a vNM stable set exists whenever there is a unique efficient matching: the set of all individually rational (IR) and efficient outcomes form a vNM stable set. If an economy has multiple efficient matchings, a vNM stable set may not exist. If the vNM stable sets are required to be rich in a certain sense, then such a rich vNM stable set exists if and only if the set of efficient matchings is essentially unique, and the set of all efficient and IR outcomes forms the unique rich vNM stable set.

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} rich if for every outcome (with matching, say, μ\mu) in V\mathcal{V}, the firm-optimal IR outcome and the worker-maximal IR outcomes corresponding to μ\mu belong to V\mathcal{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 FF be the set of firms and WW be the set of workers. A matching is a map μ:W→F∪{∅}\mu: W \to F \cup\{\emptyset\}, where μ(w)\mu(w) denotes the firm worker ww is matched to – if μ(w)=∅\mu(w) = \emptyset, then it denotes an unmatched worker. For every f∈Ff \in F, we denote by μ(f):={w:μ(w)=f}\mu(f) := \{w : \mu(w) = f\} the set of workers matched to firm ff in μ\mu.

For every f∈Ff \in F and every S⊂WS \subset W, let Vf(S)V_f(S) denote the surplus generated by matching workers in SS to firm ff. The surplus function VfV_f may be generated from value function vf:2W→R+v_f : 2^W \to\mathbb{R}_+ of the firm (with vf(∅)=0v_f(\emptyset) = 0) and disutility function vw:F∪{∅}→R+v_w : F \cup\{\emptyset\} \to\mathbb{R}_+ of each worker ww:

Vf(S)=vf(S)−∑w∈Svw(f)V_f(S) = v_f(S) - \sum_{w \in S} v_w(f)

where vw(∅)=0v_w(\emptyset) = 0. Combined with salaries, this generates utilities for firms and workers as in Kelso and Crawford [9]. However, the surplus function VfV_f of each firm ff 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), where μ\mu is a matching and u:W→Ru : W \to\mathbb{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), each firm ff receives utility equal to

Vf(μ(f))−∑w∈μ(f)u(w)V_f(\mu(f)) - \sum_{w \in\mu(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 ff and its matched workers μ(f)\mu(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,{Vf}f∈F)\left(F, W, \{V_f\}_{f \in F}\right)

An outcome (μ,u)(\mu, u) is individually rational (IR) if

u(w)≥0∀ w∈Wu(w) \ge0 \qquad\forall\ w \in W
Vf(μ(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,

with the first inequality an equality whenever μ(w)=∅\mu(w)=\varnothing. The two constraints correspond to IR of workers and firms respectively. Let I\mathcal{I} be the set of all IR outcomes.

A matching μ⋆\mu^\star is efficient if

μ⋆∈arg⁡max⁡μ∑f∈FVf(μ(f))\mu^\star\in\arg\max_{\mu}\sum_{f\in F}V_f(\mu(f))

Clearly, in an efficient matching Vf(μ⋆(f))≥0V_f(\mu^\star(f))\ge0 for all firms f∈Ff\in F. An outcome (μ,u)(\mu,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∈Ff\in F and a subset of workers S⊆WS\subseteq W block an outcome (μ,u)(\mu,u) if there exists a utility vector u^:S→R+\hat{u}:S\to\mathbb{R}_{+} such that

u^(w)≥u(w)∀w∈S\hat{u}(w)\ge u(w)\qquad\forall w\in S
Vf(S)−∑w∈Su^(w)≥Vf(μ(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)

with at least one inequality strict. In other words, firm ff and workers in SS can be better off sharing the surplus Vf(S)V_f(S) using u^\hat{u} than the current outcome (μ,u)(\mu,u). An outcome (μ,u)∈I(\mu,u)\in\mathcal{I} is stable if it is not blocked by any (f,S)(f,S) pair where f∈Ff\in F and S⊆WS\subseteq 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} is used to define vNM stability.

Definition 1. An outcome (μ,u)∈I(\mu,u) \in\mathcal{I} is dominated by an outcome (μ′,u′)∈I(\mu',u') \in\mathcal{I}, written as (μ′,u′)→(μ,u)(\mu',u') \to(\mu,u), if there exists a firm ff such that

u′(w)≥u(w)∀w∈μ′(f)u'(w) \ge u(w) \qquad\forall w \in\mu'(f)
Vf(μ′(f))−∑w∈μ′(f)u′(w)≥Vf(μ(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)

with one inequality strict. We denote this as (μ′,u′)→f(μ,u)(\mu',u') \xrightarrow{f} (\mu,u).

Hence, (μ′,u′)→(μ,u)(\mu',u') \to(\mu,u) requires that some firm ff and workers μ′(f)\mu'(f), who are matched to ff in μ′\mu', block (μ,u)(\mu,u) (using 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}. If two outcomes (μ,u)(\mu,u) and (μ′,u′)(\mu',u') are not comparable under →\to, we write (μ,u)↔(μ′,u′)(\mu,u) \leftrightarrow( \mu',u').

For every matching μ\mu, let Iμ\mathcal{I}_{\mu} denote the set of all IR outcomes associated with μ\mu:

Iμ:={(μ,u):(μ,u)∈I}\mathcal{I}_{\mu}:=\{(\mu,u):(\mu,u)\in\mathcal{I}\}

Since surplus function VfV_f of each firm ff need not be non-negative, Iμ\mathcal{I}_{\mu} 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). Hence, Iμ=∅\mathcal{I}_{\mu}=\varnothing. 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, Vf(μ∗(f))≥0V_f(\mu^{*}(f)) \ge0 for all ff and hence, the zero payoff vector 0\mathbf{0} (uw=0u_w=0 for all ww) generates the IR outcome (μ∗,0)(\mu^{*},\mathbf{0}). Hence, Iμ∗\mathcal{I}_{\mu^{*}} 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') for all (μ,u),(μ,u′)∈Iμ(\mu,u),(\mu,u') \in\mathcal{I}_{\mu}.

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} is a vNM stable set if

  • no outcome in V\mathcal{V} is dominated by another outcome in V\mathcal{V}: for every (μ,u),(μ′,u′)∈V(\mu,u),(\mu',u') \in\mathcal{V},

    (μ,u)↔(μ′,u′)(\mu,u) \leftrightarrow(\mu',u') (Internal stability)

  • every outcome not in V\mathcal{V} is dominated by some outcome in V\mathcal{V}: for every (μ,u)∈I∖V(\mu,u) \in\mathcal{I} \setminus\mathcal{V}, there exists (μ′,u′)∈V(\mu',u') \in\mathcal{V} such that

    (μ′,u′)→(μ,u)(\mu',u') \to(\mu,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) is a stable outcome, then (μ⋆,u⋆)∈V(\mu^\star,u^\star) \in\mathcal{V} for any vNM stable set V\mathcal{V}.

References

  1. [1]Aumann, R. J. (1985): “What Is Game Theory Trying to Accomplish?” in Frontiers of Economics, ed. by K. J. Arrow and S. Honkapohja, Oxford: Basil Blackwell, 28–76.
  2. [2]Border, K. C. (1991): “Implementation of reduced form auctions: A geometric approach,” Econometrica, 59, 1175–1187.DOI
  3. [3]Che, Y.-K., J. Kim, and K. Mierendorff (2013): “Generalized Reduced-Form Auctions: A Network-Flow Approach,” Econometrica, 81, 2487–2520.
  4. [4]Doğan, B. and L. Ehlers (2026): “Existence of Myopic-Farsighted Stable Sets in Matching Markets,” Econometrica, 94, 811–841.DOI
  5. [5]Ehlers, L. (2007): “Von Neumann–Morgenstern Stable Sets in Matching Problems,” Journal of Economic Theory, 134, 537–547.DOI
  6. [6]Hatfield, J. W., S. D. Kominers, A. Nichifor, M. Ostrovsky, and A. Westkamp (2019): “Full substitutability,” Theoretical Economics, 14, 1535–1590.DOI
  7. [7]Herings, P. J.-J., A. Mauleon, and V. Vannetelbosch (2017): “Stable Sets in Matching Problems with Coalitional Sovereignty and Path Dominance,” Journal of Mathematical Economics, 71, 14–19.
  8. [9]Kelso, A. S. and V. P. Crawford (1982): “Job matching, coalition formation, and gross substitutes,” Econometrica, 1483–1504.
  9. [10]Klaus, B., F. Klijn, and M. Walzl (2011): “Farsighted Stability for Roommate Markets,” Journal of Public Economic Theory, 13, 921–933.
  10. [11]Kojima, F., N. Sun, and N. N. Yu (2020): “Job matching under constraints,” American Economic Review, 110, 2935–2947.DOI
  11. [12]Liu, Q. (2024): “Matching with Incomplete Information,” in Handbook of the Economics of Matching, vol. 1.
  12. [13]Liu, Q., G. J. Mailath, A. Postlewaite, and L. Samuelson (2014): “Stable Matching with Incomplete Information,” Econometrica, 82, 541–587.
  13. [14]MAULEON, A., V. J. VANNETELBOSCH, AND W. VERGOTE (2011): “Von Neumann–Morgenstern Farsightedly Stable Sets in Two-Sided Matching,” Theoretical Economics, 6, 499–521.
  14. [15]NÚÑEZ, M. AND C. RAFELS (2013): “Von Neumann–Morgenstern Solutions in the Assignment Market,” Journal of Economic Theory, 148, 1282–1291.DOI
  15. [16]PETERS, H. (2008): Game theory: A Multi-leveled approach, Springer.
  16. [17]POURPOUNEH, M., R. RAMEZANIAN, A. SEN, AND V. TAORI (2026): “Stable Matching with Payoff Guarantees,” ArXiv preprint.arxiv.org/abs/2608.03230
  17. [18]SHAPLEY, L. AND M. SHUBIK (1971): “Assignment Game I: The Core,” International Journal of Game Theory, 1, 111–130.
  18. [19]SUBIZA, B., J.-M. GIMÉNEZ-GÓMEZ, AND J. E. PERIS (2025): “Cooperative TU-games: Dominance, stable sets, and the core revisited,” Journal of Mathematical Economics, 119, 103137.
  19. [20]VON NEUMANN, J. AND O. MORGENSTERN (1944): Theory of Games and Economic Behavior, Princeton University Press.
  20. [21]WAKO, J. (2010): “A Polynomial-Time Algorithm to Find von Neumann–Morgenstern Stable Matchings in Marriage Games,” Algorithmica, 58, 188–220.DOI

Paper details

vlnc:W_ugs4sj2m
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Economics, Econometrics and Finance

Not recorded for this paper

View statement
Looking for related papers…
Contents