Advertisement
Published in:
2018 | OriginalPaper | Chapter
Simple Games Versus Weighted Voting Games
Authors : Frits Hof, Walter Kern, Sascha Kurz, Daniël Paulusma
Published in: Algorithmic Game Theory
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 \(v(W)=1\). Simple games with \(\alpha = \min _{p\ge 0}\max _{W\in \mathcal{W},L\in \mathcal{L}} \frac{p(L)}{p(W)}<1\) are exactly the weighted voting games. Freixas and Kurz (IJGT, 2014) conjectured that \(\alpha \le \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 \le \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\).