| |
|
|
Abstract: Coalition formation is a popular topic studied in connection with multiagent systems. Recently, a new model of cooperation, called the Coalitional Resource Games (CRG for brief) has been introduced. In a CRG, agents wish to achieve certain goals that require expenditure of some resources. Agents form coalitions to pool their resources in order to be able to achieve a set of goals that satisfy all members of a coalition. When resources are consumable, many problems connected with CRGs are hard, e.g. Is a given coalition successful?, Is a given resource necessary for a coalition to be successful?, etc. In this paper we show a connection of CRGs with shared resources and 'max-min linear' systems of inequalities. This correspondence will enable us to derive polynomial algorithms for several problems whose counterparts for CRGs with consumable resources are hard. On the other hand, we prove that other problems are hard also in the case of shared resources. Contact the authors: katarina.cechlarova@upjs.sk Download PDF version of the preprint. |