DocumentCode :
2230889
Title :
Three-player shove is NP-complete
Author :
Cincotti, Alessandro
Author_Institution :
Sch. of Inf. Sci., Japan Adv. Inst. of Sci. & Technol., Ishikawa, Japan
Volume :
3
fYear :
2010
fDate :
20-22 Aug. 2010
Abstract :
In two player games players are in conflict to each other and coalitions are not allowed but in three-player games two players can join their efforts against the third player. As a result, cooperation is a key-factor that deeply affects the complexity of three-player games. In the game of Shove, cooperation can be much more difficult than competition and, as a consequence, three-player Shove played on a set of rows of dominoes is NP-complete.
Keywords :
computational complexity; game theory; optimisation; NP-complete; computational complexity; three-player Shove; three-player games; Educational institutions; combinatorial games; computational complexity;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Advanced Computer Theory and Engineering (ICACTE), 2010 3rd International Conference on
Conference_Location :
Chengdu
ISSN :
2154-7491
Print_ISBN :
978-1-4244-6539-2
Type :
conf
DOI :
10.1109/ICACTE.2010.5579653
Filename :
5579653
Link To Document :
بازگشت