Forms of representation for simple games: sizes, conversions and equivalences
Visualitza/Obre
10.1016/j.mathsocsci.2015.04.008
Inclou dades d'ús des de 2022
Cita com:
hdl:2117/77521
Tipus de documentArticle
Data publicació2015-07-01
EditorNorth Holland Mathematical Library
Condicions d'accésAccés obert
Llevat que s'hi indiqui el contrari, els
continguts d'aquesta obra estan subjectes a la llicència de Creative Commons
:
Reconeixement-NoComercial-SenseObraDerivada 3.0 Espanya
ProjecteMODELOS Y METODOS COMPUTACIONALES PARA DATOS MASIVOS ESTRUCTURADOS (MINECO-TIN2013-46181-C2-1-R)
TEORIA DE JUEGOS: FUNDAMENTOS MATEMATICOS Y APLICACIONES (MINECO-MTM2012-34426)
TEORIA DE JUEGOS: FUNDAMENTOS MATEMATICOS Y APLICACIONES (MINECO-MTM2012-34426)
Abstract
Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems.
CitacióMolinero, X., Riquelme, F., Serna, M. Forms of representation for simple games: sizes, conversions and equivalences. "Mathematical social sciences", 01 Juliol 2015, vol. 76, p. 87-102.
ISSN0165-4896
Col·leccions
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
MRS15_survey.pdf | 238,0Kb | Visualitza/Obre |