EPSRC Reference: 
EP/J019399/1 
Title: 
Efficiency and Complexity in Congestion Games 
Principal Investigator: 
Gairing, Dr M 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

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 stateoftheart. 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 nonacademic 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 