Simple games versus weighted voting games

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

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, September). Simple games versus weighted voting games. Presented at 11th International Symposium on Algorithmic Game Theory (SAGT 2018)., Beijing, China

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 11th International Symposium on Algorithmic Game Theory (SAGT 2018).
• 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: Jul 31, 2018
• Print ISSN: 0302-9743
• 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