Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
88,561 characters · 21 sections · 42 citation commands
Recovering Preferences from Finite Data
\address[Chambers]{Department of Economics, Georgetown University} \address[Echenique]{Division of the Humanities and Social Sciences, California Institute of Technology} \address[Lambert]{Department of Economics, Massachusetts Institute of Technology}
This paper provides conditions that guarantee asymptotic, large-sample, nonparametric recoverability of preferences from binary choice data. We imagine an experimenter, Alice, offering a sequence of binary choice problems to a subject, Bob. For each choice problem, Bob is presented with a pair of alternatives and is asked to choose one (for example, alternatives could be lotteries over a collection of prizes). Alice wants to ensure that, if she observes Bob on sufficiently many choice problems, then she can approximate his preference over the entire set of alternatives to an arbitrary degree of precision. We study when this approximation possible. The goal is to have conditions that are easy to check and apply broadly.
Our approach is two-pronged. Our first model is anchored in the classical revealed preference tradition, whereby Alice seeks to rationalize the choice data exactly. The model is deterministic. Alice designs a fixed experiment, and hypothesizes that Bob chooses perfectly in accordance with his preference. Our second model is statistical. The selection of experiments is random, and Alice supposes that Bob's choices are either observed with some error, or made with error. In both models, we provide conditions for the underlying data-generating preference to be recovered in the limit as the available data grows large. These conditions concern both the experimental design and the preference environment being considered.
The main substantive condition is the local strictness of preferences, a property first described by border1994dynamic. Local strictness generalizes the familiar notion of local nonsatiation. A locally strict preference means that whenever $x$ is at least as good as $y$, there are alternatives $x'$ and $y'$, near $x$ and $y$ respectively, and for which $x'$ is strictly better than $y'$. We prove that, together with technical conditions, local strictness ensures the convergence of any sequence of rationalizing preferences to the unique underlying preference governing the subject's choices as the number of observations goes to infinity. In the statistical model, we introduce an estimator based on minimizing the Kemeny distance to the observed choices. Again imposing local strictness, we prove that this estimator is consistent, and provide general convergence rates.
The usefulness of our results is illustrated with applications to expected-utility theory and other environments where preferences are defined from utility functions; to monotone preferences in consumption theory, preferences over menus, and exponential discounting in intertemporal choice. In all these applications, we show how large finite experiments can approximate a preference of the appropriate kind.
Our approach works with the choice-theoretic notion of partial observability, as in afriat: when Bob is presented with a choice, he must select no more than one alternative. Therefore, choosing one alternative over another does not preclude the possibility that Bob would have been equally happy with the other alternative. In Afriat's case, partial observability has wide-ranging implications, famously rendering the concavity of utility nontestable.\footnote{\citet*{CES} provide a discussion of what partial observability entails.} Partial observability generally leads to partial identification and hinders estimation. In our framework, preferences can still be fully learned in spite of their partial observability.
We allow for very general sets of preferences, which translate into a “model-free” approach. If, say, Alice is interested in exponential discounting, then she can estimate a preference without the need to impose this assumption on the data. If Bob is indeed discounting exponentially, then the preference estimates are guaranteed to converge to a preference that follows exponential discounting. And if the preference estimates do not converge to such a preference, then Alice may conclude that the exponential discounting hypothesis is incorrect. She can then evaluate the degree to which Bob's preference diverges from exponential discounting. The model-free aspect is also present in the statistical model: Alice can be agnostic about how the alternatives presented to subjects are sampled, and how subjects are assumed to make mistakes. Specifically, the estimator does not require knowledge of sampling or error probabilities.
Overall, our framework combines the elements of different traditions in economic modeling: the nonparametric approach and the finite amount of data in revealed preference analysis, the pairwise comparisons in decision theory and experiments (both online and laboratory), and the source of random errors in empirical research and econometrics.
The paper proceeds as follows. The remainder of this section reviews related works. Section (ref) describes the model. Section (ref) provides the main results. Sections (ref) and (ref) put these results to work in several economic environments. Section (ref) concludes with a discussion. Proofs are relegated to the appendices.
The literature on revealed-preference theory has been primarily concerned with the question of whether observed behavior conforms with standard models in economic theory. The workhorse of this literature, Afriat's theorem afriat,varian1982nonparametric, works with the classical model of consumer demand with linear budgets and finite data, and has been expanded in many directions.\footnote{ For example, matzkin1991axioms and forges2009 work with nonlinear budget sets, \citet*{chavas1993generalized} and \citet*{nishimura} work with general choice problems. Some extensions were also developed for multiperson equilibrium models, as in \citet*{brown1996testable}. } This line of research focuses for the most part on constructing revealed preference tests, and discussions of preference recoverability---as, for instance, in \citealp*{varian1982nonparametric}, or more recently \citealp*{cherchye2011revealed}---deal with bounding the sets of possible rationalizing preferences.
Closer to our work, in the context of consumer demand with linear budgets, mascolell78 introduces an “income-Lipschitz” condition and shows that, under this and a boundary condition, any sequence of preferences that rationalizes a sufficiently rich sequence of observations converges to the unique preference that rationalizes the entire demand function. forges2009 derive the analog of mascolell78's results for nonlinear budget sets. In a model of dynamic asset markets, kubler2015identification derive conditions that permit the identification of utilities and beliefs of a subjective expected utility maximizer, and show that preference estimates from finite data converge to the unique underlying preference as the number of observations grows large. \citet*{polemarchakis2016identification} give conditions under which the identification of preferences is possible, and demonstrate the convergence of preferences estimated from finite data to the unique underlying preference. More recently, \citet*{polemarchakiskubler2020} consider identification of preferences from finite data, with emphasis on applications to demand and aggregate demand. As in the above works, our paper concerns the convergence of preferences that rationalize finite but unbounded data to the underlying data-generating preference, following large sample theory. We differ in three ways: first, we focus on data from pairwise choices instead of choice from budgets; second, we work with general environments beyond choice over commodities; third, we provide a broad sufficient condition on the class of preferences under consideration. Because we abstract away from specific economic environments, our results are applicable across different domains, such as choice of menus, under uncertainty, of intertemporal streams, lotteries, or consumption bundles.
Experimentalists and decision theorists also have an obvious interest in preference recovery from pairwise choices, but little is known about the behavior of preference estimates from finite data. Decision theory works often include a discussion of identification, but presume access to the agent's full preference relation. In contrast, we are interested to know if and when the preference relation can be inferred from the data. In demand theory, there are many studies devoted to the problem of identification---known as the integrability problem---assuming access to a demand function defined on all prices. matzkin2006identification considers economy-wide data, and uses equilibrium as a means to identify consumers' utilities. In recent work, gorno studies the general problem of identification under partial observability. Gorno provides conditions on decision problems and sets of admissible preferences to ensure identification. Our research diverges from his, and from other studies of identification and integrability, in that we focus on large-sample estimation from finite data.
Another stream of literature combines nonparametric econometric methods with revealed preference theory. In demand analysis, \citet*{blundell2008best} design a statistical test for the revealed preference conditions to be satisfied. Observing that demand responses to price changes can be represented by a set of moment inequalities, they appeal to results on moment inequality estimators by \citet*{manski2003partial}, \citet*{chernozhukovhongtamer} and \citet*{andrews2009validity}. However, these results on partial identification do not apply to the general environments we consider. Instead, we work with the classical large-sample theory for $M$-estimators amemiya1985advanced,newey1994large but derive conditions for consistency without making additional compactness and equicontinuity assumptions (these assumptions are particularly substantial in a nonparametric estimation problem like ours, see Section (ref) for a detailed discussion). \citet*{halevy2018parametric} develop a method for estimating parametric models by minimizing the incompatibility of choice behavior with the proposed model, in the same spirit as our Kemeny-distance estimator. In contrast to our work, their methodology assumes data on choices from linear budgets, and adopts a money-metric version of Afriat's and Varian's “critical cost efficiency index” as a measure of distance. A crucial component of their analysis is to decompose measures in loss due to parametric misspecification, and loss due to inconsistency with rationality. More closely related to our paper, matzkin2003nonparametric and \citet*{blundell2010stochastic} consider identification in an econometric model of stochastic demand data (see matzkin2007heterogeneous, for a general discussion). Recently, \citet*{basu2018learnability} investigate the learnability of four standard models of choice under uncertainty using the notion of Probably Approximately Correct (PAC) learning from computational learning theory. \citet*{basu2019learnability} applies several other measures of model complexity to a study of stochastic choice.
Finally, a literature in political science (\citealp*{poolerosenthal1985}, \citealp*{jackman_2001}, \citealp*{clinton_jackman_rivers_2004}, are seminal) focuses on binary choice data (roll-call votes), but considers specific parametric models of spatial voting, and uses Bayesian methods for the most part. Our results are broadly applicable to the same data as in this literature.
The model features an experimenter, Alice, and a subject, Bob. Bob has a preference over a set of alternatives $X$, which is a topological space. Alice would like to learn Bob's preference through the device of a choice experiment.\footnote{Such experiments, done on a large scale, with large sample size, include for example \citet*{vonGaudecker2011}, \citet*{chapman2018econographics} and \citet*{falkQJE2018}. Alternatively, we may think of Alice as a researcher, and Bob an individual she has observed in the field. For example, Bob could be a congressman who votes among pairs of competing bills poolerosenthal1985.}
By preference relation or simply preference we mean a binary relation $\succeq$ over $X$ that is continuous and complete.\footnote{Completeness means that for all pairs of alternatives $(x,y)$, $x \succeq y$ or $y \succeq x$. Continuity means that ${\succeq}$ as a subset of the product space $X \times X$ is closed; more intuitively, if $x$ is not preferred to $y$, then $x'$ is also not preferred to $y'$ for all pairs $(x',y')$ in the vicinity of $(x,y)$. Completeness is standard and continuity is a necessary regularity condition, without it, no meaningful inferences can be made with any finite amount of data.} In formal terms, $\succeq$ is the set of pairs $(x,y) \in X \times X$ such that $x$ is at least weakly preferred to $y$, denoted by $x \succeq y$. Associated to any given preference ${\succeq}$ are its asymmetric part ${\succ}$ (strict preference) and its symmetric part ${\sim}$ (indifference); that is, $x \succ y$ means that $x \succeq y$ but $y \nsucceq x$, while $x \sim y$ indicates that both $x \succeq y$ and $y \succeq x$. We do not require that preferences be transitive.
If Alice's goal is to infer Bob's preference from his behavior, it is clear that she must somehow discipline the set of preferences being considered. With partial observability, it is very easy to find a preference that rationalizes empirical data. For example, complete indifference rationalizes any observed behavior. Throughout the paper, $\mathcal{P}$ denotes the class of preferences being considered; we think of $\mathcal{P}$ as a set that encompasses the possible preferences the subject may have. We refer to a pair $(X,\mathcal{P})$ as a preference environment.
Alice collects information about Bob through a finite experiment, in which Bob confronts a fixed number of binary choice problems. In each binary choice problem, Bob is presented with an unordered pair of alternatives, and is asked to choose exactly one of the two alternatives. An experiment of size $n$ is represented by a collection $\Sigma_n = \{B_1, \dots, B_n\}$, where $B_k = \{x_k,y_k\}$ is an unordered pair of alternatives that captures a binary choice problem. Note that binary choices are used for simplicity: one could have more than two choices instead.
To study the large-sample properties of estimated preferences, we consider not just one experiment, but a set of growing experiments indexed by their size, of the form $\{\Sigma_1, \Sigma_2, \dots\}$, where $\Sigma_n$ is an experiment of size $n$ and $\Sigma_{n} \subset \Sigma_{n+1}$. In the sequel, $\Sigma_n$ always denotes an experiment of size $n$, and the inclusion property $\Sigma_{n} \subset \Sigma_{n+1}$ is implicitly assumed. We use the abbreviated notation $\{\Sigma_n\}$ to denote a set of (growing) experiments.
The behavior of a subject who decides over binary choice problems is encoded in a single-valued choice function $c$ that maps unordered pairs of alternatives to alternatives. It records, for every possible binary choice problem $\{x,y\} \subset X$, the alternative $c(\{x,y\}) \in \{x,y\}$ that is chosen. We refer to $c$ as the choice function, and impose no a priori restrictions on choice functions.
We follow two traditions in economic modeling. The first tradition is classical revealed preference theory, in which the choice problems of an experiment are selected arbitrarily, and the experimenter seeks to exactly rationalize observed behavior, as in the classical works of afriat, mascolell78, and varian1982nonparametric. In this theory, Bob is assumed to possess a preference and to make choices that comply perfectly with this preference. Alice looks for a preference that fits exactly the empirical observations. However, this theory does not account for errors, while empirical work often tries to accommodate errors.
The second tradition tackles this problem by imposing a statistical model on the subject's choices. The subject is presented with choices drawn at random, either because the experimental design is explicitly random (as, for example, in \citealp*{ahn2014}, \citealp*{choi2014more}, \citealp*{carvalho2016poverty}, or \citealp*{carvalho2017complexity}), or because the experimenter uses observational data in which she has no control over the problems the subject faces. In the statistical tradition, Alice continues to assume that Bob has an underlying preference, but she allows for his behavior to deviate from what his preference dictates. Alice looks for a preference that fits the observed behavior the best.\footnote{See also \citet*{grant2016theory} for a general study of experimental designs that are tolerant to small deviations in the subject's perception of the experiments.}
In a revealed preference model, experiments are designed arbitrarily by the experimenter. The primitives are the preference environment $(X,\mathcal{P})$, and the set of experiments $\{\Sigma_n\}$. We refer to this model by the triple $(X,\mathcal{P},\{\Sigma_n\})$.
Recall that when presented with a pair of alternatives $\{x,y\}$, Bob is asked to choose between $x$ and $y$---he cannot choose both. In the language of \citet*{CES}, our model of choice features partial observability, as in the original work of afriat.\footnote{The tradition in revealed preference theory (and in studies of integrability) prior to Afriat was to exactly rationalize a demand function. In Afriat's model, the observed choices are contained in the rationalizing demand, and in consequence concavity of utility is not testable. See \citet*{CES} for a detailed discussion and exploration of the consequences of partial observability.} With partial observability, the appropriate concept of rationalization is weak rationalization: Given a choice function $c$ describing the subject's behavior, and given an experiment $\Sigma_n$, we say that a preference ${\succeq}$ weakly rationalizes the observed choices on $\Sigma_n$, or simply rationalizes the observed choices on $\Sigma_n$, if the experiment outcomes are compatible with the subject's preference: for every $\{x, y\} \in \Sigma_n$, $c(\{x, y\}) \succeq x$ and $c(\{x, y\}) \succeq y$. Similarly, we say that ${\succeq}$ rationalizes the choice function $c$ if, for every $x, y \in X$, $c(\{x, y\}) \succeq x$ and $c(\{x, y\}) \succeq y$. Hence, weak rationalization does not allow for Bob to choose in contradiction with his preference, but allows for Bob not to reveal the totality of what his preference implies.
In a statistical preference model, experiments are composed of randomly-selected choice problems. More precisely, the choice problems $B_1=\{x_1,y_1\}, \dots, B_n=\{x_n,y_n\}$ that make up the experiment $\Sigma_n$ are generated by drawing the alternatives $x_k, y_k$ in each $B_k$ at random from $X$, independently and identically according to some probability measure $\lambda$ ($X$ is endowed with the usual Borel $\sigma$-algebra). We also use $\lambda$ to denote the product measure on $X\times X$.
Bob's behavior is guided by his preference, but in every choice problem where Bob is not indifferent, he may make a mistake by choosing an alternative that is not preferred. The corresponding choice function is therefore random. It is determined by an error probability function $q :\mathcal{P}\times X\times X\rightarrow [0,1]$ that quantifies the extent to which a subject is prone to making errors. Assume that, for all ${\succeq} \in \mathcal{P}$, $q({\succeq}; \cdot,\cdot)$ is measurable on $X \times X$.
When a subject with preference ${\succeq}$ confronts the binary choice problem $\{x,y\}$, he chooses $x$ over $y$ with probability $q({\succeq}; x, y)$, and chooses $y$ over $x$ with the complementary probability. We assume that if $x \succ y$ then $x$ is more likely to be chosen, that is, $q({\succeq};x,y) > 1/2$. When $x \sim y$ we make no particular assumption.\footnote{Strictly speaking, an experiment $\Sigma_n$ is now a multiset, and Bob could in principle face the same choice problem more than once. The model would then have to take a stand on whether Bob's choices are constant over such repetitions, or give rise to independent choice draws. Our assumptions, however, guarantee that repetitions occur with probability zero. So these modeling assumptions are irrelevant.}
The primitives of a statistical preference model are the preference environment given by $X$ and $\mathcal{P}$, the probability measure $\lambda$ according to which alternatives are drawn, and the error probability function $q$. We refer to this model by the tuple $(X, \mathcal{P}, \lambda, q)$.
This section provides general results on the convergence of preferences. Throughout, we use the following notion of convergence: a sequence of preferences $\{ {\succeq}_n\}_{n \in \mathbf{N}}$ converges to a preference ${\succeq}^*$, written ${\succeq}_n \rightarrow {\succeq}^*$ for short, when the following two conditions are satisfied:
Under the assumptions we shall impose, these conditions define convergence in the closed convergence topology. Throughout, we endow the space of preferences and binary relations with this topology. The closed convergence topology is a common topology for spaces of sets, such as binary relations, and is the standard topology used for spaces of preferences kannai1970continuity,HILDENBRAND1970161. It is particularly well suited to the concept of partial observability; we discuss the choice of topology in Section (ref).
Under conditions that are satisfied in our model, the closed convergence topology on the space of preferences is metrizable, making it possible to quantify approximations and speak of convergence rates. We fix, and denote by $\rho$, one compatible metric. In particular, if $X$ is compact and metrizable, then we can choose as $\rho$ the usual Hausdorff metric for the product space $X \times X$. The notion of closed convergence then coincides with the notion of Hausdorff convergence.\footnote{Our results allow for $X$ to be only locally compact. In this case, $\rho$ may still be chosen to coincide with the Hausdorff metric on subsets of the product space $X_{\infty} \times X_{\infty}$, where $X_{\infty}$ is the one-point compactification of $X$ together with some metric generating $X_{\infty}$. See aliprantis2006infinite for details.} We connect the topology on preferences with familiar topologies on spaces of utility functions in Section (ref), and, for the case of parameterized classes of preferences, with metrics on the parameter space in Section (ref).
Our first main result states that convergence of rationalizing preference obtains under certain assumptions on the model primitives. Given a revealed preference model $(X,\mathcal{P},\{\Sigma_n\})$, consider the following assumptions.
\newlist{condrevealed}{enumerate}{1} \setlist[condrevealed]{label= Assumption \arabic*. , ref=(\arabic*), wide=25pt,widest=99,leftmargin=*}
Assumption (ref) puts a necessary structure on the set of alternatives. It is satisfied in many common economic environments, as we show in Sections (ref) and (ref).
The next assumption disciplines the class of the preferences being considered. The central property that allows for meaningful preference recovery is local strictness. This property rules out “thick” indifference curves, in the spirit of the local nonsatiation property of consumer theory. A preference $\succeq$ is locally strict if for every $x, y \in X$ with $x \succeq y$, and every neighborhood $V$ of $(x,y)$ in $X\times X$, there exists $(x',y')\in V$ with $x' \succ y'$ border1994dynamic.
The requirement that $\mathcal{P}$ be closed is essential. For example, suppose that $X=[0,1]$, that $\mathcal{P}$ is the set of all locally strict preferences, and that Bob prefers larger numbers, so that $x \succeq^* y$ if and only if $x \ge y$. Let $\succsim_k$ be the preference defined by the piece-wise linear utility function $u_k$ with $u_k(0)=u_k(1)=1$ and $u_k(1/k)=0$; so, $u_k(x)=1-k x$ for $x \le 1/k$ and $u_k(x)=-1/(k-1) + k/(k-1) x$ for $x > 1/k$. Note that $\mathcal{P}$ includes $\succeq^*$ and all $\succsim_k$ for $k \ge 2$. Consider any set of growing experiments $\{ \Sigma_n \}$ in which the choice problems use non-zero alternatives. In every experiment $\Sigma_n$, Bob's choices, if Bob chooses according to his preference, can be rationalized with $\succsim_k$ for $k$ large enough. As $k$ grows large, $\succsim_k$ does converge, but to a preference distinct from $\succeq^*$, so that there is information regarding Bob's preference that is never fully learned. This problem owes to the fact that the set of locally strict preferences on $[0,1]$ is not closed: the limiting preference $\succsim_\infty$ is such that $x \succsim_\infty y$ if $x \ge y$ or if $x=0$, it is thus not locally strict.
This simple example illustrates a more general fact. No matter the subject's underlying preference and the choice of growing experiments, one can always find locally strict preferences that perfectly rationalize the observations of the subject who chooses in accordance to his preference, and yet, as the size of the experiment grows large, converge to total indifference among all alternatives.\footnote{See Section (ref) in the Online Appendix.} The rationalizing preferences then convey no information on the features of the subject's preference that are not directly observed. Therefore closedness is not a mere technical assumption. It is however satisfied in several important cases. In Sections (ref) and (ref), we establish that the relevant set locally strict preferences is closed in the major preference environments.
Finally, the choice problems in the experiments must be sufficiently many, and sufficiently diverse, so that observed behavior on all these choice problems can effectively probe the subject's preference. A set of experiments $\{ \Sigma_n \}$, with $\Sigma_n = \{B_1, \dots, B_n\}$, is called exhaustive when it satisfies the following two properties:
The first property imposes that the alternatives that are used in the set of experiments sample the space of alternatives appropriately. The second property states that the experimenter should be able to elicit the subject's choices over all alternatives used in her experiments. Note that denseness is the only real constraint: starting from a countable dense set of alternatives, one can always construct an exhaustive set of experiments via routine diagonalization arguments.\footnote{In the more general case where choices are made over more than two proposed alternatives, the analog exhaustiveness property would require that any comparison between any two alternatives used in the set of experiments is eventually observed or inferred in a large enough experiment.}
The importance of having a dense set of alternatives is clear: without it, the characteristics of the preference remains unobservable on an open set, and for general classes of preferences, knowledge of the preference outside this set does not suffice to infer those unobservable characteristics.
The importance of local strictness for our results hinges on the fact that, for an exhaustive set of experiments, and any two distinct locally strict preferences $\succeq_A$ and $\succeq_B$ of two subjects $A$ and $B$ respectively, there always is at least one experiment for which subject $A$ behaves differently from subject $B$, thereby allowing the experimenter to distinguish between these two preferences. Thus, with local strictness, a false hypothesis will eventually be demonstrated to be false, whereas without it, too many preferences can be consistent with the data. This fact is stated formally in Lemma (ref).
The proof of Lemma (ref) is in Appendix (ref).
Under the above assumptions, we establish the convergence of rationalizing preference estimates.
The proof of Theorem (ref) is in Appendix (ref).
Theorem (ref) asserts that if, in each experiment, the data can be rationalized by some preference in the class $\mathcal{P}$, then there always exists one preference in $\mathcal{P}$ that rationalizes the choices made over all the experiments, and most importantly, there exists only one such preference. The observations are exactly as if the subject's choices were guided by this particular preference, which can be obtained as the limit of the rationalizations as experiments grow in size.
In particular, if we postulate the existence of a preference $\succeq^* \in \mathcal{P}$ according to which the subject chooses on any given decision problem, then no matter the selection of the rationalizing preferences, they always converge to $\succeq^*$.
When the subject makes mistakes, looking for a preference that perfectly rationalizes his behavior is moot---a rationalizing preference in the class $\mathcal{P}$ may not exist. Instead, we introduce a simple estimator that approximately rationalizes the observed data, based on minimization of the Kemeny distance kendall1938,kemeny1959.
The estimator results from a two-step procedure. Let us look at an experiment of size $n$, $\Sigma_n$, drawn at random according to the experimental design. Let $c$ be the choice function that captures the choices of the subject, which is also random. First, from the choices observed on $\Sigma_n$, a revealed preference relation is constructed that captures these choices exactly. This revealed preference relation, denoted $R_n$, is defined by $x \mathrel{R}_n y$ for all $\{x,y\} \in \Sigma_n$ such that $c(\{x,y\}) = x$---that is, $x \mathrel{R}_n y$ when the subject chooses $x$ in the choice problem $\{x,y\}$. Note that $R_n$ is sparse, as it only conveys information on the alternatives used in $\Sigma_n$. Secondly, the estimated preference ${\succeq}_n$ is chosen to minimize the distance $d_n({\succeq}, R_n)$ between the revealed preference relation just defined, and a preference in ${\succeq}\in \mathcal{P}$;
Distance $d_n$ is taken to be a version of the Kemeny distance, a rank distance measure, defined by
In words, $d_n({\succeq}, R_n)$ averages the number of mistakes made by the subject on $\Sigma_n$ if his underlying preference is $\succeq$. We refer to this estimator as the Kemeny-minimizing estimator.\footnote{$ \left | R_n \setminus {\succeq} \right | $ denotes the number of elements in $R_n \setminus {\succeq}$. The Kemeny distance between two finite binary relations $R$ and $R'$ is usually defined as $ \left | R \mathrel{\Delta} R' \right | $, where $\Delta$ is the symmetric difference. Note that if $(x,y)\in {\succeq}\setminus R_n$ and $\{x,y\}\in \Sigma_k$, Then $(y,x)\in R_n\setminus {\succ}$. In our model, alternatives are strictly ranked by $R_n$ and by $\succeq$ with probability one. Hence,
with probability one, which justifies our Kemeny distance terminology.}
\newlist{condstat}{enumerate}{1} \setlist[condstat]{label= Assumption \arabic*'. , ref=(\arabic*'), wide=25pt,widest=99,leftmargin=*}
For a statistical preference model $(X,\mathcal{P},\lambda,q)$, we shall need three assumptions. Assumptions (ref) and (ref) on the preference environment $(X,\mathcal{P})$ remain unchanged. In particular, we continue to assume that the preferences under consideration are locally strict, local strictness being the key unifying property between the revealed and statistical preference models.
We think of Assumption (ref), below, as the analog of Assumption (ref) for randomized experiments. Its main import is that we almost never draw a decision problem that makes the subject indifferent. It also imposes that the sampling distribution have full support.\footnote{Full support means that there is no proper closed subset of the sample space that has probability 1.} Analogously to Assumption (ref), this ensures that enough binary choice problems are probed. Full support can be relaxed for preferences that are identified on a proper subset of $X$ (as we do in Section (ref)).
Therefore, under Assumption (ref), using the same binary choice problem twice in an experiment occurs with probability zero. Together with Assumption (ref), Assumption (ref) guarantees identification in the usual sense: the distribution of the data under the true preference is different than that at any other preference.\footnote{Identification in the usual sense is implied by the identification condition for consistency, proved in Lemma (ref) of Appendix (ref). Although Assumption (ref) is crucial, it is by itself is not sufficient; for example, two preferences that differ at one point only cannot be distinguished when $\lambda$ has full support. This case is ruled out by local strictness.} This assumption allows to control the problem of partial observability. If instead indifference were to occur with positive probability, then the model would only be partially identified.
Under the above assumptions, the Kemeny-minimizing estimator is consistent. Recall that $\rho$ denotes the metric on the space of preferences.
The proof of Theorem (ref) is in Appendix (ref). One challenge is that the class of preferences may be very rich, which increases the potential for overfitting: the noise in the data may be misinterpreted as being part of the subject's true preference. And indeed, for many common spaces of alternatives, it can be shown that one can rationalize perfectly any finite set of observations by a locally strict preference. Imposing that the class of preferences be closed allows to overcome this difficulty.
We stress that Theorem (ref) requires no assumption on the error probability function $q$, other than measurability and asking that the subject be more likely to follow his preference than to make a mistake. Alice may remain agnostic about the dependence of $q$ on the underlying preference $\succeq$ and the alternatives to choose from $x$ and $y$. Moreover, aside from the independence of the draws of alternatives, the requisites on $\lambda$, stated in Assumption (ref), are minimal. In particular, calculating the Kemeny estimator does not require any assumptions on $q$ and $\lambda$. It requires Alice to specify $\mathcal{P}$, but allows her to be largely agnostic about the rest of the model.
Having the guarantee that preference estimates converge accurately, Alice may want to know how large of a sample is needed to estimate the subject's preference within a given approximation error. Our third result establishes lower bounds on the rate of convergence.
To state the result, we introduce some terminology. For any $\eta > 0$ and any $\delta \in (0,1)$, let $N(\eta,\delta)$ be the smallest value of $N$ such that for all $n \ge N$, and all underlying subject preferences ${\succeq}^* \in \mathcal{P}$, \[ \mathbf{Pr}( \rho({\succeq}^n,{\succeq}^*) < \eta ) \geq 1-\delta. \] (By convention, we let $N(\eta,\delta) = \infty$ if no finite value of $N$ exists.) That is, $N(\eta,\delta)$ is the size of the smallest experiment such that the probability that the preference estimate is $\eta$-close to the true subject preference is guaranteed to be at least $1-\delta$, no matter the true subject preference.
In addition, $\mu(.,{\succeq}^*)$ denotes the probability measure induced on the product space $X\times X$ by $\succeq^*$, $q$ and $\lambda$, as follows: \[ \mu(A,{\succeq}^*) = \int_A q({\succeq}^*;x,y) \mathop{}\!\mathrm{d} \lambda(x,y). \] Loosely speaking, $\mu(x,y,{\succeq}^*)$ represents how likely a subject with preference $\succeq^*$ is to choose $x$ over $y$ in a decision problem randomly drawn. In particular, the value of $\mu({\succeq},{\succeq}^*)$ represents the probability that the choice of a subject with preference $\succeq^*$ over a randomly drawn decision problem is consistent with the preference $\succeq$.
Finally, for $\eta > 0$, we let
Roughly, the value of $r(\eta)$ captures the smallest possible probability that a subject make a choice that is perfectly consistent with his own preference but is inconsistent with a preference at least $\eta$-distant.
To obtain convergence rates, we appeal to Vapnik-Chervonenkis theory. Given a preference environment $(X,\mathcal{P})$, for $n \in \mathbf{N}$, let $S_n$ be the largest size of the sets \[ \big\{ ( \mathbf{1}_{x_1 \succeq y_1}, \dots, \mathbf{1}_{x_n \succeq y_n}) \in \{0,1\}^n : {\succeq} \in \mathcal{P} \big\} \] over all binary choice problems $\{ x_k, y_k \} \subset X$ for $k=1,\dots,n$. We always have $S_n \le 2^n$, and, if $\mathcal{P}$ is rich enough, we may have $S_n = 2^n$. The VC dimension of $\mathcal{P}$ (abbreviation for Vapnik-–Chervonenkis dimension) is then defined as the maximum value of $n$ such that $S_n = 2^n$, and is infinite if no such maximum exists.
The consistency of the Kemeny-minimizing estimator applies no matter the VC dimension of $\mathcal{P}$, but when $\mathcal{P}$ has a finite VC dimension, and so is not too rich, we can, in addition, obtain uniform bounds on the convergence rates.
The proof of Theorem (ref) is in Appendix (ref), in which we also provide a more refined nonasymptotic bound. Of course, the value of $r(\eta)$ depends on the specific preference environment being considered. Below in Sections (ref) and (ref), we apply Theorem (ref) in different environments. \citet*{basu2018learnability} compute the VC dimension of some common models of choice, they show, in particular, that the class of expected utility, Choquet expected utility, and two-state max-min preferences have finite VC dimension.
In this section and the next, we show that the assumptions of our general framework are valid in a variety of important preference environments. This section handles preference environments derived from collections of utility functions. Specifically, we show how our assumptions may be derived from conditions on the utility representations under consideration, rather than directly imposing the assumptions on a family of preferences.
Consider a set of alternatives $X$. We are interested in sets of preferences $\mathcal{P}$ that correspond to sets of utility functions. A utility function is any function $u : X \rightarrow \mathbf{R}$. We endow the space of utility functions with the topology of compact convergence.\footnote{A sequence of functions $f_n : X \rightarrow \mathbf{R}$, $n \in \mathbf{N}$, converges compactly to a function $f$ if and only if it converges uniformly to $f$ on every compact set $K \subseteq X$. This topology on utilities is commonly used in the literature; see for example \citet*{mas1974continuous} and \citet*{border1994dynamic}.} For any utility function $u : X \rightarrow \mathbf{R}$, let $\Phi(u)$ denote the preference induced by $u$, that is, the binary relation defined by $x \mathrel{\Phi(u)} y$ if and only if $u(x) \geq u(y)$. And for any set of utility functions $\mathcal{U}$, let $\Phi(\mathcal{U}) = \{ \Phi(u) : u \in \mathcal{U} \}$ denote the image of $\mathcal{U}$.
The following proposition states conditions on the set of utility functions being considered under which our main results apply.
Proposition (ref) is an immediate implication of Theorem 8 of border1994dynamic, who establish the continuity of $\Phi$ (see Appendix (ref)).
To put Proposition (ref) to work in a simple concrete example, let us look at a case of intertemporal choice. Suppose a good can be consumed at $d \ge 2$ different dates $t_1 < \dots < t_d$. In this environment, an alternative is a vector of the Euclidean space $\mathbf{R}_{+}^d$ whose $i$-th entry indicates the amount consumed at the date $t_i$.
Fix $a, b \in \mathbf{R}_{++}$ with $a < b$ and call $\mathcal{V}$ the set of continuous functions $v:\mathbf{R}_+ \rightarrow \mathbf{R}$ that satisfy, for all $x < y$,
We interpret $v(x)$ as the utility for an immediate consumption of quantity $x$ of the good. The above inequality constrains marginal utilities to be positive and bounded above and below.
Denote by $\mathcal{U}$ the set of the utility functions $u$ over $\mathbf{R}_{+}^d$ that are written
where $v \in \mathcal{V}$, and $\delta = (\delta_1, \dots, \delta_d) \in [\varepsilon,1]^d$ is a vector of discount factors, with $\varepsilon$ an arbitrarily small positive lower bound. So, the set $\mathcal{U}$ captures discounted utility preferences with general discount factors.
Compactness of $\mathcal{U}$ follows directly from the Arzel\`{a}-Ascoli theorem (for example, Theorem 6.4 of dugundji). And clearly each utility function describes a locally strict preference, because if an individual with utility $u \in \mathcal{U}$ prefers the consumption vector $x \in \mathbf{R}_+^d$ to $y \in \mathbf{R}_+^d$, then he strictly prefers the consumption vector $x + \eta \mathbf{1}$ to $y$, for any $\eta > 0$. Therefore, we have the following corollary to Proposition (ref).
For example, one possible use of our theory is to recover discount factors from the data, or to check for distortions with respect to standard models such as exponential discounting.
Expected utility preferences are an important case of preferences derived from utility functions. Let $\Pi \equiv \{\pi_1, \ldots, \pi_d \}$ be a collection of $d \ge 2$ prizes, and let $\Delta^{d-1}$ denote the $(d-1)$-dimensional simplex $\{ p \in \mathbf{R}^d_+ : p_1 + \cdots + p_d = 1\}$. Think of each element $p$ of the simplex as a lottery over the prizes in $\Pi$, with $p_i$ the probability of getting $\pi_i$. The set of alternatives is $\Delta^{d-1}$, endowed with the Euclidean topology.
An expected utility preference stands for any preference $\succeq$ on $\Delta^{d-1}$ defined by a vector of utility indices $v \in \mathbf{R}^d$, with the property that $p \succeq p'$ if and only if $v \cdot p \geq v \cdot p'$, where $v \cdot p = \sum_{i=1}^d v_i p_i$ is the expected utility of lottery $p$. This preference is nonconstant if there is at least one pair $p, p' \in \Delta^{d-1}$ for which $p \succ p'$, or equivalently, if the vector of utility indices satisfies $v_i \ne v_j$ for some $i, j$. Of course, the vector of utility indices that defines a nonconstant expected utility preference is not unique. To ensure uniqueness, we normalize the utility indices by imposing that indices sum to zero and $v$ be on the unit sphere. That is, each preference of $\mathcal{P}$ is uniquely associated to a normalized vector of utility indices in the set\footnote{$\| \cdot \|$ denotes the Euclidean norm $\| x - y \| \equiv \sqrt{\sum_{i=1}^d (x_i - y_i)^2}$.}
The following result asserts that the standard expected utility model is situated within our framework.
The proof of Corollary (ref) is in Appendix (ref).
Note that, although we gather data over the entire set of relevant alternatives---here the whole simplex---we could use a smaller set, because expected utility preferences are identified on a small set of lotteries. By learning the preference on this smaller set, we can infer uniquely the preference on the full set. For example, suppose the alternatives that make the set of binary choice problems are from a subset of the simplex $\Delta^{d-1}$ that is convex and compact with non-empty interior, and that the family of binary choice problems are exhaustive relative to that subset. Then, Theorem (ref) continues to hold even though preferences continue to be defined over $\Delta^{d-1}$, that is, the rationalizing preference estimates continue to converge to a unique limiting preference. A similar observation applies to Theorems (ref) and (ref).
In the expected-utility model, we can further refine the convergence rates of Theorem (ref), provided that we restrict attention to error probability functions $q$ that are polynomially bounded in the following sense: there exists $C > 0$ and $k > 0$ such that, if lottery $p$ is strictly preferred to lottery $p'$ according to preference $\succeq$, then
where $u$ is the normalized vector of utility indices associated with preference $\succeq$. Equation (ref) is satisfied, for example, if $q({\succeq};p,p')$ is lower-bounded strictly above $1/2$ over all $\succeq$ and all $p,p'$ such that $p \succ p'$. It is also satisfied if the probability of making an error decreases with the difference of utilities between the two lotteries, for example if, for a continuously differentiable and nondecreasing function $f:\mathbf{R}_{+} \rightarrow \mathbf{R}_{+}$ with $f'(0) > 0$, we can write $q({\succeq};p,p') = 1/2 + f(u \cdot p - u \cdot p')$ for all $\succeq$ and all $p,p'$ such that $p \succ p'$ ($u$ continues to denote the utility indices associated $\succeq$). In the former case, we can use $k=0$, and in the latter case, $k=1$.
Applying Theorem (ref) also requires to specify a compatible metric on preferences. Because the set of lotteries is compact and metrizable, one could measure the distance between two preferences by the Hausdorff metric. Here however, each preference is naturally represented by a finite-dimensional vector of utility indices, and it can be more straightforward to set, as distance between preferences, the distance between their associated utility indices. So, let $\rho({\succeq}, {\succeq}')$ be the Euclidean distance between the two normalized vectors of utility indices of ${\succeq}$ and ${\succeq}'$. It can be seen that $\rho$ is a compatible metric (this fact holds quite generally, see Section (ref)).
The focus on error probability functions of the above form then allows for explicit convergence rates for the Kemeny-minimizing estimator, as below.
One can rewrite Corollary (ref) to provide a convergence rate of the form $O_p((1/n)^{1/d})$.\footnote{The $O_p$ notation refers to the stochastic boundedness notation.} The proof of Corollary (ref) is in Appendix (ref).
Note that the uniform distribution is not at all essential for Corollary (ref). It just yields a particularly simple closed form for the bound on $r(\eta)$ used in Theorem (ref).
In many economic settings, it is safe to posit the existence of a universal ordering, by which some alternatives are ranked above others by all the individuals of the relevant population: preferences are monotone with respect to this ordering. For example, for the classical consumption environment in which individuals choose bundles of goods, it is usually assumed that individuals strictly prefer to have more of each good. In laboratory experiments, it is common to assume some form of objective ranking, for instance when enforcing single-switching in price lists, or when using randomization devices to enforce incentives. Monotonicity with respect to such universal orderings turns out to be a very useful discipline on preferences.
In this section, we adopt the following terminology. Fix a set of alternatives $X$. We call dominance relation any binary relation $\rhd$ on $X$ that is not reflexive, that is, for each $x \in X$, $x \ntriangleright x$. The relation $\rhd$ is said to be open when $\rhd$ is an open set in the product space $X \times X$.\footnote{That is, for each $x, y$ with $x \rhd y$, there exists a neighborhood $V$ of $(x,y)$ in $X \times X$ such that for all $(x',y') \in V$, $x' \rhd y'$.} Being open for a dominance relation can be interpreted as a continuity property, saying that if $x$ dominates $y$ then this domination extends locally around the alternatives $x$ and $y$.
Given a dominance relation $\rhd$, a preference relation $\succeq$ is strictly monotone with respect to $\rhd$ if, for each $x,y \in X$, $x \rhd y$ implies $x \succ y$. Having a class of strictly monotone preferences captures the above idea that some alternatives are universally preferred to some others in accordance to the dominance relation.
Usually, strict monotonicity alone does not suffice to ensure that the preference is locally strict, the first crucial condition in our framework. It helps to add a notion of transitivity. We call a preference relation $\succeq$ Grodal-transitive if for all $x,y,z,w \in X$, $x \succeq y \succ z \succeq w$ implies $x \succeq w$. Named after grodal1974note, Grodal-transitivity is weaker, and so more permissive, than the usual notion of transitivity. Importantly, together with strict monotonicity, Grodal-transitivity makes the class of preferences closed, the second crucial condition of our framework.
The proof of Lemma (ref) is in Appendix (ref).
It is worth noting that, in general, closedness is not achieved under the usual notion of transitivity and strict monotonicity. If one wishes to impose transitivity, the class of preferences must be reduced further to obtain a closed set (as we did in the example of Section (ref)). Of course, there is no harm in having a more generous class of preferences. Even if the class includes preferences that fails desirable properties such as classical transitivity---and so may include irrelevant preferences---preference estimates are guaranteed to converge to the correct underlying preference, so that any violation by the preference estimates eventually gets corrected in the limit.
The main benefit of Grodal-transitivity is that it is enough to make strictly monotone preferences locally strict under relatively mild conditions.
The proof of Lemma (ref) is in Appendix (ref).
Therefore, Assumption (ref) on the class of preferences is valid as long as $X$ is well behaved, the dominance relation is open, and the preferences considered are Grodal-transitive and strictly monotone. The examples below show that these properties are satisfied in many common preference environments.
Our discussion is summed up in the following result, which we shall see has several applications.
The classical setup of consumer demand analysis features a commodity space over $d \ge 2$ goods, where consumers get to choose over bundles of goods (as in afriat, mascolell78, or varian1982nonparametric). The set of alternatives is the Euclidean space $\mathbf{R}_{++}^d$, the $i$-th entry of vector $(x_1, \dots, x_d)$ is interpreted as the consumed quantity of the $i$-th good. This environment is part of our framework when preferences are asked to satisfy a monotonicity condition.
Consider the dominance relation $\gg$ on $\mathbf{R}_{++}^d$ by $x \gg y$ exactly when $x_i > y_i$ for all $i = 1, \dots, d$. An individual whose preference is strictly monotone with respect to $\gg$ means that this individual strictly prefers to have more of every good, a postulate that appears reasonable in many situations, and that is common in economic models. It is evident that the relation $\gg$ is open, and for any $x \in \mathbf{R}_{++}^d$, $x + \varepsilon \mathbf{1} \gg x$ for all $\varepsilon > 0$ while $x \gg x - \varepsilon \mathbf{1} \in \mathbf{R}_{++}^d$ for all small enough $\varepsilon > 0$. Hence, Lemmas (ref) and (ref) apply, and we get Proposition (ref).\footnote{While the set $\mathbf{R}_{++}^d$ is not complete under the Euclidean metric, there exists a compatible complete metric by Alexandroff's Theorem (Theorem 24.12 of willard). Of course, $\mathbf{R}_{++}^d$ is also locally compact and separable, and hence Assumption (ref) is satisfied.}
The same set of alternatives can be used to describe state-contingent payments, with an objective public distribution over states, and where the $i$-th entry of a vector encodes the payment received in the state $i$. In such an environment, one may want to test the validity of the hypothesis that individuals maximize an expected utility function (as, for example, in green1986expected), or maximize a utility function that is monotone with respect to first-order stochastic dominance (as in \citealp*{nishimura}). Because both classes of preferences are more restrictive than the class $\mathcal{P}$ considered here, our convergence results continue to apply, which means that we can fully recover preferences and examine precisely the validity of these hypotheses.
Our next application deals with recovering preferences over menus, following kreps1979representation and \citet*{dlr}. Let $\Pi=\{\pi_1, \dots, \pi_d\}$ be a collection of prizes and let $\Delta_{++}^{d-1}$ be the interior of the $(d-1)$-dimensional simplex, interpreted as the set of full-support distributions over the elements of $\Pi$. We endow $\Delta_{++}^{d-1}$ with the Euclidean metric.
Let $\mathcal{M}$ denote the set of closed convex subsets of $\Delta_{++}^{d-1}$ with nonempty interior. We interpret $\mathcal{M}$ as a set of menus of lotteries. A subject who possesses a menu $m \in \mathcal{M}$ gets to choose a lottery in $m$, and subsequently receives a prize drawn according to this lottery. The convexity of menus that is assumed here is also implied by the axiom of indifference to randomization introduced by dlr. We endow $\mathcal{M}$ with the Hausdorff topology, as is standard in menu theory.
We define the dominance relation $\sqsupset$ as follows: for two menus $m_A$ and $m_B$, $m_A \sqsupset m_B$ if every expected-utility decision maker with full knowledge of her utility when making menu choices would strictly prefer $m_A$ to $m_B$. More precisely, we write
the set of all utility indexes over prizes, up to a normalization (we rule out the trivial preference that is indifferent between any two lotteries). Then we write $m_A \sqsupset m_B$ if and only if for every $u \in \mathcal{U}$,
Since we restrict attention to convex menus, $A \sqsupset B$ implies $A \supset B$. Hence, the dominance relation $\sqsupset$ is similar to, but weaker than, the set-containment relation traditionally used in models of choice over menus. In particular, monotonicity with respect to $\sqsupset$ is less demanding than monotonicity with respect to $\supset$.
Our next result establishes that the revealed preference framework applies to the menu preference environment.
The proof of Corollary (ref) is in Appendix (ref).
We revisit the example in Section (ref). There is a good to be consumed at a sequence of $d \ge 2$ increasing dates $t_1, \dots, t_d$. The set of alternatives is now $\mathbf{R}_{++}^d$, and each element $(x_1, \dots, x_d)$ gives the amount consumed at each date.
As before, we can hypothesize that individuals prefer more of the good early over less later. In the present environment, this postulate is captured by the dominance relation $\ggg$ on $\mathbf{R}_{++}^d$ whereby $x \ggg y$ if and only if for every $k$,
This dominance relation also captures the impatience assumption implicit in exponential discounting. In the same environment, \citet*{nishimura} suggest another postulate: that individuals are neutral to time while they still prefer to get more of the good. The associated dominance relation $\mathrel{>}_{\textrm{sym}}$ is defined as $x \mathrel{>}_{\textrm{sym}} y$ if and only if there exists a permutation $\sigma$ over $\{1, \dots, d\}$ such that for every $i$, $x_{\sigma(i)} > y_{\sigma(i)}$.
It is immediately seen that $\ggg$ is open, and that, when $x \in \mathbf{R}_{++}^d$ and $\varepsilon > 0$ is small enough, $x \ggg x - \varepsilon \mathbf{1}$ and $x + \varepsilon \mathbf{1} \ggg x$. The very same observations apply to the relation $\mathrel{>}_{\textrm{sym}}$. By a logic that is now routine, we get the following proposition.
Consider a set of $d \ge 2$ monetary rewards $\Pi \equiv \{\pi_1, \dots, \pi_d\}$, and let the interior of the $(d-1)$-simplex, $\Delta_{++}^{d-1}$, be the set of alternatives endowed with the Euclidean topology. We interpret an element $p \in \Delta_{++}^{d-1}$ as a full-support lottery over monetary rewards. This choice domain is an instance of the domain studied in Section (ref).
Suppose that the elements of $\Pi$ are ordered as $\pi_1 < \dots < \pi_d$. A natural dominance relation is strict first-order stochastic dominance, noted $\mathrel{>}_{\textrm{FSD}}$, where $p \mathrel{>}_{\textrm{FSD}} p'$ if and only if for all $k = 1, \dots, d-1$,
The reason for using strict first-order stochastic dominance is that this relation is open, as opposed to first-order stochastic dominance. Now, let $p \in \Delta_{++}^{d-1}$. For a small enough positive $\varepsilon$, we can define $p' \in \Delta_{++}^{d-1}$ by $p_i' = p_i - \varepsilon$ for all $i \le d-1$ and $p_d' = p_d + (d-1) \varepsilon$. Then $p' \mathrel{>}_{\textrm{FSD}} p$. And similarly, when instead $p_i' = p_i + \varepsilon$ for all $i \le d-1$ and $p_d' = p_d - (d-1) \varepsilon$, $p \mathrel{>}_{\textrm{FSD}} p'$. As a consequence of Proposition (ref), we obtain the following result.
Note that the class of nonconstant expected-utility preferences studied in Section (ref) and the class considered in the present lottery choice environment are distinct, and neither one is a refinement of the other.
This paper deals with the question of recovering individual preferences from observed choice data, when the data consist of a finite number of binary comparisons. Decision theorists often consider the question of “backing out” a model from data on pairwise choices, motivated by laboratory experiments, in which pairwise choices are common. They assume, however, rich and infinite data sets. Econometricians study the convergence of preference estimates, but their models usually differ from the pairwise choice paradigm. Moreover, the conditions needed for consistency of their estimates are imposed as added-on assumptions, instead of being derived from the properties of the economic model under consideration.
We provide a common unifying framework. We show that the class of preferences considered should be locally strict. Under local strictness, and some regularity conditions, any preference that rationalizes the observed pairwise choices converges to the correct data-generating preference. In the statistical counterpart to our model, the Kemeny-minimizing estimator, which outputs the preferences that best fit the data, is consistent. In addition, convergence rates can be obtained while remaining largely agnostic on the sampling method and the error probability function.
Our results require weak assumptions and apply to a broad range of standard preference environments. We conclude with a discussion on a few aspects of our model.
At a general level, the topology of closed convergence is defined by the property that individuals with comparable preferences behave similarly on closely related decision problems. Such continuity property appears natural, and even necessary to be able to learn from finite data. In formal terms, if $x \succ y$ for some alternatives $(x,y)$ and a preference ${\succeq}$, and if $(x', y')$ are alternatives in a neighborhood of $(x,y)$, then the topology of closed convergence is defined exactly so that $x' \succ' y'$ for any preference ${\succeq'}$ close enough to ${\succeq}$.\footnote{To be even more formal, under the assumptions of our results, the closed convergence topology is the smallest topology for which the set $\{ (x,y,{\succeq}) : x \succ y\}$ is open in the product topology; see Theorem 3.1 of kannai1970continuity.}
This topology also has the property that, if the experimenter learns that the subject prefers (at least weakly) $x$ to $y$ through her experiments---because the subject chooses $x$ when presented with the pair $\{x,y\}$---this is also reflected in the limiting preference, when it exists: if for some $N \in \mathbf{N}$ and $x, y \in X$, we have $x \succeq_n y$ for all $ n \ge N$, and if ${\succeq}_n \rightarrow {\succeq}^*$, then $x \succeq^* y$. And our model allows for the possibility that certain parts of the subject's preference remain unobserved. For example, the experimenter cannot learn, from a finite number of observations, that $x$ is strictly preferred to $y$, although she may learn that $x$ is weakly preferred. In this case, if we can still ensure a unique limiting preference ${\succeq}^*$, then it means that correct inferences about missing observations have been made. The closed convergence topology is therefore well suited to the concept of weak rationalization.
Theorem (ref) is an instance of the consistency of M-estimators. Consistency is well known to rely on three properties of the econometric environment (see, for example, Theorem 4.1.1 of amemiya1985advanced, or Theorems 2.1 and 3.1 of newey1994large). The first is that the true parameter has to be a unique extremum of the population version of the objective function. We prove this property in Lemma (ref). The second is the uniform convergence of the sample objective function to the population version. We do not need to assume this property in an ad-hoc fashion; instead, we are able to derive it from our model primitives. Finally, the canonical results on M-estimators need that the parameter space is compact. The topology we use on the space of preferences guarantees its compactness. So, even though our estimation problem is fully nonparametric, we are able to work with a compact space of parameters and we do not need to assume uniform convergence or stochastic equicontinuity.
The most related work in the econometrics literature is \citet*{chernozhukovhongtamer}, who present consistent estimators for partially identified models from moment conditions. We differ from their work in that they provide a general methodology for parametric estimation, while we are specifically interested in the approximation of preferences from pairwise comparisons, and our problem is nonparametric. Because their methodology aims at being general, their main consistency result (Theorem 3.1) assumes the uniform convergence property (part of condition C1). It is not derived from the revealed preference questions that motivate their study. Our consistency result also depends on an analogous uniform convergence property (as mentioned above, this is true generally of the consistency of M-estimators), but it is obtained as a consequence of the primitives of our model. Obtaining consistency directly from the model primitives is the key contribution of Theorem (ref). In certain environments, revealed preference conditions are representable by means of moment inequalities, and the results of chernozhukovhongtamer can be applied, \citet*{blundell2008best} is a notable instance of such an application in the context of demand analysis.
The metric $\rho$ used in our results can be any metric on the space of preferences that is compatible with the topology of closed convergence. For instance, for compact sets of alternatives that satisfy Assumption (ref), we can use for $\rho$ the Hausdorff distance between subsets of $X \times X$.
When the space of preferences $\mathcal{P}$ is parameterized, one may wish to work with a metric on preference parameters, such as the usual Euclidean distance when parameters are finite-dimensional vectors. Doing so is possible when the space of preferences and the space of parameters are homeomorphic, as formalized by the following lemma.
Lemma (ref) follows directly from the observation that, under the above conditions, the inverse of $\phi$ is continuous by compactness of $\Theta$.\footnote{Hence, any set of preferences that is open in the topology of closed convergence contains an open ball under the metric $\rho$, and conversely, any open ball of preferences under the metric $\rho$ contains an open set in the topology of closed convergence. Therefore, the topology of closed convergence and the metric topology induced by $\rho$ are identical.}
To illustrate this result in a concrete case, let us return to the expected-utility preference environment of Section (ref). Recall that the set of alternatives $X$ is the set of lotteries over a finite collection of prizes $\{\pi_1, \ldots, \pi_d\}$, represented as the $(d-1)$-dimensional simplex $\Delta^{d-1}$, and $\mathcal{P}$ is the set of nonconstant expected utility preferences. Each preference of $\mathcal{P}$ is naturally parameterized by its normalized vector of utilities: using the notation in Lemma (ref), let the space of parameters be
and $D$ be the Euclidean distance.
Let $\phi$ the mapping that, to each $v \in \Theta$, associates the expected utility preference relation $\succeq$ defined as $p \succeq p'$ if and only if $v \cdot p \ge v \cdot p'$. Let us write $\phi(v) = \Phi(U_v)$, where $U_v$ is the utility function on $X$ defined by $U_v(p) = v \cdot p$, and, as in Section (ref), $\Phi(u)$ denotes the preference induced by utility function $u: X \mapsto \mathbf{R}$. First, we observe that $v \mapsto U_v$ is continuous, when, as in Section (ref), the space of utility functions is endowed with the topology of compact convergence. Second, we observe that $\Phi$ is continuous by Theorem 8 of border1994dynamic (see Appendix (ref)), since by Corollary (ref), $\Phi(u)$ is locally strict when $u$ is defined as $u(p) = v \cdot p$ for $v \in \Theta$. Therefore Lemma (ref) applies: if $\rho({\succeq}, {\succeq}')$ is defined as the Euclidean distance between the utility indices of ${\succeq}$ and ${\succeq}'$ respectively, then $\rho$ is a compatible metric on $\mathcal{P}$.
We use this fact in Proposition (ref) to derive convergence rates of estimated preferences in terms of the Euclidean distance on utility indexes.
Aside from the assumption of local strictness, our framework applies to very general classes of preferences. In particular, it applies to preferences without classical rationality hypotheses, such as transitivity. Still, one may wish to look for rationalizing preferences that are transitive. While it is perfectly reasonable to focus on transitive preferences, one must interpret Theorem (ref) with care. Even when all the preferences that rationalize the observed behavior for a set of experiments can be chosen to be transitive, there is no guarantee that the limiting preference is transitive, even if Assumption (ref) is satisfied. This fact owes to an example of grodal1974note.
Adapted to our context, Grodal's example proceeds as follows. Figure (ref) exhibits a nontransitive relation borrowed from \citet*{grodal1974note}, with $X=\mathbf{R}_{++}^2$ (say, $X$ is a commodity space with two goods). The lines depict indifference curves. All the green indifference curves intersect at one point: $(1/2,1/2)$. Aside from the point $(1/2,1/2)$, $x$ is at least as good as $y$ if and only if it lies on a (weakly) higher indifference curve. But, all bundles on an indifference curve passing through $(1/2,1/2)$ are indifferent to $(1/2,1/2)$. This feature makes the preference nontransitive; specifically, the indifference part of the preference is intransitive here. Let $\succeq^*$ denote this preference.
Imagine an ordered collection of binary choice problems that do not include the alternative $(1/2,1/2)$. Suppose that this collection is either finite or infinite but countable, as the set used in our growing experiments. Then for every $n$ there is a ball around $(1/2,1/2)$ that does not contain any alternative in the first $n$ binary choice problems. Consider the preferences pictured in the diagram of Figure (ref). Compared to the relation depicted in Figure (ref), the preferences of Figure (ref) have been modified close to $(1/2,1/2)$ so that transitivity holds. Thus, one can construct a sequence of strictly monotone preferences, $\succeq_n$, $n \in \mathbf{N}$, where each $\succeq_n$ is transitive, and ${\succeq}_n \rightarrow {\succeq}^*$, but $\succeq^*$ is not transitive.
It is generally true that if each $\succ_n$ (the strict part of $\succeq_n$) is transitive, then $\succ^*$ will be transitive as well (see grodal1974note), but in some cases one may desire full transitivity of $\succeq^*$.\footnote{Relations for which the strict part is transitive are usually called quasitransitive, and they possess many of the useful properties possessed by transitive relations. For example, continuous quasitransitive relations possess maximums on compact sets bergstrom1975.} The central element of the example above is that the indifference curves get “squeezed” together too rapidly.
There are several ways out of Grodal's example, if we wish to obtain a transitive limiting preference $\succeq^*$. We have seen a few in Sections (ref) and (ref). A rather general approach involves Lipschitz conditions on the class of preferences being considered.
Let us apply the Lipschitz approach to the environment described in Section (ref). Fix $X=\mathbf{R}_+^d$ as the set of alternatives, such as a commodity space with $d$ goods. Also fix $a,b\in\mathbf{R}_{++}$ with $a < b$, and consider the class of utility functions $\mathcal{U}$ defined as the set of all the continuous utility functions $u: \mathbf{R}_+^d \rightarrow \mathbf{R}$ such that, for all $i$, and all $x_i, y_i \in \mathbf{R}_+$ with $x_i < y_i$,
for all $x_{-i} \in \mathbf{R}_+^{d-1}$. Hence, each utility function in $\mathcal{U}$ is Lipschitz-bounded above and below. Clearly, every such utility function also describes a transitive, locally strict preference, because $a$ is positive. And by the Arzela-Ascoli Theorem (Theorem 6.4, p. 267, of dugundji), $\mathcal{U}$ is compact. Therefore one can appeal to Proposition (ref), and if each rationalizing preference $\succeq_n$ of the $n$-th experiment of an exhaustive sequence is included in $\Phi(\mathcal{U})$, then the limiting preference exists and is a member of $\Phi(\mathcal{U})$, and so is transitive.