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.