Efficient Decentralised Approaches in Algorithmic Game Theory

博弈论是对竞争（更一般地说，非合作）情况的数学分析，经常在数学和经济学的背景下进行研究。解决方案的概念（如纳什均衡或相关均衡）是对博弈结果的数学描述-所有参与者或参与者做出的选择集。许多算法已经被提出（并实现为程序）来计算这些解决方案。计算机科学的工作吸引了博弈论社区的极大兴趣。计算机科学家已经开发了分析工具来了解计算过程的速度和效率，以及计算问题的固有难度。这提供了新的标准来判断博弈论中的替代解决方案的概念，并提出了算法来找到它们。分布式计算领域为游戏中玩家之间的交互提供了有用的数学模型。这种交叉是一个双向的过程，因为与此同时，计算机科学家已经应用博弈论的概念来模拟互联网上的大规模互动，电子市场，以及计算代理之间的互动（在人工智能的背景下）。到目前为止，已经提出的许多计算游戏结果的算法，其缺点在于该算法基本上以集中的方式协调玩家的行为。去中心化是指在没有任何中央控制的情况下开发由多个参与者（或代理）使用的算法。这些算法的开发需要玩家如何精确交互的模型（为此目的已经提出了各种模型）。这一研究议程产生了大量重要而有趣的问题，这些问题本质上是问：为了迅速找到解决方案，必须对参与者如何互动做出什么假设？这项研究旨在开发新的算法，以分散的方式有效地找到解决方案。我们还寻求更好地理解可证明有效的算法（在数学上被描述为在多项式时间内运行的算法）可以实现的一般限制。一般来说，我们对可以通过高效且分散的算法找到的解决方案感兴趣。通过这种算法可以找到的解决方案可以说比其他解决方案概念更现实。本提案中概述的研究将适用于模拟许多玩家之间的大规模互动的游戏，以及标准的正常形式游戏。

Game theory is the mathematical analysis of competitive (more generally, non-cooperative) situations, and is frequently studied in the context of mathematics and economics. A solution concept (such as Nash equilibrium, or correlated equilibrium) is a mathematical description of the outcome of a game -- the set of choices made by all players, or participants. Many algorithms have been proposed (and implemented as programs) to compute these solutions.Work in Computer Science has attracted considerable interest from the Game Theory community. Computer scientists have developed analytical tools to understand the speed and efficiency of a computational process, and the inherent difficulty of computational problems. This provides new criteria for judging alternative solution concepts in Game Theory, and the algorithms that have been proposed to find them. The field of Distributed Computation has provided useful mathematical models of the interaction amongst the players in a game. This cross-fertilisation is very much a two-way process, since at the same time, computer scientists have applied game-theoretic concepts to model large-scale interactions on the Internet, electronic marketplaces, and interactions amongst computational agents (in the context of AI).So far, many of the algorithms that have been proposed to compute the outcomes of games, have the drawback that the algorithm essentially coordinates the behaviour of the players in a centralised manner. Decentralisation refers to the development of algorithms that are used by multiple players (or agents) in the absence of any central control. The development of these algorithms requires models of precisely how the players interact (and various models have been proposed for this purpose). This research agenda gives rise to a large number of important and interesting problems, which essentially ask: What assumptions have to be made about how players interact, in order for solutions to be found rapidly? This research aims to develop novel algorithms that find solutions efficiently, and in a decentralised manner. We also seek a better understanding of the general limitations on what can be achieved by provably efficient algorithms (characterised mathematically as algorithms that run in polynomial time).Generally, we are interested in solutions that can be found by algorithms that are both efficient and decentralised. Solutions that can be found by such algorithms are arguably more realistic than other solution concepts. The research outlined in this proposal will apply to games that model large-scale interactions amongst many players, as well as standard normal-form games.