Title data
Hof, Frits ; Kern, Walter ; Kurz, Sascha ; Paulusma, Daniël:
Simple Games versus Weighted Voting Games.
Bayreuth
,
2018
.  13 S.


Download (482kB)

Abstract
A simple game (N,v) is given by a set N of n players and a partition of 2^N 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 v(W')=1. Simple games with alpha= \min_{p>=0}\max_{W' in W,L' in L} p(L')/p(W') <1 are known as weighted voting games. Freixas and Kurz (IJGT, 2014) conjectured that alpha<=n/4 for every simple game (N,v). We confirm this conjecture for two complementary cases, namely when all minimal winning coalitions have size 3 and when no minimal winning coalition has size 3. As a general bound we prove that alpha<=2n/7 for every simple game (N,v). 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 

Additional notes (visible to public):  erschienen in:
Deng, Xiaotie (Hrsg.): Algorithmic Game Theory : Proceedings.  Cham : Springer , 2018 .  S. 6981 .  (Lecture Notes in Computer Science ; 11059 ) DOI: https://doi.org/10.1007/9783319996608_7 
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:703epub37089 
Date Deposited:  09 May 2018 05:22 
Last Modified:  14 May 2021 07:35 
URI:  https://epub.unibayreuth.de/id/eprint/3708 