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

DOI10.1016/J.ENDM.2011.05.005zbMATH Open1268.91064arXiv1303.7122OpenAlexW2046053229MaRDI QIDQ2840677FDOQ2840677

Authors: Fabián Riquelme, Andreas Polyméris 

Publication date: 23 July 2013

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Title not available (Why is that?)
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
• A linear time algorithm for recognizing regular Boolean functions
• Stability of two player game structures
• Conjuncturally Stable Coalition 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
• Counting inequivalent monotone Boolean functions.
• On \(\alpha\)-roughly weighted games
• On the dimension of simple monotonic games
• Cooperation through social influence
• \(\alpha\)-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)