New Answer

New Comment

6 Answers sorted by
top scoring

Apr 15, 2023

102

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

[-]Scott Garrabrant3y40

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.

3AlexMennen3y

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

5Scott Garrabrant3y

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

4AlexMennen3y

Oh, derp. You're right.

4Scott Garrabrant3y

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.

4Scott Garrabrant3y

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.

4Scott Garrabrant3y

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

[-]Scott Garrabrant3y40

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.

4Scott Garrabrant3y

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,

SamEisenstat

Apr 24, 2023

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 $L$ satisfying axioms A1, A2, A3, and the following additional continuity axiom. For all $A, B_{1}, B_{2}, C \in L$ , the set

{p \in [0, 1] ∣ A ≺ p B_{1} + (1 - p) B_{2} ≺ C}

is open in $[0, 1]$ . Then, there exists a function $u$ from $L$ to the long line such that $u (A) \leq u (B)$ iff $A ⪯ B$ .

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 $L = Δ Ω$ satisfying axioms A1-A4. Then, there is a quasiconcave function $u : L \to R$ such that $u (A) \leq u (B)$ iff $A ⪯ B$ .

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

{p A + (1 - p) B ∣ p \in [0, 1]} .

We say that preferences are increasing along a line segment $[A, B]$ if whenever $p \leq q$ , we have

(1 - p) A + p B ⪯ (1 - q) A + q B .

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 $L = Δ Ω$ satisfying axioms A1-A4. Then, there are $⪯$ -minimal and -maximal elements in $L$ .

Proof. First, we show that there is a minimal element. Axiom A4 states that for any mixture $C = p A + (1 - p) B$ , either $C ⪰ A$ or $C ⪰ B$ . By induction, it follows more generally that any convex combination C of finitely many elements ${(A_{i})}_{i \in I}$ satisfies $C ⪰ A_{i}$ for some $i \in I$ . But every element is a convex combination of the vertices of $L$ , so some vertex of $L$ is $⪯$ -minimal.

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

F = {{B \in L ∣ B ⪰ A} ∣ A \in L} .

This is a prefilter, so since $L$ is compact ( $L$ here carries the Euclidean metric), it has a cluster point $B$ . Either $B$ will be a maximal element, or we will find some other maximal element. In particular, take any $A \in L$ . We are done if $A$ is a maximal element; otherwise, pick $A^{'} ≻ A$ . By the construction of $F$ , for every $n \in N$ , we can pick some $C_{n} ⪰ A^{'}$ within a distance of $\frac{1}{n}$ from B. Now, if we show that $B$ itself satisfies $B ⪰ A$ , it will follow that $B$ is maximal.

The idea is to pass from our sequence ${(C_{n})}_{n \in N}$ , with limit $B$ , to another sequence lying on a line segment with endpoint $B$ . We can use axiom A4, which is a kind of convexity, to control the preference relation on convex combinations of our points $C_{n}$ , 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 $B$ itself.

Let $S \subseteq L$ be the set of lotteries in the affine span of the set ${C_{n}}_{n \in N}$ . Then, if we take some index set $I \subseteq N$ such that ${(C_{n})}_{n \in I}$ is a maximal affinely independent tuple, it follows that ${C_{n}}_{n \in I}$ affinely generates $S$ . Hence, the convex combination

D = \sum n \in I \frac{1}{| I |} C_{n},

i.e. the barycenter of the simplex with vertices at ${(C_{n})}_{n \in I}$ , is in the interior of the convex hull of ${C_{n}}_{n \in I}$ relative to $S$ , so we can pick some $r > 0$ such that the $r$ -ball around $D$ relative to $S$ is contained in this simplex.

Now, we will see that every lottery $E$ in the set $(B, D]$ satisfies $E ⪰ A^{'}$ . For any $ε > 0$ , pick $k$ so that $C_{k}$ is in the $ε$ -ball around $B$ . Since the tangent vector $v = B - C_{k}$ has length less than $ε$ , the lottery

F = D + \frac{r}{ε} (B - C_{k})

is in the $r$ -ball around $D$ , and it is in $S$ , so it is in the simplex with vertices ${(C_{n})}_{n \in I}$ . Then, $F ⪰ A^{'}$ by A4, and $C_{k} ⪰ A^{'}$ by hypothesis. So, applying A4 again,

A^{'} ⪯ \frac{r}{r + ε} C_{k} + \frac{ε}{r + ε} F = \frac{r}{r + ε} B + \frac{ε}{r + ε} D .

Using A4 one more time, it follows that every lottery

E \in [\frac{r}{r + ε} B + \frac{ε}{r + ε} D, D]

satisfies $E ⪰ A^{'}$ , and hence every lottery $E \in (B, D]$ .

Now we can finish up. If $B ≺ A$ then, using A3 and the fact that $D ⪰ A^{'} ≻ A$ , there would have to be some lottery in $[B, D]$ that is $⪯$ -equivalent to A, but this would contradict what we just concluded. So, $B ⪰ A$ , and so B is $⪯$ -maximal. $□$

Proof of Theorem 2. Let $C$ be a $⪯$ -minimal and $D$ a $⪯$ -maximal element of $L$ . First, we will see that preferences are increasing on $[C, D]$ , and then we will use this fact to construct a function $L \to R$ and show that it has the desired properties. Suppose preferences we not increasing; then, there would be $A, B \in [C, D]$ such that $A$ is closer to $C$ while $B$ is closer to $D$ , and $A ≻ B$ . Then, $B$ would be a convex combination of $A$ and $D$ , but $B ≺ A ⪯ D$ by the maximality of $D$ , contradicting A4.

Now we can construct our utility function $u : L \to R$ using A3; for each $\sim$ -class $[A]$ , we have $C ⪯ A ⪯ D$ , so there is some^[1] $p \in [0, 1]$ such that

(1 - p) C + p D \sim A .

Then, let $u (A^{'}) = p$ for all $A^{'} \in [A]$ . Since preferences are increasing on $[C, D]$ , it is immediate that if $u (A) \leq u (B)$ , then $A ⪯ B$ . Conversely, if $A ⪯ B$ , we have two cases. If $A ≺ B$ , then $B ⋠ A$ , so $u (B) ≰ u (A)$ , and so $u (A) \leq u (B)$ . Finally, if $A \sim B$ , then $u (A) = u (B)$ by construction.

Finally, since for all $A, B \in L$ we have $u (A) \leq u (B)$ iff $A ⪯ B$ , it follows immediately that $u$ 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 $[C, D]$ , the intersection of the $\sim$ -class $[A]$ with $[C, D]$ is a subinterval of $[C, D]$ , so we can pick $p$ based on the midpoint of that interval

Scott Garrabrant

Apr 15, 2023

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 $u : L \to [0, 1]$ given by $u (x) = \frac{1}{2} - (x - \frac{1}{3})^{3} (x - \frac{2}{3})$ . Let $⪰$ be the preference order given by $x ⪰ y$ if and only if $u (x) \geq u (y)$ .

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

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

If $f$ is smooth, we have a problem, since $v^{'} (\frac{1}{3}) = f^{'} (u (\frac{1}{3})) u^{'} (\frac{1}{3}) = f^{'} (\frac{1}{2}) 0 = 0$ . However, since, $v^{'}$ must be on some $x > \frac{1}{3}$ , but concavity would require $v^{'}$ to be decreasing.

In order to remove the inflection point at $x = \frac{1}{3}$ , we need to flatten it out with some $f$ that has infinite slope at $\frac{1}{2}$ . For example, we could take $f (z) = \sqrt[3]{z - \frac{1}{2}}$ . However, any f that removes the inflection point at $x = \frac{1}{3}$ , will end up adding an inflection point at $x = \frac{2}{3}$ , which will have a infinite negate slope. This newly created inflection point will cause a problem for similar reasons.

[-]Scott Garrabrant3y20

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.

Scott Garrabrant

Apr 15, 2023

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

Scott Garrabrant

Apr 15, 2023

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 $p \in [0, 1]$ , with $A ⪰ B$ . Let $C = p A + (1 - p) B$ . It suffices to show $C ⪰ B$ . Assume not, for the purpose of contradiction. Then (by axiom A1), $B ≻ C$ . Thus by axiom B2 there exists a $D \in L$ such that $B ≻ D ≻ C$ . By axiom A3, we may assume $D = q B + (1 - q) C$ for some $q \in [0, 1]$ . Observe that $C = r A + (1 - r) D$ where $r = \frac{p q}{1 - p + p q} \in [0, 1]$ . $r$ is positive, since otherwise $C = D ≻ C$ . Thus, we can apply A5 to get that since $D ⪰ r A + (1 - r) D$ , we have $D ⪰ A$ . Thus $D ⪰ A ⪰ B ≻ D$ , a contradiction.

James Payor

Apr 15, 2023*

0-2

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 $\neg X$ , we prefer anything with $P (X) \leq \frac{1}{2}$ equally, and we otherwise prefer higher $P (X)$ .

If you give me a corresponding $u (p)$ , it must satisfy $u (0) = u (\frac{1}{2}) < u (1)$ , but convexity demands that $u (\frac{1}{2}) \geq \frac{1}{2} u (0) + \frac{1}{2} u (1)$ , which in this case means $u (0) \geq u (1)$ , a contradiction.

[-]Scott Garrabrant3y30

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

I believe your counterexample violates A5, taking $B = \neg X$ , $A = X$ , and $p = \frac{1}{2}$ .

1James Payor3y

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

top scoring

Click to highlight new comments since: Today at 10:29 PM

[-]So8res3y*80

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 $A, B$ with $A ⪯ Z$ and $B ⪯ Z$ , forall $p \in [0, 1]$ , we have $(1 - p) A + p B ⪯ Z$ . We will say that $Z$ is "extreme(ly high)".

Pick a lottery $X$ with $X ⪯ Z$ .

Now, for any $Y$ with $X ⪯ Y ⪯ Z$ , define $u (Y)$ to be the $p$ guaranteed by continuity (A3).

Lemma: forall $α, β \in [0, 1]$ with $α \leq β$ , $(1 - α) X + α Z ⪯ (1 - β) X + β Z$ .

Proof:

$(1 - α) X + α Z ⪯ Z$ , by $X ⪯ Z$ and $Z ⪯ Z$ and the extremeness of $Z$ .
$(1 - α) X + α Z ⪯ \frac{1 - α}{1 - β} ((1 - α) X + α Z) + (1 - \frac{1 - α}{1 - β}) Z$ , by A4.
$(1 - α) X + α Z ⪯ (1 - β) X + β Z$ , by some reduction.

We can use this lemma to get that $u (A) \leq u (B)$ implies $A ⪯ B$ , because $A \sim (1 - u (A)) X + u (A) Z$ , and $B \sim (1 - u (B)) X + u (B) Z$ , so invoke the above lemma with $α = u (A)$ and $β = u (B)$ .

Next we want to show that $A ⪯ B$ implies $u (A) \leq u (B)$ . 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 $B_{1} \sim B_{2}$ then it gives the same $p$ in both cases, or strengthen A4 to add that if $B ≺ A$ then $B ≺ p A + (1 - p) B$ , or define $u (A)$ not from A3 directly, but by using choice to pick out a $p$ for each $\sim$ -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 $\neg \neg (A ≺ B) \to (A ≺ B)$ constructively.)

The rough idea is: if $A ≺ B$ but $u (A) \geq u (B)$ then you can use the above lemma to get a contradiction, and so you basically only need to consider the case where $A \sim B$ in which case you want $u (A) = u (B)$ , 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 $u$ 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 $Y$ with $X ⪯ Y ⪯ Z$ , 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 $Y$ that you want to extend $u$ to include, you should be able to find a lower $X$ and an extreme higher $Z$ that bracket it, at which point you can find the corresponding $u$ (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 $u$ to include any lottery. handwave handwave.

Note that the exact function you get depends on how you find the lower $X$ and higher $Z$ , 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.

[-]Scott Garrabrant3y30

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.

[-]Vanessa Kosoy3y20

I propose the axioms A1-A3 together with

B2. If then for any $p \in (0, 1)$ we have $A ≺ p A + (1 - p) B ≺ B$
B3. If $A ⪯ B$ and $A ⪯ C$ , then for any $p \in [0, 1]$ we have $A ⪯ p B + (1 - p) C$

I suspect that these imply C4.

[-]Scott Garrabrant2y62

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.

[-]Vanessa Kosoy2y20

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

[-]Scott Garrabrant2y40

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.

[-]Scott Garrabrant2y20

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

[-]Scott Garrabrant3y*20

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 $P (X) \geq \frac{1}{2}$ , higher values of $P (X)$ are preferred. This satisfies A1-A4, but cannot be expressed with a concave function, since we would have to have $u (\frac{X + Y}{2}) = u (X) < \frac{u (X) + u (Y)}{2}$ , contradicting concavity. We can, however express it with a quasi-concave function: $U (p X + (1 - p) Y) = max (0, p - \frac{1}{2})$ .

[-]James Payor3y10

[Edit: yeah nevermind I have the inequality backwards]

A5 seems too strong?

Consider lotteries and $B$ , and a mixture $X = p A + (1 - p) B$ in between. Applying A5 twice gives:

If $u (X) \geq u (A)$ then $u (B) \geq u (A)$
If $u (X) \geq u (B)$ then $u (B) \geq u (A)$

So if $u (X) \geq u (A)$ and $u (X) \geq u (B)$ then $u (A) = u (B)$ ?

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

[-]Scott Garrabrant3y30

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.

[-]James Payor3y10

Got it, thanks!

[-]Scott Garrabrant3y30

You can also think of A5 in terms of its contrapositive: For all , if $A ≻ B$ , then for all $0 < p \leq 1$ $A ≻ p A + (1 - p) B$

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.

[-]Scott Garrabrant3y20

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 $A \sim B$ . If $A \sim B$ , and $A, B ≻ X$ , a mixture of $A$ and $B$ , then all we need to do is have any Y such that $A ≻ Y ≻ X$ , then we can get $Y^{'}$ between $A$ and $X$ by A3, and then $X$ will also be a mixture of $Y^{'}$ and $B$ , contradicting A5, since $B ≻ Y^{'}$ .

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.

[-]James Payor3y10

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 $n Δ$ is also good", which is much stronger.

[-]Scott Garrabrant3y30

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

[-]Scott Garrabrant3y20

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

[-]James Payor3y10

yep!

[-]James Payor3y10

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

Moderation Log

AI ALIGNMENT FORUM
AF

AI ALIGNMENT FORUM
AF

34

[ Question ]

Concave Utility Question

34

6 Answers sorted by
top scoring

Apr 15, 2023

Apr 24, 2023

Apr 15, 2023

Apr 15, 2023

Apr 15, 2023

Apr 15, 2023*

34

[ Question ]

Concave Utility Question

34

6 Answers sorted by top scoring

Apr 15, 2023

Apr 24, 2023

Apr 15, 2023

Apr 15, 2023

Apr 15, 2023

Apr 15, 2023*

6 Answers sorted by
top scoring