Tree polymatrix games are PPAD-hard

DOI10.4230/LIPICS.ICALP.2020.38MaRDI QIDQ6842538zbMATH OpenFDO

Authors Argyrios Deligkas, John Fearnley, Rahul Savani

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.38

zbMATH Keywords

Brouwer fixed pointsNash equilibriapolymatrix gamesPPAD

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• Approximating Nash equilibria in tree polymatrix games
• Computing approximate Nash equilibria in polymatrix games
• Computing constrained approximate equilibria in polymatrix games
• Constant rank two-player games are PPAD-hard
• Inapproximability of Nash equilibrium
• On minmax theorems for multiplayer games
• On the complexity of 2D discrete fixed point problem
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• Settling the complexity of computing approximate two-player Nash equilibria
• Settling the complexity of computing two-player Nash equilibria
• The complexity of computing a Nash equilibrium

Cited in

(1)

• Pure-circuit: tight inapproximability for PPAD

This page was built for publication: Tree polymatrix games are PPAD-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842538)