Cooperative Boolean games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cooperative Boolean games

Full text

Pdf (377 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2 table of contents

Estoril, Portugal

SESSION: Economic paradigms table of contents

Pages 1015-1022

Year of Publication: 2008

ISBN:978-0-9817381-1-6

Authors

Paul E. Dunne	University of Liverpool, Liverpool, UK
Wiebe van der Hoek	University of Liverpool, Liverpool, UK
Sarit Kraus	Bar-Ilan University, Ramat Gan, Israel
Michael Wooldridge	Bar-Ilan University, Ramat Gan, Israel

Sponsors

AAAI : Association for the Advancement of Artifical Intelligence
ACM: Association for Computing Machinery

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 43, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

We present and formally investigate Cooperative Boolean Games, a new, natural family of coalitional games that are both compact and expressive. In such a game, an agent's primary aim is to achieve its individual goal, which is represented as a propositional logic formula over some set of Boolean variables. Each agent is assumed to exercise unique control over some subset of the overall set of Boolean variables, and the set of valuations for these variables corresponds to the set of actions the agent can take. However, the actions available to an agent are assumed to have some cost, and an agent's secondary aim is to minimise its costs. Typically, an agent must cooperate with others because it does not have sufficient control to ensure its goal is satisfied. However, the desire to minimise costs leads to preferences over possible coalitions, and hence to strategic behaviour. Following an introduction to the formal framework of Cooperative Boolean Games, we investigate solution concepts of the core and stable sets for them. In each case, we characterise the complexity of the associated solution concept, and discuss the surrounding issues. Finally, we present a bargaining protocol for cooperation in Boolean games, and characterise the strategies in equilibrium for this protocol.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	E. Bonzon. Modélisation des interactions entre agents rationnels: les jeux booléens. PhD thesis, Université Paul Sabatier, Toulouse, 2007.
	2	E. Bonzon, M. Lagasquie, J. Lang, and B. Zanuttini. Boolean games revisited. In Proceedings of the Seventeenth European Conference on Artificial Intelligence (ECAI-2006), Riva del Garda, Italy, 2006.
	3	Vincent Conitzer , Tuomas Sandholm, Complexity of constructing solutions in the core based on synergies among coalitions, Artificial Intelligence, v.170 n.6, p.607-619, May 2006 [doi>10.1016/j.artint.2006.01.005]
	4	Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
	5	P. Harrenstein. Logic in Conflict. PhD thesis, Utrecht University, 2004.
	6	Paul Harrenstein , Wiebe van der Hoek , John-Jules Meyer , Cees Witteveen, Boolean games, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
	7	Wiebe van der Hoek , Michael Wooldridge, On the logic of cooperation and propositional control, Artificial Intelligence, v.164 n.1-2, p.81-119, May 2005 [doi>10.1016/j.artint.2005.01.003]
	8	Samuel Ieong , Yoav Shoham, Marginal contribution nets: a compact representation scheme for coalitional games, Proceedings of the 6th ACM conference on Electronic commerce, p.193-202, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064030]
	9	Sarit Kraus, Strategic negotiation in multiagent environments, MIT Press, Cambridge, MA, 2001
	10	J. Neumann and O. Morgenstern. Theory of Games and Economic Behaviour. Princeton University Press: Princeton, NJ, 1944.
	11	M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press: Cambridge, MA, 1994.
	12	C. H. Papadimitriou. Computational Complexity. Addison-Wesley: Reading, MA, 1994.
	13	Jeffrey S. Rosenschein , Gilad Zlotkin, Rules of encounter: designing conventions for automated negotiation among computers, MIT Press, Cambridge, MA, 1994
	14	Tuomas Sandholm , Kate Larson , Martin Andersson , Onn Shehory , Fernando Tohmé, Coalition structure generation with worst case guarantees, Artificial Intelligence, v.111 n.1-2, p.209-238, July 1999 [doi>10.1016/S0004-3702(99)00036-3]
	15	Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]
	16	Michael Wooldridge , Paul E. Dunne, On the computational complexity of qualitative coalitional games, Artificial Intelligence, v.158 n.1, p.27-73, September 2004 [doi>10.1016/j.artint.2004.04.002]
	17	Michael Wooldridge , Paul E. Dunne, On the computational complexity of coalitional resource games, Artificial Intelligence, v.170 n.10, p.835-871, July 2006 [doi>10.1016/j.artint.2006.03.003]