TY - JOUR
T1 - Simple games versus weighted voting games
T2 - bounding the critical threshold value
AU - Hof, Frits
AU - Kern, Walter
AU - Kurz, Sascha
AU - Pashkovich, Kanstantsin
AU - Paulusma, Daniël
PY - 2020/4/1
Y1 - 2020/4/1
N2 - 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.
AB - 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.
KW - 22/2 OA procedure
UR - http://www.scopus.com/inward/record.url?scp=85074011711&partnerID=8YFLogxK
U2 - 10.1007/s00355-019-01221-6
DO - 10.1007/s00355-019-01221-6
M3 - Article
AN - SCOPUS:85074011711
SN - 0176-1714
VL - 54
SP - 609
EP - 621
JO - Social choice and welfare
JF - Social choice and welfare
IS - 4
ER -