纳什均衡与不动点计算是算法博弈论的基本研究方向之一，其主要目标是利用经典计算理论去解释均衡计算问题的复杂程度。在过去三十年中，研究人员设计算法并建立复杂性归约，已在这一研究方向上取得了重大的成就。该领域最新的进展是利用指数时间假设证明均衡问题的细粒度复杂性结果。此想法是受到经典复杂性理论的启发，利用合理假设对组合优化问题中更精确的复杂性结果进行研究。指数时间假设对经典组合优化问题的研究已经蓬勃发展，取得了令人瞩目的成果。相比之下，均衡计算问题的细粒度复杂性研究尚处于初级阶段：甚至一个合理版本的假设都尚未确定。本项目致力于深入理解纳什均衡与不动点计算问题的细粒度复杂性研究，聚焦于完善已有假设和发展相应的归约技术。相关成果将为解决二人博弈和匿名博弈纳什均衡的不可近似性等算法博弈论核心问题奠定基础。

The study of Nash equilibrium and fixed-point computation is one of the fundamental research topics in the algorithmic game theory. The main focus is to understand the intractability of equilibrium related computational problems using tools from the classical complexity theory. This is an active research direction and incredible achievements have been made over the past three decades, through both the lines of designing algorithms and establishing hardness reductions. Recent progress of the area is the application of the Exponential Time Hypothesis (ETH) to prove fine-grained complexity results for equilibrium related problems, inspired by the use of ETH to establish precise hardness results for combinational optimization problems, which is fruitful and well-developed. However, for equilibrium computation problems, the study of their fine-grained complexity is still at an early stage: even a robust version of ETH seems to be unclear. This proposal aims to deepen our understanding of the fine-grained complexity of Nash equilibrium and fixed-point computation. We will mainly focus on refining the complexity assumptions and developing related reduction techniques. These results will serve as a basis for resolving central problems in algorithmic game theory including inapproximability of Nash equilibrium in two-player games and anonymous games.