On the complexity of the decisive problem in simple and weighted games

DOI10.1016/J.ENDM.2011.05.005MaRDI QIDQ2840677zbMATH OpenOpenAlexFDO

Authors Fabián Riquelme, Andreas Polyméris

Publication date 23 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphself-dualityquasi-polynomialsimple/weighted game

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Cooperative games (91A12) Hypergraphs (05C65) Voting theory (91B12)

Abstract: We study the computational complexity of an important property of simple, regular and weighted games, which is decisiveness. We show that this concept can naturally be represented in the context of hypergraph theory, and that decisiveness can be decided for simple games in quasi-polynomial time, and for regular and weighted games in polynomial time. The strongness condition poses the main difficulties, while properness reduces the complexity of the problem, especially if it is amplified by regularity. On the other hand, regularity also allows to specify the problem instances much more economically, implying a reconsideration of the corresponding complexity measure that, as we prove, has important structural as well as algorithmic consequences.

Recommendations

• On the complexity of problems on simple games
• Simple games versus weighted voting games
• The weighted majority game
• Simple games versus weighted voting games: bounding the critical threshold value
• Dimension and codimension of simple games

Cites work

• scientific article; zbMATH DE number 1357433 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• A linear time algorithm for recognizing regular Boolean functions
• An O(nm)-time algorithm for computing the dual of a regular Boolean function
• Conjuncturally Stable Coalition Structures
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• Stability of two player game structures

Cited in

(12)

• On the complexity of exchanging
• On the complexity of problems on simple games
• A decisiveness index for simple games
• On the Value Problem in Weighted Timed Games.
• Simple games versus weighted voting games
• On -roughly weighted games
• Counting inequivalent monotone Boolean functions.
• On the dimension of simple monotonic games
• Cooperation through social influence
• -decisiveness in simple games
• On the use of binary decision diagrams for solving problems on simple games
• Forms of representation for simple games: sizes, conversions and equivalences

This page was built for publication: On the complexity of the decisive problem in simple and weighted games

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