Recovering utility

Let $X$ be a set. Given a binary relation $R\subseteq X\times X$, we write $x\mathrel{R}y$ when $(x,y)\in R$. A binary relation that is complete and transitive is called a weak order. If $X$ is a topological space, then we say that $R$ is continuous if $R$ is closed as a subset of $X\times X$ (see, for example, Bergstrom, Parks, and Rader, 1976). A preference relation is a weak order that is also continuous.

A preference relation $\succeq$ is locally strict if, for all $x,y\in X$, $x\succeq y$ implies that for each neighborhood $U$ of $(x,y)$, there is $(x^{\prime},y^{\prime})\in U$ with $x\succ y$. The notion of local strictness was first introduced by Border and Segal (1994) as a generalization of the property of being locally non-satiated from consumer theory.

If $\succeq$ is a preference on $X$ and $u:X\to\mathbf{R}$ is a function for which $x\succeq y$ if and only if $u(x)\geq u(y)$ then we say that $u$ is a representation of $\succeq$, or that $u$ is a utility function for $\succeq$.

If $A\subseteq\mathbf{R}^{d}$ is a Borel set, we write $\Delta(A)$ for the set of all Borel probability measures on $A$. We endow $\Delta(A)$ with the weak* topology. If $S$ is a finite set, then we topologize $\Delta(A)^{S}$ with the product topology.

For $p,q\in\Delta(A)$, we say that $p$ is larger than $q$ in the sense of first-order stochastic dominance if $\int_{A}fdx\geq\int_{A}fdy$ for all monotone increasing, continuous and bounded functions $f$ on $A$.

The set of preferences over $X$, when $X$ is a topological space, is endowed with the topology of closed convergence. The space of corresponding utility representations is endowed with the compact-open topology. These are the standard topologies for preferences and utilities, used in prior work in mathematical economics. See, for example, Hildenbrand (1970), Kannai (1970), and Mas-Colell (1974). Here we offer definitions and a brief discussion of our choice of topology.

Let $X$ be a topological space, and $\mathcal{F}=\{F^{n}\}_{n}$ be a sequence of closed sets in $X\times X$ (with the product topology). We define $\textrm{Li}(\mathcal{F})$ and $\textrm{Ls}(\mathcal{F})$ to be closed subsets of $X\times X$ as follows:

• •

  $(x,y)\in\textrm{Li}(\mathcal{F})$ if and only if, for all neighborhoods $V$ of $(x,y)$, there exists $N\in\mathbf{N}$ such that $F^{n}\cap V\neq\varnothing$ for all $n\geq N$.

• •

  $(x,y)\in\textrm{Ls}(\mathcal{F})$ if and only if, for all neighborhoods $V$ of $(x,y)$, and all $N\in\mathbf{N}$, there is $n\geq N$ such that $F^{n}\cap V\neq\varnothing$.

Observe that $\textrm{Li}(\mathcal{F})\subseteq\textrm{Ls}(\mathcal{F})$. The definition of closed convergence is as follows.

Closed convergence captures the property that agents with similar preferences should have similar choice behavior—a property that is necessary to be able to learn the preference from finite data. Specifically, if $X\subseteq\mathbf{R}^{n}$, and $\mathcal{P}$ is the set of all locally strict and continuous preferences on $X$, then the topology of closed convergence is the smallest topology on $\mathcal{P}$ for which the sets

are open.²²2See Kannai (1970) and Hildenbrand (1970) for a discussion; a proof of this claim is available from the authors upon request. In words: suppose that $x\succ y$, then for $x^{\prime}$ close to $x$, $y^{\prime}$ close to $y$, and $\succeq^{\prime}$ close to $\succeq$, we obtain that $x^{\prime}\succ^{\prime}y^{\prime}$.

For utility functions, we adopt the compact-open topology, which we also claim is a natural choice of topology. The compact-open topology is characterized by the convergence criterion of uniform convergence on compact sets. The reason it is natural for utility functions is that a utility usually has two arguments: one is the object being “consumed” (a lottery, for example) and the other is the ordinal preference that utility is meant to represent. (The preference argument is usually implicit, but of course it remains a key aspect of the exercise.) Now an analyst wants the utility to be “jointly continuous,” or continuous in both of its arguments. For such a purpose, the natural topology on the set of utilities, when they are viewed solely as functions of consumption, is indeed the compact-open topology. More formally, consider the following result, originally due to Mas-Colell (1977).³³3Levin (1983) provides a generalization to incomplete preferences.

We may view the map $U$ as a mapping from $\succeq$ to the space of utility functions. Then continuity of this induced mapping is equivalent to the joint continuity result discussed in Theorem 1, as long as we impose the compact-open topology on the space of utility functions (see Fox (1945)).

As laid our in Section 2, we want to understand when we may conclude that $u^{k}\to u$ from knowing that $\succeq^{k}\to\succeq$. Mas-Colell’s theorem (Theorem 1) provides general conditions under which there exists one utility representation that has the requisite convergence property, but he is clear about the practical limitations of his result: “There is probably not a simple constructive (“canonical”) method to find a $U$ function.” In contrast, economists are generally interested in specific parameterizations of utility.

For example, if an agent has subjective expected-utility preferences, economists want to estimate beliefs and a von-Neumann-Morgenstern index; not some arbitrary representation of the agent’s preferences. Or, if the data involve intertemporal choices, and the agent discounts utility exponentially, then an economist will want to estimate their discount factor. Such specific parameterizations of utility are not meaningful in the context of Theorem 1.

The following (trivial) example shows that there is indeed a problem to be studied. Convergence of arbitrary utility representations to the correct limit is not guaranteed, even when recovered utilities form a convergent sequence, and recovered preferences converge to the correct limit.

In the example, we have imposed some discipline on the representation. Given that the utility converges to a constant, the discipline we have chosen is a particular normalization of the utility representations (their norm is constant). The normalization just makes the construction of the example slightly more challenging, and reflects perhaps the most basic care that an analyst could impose on the recovery exercise.

We present our first main result in the context of Anscombe-Aumann acts, the workhorse model of the modern theory of decisions under uncertainty. Let $S$ be a finite set of states of the world, and fix a closed interval of the real line $[a,b]\subseteq\mathbf{R}$. An act is a function $f:S\to\Delta([a,b])$. We interpret the elements of $\Delta([a,b])$ as monetary lotteries, so that acts are state-contingent monetary lotteries. The set of all acts is $\Delta([a,b])^{S}$. When $p\in\Delta([a,b])$, we denote the constant act that is identically equal to $p$ by $(p,\ldots,p)$; or sometimes by $p$ for short.

Note that we do not work with abstract, general, Anscombe-Aumann acts, but in assuming monetary lotteries we impose a particular structure on the objective lotteries in our Anscombe-Aumann framework. The reason is that our theory necessitates a certain known and objective direction of preference. Certain preference comparisons must be known a priori: monotonicity of preference will do the job, but for monotonicity to be objective we need the structure of monetary lotteries.

An act $f$ dominates an act $g$ if, for all $s\in S$, $f(s)$ first-order stochastic dominates $g(s)$. And $f$ strictly dominates $g$ if, for all $s\in S$, $f(s)$ strictly first-order stochastic dominates $g(s)$. A preference $\succeq$ over acts is weakly monotone if $f\succeq g$ whenever $f$ first-order stochastic dominates $g$.

Let $U$ be the set of all continuous and monotone weakly increasing functions $u:[a,b]\to\mathbf{R}$ with $u(a)=0$ and $u(b)=1$. A pair $(V,u)$ is a standard representation if $V:\Delta([a,b])^{S}\to\mathbf{R}$ and $u\in U$ are continuous functions such that $v(p,\ldots,p)=\int_{[a,b]}u\mathop{}\!\mathrm{d}p$, for all constant acts $(p,\ldots,p)$. Moreover, we say that a standard representation $(V,u)$ is aggregative if there is an aggregator $H:[0,1]^{S}\to\mathbf{R}$ with $V(f)=H((\int u\mathop{}\!\mathrm{d}f(s))_{s\in S})$ for $f\in\Delta([a,b])^{S}$. An aggregative representation with aggregator $H$ is denoted by $(V,u,H)$. Observe that a standard representation rules out total indifference.

A preference $\succeq$ on $\Delta([a,b])^{S}$ is standard if it is weakly monotone, and there is a standard representation $(V,u)$ in which $V$ represents $\succeq$. Roughly, standard preferences will be those that satisfy the expected utility axioms across constant acts, and are monotone with respect to the (statewise) first order stochastic dominance relation. Aggregative preferences will additionally satisfy an analogue of Savage’s P3 or the Anscombe-Aumann notion of monotonicity.

Some other examples of aggregative preferences include special cases of the variational model Gilboa and Schmeidler (1989), as well as generalizations of it, Cerreia-Vioglio, Maccheroni, Marinacci, and Montrucchio (2011); Chandrasekher, Frick, Iijima, and Le Yaouanq (2021), and others which are not comparable Schmeidler (1989); Chateauneuf, Grabisch, and Rico (2008); Chateauneuf and Faro (2009).⁵⁵5A class of variational preferences that are of particular interest to computer scientists are preferences with a max-min representation (Gilboa and Schmeidler, 1989). These evaluate acts by $$V(f)=\inf\{\int v(f(s))d\pi(s):\pi\in\Pi\},$$ with $\Pi\subseteq\Delta(S)$ a closed and convex set. Here $c$ is the indicator function of $\Pi$ (as defined in convex analysis).

In terms of interpretation, Theorem 2 suggests that, as preferences converge, risk-attitudes, or von Neumann morgenstern utility indices also converge in a pointwise sense. The aggregative part claims that we can study the convergence of risk attitudes and the convergence of the aggregator controlling for risk separately. So, for example, in the multiple priors case, two decision makers whose preferences are close will have similar sets of priors.

In this section, we focus on a canonical representation for preferences over lotteries: the certainty equivalent. There are many models of preferences over lotteries, but we have in mind in particular Cerreia-Vioglio, Dillenberger, and Ortoleva (2015), whereby a preference representation over lotteries is given by $U(p)=\inf_{u\in\mathcal{U}}u^{-1}(\int udp)$; a minimum over a set of certainty equivalents for expected utility maximizers. Key is that for this representation, and any degenerate lottery $\delta_{x}$, $U(\delta_{x})=x$.

Let $[a,b]\subset\mathbf{R}$, where $a<b$, be an interval in the real line and consider $\Delta([a,b])$. Say that $\succeq$ on $\Delta([a,b])$ is certainty monotone if when ever $p$ first order stochastically dominates $q$, then $p\succeq q$, and for all $x,y\in[a,b]$ for which $x>y$, $\delta_{x}\succ\delta_{y}$. Any certainty monotone continuous preference $\succeq$ and any lottery $p\in\Delta([a,b])$ then possesses a unique certainty equivalent $x\in[0,1]$, satisfying $\delta_{x}\sim p$. To this end, we define $\mbox{ce}(\succeq,p)$ to be the certainty equivalent of $p$ for $\succeq$. It is clear that, fixing $\succeq$, $\mbox{ce}(\cdot,\succeq)$ is a continuous utility representation of $\succeq$.

To this end, the map carrying each preference to its certainty equivalent representation is a continuous map in the topology of closed convergence.

The primitives of our noisy choice model are collected in the tuple $(X,\mathcal{P},\lambda,q)$, where:

• •

  $X\subseteq\mathbf{R}^{d}$ is the ambient choice, or consumption, space. The set $X$ is endowed with the (relative) topology inherited from $\mathbf{R}^{d}$.

• •

  $\mathcal{P}$ is a class of continuous and locally strict preferences on $X$. The class comes with a set of utility functions $\mathcal{U}$, so that each element of $\mathcal{P}$ has a utility representation in the set $\mathcal{U}$.

• •

  $\lambda$ is a probability measure on $X$, assumed to be absolutely continuous with respect to Lebesgue measure. We also assume that $\lambda\geq c\,\mathrm{Leb}$, where $c>0$ is a constant and Leb denotes Lebesgue measure.

• •

  $q:X\times X\times\mathcal{P}\to[0,1]$ is a random choice function, so $q(x,y;\succeq)$ is the probability that an agent with preferences $\succeq$ chooses $x$ over $y$. Assume that if $x\succ y$, then $x$ is chosen with probability $q(x,y;\succeq)>1/2$ and $y$ with probability $q(y,x;\succeq^{*})=1-q(x,y;\succeq)$. If $x\sim y$ then $x$ and $y$ are chosen with equal probability.

• •

  We shall assume that the error probability $q$ satisfies that

  $$\Theta\equiv\inf\{q(\succeq,(x,y)):x\succ y\text{ and }\succeq\in\mathcal{P}\}>\frac{1}{2}.$$

The tuple $(X,\mathcal{P},\lambda,q)$ describes a data-generating process for noisy choice data. Fix a sample size $n$ and consider an agent with preference $\succeq^{*}\in\mathcal{P}$. A sequence of choice problems $\{x_{i},y_{i}\}$, $1\leq i\leq n$ are obtained by drawing $x_{i}$ and $y_{i}$ from $X$, independently, according to the law $\lambda$. Then a choice is made from each problem $\{x_{i},y_{i}\}$ according to $q(\cdot,\cdot;\succeq^{*})$.

Observe that our assumptions on $q$ are mild. We allow errors to depend on the pair $\{x,y\}$ under consideration, almost arbitrarily. The only requirement is that one is more likely to choose according to one’s preference than to go against them, as well as the more technical assumptions of measurability and a control on how large the deviation from $1/2$-$1/2$ choice may get.

To keep track of the chosen alternative, we order the elements of each problem so that $(x_{i},y_{i})$ means that $x_{i}$ was chosen from the choice problem $\{x_{i},y_{i}\}$. So a sample of size $n$ is $\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\}$, consisting of $2n$ iid draws from $X\times X$ according to our stochastic choice model: in the $i$th draw, the choice problem was $\{x_{i},y_{i}\}$ and $x_{i}$ was chosen.

A utility function $u_{n}\in\mathcal{U}$ is chosen to maximize the number of rationalized choices in the data. So $u_{n}$ maximizes $\sum_{i=1}^{n}\mathbf{1}_{u(x_{i})\geq u(y_{i})}$. The space of utility functions is endowed with a metric, $\rho$. In this section, all we ask of $\rho$ is that, for any $u,u^{\prime}\in\mathcal{U}$, there is $x\in X$ with $\left|u(x)-u^{\prime}(x)\right|\geq\rho(u,u^{\prime})$. For example, we could use the sup norm for the purposes of any of the results in this section.

Of course, the second statement in the theorem is only meaningful when the VC dimension of $\mathcal{P}$ is finite. The constants $K$ and $\bar{C}$ depend on the primitives in the environment, but not on preferences, utilities, or sample sizes.

Our next result serves to contrast what can be achieved with the “limiting” (countably infinite) data with the limit of preferences recovered from finite choice experiments.

Indeed, as the proof makes clear, Theorem 4 would hold more generally for any $X$ which is a connected topological space, but it may not hold in absence of connectedness. There is a sense in which the limiting case with an infinite amount of data offers no problems for preference recovery. The structure we impose is needed for the limit of rationalizations drawn from finite data.

Here we adopt the same structural assumptions as in Section 3.4, namely that $X=\Delta([a,b])^{S}$, endowed with the weak topology and the first order stochastic dominance relation. However, the result easily extends to broader environments, as the proof makes clear.

Note that Theorem 5 requires the existence of the data-generating preference $\succeq^{*}$.

A “dual” result to Theorem 5 was established in Chambers, Echenique, and Lambert (2021). There, the focus was on weak rationalization via $\succeq^{k}$, which is a weaker notion than the strong rationalization hypothesized here. To achieve a weak rationalization result, we assumed instead that preferences were strictly monotone.

The lemmas stated here will be used in the proofs of our results.

The results we have obtained motivate two definitions that will prove useful. Say that the set $X$, together with the collection of finite experiments $\Sigma_{\infty}$, has the countable order property if for each $x\in X$ and each neighborhood $V$ of $x$ in $X$ there is $x^{\prime},x^{\prime\prime}\in(\cup_{i}B_{i})\cap V$ with $x^{\prime}\leq x\leq x^{\prime\prime}$. We say that $X$ has the squeezing property if for any convergent sequence $\{x_{n}\}_{n}$ in $X$, if $x_{n}\rightarrow x^{*}$ then there is an increasing sequence $\{x^{\prime}_{n}\}_{n}$, and an a decreasing sequence $\{x^{\prime\prime}_{n}\}_{n}$, such that $x^{\prime}_{n}\leq x_{n}\leq x^{\prime\prime}_{n}$, and $\lim_{n\rightarrow\infty}x^{\prime}_{n}=x^{*}=\lim_{n\rightarrow\infty}x^{\prime\prime}_{n}$.

Without loss of generality, we may set $[a,b]=[0,1]$. First we show that $u^{k}\to u$ in the compact-open topology. To this end, let $x^{k}\to x$. We want to show that $u^{k}(x^{k})\to u(x)$. Suppose then that this is not the case, and by selecting a subsequence that $u^{k}(x^{k})\to Y>u(x)$ (without loss). Note that $\delta_{x^{k}}\sim^{k}p^{k}$, where $p^{k}$ is the lottery that pays $1$ with probability $u^{k}(x^{k})\in[0,1]$, and $0$ with probability $1-u^{k}(x^{k})$. Let $p$ be the lottery that pays $1$ with probability $Y$, and $0$ with probability $1-Y$ (given that the range of $u^{k}$ is $[0,1]$, we must have $Y\in[0,1]$). Now we have that $(\delta_{x^{k}},p^{k})\to(\delta_{x},p)$ and $\delta_{x^{k}}\sim^{k}p^{k}$ implies $\delta_{x}\sim p$. This is a contradiction because $\delta_{x}$ is indifferent in $\succeq$ to the lottery that pays $1$ with probability $u^{k}(x^{k})\in[0,1]$, and $0$ with probability $1-u^{k}(x^{k})$. The latter is strictly first-order stochastically dominated by the lottery $p$.

To finish the proof, we show that $V^{k}\to V$. This is the same as proving that $V^{k}(f^{k})\to V(f)$ when $f^{k}\to f$. For each $k$, continuity and weak monotonicity imply that there is $x^{k}\in[0,1]$ so that

Similarly, there is $x$ with $V(f)=V(\delta_{x},\ldots,\delta_{x})=u(x)$.

Now we argue that $x^{k}\to x$. Indeed $\{x^{k}\}$ is a sequence in $[0,1]$. If there is a subsequence that converges to, say, $x^{\prime}>x$ then we may choose $x^{\prime\prime}=\frac{x+x^{\prime}}{2}$ and eventually

using weak monotonicity. This is impossible because $(f^{k},(\delta_{x^{k}},\ldots,\delta_{x^{k}})\to(f,(\delta_{x^{\prime}},\ldots,\delta_{x^{\prime}}))$ and $f^{k}\succeq^{k}((\delta_{x^{k}},\ldots,\delta_{x^{k}})$ imply that $f\succeq((\delta_{x^{\prime}},\ldots,\delta_{x^{\prime}})\succeq(\delta_{x^{\prime\prime}},\ldots,\delta_{x^{\prime\prime}})$.

Finally, using what we know about the convergence of $u^{k}$ to $u$, $V^{k}(f^{k})=u^{k}(x^{k})\to u(x)=V(f)$.

We now turn to the second statement in the theorem. Observe that $H^{k}$ is a continuous function from $[0,1]^{S}$ onto $[0,1]$. Let $z^{k}\in[0,1]^{S}$ be an arbitrary convergent sequence, and say that $z^{k}\rightarrow z^{*}$. We claim that $H^{k}(z^{k})\rightarrow H(z^{*})$. Without loss we may assume that $H^{k}(z^{k})\rightarrow Y$, by taking a subsequence if necessary. For each $k$ and $s$, choose $y^{k}(s)\in[0,1]$ for which $u^{k}(y^{k}(s))=z^{k}(s)$. Again, without loss, we may assume that $y^{k}\rightarrow y^{*}$ by taking a subsequence if necessary, and using the finiteness of $S$. Observe also that $u(y^{*}(s))=z^{*}(s)$ as we have shown that $u^{k}\to u$ in the compact-open topology.

Now, we may also choose $\hat{z}^{k}\in[0,1]$ so that

and further may again without loss (by taking a subsequence) assume that $\hat{z}^{k}$ converges to $\hat{z}^{*}$. Thus $u(\hat{z}^{*})=\lim u^{k}(\hat{z}^{k})=\lim H^{k}(z^{k})=Y$, again using what we have shown regarding $u^{k}\to u$. Then $(\delta_{\hat{z}^{k}},\ldots,\delta_{\hat{z}^{k}})\sim^{k}(y^{k}(s))_{s\in S}$ so that, by taking limits, $(\delta_{\hat{z}^{*}},\ldots,\delta_{\hat{z}^{*}})\sim^{*}(y^{*}(s))_{s}$. This implies that $Y=u(\hat{z}^{*})=H(u(y^{*}(s))=H(z^{*})$.

Take $(\succeq^{k},p^{k})$ as in the statement of the Proposition, and observe that for every $p\in\Delta([a,b])$, $\mbox{ce}(\succeq^{k},p^{k})\in[a,b]$. Suppose by means of contradiction that $\mbox{ce}(\succeq^{k},p^{k})\rightarrow\mbox{ce}(\succeq,p)$ is false, then there is some $\epsilon>0$ and a subsequence for which $|\mbox{ce}(\succeq^{k_{m}},p^{k_{m}})-\mbox{ce}(\succeq,p)|>\epsilon$, by taking a further subsequence, we assume without loss that $\mbox{ce}(\succeq^{k_{m}},p^{k_{m}})\rightarrow\alpha\neq\mbox{ce}(\succeq,p)$. Now, $p^{k_{m}}\sim^{k_{m}}\delta_{\mbox{ce}(\succeq^{k_{m}},p^{k_{m}})}$, and $p^{k_{m}}\rightarrow p$ and $\delta_{\mbox{ce}(\succeq^{k_{m}},p^{k_{m}})}\rightarrow\delta_{\alpha}$. So by definition of closed convergence, it follows that $p\sim\delta_{\alpha}$; but this violates certainty monotonicity as $\alpha\neq\mbox{ce}(\succeq,p)$.