Skip to main content

Research Repository

Advanced Search

Simple games versus weighted voting games

Hof, F.; Kern, W.; Kurz, S.; Paulusma, D.

Simple games versus weighted voting games Thumbnail


Authors

F. Hof

W. Kern

S. Kurz



Contributors

Xiaotie Deng
Editor

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 v(W)=1 . Simple games with α=minp≥0maxW∈W,L∈Lp(L)p(W)<1 are exactly the weighted voting games. Freixas and Kurz (IJGT, 2014) conjectured that α≤14n 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 α≤27n for every simple game (N, v). For complete simple games, Freixas and Kurz conjectured that α=O(n−−√) . We prove this conjecture up to a lnn factor. We also prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size 2, computing α is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if α0 .

Citation

Hof, F., Kern, W., Kurz, S., & Paulusma, D. (2018). Simple games versus weighted voting games. In X. Deng (Ed.), Algorithmic game theory : 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings (69-81). https://doi.org/10.1007/978-3-319-99660-8_7

Conference Name 11th International Symposium on Algorithmic Game Theory (SAGT 2018).
Conference Location Beijing, China
Start Date Sep 11, 2018
End Date Sep 13, 2018
Acceptance Date Jul 5, 2018
Online Publication Date Aug 27, 2018
Publication Date Aug 27, 2018
Deposit Date Jul 30, 2018
Publicly Available Date Mar 29, 2024
Pages 69-81
Series Title Lecture notes in computer science
Series Number 11059
Series ISSN 0302-9743,1611-3349
Book Title Algorithmic game theory : 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings.
ISBN 9783319996592
DOI https://doi.org/10.1007/978-3-319-99660-8_7
Public URL https://durham-repository.worktribe.com/output/1146252

Files





You might also like



Downloadable Citations