Loading...
Loading...

Go to the content (press return)

On the complexity of exchanging

Author
Molinero, X.; Olsen, M.; Serna, M.
Type of activity
Journal article
Journal
Information processing letters
Date of publication
2016-02-04
Volume
116
Number
6
First page
437
Last page
441
DOI
https://doi.org/10.1016/j.ipl.2016.01.004 Open in new window
Project funding
Algorísmia, Bioinformàtica, Complexitat i Mètodes Formals ALBCOM
TIN2013-46181-C2-1-R Modelos y Métodos Computacionales para Datos Masivos Estructurados
Teoría de juegos: fundamentos matemáticos y aplicaciones
Repository
http://arxiv.org/abs/1503.06052# Open in new window
http://hdl.handle.net/2117/86068 Open in new window
Abstract
We analyze the computational complexity of the problem of deciding whether, for a given simple game, there exists the possibility of rearranging the participants in a set of j given losing coalitions into a set of j winning coalitions. We also look at the problem of turning winning coalitions into losing coalitions. We analyze the problem when the simple game is represented by a list of wining, losing, minimal winning or maximal loosing coalitions.
Citation
Molinero, X., Olsen, M., Serna, M. On the complexity of exchanging. "Information processing letters", 04 Febrer 2016, vol. 116, núm. 6, p. 437-441.
Keywords
Computational complexity, Simple games, Tradeness, Weighted games
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods
GRTJ - Game Theory Research Group

Participants

Attachments