The Banzhaf index, Shapley-Shubik index and other voting power indices measure the importance of a player in a coalitional game. We consider a simple coalitional game called the spanning connectivity game (SCG) based on an undirected, unweighted multigraph, where edges are players. We examine the computational complexity of computing the voting power indices of edges in the SCG. It is shown that computing Banzhaf values and Shapley-Shubik indices is #P-complete for SCGs. Interestingly, Holler indices and Deegan-Packel indices can be computed in polynomial time. Among other results, it is proved that Banzhaf indices can be computed in polynomial time for graphs with bounded treewidth. It is also shown that for any reasonable representation of a simple game, a polynomial time algorithm to compute the Shapley-Shubik indices implies a polynomial time algorithm to compute the Banzhaf indices. As a corollary, computing the Shapley value is #P-complete for simple games represented by the set of minimal winning coalitions, Threshold Network Flow Games, Vertex Connectivity Games and Coalitional Skill Games.
The study of cooperative games in combinatorial domains is widespread in operations research @cite_22 @cite_14 . Spanning network games have been examined previously @cite_20 @cite_1 but they are treated differently, with weighted graphs and as players (not , as here). The SCG is related to the all-terminal reliability model, a non-game-theoretic model that is relevant in broadcasting @cite_7 @cite_8 . Whereas the reliability of a network concerns the overall probability of a network being connected, this paper concentrates on resource allocation to the edges. A game-theoretic approach can provide fair and stable outcomes in a strategic setting.
@cite_14 @cite_22 @cite_7 @cite_8 @cite_1 @cite_20
1562095019 1999587457 2115826669 1991536882 1969364062
Preface. 1. Cooperative Games and Solution Concepts. 2. Linear Programming Games. 3. Assignment Games and Permutation Games. 4. Sequencing Games and Generalizations. 5. Travelling Salesman Games and Routing Games. 6. Minimum Cost Spanning Tree Games. 7. Location Games. References. Index. This paper surveys the research area of cooperative games associated with several types of operations research problems in which various decision makers (players) are involved.Cooperating players not only face a joint optimisation problem in trying, e.g., to minimise total joint costs, but also face an additional allocation problem in how to distribute these joint costs back to the individual players.This interplay between optimisation and allocation is the main subject of the area of operations research games.It is surveyed on the basis of a distinction between the nature of the underlying optimisation problem: connection, routing, scheduling, production and inventory. The class of @math -complete problems is a class of computationally eqivalent counting problems (defined by the author in a previous paper) that are at least as difficult as the @math -complete problems. Here we show, for a large number of natural counting problems for which there was no previous indication of intractability, that they belong to this class. The technique used is that of polynomial time reduction with oracles via translations that are of algebraic or arithmetic nature. This paper presents an overview of results related to the computational complexity of network reliability analysis problems. Network reliability analysis problems deal with the determination of reliability measures for stochastic networks. We show how these problems are related to the more familiar computational network problems of recognizing certain subnetworks, finding optimal subnetworks, and counting certain subnetworks. We use these relationships to show that the k-terminal, the 2-terminal, and the all-terminal network reliability analysis problems are at least as hard as the renowned set of computationally difficult problems, NP-Complete. Finally, we discuss the impact of these results on how one should approach problem solving in this area. Spanning network games, which are a generalization of minimum cost spanning tree games, were introduced by Granot and Maschler (1991), who showed that these games are always monotonic. In this paper a subclass of spanning network games is introduced, namely simplex games, and it is shown that every monotonic game is a simplex game. Hence, the class of spanning network games coincides with the class of monotonic games.