EPSRC logo

Details of Grant 

EPSRC Reference: GR/T07343/02
Title: Algorithms of Nework-sharing Games
Principal Investigator: Goldberg, Professor P
Other Investigators:
Goldberg, Professor L
Researcher Co-Investigators:
Project Partners:
Department: Computer Science
Organisation: University of Liverpool
Scheme: Standard Research (Pre-FEC)
Starts: 14 August 2006 Ends: 13 January 2008 Value (£): 53,437
EPSRC Research Topic Classifications:
Fundamentals of Computing Mathematical Aspects of OR
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:  
Summary on Grant Application Form
We consider game-theoretic situations in which a set of users wish to carry out tasks using a set of shared resources. (Examples include road traffic and computer network traffic.) The cost of using a resource depends on the amount of usage it attracts, and increases in proportion with usage.If users are free to modify their choices based on the observed costs of resources, they will tend to distribute themselves evenly over the resources. We expect them to find a Nash equilibrium, in which no user cam modify her selection so as to reduce her cost.For some instances of these congestion games there may be many possible Nash equilibria, and this raises the research questions of how they vary in overall cost, and how hard it is to find the best and the worst. Also, whether some Nash equilibria are more plausible than others on the grounds that that are in some sense more stable. Other questions relate to the time taken by algorithms to find Nash equilibria. The focus of the proposed research is on standard rather than ad-hoc algorithms that may be used to find Nash equilibria, for example randomized search techniques that have been studied in the context of other optimization problems, and standard game-theoretic approaches such as fictitious play. We propose to study the types of equilibria found by these algorithms, and the time taken by them to converge.
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