×

Descriptive complexity and revealed preference theory. (English) Zbl 1426.91087

Summary: 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.

MSC:

91B08 Individual preferences
91B06 Decision theory
91A80 Applications of game theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Backhouse, R., (Founder of Modern Economics: Paul A. Samuelson: Volume 1: Becoming Samuelson, 1915-1948. Founder of Modern Economics: Paul A. Samuelson: Volume 1: Becoming Samuelson, 1915-1948, Oxford Studies in History of Economics (2017), Oxford University Press), https://books.google.com/books?id=65-PDgAAQBAJ
[2] Benthem, J. F.A. K.v., Ramsey eliminability, Studia Logica, 37, 4, 321-336 (1978), http://www.jstor.org/stable/20014913 · Zbl 0402.03014
[3] Carvajal, A.; Ray, I.; Snyder, S., Equilibrium behavior in markets and games: testable restrictions and identification, J. Math. Econom., 40, 1-2, 1-40 (2004) · Zbl 1059.91026
[4] Chambers, C.; Echenique, F., Revealed Preference Theory. Econometric Society Monographs (2016), Cambridge University Press, https://books.google.com/books?id=4fSTCwAAQBAJ · Zbl 1335.91002
[5] Chambers, C. P.; Echenique, F.; Shmaya, E., General revealed preference theory, Theor. Econ., 12, 2, 493-511 (2017) · Zbl 1396.91105
[6] Cook, S. A., The complexity of theorem-proving procedures, (Proceedings of the Third Annual ACM Symposium on Theory of Computing (1971), Association for Computing Machinery), 151-158 · Zbl 0253.68020
[7] Fagin, R., Contributions to the model theory of finite structures (1973), U.C. Berkeley, Ph.D. thesis
[8] Galambos, A., Revealed preference in game theory (2004), University of Minnesota, Ph.D. thesis
[9] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freeman and Company · Zbl 0411.68039
[10] Gradwohl, R.; Shmaya, E., Tractable falsifiability, Econ. Philos., 31, 2, 259-274 (2015)
[11] Hands, D. W., Reflection Without Rules: Economic Methodology and Contemporary Science Theory (2001), Cambridge University Press
[12] Hintikka, J., Ramsey sentences and the meaning of quantifiers, Philos. Sci., 65, 2, 289-305 (1998), http://www.jstor.org/stable/188262
[13] Houthakker, H. S., Revealed preference and the utility function, Econ. NS, 17, 66, 159-174 (1950)
[14] Immerman, N., Relational queries computable in polynomial time, (14th Symposium on Theory of Computation (1982), ACM), 147-152
[15] Immerman, N., Descriptive Complexity: A Logician’s Approach to Computation, 42 (1995), Notices of the American Mathematical Society · Zbl 1042.68604
[16] Immerman, N., Descriptive Complexity. Graduate Texts in Computer Science (1999), Springer · Zbl 0918.68031
[17] Matzkin, R. L.; Richter, M. K., Testing strictly concave rationality, J. Econom. Theory, 53, 287-303 (1991) · Zbl 0719.90009
[18] Ramsey, F., Theories, (Braithwaite, R., The Foundations of Mathematics and Other Logical Essays. The Foundations of Mathematics and Other Logical Essays, No. v. 5 in The international library of philosophy: Philosophy of logic and mathematics (1931), Routledge and Kegan Paul) · Zbl 0002.00501
[19] Richter, M. K., Revealed preference theory, Econometrica, 34, 635-645 (1966) · Zbl 0158.38802
[20] Samuelson, P. A., Consumption theorems in terms of overcompensation rather than indifference comparisons, Economica, 20, 77, 1-9 (1953), http://www.jstor.org/stable/2550984
[21] Sneed, J., The logical structure of mathematical physics (1971), Synthese library, Reidel · Zbl 0324.02001
[22] Sprumont, Y., On the testable implications of collective choice theories, J. Econom. Theory, 93, 205-232 (2000) · Zbl 0976.91014
[23] Vardi, M. Y., Complexity of relational query languages, (14th Symposium on Theory of Computation (1982), ACM), 137-146
[24] Varian, H. R., The nonparametric approach to demand analysis, Econometrica, 945-973 (1982) · Zbl 0483.90006
[25] Yanovskaya, E., Revealed preference in non-cooperative games, Math. Methods Soc. Sci., 24, 13 (1980), in Russian · Zbl 0484.90005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.