Hof, F. and Kern, W. and Kurz, S. and Pashkovich, K. and Paulusma, D. (2020) 'Simple games versus weighted voting games : bounding the critical threshold value.', Social choice and welfare., 54 (4). pp. 609-621.
A simple game (N; v) is given by a set N of n players and a partition of 2N 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;p6=0 maxW2W;L2L p(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 6 1 4n holds for every simple game (N; v), confirming the conjecture of Freixas and Kurz (IJGT, 2014). For complete simple games, Freixas and Kurz conjectured that = O( p 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 < 0 is polynomial-time solvable for every fixed 0 > 0.
|Full text:||(AM) Accepted Manuscript|
Download PDF (473Kb)
|Publisher Web site:||https://doi.org/10.1007/s00355-019-01221-6|
|Publisher statement:||This is a post-peer-review, pre-copyedit version of an article published in Social Choice and Welfare. The final authenticated version is available online at: https://doi.org/10.1007/s00355-019-01221-6|
|Date accepted:||23 September 2019|
|Date deposited:||25 September 2019|
|Date of first online publication:||28 September 2019|
|Date first made open access:||28 September 2020|
Save or Share this output
|Look up in GoogleScholar|