NAfANE: New Approaches for Approximate Nash Equilibria

这项建议的主要目标是开发新的技术，目的是确定纳什均衡(NE)的易处理和难处理近似之间的精确界限，Nash均衡是博弈论和经济学中的基本解概念。纳什均衡是一种没有玩家可以通过单方面偏离来增加收益的情况。最终，我们的目标是开发新的方法，以增强我们对均衡计算的理解，均衡计算是算法博弈论中最基本的问题。我们将为经济、数学、人工智能、机器学习和计算机科学社区内的各种研究人员感兴趣的三类一般游戏解决均衡计算的可操纵性边界。-Bimatrix游戏：这是两个玩家之间玩的基本游戏类别，多年来已被广泛研究。-PolyMatrix游戏：这类游戏捕获具有基本网络结构的多人游戏，其中每个节点对应一个玩家，每个玩家与网络定义的邻居中的玩家互动。由于从积木到降低难度的众多应用，这类游戏受到了许多关注，在蛋白质功能预测和半监督学习中的应用。-贝叶斯博弈：这是不完全信息博弈的基础类别。我们将专注于两人贝叶斯游戏的基石子类。这类对策与多矩阵对策密切相关，因为它可以表示为二部网络上的多矩阵对策，虽然在寻找上述对策类中的近似均衡方面已有几个结果，无论是正的还是负的，但难解性和多项式时间逼近之间的差距仍然很大。此外，有几个“行为良好”的家庭，这些游戏不能被目前的不可逼近结果所捕获。这些博弈族可以接受一种尚未被发现的多项式时间算法。这项建议的目标是纠正这种情况：弥合下限和上限之间的差距，并为每类游戏确定允许多项式时间算法的参数。

The main goal of this proposal is to develop new techniques with the aim of identifying the precise cut-off between tractable and intractable approximations of Nash equilibria (NE), the foundational solution-concept in Game Theory and Economics. A Nash equilibrium is a situation where no player can increase their payoff by unilaterally deviating. Ultimately our target is to develop new approaches that will enhance our understanding of equilibrium computation, the most fundamental problem in Algorithmic Game Theory. We will settle the tractability frontier of equilibrium computation for three general classes of games that are of interest to a wide variety of researchers within the communities of Economics, Mathematics, Artificial Intelligence, Machine Learning, and Computer Science.- Bimatrix Games: This is the fundamental class of games, played between two players, that has been studied extensively over the years.- Polymatrix Games: This class captures many-player games with an underlying network structure, where every node corresponds to a player, and every player interacts with the players in their neighborhood as defined by the network.This type of games received a lot of attention due to numerous applications ranging from building-blocks to hardness reductions, to applications in protein function prediction and semi-supervised learning.- Bayesian Games: This is the foundational class of games with incomplete information. We will focus on the cornerstone subclass of two-player Bayesian games. This family of games is closely related to polymatrix games, since it can be represented as a polymatrix game over a bipartite network.While there exist several results, both positive and negative, for finding approximate equilibria in the above-mentioned classes of games, the gaps between intractability and polynomial-time approximability are still large. In addition, there exist several ``well-behaved'' families of these games that cannot be captured by the current inapproximability results. These families of games could admit a polynomial-time algorithm that has not been discovered yet. The objective of this proposal is to rectify this situation: close the gaps between lower bounds and upper bounds, and identify parameters for each class of games that allow for polynomial-time algorithms.