Title data
Hof, Frits ; Kern, Walter ; Kurz, Sascha ; Pashkovich, Kanstantsin ; Paulusma, Daniël:
Simple games versus weighted voting games: Bounding the critical threshold value.
Bayreuth
,
2018
.  10 S.


Download (335kB)

Abstract
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 NPhard, but polynomialtime solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if alpha<a is polynomialtime solvable for every fixed a>0.
Further data
Item Type:  Preprint, postprint 

Keywords:  simple game; weighted voting game; graphic simple game; complete simple game 
Subject classification:  Mathematics Subject Classification Code: 91B12 94C10 
DDC Subjects:  000 Computer Science, information, general works > 004 Computer science 500 Science > 510 Mathematics 
Institutions of the University:  Faculties > Faculty of Mathematics, Physics und Computer Science 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 > Emerging Fields > Governance and Responsibility Faculties Profile Fields Profile Fields > Emerging Fields 
Language:  English 
Originates at UBT:  Yes 
URN:  urn:nbn:de:bvb:703epub38824 
Date Deposited:  23 Oct 2018 06:16 
Last Modified:  14 Mar 2019 14:26 
URI:  https://epub.unibayreuth.de/id/eprint/3882 