Research output per year
Research output per year
Frits Hof, Walter Kern, Sascha Kurz, Kanstantsin Pashkovich, Daniël Paulusma*
Research output: Contribution to journal › Article › Academic › peer-review
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 |
---|---|
Pages (from-to) | 609–621 |
Number of pages | 13 |
Journal | Social choice and welfare |
Volume | 54 |
Issue number | 4 |
Early online date | 28 Sept 2019 |
DOIs | |
Publication status | Published - 1 Apr 2020 |
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
Research output: Working paper › Preprint › Academic
Research output: Working paper › Preprint › Academic