Simple games versus weighted voting games

Frits Hof, Walter Kern, Sascha Kurz, Daniël Paulusma*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
1 Downloads (Pure)

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 (Formula Presented) are exactly the weighted voting games. Freixas and Kurz (IJGT, 2014) conjectured that (Formula Presented) 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 (Formula Presented) for every simple game (N, v). For complete simple games, Freixas and Kurz conjectured that (Formula Presented). 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 α is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if α > a is polynomial-time solvable for every fixed a<0.

Original languageEnglish
Title of host publicationAlgorithmic Game Theory
Subtitle of host publication11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings
EditorsXiaotie Deng
Place of PublicationCham
PublisherSpringer
Pages69-81
Number of pages13
ISBN (Electronic)978-3-319-99660-8
ISBN (Print)978-3-319-99659-2
DOIs
Publication statusPublished - 2018
Event11th International Symposium on Algorithmic Game Theory, SAGT 2018 - Beijing, China
Duration: 11 Sept 201813 Sept 2018
Conference number: 11

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11059
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Symposium on Algorithmic Game Theory, SAGT 2018
Abbreviated titleSAGT 2018
Country/TerritoryChina
CityBeijing
Period11/09/1813/09/18

Fingerprint

Dive into the research topics of 'Simple games versus weighted voting games'. Together they form a unique fingerprint.

Cite this