On max-min linear inequalities and Coalitional Resource Games with sharable resources |
| |
Authors: | Katar?´ na Cechlá rová |
| |
Affiliation: | Institute of Mathematics, Faculty of Science, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovakia |
| |
Abstract: | In a Coalitional Resource Game (CRG for brief), agents form coalitions to pool their resources in order to achieve certain goals, requiring the expenditure of these resources. A particular coalition is said to be successful, if the common resources of its members enable to achieve a set of goals that satisfies all members of the coalition. It is known that when resources are consumable it is NP-complete to decide whether a given coalition is successful. In this paper, we show a connection of CRGs with sharable resources and max-min linear systems of inequalities. This correspondence leads to polynomial algorithms for checking whether a given CRG admits a successful coalition and for several other problems whose counterparts for CRGs with consumable resources are hard. On the other hand, we prove that some problems concerning the structure of successful coalitions are hard also in the case of sharable resources. |
| |
Keywords: | 91B68 68Q25 |
本文献已被 ScienceDirect 等数据库收录! |
|