in the repository
Title data
Hof, Frits ; Kern, Walter ; Kurz, Sascha ; Pashkovich, Kanstantsin ; Paulusma, Daniël:
Simple games versus weighted voting games: Bounding the critical threshold value.
Bayreuth
,
2018
. - 10 S.
![[thumbnail of critical_threshold_arxiv.pdf]](https://epub.uni-bayreuth.de/style/images/fileicons/application_pdf.png) |
|
||||||||
|
Download (335kB)
|
Abstract
A simple game (N,v) is given by a set N of $n$ players and a partition of the set of subsets of N into a set of losing coalitions L with value v(L)=0 that is closed under taking subsets and a set W of winning coalitions with v(W)=1. Simple games with alpha= min _{p>=0} max_{W' in W, L' in L} p(L')/p(W')<1 are exactly the weighted voting games. We show that alpha<=n/4 for every simple game (N,v), confirming the conjecture of Freixas and Kurz (IJGT, 2014). For complete simple games, Freixas and Kurz conjectured that alpha=O(sqrt(n))$. 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 alpha is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if alpha<a is polynomial-time solvable for every fixed a>0.
Further data
| Item Type: | Preprint, postprint |
|---|---|
| Additional notes (visible to public): | erschienen in:
Social Choice and Welfare. Bd. 54 (2020) Heft 4 . - S. 609-621. DOI: https://doi.org/10.1007/s00355-019-01221-6 und in: In: Deng, Xiaotie (Hrsg.): Algorithmic Game Theory : Proceedings. - Cham : Springer , 2018 . - S. 69-81 . - (Lecture Notes in Computer Science ; 11059 ) ISBN 978-3-319-99659-2 DOI: https://doi.org/10.1007/978-3-319-99660-8_7 |
| Keywords: | simple game; weighted voting game; graphic simple game; complete simple game |
| Subject classification: | Mathematics Subject Classification Code: 91B12 94C10 |
| DDC Subjects: | 000 Computer Science, information, general works > 004 Computer science 500 Science > 510 Mathematics |
| Institutions of the University: | Faculties > Faculty of Mathematics, Physics und Computer Science Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics Profile Fields > Emerging Fields > Governance and Responsibility Faculties Profile Fields Profile Fields > Emerging Fields |
| Language: | English |
| Originates at UBT: | Yes |
| URN: | urn:nbn:de:bvb:703-epub-3882-4 |
| Date Deposited: | 23 Oct 2018 06:16 |
| Last Modified: | 12 May 2021 10:35 |
| URI: | https://epub.uni-bayreuth.de/id/eprint/3882 |
Download Statistics