NAfANE: New Approaches for Approximate Nash Equilibria

该提案的主要目标是开发新技术，旨在确定纳什均衡（NE）的易处理和难处理近似值之间的精确截止值，这是博弈论和经济学中的基本解决方案概念。纳什均衡是一种没有参与者可以通过单方面偏离来增加收益的情况。最终，我们的目标是开发新的方法，这将提高我们对均衡计算的理解，这是数学博弈论中最基本的问题。我们将解决三个一般类别的游戏的均衡计算的易处理性边界，这些游戏对经济学，数学，人工智能，机器学习和计算机科学领域的各种研究人员都感兴趣。Bimatrix游戏：这是两个玩家之间玩的基本游戏类，多年来一直被广泛研究。Polymatrix Games：本课程描述了具有底层网络结构的多人游戏，其中每个节点对应一个玩家，每个玩家与网络定义的邻居中的玩家进行交互。由于从构建模块到硬度降低，再到蛋白质功能预测和半监督学习的应用，这类游戏受到了广泛的关注。贝叶斯博弈：这是不完全信息博弈的基础类。我们将专注于两人贝叶斯博弈的基石子类。这类博弈与多矩阵博弈密切相关，因为它可以被表示为二部网络上的多矩阵博弈。虽然在上述博弈类中找到近似均衡有几个结果，既有正面的也有负面的，但在难处理性和多项式时间近似性之间的差距仍然很大。此外，有几个“很好的”家庭，这些游戏，不能捕捉到目前的不可逼近的结果。这些家族的游戏可以承认一个多项式时间的算法，尚未发现。这个建议的目的是纠正这种情况：关闭下界和上界之间的差距，并确定参数的每一类游戏，允许多项式时间算法。

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.