Easy weighted majority games
The authors consider a weighted majority game with \(n\) players. Such a game is easy if the calculation of the number of coalitions for which a player is pivotal can be determined in polynomial time \((n)\). The paper identifies 3 types of games which are easy-unbalanced, generalized unbalanced, and sequential. In each type, a special structure to the voting weights makes the game easy. For instance, in the sequential type, each weight is exactly divided by the next smaller weight. The question whether these 3 types exhaust the class of easy games is left open.
scientific article; zbMATH DE number 1545422