2026-04-13T07:12:45Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/4455582026-02-07T11:54:32Zcom_2072_1033col_2072_452950

On the complexity of the decisive problem in simple and weighted games Riquelme Csori, Fabian Rolando Polyméris, Andreas Universitat Politècnica de Catalunya. Departament de Ciències de la Computació Universitat Politècnica de Catalunya. ALBCOM - Algorísmia, Bioinformàtica, Complexitat i Mètodes Formals Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat Simple/Weighted game Hypergraph Self-duality Quasi-polynomial We study the computational complexity of an important property of simple and weighted games, which is decisiveness. We show that this concept can naturally be represented in the context of hypergraph theory, and that decisiveness can be decided for simple games in quasi-polynomial time, and for weighted games in polynomial time. The strongness condition poses the main difficulties. Instead, properness reduces the complexity of the problem. Specially if it is amplified by weightiness. Peer Reviewed Postprint (author's final draft) 2011-08 Article Riquelme, F.; Polyméris, A. On the complexity of the decisive problem in simple and weighted games. «Electronic notes in discrete mathematics», Agost 2011, vol. 37, p. 21-26. 1571-0653 https://hdl.handle.net/2117/445558 10.1016/j.endm.2011.05.005 eng https://www.sciencedirect.com/science/article/pii/S1571065311000060 http://creativecommons.org/licenses/by-nc-nd/4.0/ Open Access Attribution-NonCommercial-NoDerivatives 4.0 International 6 p. application/pdf