Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

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

Title data

Hof, Frits ; Kern, Walter ; Kurz, Sascha ; Pashkovich, Kanstantsin ; Paulusma, Daniël:
Simple games versus weighted voting games : Bounding the critical threshold value.
In: Social Choice and Welfare. Vol. 54 (2020) Issue 4 . - pp. 609-621.
ISSN 1432-217X
DOI: https://doi.org/10.1007/s00355-019-01221-6

Abstract in another language

A simple game (N,v) is given by a set N of $n$ players and a partition of the set of subsets of N into a set of losing coalitions L with value v(L)=0 that is closed under taking subsets and a set W of winning coalitions with v(W)=1. Simple games with alpha= min _{p>=0} max_{W' in W, L' in L} p(L')/p(W')<1 are exactly the weighted voting games. We show that alpha<=n/4 for every simple game (N,v), confirming the conjecture of Freixas and Kurz (IJGT, 2014). For complete simple games, Freixas and Kurz conjectured that alpha=O(sqrt(n))$. We prove this conjecture up to a (ln n) factor. We also prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size 2, computing alpha is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if alpha<a is polynomial-time solvable for every fixed a>0.

Further data

Item Type: Article in a journal
Refereed: Yes
Keywords: simple game; weighted voting game; graphic simple game; complete simple game
Subject classification: Mathematics Subject Classification Code: 91B12 94C10
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics
Profile Fields
Profile Fields > Emerging Fields
Profile Fields > Emerging Fields > Governance and Responsibility
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
500 Science > 510 Mathematics
Date Deposited: 08 Apr 2020 08:45
Last Modified: 08 Apr 2020 08:45
URI: https://eref.uni-bayreuth.de/id/eprint/54870