FBE Research Report KBI_1204
Publication date:
2012-02-01
Publisher:
KU Leuven - Faculty of Business and Economics; Leuven (Belgium)
Author:
Talla Nobibon, Fabrice
Smeulders, Bart ; Spieksma, Frits
Keywords:
Generalized axiom of revealed preference, Directed graph, Strongly connected components, Computational complexity, Microeconomics
Abstract:
This note presents an algorithm for testing the generalized axiom of revealed preference in time O(n2), where n is the number of observations in a given data set. Furthermore, we prove a lower bound of (n log n) on the running time of any algorithm for testing different axioms of revealed preference.