Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

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.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(473Kb)
Status:Peer-reviewed
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

Export:
Export
Look up in GoogleScholar