Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1051/ro/2011115 | RAIRO-OPERATIONS RESEARCH |
Keywords | Field | DocType |
Simple,weighted,majority games,NP-completeness | Simultaneous game,Combinatorial game theory,Mathematical optimization,Computer science,Repeated game,Normal-form game,Screening game,Sequential game,Game tree,Game complexity | Journal |
Volume | Issue | ISSN |
45 | 4 | 0399-0559 |
Citations | PageRank | References |
9 | 0.58 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Freixas | 1 | 171 | 21.48 |
| Xavier Molinero | 2 | 133 | 15.58 |
| Martin Olsen | 3 | 74 | 11.99 |
| Maria J. Serna | 4 | 473 | 70.53 |