skip to main content

Linde Institute/Social and Information Sciences Laboratory (SISL) Seminar

Friday, November 22, 2013
12:00pm to 1:00pm
Add to Cal
Baxter 127
The Complexity of Nash Equilibria as Revealed by Data
Siddharth Barman, Postdoctoral Scholar, Computing and Mathematical Sciences, Caltech,

In this paper we initiate the study of the computational complexity of Nash equilibria in bimatrix games that are specified via data. This direction is motivated by an attempt to connect the emerging work on the computational complexity of Nash equilibria with the perspective of revealed preference theory, where inputs are data about observed behavior, rather than explicit payoffs. Our results draw such connections for large classes of data sets, and provide a formal basis for studying these connections more generally. In particular, we derive three structural conditions that are sufficient to ensure that a data set is both consistent with Nash equilibria and that the observed equilibria could have been computed efficiently: (i) small dimensionality of the observed strategies, (ii) small support size of the observed strategies, and (iii) small chromatic number of the data set. Key to these results is a connection between data sets and the player rank of a game, defined to be the minimum rank of the payoff matrices of the players. We complement our results by constructing data sets that require rationalizing games to have high player rank, which suggests that computational constraints may be important empirically as well.

Joint work with Umang Bhaskar, Federico Echenique, and Adam Wierman


For more information, please contact Jenny Niese by phone at Ext. 6010 or by email at