Efficiency and Complexity in Congestion Games

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

The long term aim of this project is to improve the performance of large scale networks. Our focus is on the Internet and transportation networks. A central problem in such networks is the contention for scarce resources. The congestion games that we study in this project provide us with a fairly general model for the non-cooperative sharing of resources. The expected results will significantly improve our theoretical understanding of such systems. Our strong collaborations with industry will ensure that the results will also be deployed to practical problems.

Throughout the project we will collaborate with the Xerox Research Centre Europe (Xerox). Xerox's business modelling group has a strong expectise in applying theoretical results (e.g. algorithms) to solve real-world problems. They are a relevant partner for this project due to their specialisation in transportation problems, which are a very natural application domain for congestion games. We have discussed the planned research with Onno Zoeter, researcher at Xerox's research office in Grenoble, France, and project leader for its demand management project, and with Marco Bressan, Chief Innovation Officer of Xerox's transportation solutions group. During the discussions we have identified several interesting practical transportation problems to which the insights and techniques developed in this project can contribute significantly.

A short term impact of this project is the establishment of a strong collaboration between the University of Liverpool and the Xerox Research Centre Europe. This collaboration will shape the direction of our theoretical work towards important problems in real world applications.

In cooperation with Xerox, we aim to improve the demand management in transportation systems. Our research will give new insights on how demand management tools (e.g. road tolls or parking charges) influence user behaviour and how to use this information to
design optimised pricing strategies. We expect that the knowledge exchange and collaborative research effort will have a strong impact on transportation demand management systems. At the same time, we as the academic partner will benefit from this collaboration by getting access to research questions, which are not only interesting from an academic perspective but also have the potential for a strong commercial and societal impact.

The long-term beneficiaries of this project will be the general public. Our project has the potential to improve their quality of living by helping to make their streets less congested. This not only reduces the time that each of us spends in traffic but also helps to make our streets safer and our cities less polluted.