On the complexity of nucleolus computation for bipartite \(b\)-matching games

DOI10.1007/978-3-030-85947-3_12zbMath1492.91032arXiv2105.07161OpenAlexW3202130907MaRDI QIDQ2670922

Justin Toth, Jochen Könemann, Felix Zhou

Publication date: 1 June 2022

Full work available at URL: https://arxiv.org/abs/2105.07161

zbMATH Keywords

computational complexitycooperative game theorynucleolus\(b\)-matching

Mathematics Subject Classification ID

Cooperative games (91A12) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic game theory and complexity (91A68)

Related Items

Arboricity games: the core and the nucleolus

Cites Work

• Unnamed Item
• On the core and nucleolus of directed acyclic graph games
• The nucleolus of balanced simple flow networks
• A note on the complexity of finding regular subgraphs
• Game theoretic analysis of a bankruptcy problem from the Talmud
• An algorithm for finding the nucleolus of assignment games
• Note on the computational complexity of least core concepts for min-cost spanning tree games.
• On the computation of the nucleolus of a cooperative game
• Computing the nucleolus of some combinatorially-structured games.
• The stable fixtures problem with payments
• Characterization sets for the nucleolus in balanced games
• The kernel/nucleolus of a standard tree game
• Characterization sets for the nucleolus
• Computing the nucleolus of min-cost spanning tree games is NP-hard.
• A general framework for computing the nucleolus via dynamic programming
• On the computational complexity of weighted voting games
• The subcoalition-perfect core of cooperative games
• Computing an element in the lexicographic kernel of a game
• The assignment game. I: The core
• Strongly essential coalitions and the nucleolus of peer group games
• The Bargaining Problem
• Algorithmic Cooperative Game Theory
• The Cooperative Game Theory Foundations of Network Bargaining Games
• Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• Convergent Transfer Schemes for N-Person Games
• The Nucleolus of a Characteristic Function Game
• The kernel of a cooperative game
• Matching Games: The Least Core and the Nucleolus
• Finding nucleolus of flow game
• Computing the nucleolus of weighted cooperative matching games in polynomial time