Game theory result takes CQTian to STOC

CQT's Troy Lee has helped address an open question about 'Nash equilibria' using a tool he and his collaborators earlier applied to study quantum communication.

Troy presented the work at the 45th ACM Symposium on the Theory of Computing (STOC) at Stanford in Palo Alto, California, on 4 June. STOC is a prestigious annual conference for the dissemination of research in information theory and computer science.

Rock, paper, scissors (this photo from a 2009 world championships) is a classic non-cooperative game: for players, the best strategy is to choose their hand randomly. Findng such optimal strategies, known as 'Nash equilibria', for other non-cooperative games is an ongoing challenge in game theory. New research by Troy Lee and his collaborators identifies classes of games for which the Nash equilibria can be efficiently approximated. Image by wizardhat on Flickr.

Nash equilibria are a property of strategy games involving two or more players. The concept, for which American mathematician John Nash won a Nobel prize, is a set of strategies that players wouldn't want to change even if they knew what the other players were doing. It provides a mathematical way of thinking about situations often encountered in human life.

"We now think that it is computationally difficult to arrive at or compute these equilibrium strategies in the first place," says Troy. Hence researchers have become interested in 'approximate' Nash equilibria – strategies for which the players can only increase their payoff a little by unilaterally changing their strategy. In practice, these are likely to be just as useful as exact solutions. "Most people probably do not change their behaviour too much to pick up an extra penny," says Troy.

But it is still not known if approximate Nash equilibria are easy to compute. Troy, with colleagues from Israel and the US, identified classes of games for which it is possible to compute approximate Nash equilibria in 'polynomial time' – this means the calculation time scales manageably with the number of strategies. Their approach also gives a way to calculate these strategies.

The team's approach relies on classifying the simplicity of the game: they looked at a property known as 'matrix rank'. A two-player game played by Alice and Bob can be described by two matrices, A and B, that detail their payoffs for all the different possible combinations of strategies the two could adopt. The matrix rank is a measure of the complexity of the matrix.

Troy and his colleagues showed that a particular way of approximating the matrix rank also leads to an algorithm to compute approximate Nash equilibria. The trick works for A and B matrices that are simple according to this measure of complexity: technically, for cases where A+B has constant rank or rank logarithmic in the number of strategies.

"The algorithm we develop is quite general and works for a whole family of optimization problems, of which Nash equilibrium is one example," says Troy.

The result does not involve any quantum component, but shows the value of interdisciplinary research. In earlier work on quantum communication, Troy and his co-author Adi Shraibman from the Academic College of Tel-Aviv in Israel had shown that approximate rank is roughly equivalent to another quantity – and this equivalence was a tool in the new work.

Other collaborators in the new research are Noga Alon from Tel Aviv University, Israel and Santosh Vempala of Georgia Tech, Atlanta, in the United States.

The work is published in the Proceedings of STOC 2013 as "The Approximate Rank of a Matrix and its Algorithmic Applications" doi:10.1145/2488608.2488694 (2013); a pdf is also available here.