EPSRC Reference: 
EP/D067170/1 
Title: 
Algorithms for computing equilibria in games 
Principal Investigator: 
Savani, Professor R 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computer Science 
Organisation: 
University of Warwick 
Scheme: 
Postdoc Research Fellowship 
Starts: 
01 October 2006 
Ends: 
30 September 2009 
Value (£): 
183,222

EPSRC Research Topic Classifications: 
Algebra & Geometry 
Fundamentals of Computing 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
17 Feb 2006

PDRF  Theoretical Computer Science

Deferred


Summary on Grant Application Form 
Game theory is the mathematical study of conflict andcooperation. It is widely used in modelling economicinteractions, for example in the design of auctions.The understanding of games has become important to users of the internet, for example if they are usingan automated bidding agent on eBay.The internet is studied in computer science with the help ofgame theory. This concerns not only electronic commerce(like eBay), but also congestion (how to control thetransmission rates of popular websites so they do notcrash), and the verification of underlying complextechnical systems that implement internet protocols.A game describes an interactive situation, for exampleby a table that lists possible outcomes when one playerchooses a row and another player a column of the table.Another description may be a network in which players move, with different players in control at different pointsof the network. The players' actions define payoffs for each player that this player wants to maximize. An equilibrium is a stable situation where no player can doany better.This research is concerned with finding equilibria forcertain games. When the game description becomes large, anequilibrium can in practice only be found with the help of acomputer. A trivial method to find an equilibrium is to tryout all possibilities of strategy combinations , and checkthe equilibrium property. Other methods are known that arebetter in practice. However, all currently known algorithmshave exponential worstcase behaviour. Essentially, thismeans that for some hard cases, they are no better thantrivially trying out all possibilities.The research belongs to the area of computational complexityand the design and analysis of algorithms. A famous openproblem in this area is the P vs NP question, which asksif any NPproblem, where a solution can be quickly verified,can also be directly computed quickly (belonging to P,finding the solution in polynomial time). This is widelybelieved to be false, but noone has found a proof. Onemillion dollars is offered as a prize to prove it (seehttp://www.claymath.org/millennium/P_vs_NP).Apart from the famous P vs NP problem, several openproblems in computional complexity are concretecomputational questions. In particular, it is not known ifan equilibrium of a tabular twoplayer game can be found inpolynomial time. This is an important open problem intheoretical computer science, and one goal of this researchis to study it further, for example with methods fromgeometry.A second problem concerns games that are defined bynetworks, called parity games . Determining the winner insuch a parity game is useful for the verification of formalsystems as used in communication protocols. Again, it isa wellknown open problem to find a polynomialtimealgorithm for parity games. This requires an understandingof network techniques (like finding shortest paths). In this research, one intended approach are thegeometrically inspired interior point methods . Thesesolve linear optimization problems, which are very importantfor operational research. For linear optimization, oldermethods had exponential worstcase running time (althoughthey may perform well in practice). Interior point methodsshow that linear optimization problems can be solved inpolynomial time, so they may be relevant for the equilibriumproblems as well.

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.warwick.ac.uk 