2026-08-18T14:22:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8805 2024-03-06T10:42:42Z ddc:004 open_access

Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games Coulombe, Michael J. Lynch, Jayson computational complexity undecidable team games imperfect information We show the undecidability of whether a team has a forced win in a number of well known video games including: Team Fortress 2, Super Smash Brothers: Brawl, and Mario Kart.To do so, we give a simplification of the Team Computation Game [Hearn and Demaine, 2009] and use that to give an undecidable abstract game on graphs. This graph game framework better captures the geometry and common constraints in many games and is thus a powerful tool for showing their computational complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael J. Coulombe and Jayson Lynch 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.14 urn:nbn:de:0030-drops-88051 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.14 eng https://creativecommons.org/licenses/by/3.0/legalcode