Voir la notice de l'article provenant de la source Numdam
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.
@article{RO_2011__45_4_295_0,
author = {Freixas, Josep and Molinero, Xavier and Olsen, Martin and Serna, Maria},
title = {On the complexity of problems on simple games},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {295--314},
publisher = {EDP-Sciences},
volume = {45},
number = {4},
year = {2011},
doi = {10.1051/ro/2011115},
mrnumber = {2881357},
zbl = {1235.68082},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2011115/}
}
TY - JOUR AU - Freixas, Josep AU - Molinero, Xavier AU - Olsen, Martin AU - Serna, Maria TI - On the complexity of problems on simple games JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2011 SP - 295 EP - 314 VL - 45 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2011115/ DO - 10.1051/ro/2011115 LA - en ID - RO_2011__45_4_295_0 ER -
%0 Journal Article %A Freixas, Josep %A Molinero, Xavier %A Olsen, Martin %A Serna, Maria %T On the complexity of problems on simple games %J RAIRO - Operations Research - Recherche Opérationnelle %D 2011 %P 295-314 %V 45 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2011115/ %R 10.1051/ro/2011115 %G en %F RO_2011__45_4_295_0
Freixas, Josep; Molinero, Xavier; Olsen, Martin; Serna, Maria. On the complexity of problems on simple games. RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 4, pp. 295-314. doi: 10.1051/ro/2011115
Cité par Sources :