Title :
Three-player shove is NP-complete
Author :
Cincotti, Alessandro
Author_Institution :
Sch. of Inf. Sci., Japan Adv. Inst. of Sci. & Technol., Ishikawa, Japan
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;
Conference_Titel :
Advanced Computer Theory and Engineering (ICACTE), 2010 3rd International Conference on
Conference_Location :
Chengdu
Print_ISBN :
978-1-4244-6539-2
DOI :
10.1109/ICACTE.2010.5579653