Three-player Toppling Dominoes is NP-complete

摘要

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 Toppling Dominoes, cooperation can be much more difficult than competition and, as a consequence, three-player Toppling Dominoes played on a set of rows of dominoes is NP-complete.