Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Simple games versus weighted voting games.

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).

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 α<a is polynomial-time solvable for every fixed a>0 .

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(437Kb)
Status:Peer-reviewed
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

Export:
Export
Look up in GoogleScholar