Simple games versus weighted voting games

Frits Hof; Walter Kern; Sascha Kurz; Daniël Paulusma

doi:10.1007/978-3-319-99660-8_7

Simple games versus weighted voting games

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

^*Corresponding author for this work

Mathematics of Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 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 (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 language	English
Title of host publication	Algorithmic Game Theory
Subtitle of host publication	11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings
Editors	Xiaotie Deng
Place of Publication	Cham
Publisher	Springer
Pages	69-81
Number of pages	13
ISBN (Electronic)	978-3-319-99660-8
ISBN (Print)	978-3-319-99659-2
DOIs	https://doi.org/10.1007/978-3-319-99660-8_7
Publication status	Published - 2018
Event	11th International Symposium on Algorithmic Game Theory, SAGT 2018 - Beijing, China Duration: 11 Sept 2018 → 13 Sept 2018 Conference number: 11

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11059
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Symposium on Algorithmic Game Theory, SAGT 2018
Abbreviated title	SAGT 2018
Country/Territory	China
City	Beijing
Period	11/09/18 → 13/09/18

Access to Document

10.1007/978-3-319-99660-8_7

Cite this

@inproceedings{c931caddf59a4be78a113f08bb4067c5,

title = "Simple games versus weighted voting games",

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.",

author = "Frits Hof and Walter Kern and Sascha Kurz and Dani{\"e}l Paulusma",

year = "2018",

doi = "10.1007/978-3-319-99660-8_7",

language = "English",

isbn = "978-3-319-99659-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "69--81",

editor = "Xiaotie Deng",

booktitle = "Algorithmic Game Theory",

address = "Germany",

note = "11th International Symposium on Algorithmic Game Theory, SAGT 2018, SAGT 2018 ; Conference date: 11-09-2018 Through 13-09-2018",

}

Hof, F, Kern, W, Kurz, S & Paulusma, D 2018, Simple games versus weighted voting games. in X Deng (ed.), Algorithmic Game Theory: 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings. Lecture Notes in Computer Science, vol. 11059, Springer, Cham, pp. 69-81, 11th International Symposium on Algorithmic Game Theory, SAGT 2018, Beijing, China, 11/09/18. https://doi.org/10.1007/978-3-319-99660-8_7

Simple games versus weighted voting games. / Hof, Frits; Kern, Walter; Kurz, Sascha et al.
Algorithmic Game Theory: 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings. ed. / Xiaotie Deng. Cham: Springer, 2018. p. 69-81 (Lecture Notes in Computer Science; Vol. 11059).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Simple games versus weighted voting games

AU - Hof, Frits

AU - Kern, Walter

AU - Kurz, Sascha

AU - Paulusma, Daniël

N1 - Conference code: 11

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85053271172&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-99660-8_7

DO - 10.1007/978-3-319-99660-8_7

M3 - Conference contribution

AN - SCOPUS:85053271172

SN - 978-3-319-99659-2

T3 - Lecture Notes in Computer Science

SP - 69

EP - 81

BT - Algorithmic Game Theory

A2 - Deng, Xiaotie

PB - Springer

CY - Cham

T2 - 11th International Symposium on Algorithmic Game Theory, SAGT 2018

Y2 - 11 September 2018 through 13 September 2018

ER -

Simple games versus weighted voting games

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

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

Simple Games versus Weighted Voting Games: Bounding the Critical Threshold Value

Simple Games versus Weighted Voting Games

Cite this