Suche nach Personen

plus im Publikationsserver
plus bei Google Scholar

Bibliografische Daten exportieren
 

Simple Games versus Weighted Voting Games

URN zum Zitieren der Version auf EPub Bayreuth: urn:nbn:de:bvb:703-epub-3708-9

Titelangaben

Hof, Frits ; Kern, Walter ; Kurz, Sascha ; Paulusma, Daniël:
Simple Games versus Weighted Voting Games.
Bayreuth , 2018 . - 13 S.

Volltext

[thumbnail of alpha-arxiv.pdf]
Format: PDF
Name: alpha-arxiv.pdf
Version: Veröffentlichte Version
Verfügbar mit der Lizenz Creative Commons BY 4.0: Namensnennung
Download (482kB)

Abstract

A simple game (N,v) is given by a set N of n players and a partition of 2^N 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 alpha= \min_{p>=0}\max_{W' in W,L' in L} p(L')/p(W') <1 are known as weighted voting games. Freixas and Kurz (IJGT, 2014) conjectured that alpha<=n/4 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 alpha<=2n/7 for every simple game (N,v). 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
Zusätzliche Informationen (öffentlich sichtbar): erschienen in:
Deng, Xiaotie (Hrsg.): Algorithmic Game Theory : Proceedings. - Cham : Springer , 2018 . - S. 69-81 . - (Lecture Notes in Computer Science ; 11059 )
DOI: https://doi.org/10.1007/978-3-319-99660-8_7
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-3708-9
Eingestellt am: 09 Mai 2018 05:22
Letzte Änderung: 14 Mai 2021 07:35
URI: https://epub.uni-bayreuth.de/id/eprint/3708

Downloads

Downloads pro Monat im letzten Jahr