On the complexity of core, kernel, and bargaining set

DOI10.1016/j.artint.2011.06.002zbMath1233.91018OpenAlexW2087243523WikidataQ57931574 ScholiaQ57931574MaRDI QIDQ650525

Luigi Palopoli, Enrico Malizia, Gianluigi Greco, Francesco Scarcello

Publication date: 25 November 2011

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2011.06.002

zbMATH Keywords

computational complexitycoalitional gamesbounded treewidthsolution conceptscompact representations

Mathematics Subject Classification ID

Cooperative games (91A12)

Related Items (14)

Inconsistency-tolerant query answering for existential rules ⋮ Characteristic function games with restricted agent interactions: core-stability and coalition structures ⋮ The Least-Core and Nucleolus of Path Cooperative Games ⋮ A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison ⋮ A cooperative game-theoretic approach to the social ridesharing problem ⋮ Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability ⋮ On the use of binary decision diagrams for solving problems on simple games ⋮ On the complexity of core, kernel, and bargaining set ⋮ Path cooperative games ⋮ 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 ⋮ The Complexity of the Nucleolus in Compact Games ⋮ Cooperative games with overlapping coalitions: charting the tractability frontier ⋮ Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equilibria, fixed points, and complexity classes
• On the complexity of core, kernel, and bargaining set
• Permutation games: Another class of totally balanced games
• Graph minors. III. Planar tree-width
• Reasoning about coalitional games
• NP-completeness of some problems concerning voting games
• On the power of structural decompositions of graph-based representations of constraint problems
• The complexity of facets (and some facets of complexity)
• The complexity of stochastic games
• A taxonomy of complexity classes of functions
• On the complexity of testing membership in the core of min-cost spanning tree games
• On approximately fair cost allocation in Euclidean TSP games
• Traveling salesman games with the Monge property
• On the computational complexity of weighted voting games
• Complexity of constructing solutions in the core based on synergies among coalitions
• The inequalities that determine the bargaining set \({\mathcal M}_ 1^ {(1)}\).
• The assignment game. I: The core
• A note on Helly's theorem
• On some approximately balanced combinatorial cooperative games
• Coalition Structure Generation over Graphs
• Easy problems for tree-decomposable graphs
• A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications
• Non-Transferable Utility Coalitional Games via Mixed-Integer Linear Constraints
• The Cost of Stability in Coalitional Games
• Efficient algorithms for finding maximum matching in graphs
• Finite Rationality and Interpersonal Complexity in Repeated Games
• Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts
• Power of Natural Semijoins
• Totally Balanced Games and Games of Flow
• 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
• Cooperative facility location games
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• Cost minimization in wireless networks with a bounded and unbounded number of interfaces
• The Nucleolus of a Characteristic Function Game
• The kernel of a cooperative game
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Matching Games: The Least Core and the Nucleolus
• Finding nucleolus of flow game
• Graph Ramsey theory and the polynomial hierarchy

This page was built for publication: On the complexity of core, kernel, and bargaining set