# Tree Polymatrix Games are PPAD-hard

arXiv: https://arxiv.org/abs/2002.12119 · HTML: https://mlsanity.com/paper/2002.12119/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2020.

## Built on by (most cited first, 2 of 2)

- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [On the Computational Complexity of Performative Prediction](https://mlsanity.com/paper/2601.20180/) (2026)

## Abstract (arXiv)

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.