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

Abstract

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 value $v(W)=1$. We let $\alpha = \min _{p\geqslant {\varvec{0}}, p\ne {\varvec{0}}}\max _{W\in \mathcal{W}, L\in \mathcal{L}} \frac{p(L)}{p(W)}$. It is known that the subclass of simple games with $\alpha <1$ coincides with the class of weighted voting games. Hence, $\alpha$ can be seen as a measure of the distance between a simple game and the class of weighted voting games. We prove that $\alpha \leqslant \frac{1}{4}n$ 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 $\alpha =O(\sqrt{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 $\alpha$ is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Finally, we show that for every graphic simple game, deciding if $\alpha <\alpha _0$ is polynomial-time solvable for every fixed $\alpha _0>0$.