2026-07-22T06:27:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12445 2024-03-06T10:50:09Z ddc:004 open_access

Tree Polymatrix Games Are PPAD-Hard Deligkas, Argyrios Fearnley, John Savani, Rahul Nash Equilibria Polymatrix Games PPAD Brouwer Fixed Points We prove that it is PPAD-hard to compute a Nash equilibrium in a tree polymatrix game with twenty actions per player. This is the first PPAD hardness result for a game with a constant number of actions per player where the interaction graph is acyclic. Along the way we show PPAD-hardness for finding an ε-fixed point of a 2D-LinearFIXP instance, when ε is any constant less than (√2 - 1)/2 ≈ 0.2071. This lifts the hardness regime from polynomially small approximations in k-dimensions to constant approximations in two-dimensions, and our constant is substantial when compared to the trivial upper bound of 0.5. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Argyrios Deligkas and John Fearnley and Rahul Savani 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.38 urn:nbn:de:0030-drops-124458 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.38 eng https://creativecommons.org/licenses/by/3.0/legalcode