Concave Utility Question

15Alex Mennen

5Scott Garrabrant

4Scott Garrabrant

4Scott Garrabrant

4Scott Garrabrant

4Alex Mennen

6Scott Garrabrant

6Alex Mennen

4Scott Garrabrant

4Scott Garrabrant

3Sam Eisenstat

3Scott Garrabrant

2Scott Garrabrant

2Scott Garrabrant

2Scott Garrabrant

0James Payor

3Scott Garrabrant

1James Payor

12Nate Soares

6Scott Garrabrant

2Vanessa Kosoy

6Scott Garrabrant

2Vanessa Kosoy

4Scott Garrabrant

2Scott Garrabrant

2Scott Garrabrant

1James Payor

3Scott Garrabrant

1James Payor

3Scott Garrabrant

2Scott Garrabrant

1James Payor

3Scott Garrabrant

2Scott Garrabrant

1James Payor

1James Payor

New Answer

New Comment

6 Answers sorted by

Q2: No. Counterexample: Suppose there's one outcome such that all lotteries are equally good, except for the lottery than puts probability 1 on , which is worse than the others.

410mo

That proposed axiom to add does not work. Consider the function on lotteries over {x,y,z} that gives utility 1 if z is supported, and otherwise gives utility equality to the probability of x. This function is concave but not continuous, satisfies A1-A5 and the extra axiom I just proposed, and cannot be made continuous.

410mo

Oh, no, I made a mistake, this counterexample violates A3. However, the proposed fix still doesn't work, because you just need a function that is decreasing in probability of x, but does not hit 0, and then jumps to 0 when probability of x is 1.

410mo

Oh, nvm, that is fine, maybe it works.

310mo

I think the way I would rule out my counterexample is by strengthening A3 to if A≻B and B≻C then there is p∈(0,1)...

510mo

That does not rule out your counterexample. The condition is never met in your counterexample.

410mo

Oh, derp. You're right.

410mo

I edited the post to remove the continuity assumption from the main conclusion. However, my guess is that if we get a VNM-like result, we will want to add back in another axiom that gives us continuity,

Q5 is true if (as you assumed), the space of lotteries is the space of distributions over a finite set. (For a general convex set, you can get long-line phenomena.)

First, without proof, I'll state the following generalization.

**Theorem 1.** Let be a relation on a convex space satisfying axioms A1, A2, A3, and the following additional continuity axiom. For all , the set

is open in . Then, there exists a function from to the long line such that iff .

The proof is not too different, but simpler, if we also assume A4. In particular, we no longer need the extra continuity axiom, and we get a stronger conclusion. Nate sketched part of the proof of this already, but I want to be clearer about what is stated and skip fewer steps. In particular, I'm not sure how Nate's hypotheses rule out examples that require long-line-valued functions—maybe he's assuming that the domain of the preference relation is a finite-dimensional simplex like I am, but none of his arguments use this explicitly.

**Theorem 2.** Let be a relation on a finite-dimensional simplex satisfying axioms A1-A4. Then, there is a quasiconcave function such that iff .

First, I'll set up some definitions and a lemma. For any lotteries , , let denote the line segment

We say that preferences are increasing along a line segment if whenever , we have

We will also use open and half-open interval notation in the corresponding way.

**Lemma.** Let be a preference relation on a finite-dimensional simplex satisfying axioms A1-A4. Then, there are -minimal and -maximal elements in .

**Proof.** First, we show that there is a minimal element. Axiom A4 states that for any mixture , either or . By induction, it follows more generally that any convex combination C of finitely many elements satisfies for some . But every element is a convex combination of the vertices of , so some vertex of is -minimal.

The proof that there is a maximal element is more complex. Consider the family of sets

This is a prefilter, so since is compact ( here carries the Euclidean metric), it has a cluster point . Either will be a maximal element, or we will find some other maximal element. In particular, take any . We are done if is a maximal element; otherwise, pick . By the construction of , for every , we can pick some within a distance of from B. Now, if we show that itself satisfies , it will follow that is maximal.

The idea is to pass from our sequence , with limit , to another sequence lying on a line segment with endpoint . We can use axiom A4, which is a kind of convexity, to control the preference relation on convex combinations of our points , so these are the points that we will construct along a line segment. Once we have this line segment, we can finish by using A3, which is a kind of continuity restricted to line segments, to control itself.

Let be the set of lotteries in the affine span of the set . Then, if we take some index set such that is a maximal affinely independent tuple, it follows that affinely generates . Hence, the convex combination

i.e. the barycenter of the simplex with vertices at , is in the interior of the convex hull of relative to , so we can pick some such that the -ball around relative to is contained in this simplex.

Now, we will see that every lottery in the set satisfies . For any , pick so that is in the -ball around . Since the tangent vector has length less than , the lottery

is in the -ball around , and it is in , so it is in the simplex with vertices . Then, by A4, and by hypothesis. So, applying A4 again,

Using A4 one more time, it follows that every lottery

satisfies , and hence every lottery .

Now we can finish up. If then, using A3 and the fact that , there would have to be some lottery in that is -equivalent to A, but this would contradict what we just concluded. So, , and so B is -maximal.

**Proof of Theorem 2.** Let be a -minimal and a -maximal element of . First, we will see that preferences are increasing on , and then we will use this fact to construct a function and show that it has the desired properties. Suppose preferences we not increasing; then, there would be such that is closer to while is closer to , and . Then, would be a convex combination of and , but by the maximality of , contradicting A4.

Now we can construct our utility function using A3; for each -class , we have , so there is some^{[1]} such that

Then, let for all . Since preferences are increasing on , it is immediate that if , then . Conversely, if , we have two cases. If , then , so , and so . Finally, if , then by construction.

Finally, since for all we have iff , it follows immediately that is quasiconcave by A4.

^{^}Nate mentions using choice in his answer, but here at least the use of choice is removable. Since is monotone on , the intersection of the -class with is a subinterval of , so we can pick based on the midpoint of that interval

The answers to Q3, Q4 and Q6 are all no. I will give a sketchy argument here.

Consider the one dimensional case, where the lotteries are represented by real numbers in the interval , and consider the function given by . Let be the preference order given by if and only if .

is continuous and quasi-concave, which means is going to satisfy A1, A2, A3, A4, and B2. Further, since is monotonically increasing up to the unique argmax, and then monotonically decreasing, is going to satisfy A5.

is not concave, but we need to show there is not another concave function giving the same preference relation as . The only way to keep the same preference relation is to compose with a strictly monotonic function , so ).

If is smooth, we have a problem, since . However, since, must be on some , but concavity would require to be decreasing.

In order to remove the inflection point at , we need to flatten it out with some that has infinite slope at . For example, we could take . However, any f that removes the inflection point at , will end up adding an inflection point at , which will have a infinite negate slope. This newly created inflection point will cause a problem for similar reasons.

Claim: A1, A2, A3, A5, and B2 imply A4.

Proof: Assume we have a preference ordering that satisfies A1, A2, A3, A5, and B2, and consider lotteries , and , with . Let . It suffices to show . Assume not, for the purpose of contradiction. Then (by axiom A1), . Thus by axiom B2 there exists a such that . By axiom A3, we may assume for some . Observe that where . is positive, since otherwise . Thus, we can apply A5 to get that since , we have . Thus , a contradiction.

The answer to Q1 is no, using the same counter example here. However, the spirit of my original question lives on in Q4 (and Q6).

No on Q4? I think Alex's counterexample applies to Q4 as well.

(EDIT: Scott points out I'm wrong here, Alex's counterexample doesn't apply, and mine violates A5.)

In particular I think A4 and A5 don't imply anything about the rate of change as we move between lotteries, so we can have movements too sharp to be concave. We only have quasi-concavity.

My version of the counterexample: you have two outcomes and , we prefer anything with equally, and we otherwise prefer higher .

If you give me a corresponding , it must satisfy , but convexity demands that , which in this case means , a contradiction.

110mo

Seems right, oops! A5 is here saying that if any part of my u is flat it had better stay flat!
I think I can repair my counterexample but looks like you've already found your own.

18 comments, sorted by Click to highlight new comments since: Today at 11:22 PM

Below is a sketch of an argument that might imply that the answer to Q5 is (clasically) 'yes'. (I thought about a question that's probably the same a little while back, and am reciting from cache, without checking in detail that my axioms lined up with your A1-4).

Pick a lottery with the property that forall with and , forall , we have . We will say that is "extreme(ly high)".

Pick a lottery with .

Now, for any with , define to be the guaranteed by continuity (A3).

**Lemma**: forall with , .

Proof:

- , by and and the extremeness of .
- , by A4.
- , by some reduction.

We can use this lemma to get that implies , because , and , so invoke the above lemma with and .

Next we want to show that implies . I think this probably works, but it appears to require either the axiom of choice (!) or a strengthening of one of A3 or A4. (Either strengthen A3 to guarantee that if then it gives the same in both cases, or strengthen A4 to add that if then , or define not from A3 directly, but by using choice to pick out a for each -equivalence-class of lotteries.) Once you've picked one of those branches, the proof basically proceeds by contradiction. (And so it's not terribly constructive, unless you can do constructively.)

The rough idea is: if but then you can use the above lemma to get a contradiction, and so you basically only need to consider the case where in which case you want , which you can get by definition (if you use the axiom of choice), or directly by the strengthening of A3. And... my cache says that you can also get it by the strengthening of A4, albeit less directly, but I haven't reloaded that part of my cache, so \shrug I dunno.

Next we argue that this function is unique up to postcomposition by... any strictly isotone endofunction on the reals? I think? (Perhaps unique only among quasiconvex functions?) I haven't checked the details.

Now we have a class of utility-function-ish-things, defined only on with , and we want to extend it to all lotteries.

I'm not sure if this step works, but the handwavy idea is that for any lottery that you want to extend to include, you should be able to find a lower and an extreme higher that bracket it, at which point you can find the corresponding (using the above machinery), at which point you can (probably?) pick some canonical strictly-isotone real endofunction to compose with it that makes it agree with the parts of the function you've defined so far, and through this process you can extend your definition of to include any lottery. *handwave handwave.*

Note that the exact function you get depends on how you find the lower and higher , and which isotone function you use to get all the pieces to line up, but when you're done you can probably argue that the whole result is unique up to postcomposition by a strictly isotone real endofunction, of which your construction is a fine representative.

This gets you C1. My cache says it should be easy to get C2 from there, and the first paragraph of "Edit 3" to the OP suggests the same, so I haven't checked this again.

I believe using A4 (and maybe also A5) in multiple places will be important to proving a positive result. This is because A1, A2, and A3 are extremely week on their own.

A1-A3 is not even enough to prove C1. To see a counterexample, take any well ordering on , and consider the preference ordering over the space of lotteries on a two element set of deterministic outcomes. If two lotteries have probabilities of the first outcome that differ by a rational number, they are equivalent, otherwise, you compare them according to your well ordering. This clearly satisfies A1 and A2, and it satisfies A3, since every nonempty open set contains lotteries incomparable with any given lottery. However, has a continuum length ascending chain of strict preference, and so cant be captured in a function to the interval.

Further, one might hope that C1 together with A3 would be enough to conclude C2, but this is also not possible, since there are discontinuous functions on the simplex that are continuous when restricted to any line segment in the domain.

In both of these cases, it seems to me like there is hope that A4 provides enough structure to eliminate the pathological counterexamples, since there is much less you can do with convex upsets.

Then it is equivalent to the thing I call B2 in edit 2 in the post (Assuming A1-A3).

In this case, your modified B2 is my B2, and your B3 is my A4, which follows from A5 assuming A1-A3 and B2, so your suspicion that these imply C4 is stronger than my Q6, which is false, as I argue here.

However, without A5, it is actually much easier to see that this doesn't work. The counterexample here satisfies my A1-A3, your weaker version of B2, your B3, and violates C4.

To see why A1-A4 is not enough to prove C4 on its own, consider the preference relation on the space of lotteries between two outcomes X and Y such that all lotteries are equivalent if , and if , higher values of are preferred. This satisfies A1-A4, but cannot be expressed with a concave function, since we would have to have , contradicting concavity. We can, however express it with a quasi-concave function: .

[Edit: yeah nevermind I have the inequality backwards]

A5 seems too strong?

Consider lotteries and , and a mixture in between. Applying A5 twice gives:

- If then
- If then

So if and then ?

Either I'm confused or A5 is a stricter condition than concavity.

You can also think of A5 in terms of its contrapositive: For all , if , then for all

This is basically just the strict version of A4. I probably should have written it that way instead. I wanted to use instead of , because it is closer to the base definition, but that is not how I was natively thinking about it, and I probably should have written it the way I think about it.

I haven't actually thought about whether A5 implies A4 though. It is plausible that it does. (together with A1-A3, or some other simple axioms,)

When , we get A4 from A5, so it suffices to replace A4 with the special case that . If , and , a mixture of and , then all we need to do is have any Y such that , then we can get between and by A3, and then will also be a mixture of and , contradicting A5, since .

A1,A2,A3,A5 do not imply A4 directly, because you can have the function that assigns utility 0 to a fair coin flip between two options, and utility 1 to everything else. However, I suspect when we add the right axiom to imply continuity, I think that will be sufficient to also allow us to remove A4, and only have A5.

This post will just be a concrete math question. I am interested in this question because I have recently come tor reject the independence axiom of VNM, and am thus playing with some weaker versions.

Let Ω be a finite set of deterministic outcomes. Let L be the space of all lotteries over these outcomes, and let ⪰ be a relation on L. We write A∼B if A ⪰ B and B ⪰ A. We write A≻B if A⪰B but not A∼B.

Here are some axioms we can assume about ⪰:

A1. For all A,B∈L, either A⪰B or B⪰A (or both).

A2. For all A,B,C∈L, if A⪰B, and B⪰C, then A⪰C.

A3. For all A,B,C∈L, if A⪰B, and B⪰C, then there exists a p∈[0,1] such that B∼pA+(1−p)C.

A4. For all A,B∈L, and p∈[0,1] if A⪰B, then pA+(1−p)B⪰B.

A5. For all A,B∈L, and p∈[0,1], if p>0 and B⪰pA+(1−p)B, then B⪰A.

Here is one bonus axiom:

B1. For all A,B,C∈L, and p∈[0,1], A⪰B if and only if pA+(1−p)C⪰pB+(1−p)C.

(Note that B1 is stronger than both A4 and A5)

Finally, here are some conclusions of successively increasing strength:

C1. There exists a function u:L→[0,1] such that A⪰B if and only if u(A)≥u(B).

C2. Further, we require u is quasi-concave.

C3. Further, we require u is continuous.

C4. Further, we require u is concave.

C5. Further, we require u is linear.

The standard VNM utility theorem can be thought of as saying A1, A2, A3, and B1 together imply C5.

Here is the main question I am curious about:

Q1: Do A1, A2, A3, A4, and A5 together imply C4?

[ANSWER: NO](If no, how can we salvage C4, by adding or changing some axioms?)

Here are some sub-questions that would constitute significant partial progress, and that I think are interesting in their own right:

Q2: Do A1, A2, A3, and A4 together imply C3?

[ANSWER: NO]Q3: Do C3 and A5 together imply C4?

[ANSWER: NO](Feel free to give answers that are only partial progress, and use this space to think out loud or discuss anything else related to weaker versions of VNM.)

EDIT:

AlexMennen actually resolved the question in the negative as stated, but my curiosity is not resolved, since his argument is violating continuity, and I really care about concavity. My updated main question is now:

Q4: Do A1, A2, A3, A4, and A5 together imply that there exists a concave function u:L→[0,1] such that A⪰B if and only if u(A)≥u(B)?

[ANSWER: NO](i.e. We do not require u to be continuous.)

This modification also implies interest in the subquestion:

Q5: Do A1, A2, A3, and A4 together imply C2?EDIT 2:

Here is another bonus axiom:

B2. For all A,B∈L, if A≻B, then there exists some C∈L such that A≻C≻B.

(Really, we don't need to assume C is already in L. We just need it to be possible to add a C, and extend our preferences in a way that satisfies the other axioms, and A3 will imply that such a lottery was already in L. We might want to replace this with a cleaner axiom later.)

Q6: Do A1, A2, A3, A5, and B2 together imply C4?

[ANSWER: NO]EDIT 3:

We now have negative answers to everything other than Q5, which I still think is pretty interesting. We could also weaken Q5 to include other axioms, like A5 and B2. Weakening the conclusion doesn't help, since it is easy to get C2 from C1 and A4.

I would still really like some axioms that get us all the way to a concave function, but I doubt there will be any simple ones. Concavity feels like it really needs more structure that does not translate well to a preference relation.