Loading...
Loading...

Go to the content (press return)

On the complexity of some specific problems on simple games

Author
Molinero, X.; Olsen, M.; Serna, M.
Type of activity
Presentation of work at congresses
Name of edition
27th European Conference on Operational Research
Date of publication
2015
Presentation's date
2015-07-12
Book of congress proceedings
27th European Conference on Operational Research: conference handbook: EURO 2015, 12-15 July 2015, Glasgow
First page
74
URL
http://www.theorsociety.com/ygu575kjg/EURO2015_Programme_Handbook_FINAL_for_USB.pdf Open in new window
Abstract
This work is a follow up of results given in [1]. Here we present some computational complexity results for specific problems and simple games. For instance, we consider the complexity of determining trade robustness for a given simple game in the four natural explicit representations: winning, losing, minimal winning, and maximal losing. Our results show that the problem is solvable in polynomial in some cases but in other it is NP-hard depending on the input and the output. We also define the ...
Keywords
Complexity and approximation, Computer science/applications, Game theory
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods
GRTJ - Game Theory Research Group

Participants