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 α = min_(p≥0) max_(w∈w, L∈L) (p(L))/(p(W)) < 1 are exactly the weighted voting games. Freixas and Kurz (IJGT, 2014) conjectured that α ≤ 1/4n for every simple game (N,v). We confirm this conjecture for two complementary cases, namely when all minimal winning coalitions have size 3 and when no minimal winning coalition has size 3. As a general bound we prove that α ≤ 2/7n for every simple game (N,v). For complete simple games, Freixas and Kurz conjectured that α = O(√n). We prove this conjecture up to a ln 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 NP-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.
展开▼
