VNM agents and lotteries involving an infinite number of possible outcomes

alexmennen

VNM agents and lotteries involving an infinite number of possible outcomes

post by AlexMennen · 2013-02-21T21:58:30.280Z · LW · GW · Legacy · 8 comments

  Outcomes versus Lotteries
  Infinite lotteries
  Extended VNM hypothesis
  Bounded and unbounded utility functions
None
8 comments

Summary: The VNM utility theorem only applies to lotteries that involve a finite number of possible outcomes. If an agent maximizes the expected value of a utility function when considering lotteries that involve a potentially infinite number of outcomes as well, then its utility function must be bounded.

Outcomes versus Lotteries

One way to formulate the VNM utility theorem is in terms of outcomes and lotteries over outcomes. That is, there is some set $\mathcal{O}$ of outcomes, and a set $\mathcal{L}$ of lotteries defined as $\mathcal{L}:=\left\{ \sum_{i=1}^{n}p_{i}O_{i}\mid n\in\mathbb{N},p_{i}>0,O_{i}\in\mathcal{O}\left(\forall i\right),\sum_{i=1}^{n}p_{i}=1\right\}$ . In other words, the set of lotteries is the set of probability distributions over a finite number of outcomes. The finiteness is very important; we'll get to that later. Note that for each outcome, there is a corresponding lottery that guarantees this outcome, and these “pure outcome” lotteries are a basis for $\mathcal{L}$ .

Given that formulation, and given the VNM axioms, there exists some function $u:\mathcal{O}\rightarrow\mathbb{R}$ such that given any 2 lotteries $L:=\sum_{i=1}^{n}p_{i}O_{L,i}$ and $M:=\sum_{i=1}^{m}q_{i}O_{M,i}$ , $L\succ M$ iff $\sum_{i=1}^{n}p_{i}u\left(O_{L,i}\right)>\sum_{i=1}^{m}q_{i}u\left(O_{M,i}\right)$ .

The other formulation does not mention $\mathcal{O}$ . Instead, there is simply a set $\mathcal{L}$ of lotteries, such that $\forall L_{1},L_{2},...,L_{n}\in\mathcal{L},\forall p_{1},p_{2},...,p_{n}>0\,\sum_{i=1}^{n}p_{i}L_{i}\in\mathcal{L}$ iff $\sum_{i=1}^{n}p_{i}=1$ . In this formulation, there exists some function $u:\mathcal{L}\rightarrow\mathbb{R}$ such that if $L=\sum_{i=1}^{n}p_{i}L_{i}$ , then $u\left(L\right)=\sum_{i=1}^{n}p_{i}u\left(L_{i}\right)$ (notice $n$ still must be finite) and for any 2 lotteries $L$ and $M$ , $L\succ M$ iff $u\left(L\right)>u\left(M\right)$ .

The formulation in terms of outcomes and lotteries over outcomes is more intuitively appealing (to me, at least), since real life has outcomes and uncertainty about outcomes, so I will use it when I can, but the formulation purely in terms of lotteries, which is more similar to what von Neumann and Morgenstern did in their original paper, will be useful sometimes, so I will switch back to it intermittently.

Infinite lotteries

Myth: Given some utility function $u:\mathcal{O}\rightarrow\mathbb{R}$ that accurately describes a VNM-rational agent's preferences over finite lotteries, if you expand $\mathcal{L}$ to include lotteries with an infinite number of possible outcomes (let's call the expanded set of lotteries $\mathcal{L}^{+}$ ), then for any 2 lotteries $L:=\sum_{i=1}^{\infty}p_{i}O_{L,i}$ and $M:=\sum_{i=1}^{\infty}q_{i}O_{M,i}$ , $L\succ M$ iff $\sum_{i=1}^{\infty}p_{i}u\left(O_{L,i}\right)>\sum_{i=1}^{\infty}q_{i}u\left(O_{M,i}\right)$ .

Reality: Knowing an agent's preferences over finite lotteries, and that the agent obeys the VNM axioms, does not tell you everything about the agent's preferences over lotteries with an infinite number of possible outcomes. To demonstrate this, I'm going to construct a VNM-rational agent that maximizes a utility function $u:\mathcal{L}^{+}\rightarrow\mathbb{R}$ , where $\exists\left\{ L_{i}\right\} _{i=1}^{\infty}\in\mathcal{L}^{+}\,\exists\left\{ p_{i}\left(\geq0\right)\right\} _{i=1}^{\infty}\,\sum_{i=1}^{\infty}p_{i}=1,\, u\left(\sum_{i=1}^{\infty}p_{i}L_{i}\right)\neq\sum_{i=1}^{\infty}p_{i}u\left(L_{i}\right)$ . This construction relies on the axiom of choice (please let me know if you figure out whether or not it is possible to construct such an agent without the axiom of choice). I will also be assuming that $\mathcal{O}$ is countably infinite (if $\mathcal{O}$ is finite, such an agent is impossible, and if it is uncountable, then you can consider a countable subset).

Notice that $\mathcal{L}^{+}$ can be seen as a subset of the real vector space $\mathcal{V}:=\left\{ \sum_{O\in\mathcal{O}}\alpha_{O}O\mid\forall O\in\mathcal{O}\,\alpha_{O}\in\mathbb{R},\,\sum_{O\in\mathcal{O}}\left|\alpha_{O}\right|\, converges\right\}$ , with the addition and multiplication by scalar operations being exactly what you would expect ( $\left(\sum_{O\in\mathcal{O}}\alpha_{O}O\right)+\left(\sum_{O\in\mathcal{O}}\beta_{O}O\right)=\sum_{O\in\mathcal{O}}\left(\alpha_{O}+\beta_{O}\right)O$ , and $x\left(\sum_{O\in\mathcal{O}}\alpha_{O}O\right)=\sum_{O\in\mathcal{O}}x\alpha_{O}O$ ). A utility function $u$ can be seen as an element of the dual space of $\mathcal{V}$ . The axiom of choice implies that this vector space has a basis (in this context, a basis means a set of vectors for which any finite subset is linearly independent, and every vector is a linear combination of a finite number of basis vectors). The value of $u$ on each basis element can be chosen independently, and these choices completely determine $u$ . In particular, the basis could contain every element of $\mathcal{O}$ , and also contain $\sum_{i=1}^{\infty}2^{-i}O_{i}$ for some sequence $\left\{ O_{i}\in\mathcal{O}\right\} _{i=1}^{\infty}$ with distinct elements. Then we could have $\forall O\in\mathcal{O}\, u\left(O\right)=0$ and $u\left(\sum_{i=1}^{\infty}2^{-i}O_{i}\right)=1$ , violating the conclusion of the myth, but this meets all the VNM axioms.

The fact that there is a real-valued function on lotteries that the agent maximizes guarantees that the completeness and transitivity axioms hold, since $u\left(L\right)>u\left(M\right)$ or $u\left(L\right)=u\left(M\right)$ or $u\left(L\right)<u\left(M\right)$ (completeness), and if $u\left(L\right)\leq u\left(M\right)$ and $u\left(M\right)\leq u\left(N\right)$ then $u\left(L\right)\leq u\left(N\right)$ (transitivity). The fact that the function is linear with respect to finite sums guarantees that the continuity and independence axioms hold, since if $u\left(L\right)<u\left(M\right)<u\left(N\right)$ then $u\left(\frac{u\left(N\right)-u\left(M\right)}{u\left(N\right)-u\left(L\right)}L+\frac{u\left(M\right)-u\left(L\right)}{u\left(N\right)-u\left(L\right)}N\right)=\frac{u\left(N\right)-u\left(M\right)}{u\left(N\right)-u\left(L\right)}u\left(L\right)+\frac{u\left(M\right)-u\left(L\right)}{u\left(N\right)-u\left(L\right)}u\left(N\right)=u\left(M\right)$ (continuity), and if $u\left(L\right)<u\left(M\right)$ then for any lottery $N$ and positive probability $p$ , $u\left(pL+\left(1-p\right)N\right)=pu\left(L\right)+\left(1-p\right)u\left(N\right)<pu\left(M\right)+\left(1-p\right)u\left(N\right)=u\left(pM+\left(1-p\right)N\right)$ (independence).

Extended VNM hypothesis

The VNM utility theorem does not prove that an agent meeting its axioms will maximize the expected value of a utility function when presented with infinite lotteries, but the fact that any such agent will maximize the expected value of a utility function when presented with finite lotteries certainly seems very suggestive. With that in mind, I suggest that this be called the “extended von Neumann-Morgenstern hypothesis”:

An agent, in order to be considered rational, should maximize the expected value of a utility function over outcomes when choosing between lotteries over any (possibly infinite) number of outcomes.

Bounded and unbounded utility functions

It is perfectly possible to construct VNM-rational agents with an unbounded utility function. But all such agents will inevitably violate the extended VNM hypothesis, because it is possible to create infinite lotteries with undefined expected value. For instance, the St. Petersburg paradox can be modified to refer specifically to utilities instead of money. That is, if there is no upper bound to the agent's utility function, then there exists a sequence of outcomes $\left\{ O_{i}\right\} _{i=1}^{\infty}$ such that for each $i$ , $u\left(O_{i}\right)\geq2^{i}$ . Then the expected utility of $\sum_{i=1}^{\infty}2^{-i}O_{i}$ is $\sum_{i=1}^{\infty}2^{-i}u\left(O_{i}\right)\geq\sum_{i=1}^{\infty}2^{-i}2^{i}=\sum_{i=1}^{\infty}1$ , which does not converge. So unbounded utility functions are not compatible with the extended VNM hypothesis.

At this point, one may feel a strong temptation to come up with some way to characterize the values of infinite sums with some ordered superset of the real numbers, so that it is possible to compare nonconvergent sums. However, by the formulation of the VNM theorem solely in terms of lotteries, the utility of any lottery, such as $u\left(\sum_{i=1}^{\infty}2^{-i}O_{i}\right)$ , is a real number. So any such scheme that requires that the range of the utility function include nonreals will violate the VNM axioms. In particular, it will probably violate the archimedian axiom.

One possible response to this is to dismiss the archimedian axiom, and try to characterize agents that obey the completeness, transitivity, and independence axioms. Benja has written (section "Doing without Continuity) about this, and I find his solution fairly compelling, but it isn't clear that it helps us deal with situations like the St. Petersburg paradox. I intend to say more about nonarchimedian preferences soon.

8 comments

Comments sorted by top scores.

comment by Qiaochu_Yuan · 2013-02-22T00:32:31.233Z · LW(p) · GW(p)

Ignoring the fact that some numbers need to be non-negative and sum up to 1, the basic mathematical issue here is some well-understood subtleties involving infinite-dimensional vector spaces. More specifically, let S be an infinite set. Then we can write down the following three (real) vector spaces from S:

The vector space of finite linear combinations of elements of S.
The vector space of infinite linear combinations of elements of S such that the sum of the absolute value of the coefficients converges.
The vector space of all infinite linear combinations of elements of S.

Each of these spaces naturally sits inside of the next one. The VNM theorem should be regarded as describing certain linear functionals on the first vector space, which are uniquely determined by what they do to elements of S. Linear functionals on the second and third vector spaces are not uniquely determined by what they do to elements of S, the reason being that linear functionals only have to preserve finite linear combinations by default and this does not imply preserving infinite linear combinations. To preserve infinite linear combinations on the second vector space (a Lebesgue space ) we need some continuity hypothesis on the linear functional (Lebesgue spaces are in particular Banach spaces and have an induced topology ), which turns out to imply boundedness as a function on S essentially because of the St. Petersburg argument. The third vector space is even worse.

On the other hand, my impression is that the existence of pathological agents of the kind described in the OP (which in the language I'm using translates to pathological linear functionals on the second and third vector spaces) is independent of ZF but weaker than the axiom of choice. Similar objects such as Banach limits can be constructed using the Hahn-Banach theorem or the ultrafilter lemma. I've posted a math.stackexchange question about this.

I have serious doubts that any of these issues are relevant to agents in the real world.

Replies from: AlexMennen, Eugine_Nier

↑ comment by AlexMennen · 2013-02-22T01:11:47.588Z · LW(p) · GW(p)

That's a better explanation than mine. And thanks for asking what assumptions it takes for such agents to exist where people are more likely to know the answer; I should have thought of that.

I have serious doubts that any of these issues are relevant to agents in the real world.

Agreed.

↑ comment by Eugine_Nier · 2013-02-22T03:34:14.173Z · LW(p) · GW(p)

I have serious doubts that any of these issues are relevant to agents in the real world.

I'm not sure about that. One relevant question is what happens if we restrict the set of priors our Bayesian utilitarians can have.

comment by jsalvatier · 2013-02-21T22:09:23.792Z · LW(p) · GW(p)

This needs a summary at the top.

Replies from: AlexMennen

↑ comment by AlexMennen · 2013-02-22T02:26:46.621Z · LW(p) · GW(p)

Good idea. Edited.

comment by Fhyve · 2013-02-23T21:24:20.798Z · LW(p) · GW(p)

Why do we even need to deal with outcomes in the first place? For any outcome O, it is equivalent to the lottery L = pO where p = 1.

Also, how do you do LaTeX here?

Replies from: AlexMennen, Eugine_Nier

↑ comment by AlexMennen · 2013-02-24T01:09:15.730Z · LW(p) · GW(p)

You don't need to talk about outcomes, but I like to talk in terms of outcomes anyway because it makes it easier for me to interpret the lotteries. If you would rather not talk about outcomes, it shouldn't be too hard to mentally translate everything in the post in terms of lotteries.

↑ comment by Eugine_Nier · 2013-02-24T00:26:33.276Z · LW(p) · GW(p)

Also, how do you do LaTeX here?

Useful links for that here and here.

VNM agents and lotteries involving an infinite number of possible outcomes

Contents

Outcomes versus Lotteries

Infinite lotteries

Extended VNM hypothesis

Bounded and unbounded utility functions

8 comments