## Title data

Hof, Frits ; Kern, Walter ; Kurz, Sascha ; Paulusma, Daniël:

**Simple Games versus Weighted Voting Games.**

*In:* Deng, Xiaotie
(ed.):
Algorithmic Game Theory : Proceedings. -
Cham
: Springer
,
2018
. - pp. 69-81
. - (Lecture Notes in Computer Science
; 11059
)

ISBN 978-3-319-99659-2

DOI: https://doi.org/10.1007/978-3-319-99660-8_7

## Abstract in another language

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 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 book |
---|---|

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 > Chair Mathematics in Economy Profile Fields > Emerging Fields > Governance and Responsibility Faculties Faculties > Faculty of Mathematics, Physics und Computer Science Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics Profile Fields Profile Fields > Emerging Fields |

Result of work at the UBT: | Yes |

DDC Subjects: | 000 Computer Science, information, general works > 004 Computer science 500 Science > 510 Mathematics |

Date Deposited: | 30 Aug 2018 06:29 |

Last Modified: | 30 Aug 2018 06:29 |

URI: | https://eref.uni-bayreuth.de/id/eprint/45634 |