Tree Polymatrix Games are PPAD-hard
share
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.
READ FULL TEXT