In this paper, we address the selfish bin covering problem, which is greatly related both to the bin covering problem, and to the weighted majority game. What we are mainly concerned with is how much the lack of central coordination harms social welfare. Besides the standard PoA and PoS, which are based on Nash equilibrium, we also take into account the strong Nash equilibrium, and several new equilibrium concepts. For each equilibrium concept, the corresponding PoA and PoS are given, and the problems of computing an arbitrary equilibrium, as well as approximating the best one, are also considered.
Matsui and Matsui ( @cite_4 @cite_9 ) prove that all the problems of computing the Shapley-Shubik indices, the Banzhaf indices and the Deegan-Packel indices in WMGs are NP-hard, and there are pseudo-polynomial time dynamic programming algorithms for them. Cao and Yang ( @cite_11 ) show that computing the Holler-Packel index is also NP-hard. Deng and Papadimitriou ( @cite_5 ) prove that it is #P-complete to compute the Shapley-Shubik index. Matsui and Matsui ( @cite_9 ) observe that Deng and Papadimitriou's proof can be easily carried over to the problem of computing the Banzhaf index.
@cite_5 @cite_9 @cite_4 @cite_11
2046116913 2038127015 2144872768 2005524240
We study from a complexity theoretic standpoint the various solution concepts arising in cooperative game theory. We use as a vehicle for this study a game in which the players are nodes of a graph with weights on the edges, and the value of a coalition is determined by the total weight of the edges contained in it. The Shapley value is always easy to compute. The core is easy to characterize when the game is convex, and is intractable (NP-complete) otherwise. Similar results are shown for the kernel, the nucleolus, the e-core, and the bargaining set. As for the von Neumann-Morgenstern solution, we point out that its existence may not even be decidable. Many of these results generalize to the case in which the game is presented by a hypergraph with edges of size k > 2. In this paper, we prove that both problems for calculating the Banzhaf power index and the Shapley-Shubik power index for weighted majority games are NP-complete. For measuring an individual's voting power of a voting game, some power indices are proposed. In this paper, we discuss the problems for calculating the Shapley-Shubik index, the Banzhaf index and the Deegan-Packel index of weighted majority games. In this paper, we introduce a simple coalition formation game in the environment of bidding, which is a special case of the weighted majority game (WMG), and is named the weighted simple-majority game (WSMG). In WSMG, payoff is allocated to the winners proportional to the players’ powers, which can be measured in various ways. We define a new kind of stability: the counteraction-stability (C-stability), where any potential deviating players will confront counteractions of the other players. We show that C-stable coalition structures in WSMG always contains a minimal winning coalition of minimum total power. For the variant where powers are measured directly by their weights, we show that it is NP-hard to find a C-stable coalition structure and design a pseudo-polynomial time algorithm. Sensitivity analysis for this variant, which shows many interesting properties, is also done. We also prove that it is NP-hard to compute the Holler-Packel indices in WSMGs, and hence in WMGs as well.