Simple games cover voting systems in which a single alternative, such as a bill or anamendment, is pitted against the status quo. A simple game or a yes-no voting system is aset of rules that specifies exactly which collections of “yea” votes yield passage of theissue at hand. Each of these collections of “yea” voters forms a winning coalition. We areinterested in performing a complexity analysis on problems defined on such families ofgames. This analysis as usual depends on the game representation used as input. Weconsider four natural explicit representations: winning, losing, minimal winning, andmaximal losing. We first analyze the complexity of testing whether a game is simple andtesting whether a game is weighted. We show that, for the four types of representations,both problems can be solved in polynomial time. Finally, we provide results on thecomplexity of testing whether a simple game or a weighted game is of a special type. Weanalyze strongness, properness, weightedness, homogeneousness, decisiveness andmajorityness, which are desirable properties to be fulfilled for a simple game. Finally,we consider the possibility of representing a game in a more succinct and natural way andshow that the corresponding recognition problem is hard.
