2026-04-14T05:38:22Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/250932026-01-14T07:53:46Zcom_2072_1033col_2072_452950

On the complexity of problems on simple games Freixas Bosch, Josep Molinero Albareda, Xavier Olsen, Martin Serna Iglesias, María José Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III Universitat Politècnica de Catalunya. Departament de Ciències de la Computació Universitat Politècnica de Catalunya. GRTJ - Grup de Recerca en Teoria de Jocs Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Teoria de jocs Voting--Mathematical models Game theory Simple Weighted Majority games NP-completeness Vot -- Models matemàtics Jocs, Teoria de Classificació AMS::91 Game theory, economics, social and behavioral sciences::91A Game theory The original publication is available at www.rairo-ro.org Simple games cover voting systems in which a single alter- native, 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. Peer Reviewed Postprint (published version) 2011-10 Article Freixas, J. [et al.]. On the complexity of problems on simple games. "RAIRO. Operations research", Octubre 2011, p. 295-314. 0399-0559 https://hdl.handle.net/2117/25093 10.1051/ro/2011115 eng Open Access 20 p. application/pdf