Research output per year
Research output per year
Frits Hof, Walter Kern, Sascha Kurz, Daniël Paulusma*
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
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 |
Subtitle of host publication | 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings |
Editors | Xiaotie Deng |
Place of Publication | Cham |
Publisher | Springer |
Pages | 69-81 |
Number of pages | 13 |
ISBN (Electronic) | 978-3-319-99660-8 |
ISBN (Print) | 978-3-319-99659-2 |
DOIs | |
Publication status | Published - 2018 |
Event | 11th International Symposium on Algorithmic Game Theory, SAGT 2018 - Beijing, China Duration: 11 Sept 2018 → 13 Sept 2018 Conference number: 11 |
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 11059 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
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 |
Research output: Contribution to journal › Article › Academic › peer-review
Research output: Working paper › Preprint › Academic
Research output: Working paper › Preprint › Academic