Skip to main content

Research Repository

Advanced Search

Simple games versus weighted voting games: bounding the critical threshold value

Hof, F.; Kern, W.; Kurz, S.; Pashkovich, K.; Paulusma, D.

Simple games versus weighted voting games: bounding the critical threshold value Thumbnail


Authors

F. Hof

W. Kern

S. Kurz

K. Pashkovich



Abstract

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.

Citation

Hof, F., Kern, W., Kurz, S., Pashkovich, K., & Paulusma, D. (2020). Simple games versus weighted voting games: bounding the critical threshold value. Social Choice and Welfare, 54(4), 609-621. https://doi.org/10.1007/s00355-019-01221-6

Journal Article Type Article
Acceptance Date Sep 23, 2019
Online Publication Date Sep 28, 2019
Publication Date Apr 30, 2020
Deposit Date Sep 21, 2019
Publicly Available Date Sep 28, 2020
Journal Social Choice and Welfare
Print ISSN 0176-1714
Electronic ISSN 1432-217X
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 54
Issue 4
Pages 609-621
DOI https://doi.org/10.1007/s00355-019-01221-6
Public URL https://durham-repository.worktribe.com/output/1291092

Files





You might also like



Downloadable Citations