  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 an important
consideration in this framework. If the instance of the model that explains
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 Nash equilibrium is a reasonable explanation for
strategic behavior, i.e., 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 is consistent with payoff
matrices for which the observed Nash equilibria could have been computed
efficiently. Our conditions admit large and structurally complex data sets of
observed behavior, showing that even with complexity considerations, Nash
equilibrium is often a reasonable model.
