Simple Games versus Weighted Voting Games: Bounding the Critical Threshold Value
share
A simple game (N,v) is given by a set N of n players and a partition of 2^N into a set L of losing coalitions L with value v(L)=0 that is closed under taking subsets and a set W of winning coalitions W with v(W)=1. Simple games with α= _p≥ 0_W∈ W, L∈ Lp(L)/p(W)<1 are exactly the weighted voting games. We show that α≤1/4n for every simple game (N,v), confirming the conjecture of Freixas and Kurz (IJGT, 2014). For complete simple games, Freixas and Kurz conjectured that α=O(√(n)). We prove this conjecture up to a n factor. We also prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size 2, computing α is -hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if α<a is polynomial-time solvable for every fixed a>0.
READ FULL TEXT