Details of Grant 

EPSRC Reference:	EP/J019399/1
Title:	Efficiency and Complexity in Congestion Games
Principal Investigator:	Gairing, Dr M
Other Investigators:
Researcher Co-Investigators:
Project Partners:	Xerox
Department:	Computer Science
Organisation:	University of Liverpool
Scheme:	First Grant - Revised 2009
Starts:	01 January 2013	Ends:	31 December 2014	Value (£):	99,571
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:	Panel Date Panel Name Outcome 06 Jun 2012 EPSRC ICT Responsive Mode - Jun 2012 Announced
Summary on Grant Application Form
The goal of this project is to study ways to improve the performance of large scale networks, like the Internet, in the presence of selfish entities. This can only be achieved with a better understanding of these environments and their operational points, called Nash equilibria. A Nash equilibrium is a state in which no player improve their utility by changing to another strategy. In this project we focus on the very fundamental class of congestion games and the related class of potential games. In a congestion game, we are given a set of resources and each player selects a subset of them (e.g. a path in a network). Each resource has a cost function that depends on the load induced by the players that use it. Each player aspires to minimise the sum of the resources' costs in its strategy given the strategies chosen by the other players. Such games are expressive enough to capture a number of otherwise unrelated applications - including routing and network design - yet structured enough to permit a useful theory. In this project, we will push the frontiers of this theory even further. Moreover, in collaboration with XEROX, we will investigate applications of this theory to demand management in transportation systems. Two of these applications are smart road toll and parking management systems. Congestion games have attracted lots of research, but many fundamental problems are still open. We have identified three important directions in which we want to extent the current state-of-the-art. These are: (1) evaluation of Nash equilibria (2) computational complexity of Nash equilibria (3) approximation of optimal solutions
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