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 (Formula Presented) are exactly the weighted voting games. Freixas and Kurz (IJGT, 2014) conjectured that (Formula Presented) 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 (Formula Presented) for every simple game (N, v). For complete simple games, Freixas and Kurz conjectured that (Formula Presented). 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 α 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.
Original language | English |
---|---|
Title of host publication | Algorithmic Game Theory - 11th International Symposium, SAGT 2018, Proceedings |
Editors | Xiaotie Deng |
Publisher | Springer |
Pages | 69-81 |
Number of pages | 13 |
ISBN (Print) | 9783319996592 |
DOIs | |
Publication status | Published - 2018 |
Event | 11th International Symposium on Algorithmic Game Theory, SAGT 2018 - Beijing, China Duration: 11 Sep 2018 → 13 Sep 2018 Conference number: 11 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 11059 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 11th International Symposium on Algorithmic Game Theory, SAGT 2018 |
---|---|
Abbreviated title | SAGT 2018 |
Country/Territory | China |
City | Beijing |
Period | 11/09/18 → 13/09/18 |