F. Hof
Simple games versus weighted voting games
Hof, F.; Kern, W.; Kurz, S.; Paulusma, D.
Authors
Contributors
Xiaotie Deng
Editor
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 .
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 |
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 |
Files
Accepted Conference Proceeding
(447 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/978-3-319-99660-8_7.
You might also like
Classifying Subset Feedback Vertex Set for H-free graphs
(2022)
Presentation / Conference Contribution
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
An algorithmic framework for locally constrained homomorphisms
(2022)
Presentation / Conference Contribution
The Complexity of L(p,q)-Edge-Labelling
(2022)
Presentation / Conference Contribution
Computing Balanced Solutions for Large International Kidney Exchange Schemes
(2022)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search