Note on the computational complexity of least core concepts for min-cost spanning tree games.
type: Item
instance of: scholarly article
title: Note on the computational complexity of least core concepts for min-cost spanning tree games.
zbMATH Open document ID: 1054.91010
author: U. Faigle
author: Walter Kern
author: Daniël Paulusma
published in: Mathematical Methods of Operations Research
publication date: 2000-01-01T00:00:00Z
full work available at URL: 6122.pdf
review text: A cooperative game is usually described by its characteristic function \(v(S)\) which assigns, to each possible coalition of players \(S\subseteq N\), the value that this coalition can guarantee if its participants act together. If they all act together, they gain \(v(N)\); the problem is how to allocate this amount between the participants, i.e., how to assign the value \(x_i\) to each participant \(i\in N\) so that \(\sum\limits_{i\in N} x_i=v(N)\). In some situations, there exist allocations for which for every coalition \(S\), the gained amount \(x(S)=\sum\limits_{i\in S} x_i\) is not smaller than \(v(S)\): \(x(S)\geq v(S)\); the set of all such allocations is called a core. For allocations from the core, no coalition \(S\) benefits from acting separately. In many games, however, the core is empty. In this case, it is desirable to select allocations for which the benefit of breaking the rules is the smallest, i.e., for which \(x(S)\geq v(S)-\varepsilon\cdot f(S)\) for all \(S\) -- for the smallest possible \(\varepsilon>0\) for which these inequalities are possible; the set of such allocations is called the \textit{least core}. We may want to choose \(f(S)=1\), in which case we bound the absolute difference \(v(S)-x(S)\); we may choose \(f(S)=v(S)\), in which case we bound the relative difference \((v(S)-x(S))/v(S)\); we may choose \(v(S)=| S| \), in which case we bound the difference per person. The authors show that even for simple games -- in which \(v(S)\) is the cost of the minimum spanning tree -- for each of these functions \(f(S)\), computing the least core is NP-hard. As a corollary, the authors prove that for such games, many other solution concepts also result in NP-hard problems.
Mathematics Subject Classification ID: 91A12
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 1972726
zbMATH Keywords: cooperative games
zbMATH Keywords: least core
zbMATH Keywords: NP-hard
zbMATH Keywords: nucleolus
reviewed by: Olga Kosheleva
MaRDI profile type: Publication
OpenAlex ID: W2165116885
DOI: 10.1007/S001860000059
description: scientific article; zbMATH DE number 1972726