LP-duality theory has played a central role in the study of the core, right from its early days to the present time. The 1971 paper of Shapley and Shubik, which gave a characterization of the core of the assignment game, has been a paradigm-setting work in this regard. However, despite extensive follow-up work, basic gaps still remain. We address these gaps using the following building blocks from LP-duality theory:

* Total unimodularity (TUM).

* Complementary slackness conditions and strict complementarity.

TUM plays a vital role in the Shapley-Shubik theorem. We define several generalizations of the assignment game whose LP-formulations admit TUM; using the latter, we characterize their cores. The Hoffman-Kruskal game is the most general of these. Its applications include matching students to schools and medical residents to hospitals, and its core imputations provide a way of enforcing constraints arising naturally in these applications: encouraging diversity and discouraging over-representation.

Complementarity enables us to prove new properties of core imputations of the assignment game and its generalizations.

§ INTRODUCTION

The core is a quintessential solution concept, for profit sharing, in cooperative game theory. It contains all possible ways of distributing the total profit of a game among individual agents in such a way that the grand coalition remains intact, i.e., a sub-coalition will not be able to generate more profits by itself and therefore has no incentive to secede from the grand coalition.

LP-duality theory has played a central role in the study of the core, right from the early works of Bondareva [3] and Shapley [27], see Section <ref>, to the present time. The classic paper of Shapley and Shubik [28] gave a complete characterization of core imputations of the assignment game, namely they are  optimal solutions to the dual of the LP-relaxation of the maximum weight matching problem in the underlying graph. At the heart of their proof lies the fact that the polytope defined by the constraints of this LP is integral, i.e., its vertices have integral coordinates, see Definition <ref>. This raises the following question:

What is the root cause of integrality of the polytope defined by the linear system of an LP?

For the assignment game, the root cause is total unimodularity (TUM), see Definition <ref>.

Shapley-Shubik was a paradigm-setting work. Over the years, in its vein, many researchers explored aspects of the core using TUM and LP-duality theory, see Section <ref>, e.g., the importance of TUM was also observed by Deng et al. [6]; however, they exploited it only in a limited setting, see Section <ref> for details. Indeed, despite the extensive nature of this follow-up work, basic gaps still remain. The purpose of this paper, and its sequel [31], is to use the following three building blocks from LP-duality theory to address these gaps:

* Total unimodularity (TUM).

* Complementary slackness conditions and strict complementarity.

* Total dual integrality (TDI); this is explored in [31], which extends the scope of the notion of core beyond profit — equivalently cost or utility — sharing.

These building blocks have much to do with the theory of efficient[By “efficient” we mean polynomial time computable.] algorithms. That connection is not accidental; in fact, it is very deliberate, since in this paper, we are seeking insights into the core that are supported by efficient algorithms. Section <ref> clarifies this point by drawing a contrast between Bondareva-Shapley and Shapley-Shubik.

Our first task in this paper is to exploit total unimodularity in depth, thereby characterizing the cores of several natural matching-based games.
What happens when the constraint matrix is not totally unimodular? It turns out that the polytope defined by the linear system of the LP may still be integral — the more general condition that ascertains this fact is total dual integrality of the linear system. Exploring TDI is listed as the third task  above and is done in [31].

We start by studying a generalization of the assignment game to the $b$-matching game, in which an integral function $b$ specifies a bound on the number of matched edges that can be incident on a vertex. We consider two cases: $b$ is a constant function and $b$ is arbitrary. We also define two types of characterizations of the core: complete and partial, see Definition <ref>; in the former (latter), optimal dual solutions completely (partially) capture core imputations. We prove that the cores of the two cases of the $b$-matching game exhibit these two characterizations, respectively. For the latter game, this leads to the tantalizing question of understanding the origins of core imputations that do not correspond to optimal dual solutions.

We next consider a very general LP-formulation, due to Hoffman and Kruskal [14], given in Theorem <ref>, in which the constraint matrix is totally unimodular and the underlying polytope has integral vertices. We define a natural game, the Hoffman-Kruskal game, which is the most general matching-based game we study; it generalizes the assignment and $b$-matching games, see Section <ref> for applications of this game. We show that optimal dual solutions of this game partially characterize core imputations. We next ask if there are sub-cases of this game, besides the uniform bipartite $b$-matching game, for which optimal dual solutions completely capture core imputations. We provide a negative answer to this question.

Shapley and Shubik [28] had also obtained other insights into the core of the assignment game. Since the core of this game consists of all optimal dual solutions, it is a convex polytope, and they asked the question: What does this polytope “look like?” They proved that if it contains two or more imputations, then it contains two “antipodal” ones which are maximally far apart in the core, see Theorem <ref>. These two imputations maximally favor one side and disfavor the other side of the bipartition[Much like the top and bottom elements in a lattice of stable matchings.].

Continuing is this vein, we seek further insights into the core of the assignment game; this leads to our second task, of exploring complementarity. The following broad observation indicates why complementarity needs to play an important role: The worth of the assignment game is given by an optimal solution to the primal LP and its core imputations are given by optimal solutions to the dual LP. The fundamental fact connecting these two solutions is complementary slackness conditions. Yet, despite the passage of half a century since  [28], the implications of this fact were not explored. Complementarity helps answer these three basic questions:

* Do core imputations spread the profit more-or-less evenly or do they restrict profit to certain well-chosen agents? If the latter, what characterizes these “chosen” agents?

* An edge $(i, j)$ in the underlying graph is called a team. By definition, under any core imputation, the sum of profits of $i$ and $j$ is at least the weight of this edge. For which teams is the sum strictly larger than the weight of the edge?

* How do core imputations behave in the presence of degeneracy?

Our answer to the first question is that the core rewards only essential agents, namely those who are matched by every maximum weight matching, see Theorem <ref>. Our answer to the second question is quite counter-intuitive: we show that a team $(i, j)$ gets overpaid by some core imputation if and only if it is so incompetent that it doesn't participate in any maximum weight matching! If so, we show that at least one of $i$ and $j$ must be essential. Thus $i$ and $j$ do play well with other players but not with each other. This is the reason the sum of profits of $i$ and $j$ exceeds the weight of edge $(i, j)$.

An assignment game is said to be degenerate if the optimal assignment is not unique. Although Shapley and Shubik had mentioned this phenomenon, they brushed it away, claiming that “in the most common case” the optimal assignment will be unique, and if not, their suggestion was to perturb the edge weights to make the optimal assignment unique. However, this is far from satisfactory, since perturbing the weights destroys crucial information contained in the original instance and the outcome becomes a function of the vagaries of the randomness imposed on the instance. Our answer to the third question is that degeneracy treats teams and agents in totally different ways, see  Section <ref>. Section <ref> discusses past approaches to degeneracy.

Whereas the core of the assignment game is always non-empty, that of the general graph matching game can be empty. Deng et al. [6] showed that the core of this game is non-empty if and only if the weights of maximum weight integral and fractional matchings concur. In this paper, we call such games concurrent games. For concurrent games, optimal dual solutions to Balinski's LP completely characterize core imputations.

Next, we study the three questions, raised above, for concurrent games, Section <ref>.  The answers obtained for the first two questions are weaker than those for the assignment game. The underlying reason is that the characterization of the vertices of the Balinski polytope, Theorem <ref>, for concurrent games, is weaker than the characterization of the vertices of the polytope defined by the assignment game LP, Theorem <ref>; in the former, vertices are half-integral matchings and in the latter, they are integral matchings. The answer to third question is identical to that of the assignment game.

§.§ Applications of Matching Games and the Tennis-Club Analogy

The matching game forms one of the cornerstones of cooperative game theory. The assignment game and its generalizations have numerous applications, e.g., matching students to schools or medical residents to hospitals. In particular, the core imputations of our most general matching-based game, the Hoffman-Kruskal game, provide a way of enforcing constraints arising naturally in these applications: encouraging diversity and discouraging over-representation, see Section <ref>.

The matching game can also be viewed as a matching market in which utilities of the agents are stated in monetary terms and side payments are allowed, i.e., it is a transferable utility (TU) market. For an extensive coverage of these notions, see the book by Moulin [20].

The following setting, taken from [8] and [2], vividly captures the issues underlying profit-sharing in an assignment game (and its generalizations). Suppose a coed tennis club has sets $U$ and $V$ of women and men players, respectively, who can participate in an upcoming mixed doubles tournament. Assume $|U| = m$ and $|V| = n$, where $m, n$ are arbitrary. Let $G = (U, V, E)$ be a bipartite graph whose vertices are the women and men players and an edge $(i, j)$ represents the fact that agents $i \in U$ and $j \in V$ are eligible to participate as a mixed doubles team in the tournament. Let $w$ be an edge-weight function for $G$, where $w_{i j} > 0$ represents the expected earnings if $i$ and $j$ do participate as a team in the tournament. The total worth of the game is the weight of a maximum weight matching in $G$.

Assume that the club picks such a matching for the tournament. The question is how to distribute the total profit among the agents — strong players, weak players and unmatched players — so that no subset of players feel they will be better off seceding and forming their own tennis club. We will use this setting to discuss the issues involved in the questions raised above.

The tennis club analogy extends to generalizations of the assignment game as follows. For the $b$-matching game, let $K$ denote the maximum $b$-value of a vertex. We will assume that the tennis club needs to enter teams into $K$ mixed doubles tournaments. The $b$-value of a player gives an upper bound on the number of tournaments the player can play. As before, the tennis club needs to maximize its total earnings. The Hoffman-Kruskal game generalizes the $b$-matching game in that each team has an upper and lower bound on how many tournaments it can play.

For the general graph matching game, we will assume that the tennis club has players of one gender only and any two players can form a doubles team, thereby allowing the underlying graph to be non-bipartite.

§.§ The Role of Integrality: Bondareva-Shapley vs Shapley-Shubik

The early works of Bondareva [3] and Shapley [27] gave a necessary and sufficient condition for non-emptiness of the core of a game, namely that it be balanced (see Section <ref> for a definition); the proof of this fact is based on Farkas' Lemma from LP-duality theory.

At the outset, the Bondareva-Shapley Theorem had the potential of being extremely useful, since it addresses a key property which one would like to ascertain about a game, namely non-emptiness of its core. Yet, in hindsight, it had no useful algorithmic consequences. The reason is two-fold: first, the LP employed for proving this theorem involves exponentially many variables, one for each subset of players and secondly, this LP is not built around any combinatorial structure[In contrast, Edmonds' linear programming relaxation for non-bipartite matching, which also has exponentially many variables, one for each odd subset of vertices, is amenable to an efficient solution [12]. We believe the reason is the underlying combinatorial structure of matching.].

Shapley and Shubik [28] introduced the “right” way of exploiting the power of LP-duality theory for characterizing core imputations. Perhaps their key ingenuity lay in choosing a game that not only had wide applicability and efficient solvability, but was also amenable to such an analysis. We discus the last point below; efficient solvability follows from the fact that the primal and dual LPs of the assignment game are small, i.e., they have polynomially many variables and constraints.

An optimal solution to the LP-relaxation of the maximum weight matching problem is not “obliged” to be an integral matching in the underlying graph – in general it will be a fractional matching. However, fractionally matching agents is not meaningful for the purpose of the assignment game. The saving grace is a property of the assignment game, namely that its LP-relaxation always has an integral optimal solution. A close examination of the Shapley-Shubik theorem reveals that their proof hinges precisely on this fact. In turn, the reason for this fact is that the polytope defined by the constraints of the primal LP has integral vertices; in this case, they are matchings in the graph.

Organization of the paper: Section <ref> lists various works which explore the core via LP-duality theory. Section <ref> provides basic definitions related to the core, as well as the setup of the assignment game in order to state in detail the theorems of Shapley and Shubik. In Section <ref> we start with the second task, of viewing core imputations of the assignment game via the lens of complementarity; these results will also help provide insights into the new games studied in this paper. Section <ref> defines and characterizes the core of the $b$-matching game and the uniform $b$-matching game. Section <ref> does the same for their generalization to the Hoffman-Kruskal game. Finally, in Section <ref> we define concurrent games and view their core imputations via the lens of complementarity.

§ RELATED WORKS

We start by giving the result of Deng et al. [6]. Let the set of agents of the game be denoted by $T = \{1, \cdots, n\}$ and let $w \in \R^m_+$ be an $m$-dimensional non-negative real vector specifying the weights of $m$ objects; in the assignment game, the objects are edges of the underlying bipartite graph. Let $A$ be an $n \times m$ matrix with $0/1$ entries whose $i^{th}$ row corresponds to agent $i \in T$. Let $x$ be an $m$-dimensional vector of variables and $\mathbb{1}$ be the $n$-dimensional vector of all 1s. Assume that the worth of the game is given by the objective function value of following integer program.

w ·x

Ax ≤1
x ∈{0, 1}

The worth of a sub-coalition, $T' \subseteq T$ is given by the integer program obtained by replacing $A$ by $A'$ in (<ref>), where $A'$ picks the set of rows corresponding to agents in $T'$. The LP-relaxation of (<ref>) is:

w ·x

Ax ≤1
x ≥0

Deng et al. proved that if LP (<ref>) always has an integral optimal solution, then the set of core imputations of this game is exactly the set of optimal solutions to the dual of LP (<ref>). As is well known, integrality holds if $A$ is totally unimodular, i.e., if every square sub-matrix of $A$ has determinant of 0, $+1$ or $-1$. This fact helps Deng et al.  characterize that the cores of several combinatorial optimization games, including maximum flow in unit capacity networks both directed and undirected, maximum number of edge-disjoint $s$-$t$ paths, maximum number of vertex-disjoint $s$-$t$ paths, maximum number of disjoint arborescences rooted at a vertex $r$, and concurrent games (defined below).

A different kind of game, in which preferences are cardinal, is based on the stable matching problem defined by Gale and Shapley [13]. The only coalitions that matter in this game are ones formed by one agent from each side of the bipartition. A stable matching ensures that no such coalition has the incentive to secede and the set of such matchings constitute the core of this game. Vande Vate [29] and Rothblum [24] gave linear programming formulations for stable matchings; the vertices of their underlying polytopes are integral and are stable matchings. More recently, Kiraly and Pap [16] showed that the linear system of Rothblum is in fact totally dual integral (TDI).

To deal with games having an empty core, e.g., the general graph matching game, the following two notions have been given in the past. The first is that of least core, defined by Mascher et al. [21]. If the core is empty, there will necessarily be sets $S \subseteq V$ such that $v(S) < p(S)$ for any imputation $v$. The least core maximizes the minimum of $v(S) - p(S)$ over all sets $S \subseteq V$, subject to $v(\emptyset) = 0$ and $v(V) = p(V)$. This involves solving an LP with exponentially many constraints, though, if a separation oracle can be implemented in polynomial time, then the ellipsoid algorithm will accomplish this in polynomial time [12]; see below for a resolution for the case of the matching game.

A more well known notion is that of nucleolus which is contained in the least core.  After maximizing the minimum of $v(S) - p(S)$ over all sets $S \subseteq V$, it does the same for all remaining sets and so on. A formal definition is given below.

For an imputation $v: {V} \rightarrow \cR_+$, let $\theta(v)$ be the vector obtained by sorting the $2^{|V|} - 2$ values $v(S) - p(S)$ for each $\emptyset \subset S \subset V$ in non-decreasing order. Then the unique imputation, $v$, that lexicographically maximizes $\theta(v)$ is called the nucleolus and is denoted $\nu(G)$.

In 1998, [9] stated the problem of computing the nucleolus of the matching game in polynomial time. For the unit weight case, this was done by Kern and Paulusma [15], and for arbitrary weights by Konemann et al. [17]. However, their algorithm makes extensive use of the ellipsoid algorithm and is therefore neither efficient nor does it give deep insights into the underlying combinatorial structure. They leave the open problem of finding a combinatorial polynomial time algorithm. We note that the difference $v(S) - p(S)$ appearing in the least core and nucleolus has not been upper-bounded for any standard family of games, including the general graph matching game.

A different notion was recently proposed in [30], namely approximate core, and was used to obtain an imputation in the $2/3$-approximate core for the general graph matching game. This imputation can be computed in polynomial time, again using the power of LP-duality theory. This result was extended to $b$-matching games in general graphs by Xiaoet al. [32].

Granot and Huberman [10, 11] showed that the core of the minimum cost spanning tree game is non-empty and gave an algorithm for finding an imputation in it. Koh and Sanita [18] settle the question of efficiently determining if a spanning tree game is submodular; the core of such games is always non-empty. Nagamochi et al. [23] characterize non-emptyness of core for the minimum base game in a matroid; the minimum spanning tree game is a special case of this game.

Over the years, researchers have approached the phenomenon of degeneracy in the assignment game from directions that are different from ours. Nunez and Rafels [22], studied relationships between degeneracy and the dimension of the core. They defined an agent to be active if her profit is not constant across the various imputations in the core, and non-active otherwise. Clearly, this notion has much to do with the dimension of the core, e.g., it is easy to see that if all agents are non-active, the core must be zero-dimensional. They prove that if all agents are active, then the core is full dimensional if and only if the game is non-degenerate. Furthermore, if there are exactly two optimal matchings, then the core can have any dimension between 1 and $m-1$, where $m$ is the smaller of $|U|$ and $|V|$; clearly, $m$ is an upper bound on the dimension.

In another work, Chambers and Echenique [4] study the following question: Given the entire set of optimal matchings of a game on $m = |U|$, $n = |V|$ agents, is there an $m \times n$ surplus matrix which has this set of optimal matchings. They give necessary and sufficient conditions for the existence of such a matrix.

§ DEFINITIONS AND PRELIMINARY FACTS

A cooperative game consists of a pair $(N, c)$ where $N$ is a set of $n$ agents and $v$ is the characteristic function; $c: 2^N \rightarrow \cR_+$, where for $S \subseteq N, \ c(S)$ is the worth that the sub-coalition $S$ can generate by itself. $N$ is also called the grand coalition.

An imputation
is a function $p: N \rightarrow \cR_+$ that gives a way of dividing the worth of the game, $c(N)$, among the agents. It satisfies $\sum_{i \in N} {p(i)} = c(N)$; $p(i)$ is called the profit of agent $i$.

An imputation $p$ is said to be in the core of the game $(N, c)$ if for any sub-coalition $S \subseteq N$, the total profit allocated to agents in $S$ is at least as large as the worth that they can generate by themselves, i.e., $\sum_{i \in S} {p(i)} \geq c(S)$.

A cooperative game $(N, c)$ is said to be balanced if for every function $\lambda: 2^N - \{\emptyset\} \rightarrow [0, 1]$ such that $\forall i \in N: \ \sum_{S \ni i} {\lambda(S)} = 1$, the following holds: $\sum_{2^N - \{\emptyset\}} {\lambda(S) \cdot c(S)} \leq c(N)$.

(Bondareva-Shapley Theorem [3, 27])
A cooperative game $(N, c)$ has a non-empty core if and only if it is balanced.

We will say that a polytope is integral if its vertices have all integral coordinates.

Let $A$ be an $m \times n$ matrix with entries from the set $\{0, 1, -1\}$.  $A$ is said to be totally unimodular[There is a polynomial time algorithm for checking if a matrix is totally unimodular [26].] (TUM) if every submatrix of $A$ has determinant $0, 1$ or $-1$.

[Hoffman and Kruskal [14]]
Let $A$ be an $n \times m$ with entries from the set $\{0, 1, -1\}$. Then $A$ is totally unimodular matrix if and only if for all integral vectors $a, b \in \ZZ_+^n$ and $c, d \in \ZZ^m$, the polyhedron

\[ x \in \R^m \ \ s.t. \ \ a \leq Ax \leq b, \ \ c \leq x \leq d \]

is integral.

§.§ The Core of the Assignment Game

The assignment game, $G = (U, V, E), \ w: E \rightarrow \cR_+$, has been defined in the Introduction. We start by giving definitions needed to state the Shapley-Shubik Theorem. For convenience, we will modify some of the notation that has been defined above to make it more suitable for the assignment game.

A sub-coalition $(S_u \cup S_v)$ consists of a subset of the players with $S_u \subseteq U$ and $S_v \subseteq V$. The worth of a sub-coalition $(S_u \cup S_v)$ is defined to be the weight of a maximum weight matching in the graph $G$ restricted to vertices in $(S_u \cup S_v)$ and is denoted by $c(S_u \cup S_v)$. The characteristic function of the game is defined to be $c: 2^{U \cup V} \rightarrow \cR_+$.

An imputation	consists of two functions $u: {U} \rightarrow \cR_+$ and $v: {V} \rightarrow \cR_+$ such that $\sum_{i \in U} {u(i)} + \sum_{j \in V} {v(j)} = c(U \cup V)$. Imputation $(u, v)$ is said to be in the core of the assignment game if for any sub-coalition $(S_u \cup S_v)$, the total profit allocated to agents in the sub-coalition is at least as large as the worth that they can generate by themselves, i.e., $\sum_{i \in S_u} {u(i)} +  \sum_{j \in S_v} {v(j)} \geq c(S)$. We next describe the characterization of the core of the assignment game given by Shapley and Shubik [28][Shapley and Shubik had described this game in the context of the housing market and had reduced it to the assignment game; the latter is a simpler setting.]

Linear program (<ref>) gives the LP-relaxation of the problem of finding a maximum weight matching in $G$. In this program, variable $x_{ij}$ indicates the extent to which edge $(i, j)$ is picked in the solution.

∑_(i, j) ∈E  w_ij x_ij

∑_(i, j) ∈E x_ij≤1   ∀i ∈U
∑_(i, j) ∈E x_ij≤1 ∀j ∈V
x_ij≥0∀(i, j) ∈E

Taking $u_i$ and $v_j$ to be the dual variables for the first and second constraints of (<ref>), we obtain the dual LP:

∑_i ∈U  u_i + ∑_j ∈V v_j

u_i + v_j ≥w_ij   ∀(i, j) ∈E
u_i≥0∀i ∈U
v_j≥0∀j ∈V

It is easy to see that the constraint matrix of LP (<ref>) is totally unimodular and this LP is clearly a special case of the general formulation given in Theorem <ref>. The next theorem follows from this fact; for a proof see [19].

The polytope defined by the constraints of LP (<ref>) is integral; its vertices are matchings in the underlying graph.

The proof of the next theorem hinges on the key fact stated in Theorem <ref>.

(Shapley and Shubik [28])
The imputation $(u, v)$ is in the core of the assignment game if and only if it is an optimal solution to the dual LP, (<ref>).

Given a cooperative game, we will say that the dual completely characterizes its core if there is a one-to-one correspondence between core imputations and optimal solutions to the dual. On the other hand, if every optimal solution to the dual corresponds to a core imputation but there are core imputations that do not correspond to optimal solutions to the dual, then we will say that the dual partially characterizes its core.

By Theorem <ref>, the assignment game's dual completely characterizes its core. Clearly, the core is a convex polyhedron. Shapley and Shubik had shed further light on the structure of the core by showing that it has two special imputations which are furtherest apart and so can be thought of as antipodal imputations. In the tennis club setup, one of these imputations maximizes the earnings of women players and minimizes the earnings of men players, and the second does exactly the opposite.

For $i \in U$, let $u_i^h$ and $u_i^l$ denote the highest and lowest profits that $i$ accrues among all imputations in the core. Similarly, for $j \in V$, let $v_j^h$ and $v_j^l$ denote the highest and lowest profits that $j$ accrues in the core. Let $u^h$ and $u^l$ denote the vectors whose components are $u_i^h$ and $u_i^l$, respectively. Similarly, let $v^h$ and $v^l$ denote vectors whose components are $v_j^h$ and $v_j^l$, respectively. The following is a formal statement regarding the extreme imputations.

(Shapley and Shubik [28])

The core of the assignment game has two extreme imputations; they are $(u^h, v^l)$ and $(u^l, v^h)$.

§ COMPLEMENTARITY APPLIED TO THE ASSIGNMENT GAME

In this section, we provide answers to the three questions, for assignment games, which were
raised in the Introduction.

§.§ The first question: Allocations made to agents by core imputations

A generic player in $U \cup V$ will be denoted by $q$. We will say that $q$ is:

* essential if $q$ is matched in every maximum weight matching in $G$.

* viable if there is a maximum weight matching $M$ such that $q$ is matched in $M$ and another, $M'$ such that $q$ is not matched in $M'$.

* subpar if for every maximum weight matching $M$ in $G$, $q$ is not matched in $M$.

Let $y$ be an imputation in the core. We will say that $q$ gets paid in $y$ if $y_q > 0$ and does not get paid otherwise. Furthermore, $q$ is paid sometimes if there is at least one imputation in the core under which $q$ gets paid, and it is never paid if it is not paid under every imputation.

For every player $q \in (U \cup V)$:

\[ q \ \mbox{is paid sometimes}  \ \iff \ q \ \mbox{is essential} \]

The proof follows by applying complementary slackness conditions and strict complementarity to the primal LP (<ref>) and dual LP (<ref>); see [25] for formal statements of these facts. By Theorem <ref>, talking about imputations in the core of the assignment game is equivalent to talking about optimal solutions to the dual LP.

Let $x$ and $y$ be optimal solutions to LP (<ref>) and LP (<ref>), respectively. By the Complementary Slackness Theorem, for each $q \in (U \cup V): \ y_q \cdot (x(\delta(q)) - 1) = 0$.

$(\Rightarrow)$  Suppose $q$ is paid sometimes. Then, there is an optimal solution to the dual LP, say $y$, such that $y_q > 0$. By the Complementary Slackness Theorem, for any optimal solution, $x$, to LP (<ref>), $x(\delta(q)) = 1$, i.e., $q$ is matched in $x$. Varying $x$ over all optimal primal solutions, we get that $q$ is always matched. In particular, $q$ is matched in all optimal assignments, i.e., integral optimal primal solutions, and is therefore essential. This proves the forward direction.

$(\Leftarrow)$ Strict complementarity implies that corresponding to each player $q$, there is a pair of optimal primal and dual solutions, say $x$ and $y$, such that either $y_q = 0$ or $x(\delta(q)) = 1$ but not both. Assume that $q$ is essential, i.e., it is matched in every integral optimal primal solution.

We will use Theorem <ref>, which implies that every fractional optimal primal solution to LP (<ref>) is a convex combination of integral optimal primal solutions. Therefore $q$ is fully matched in every optimal solution, $x$, to LP (<ref>), i.e., $x(\delta(q)) = 1$, so there must be an optimal dual solution $y$ such that $y_q > 0$. Hence $q$ is paid sometimes, proving the reverse direction.

Theorem <ref> is equivalent to the following. For every player $q \in (U \cup V)$:

\[ q \ \mbox{is never paid} \ \iff \ q \ \mbox{is not essential} \]

Thus core imputations pay only essential players and each of them is paid in some core imputation.  Since we have assumed that the weight of each edge is positive, so is the worth of the game, and all of it goes to essential players. Hence we get:

In the assignment game, the set of essential players is non-empty and in every core imputation, the entire worth of the game is distributed among essential players; moreover, each of them is paid in some core imputation.

By Corollary <ref>, core imputations reward only essential players. This raises the following question: Can't a non-essential player, say $q$, team up with another player, say $p$, and secede, by promising $p$ almost all of the resulting profit? The answer is “No”, because the dual (<ref>) has the constraint $y_q + y_p \geq w_{qp}$. Therefore, if $y_q = 0$, $y_p \geq w_{q p}$, i.e., $p$ will not gain by seceding together with $q$.

§.§ The second question: Allocations made to teams by core imputations

By a team we mean an edge in $G$; a generic one will be denoted as $e = (u, v)$. We will say that $e$ is:

* essential if $e$ is matched in every maximum weight matching in $G$.

* viable if there is a maximum weight matching $M$ such that $e \in M$, and another, $M'$ such that $e \notin M'$.

* subpar if for every maximum weight matching $M$ in $G$, $e \notin M$.

Let $y$ be an imputation in the core of the game. We will say that $e$ is fairly paid in $y$ if $y_u + y_v = w_e$ and it is overpaid if $y_u + y_v > w_e$[Observe that by the first constraint of the dual LP (<ref>), these are the only possibilities.]. Finally, we will say that $e$ is always paid fairly if it is fairly paid in every imputation in the core.

For every team $e \in E$:

\[ e \ \mbox{is always paid fairly} \ \iff \ e \ \mbox{is viable or essential} \]

The proof is similar to that of Theorem <ref>. Let $x$ and $y$ be optimal solutions to LP (<ref>) and LP (<ref>), respectively. By the Complementary Slackness Theorem, for each $e = (u, v) \in E: \ \ x_e \cdot (y_u + y_v - w_e) = 0$.

$(\Leftarrow)$ To prove the reverse direction, suppose $e$ is viable or essential. Then there is an optimal solution to the primal, say $x$, under which it is matched. Therefore,  $x_e > 0$. Let $y$ be an arbitrary optimal dual solution. Then, by the Complementary Slackness Theorem, $y_u + y_v = w_e$, i.e., $e$ is fairly paid in $y$. Varying $y$ over all optimal dual solutions, we get that $e$ is always paid fairly.

$(\Rightarrow)$ To prove the forward direction, we will use strict complementarity. It implies that corresponding to each team $e$, there is a pair of optimal primal and dual solutions $x$ and $y$ such that either $x_e = 0$ or $y_u + y_v = w_e$ but not both.

Assume that team $e$ is always fairly paid, i.e., under every optimal dual solution $y$, $y_u + y_v = w_e$. By strict complementarity, there must be an optimal primal solution $x$ for which $x_e > 0$. Theorem <ref> implies that $x$ is a convex combination of optimal assignments. Therefore, there must be an optimal assignment in which $e$ is matched. Therefore $e$ is viable or essential and the forward direction also holds.

Let $e = (u, v)$ be a subpar team. Then at least one of $u$ and $v$ is essential.

In every maximum weight matching, at least one of $u$ and $v$ must be matched, since otherwise $e$ should get matched. By Theorem <ref>, there is a core imputation under which $e$ is overpaid. Therefore, under this imputation, at least one of $u$ and $v$ is paid and by Theorem <ref>, that vertex must be essential.

Negating both sides of the implication proved in Theorem <ref>, we get the following  implication. For every team $e \in E$:

\[ e \ \mbox{is subpar} \ \iff \ e \ \mbox{is sometimes overpaid} \]

Clearly, this statement is equivalent to the statement proved Theorem <ref> and hence contains no new information. However, it provides a new viewpoint. These two equivalent  statements yield the following assertion, which at first sight seems incongruous with what we desire from the notion of the core and the just manner in which it allocates profits:

Whereas viable and essential teams are always paid fairly, subpar teams are sometimes overpaid.

How can the core favor subpar teams over viable and essential teams? An explanation is provided in the Introduction, namely a subpar team $(i, j)$ gets overpaid because $i$ and $j$ create worth by playing in competent teams with other players. Finally, we observe that contrary to Corollary <ref>, which says that the set of essential players is non-empty, it is easy to construct examples in which the set of essential teams may be empty.

By Theorem <ref>, different essential players are paid in different core imputations and by Theorem <ref>, different subpar teams are overpaid in different core imputations. This raises the following question: is there a core imputation that simultaneously satisfies all these conditions? Theorem <ref> gives a positive answer.

For the assignment game, there is a core imputation satisfying:

* a player $q \in U \cup V$ gets paid if and only if $q$ is essential.

* a team $e \in E$ gets overpaid if and only if $e$ is subpar.

By Theorem <ref>, for each essential player $q$, there is a core imputation under which $q$ gets paid and by Theorem <ref>, for each subpar team $e$, there is a core imputation under which $e$ gets overpaid. Consider a convex combination of all these imputations; it must give positive weight to each of these imputations. Clearly, this is a core imputation.

We observe that none of the core imputations pay non-essential players or overpay non-subpar teams. Consequently, the imputation constructed above satisfies the conditions of the theorem.

§.§ The third question: Degeneracy

Next we use Theorems <ref> and <ref> to get insights into degeneracy. Clearly, if an assignment game is non-degenerate, then every team and every player is either always matched or always unmatched in the set of maximum weight matchings in $G$, i.e., there are no viable teams or players. Since viable teams and players arise due to degeneracy, in order to understand the phenomenon of degeneracy, we need to understand how viable teams and players behave with respect to core imputations; this is done in the next corollary.

In the presence of degeneracy, imputations in the core of an assignment game treat:

* viable players in the same way as subpar players, namely they are never paid.

* viable teams in the same way as essential teams, namely they are always fairly paid.

§ THE BIPARTITE $B$-MATCHING GAME

In this section, we will define the bipartite $b$-matching game and its special case when $b$ is the constant function and we will study their core imputations; both versions generalize the assignment game.

§.§ Definitions and Preliminary Facts

As in the assignment game, let $G = (U, V, E), \ w: E \rightarrow \cR_+$ be the underlying bipartite graph and edge-weight function. Let function $b: U \cup V \rightarrow \ZZ_+$ give an upper bound on the number of times a vertex can be matched. An edge can be matched multiple number of times; however, limits imposed by $b$ on vertices will impose limits on edges. Thus edge $(i, j)$ can be matched at most $\min \{b_i, b_j\}$ times. Any choice of edges, with multiplicity, subject to these constraints, is called a $b$-matching.

Under the bipartite $b$-matching game, the worth of a coalition $(S_u \cup S_v)$, with $S_u \subseteq U, S_v \subseteq V$, is the weight of a maximum weight $b$-matching in the graph $G$ restricted to vertices in $(S_u \cup S_v)$ only. We will denote this by $c(S_u \cup S_v)$; the characteristic function of the game is defined to be $c: 2^{U \cup V} \rightarrow \cR_+$. An imputation	consists of two functions $\alpha : {U} \rightarrow \cR_+$ and $\beta : {V} \rightarrow \cR_+$ such that $\sum_{i \in U} {\alpha (i)} + \sum_{j \in V} {\beta (j)} = c(U \cup V)$. Definition <ref>, defining the core, carries over unchanged. The special case of the bipartite $b$-matching game in which $b$ is the constant function is called  the uniform bipartite $b$-matching game; we will denote the constant by $b_c \in \ZZ_+$. As stated in the Introduction, the tennis club analogy applies to these two games as well.

Linear program (<ref>) gives the LP-relaxation of the problem of finding a maximum weight $b$-matching. In this program, variable $x_{ij}$ indicates the extent to which edge $(i, j)$ is picked in the solution; observe that  there is no upper bound on the variables $x_{ij}$ since an edge can be matched any number of times.

∑_(i, j) ∈E  w_ij x_ij

∑_(i, j) ∈E x_ij≤b_i   ∀i ∈U
∑_(i, j) ∈E x_ij≤b_j ∀j ∈V
x_ij≥0∀(i, j) ∈E

Taking $u_i$ and $v_j$ to be the dual variables for the first and second constraints of (<ref>), we obtain the dual LP:

∑_i ∈U  b_i u_i + ∑_j ∈V b_j v_j

u_i + v_j ≥w_ij   ∀(i, j) ∈E
u_i≥0∀i ∈U
v_j≥0∀j ∈V

As in the assignment game, the constraint matrix of LP (<ref>) is  totally unimodular and this LP is a special case of the general formulation given in Theorem <ref>. Consequently, the underlying polyhedron has all integral vertices. Once again, this fact plays a key role in characterizing the core of the (uniform) bipartite $b$-matching game.

§.§ The Core of the Uniform Bipartite $b$-Matching Game

The next theorem is analogous to the Shapley-Shubik Theorem.

For the uniform bipartite $b$-matching game, the dual completely characterizes its core.

The proof hinges on the fact that the polytope defined by the constraints of the primal LP, (<ref>) has integral vertices, i.e., they are $b$-matchings in $G$.

Let $(u, v)$ be an optimal dual solution. By integrality and the LP-duality theorem, the worth of the game,

$$c(U \cup V) = b_c \cdot (\sum_{i \in U} {u_i} + \sum_{j \in V} {v_j}) .$$

Therefore $(\alpha, \beta)$ is an imputation, where $\alpha_i = b_c \cdot u_i$ and $\beta_j = b_c \cdot v_j$.

Consider a sub-coalition $(S_u \cup S_v)$, with $S_u \subseteq U, S_v \subseteq V$. Let $G'$ denote the subgraph of $G$ induced on the vertices $(S_u \cup S_v)$. Once again by integrality and the LP-duality theorem, we get that worth of $(S_u \cup S_v)$ equals the objective function value of  the optimal dual for graph  $G'$. Since the restriction of $(u, v)$ to $G'$ is a feasible dual for $G'$, we get that $b_c \cdot (\sum_{i \in S_u} {u_i} + \sum_{j \in S_v} {v_j}) =  \sum_{i \in S_u} {\alpha_i} + \sum_{j \in S_v} {\beta_j} \geq c(S_u \cup S_v)$, i.e., the core condition is satisfied for sub-coalition $(S_u \cup S_v)$. Therefore $(\alpha, \beta)$ is a core imputation.

Next, let $(\alpha, \beta)$ be a core imputation. By integrality and the LP-duality theorem,

$$ \sum_{i \in U} {\alpha_i} + \sum_{j \in V} {\beta_j} \ = c(U \cup V) .$$

Let $u_i = {1 \over b_c} \alpha_i$ and $v_j = {1 \over b_c} \beta_j$. We will show that $(u, v)$ is an optimal dual solution for $G$, thereby proving the theorem.

Corresponding to any edge $e = (i, j)$, consider the sub-coalition $S = \{ i, j\}$. The worth of this sub-coalition is obtained by picking edge $e$ $b_c$ times, i.e., $c(\{i, j\}) = b_c \cdot w_e$.  Since $(\alpha, \beta)$ be a core imputation, the profit allocated to this sub-coalition is at least its worth, i.e., $\alpha_i + \beta_j \geq b_c \cdot w_e$. Dividing by $b_c$ we get $u_i + v_j \geq w_e$. Therefore $(u, v)$ satisfies the constraint in LP (<ref>) and is hence a dual feasible solution. Since $(\alpha, \beta)$ is a core imputation, $ \sum_{i \in U} {\alpha_i} + \sum_{j \in V} {\beta_j} \ = c(U \cup V) .$ Therefore, by integrality and the LP-duality theorem, the objective function value of this dual equals the  optimal primal. Therefore $(u, v)$ is an optimal dual solution.

Clearly, the proof given above can be used for characterizing the core of the assignment game as well. We note that it is simpler and more modular than the proof given in [28]. Because of its modularity, its ideas apply to other games admitting TUM. We further observe that with a little bit of care, Theorem <ref> could have been derived from Theorem <ref>. However, by doing that we would have lost the opportunity of stating these ideas in a simple setting before applying them to more complex games.

Next, we prove that the core of the uniform bipartite $b$-matching game also has two extreme imputations, as claimed for the assignment game in Theorem <ref>. For $i \in U$, let $\alpha_i^h$ and $\alpha_i^l$ denote the highest and lowest profits that $i$ accrues among all imputations in the core. Similarly, for $j \in V$, let $\beta_j^h$ and $\beta_j^l$ denote the highest and lowest profits that $j$ accrues in the core. Let $\alpha^h$ and $\alpha^l$ denote the vectors whose components are $\alpha_i^h$ and $\alpha_i^l$, respectively. Similarly, let $\beta^h$ and $\beta^l$ denote vectors whose components are $\beta_j^h$ and $\beta_j^l$, respectively.

The core of the uniform bipartite $b$-matching game has two extreme imputations; they are $(\alpha^h, \beta^l)$ and $(\alpha^l, \beta^h)$.

The proof of this theorem follows from Lemma <ref>, whose proof is straightforward and is omitted. Let $(q, r)$ and $(s, t)$ be two imputations in the core of the uniform bipartite $b$-matching game. For each $i \in U$, let

\[ \un{\alpha_i} = \min(q_i, s_i) \ \ \ \  \mbox{and} \ \ \ \  \ov{\alpha_i} = \max (q_i, s_i) .\]

Further, for each $j \in R$, let

\[  \un{\beta_j} = \min (r_j , t_j) \ \ \ \  \mbox{and} \ \ \ \  \ov{\beta_j} = \max (r_j, t_j) .\]

$(\un{\alpha} , \ov{\beta} )$ and $(\ov{\alpha}, \un{\beta} )$ are imputations in the core of the uniform bipartite $b$-matching game.

Finally, we use complementarity to gain further insights into core imputations of the uniform bipartite $b$-matching game.

A generic player in $U \cup V$ will be denoted by $q$. We will say that $q$ is:

* essential if $q$ is matched $b$ times in every maximum weight matching in $G$.

* viable if there is a maximum weight matching $M$ such that $q$ is matched $b$ times in $M$ and another, $M'$ such that $q$ is matched less than $b$ times in $M'$.

* subpar if for every maximum weight matching $M$ in $G$, $q$ is matched than $b$ times in $M$.

Definitions <ref>, <ref> and <ref> carry over verbatim. Under these definitions, it is easy to check that all theorems and corollaries stated in Section <ref> for the assignment game carry over to the uniform bipartite $b$-matching game.

§.§ The Core of the Bipartite $b$-Matching Game

We next study the case that $b$ is an arbitrary function. As stated in Theorem <ref>, for this game the dual partially characterizes its core. Corresponding to each optimal solution $(u, v)$ to the dual LP (<ref>) there exists a core imputation $(\alpha, \beta)$, where the profit allocated to $i \in U$ is $\alpha_i = b_i \cdot u_i$ and that to $j \in V$ is $\beta_j = b_j \cdot v_j$. The proof of this statement is exactly the same as the the analogous statement in Theorem <ref> and is omitted. Example <ref> gives an instance of a bipartite $b$-matching game which has core imputations that do not correspond to any optimal dual solution. Hence we get:

For the bipartite $b$-matching game, the dual partially characterizes its core.

The core of the bipartite $b$-matching game is always non-empty.

The graph for Example <ref>.

For the bipartite $b$-matching game defined by the graph of Figure <ref>, let the $b$ values be $(2, 2, 1)$ for $(u, v_1, v_2)$, and let the edge weights be $1$ and $3$ for $(u, v_1)$ and $(u, v_2)$, respectively.

By matching both edges once each we get that the worth of the game is 4. The unique optimal dual solution is $(1, 0, 2)$ for $(u, v_1, v_2)$. It is easy to see that allocation of profits of $(4, 0, 0)$ for $(u, v_1, v_2)$ is a core imputation. The corresponding dual solution would have been $(2, 0, 0)$; however, it is infeasible. Therefore this core imputation does not correspond to an optimal dual solution.

Let $I$ be an instance of the bipartite $b$-matching game and let $D(I)$ denote the set of its core imputations which are optimal solutions to the dual LP. Since the optimal dual solutions don't capture all core imputations, the characterizations established in Theorems <ref> and <ref> for the assignment game, don't carry over. Instead, let us restrict all definitions about payments given in Section <ref> to core imputations in $D(I)$ only. Thus we will say that $q$ is paid sometimes if there is at least one imputation in $D(I)$ under which $q$ gets paid, and it is never paid if it is not paid under every imputation in $D(I)$. Similarly, we will say that $e$ is always paid fairly if it is fairly paid in every imputation in $D(I)$. It is easy to see that under these new definitions, Theorems <ref> and <ref> do hold for the bipartite $b$-matching game.

§ THE CORE OF THE HOFFMAN-KRUSKAL GAME

In this section, we will define a game that generalizes the $b$-matching game and whose LP-relaxation sacrifices as little generality as possible compared to the LP-formulation given in the theorem of Hoffman and Kruskal, Theorem <ref>. The game we obtain is a natural one; its applications include matching students to schools and medical residents to hospitals. As described below, its dual variables provide a way of enforcing constraints that arise in such applications. The game has an interesting interpretation in the tennis setting as well, as described in Section <ref>.

The Hoffman-Kruskal game is defined as follows. Let $G = (U, V, E), \ w: E \rightarrow \cR_+$ be a bipartite graph and edge-weight function. The set of agents is $U \cup V$ and the set of teams is $E$. Let function $b: U \cup V \rightarrow \ZZ_+$ give an upper bound on the number of times a vertex can be matched. Further, let functions $c: E \rightarrow \ZZ_+$ and $d: E\rightarrow \ZZ_+$ give a lower bound and an upper bound, respectively, on the number of times an edge can be matched. A matching obeying these conditions will be called an HK matching.

Linear program  (<ref>) gives the LP-relaxation of the problem of finding a maximum weight HK matching.

∑_(i, j) ∈E  w_ij x_ij

∑_(i, j) ∈E x_ij≤b_i   ∀i ∈U
∑_(i, j) ∈E x_ij≤b_j   ∀j ∈V
x_ij≥c_ij∀(i, j) ∈E
x_ij≤d_ij∀(i, j) ∈E

Taking $u_i$, $v_j$, $y_{ij}$ and $z_{ij}$  to be the dual variables for the first to the fourth constraints, respectively, of (<ref>), we obtain the dual LP:

∑_i ∈U  b_i u_i + ∑_j ∈V b_j v_j + ∑_(i, j) ∈E  (d_ij z_ij - c_ij y_ij)

u_i + v_j + z_ij - y_ij≥w_ij   ∀(i, j) ∈E
u_i≥0∀i ∈U
v_j≥0∀j ∈V
y_ij,z_ij≥0∀(i, j) ∈E

We next state the manner in which the LP-relaxation for the Hoffman-Kruskal game is less general as compared to  the LP in Theorem <ref>. For this purpose, recall the latter LP:

\[ x \in \R^m \ \ s.t. \ \ a \leq Ax \leq b, \ \ c \leq x \leq d \]

* The constraint matrix has entries from $\{0, 1\}$ rather than $\{0, 1, -1\}$.

* The lower bound on the number of times a vertex can be matched, $a \leq Ax$, has been removed. The reason is the following: if this constraint were added, then the form of the dual LP dictates that agents may receive negative profit. This would violate individual rationality and of course would be a reason for the agent to secede, hence going against the spirit of the core.

* The vectors are constrained to have non-negative integral entries rather than arbitrary integral entries, since constraining an agent to play a negative number of games is meaningless.

The constraints on edges make the Hoffman-Kruskal game considerably more complex than the $b$-matching game; in particular, the dual contains not only vertex-variables, which would help us characterize the core of this game, but also edge-variables. However, this is a double-edged sword in that the latter variables help enforce constraints that arise naturally in applications of this game.

Let us describe two applications among several. The first is matching students to schools. One way to use the Hoffman-Kruskal game in this setting is to let each vertex in $U$ represent a distinct category of students, e.g., minority students, women students with high grades, white male students with average grades etc. For $i \in U$, $b_i$ is the number of students in category $i$. Let vertices in $V$ represent schools, with $b_j$ for $j \in V$ being the number of students which school $j$ can admit. The second application is matching medical residents to hospitals, in which vertices in $U$ represent  categories of residents, divided according to their speciality, and $V$ represents hospitals. The constraints which the Hoffman-Kruskal game can handle are of two types:

* Diversity: These are the lower bound constraints on edges. They can be used for ensuring that a school has a sufficient number of minority or women students, or that a rural hospital has a sufficient number of doctors having a specific speciality.

* Avoiding over-representation: These are the upper bound constraints on edges. They can be used for ensuring that certain classes of students or doctors are not over-representation, so as to obtain a “balanced” allocation.

Let us start by rewriting the constraint corresponding to edge $(i, j)$ in the dual LP (<ref>) as follows:

$$ u_i + v_j \geq w_{ij} + c_{ij} \cdot y_{ij} - d_{ij} \cdot z_{ij} .$$

The worth of edge $(i, j)$ is defined to be $w_{ij}$. We will define the surplus generated, when edge $(i, j)$ is matched, to be the right-hand-side of this inequality. The surplus adjusts the worth of the edge endogenously up or down depending on whether the lower or the upper bound constraint on $(i, j)$, respectively, is binding; if neither is binding the worth and surplus are the same.

Thus, when the lower bound constraint on $(i, j)$ is binding, matching $i$ to $j$ generates more value than is physically possible in order to encourage more matchings of this type. Similarly,  when the upper bound constraint on $(i, j)$ is binding, matching $i$ to $j$ generates less value than is physically possible in order to prevent additional matchings of this type.

As before, the worth of the game is the weight of a maximum weight HK matching in $G$ and is denoted by $W(U \cup V)$. However, the more important quantity is the total surplus, which is defined to be:

$$ \surplus(U \cup V) \ := \ W(U \cup V)  + \sum_{(i, j) \in E}  {(c_{ij} \cdot y_{ij} - d_{ij} \cdot z_{ij})} .$$

For a sub-coalition $(S_u \cup S_v)$, with $S_u \subseteq U, S_v \subseteq V$, let $G(S_u \cup S_v)$ denote the subgraph of $G$ induced on $S_u \cup S_v$ and let $E_S$ denote its edges. The worth of $(S_u \cup S_v)$ is the weight of a maximum weight HK matching in $G(S_u \cup S_v)$ and is denoted by $W(S_u \cup S_v)$. Next consider the dual LP (<ref>) defined for the subgraph  $G(S_u \cup S_v)$ and consider an optimal solution for it. Let $y_{ij}^S$ and $z_{ij}^S$ be the dual variables for the lower and upper bound constraints on edge $(i, j) \in E_S$ in this optimal solution, respectively. Then, the total surplus generated in $G(S_u \cup S_v)$ is defined to be:

$$  \surplus(S_u \cup S_v) \ := \ W(S_u \cup S_v)  + \sum_{(i, j) \in E}  {(c_{ij} \cdot y_{ij}^S - d_{ij} \cdot z_{ij}^S)} .$$

An imputation for the Hoffman-Kruskal game gives a way of dividing the total surplus among agents. Let $\alpha_i$ and $\beta_j$ denote the payments made to agents $i \in U$ and $j \in V$, respectively, under this imputation. Then,

$$  \surplus(U \cup V) \ = \  {\sum_{i \in U}  {\alpha_i} + \sum_{j \in V} {\beta_j}}  . $$

An imputation $(\alpha, \beta)$ is in the core of the Hoffman-Kruskal game if for every sub-coalition $(S_u \cup S_v)$,

$$  \surplus(S_u \cup S_v) \ \leq \  {\sum_{i \in S_u}  {\alpha_i} + \sum_{j \in S_v} {\beta_j}}  , $$

i.e., the total payment to the agents of the sub-coalition is at least as large as the surplus which the sub-coalition can generate.

For the Hoffman-Kruskal game, the dual partially characterizes its core in the following sense:
Let $(u, v, y, z)$ be an optimal solution to the dual LP (<ref>). Obtain $\surplus(U \cup V)$ using the worth of the game and these dual variables. Then $(\alpha, \beta)$, where $\alpha_i = b_i \cdot u_i$ and $\beta_j = b_j \cdot v_j$, is an imputation and is in the core of this game.

The proof again hinges on the fact that the polytope defined by the constraints of the primal LP, (<ref>) has integral vertices, which follows from Theorem <ref>.

Let $(u, v, y, z)$ be an optimal solution to the dual LP (<ref>). By integrality and the LP-duality theorem, the worth of the game,

$$W(U \cup V) = {\sum_{i \in U}  {b_i u_i} + \sum_{j \in V} {b_j v_j} + \sum_{(i, j) \in E}  {(d_{ij} z_{ij} - c_{ij} y_{ij})}} .$$

Using $\alpha_i = b_i \cdot u_i$ and $\beta_j = b_j \cdot v_j$, we get:

$$ \surplus(U \cup V) \ = \ W(U \cup V)  + \sum_{(i, j) \in E}  {(c_{ij} \cdot y_{ij} - d_{ij} \cdot z_{ij})}  \ = \  {\sum_{i \in U}  {\alpha_i} + \sum_{j \in V} {\beta_j}}  , $$

and hence $(\alpha, \beta)$ is an imputation.

Consider a sub-coalition $(S_u \cup S_v)$, with $S_u \subseteq U, S_v \subseteq V$. The restriction of the dual $(u, v, y, z)$ to the vertices and edges of $G(S_u \cup S_v)$ satisfies the constraints of the dual for this graph and is therefore a feasible dual for this subgraph. By integrality and the LP-duality theorem, we get that worth of $(S_u \cup S_v)$, namely $W(S_u \cup S_v)$, equals the objective function value of the optimal dual for this subgraph, and this is upper bounded by any feasible dual for this subgraph. Therefore,

$$ W(S_u \cup S_v) \ \leq \ {\sum_{i \in S_u}  {b_i u_i} + \sum_{j \in S_v} {b_j v_j} + \sum_{(i, j) \in E_S}  {(d_{ij} z_{ij} - c_{ij} y_{ij})}} . $$

$$  \surplus(S_u \cup S_v) \ \leq \  {\sum_{i \in S_u}  {\alpha_i} + \sum_{j \in S_v} {\beta_j}}, $$

thereby proving that $(\alpha, \beta)$ is a core imputation.

The core of the Hoffman-Kruskal game is always non-empty.

By Example <ref>, there are core imputations for the special case of the bipartite $b$-matching game which are not optimal dual solutions. Therefore the same holds for the Hoffman-Kruskal game.

§.§ Is the surplus of the Hoffman-Kruskal game uniquely defined?

In this section, we will answer the question stated in the title. Clearly, the worth of this game is unique. The answer[This non-uniqueness is similar to the non-uniqueness of other solution concepts in economics, e.g., Nash equilibrium and market equilibrium.] turns out to be “No”, as shown in Example <ref>. Therefore, Theorem <ref> holds only if the surplus and the payments to agents come from the same optimal dual solution. In the assignment game, different optimal duals make different allocations of profits to agents; however, the total profit allocated is the same and is the worth of the game. On the other hand, as shown in Example <ref>, the total payments made by different optimal duals can be different under the Hoffman-Kruskal game.

Consider the following instance of the Hoffman-Kruskal game, based on the graph of Figure <ref>. Let the $b$ values of vertices be $(4, 2, 3)$ for $(u, v_1, v_2)$. For edges $(u, v_1)$ and $(u, v_2)$, let their weights be $1$ and $3$, and let their lower and upper bounds be $(1, 2)$ and $(0, 3)$, respectively.

The maximum weight HK matching matches edges $(u, v_1)$ and $(u, v_2)$ 1 and 3 times, respectively, for a primal solution of value 10. Here are two optimal duals of value 10: The first assigns values of $(4, 0, 0)$ to vertices $(u, v_1, v_2)$, 2 for the lower bound for edge $(u, v_1)$ and the rest zero. The second assigns values of $(1, 0, 2)$ to vertices $(u, v_1, v_2)$ and zero to all edge dual variables. The surplus of the game under these two duals is 12 and 10, respectively. The payments to vertices $(u, v_1, v_2)$ under these two duals is $(12, 0, 0)$ and $(4, 0, 6)$, respectively.

§.§ Are there other Games Having Complete Characterizations?

Recall that for the uniform bipartite $b$-matching game, which is a sub-case of the Hoffman-Kruskal game, the optimal dual completely characterizes the core. This leads to the following interesting question:

Are there other sub-cases of the Hoffman-Kruskal game for which the optimal dual completely characterizes the core?

By Example <ref>, if the answer were “yes”, $b$ must be the constant function. Now there are two possibilities: there are edge upper bounds or there are edge lower bounds. To force a “yes” answer, let us pick these bounds to also be the constant function. Hence we are left with examining the following possibilities:

* $b$ is the constant function and edge upper bounds are also constant; there are no edge lower bounds.

* $b$ is the constant function and edge lower bounds are also constant; there are no edge upper bounds.

Examples <ref> and <ref> give instances showing that for both these games, the optimal dual only partially characterizes the core.

Let the graph of Figure <ref> define the following Hoffman-Kruskal game: the $b$ value of all vertices is $2$ and all edge upper bounds are 1. As before, let the edge weights be $1$ and $3$ for $(u, v_1)$ and $(u, v_2)$, respectively.

The worth of the game is 4 and is obtained by matching both edges once each. The following are optimal dual solutions:

* Assign zero to all vertices and 1 and 3 to edges $(u, v_1)$ and $(u, v_2)$, respectively.

* Assign 1 to $u$, 2 to the upper bound dual of the edge $(u, v_2)$ and zero to the remaining vertices and edges.

Clearly, any convex combination of these two is also an optima dual solution. It is easy to verify that this list is exhaustive.

The surplus of the game is zero under the first dual and 2 under the second. Corresponding to the second dual, the allocation of payments of $(1, 0, 1)$ for $(u, v_1, v_2)$ is a core imputation. The corresponding dual solution assigns $(1/2, 0, 1/2)$ to vertices $(u, v_1, v_2)$ and 2 to the upper bound dual of the edge $(u, v_2)$; this dual is infeasible. Therefore this core imputation does not correspond to an optimal dual solution.

Let the graph of Figure <ref> define the following Hoffman-Kruskal game: the $b$ value of all vertices is $2$ and all edge lower bounds are 1; there are no edge upper bounds. As before, let the edge weights be $1$ and $3$ for $(u, v_1)$ and $(u, v_2)$, respectively.

The worth of the game is 4 and is obtained by matching both edges once each. Consider the following optimal dual solution: 	 Assign 3 to $u$, 2 to the lower bound dual of the edge $(u, v_1)$ and zero to the remaining vertices and edges. Under this dual, the surplus of the game is 6 and the corresponding payments of $(6, 0, 0)$ for $(u, v_1, v_2)$ is a core imputation.

Corresponding to this surplus, another payment in the core is $(3, 3, 0)$ for $(u, v_1, v_2)$. The corresponding dual solution assigns $(1.5, 0, 1.5)$ to vertices $(u, v_1, v_2)$ and 2 to the lower bound dual of the edge $(u, v_1)$; this dual is infeasible. Therefore this core imputation does not correspond to an optimal dual solution.

§ THE CORE OF CONCURRENT GAMES

The general graph matching game consists of an undirected graph $G = (V, E)$ and an edge-weight function $w$, with the vertices $V$ being agents and edges $E$ being possible doubles teams in the tennis analogy of Section <ref>; $w_{i j}$ represents the profit generated by team $(i, j)$. The worth of a coalition $S \subseteq V$, denoted by $p(S)$, is defined to be the weight of a maximum weight matching in the graph $G(S)$, i.e., the restriction of $G$ to vertices in $S$. Definitions <ref>, <ref>, <ref> carry over.

Deng et al. [6] showed that the core of this game is non-empty if and only if the weights of maximum weight integral and fractional matchings concur; if so, we will say that the game is concurrent. Below we give the LP-relaxation of the problem of finding a maximum weight fractional matching and thereby provide the underlying reason for the above-stated result of [6] as well as their characterization of the core of concurrent games.

We will work with the following LP (<ref>), whose optimal solutions are maximum weight fractional matchings in $G$.

∑_(i, j) ∈E  w_ij x_ij

∑_(i, j) ∈E x_ij≤1   ∀i ∈V
x_ij≥0∀(i, j) ∈E

Note that in case $G$ is bipartite, LP (<ref>) is equivalent to LP (<ref>). Therefore, by Theorem <ref>, it always has an integral optimal solution. On the other hand, if $G$ is non-bipartite, LP (<ref>) may have no integral optimal solutions, e.g., a triangle with unit weight edges. However, by Theorem <ref>, this LP always has a half-integral optimal solution.

(Balinski [1])
For a general graph, the vertices of the polytope defined by the constraints of LP (<ref>) are half-integral, such that the edges set to 1 form a matching and those set to half form disjoint odd-length cycles.

Taking $v_i$ to be dual variables for the first constraint of (<ref>), we obtain  LP (<ref>). Any feasible solution to this LP is called a cover of $G$, since for each edge $(i, j)$, $v_i$ and $v_j$ cover edge $(i, j)$ in the sense that $v_i + v_j \geq w_{ij}$. An optimal solution to this LP is a minimum cover. We will say that $v_i$ is the profit of player $i$.

∑_i ∈V  v_i

v_i + v_j ≥w_ij   ∀(i, j) ∈E
v_i≥0∀i ∈V

Let $Q_f$ ($Q_i$) be the weight of a maximum weight fractional (integral) matching in $G$. Now, $Q_f \geq Q_i$, since every integral matching is also a fractional matching. By the LP Duality Theorem, $Q_f$ equals the total value of a minimum cover. On the other hand, $Q_i$ is the worth of the game.

[6] proved that the core of the general graph matching game is non-empty if and only if $Q_f = Q_i$. If so, by a proof that is similar to that of the Shapley-Shubik Theorem, it is easy to see each optimal solution to the dual LP, namely LP (<ref>),  gives a way for distributing the worth of the game among agents so that the condition of the core is satisfied, i.e., it is a core imputation. The converse is also true, i.e., every core imputation is an optimal solution to the dual LP. We summarize below.

(Deng et al. [6])
The core of the general graph matching game is non-empty if and only if $Q_f = Q_i$. If so, 	the dual LP (<ref>) completely characterizes the core of the game.

Consider the graph given in Figure <ref>. Assume that the weight of edge $(v_2, v_7)$ is 2 and the weights of the rest of the edges is 1. This graph has three maximum weight integral matching, of weight 4, and edge $(v_2, v_7)$ is in each of them; in addition, the three matchings contain the edge sets $\{(v_1, v_6), (v_4, v_5) \}, \{(v_1, v_6), (v_3, v_4) \}$ and $\{(v_3, v_4), (v_5, v_6) \}$. This graph also has three fractional matchings having a weight of 4, which are not integral: the seven-cycle $v_1, v_2, v_7, v_3, v_4, v_5, v_6$ taken half-integrally; the three-cycle $v_1, v_2, v_7$ taken half-integrally together with the edges $\{(v_3, v_4), (v_5, v_6)\}$; and the three-cycle $v_2, v_3, v_7$ taken half-integrally together with the edges $\{(v_4, v_5), (v_1, v_6)\}$.

By Theorem <ref>, this game has a non-empty core. The unique core imputation assigns a profit of 1 to each of $v_2, v_4, v_6, v_7$ and zero to the rest. Observe that if the weight of edge $(v_2, v_7)$ is decreased a bit, then the core will become empty and if it is increased a bit, then the maximum weight fractional matchings will all be integral and the core will remain non-empty.

The graph for Example <ref>.

For completeness, we describe a different LP for general graphs, namely LP (<ref>), given by Edmonds [7], which always has integral optimal solutions; these are maximum weight matchings in the graph. This LP is an enhancement of LP (<ref>) via odd set constraints, as specified in (<ref>). The latter constraints are exponential in number, namely one for every odd subset $S$ of vertices. Clearly, the total number of integral matched edges in this set can be at most ${{(|S|-1)} \over 2}$. The constraint imposes this bound on any fractional matching as well, thereby ensuring that a fractional matching that picks each edge of an odd cycle half-integrally is disallowed and there is always an integral optimal matching.

∑_(i, j) ∈E  w_ij x_ij

∑_(i, j) ∈E x_ij≤1   ∀i ∈V
∑_(i, j) ∈S x_ij≤(|S|-1) 2   ∀S ⊆V,  S
x_ij≥0∀(i, j) ∈E

The dual of this LP has, in addition to variables corresponding to vertices, $v_i$, exponentially many more variables corresponding to odd sets, $z_S$, as given in (<ref>). As a result, the entire worth of the game does not reside on vertices only — it also resides on odd sets.

∑_i ∈V  v_i + ∑_S ⊆V,   z_S

v_i + v_j + ∑_S   ∋  i, jz_S ≥w_ij   ∀(i, j) ∈E
v_i≥0∀i ∈V
z_S≥0∀S ⊆V,  S

There is no natural way of dividing $z_S$ among the vertices in $S$ to restore core properties. The situation is more serious than that: it turns out that in general, the core of a non-bipartite game may be empty.

This is easy to see for the graph $K_3$, i.e., a clique on three vertices, $i, j, k$, with a weight of 1 on each edge. Any maximum matching in $K_3$ has only one edge, and therefore the worth of this game is 1. Suppose there is an imputation $v$ which lies in the core. Consider all three two-agent coalitions. Then, we must have:

\[ v(i) + v(j) \geq 1, \ \ \ \  v(j) + v(k) \geq 1 \ \ \ \ \mbox{and} \ \ \ \ v(i) + v(k) \geq 1 .\]

This implies $v(i) + v(j) + v(k) \geq 3/2$ which exceeds the worth of the game, giving a contradiction.

One recourse to this eventuality was provided in [30], which gives a ${1 \over 3}$-approximate core imputation for such games, i.e., the weight of a maximum weight matching in the graph is distributed among vertices in such a way that the total profit accrued by agents in a sub-coalition $S \subseteq V$ is at least ${1 \over 3}$ fraction of the profit which $S$ can generate by itself.

§.§ Complementarity Applied to Concurrent Games

In this section, we will provide answers to the three issues raised in the Introduction, as they pertain to concurrent games. First we provide necessary definitions, which are adaptations of definitions from Section <ref>. We will assume that $G = (V, E)$, $w: E \rightarrow \QQ_+$ is a concurrent game,

A generic player in $V$ will be denoted by $q$. We will say that $q$ is:

* essential if $q$ is matched in every maximum weight integral matching in $G$.

* viable if there is a maximum weight integral matching $M$ such that $q$ is matched in $M$ and another, $M'$ such that $q$ is not matched in $M'$.

* subpar if for every maximum weight integral matching $M$ in $G$, $q$ is not matched in $M$.

Let $y$ be an imputation in the core. We will say that $q$ gets paid in $y$ if $y_q > 0$ and does not get paid otherwise. Furthermore, $q$ is paid sometimes if there is at least one imputation in the core under which $q$ gets paid, and it is never paid if it is not paid under every imputation.

By a team we mean an edge in $G$; a generic one will be denoted as $e = (u, v)$. We will say that $e$ is:

* essential if $e$ is matched in every maximum weight matching in $G$.

* viable if there is a maximum weight matching $M$ such that $e \in M$, and another, $M'$ such that $e \notin M'$.

* subpar if for every maximum weight matching $M$ in $G$, $e \notin M$.

Let $y$ be an imputation in the core of a concurrent game. We will say that $e$ is fairly paid in $y$ if $y_u + y_v = w_e$ and it is overpaid if $y_u + y_v > w_e$[Observe that by the first constraint of the dual LP (<ref>), these are the only possibilities.]. Finally, we will say that $e$ is always paid fairly if it is fairly paid in every imputation in the core, and it is sometimes overpaid if there is a core imputation in which it is overpaid.

The following hold:

* For every player $q \in (U \cup V)$:

\[ q \ \mbox{is paid sometimes}  \ \Rightarrow \ q \ \mbox{is essential} \]

* For every team $e \in E$:

\[ e \ \mbox{is viable or essential} \ \Rightarrow \ e \ \mbox{is always paid fairly} \]

Observe that the first statement of Theorem <ref> is equivalent to the forward direction of Theorem <ref>, and the proof is also identical. The second statement of Theorem <ref> is equivalent to the reverse direction of Theorem <ref> and again the proof is identical.

The proofs of the reverse direction of Theorem <ref> and the forward direction of Theorem <ref> do not hold for general graphs. Counter-examples to these statements are given in Example <ref> and Example <ref>, respectively. In bipartite graphs, both these facts   follow from Theorem <ref>. The latter fact does not hold for LP (<ref>); however, a weaker fact, given in Theorem <ref>, holds.

Consider the game depicted in Figure <ref>. Let the weights of edges $(v_1, v_2)$, $(v_2, v_3)$, $(v_3, v_1)$ and $(v_1, v_4)$ be $1.5, 1, 1.5$ and $1$, respectively. Then an optimal integral matching is $\{ (v_1, v_4), (v_2, v_3) \}$, having weight 2. The three-cycle $v_1, v_2, v_3$, taken to the extent of half, is a fractional matching of the same weight. Therefore, this graph has non-empty core. It has a unique core imputation which assigns profits of $1, {1 \over 2}, {1 \over 2}, 0$ to $v_1, v_2, v_3, v_4$, respectively. Since $v_4$ is essential but is not paid in the unique core imputation, this game provides a counter-example to the reverse direction of Theorem <ref> in general graphs.

The counter-example related to Theorem <ref>.

Since the first statement of Theorem <ref> is weaker than Theorem <ref>, the following corollary is weaker than Corollary <ref>.

In a concurrent game, the set of essential players is non-empty and in every core imputation, the entire worth of the game is distributed among essential players.

The contrapositive of the second statement of Theorem <ref> is the following:

If a team is sometimes overpaid, then it is subpar.

In the game defined in Example <ref>, the teams $(v_4, v_7), (v_1, v_2), (v_2, v_3)$ and $(v_1, v_7)$ are all subpar, since they are not matched in any maximum weight matching. Of these, only the first team is overpaid in the unique imputation in the core, the rest are fairly paid. On the other hand,	the vertices which get positive profit are precisely the essential vertices.

Corollary <ref> is identical to Corollary <ref>.

In the presence of degeneracy, imputations in the core of a concurrent game treat:

* viable players in the same way as subpar players, namely they are never paid.

* viable teams in the same way as essential teams, namely they are always fairly paid.

§ DISCUSSION

Our most important open question is to shed light on the origins of core imputations, for the bipartite $b$-matching game and the Hoffman-Kruskal game, which do not correspond to optimal dual solutions. Is there a “mathematical structure” that produces them? A related question is to determine the complexity of the following question for these two games: Given an imputation for a game, decide if it belongs to the core. We believe this question should be co-NP-complete. On the other hand, the following question is clearly in P: Given an imputation for a game $I$, decide if it lies in $D(I)$.

Shapley and Shubik were able to characterize “antipodal” points in the core for the assignment game, see Theorem <ref>. An analogous understanding of the core of the general graph matching games having non-empty core will be desirable.

For the assignment game, Demange, Gale and Sotomayor [5] give an auction-based procedure to obtain a core imputation; it turns out to be optimal for the side that proposes, as was the case for the deferred acceptance algorithm of Gale and Shapley [13] for stable matching. Is there an analogous procedure for obtaining an imputation in the core of the general graph matching games having non-empty core?

§ ACKNOWLEDGEMENTS

I wish to thank Hervé Moulin for asking the interesting question of extending results obtained for the assignment game to general graph matching games having a non-empty core, and Federico Echenique for generously sharing his understanding of issues in economics. I also wish to thank Rohith Gangam and Thorben Trobst for several valuable discussions.

[1]
Michel Louis Balinski.
Integer programming: methods, uses, computations.
Management science, 12(3):253–313, 1965.

[2]
Péter Biró, Walter Kern, and Daniël Paulusma.
Computing solutions for matching games.
International journal of game theory, 41(1):75–90, 2012.

[3]
Olga N Bondareva.
Some applications of linear programming methods to the theory of
cooperative games.
Problemy Kibernetiki, 10(119):139, 1963.

[4]
Christopher P Chambers and Federico Echenique.
The core matchings of markets with transfers.
American Economic Journal: Microeconomics, 7(1):144–64, 2015.

[5]
Gabrielle Demange, David Gale, and Marilda Sotomayor.
Multi-item auctions.
Journal of political economy, 94(4):863–872, 1986.

[6]
Xiaotie Deng, Toshihide Ibaraki, and Hiroshi Nagamochi.
Algorithmic aspects of the core of combinatorial optimization games.
Mathematics of Operations Research, 24(3):751–766, 1999.

[7]
J. Edmonds.
Maximum matching and a polyhedron with 0,1-vertices.
Journal of Research of the National Bureau of Standards B,
69B:125–130, 1965.

[8]
Kimmo Eriksson and Johan Karlander.
Stable outcomes of the roommate game with transferable utility.
International Journal of Game Theory, 29(4):555–569, 2001.

[9]
Ulrich Faigle, Walter Kern, Sándor P Fekete, and Winfried Hochstättler.
The nucleon of cooperative games and an algorithm for matching games.
Mathematical Programming, 83(1):195–211, 1998.

[10]
Daniel Granot and Gur Huberman.
Minimum cost spanning tree games.
Mathematical programming, 21(1), 1981.

[11]
Daniel Granot and Gur Huberman.
On the core and nucleolus of minimum cost spanning tree games.
Mathematical programming, 29(3):323–347, 1984.

[12]
M. Grotschel, L. Lovasz, and A. Schirjver.
Geometric Algorithms and Combinatorial Optimization.
Springer-Verlag, 1988.

[13]
David Gale and Lloyd S Shapley.
College admissions and the stability of marriage.
The American Mathematical Monthly, 69(1):9–15, 1962.

[14]
Alan J Hoffman and Joseph B Kruskal.
Integral boundary points of convex polyhedra.
In 50 Years of integer programming 1958-2008, pages 49–76.
Springer, 2010.

[15]
Walter Kern and Daniël Paulusma.
Matching games: the least core and the nucleolus.
Mathematics of operations research, 28(2):294–308, 2003.

[16]
Tamás Király and Júlia Pap.
Total dual integrality of rothblum's description of the
stable-marriage polyhedron.
Mathematics of Operations Research, 33(2):283–290, 2008.

[17]
Jochen Könemann, Kanstantsin Pashkovich, and Justin Toth.
Computing the nucleolus of weighted cooperative matching games in
polynomial time.
Mathematical Programming, 183(1):555–581, 2020.

[18]
Zhuan Khye Koh and Laura Sanità.
An efficient characterization of submodular spanning tree games.
Mathematical Programming, 183(1):359–377, 2020.

[19]
L. Lovász and M.D. Plummer.
Matching Theory.
North-Holland, Amsterdam–New York, 1986.

[20]
Hervé Moulin.
Cooperative microeconomics: a game-theoretic introduction,
volume 313.
Princeton University Press, 2014.

[21]
Michael Maschler, Bezalel Peleg, and Lloyd S Shapley.
Geometric properties of the kernel, nucleolus, and related solution
Mathematics of operations research, 4(4):303–338, 1979.

[22]
Marina Núñez and Carles Rafels.
On the dimension of the core of the assignment game.
Games and Economic Behavior, 64(1):290–302, 2008.

[23]
Hiroshi Nagamochi, Dao-Zhi Zeng, Naohiśa Kabutoya, and Toshihide Ibaraki.
Complexity of the minimum base game on matroids.
Mathematics of Operations Research, 22(1):146–164, 1997.

[24]
Uriel G Rothblum.
Characterization of stable matchings as extreme points of a polytope.
Mathematical Programming, 54(1):57–67, 1992.

[25]
A. Schrijver.
Theory of Linear and Integer Programming.
John Wiley & Sons, New York, NY, 1986.

[26]
Paul D Seymour.
Decomposition of regular matroids.
Journal of combinatorial theory, Series B, 28(3):305–359,

[27]
Lloyd S Shapley.
On balanced sets and cores.
Technical report, RAND Corp Santa Monica, California, 1965.

[28]
Lloyd S Shapley and Martin Shubik.
The assignment game I: The core.
International Journal of Game Theory, 1(1):111–130, 1971.

[29]
John H Vande Vate.
Linear programming brings marital bliss.
Operations Research Letters, 8(3):147–153, 1989.

[30]
Vijay V Vazirani.
The general graph matching game: Approximate core.
Games and Economic Behavior, 132, 2022.

[31]
Vijay V Vazirani.
The investment management game: Extending the scope of the notion of
arXiv preprint arXiv:2302.00608, 2023.

[32]
Han Xiao, Tianhang Lu, and Qizhi Fang.
Approximate core allocations for multiple partners matching games.
arXiv preprint arXiv:2107.01442, 2021.