CaltechAUTHORS
  A Caltech Library Service

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

Barman, Siddharth and Bhaskar, Umang and Echenique, Federico and Wierman, Adam (2014) On the Existence of Low-Rank Explanations for Mixed Strategy Behavior. In: Web and Internet Economics. Lecture Notes in Computer Science. No.8877. Springer , Cambridge, MA, pp. 447-452. ISBN 978-3-319-13129-0. https://resolver.caltech.edu/CaltechAUTHORS:20150615-083251191

[img] PDF - Submitted Version
See Usage Policy.

210Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20150615-083251191

Abstract

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1007/978-3-319-13129-0_38DOIArticle
http://link.springer.com/chapter/10.1007%2F978-3-319-13129-0_38PublisherArticle
http://arxiv.org/abs/1311.2655arXivDiscussion Paper
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.
Funders:
Funding AgencyGrant Number
NSFCNS-0846025
NSFEPAS-1307794
NSFCCF-1101470
Linde/SISL postdoctoral fellowshipUNSPECIFIED
Subject Keywords:equilibrium computation, revealed preference, matrix rank
Series Name:Lecture Notes in Computer Science
Issue or Number:8877
Record Number:CaltechAUTHORS:20150615-083251191
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20150615-083251191
Official Citation:On the Existence of Low-Rank Explanations for Mixed Strategy Behavior Barman, Siddharth (et al.) 2014, Web and Internet Economics, 447-452
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:58232
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:15 Jun 2015 18:28
Last Modified:03 Oct 2019 08:33

Repository Staff Only: item control page