### Abstract

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.

Original language | English |
---|---|

Number of pages | 13 |

Journal | Social choice and welfare |

Early online date | 28 Sep 2019 |

DOIs | |

Publication status | E-pub ahead of print/First online - 28 Sep 2019 |

### Fingerprint

### Cite this

*Social choice and welfare*. https://doi.org/10.1007/s00355-019-01221-6