Efficient Decentralised Approaches in Algorithmic Game Theory

Lead Research Organisation: University of Liverpool
Department Name: Computer Science

Abstract

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.

Publications

10 25 50
publication icon
Ackermann H (2011) Uncoordinated Two-Sided Matching Markets in SIAM Journal on Computing

publication icon
Chen N (2014) On revenue maximization with sharp multi-unit demands in Journal of Combinatorial Optimization

publication icon
Deng X (2014) Revenue maximization in a Bayesian double auction market in Theoretical Computer Science

publication icon
Fearnley J (2012) Algorithmic Game Theory

publication icon
Ferraioli D (2016) Decentralized dynamics for finite opinion games in Theoretical Computer Science

publication icon
Ferraioli D (2012) Algorithmic Game Theory

 
Description Game Theory seeks to provide forecasts of interactions amongst competing entities. The classical solution concept of Nash Equilibrium defines a state of affairs in which all players are satisfied (have no incentive to do something different). But, it does not explain a may in which such a state of affairs can be reached. In particular, one would prefer to believe that any outcome or solution, can be obtained by players "negotiating amongst themselves", rather than having it imposed on them by a central authority.



Our focus was on well-known "standard" algorithms have been studied for Nash Equilibrium computation, in particular ones that can be regarded as modelling decentralised interaction amongst the players. We obtained new results for Fictitious Play, and the Lemke-Howson algorithm. Fictitious Play is a simple "learning dynamics" that has been proven to solve certain important classes of games. The paper "On the Approximation Performance of Fictitious Play in Finite Games" answers the question of well FP performs at finding approximate Nash equilibria. Meanwhile, the paper "The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions" makes a fundamental contribution to our understanding of the view of this algorithm as an equilibrium-selection model. For this algorithm, we characterise the computational complexity of the solutions that it finds.

We also studied a class of games that forms a useful representation of real-world competition, and where there exist efficient algorithms. This is the content of the paper "Ranking games that have competitiveness-based strategies". This is a class of games that represents an interesting challenge instance for the study of decentralised solutions, because while we obtained algorithms that solve them, having provable performance guarantees, the algorithms do not model a decentralised interaction. We have some purely experimental results that Fictitious Play nevertheless solves this class of games.
Exploitation Route Our results highlight the distinction between outcomes that can arise due to "realistic" behaviour of decentralised agents, and outcomes that require central authority in order to be determined. As such, they shed new light on the realism of game-theoretic solution concepts. Future researchers should use these results as guidance on the reliability of predictions that are based on game-theoretic or multi-agent models.
Sectors Aerospace, Defence and Marine,Digital/Communication/Information Technologies (including Software),Security and Diplomacy