Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time

Abstract

We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. This resolves a long-standing open question posed in [Faigle, Kern, Fekete, Hochstättler, Mathematical Programming, 1998].

This work was done in part while the second author was visiting the Simons Institute for the Theory of Computing. Supported by DIMACS/Simons Collaboration on Bridging Continuous and Discrete Optimization through NSF grant #CCF-1740425.

We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG).

1 Introduction

Imagine a network of players that form partnerships to generate value. For example, maybe a tennis league pairing players to play exhibition matches [3], or people making trades in an exchange network [39]. These are examples of what are called matching games. In a (weighted) matching game, we are given a graph $G=(V,E)$, weights , the player set is the set V of nodes of G, and w(uv) denotes the value earned when u and v collaborate. Each coalition $S\subseteq V$ is assigned a value $\nu (S)$ so that $\nu (S)$ is equal to the value of a maximum weight matching on the induced subgraph G[S]. The special case of matching games where is the all-ones vector, and G is bipartite is called an assignment game and was introduced in a classical paper by Shapley and Shubik [39], and was later generalized to general graphs by Deng, Ibaraki, and Nagamochi [11].

We are interested in what a fair redistribution of the total value $\nu (V)$ to the players in the network looks like. The field of cooperative game theory gives us the language to make this question formal. A vector is called an allocation if $x(V)=\nu (V)$ (where we use x(V) as a short-hand for $\sum _{i \in V}x(i)$ as usual). Given such an allocation, we let $x(S)-\nu (S)$ be the excess of coalition $S \subseteq V$. This quantity can be thought of as a measure of the satisfaction of coalition S. A fair allocation should maximize the bottleneck excess, i.e. maximize the minimum excess, and this can be accomplished by an LP:

Let $\varepsilon ^*$ be the optimum value of (P), and define $P(\varepsilon ^*)$ to be the set of allocations x such that $(x,\varepsilon ^*)$ is feasible for (P). The set $P(\varepsilon ^*)$ is known as the leastcore [33] of the given cooperative game, and the special case when $\varepsilon ^* = 0$, P(0) is the well-known core [21] of $(V,\nu )$. Intuitively, allocations in the core describe payoffs in which no coalition of players could profitably deviate from the grand coalition V.

Why stop at maximizing the bottleneck excess? Consider an allocation which, subject to maximizing the smallest excess, maximizes the second smallest excess, and subject to that maximizes the third smallest excess, and so on. This process of successively optimizing the excess of the worst-off coalitions yields our primary object of interest, the nucleolus. For an allocation , let be the vector obtained by sorting the list of excess values $x(S) - \nu (S)$ for any $\varnothing \ne S \subset V$ in non-decreasing order¹. The nucleolus, denoted $\eta (V,\nu )$ and defined by Schmeidler [38], is the unique allocation that lexicographically maximizes $\theta (x)$:

$$\eta (V,\nu ) := \text {arg lex max}\{ \theta (x): x \in P(\varepsilon ^*)\}.$$

We refer the reader to Appendix B for an example instance of the weighted matching game with its nucleolus. We now have sufficient terminology to state our main result:

Theorem 1

Given a graph $G=(V,E)$ and weights , the nucleolus $\eta (V,\nu )$ of the corresponding weighted matching game can be computed in polynomial time.

Despite its intricate definition the concept of the nucleolus is surprisingly ancient. Its history can be traced back to a discussion on bankruptcy division in the Babylonian Talmud [1]. Modern research interest in the nucleolus stems not only from its geometric beauty [33], or several practical applications (e.g., see [5, 32]), but from the strange way problems of computing the nucleolus fall in the complexity landscape, seeming to straddle the NP vs P boundary.

Beyond being one of the most fundamental problems in combinatorial optimization, starting with the founding work of Kuhn on the Hungarian method for the assignment problem [29], matching problems have historically teetered on the cusp of hardness. For example, prior to Edmonds’ celebrated Blossom Algorithm [12, 13] it was not clear whether Maximum Matching belonged in P. For another example, until Rothvoß’ landmark result [37] it was thought that the matching polytope could potentially have sub-exponential extension complexity. In cooperative game theory, matchings live up to their historical pedigree of representing a challenging problem class. The long standing open problem in this area was whether the nucleolus of a weighted matching game instance can be computed in polynomial time. The concept of the nucleolus has been known since 1969 [38], and the question was posed as an important open problem in multiple papers. In 1998, Faigle, Kern, Fekete, and Hochstättler [15] mention the problem in their work on the nucleon, a multiplicative-error analog to the nucleolus which they show is polynomial time computable. Kern and Paulusma state the question of computing the nucleolus for general matching games as an important open problem in 2003 [26]. In 2008, Deng and Fang [9] conjectured this problem to be NP-hard, and in 2017 Biró, Kern, Paulusma, and Wojuteczky [4] reaffirmed this problem as an interesting open question. Theorem 1 settles the question, providing a polynomial-time algorithm to compute the nucleolus of a general instance of a weighted cooperative matching game.

Prior to our work, the nucleolus was known to be polynomial-time computable only in structured instances of the matching game. Solymosi and Raghavan [40] showed how to compute the nucleolus in an (unweighted) assignment game instance in polynomial time. Kern and Paulusma [26] later provided an efficient algorithm to compute the nucleolus in general unweighted matching game instances. Paulusma [35] extended the work in [26] and gave an efficient algorithm to compute the nucleolus in matching games where edge weights are induced by node potentials. Farczadi [20] finally extended Paulusma’s framework further using the concept of extendible allocations. We note also that it is easy to compute the nucleolus in weighted instances of the matching game with non-empty core. For such instances, the leastcore has a simple compact description that does not include constraints for coalitions of size greater than 2. Thus it is relatively straightforward to adapt the iterative algorithm of Maschler [33] to a polynomial-time algorithm for computing the nucleolus (e.g., see [20, Chapter 2.3] for the details, Sect. 1.2 for an overview).

In a manner analogous to how we have defined matching games, a wide variety combinatorial optimization games can be defined [11]. In such games, the value of a coalition S of players is succinctly given as the optimal solution to an underlying combinatorial optimization problem. It is natural to conjecture that the complexity of computing the nucleolus in an instance of such a game would fall in lock-step with the complexity of the underlying problem. Surprisingly this is not the case. For instance, computing the nucleolus is known to be NP-hard for network flow games [10], weighted threshold games [14], and spanning tree games [16, 19]. On the other hand, polynomial time algorithms are known for finding the nucleolus of special cases of flow games, certain classes of matching games, fractional matching games, and convex games [2, 6, 10, 17, 20, 22, 23, 26, 30, 34,35,36, 40].

The nucleolus is known to lie in the prekernel [38], a solution concept representing allocations which, speaking intuitively, reflect a balance of power between players. The prekernel of a cooperative game is known to be non-convex and even disconnected in general [28, 41]. Despite this, Faigle, Kern and Kuipers [17] showed how to compute a point in the intersection of prekernel and leastcore in polynomial time under the reasonable assumption that the game has a polynomial time oracle to compute the minimum excess coalition for a given allocation. Later the same authors [18] refine their result to computing a point in the intersection of the core and lexicographic kernel, a set which is also known to contain the nucleolus. Bateni et al. [2] pose as an open question the existence of an efficiently computable, balanced and unique way of sharing profit in a network bargaining setting. The nucleolus is always unique [38], and balanced in the sense of lying in the leastcore intersect prekernel. Theorem 1 therefore resolves the latter open question left in [2].

1.1 Leastcore and Core of Matching Games

It is straightforward to see that (P) can be rewritten equivalently as

where $\mathcal {M}$ is the set of all matchings M on G, and x(M) is a shorthand for x(V(M)).

The separation problem for the linear program $(P_1)$ can be reduced to finding a maximum weight matching in the graph G with edge weights $w(uv)-x(uv)$, $uv\in E$ (where we use x(uv) as a shorthand for $x(u)+x(v)$). Since the maximum weight matching can be found in polynomial time [12], we know that the linear program $(P_1)$ can be solved in polynomial time as well [25].

We use $\varepsilon _1$ to denote the optimal value of $(P_1)$ and $P_1(\varepsilon _1)$ for the set of allocations x such that $(x,\varepsilon _1)$ is feasible for the leastcore linear program $(P_1)$. In general, for a value $\varepsilon$ and a linear program Q on variables in we denote by $Q(\varepsilon )$ the set .

Note that $\varepsilon _1\le 0$. Indeed, $\varepsilon \le 0$ in any feasible solution $(x, \varepsilon )$ to $(P_1)$ as otherwise x(M) would need to exceed w(M) for all matchings M. In particular this would also hold for a maximum weight matching on G, implying that $x(V) > \nu (G)$. If $\varepsilon _1=0$ then the core of the cooperative matching game is non-empty. One can see that $\varepsilon _1=0$ if and only if the value of a maximum weight matching on G with weights w equals the value of a maximum weight fractional matching. This follows since $x\in P_1(\varepsilon _1)$ is a fractional weighted node cover of value $\nu (G)$ when $\varepsilon _1=0$. When $\varepsilon _1<0$, we say that the cooperative matching game has an empty core. The matching game instance given in Appendix B has an empty core.

In this paper, we assume that the cooperative matching game (G, w) has an empty core, as computing the nucleolus is otherwise well-known to be doable in polynomial time [35].

1.2 Maschler’s Scheme

As discussed, our approach to proving Theorem 1 relies on Maschler’s scheme. The scheme requires us to solve a linear number of LPs: $\{(P_j)\}_{j \ge 1}$ that we now define. $(P_1)$ is the leastcore LP that we have already seen in Sect. 1.1. LPs $(P_j)$ for $j \ge 2$ are defined inductively. Crucial in their definition is the notion of fixed coalitions that we introduce first. For a polyhedron we denote by $\mathrm {Fix}(Q)$ the collection of sets $S\subseteq V$ such that x(S) is constant over the polyhedron Q, i.e.

$$ \mathrm {Fix}(Q):= \{ S \subseteq V\,:\quad x(S) = x'(S)\quad \text {for all}\quad x,x'\in Q\}\,. $$

With this we are now ready to state LP $(P_j)$ for $j \ge 2$:

where $\varepsilon _j$ be the optimal value of the linear program $(P_j)$. Let $j^*$ be the minimum number j such that $P_j(\varepsilon _j)$ contains a single point. This point is the nucleolus of the game [8]. It is well-known [33] that $P_{j-1}(\varepsilon _{j-1}) \subset P_{j}(\epsilon _j)$ and $\varepsilon _{j-1} < \varepsilon _j$ for all j. Since the dimension of the polytope describing feasible solutions of $(P_j)$ decreases in every round until the dimension becomes zero, we have $j^*\le |V|$ [33], [35, Pages 20–24].

Therefore, in order to find the nucleolus of the cooperative matching game efficiently it suffices to solve each linear program $(P_j)$, $j=1,\ldots ,j^*$ in polynomial time. We accomplish this by providing polynomial-size formulations for $(P_j)$ for all $j \ge 1$.

In Sect. 2 we introduce the concept of universal matchings which are fundamental to our approach, and give a compact formulation for the first linear program in Maschler’s Scheme, the leastcore. We also present our main technical lemma, Lemma 5, which provides a crucial symmetry condition on the values allocations can take over the vertices of blossoms in the graph decomposition we use to describe the compact formulation. In Sect. 3 we describe the successive linear programs in Maschler’s Scheme and provide a compact formulation for each one in a matching game.

2 Leastcore Formulation

In this section we provide a polynomial-size description of $(P_1)$. It will be useful to define a notation for excess: for any $x \in P_1(\varepsilon _1)$ and $M \in \mathcal {M}$ let .

2.1 Universal Matchings, Universal Allocations

For each $x \in P_1(\varepsilon _1)$ we say that a matching $M\in \mathcal {M}$ is an x-tight matching whenever . We denote by $\mathcal {M}^{x}$ the set of x-tight matchings.

A universal matching $M \in \mathcal {M}$ is a matching which is x-tight for all $x \in P_1(\varepsilon _1)$. We denote the set of universal matchings on G by $\mathcal {M}_{uni}$. A universal allocation $x^* \in P_1(\varepsilon _1)$ is a leastcore point whose $x^*$-tight matchings are precisely the set of universal matchings, i.e. $\mathcal {M}^{x^*}=\mathcal {M}_{uni}$.

Lemma 1

There exists a universal allocation $x^* \in P_1(\varepsilon _1)$.

Proof

Indeed, it is straightforward to show that every $x^*$ in the relative interior (see [42, Lemma 2.9(ii)]) of $P_1(\varepsilon _1)$ is a universal allocation. If the relative interior is empty then $P_1(\varepsilon _1)$ is a singleton, which trivially contains a universal allocation. In the arxiv version [27] we provide a combinatorial proof.    $\blacksquare$

Lemma 2

A universal allocation $x^* \in P_1(\varepsilon _1)$ can be computed in polynomial time.

Proof

A point $x^*$ in the relative interior of $P_1(\varepsilon _1)$ can be found in polynomial time using the ellipsoid method (Theorem 6.5.5 [24], [7]). Since any allocation $x^*$ from the relative interior of $P_1(\varepsilon _1)$ is a universal allocation, this implies the statement of the lemma.    $\blacksquare$

Given a non-universal allocation x and a universal allocation $x^*$, we observe that $\mathcal {M}^{x^*} \subset \mathcal {M}^x$ and so $\theta (x^*)$ is strictly lexicographically greater than $\theta (x)$. Thus the nucleolus is a universal allocation. We emphasize that $\mathcal {M}^{x^*}=\mathcal {M}_{uni}$ is invariant under the (not necessarily unique) choice of universal allocations $x^*$. Henceforth we fix a universal allocation $x^* \in P_1(\varepsilon _1)$.

2.2 Description for Convex Hull of Universal Matchings.

By the definition of universal allocation $x^*$, a matching M is universal if and only if it is $x^*$-tight. Thus, M is a universal matching if and only if its characteristic vector lies in the optimal face of the matching polytope corresponding to (the maximization of) the linear objective function assigning weight to each edge $uv \in E$. Let $\mathcal {O}$ be the set of node sets $S \subseteq V$ such that $|S| \ge 3$, |S| is odd. Edmonds [12] gave a linear description of the matching polytope of G as the set of satisfying:

Thus, a matching $M\in \mathcal {M}$ is universal if and only if it satisfies the constraints

where W is some subset of V, $\mathcal {L}$ is a subset of $\mathcal {O}$, and F is a subset of E. Using an uncrossing argument, as in [31, Pages 141–150], we may assume that the collection of sets $\mathcal {L}$ is a laminar family of node sets; i.e., for any two distinct sets $S,T\in \mathcal {L}$, either $S\cap T =\varnothing$ or $S\subseteq T$ or $T\subseteq S$.

Lemma 3

For every node $v\in V$ there exists $M\in \mathcal {M}_{uni}$ such that v is exposed by M. Hence, $W=\varnothing$.

Proof

Assume for a contradiction that there exists a node $v\in V$ such that $v\in W$.

First, note that there always exists a non-universal matching $M \in \mathcal {M}\setminus \mathcal {M}_{uni}$ since otherwise the empty matching would be universal, and thus

$$\begin{aligned} 0 = x^*(\varnothing ) = w(\varnothing ) + \varepsilon _1, \end{aligned}$$

implying that the core of the given matching game instance is non-empty.

Suppose first that there exists a node $u\in V$ exposed by some matching $M' \in \mathcal {M}_{uni}$ such that $x^*_u>0$. We define

Recall that $\mathcal {M}_{uni}$ is the set of maximum weight matchings on G with respect to the node weights $w(uv)-x^*(uv)$, $uv\in E$, i.e. $\mathcal {M}_{uni}$ is the set of $x^*$-tight matchings. Moreover, recall that for $M\in \mathcal {M}_{uni}$. Thus, we have $\delta _0>0$.

We define $\delta :=\min \{\delta _0, x^*_u\}>0$ and a new allocation $x'$ as follows:

$$ x'_r := {\left\{ \begin{array}{ll} x^*_r + \delta , &{}\text {if }r=v \\ x^*_r - \delta , &{}\text {if }r=u \\ x^*_r, &{}\text {otherwise}. \end{array}\right. }$$

Since all universal matchings contain v, the excess with respect to $x'$ of any universal matching is no smaller than their excess with respect to $x^*$. Therefore, by our choice of $\delta$, $(x',\epsilon _1)$ is a feasible, and hence optimal, solution for $(P_1)$. But $M'$ is not $x'$-tight, since $M'$ covers v and exposes u. This contradicts that $M'$ is a universal matching.

Now consider the other case: for all $u\in V$ if u is exposed by a universal matching then $x^*_u=0$. Then, for every universal matching $M\in \mathcal {M}_{uni}$ we have

Since $\nu (G)$ is the maximum weight of a matching on G with respect to the weights w, we get that $\varepsilon _1\ge 0$. Thus $x^*$ is in the core, contradicting our assumption that the core is empty.    $\blacksquare$

2.3 Description of Leastcore

We denote inclusion-wise maximal sets in the family $\mathcal {L}$ as $S_1^*,S_2^*,\ldots , S_k^*.$ We define the edge set $E^+$ to be the set of edges in G such that at most one of its nodes is in $S_i^*$ for every $i\in [k] :=\{1, \dots , k\}$, i.e.

$$ E^+:=E\setminus \big (\bigcup _{i=1}^{k} E(S_i^*)\big ). $$

Lemma 4

For every choice of $v_i \in S_i^*$, $i \in [k]$, there exists a universal matching $M \in \mathcal {M}_{uni}$ such that the node set covered by M is as follows

$$\bigcup _{i=1}^k S_i^* \backslash \{v_i\}\,.$$

Proof

By Lemma 3, we know that for every $i \in [k]$ there exists a universal matching $M_{v_i}\in \mathcal {M}_{uni}$ such that $v_i$ is exposed by $M_{v_i}$. Now, for every $i \in [k]$, let us define

$$ M_i:=E(S_i^*)\cap M_{v_i}. $$

Since $M_i$ satisfies all laminar family constraints in $\mathcal {L}$ for subsets of $S_i^*$ we have that

$$ \bigcup _{i=1}^k M_i $$

is a matching satisfying all the constraints (1), and hence is a universal matching covering the desired nodes.    $\blacksquare$

For each $i \in [k]$ fix a unique representative node $v_i^* \in S_i^*$. By Lemma 4, there exists a universal matching $M^*$ covering precisely $\bigcup _{i \in [k]}S_i^*\backslash \{v_i^*\}$. For any $x \in P_1(\varepsilon _1)$ and $S\subseteq V$ we use to denote

For single nodes we use the shorthand . We now prove the following crucial structure result on allocations in the leastcore.

Lemma 5

For every leastcore allocation x, i.e. for every $x\in P_1(\varepsilon _1)$, we have that

• (i) for all $i \in [k]$, for all

• (ii) for all

Proof

Consider $u\in S^*_i$, and note that we may use Lemma 4 to choose a universal matching $M_u$ covering precisely

$$S_i^*\backslash \{u\} \cup \bigcup _{j \ne i} S_j^*\backslash \{v_j^*\}.$$

Hence we have $V(M_u) \cup \{u\} = V(M^*) \cup \{v_i^*\}$, and since $M^*$ and $M_u$ are universal, $x(M^*) = x^*(M^*)$ and $x(M_u) = x^*(M_u)$. Using these observations we see that

showing (i).

Now we prove (ii). Consider $e\in E^+$ where $e=\{u,v\}$. Since $e \not \in E(S_i^*)$ for all $i \in [k]$, we can choose a universal matching M exposing u and v by Lemma 4. Thus $M\cup \{e\}$ is also a matching. Notice M is x-tight, and so we have

as desired.    $\blacksquare$

Lemma 6

Let $x \in P_1(\varepsilon _1)$ and let $M \in \mathcal {M}$ be a matching such that $M \subseteq \bigcup _{i\in [k]}E(S_i^*)$. Then there exists $M' \subseteq M^*$ such that and for all $i \in [k]$, $|M' \cap E(S_i^*)| = |M\cap E(S_i^*)|$.

Proof

See the arxiv version [27].    $\blacksquare$

Recall that $x^*$ is a fixed universal allocation in $P_1(\varepsilon _1)$. Let $E^*\subseteq E$ denote the union of universal matchings, i.e. $E^* = \cup _{M \in \mathcal {M}_{uni}} M$. We now define linear program $(\overline{P}_1)$.

Let $\overline{\varepsilon }_1$ be the optimal value of the linear program $(\overline{P}_1)$. We now show that $\overline{P_1}(\overline{\varepsilon }_1)$ is indeed a compact description of the leastcore $P_1(\varepsilon _1)$.

Theorem 2

We have $\varepsilon _1=\overline{\varepsilon }_1$ and $P_1(\varepsilon _1)=\overline{P}_1(\overline{\varepsilon }_1)$.

Proof

See Appendix A.

3 Computing the Nucleolus

The last section presented a polynomial-size formulation for the leastcore LP $(P_1)$. In this section we complete our polynomial-time implementation of Maschler’s scheme by showing that $(P_j)$ has the following compact reformulation:

where $\overline{\varepsilon }_j$ is the optimal value of the linear program ($\overline{P}_j$).

Theorem 3

For all $j=1,\ldots ,j^*$, we have $\varepsilon _j=\overline{\varepsilon }_j$ and $P_j(\varepsilon _j) = \overline{P}_j(\overline{\varepsilon }_j)$.

Proof

We refer the reading to the arxiv version [27] for the proof.

With Theorem 3 we can replace each linear program $(P_j)$ with $(\overline{P}_j)$ in Maschler’s Scheme. Since the universal allocation $x^*$, the node sets $S^*_i$, $i\in [k]$, the edge set $E^+$, and the edge set $E^*$ can all be computed in polynomial time, we have shown that the nucleolus of any cooperative matching game with empty core can be computed in polynomial time. Therefore we have shown Theorem 1.

Open Questions. Matching Games generalize naturally to b-matching games, where instead the underlying optimization problem is to find an edge subset M with $|M\cap \delta (v)| \le b_v$ for each node v. Biro, Kern, Paulusma, and Wojuteczky [4] showed that the core-separation problem when $b_v > 2$ for some vertex v, is coNP-Hard. Despite this, the complexity of computing the nucleolus of these games is open.

Our algorithm relies heavily on the ellipsoid method. When the core is non-empty, there is a combinatorial algorithm for finding the nucleolus [3]. It would be interesting to develop a combinatorial algorithm for nucleolus computation of matching games in general.

Appendices

Appendix

A Proof of Theorem 2

Proof

First, we show that $P_1(\varepsilon _1)\subseteq \overline{P}_1(\varepsilon _1)$. Consider $x\in P_1(\varepsilon _1)$. By Lemma 5(i) we have

Lemma 5(ii) shows that for all $e\in E^+$, and holds by the universality of $M^*$. It remains to show that

Suppose for contradiction there exists $e \in E^*$ such that . By the definition of $E^*$, there exists a universal matching $M'$ containing e. Since $M'$ is universal, . But by our choice of e,

contradicting that x is in $P_1(\varepsilon _1)$. Thus we showed that $(x,\varepsilon _1)$ is feasible for ($\overline{P}_1$), i.e. we showed that $P_1(\varepsilon _1)\subseteq \overline{P}_1(\varepsilon _1)$.

To complete the proof we show that $\overline{P}_1(\overline{\varepsilon }_1)\subseteq P_1(\overline{\varepsilon }_1)$. Let x be an allocation in $\overline{P}_1(\overline{\varepsilon }_1)$. Due to the description of the linear program ($P_1$), it is enough to show that for every matching $M\in \mathcal {M}$ we have

Since it suffices to consider only the matchings M, which are unions of matchings on the graphs $G[S_i^*]$, $i \in [k]$. Let $t_i:=|M\cap E(S_i^*)|$. By Lemma 6 applied to $x^*$ there exists $M' \subseteq M^*$ such that and $|M'\cap E(S_i^*)|=t_i$, for all $i\in [k]$. Then due to constraints (2) in ($\overline{P}_1$) we have

where the last inequality follows since $M' \subseteq M^*$ and for all $e \in E^*$.

Thus, we showed that $P_1(\varepsilon _1)\subseteq \overline{P}_1(\varepsilon _1)$ and $\overline{P}_1(\overline{\varepsilon }_1)\subseteq P_1(\overline{\varepsilon }_1)$. Recall, that $\varepsilon _1$ and $\overline{\varepsilon }_1$ are the optimal values of the linear programs ($P_1$) and ($\overline{P}_1$) respectively. Thus, we have $\varepsilon _1=\overline{\varepsilon }_1$ and $P_1(\varepsilon _1)=\overline{P}_1(\overline{\varepsilon }_1)$.    $\blacksquare$

B Example of a Matching Game With Empty Core

Consider the example in Fig. 1. This graph $G=(V,E)$ is a 5-cycle with two adjacent edges 15 and 12 of weight 2, and the remaining three edges of weight 1. Since the maximum weight matching value is $\nu (G) = 3$, but the maximum weight fractional matching value is $\frac{7}{2}$, the core of this game is empty. The allocation $x^*$ defined by $x^*(1) = \frac{7}{5}$ and $x^*(2) = x^*(3) = x^*(4) = x^*(5) = \frac{2}{5}$ lies in the leastcore. Each edge has the same excess, $-\frac{1}{5}$, and any coalition of four vertices yields a minimum excess coalition with excess $-\frac{2}{5}$. Hence the leastcore value of this game is $\varepsilon _1=-\frac{2}{5}$.

In fact, we can see that $x^*$ is the nucleolus of this game. To certify this we can use the result of Schmeidler [38] that the nucleolus lies in the intersection of the leastcore and the prekernel. For this example, the prekernel condition that for all $i\ne j \in V$,

$$\begin{aligned} \max \{ x(S\cup \{i\}) -\nu (S\cup \{i\}) : S\subseteq V\backslash \{j\}\} \\ = \max \{ x(S\cup \{j\}) -\nu (S\cup \{j\}):S\subseteq V\backslash \{i\}\} \end{aligned}$$

reduces to the condition that the excess values of non-adjacent edges are equal. Since G is an odd cycle, this implies that all edges has equal excess, i.e.

Combining the four equations above with the leastcore condition that $x(V) = \nu (G)$ we obtain a system of equations with the unique solution $x^*$. Hence the intersection of the leastcore and prekernel is precisely $\{x^*\}$, and so by Schmeidler, $x^*$ is the nucleolus.

Fig. 1.

Matching game with empty core