On the Core of the-Matching Game

Rohith Reddy Gangam, Shayan Taherijam, Vijay V. VaziraniarXiv 2025 · arXiv · OpenReview

TL;DR

This paper tackles the computational problem of determining if a proposed profit distribution (an imputation) is "stable" within a cooperative game, specifically for b-matching games where edges can be used multiple times. The authors prove that this seemingly simple check is, in fact, computationally hard (co-NP-complete), extending known hardness results for similar game theory problems. This has implications for understanding fairness and stability in resource allocation scenarios.

What Problem Does This Paper Address?

In cooperative game theory, the "core" is a fundamental concept representing stable outcomes. An imputation is a way to distribute the total value generated by a group of agents. An imputation is in the core if no subgroup of agents has an incentive to break away and form their own coalition, because they can achieve at least as much value on their own as they receive in the proposed distribution.

The computational challenge is: given a game and a proposed imputation, can we efficiently determine if it lies in the core? This problem is known to be in co-NP (meaning it's easy to verify a "no" answer). For some games, like the assignment game, this check is easy (in P). However, for other natural games like max-flow and minimum spanning tree (MST) games, it's been shown to be computationally hard (co-NP-hard).

A specific open question was the "b-matching game" where edges can be used multiple times (unconstrained b-matching). This is a natural extension of the assignment game and has interesting structural properties. The authors aim to resolve the computational complexity of checking core membership for this game.

Methods

The paper employs a common technique in computational complexity: reduction. They show that a known hard problem can be transformed into the problem of checking core membership in b-matching games. Specifically, they reduce the 0-1 Knapsack Problem (a well-known NP-complete problem) to the problem of finding an "unstable sub-coalition" in a b-matching game on a star graph.

To achieve this, they construct specific star graphs and define edge weights and vertex capacities in a way that mirrors the items, weights, values, and capacity of the knapsack problem. If a knapsack solution exists, it corresponds to an unstable coalition in the b-matching game, and vice-versa.

They then extend this hardness result from star graphs to general bipartite graphs by constructing a new graph that incorporates the star graph structure. This construction cleverly adds vertices and edges such that the core membership problem in the larger graph is equivalent to the core membership problem in the original star graph.

Finally, they leverage these hardness results to show that finding "fair" core imputations (like leximin or leximax) is also NP-hard.

Datasets

Not discussed in the paper. The paper focuses on theoretical computational complexity and uses constructed graph instances for proofs rather than real-world datasets.

Key Insights and Ideas

  • The core check is hard for b-matching: The paper definitively shows that determining if an imputation is in the core of an unconstrained b-matching game is co-NP-complete. This resolves a significant open question in the field.
  • Reduction from Knapsack is key: The clever construction of b-matching games from knapsack instances is a crucial methodological contribution, demonstrating how to map the constraints and objectives of one problem to the other.
  • Star graphs as a stepping stone: The initial proof of hardness on simpler star graphs simplifies the problem and provides a foundation for generalizing to more complex bipartite graphs.
  • Fairness is also hard: The paper extends the hardness results to fair imputation concepts (leximin/leximax), suggesting that finding "optimal" fair distributions is computationally challenging.

Key Results

  • Co-NP-Completeness for Core Membership: Deciding if an imputation is in the core of an unconstrained b-matching game is co-NP-complete.
  • NP-Hardness for Fair Imputations: Computing leximin or leximax core imputations for b-matching games is NP-hard.
  • Characterization for Star Graphs: The paper provides a complete characterization of the core for b-matching games on star graphs, leading to a polynomial-time algorithm for this specific case.

Limitations and Future Work

  • Focus on theoretical hardness: The paper establishes theoretical hardness bounds. Practical algorithms for finding core imputations or checking membership in specific scenarios might still be efficient for many real-world instances, even if worst-case complexity is high.
  • Specific b-matching variants: The paper focuses on the "unconstrained" b-matching game. Further research could explore the complexity for other variants or related graph structures.
  • Algorithmic implications: While hardness is established, developing efficient approximation algorithms or heuristics for finding core imputations or checking membership in practice remains an important avenue for future work. The paper mentions that for star graphs, a polynomial-time algorithm exists, suggesting that specific structures can yield tractability.

Summary updated

Abstract

The core is a quintessential solution concept for profit sharing in cooperative game theory. An imputation allocates the worth of the given game among its agents. The imputation lies in the core of the game if, for each sub-coalition, the amount allocated to its agents is at least the worth of this sub-coalition. Hence, under a core imputation, each of exponentially many sub-coalitions gets satisfied. The following computational question has received much attention: Given an imputation, does it lie in the core? Clearly, this question lies in co-NP, since a co-NP certificate for this problem would be a sub-coalition which is not satisfied under the imputation. This question is in P for the assignment game [SS71] and has been shown to be co-NP-hard for several natural games, including max-flow [FZCD02] and MST [FKFH97]. The one natural game for which this question has remained open is the b-matching game when the number of times an edge can be matched is unconstrained; in case each edge can be matched at most once, it is co-NP-hard [BKPW18]. At the outset, it was not clear which way this open question would resolve: on the one hand, for all but one game, this problem was shown co-NP-hard and on the other hand, proximity to the assignment problem and the deep structural properties of matching could lead to a positive result. In this paper, we show that the problem is indeed co-NP-hard.
BibTeX
@misc{gangam2025core,
  author = {Rohith Reddy Gangam and Shayan Taherijam and Vijay V. Vazirani},
  title = {{On the Core of the-Matching Game}},
  year = {2025},
  eprint = {2502.01914},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.01914},
}

Loading related content...

Figure