Query complexity of approximate equilibria in anonymous games
作者：
Highlights：
• We study equilibrium computation of multi-player anonymous games.
• We extend and develop the general theory of query-efficiency of multi-player games.
• We obtain improved computational efficiency, as well as query efficiency.
• Our main result leads to a new polynomial-time approximation scheme.
• We exhibit an anonymous game whose exact equilibria require irrational numbers.
摘要
•We study equilibrium computation of multi-player anonymous games.•We extend and develop the general theory of query-efficiency of multi-player games.•We obtain improved computational efficiency, as well as query efficiency.•Our main result leads to a new polynomial-time approximation scheme.•We exhibit an anonymous game whose exact equilibria require irrational numbers.
论文关键词：Algorithms,Computational complexity,Game theory
论文评审过程：Received 6 May 2016, Revised 18 May 2017, Accepted 4 July 2017, Available online 29 July 2017, Version of Record 14 September 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.07.002
