A Logic-Based Representation for Coalitional Games with Externalities

We consider the issue of representing coalitional games in multi-agent systems that exhibit externalities from coalition formation, i. e. , systems in which the gain from forming a coalition may be affected by the formation of other co-existing coalitions. Althoughexternalities play a key role in many real-life situations, very littleattention has been given to this issue in the multi-agent system literature, especially with regard to the computational aspects involved. To this end, we propose a new representation which, in the spiritof Ieong and Shoham, is based on Boolean expressions. Theidea behind our representation is to construct much richer expressions that allow for capturing externalities induced upon coalitions. We show that the new representation is fully expressive, at least asconcise as the conventional partition function game representationand, for many games, exponentially more concise. We evaluate theefficiency of our new representation by considering the problem ofcomputing the Extended and Generalized Shapley value, a powerful extension of the conventional Shapley value to games withexternalities. We show that by using our new representation, theExtended and Generalized Shapley value, which has not been studied in the computer science literature to date, can be computed intime linear in the size of the input.

Authors

• Tomasz Michalak University of Warsaw IDEAS NCBR
• Dorota Marciniak
• Marcin Szamotulski
• Talal Rahwan
• Michael Wooldridge University of Oxford
• Peter McBurney
• Nicholas R. Jennings

Keywords

No keywords are indexed for this paper.