×

On max-min linear inequalities and coalitional resource games with sharable resources. (English) Zbl 1187.91013

Summary: 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.

MSC:

91A12 Cooperative games
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baccelli, F. L.; Cohen, G.; Olsder, G. J.; Quadrat, J. P., Synchronization and Linearity. Synchronization and Linearity, An Algebra for Discrete Event Systems (1992), Wiley: Wiley Chichester · Zbl 0824.93003
[2] Butkovič, P.; Zimmermann, K., A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Discrete Appl. Math., 154, 437-446 (2006) · Zbl 1090.68119
[3] Cuninghame-Green, R. A.; Butkovič, P., The equation \(A \otimes x = B \otimes y\) over \((\{- \infty \} \cup R, \max, +) \}\), Theor. Comput. Sci., 293, 3-12 (2003) · Zbl 1021.65022
[4] Cuninghame-Green, R. A.; Zimmermann, K., Equation with residuated function, Comment. Math. Univ. Carolin., 42, 729-740 (2001) · Zbl 1068.93039
[5] De Schutter, B.; De Moor, B., A method to find all solutions of a system of multivariate polynomial equalities and inequalities in the max algebra, Discrete Event Dyn. Syst.: Theory Appl., 6, 2, 115-138 (1996) · Zbl 0855.93018
[6] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[7] von Neumann, J.; Morgenstern, O., Theory of Games and Economic Behavior (1944), Princeton University Press · Zbl 0063.05930
[8] Sanchez, E., Resolution of composite fuzzy relation equations, Inform. and Control, 30, 38-48 (1976) · Zbl 0326.02048
[9] Walkup, E. A.; Boriello, G., A general linear max-plus solution technique, (Gunawardena, J.; Atiyah, M. F.; Taylor, T., Idempotency, Proc. of the Workshop on Idempotency, Bristol, UK, October 1994 (1998), Cambridge University Press: Cambridge University Press Cambridge, UK)
[10] Wooldridge, M.; Dunne, P. E., On the computational complexity of coalitional resource games, Artificial Intelligence, 170, 835-871 (2006) · Zbl 1131.91011
[11] Zimmermann, K., Extremální algebra, Ekon. ústav ČSAV, Praha (1976), (in Czech)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.