Summary: A simple game \((N,v)\) is given by a set \(N\) of \(n\) players and a partition of \(2^N\) into a set \(\mathcal{L}\) of losing coalitions \(L\) with value \(v(L)=0\) that is closed under taking subsets and a set \(\mathcal{W}\) of winning coalitions \(W\) with \(v(W)=1\). Simple games with \(\alpha=\min_{p\geq 0}\max_{W\in\mathcal{W},L\in\mathcal{L}}\frac{p(L)}{p(W)}<1\) are exactly the weighted voting games. In [Int. J. Game Theory 43, No. 3, 659–692 (2014; Zbl 1304.91021)], J. Freixas and the third author conjectured that \(\alpha\leq\frac{1}{4}n\) 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 \(\alpha\leq\frac{2}{7}n\) for every simple game \((N,v)\). For complete simple games, Freixas and Kurz conjectured that \(\alpha=O(\sqrt{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 \(\alpha\) is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if \(\alpha<a\) is polynomial-time solvable for every fixed \(a>0\).
For the entire collection see [Zbl 1397.91007].