Concave Utility Question

post by Scott Garrabrant · 2023-04-15T00:14:58.895Z · LW · GW · 18 comments

This is a question post.

Contents

  Q5: Do A1, A2, A3, and A4 together imply C2?
None
  Answers
    15 AlexMennen
    3 SamEisenstat
    3 Scott Garrabrant
    2 Scott Garrabrant
    2 Scott Garrabrant
    0 James Payor
None
18 comments

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  be the space of all lotteries over these outcomes, and let  be a relation on . We write  if A  B and B  A. We write  if  but not 

Here are some axioms we can assume about :

A1. For all , either  or  (or both).

A2. For all , if , and , then .

A3. For all , if , and , then there exists a  such that .

A4. For all , and  if , then .

A5. For all , and , if  and , then .

Here is one bonus axiom:

B1. For all , and  if and only if .

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

Finally, here are some conclusions of successively increasing strength:

C1. There exists a function  such that  if and only if .

C2. Further, we require  is quasi-concave.

C3. Further, we require  is continuous.

C4. Further, we require  is concave.

C5. Further, we require  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  such that  if and only if ? [ANSWER: NO]

(i.e. We do not require  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 , if , then there exists some  such that .

(Really, we don't need to assume  is already in . We just need it to be possible to add a , and extend our preferences in a way that satisfies the other axioms, and A3 will imply that such a lottery was already in . 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.

Answers

answer by AlexMennen · 2023-04-15T01:10:10.024Z · LW(p) · GW(p)

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.

comment by Scott Garrabrant · 2023-04-15T01:23:51.716Z · LW(p) · GW(p)

Nice! This, of course, seems like something we should salvage, by e.g. adding an axiom that if A is strictly preferred to B, there should be a lottery strictly between them.

Replies from: AlexMennen, Scott Garrabrant
comment by AlexMennen · 2023-04-15T04:49:49.553Z · LW(p) · GW(p)

I think the way I would rule out my counterexample is by strengthening A3 to if  and  then there is ...

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2023-04-15T05:07:06.512Z · LW(p) · GW(p)

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

Replies from: AlexMennen
comment by AlexMennen · 2023-04-15T05:31:54.497Z · LW(p) · GW(p)

Oh, derp. You're right.

comment by Scott Garrabrant · 2023-04-15T02:00:21.424Z · LW(p) · GW(p)

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

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2023-04-15T03:14:20.748Z · LW(p) · GW(p)

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 , but does not hit 0, and then jumps to 0 when probability of  is 1.

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2023-04-15T03:19:02.295Z · LW(p) · GW(p)

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

comment by Scott Garrabrant · 2023-04-15T01:31:12.362Z · LW(p) · GW(p)

I meant the conclusions to all be adding to the previous one, so this actually also answers the main question I stated, by violating continuity, but not the main question I care about. I will edit the post to say that I actually care about concavity, even without continuity.

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2023-04-15T01:53:44.994Z · LW(p) · GW(p)

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,

answer by SamEisenstat · 2023-04-24T22:23:15.975Z · LW(p) · GW(p)

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. 

  1. ^

    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

answer by Scott Garrabrant · 2023-04-15T08:09:20.803Z · LW(p) · GW(p)

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.

comment by Scott Garrabrant · 2023-04-15T08:12:37.022Z · LW(p) · GW(p)

I am skeptical that it will be possible to salvage any nice VNM-like theorem here that makes it all the way to concavity. It seems like the jump necessary to fix this counterexample will be hard to express in terms of only a preference relation.

answer by Scott Garrabrant · 2023-04-15T04:32:32.817Z · LW(p) · GW(p)

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

answer by Scott Garrabrant · 2023-04-15T04:14:42.388Z · LW(p) · GW(p)

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.

answer by James Payor · 2023-04-15T06:10:38.148Z · LW(p) · GW(p)

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.

comment by Scott Garrabrant · 2023-04-15T06:41:10.461Z · LW(p) · GW(p)

Alex's counterexample as stated is not a counterexample to Q4, since it is in fact concave.
 

I believe your counterexample violates A5, taking , and .

Replies from: JamesPayor
comment by James Payor (JamesPayor) · 2023-04-15T15:20:58.904Z · LW(p) · GW(p)

Seems right, oops! A5 is here saying that if any part of my 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

Comments sorted by top scores.

comment by So8res · 2023-04-16T00:35:34.205Z · LW(p) · GW(p)

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:

  1. , by and and the extremeness of .
  2. , by A4.
  3. , 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.

comment by Scott Garrabrant · 2023-04-15T00:47:42.432Z · LW(p) · GW(p)

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.

comment by Vanessa Kosoy (vanessa-kosoy) · 2023-04-16T08:37:47.720Z · LW(p) · GW(p)

I propose the axioms A1-A3 together with

B2. If  then for any  we have 
B3. If  and , then for any  we have 

I suspect that these imply C4.

Replies from: Scott Garrabrant, Scott Garrabrant
comment by Scott Garrabrant · 2023-04-16T18:45:06.696Z · LW(p) · GW(p)

Your B2 is going to rule out a bunch of concave functions. I was hoping to only use axioms consistent with all (continuous) concave functions.

Replies from: vanessa-kosoy
comment by Vanessa Kosoy (vanessa-kosoy) · 2023-04-17T07:21:42.322Z · LW(p) · GW(p)

Oops. What if instead of "for any " we go with "there exists "?

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2023-04-17T07:59:18.572Z · LW(p) · GW(p)

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 [LW(p) · GW(p)].

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

comment by Scott Garrabrant · 2023-04-16T18:49:42.547Z · LW(p) · GW(p)

Your B3 is equivalent to A4 (assuming A1-3).

comment by Scott Garrabrant · 2023-04-15T01:00:36.106Z · LW(p) · GW(p)

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: .

comment by James Payor (JamesPayor) · 2023-04-15T02:25:23.192Z · LW(p) · GW(p)

[Edit: yeah nevermind I have the inequality backwards [LW(p) · GW(p)]]

A5 seems too strong?

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

  1. If then
  2. If then

So if and then ?

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

Replies from: Scott Garrabrant, Scott Garrabrant, JamesPayor
comment by Scott Garrabrant · 2023-04-15T02:50:45.862Z · LW(p) · GW(p)

You have the inequality backwards. You can't apply A5 when the mixture is better than the endpoint, only when the mixture is worse than the endpoint.

Replies from: JamesPayor
comment by James Payor (JamesPayor) · 2023-04-15T03:02:34.207Z · LW(p) · GW(p)

Got it, thanks!

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2023-04-15T06:58:45.138Z · LW(p) · GW(p)

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.

comment by Scott Garrabrant · 2023-04-15T03:10:38.626Z · LW(p) · GW(p)

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.

comment by James Payor (JamesPayor) · 2023-04-15T02:33:03.217Z · LW(p) · GW(p)

The way I understand A4 is that it says "if moving by is good, then moving by any fraction is also good".

And A5 says "if moving by is good, then moving by any multiple is also good", which is much stronger.

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2023-04-15T02:52:57.722Z · LW(p) · GW(p)

Your understanding of A4 is right. In A5, "good" should be replaced with "bad."

Replies from: Scott Garrabrant, JamesPayor
comment by Scott Garrabrant · 2023-04-15T03:08:52.579Z · LW(p) · GW(p)

(and everywhere you say "good" and "bad", they are the non-strict versions of the words)

Replies from: JamesPayor
comment by James Payor (JamesPayor) · 2023-04-15T03:10:01.123Z · LW(p) · GW(p)

Okay, I now think A5 implies: "if moving by is good, then moving by any negative multiple is bad". Which checks out to me re concavity.