On the Complexity of Nucleolus Computation for Bipartite b-Matching Games

Basic Information

• Paper ID: 2105.07161
• Title: On the Complexity of Nucleolus Computation for Bipartite b-Matching Games
• Authors: Jochen Könemann, Justin Toth, Felix Zhou (University of Waterloo)
• Classification: cs.GT (Game Theory), cs.CC (Computational Complexity), cs.DS (Data Structures and Algorithms)
• Publication Date: December 27, 2022 (arXiv version)
• Paper Link: https://arxiv.org/abs/2105.07161

Abstract

This paper investigates the computational complexity of nucleolus computation for b-matching games on bipartite graphs. The research demonstrates that computing the nucleolus of simple b-matching games is NP-hard even on bipartite graphs with maximum degree 7. As a complement, the paper provides partial positive results for the special case where b is restricted to 2, particularly describing efficient algorithms for cases where a constant number of vertices satisfy b(v)=2, and efficient algorithms for computing the nucleolus of non-simple b-matching games when b≡2.

Research Background and Motivation

Problem Background

1. Cooperative Game Theory: This paper studies cooperative b-matching games, an important class of combinatorial optimization games that can model inter-firm cooperation, network bargaining, and other real-world scenarios.
2. Nucleolus Computation: The nucleolus is one of the most important solution concepts in cooperative game theory, providing a unique and "most stable" payoff distribution scheme.
3. Computational Complexity: Despite its favorable theoretical properties, the computational complexity of the nucleolus has remained an open problem.

Research Motivation

1. Theoretical Gap: Kern and Paulusma posed an open problem on nucleolus computation for general matching games in 2003, and Deng and Fang conjectured in 2008 that this problem is NP-hard.
2. Bipartite Graph Specificity: While the core of bipartite b-matching games is known to be non-empty, the computational complexity of the nucleolus remains unknown.
3. Practical Applications: b-matching games have important applications in supply chain management, network bargaining, and other domains.

Limitations of Existing Work

• NP-hardness for b≥3 on general graphs is known, but the proof relies on odd cycle structures.
• Bipartite graphs avoid odd cycle issues, making the complexity unclear.
• Lack of efficient algorithms for special cases.

Core Contributions

1. Main Hardness Result: Proves that determining whether a given allocation is the nucleolus of a simple 3-matching game on bipartite graphs with maximum degree 7 is NP-hard.
2. New NP-Hard Problem: Introduces and proves the NP-hardness of the "Two from Cubic Subgraph" problem.
3. Positive Algorithmic Results: Provides polynomial-time algorithms for special cases with b≤2:
   • Simple b-matching games when a constant number of vertices satisfy b_v=2.
   • Non-simple b-matching games when b≡2.
4. Technical Innovation: Extends the theoretical analysis framework of the Kopelowitz scheme for nucleolus computation.

Methodology Details

Task Definition

Input: Bipartite graph G=(N,E), vertex capacities b: N→Z⁺, edge weights w: E→R Output: Determine whether a given allocation is the nucleolus of the corresponding b-matching game Constraints: Simple b-matching requires each edge to be used at most once; non-simple cases allow edge reuse.

Hardness Proof Architecture

1. Reduction Strategy

• Reduction from the "Two from Cubic Subgraph" problem to the nucleolus decision problem.
• Uses gadget graph construction techniques proposed by Birő et al.

2. Gadget Graph Construction

For each vertex u in the original graph G, create 5 new vertices {v_u, w_u, x_u, y_u, z_u} forming a K₃,₃ subgraph:

N* := N ∪ {v_u, w_u, x_u, y_u, z_u : u ∈ N}

3. Nucleolus Analysis Framework

Analyzes the nucleolus using the Kopelowitz scheme:

• If no "two from cubic subgraph" exists, the uniform allocation x* ≡ 3/2 is the nucleolus.
• If one exists, then x* is not the nucleolus.

Two from Cubic Subgraph Problem

Definition: Given a graph G, determine whether there exists a subgraph H and distinct vertices u,v such that:

deg_H(w) = {2, w ∈ {u,v}
           {3, otherwise w ∈ V(H)

Hardness Proof: Reduction from Exact Cover by 3-Sets through complex graph construction techniques.

Positive Results Methods

1. Characterization Set Method

Uses the characterization set theory of Granot et al.:

S := {S ∈ S : For all maximum-weight b-matchings M of G[S], G[S][M] is connected}

2. Polynomial-Time Algorithm Conditions

When the size of the characterization set S is polynomial, the nucleolus can be computed in polynomial time.

Experimental Setup

This paper is primarily theoretical work without traditional experimental setup, but rather validates results through mathematical proofs.

Theoretical Verification Methods

1. Constructive Proofs: Prove hardness through explicit graph constructions.
2. Reduction Proofs: Establish polynomial-time reductions between problems.
3. Algorithm Analysis: Analyze the time complexity of proposed algorithms.

Experimental Results

Main Theoretical Results

Theorem 1.1 (Hardness Result)

In unweighted bipartite 3-matching games with maximum degree 7, determining whether an allocation equals the nucleolus is NP-hard.

Theorem 1.2 (Positive Results)

Let G be a simple bipartite graph with bipartition N = A∪̇B, k≥0 a constant independent of |N|, and b≤2:

1. If all vertices in A satisfy b_v=2 but at most k vertices in B satisfy b_v=2, then the nucleolus of the simple weighted b-matching game can be computed in polynomial time.
2. If b≡2, then the nucleolus of the non-simple weighted b-matching game can be computed in polynomial time.

Theorem 2.1 (New Problem Hardness)

The Two from Cubic Subgraph problem is NP-hard on bipartite graphs with maximum degree 4.

Technical Innovation Results

1. Propagation Lemma: Proves propagation properties of locally regular subgraphs.
2. Characterization Set Application: First application of this technique to b-matching games.
3. Non-simple Matching Analysis: Simplifies problem structure using bipartite graph properties.

Related Work

Nucleolus Computation Complexity

• Positive Results: Matching games KP03, assignment games SR94, convex games FKK01
• Hardness Results: Network flow games DFS09, weighted threshold games Elk+07, spanning tree games FKK98

b-Matching Game Research

• Bateni et al.: Polynomial algorithm for bipartite b-matching games with b_v=1 on one side Bat+10
• Birő et al.: NP-hardness for b≥3 on general graphs Bir+19
• Könemann et al.: Polynomial algorithm for weighted matching games KPT20

Methodological Contributions

• Extended application of the Kopelowitz scheme
• Local regularity analysis techniques
• Complexity analysis framework for combinatorial optimization games

Conclusions and Discussion

Main Conclusions

1. Complexity Boundaries: Clarifies NP-hardness of nucleolus computation for bipartite b-matching games when b≥3.
2. Algorithm Design: Provides practical polynomial-time algorithms for special cases with b≤2.
3. Theoretical Framework: Establishes a systematic methodology for analyzing such problems.

Limitations

1. Degree Restrictions: Hardness results require maximum degree 7, which is relatively high.
2. Special Cases: Positive results apply only to b≤2 or specific structures.
3. Non-simple vs. Simple: Significant complexity differences between the two problem classes.

Future Directions

1. General b≤2 Cases: Complexity of simple b-matching games on general bipartite graphs.
2. Combinatorial Algorithms: Development of non-LP-based combinatorial algorithms.
3. Approximation Algorithms: Approximate solution schemes for hard cases.
4. Practical Applications: Application of theoretical results to concrete domain problems.

In-Depth Evaluation

Strengths

1. Theoretical Rigor: Complete and technically sophisticated proofs, particularly the hardness proof for Two from Cubic Subgraph.
2. Problem Importance: Resolves an important open problem in the field.
3. Methodological Innovation: Cleverly combines graph-theoretic constructions with game-theoretic analysis.
4. Result Completeness: Provides both hardness results and positive algorithms, forming a complete complexity landscape.

Weaknesses

1. Practical Applicability: Connection between theoretical results and real-world application scenarios could be stronger.
2. Algorithm Implementation: Lacks concrete implementation and performance analysis of algorithms.
3. Parameter Optimization: Degree bounds in hardness results have room for improvement.

Impact

1. Theoretical Contribution: Provides important complexity results for cooperative game theory.
2. Methodological Value: Proof techniques applicable to other combinatorial optimization games.
3. Practical Value: Positive algorithmic results directly applicable to related problems.

Applicable Scenarios

1. Network Bargaining: Resource allocation in bipartite networks.
2. Supply Chain Management: Revenue sharing among cooperating enterprises.
3. Matching Markets: Bilateral matching problems with capacity constraints.

References

This paper cites important literature in the field, including:

• Sch69 Schmeidler's pioneering work on the nucleolus
• KP03 Kern and Paulusma's foundational research on matching games
• Bir+18 Birő et al.'s hardness results on core separation
• GGZ98 Granot et al.'s theoretical framework on characterization sets

Overall Assessment: This is a high-quality theoretical computer science paper making important contributions at the intersection of cooperative game theory and algorithmic complexity. The paper demonstrates high technical content with rigorous proofs, providing a complete answer to an important open problem in the field.