Algorithms for computing equilibria in games

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 worst-case 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 NP-problem, 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 no-one 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 two-player 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 well-known open problem to find a polynomial-timealgorithm 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 worst-case 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.