How consistent are your choice data?

Economists have a long tradition of specifying their models in terms of axioms, or restrictions on data which must be obeyed for it to be consistent with a particular model. One common axiom is that a binary relation on some set Z must be acyclic. Acyclic, antisymmetric relations have the important property that they can be extended to complete linear orders. As such, we can interpret such relations as being an incomplete observation of some consistent ordering on Z. The most famous use of this result is Strong Axiom of Revealed Preference (SARP), which shows that a set of choice data can be considered consistent with the maximization of some underlying preference ordering if and only if the generated revealed preference relation is acyclic. Caplin and Dean [2008] provide an example in which the acyclic property is central to characterising a model of search and choice. One problem with the axiomatic method of characterizing a model is that it provides only a very stark measure of whether a data set is consistent with a particular model: data either does or does not violate the stated axioms. There is no concept of whether a data set is `close' to satisfying an axiom set. Recognising this problem, several authors have proposed measures of how `far away' a data set is from satisfying a set of axioms (see Afriat [1972], Varian [1991], and Houtman and Maks [1985]). The Houtman and Maks measure is based on finding the largest subset of observations which satisfy the axiomatic system. While this measure is not without its problems (see Choi et al. [2006] for a discussion), it has the advantage of being applicable to wide variety of data sets and axiomatic systems. In contrast, the Afriat and Varian measures are only applicable to data obtained by observing choices derived from different budget sets. One possible reason that the Houtman and Maks measure has not been widely adopted is that it can be extremely computationally intensive (see Choi et al. [2007] and Fisman et al. [2007] for examples in which computational constraints have been binding). The innovation in this paper is to show that the problem of finding the maximal acyclic subset can be reduced to a well-studied problem within the computer sciences and operations research: the Minimum Set Covering Problem (MSCP). While MSCP is NP-hard in the strong sense, there are a wide variety of algorithms built to solve this problem (see Caprara, Toth, and Fischetti [2000]), which can be used to find the maximal acyclic set quickly and exactly for reasonably-sized data sets. This paper describes some of these algorithms, and a companion website (www.danielmartin.com) provides code which adapts them to the Houtman-Maks measure. Furthermore, we demonstrate that with this approach, the measure can be calculated in under a second for cases that were previously insoluble. This result opens up the possibility that the Houtman-Maks measure can be developed into a more formal statistical test of axiomatic consistency.