Details of Grant 

EPSRC Reference:	EP/L011018/1
Title:	Algorithms for Finding Approximate Nash Equilibria
Principal Investigator:	Savani, Professor R
Other Investigators:	Gairing, Dr M
Researcher Co-Investigators:
Project Partners:	University of East Anglia Value Per Click Ltd
Department:	Computer Science
Organisation:	University of Liverpool
Scheme:	Standard Research
Starts:	01 December 2013	Ends:	30 November 2016	Value (£):	276,828
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:	Information Technologies
Related Grants:
Panel History:	Panel Date Panel Name Outcome 17 Jul 2013 EPSRC ICT Responsive Mode - July 2013 Announced
Summary on Grant Application Form
Game theory is the analysis of how people behave in strategic settings. It has risen to prominence because it can be applied in a wide variety of practical settings. For example, game theory was used in the late 1990s to design auctions for 3G telecommunications, which raised billions of pounds for the UK taxpayer. Game theory has also been used to design patrol routes for airport security, to design strategies for nuclear weapon inspectors, to match junior doctors to their hospital residencies, and to model road congestion. In the commercial world, game theory has found applications ranging from auctions for selling advertising in search engine results to designing the layout of circuits on microchips. The Nash equilibrium is the most fundamental concept in game theory. An exact Nash equilibrium of a game predicts how the players of a game should play: in an exact Nash equilibrium, no player should have an incentive to deviate from their current strategy. This research considers algorithms for finding Nash equilibria. In Computer Science, we usually look for algorithms that are guaranteed to run quickly. Unfortunately, it has been shown that fast algorithms for finding exact Nash equilibria are unlikely to exist. The fact that exact Nash equilibria are hard to compute poses a significant problem. For practical applications, people often want to find Nash equilibria in very large games, but the existing algorithms for finding exact Nash equilibria will take a prohibitively large amount of time to solve these games. The use of approximate Nash equilibria is one way to address this issue: whereas exact Nash equilibria require that all players have no incentive to deviate from their current strategies, approximate Nash equilibria allow the players to have a small incentive to deviate. Since it can be costly to change strategies, approximate Nash equilibria are often good enough for practical applications, and they can be significantly easier to compute. In this research project, we will study algorithms for finding approximate Nash equilibria. Our goal is to study approximation algorithms for bimatrix games, which are a fundamental game model, and potential games, which encompass a wide variety of useful special cases. We will either find efficient approximation algorithms, or formally prove that efficient approximation algorithms are unlikely to exist. We will also study algorithms from the payoff-query point of view. In real-world applications, it is unusual to be given a complete description of the game. Instead, we must find out the properties of the game through experimentation, and performing these experiments may be very costly. Payoff query complexity captures this, and algorithms with low payoff query complexity require few experiments before they give their answer. We will study the payoff query complexity of finding approximate Nash equilibria in bimatrix games and potential games, in order to find useful algorithms that can be applied in real-world settings.
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