Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2014 | public
Book Section - Chapter Open

On the Existence of Low-Rank Explanations for Mixed Strategy Behavior


Nash equilibrium is used as a model to explain the observed behavior of players in strategic settings. For example, in many empirical applications we observe player behavior, and the problem is to determine if there exist payoffs for the players for which the equilibrium corresponds to observed player behavior. Computational complexity of Nash equilibria is important in this framework. If the payoffs that explain observed player behavior requires players to have solved a computationally hard problem, then the explanation provided is questionable. In this paper we provide conditions under which observed behavior of players can be explained by games in which Nash equilibria are easy to compute. We identify three structural conditions and show that if the data set of observed behavior satisfies any of these conditions, then it can be explained by payoff matrices for which Nash equilibria are efficiently computable.

Additional Information

© 2014 Springer International Publishing Switzerland. This research was supported by NSF grants CNS-0846025, EPAS-1307794, and CCF-1101470, along with a Linde/SISL postdoctoral fellowship.

Attached Files

Submitted - 1311.2655v2.pdf


Files (215.7 kB)
Name Size Download all
215.7 kB Preview Download

Additional details

August 19, 2023
August 19, 2023