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

DOI10.1007/978-3-030-85947-3_12MaRDI QIDQ2670922zbMATH OpenOpenAlexFDO

Authors Jochen Könemann, Justin Toth, Felix Zhou

Publication date 1 June 2022

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

zbMATH Keywords

\(b\)-matchingcomputational complexitycooperative game theorynucleolus

Mathematics Subject Classification ID

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

Abstract: We explore the complexity of nucleolus computation in b-matching games on bipartite graphs. We show that computing the nucleolus of a simple b-matching game is NP-hard even on bipartite graphs of maximum degree 7. We complement this with partial positive results in the special case where b values are bounded by 2. In particular, we describe an efficient algorithm when a constant number of vertices satisfy b(v) = 2 as well as an efficient algorithm for computing the non-simple b-matching nucleolus when b = 2.

Recommendations

• A general framework for computing the nucleolus via dynamic programming
• Matching Games: The Least Core and the Nucleolus
• On solution concepts for matching games
• Computing solutions for matching games

Cites work

• A general framework for computing the nucleolus via dynamic programming
• A note on the complexity of finding regular subgraphs
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• Algorithmic Cooperative Game Theory
• An algorithm for finding the nucleolus of assignment games
• Characterization sets for the nucleolus
• Characterization sets for the nucleolus in balanced games
• Computing an element in the lexicographic kernel of a game
• Computing the nucleolus of min-cost spanning tree games is NP-hard.
• Computing the nucleolus of some combinatorially-structured games.
• Convergent Transfer Schemes for N-Person Games
• Finding nucleolus of flow game
• Game theoretic analysis of a bankruptcy problem from the Talmud
• Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• Matching Games: The Least Core and the Nucleolus
• 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
• On the computational complexity of weighted voting games
• On the core and nucleolus of directed acyclic graph games
• Strongly essential coalitions and the nucleolus of peer group games
• The assignment game. I: The core
• The bargaining problem
• The cooperative game theory foundations of network bargaining games
• The kernel of a cooperative game
• The kernel/nucleolus of a standard tree game
• The Nucleolus of a Characteristic Function Game
• The nucleolus of balanced simple flow networks
• The stable fixtures problem with payments
• The subcoalition-perfect core of cooperative games

Cited in

(5)

• Computing the nucleolus of some combinatorially-structured games.
• Arboricity games: the core and the nucleolus
• On the complexity of nucleolus computation for bipartite \(b\)-matching games
• A polynomial time algorithm for computing the nucleolus for a class of disjunctive games with a permission structure
• Partitioned matching games for international kidney exchange

This page was built for publication: On the complexity of nucleolus computation for bipartite \(b\)-matching games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2670922)