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.