The Complexity of the Nucleolus in Compact Games

DOI10.1145/2692372.2692374zbMath1348.91073OpenAlexW2072395547WikidataQ62044181 ScholiaQ62044181MaRDI QIDQ2828226

Enrico Malizia, Francesco Scarcello, Gianluigi Greco, Luigi Palopoli

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10871/31581

zbMATH Keywords

computational complexitygame theorylinear programmingnucleoluscoalitional gamessolution conceptscompact representations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12) Linear programming (90C05) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Characteristic function games with restricted agent interactions: core-stability and coalition structures ⋮ A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ Answers set programs for non-transferable utility games: expressiveness, complexity and applications ⋮ Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting ⋮ A heuristic procedure for computing the nucleolus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial time algorithm for computing the nucleolus for a class of disjunctive games with a permission structure
• On the complexity of core, kernel, and bargaining set
• Computing the nucleolus of cyclic permutation games
• On finding the nucleolus of an \(n\)-person cooperative game
• Reasoning about coalitional games
• On the complexity of succinct zero-sum games
• Game theoretic analysis of a bankruptcy problem from the Talmud
• NP is as easy as detecting unique solutions
• The \({\mathcal B}\)-nucleolus of TU-games
• An algorithm for finding the nucleolus of assignment games
• The nucleolus and kernel of veto-rich transferable utility games
• A simple expression for the nucleolus in a special case
• A note on the nucleolus
• \(\Gamma\)-component additive 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.
• On the computational complexity of weighted voting games
• Complexity of constructing solutions in the core based on synergies among coalitions
• A simple algorithm for the nucleolus of airport profit games
• The assignment game. I: The core
• The Böhm-Bawerk horse market: a cooperative analysis
• A note on Helly's theorem
• On Computing the Nucleolus of a Balanced Connected Game
• A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications
• Non-Transferable Utility Coalitional Games via Mixed-Integer Linear Constraints
• Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts
• A procedure for finding the nucleolus of a cooperativen person game
• Totally Balanced Games and Games of Flow
• On Some Network Flow Games
• On the core of linear production games
• Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
• On the Complexity of Cooperative Solution Concepts
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Computing the Nucleolus by Solving a Prolonged Simplex Algorithm
• The Nucleolus of a Characteristic Function Game
• The Nucleolus as a Solution of a Minimization Problem
• Matching Games: The Least Core and the Nucleolus
• Finding nucleolus of flow game