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

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

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