Introduction
In cooperative game theory, the central challenge is determining how to distribute the total profit of a "grand coalition" among its members such that the distribution is stable. A payoff is considered stable if no subgroup of players has a rational incentive to break away and form their own coalition. Two of the most prominent solution concepts for this problem are the least-core and the nucleolus.
While finding these values is often computationally intensive—and specifically NP-hard for weighted matching games—this research provides the first polynomial-time algorithms for computing the least-core and nucleolus in Threshold Cardinality Matching Games (TCMG). By focusing on unweighted graphs, the authors demonstrate that fair profit distribution can be achieved efficiently, revealing deep structural properties of these games.
The Threshold Cardinality Matching Game (TCMG)
In a TCMG, players are represented as vertices in a graph. A coalition (a subset of players) is considered "winning" if the maximum matching in the subgraph induced by those players meets or exceeds a specific threshold $T$.
- Winning Coalition: Earns a profit of 1 if the maximum matching size $\ge T$.
- Losing Coalition: Earns a profit of 0 otherwise.
The objective is to find a payoff vector—a distribution of the total profit—that satisfies stability criteria. The least-core minimizes the maximum dissatisfaction (or "excess") among all possible coalitions, while the nucleolus is a unique payoff vector that lexicographically minimizes these dissatisfactions, providing a refined sense of fairness.
Algorithmic Framework
The authors utilize a combination of combinatorial optimization and linear programming (LP) to overcome the exponential number of constraints typically associated with stability concepts.
Ellipsoid Method and Separation Oracles
To compute the least-core, the authors design a "separation oracle." Because there are $2^n$ possible coalitions, a standard LP solver cannot list every constraint. The separation oracle allows the Ellipsoid method to function in polynomial time by efficiently identifying violated constraints—specifically by finding the minimum cost matching of a fixed size $T$.
Gallai-Edmonds Decomposition
The research leverages the Gallai-Edmonds Decomposition, a fundamental tool in matching theory that partitions a graph based on its maximum matching properties. This decomposition is instrumental in characterizing the structure of the least-core and identifying which players are essential to reaching the threshold $T$.
Dual Linear Programming and Game Duality
By analyzing the dual of the least-core problem, the authors establish a mathematical bridge to a non-cooperative zero-sum game known as the Matching Intercept Game. In this scenario, one player attempts to "intercept" or block a matching formed by another. The authors prove that the least-core of a TCMG is mathematically equivalent to the mixed Nash Equilibrium of this intercept game, linking cooperative stability directly to competitive strategy.
Key Insights: Threshold Independence
One of the most striking findings of the paper is the phenomenon of Threshold Independence. For specific graph classes—namely bipartite graphs and graphs containing perfect matchings—the least-core and nucleolus do not depend on the specific value of the threshold $T$.
This implies that whether a coalition needs a matching of size 2 or size 10 to "win," the fairest way to distribute the profit among the players remains identical. This structural robustness suggests that in many common network configurations, the internal logic of the graph's connectivity is more important for fairness than the specific difficulty of the task (the threshold).
Results and Complexity
The paper establishes several landmark results regarding the computational complexity of these games:
- Least-Core Efficiency: Computing the least-core value, finding a payoff within the least-core, and verifying a given payoff are all solvable in polynomial time for any TCMG.
- Nucleolus for Special Cases: The authors provide polynomial-time algorithms for the nucleolus in bipartite graphs, graphs with perfect matchings, and "Edge Coalitional Games" (where $T=1$).
- Essential Coalitions: The research proves that stability can be determined by looking only at "essential coalitions"—minimal winning matchings and individual players—rather than the entire power set of players.
Conclusion and Future Work
This work significantly advances the algorithmic understanding of cooperative games on graphs. By moving from weighted to cardinality-based matching, the authors transitioned the problem from NP-hard to polynomial-time solvable.
While the nucleolus is efficiently computable for bipartite and perfect-matching graphs, a general polynomial-time algorithm for the nucleolus on any unweighted graph remains a conjecture. Future research may also explore extending these techniques to other threshold-based cooperative games, such as those where players have varying weights or where the winning condition involves different combinatorial structures.
Summary updated