Tree polymatrix games are PPAD-hard

Deligkas, A, Fearnley, J and Savani, R ORCID: 0000-0003-1262-7831 (2020) Tree polymatrix games are PPAD-hard In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020-7-8 - 2020-7-12, Beijing.

Text LIPIcs-ICALP-2020-38.pdf - Published version Download (636kB) | Preview

Abstract

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.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	cs.GT, cs.GT, cs.CC
Depositing User:	Symplectic Admin
Date Deposited:	11 Sep 2020 08:51
Last Modified:	21 Apr 2026 18:17
DOI:	10.4230/LIPIcs.ICALP.2020.38
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3100781
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.