Details of Grant 

EPSRC Reference:	EP/G069239/1
Title:	Efficient Decentralised Approaches in Algorithmic Game Theory
Principal Investigator:	Goldberg, Professor P
Other Investigators:	Goldberg, Professor L Krysta, Professor P
Researcher Co-Investigators:
Project Partners:
Department:	Computer Science
Organisation:	University of Liverpool
Scheme:	Standard Research
Starts:	01 October 2009	Ends:	31 December 2012	Value (£):	398,279
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:	EP/G069034/1
Panel History:	Panel Date Panel Name Outcome 24 Apr 2009 ICT Prioritisation Panel (April 09) Announced
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.liv.ac.uk