CaltechAUTHORS
  A Caltech Library Service

The Complexity of Nash Equilibria as Revealed by Data

Barman, Siddharth and Bhaskar, Umang and Echenique, Federico and Wierman, Adam (2014) The Complexity of Nash Equilibria as Revealed by Data. California Institute of Technology , Pasadena, California. http://resolver.caltech.edu/CaltechAUTHORS:20160321-140122265

[img] PDF (v. 1 (Nov. 12, 2013)) - Accepted Version
See Usage Policy.

321Kb
[img] PDF (v. 2 (Sept. 26, 2014)) - Updated Version
See Usage Policy.

210Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160321-140122265

Abstract

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 effciently: (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.


Item Type:Report or Paper (Working Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1311.2655arXivWorking paper
Additional Information:ArXiv: Submitted on 12 Nov 2013 (v1), last revised 26 Sep 2014 (this version, v2)). This research was supported by NSF grants CNS-0846025, EPAS-1307794, and CCF-1101470, along with a Linde/SISL postdoctoral fellowship.
Funders:
Funding AgencyGrant Number
NSFCNS-0846025
NSFCCF-1101470
NSFEPAS-1307794
Linde/SISL postdoctoral fellowshipUNSPECIFIED
Subject Keywords:Computer Science and Game Theory
Record Number:CaltechAUTHORS:20160321-140122265
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160321-140122265
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65550
Collection:CaltechAUTHORS
Deposited By: Susan Vite
Deposited On:23 Mar 2016 23:15
Last Modified:23 Mar 2016 23:15

Repository Staff Only: item control page