• 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