On the computational complexity of qualitative coalitional games

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

Michael Wooldridge, Paul E. Dunne

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 complexity; Multiagent systems; Coalitional games

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

91A12: Cooperative games

68T27: Logic in artificial intelligence

Related Items

Optimal coalition formation and surplus distribution: two sides of one coin, Reasoning about coalitional games, Dependencies between players in Boolean games, Quantified coalition logic, Solving coalitional resource games, On the computational complexity of coalitional resource games, Dependencies Between Players in Boolean Games, A logical characterisation of qualitative coalitional games

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item