Growth of dimension in complete simple games

DOI10.1016/J.MATHSOCSCI.2016.08.008MaRDI QIDQ1680089zbMATH OpenOpenAlexFDO

Authors Liam O'Dwyer, Arkadii Slinko

Publication date 22 November 2017

Published in Mathematical Social Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.05114

zbMATH Keywords

complete simple gamesgrowth of dimension

Mathematics Subject Classification ID

(n)-person games, (n>2) (91A06) Hierarchical games (including Stackelberg games) (91A65)

Abstract: The concept of dimension in simple games was introduced as a measure of the remoteness of a given game from a weighted game. Taylor and Zwicker (1993) demonstrated that the dimension of a simple game can grow exponentially in the number of players. However, the problem of worst-case growth of the dimension in complete games was left open. Freixas and Puente (2008) showed that complete games of arbitrary dimension exist and, in particular, their examples demonstrate that the worst-case growth of dimension in complete games is at least linear. In this paper, using a novel technique of Kurz and Napel (2016), we demonstrate that the worst-case growth of dimension in complete simple games is exponential in the number of players.

Recommendations

• A note on the growth of the dimension in complete simple games
• Dimension of complete simple games with minimum
• Dimension and codimension of simple games
• Heights of simple games
• A note about games-composition dimension

Cites work

• A class of simple games
• A minimum dimensional class of simple games
• Characterizing Ideal Weighted Threshold Secret Sharing
• Complete simple games
• Different ways to represent weighted majority games
• Dimension and codimension of simple games
• Dimension of complete simple games with minimum
• Hierarchical threshold secret sharing
• scientific article; zbMATH DE number 1357433 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• On the Complexity of Cooperative Solution Concepts
• On the computational complexity of weighted voting games
• On the dimension of simple monotonic games
• Roughly weighted hierarchical simple games
• The dimension for the European Union Council under the Nice rules.
• Weighted voting, multicameral representation, and power
• Weightedness and structural characterization of hierarchical simple games

Cited in

(5)

• A note on the growth of the dimension in complete simple games
• A growth model based on the arithmetic \(Z\)-game
• Dimension of complete simple games with minimum
• Multidimension: a dimensionality extension of simple games
• On the generalized dimension and codimension of simple games

This page was built for publication: Growth of dimension in complete simple games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1680089)