Simple games versus weighted voting games: bounding the critical threshold value

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 value v(W) = 1. We let α=minp⩾0,p≠0maxW∈W,L∈Lp(L)p(W). It is known that the subclass of simple games with α< 1 coincides with the class of weighted voting games. Hence, α can be seen as a measure of the distance between a simple game and the class of weighted voting games. We prove that α⩽14n holds for every simple game (N, v), confirming the conjecture of Freixas and Kurz (Int J Game Theory 43:659–692, 2014). For complete simple games, Freixas and Kurz conjectured that α=O(n). We also prove this conjecture, up to an ln n factor. Moreover, we prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size 2, the problem of computing α is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Finally, we show that for every graphic simple game, deciding if α< α is polynomial-time solvable for every fixed α> 0.