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

Abstract

We study the computational complexity of an important property of simple 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 weighted games in polynomial time. The strongness condition poses the main difficulties. Instead, properness reduces the complexity of the problem. Specially if it is amplified by weightiness.

Peer Reviewed

Postprint (author's final draft)