Hof, F. and Kern, W. and Kurz, S. and Paulusma, D. (2018) 'Simple games versus weighted voting games.', in Algorithmic game theory : 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings. Cham: Springer, pp. 69-81. Lecture notes in computer science. (11059).
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 α<a is polynomial-time solvable for every fixed a>0 .
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (437Kb)
|Publisher Web site:||https://doi.org/10.1007/978-3-319-99660-8_7|
|Publisher statement:||The final publication is available at Springer via https://doi.org/10.1007/978-3-319-99660-8_7.|
|Date accepted:||05 July 2018|
|Date deposited:||31 July 2018|
|Date of first online publication:||27 August 2018|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|