NAfANE: New Approaches for Approximate Nash Equilibria

NAfANE：近似纳什均衡的新方法

• 批准号: EP/X039862/1
• 负责人: Argyrios Deligkas
• 金额: $ 63.73万
• 依托单位: Royal Holloway University of London
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX039862%2F1
• 关键词: NAfANE; New; Approaches; Approximate; Nash

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.

该提案的主要目标是开发新技术，目的是确定NASH Eqeilibria（NE）（游戏理论和经济学中的基础解决方案）概念的可诉说和顽固近似之间的精确截止。纳什均衡是一种情况，没有球员可以通过单方面偏差来增加收益。最终，我们的目标是开发新方法，以增强我们对均衡计算的理解，这是算法游戏理论中最根本的问题。我们将为三个一般类别的游戏均衡的典型性边界，在经济学，数学，数学，人工智能，机器学习和计算机科学社区中引起的各种研究人员都感兴趣。-bimatrix游戏：这是两个玩家之间的基本阶级，在这两个玩家之间进行了广泛的阶级，这些游戏已经在整个游戏中进行了广泛研究。结构，每个节点都与一个玩家相对应，并且每个玩家都与网络定义的相互作用。这种类型的游戏受到了很多关注，这是由于许多应用程序从构建障碍到降低硬度的降低到蛋白质功能预测和半超级监督学习的应用。我们将专注于两人贝叶斯游戏的基石子类。这个游戏系列与Polymatrix游戏密切相关，因为它可以用作两部分网络上的多头发游戏。尽管在上述游戏类别中找到了近似均衡的游戏，但在上述游戏类别中，有几个结果，即可行性和多态度时近似值之间的差距仍然很大。此外，这些游戏的几个``行为举止''家族无法被当前的无XIBIBIBIBITIOS结果捕获。这些游戏家族可以承认尚未发现的多项式时间算法。该建议的目的是纠正这种情况：缩小下限和上限之间的差距，并确定允许多项式时间算法的每类游戏的参数。