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.

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

VL - 54

SP - 609

EP - 621

JO - Social choice and welfare

JF - Social choice and welfare

SN - 0176-1714

IS - 4

ER -