On the complexity of problems on simple games

¹ Universitat Politècnica de Catalunya, EPSEM-DMA3, 08240 Manresa, Spain
josep.freixas@upc.edu
² Universitat Politècnica de Catalunya, EPSEM-DMA3, 08240 Manresa, Spain
xavier.molinero@upc.edu
³ Center for Innovation and Business Development, Institute of Business and Technology, Aarhus University, Birk Centerpark 15, 7400 Herning, Denmark
martino@hih.au.dk
⁴ Universitat Politècnica de Catalunya, LSI, 08034 Barcelona, Spain
mjserna@lsi.upc.edu

Received: 9 March 2011
Accepted: 1 September 2011

Abstract

Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation used as input. We consider four natural explicit representations: winning, losing, minimal winning, and maximal losing. We first analyze the complexity of testing whether a game is simple and testing 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 the complexity of testing whether a simple game or a weighted game is of a special type. We analyze strongness, properness, weightedness, homogeneousness, decisiveness and majorityness, 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 and show that the corresponding recognition problem is hard.