Computing Cooperative Solution Concepts in Coalitional Skill Games

Yoram Bachrach, David Parkes, and Jeffrey S. Rosenschein

Abstract

We consider a simple model of cooperation among agents called Coalitional Skill Games (CSGs). This is a restricted form of coalitional games, where each agent has a set of skills that are required to complete various tasks. Each task requires a set of skills in order to be completed, and a coalition can accomplish the task only if the coalition's agents cover the set of required skills for the task. The gain for a coalition depends only on the subset of tasks it can complete. We consider the computational complexity of several problems in CSGs, such as testing if an agent is a dummy or veto agent, computing the core and core-related solution concepts, and computing power indices such as the Shapley value and Banzhaf power index.

Details

Publication typeArticle
Published inArtificial Intelligence
> Publications > Computing Cooperative Solution Concepts in Coalitional Skill Games