Algorithms for Finding Approximate Nash Equilibria

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.

Game theory is applied in a wide variety of non-academic contexts. There is a clear existing commercial interest from internet companies like Google, eBay, and Microsoft, who run sponsored search auctions and employ large teams of game theorists. As more business takes place online, further commercial applications of game theory will arise. The finance sector, which is important for the UK economy, is another area where game theory is highly relevant. Game theory also has applications in the public sector, ranging from spectrum auctions for telecommunications, to hospital matching schemes for junior doctors.

We see the primary long-term non-academic impact of game-theory research as economic. The potential beneficiaries include businesses such as search engines that run advertisement auctions, security companies that need to design patrols, and managers of transportation networks that need to control congestion. We expect that a wide variety of industrial partners will at some point need expertise from academia to apply game theory to enhance their businesses.

In order to generate short term impact for the project we will work directly with relevant non-academic collaborators. We have identified one main project partner along with two sets of existing collaborators. They will directly benefit from the work that takes place during the project. With all three, we have started preliminary engagement and we anticipate that there will be an ongoing two-way exchange of ideas. We will take the techniques that are developed during the project, and try to use them to solve the specific problems of our non-academic collaborators. At the same time, by maintaining an ongoing dialogue, we will be able to tailor our future research towards non-academic applications.

Our project partner is ValuePerClick (http://valueperclick.com/), a Merseyside-based company that designs bidding rules for online advertisers. They use statistical analysis and simulation to design and test rules. However, that approach ignores the well-know strategic aspects of advertising auctions. We propose to apply empirical game-theoretic analysis by using their data to build empirical games (using insights from WP3) and provide strategic insights by analysing their approximate equilibria (using algorithms from WP1 and the implementations from WP4).

In addition, we have existing non-academic collaborators that can benefit from the research proposed here:

Gairing and Savani, in collaboration with other members of the school of Electrical Engineering, Electronics, and Computer Science, have recently started to engage with Liverpool City Council about real-time methods to reduce traffic congestion in Liverpool. We plan to use existing approaches along with those developed in WP2 and WP3 to develop potential solutions to this problem.

Savani has a current ESRC grant in which he has developed an agent-based model (simulator) for the Sterling money market. The project partners are the Royal Bank of Scotland and Logica. We will employ a similar approach as with ValuePerClick, using our agent-based model as a simulator to generate empirical games and the analysing their equilibria (using the work from WP1, WP3, and WP4). The strategies in these games will correspond to agent behaviours, such as how banks make funding decisions in the inter-bank market. Insights here offer potential impacts for bank and regulator policy, and consequently financial stability.