Dependency in Cooperative Boolean Games

Luigi Sauro 1 Serena Villata 2
2 WIMMICS - Web-Instrumented Man-Machine Interactions, Communities and Semantics
CRISAM - Inria Sophia Antipolis - Méditerranée , SPARKS - Scalable and Pervasive softwARe and Knowledge Systems
Abstract : Cooperative boolean games (CBG) are a family of coalitional games where agents may depend on each other for the satisfaction of their personal goals. In Dunne et al. (2008, Cooperative Boolean games. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), 1015-1022), the authors define as solution concept the notion of core showing that several decision problems, such as core-emptiness, are Formula-complete. In this work, we investigate how to improve the computation of the core. In particular, we introduce two different types of dependence networks, abstract dependence networks and refined dependence networks, that are used to define the notion of stable coalitions and Δ-reduction, respectively. Stable coalitions enable to focus on a subset of the agents and use results to determinate the core of the whole game. Δ-reduction prunes the search space by returning a set of actions that are not admissible to be executed. We present an algorithm based on stable coalitions and a Δ-reduction implemented in Prolog and experimental results that show how they effectively improve the computation of the core.
Type de document :
Article dans une revue
Journal of Logic and Computation, Oxford University Press (OUP), 2013, <10.1093/logcom/exr030>


https://hal.inria.fr/hal-00907869
Contributeur : Serena Villata <>
Soumis le : jeudi 21 novembre 2013 - 22:46:47
Dernière modification le : lundi 5 octobre 2015 - 17:00:46

Identifiants

Collections

Citation

Luigi Sauro, Serena Villata. Dependency in Cooperative Boolean Games. Journal of Logic and Computation, Oxford University Press (OUP), 2013, <10.1093/logcom/exr030>. <hal-00907869>

Partager

Métriques

Consultations de la notice

91