On the computational complexity of qualitative coalitional games

DOI10.1016/j.artint.2004.04.002zbMath1085.68070OpenAlexW2029608926MaRDI QIDQ814613

Paul E. Dunne, Michael Wooldridge

Publication date: 7 February 2006

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

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

zbMATH Keywords

Computational complexityMultiagent systemsCoalitional games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12) Logic in artificial intelligence (68T27)

Related Items (14)

Reasoning about coalitional games ⋮ Cooperation through social influence ⋮ Characteristic function games with restricted agent interactions: core-stability and coalition structures ⋮ Effectivity functions and efficient coalitions in Boolean games ⋮ Optimal coalition formation and surplus distribution: two sides of one coin ⋮ Formal modelling and verification of probabilistic resource bounded agents ⋮ Dependencies Between Players in Boolean Games ⋮ On the computational complexity of coalitional resource games ⋮ Coalition formation in social environments with logic-based agents1 ⋮ Dependencies between players in Boolean games ⋮ Solving coalitional resource games ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ Quantified coalition logic ⋮ A logical characterisation of qualitative coalitional games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of facets (and some facets of complexity)
• Lower bounds on monotone complexity of the logical permanent
• The network complexity and the Turing machine complexity of finite functions
• Complete sets and the polynomial-time hierarchy
• Methods for task allocation via agent coalition formation
• Coalition structure generation with worst case guarantees
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• More on non-cooperation in dialogue logic
• Graph-Based Algorithms for Boolean Function Manipulation
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Relations Among Complexity Measures
• A Modal Logic for Coalitional Power in Games
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: On the computational complexity of qualitative coalitional games