文章基本信息

标题：Tree Polymatrix Games Are PPAD-Hard
本地全文：下载
作者：Argyrios Deligkas ; John Fearnley ; Rahul Savani 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：38:1-38:14
DOI：10.4230/LIPIcs.ICALP.2020.38
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 (â^S2 - 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.
关键词：Nash Equilibria; Polymatrix Games; PPAD; Brouwer Fixed Points