F. Hof
Simple games versus weighted voting games: bounding the critical threshold value
Hof, F.; Kern, W.; Kurz, S.; Pashkovich, K.; Paulusma, D.
Authors
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 value v(W) = 1. We let = minp>0;p6=0 maxW2W;L2L p(L) p(W) . It is known that the subclass of simple games with < 1 coincides with the class of weighted voting games. Hence, can be seen as a measure of the distance between a simple game and the class of weighted voting games. We prove that 6 1 4n holds for every simple game (N; v), confirming the conjecture of Freixas and Kurz (IJGT, 2014). For complete simple games, Freixas and Kurz conjectured that = O( p n). We also prove this conjecture, up to an ln n factor. Moreover, we prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size 2, the problem of computing is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Finally, we show that for every graphic simple game, deciding if < 0 is polynomial-time solvable for every fixed 0 > 0.
Journal Article Type | Article |
---|---|
Acceptance Date | Sep 23, 2019 |
Online Publication Date | Sep 28, 2019 |
Publication Date | Apr 30, 2020 |
Deposit Date | Sep 21, 2019 |
Publicly Available Date | Sep 28, 2020 |
Journal | Social Choice and Welfare |
Print ISSN | 0176-1714 |
Electronic ISSN | 1432-217X |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 54 |
Issue | 4 |
Pages | 609-621 |
DOI | https://doi.org/10.1007/s00355-019-01221-6 |
Public URL | https://durham-repository.worktribe.com/output/1291092 |
Files
Accepted Journal Article
(484 Kb)
PDF
Copyright Statement
This is a post-peer-review, pre-copyedit version of an article published in Social Choice and Welfare. The final authenticated version is available online at: https://doi.org/10.1007/s00355-019-01221-6
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