Titlebar

Bibliografische Daten exportieren
Literatur vom gleichen Autor
plus im Publikationsserver
plus bei Google Scholar

 

Simple games versus weighted voting games: Bounding the critical threshold value

URN zum Zitieren dieses Dokuments: urn:nbn:de:bvb:703-epub-3882-4

Titelangaben

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.

Volltext

[img] PDF
critical_threshold_arxiv.pdf - Veröffentlichte Version
Available under License Creative Commons BY 4.0: Namensnennung .

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.

Weitere Angaben

Publikationsform: Preprint, Postprint, Working paper, Diskussionspapier
Keywords: simple game; weighted voting game; graphic simple game; complete simple game
Fachklassifikationen: Mathematics Subject Classification Code: 91B12 94C10
Themengebiete aus DDC: 000 Informatik,Informationswissenschaft, allgemeine Werke > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Institutionen der Universität: Fakultäten > Fakultät für Mathematik, Physik und Informatik
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut > Lehrstuhl Wirtschaftsmathematik
Profilfelder > Emerging Fields > Governance and Responsibility
Fakultäten
Profilfelder
Profilfelder > Emerging Fields
Sprache: Englisch
Titel an der UBT entstanden: Ja
URN: urn:nbn:de:bvb:703-epub-3882-4
Eingestellt am: 23 Okt 2018 06:16
Letzte Änderung: 23 Okt 2018 06:16
URI: https://epub.uni-bayreuth.de/id/eprint/3882

Downloads

Downloads pro Monat im letzten Jahr