On the complexity of core, kernel, and bargaining set

DOI10.1016/J.ARTINT.2011.06.002zbMATH Open1233.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 complexitybounded treewidthcoalitional gamessolution conceptscompact representations

Mathematics Subject Classification ID

Cooperative games (91A12)

Cites Work

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

Cited In (15)

• Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting
• Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
• Complexity of computing the Shapley value in partition function form games
• The complexity of the nucleolus in compact games
• Path cooperative games
• A cooperative game-theoretic approach to the social ridesharing problem
• Answers set programs for non-transferable utility games: expressiveness, complexity and applications
• 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
• Cooperative games with overlapping coalitions: charting the tractability frontier
• On the complexity of core, kernel, and bargaining set
• Characteristic function games with restricted agent interactions: core-stability and coalition structures
• On the use of binary decision diagrams for solving problems on simple games
• The Least-Core and Nucleolus of Path Cooperative Games
• Inconsistency-tolerant query answering for existential rules

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

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