Descriptive complexity and revealed preference theory

Adam Galambos

Mathematical Social Sciences, 2019, vol. 101, issue C, 54-64

Abstract: This paper formalizes revealed preference theory using the notion of Ramsey eliminability in logic, and shows how the language required to state a revealed preference axiom for some choice theory is closely connected with the computational tractability of testing that theory. The connection is made through results in descriptive complexity theory, a relatively new field in finite model theory. It is shown that checking whether observed choices of players in normal form games are Nash rationalizable is an NP-complete problem. This also means that there does not exist an analogue (in a precise sense) of the Strong Axiom of Revealed Preference for Nash equilibrium.

Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489619300538
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matsoc:v:101:y:2019:i:c:p:54-64

DOI: 10.1016/j.mathsocsci.2019.06.006

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().