Toy model piece #1: Partial preferences revisited

[Stuart_Armstrong]

EDIT: This model is currently obsolete, see here for the most current version.

I’m working towards a toy model that will illustrate all the steps in the research agenda. It will start with some algorithmic stand-in for the “human”, and proceed to create the $U_H$, following all the steps in that research agenda. So I’ll be posting a series of “toy model pieces”, that will then be ultimately combined in a full toy model. Along the way, I hope to get a better understanding of how to do the research agenda in practice, and maybe even modify that agenda based on insights making the toy model.

In this post, I’ll revisit and re-formalise partial preferences, and then transform them into utility functions.

The problem with the old definition

My previous model of partial preferences can’t capture some very simple mental models, such as $P=$“the more people smile, the better the world is”.

This is because the partial preference decomposes the space of worlds locally as $Y\times Z$, fixes two values $y_{-}$ and $y_{+}$ in $Y$, and only compares worlds of type $(y_{-},z)$ and $(y_{+},z)$ for fixed $z$. This means that we can only compare worlds with the same $z$ value, and only two of these worlds can be compared: so we can’t say $w_1<w_2<w_3$ for three distinct worlds. Thus we can’t say that three people smiling is better than two, which is better than one. Not being able to capture preferences like $P$ is a major flaw.

New definition: preorder

So now model a partial preference as preorder. A preorder $\le$ is a type of ordering that is transitive (if $w_1\le w_2$ and $w_2\le w_3$, then $w_1\le w_3$) and reflexive ($w\le w$ for all worlds $w$).

The previous type of partial preference can be made into a preorder quite easily: $w_1<w_2$ implies $w_1\le w_2$, and add $w\le w$ for all worlds $w$.

Now we can easily express $P=$“the more people smile, the better the world is”. Let $w(n,v)$ be a world with $n$ smiling people in it, with $v$ representing all the other relevant variables describing the world. The $P$ is described by the preorder:

• $w(n,v)\le w(n,v^{\prime })$ if and only if $v=v^{\prime }$ and $n\le m$.

For a general preorder $\le$, define $w<w^{\prime }$ to mean $w\le w^{\prime }$ but it not being the case that $w^{\prime }\le w$.

Circular preferences and utility functions

Unfortunately, unlike the previous partial preferences, preorders can allow for circular preferences $w_1\le w_2\le w_3\le w_1$. In practice, most sensible partial preferences will not have circular preferences, and will instead resemble $P$: just a collection of orderings among separate sets of worlds.

But, it will might be possible to have circular partial preferences, maybe of the type “in Australia, the cities gets nicer as you go clockwise along the coast”.

So you need a way of dealing with circular preferences, and with complicated sets of partial preferences that might include some circular preferences.

We also want a way to transform all of these preorders into a full preference, given as a utility function over all worlds. The research agenda calls for aggregating similar preferences before making them into full preferences, but we still need some way of doing this in the cases where we have a single partial preference. The rest of this section will show one way of doing this.

The sensible case

In the simplest case, we’d have a partial preference such as “these ten worlds are good, in this order”, and we’d map them to a utility function with equal spaces between each world. And we wouldn’t say these ten worlds were all better or all worse than the other worlds not mentioned.

And we can do that, in the most likely and sensible case. Take $P$ and its preorder $\le$ (and $<$): under this partial preference, the worlds decompose into simple ordered chains. That means that if $W$ is the set of worlds, then it decomposes as a disjoint union $W={\bigcup }_{i\in I}{W}_i$ (for some indexing set $I$). These sets are incomparable: if $w_i\in W_i$ and $w_j\in W_j$, then neither $w_i\le w_j$ nor $w_j\le w_i$.

Moreover, each of these $W_i$ is totally ordered by $<$: so we can index any $w_i\in W_i$ by some natural number $k$, as $w_{ik}$, and say that $w_{ik}<w_{il}$ if and only if $k<l$. Let $n_i=||W_i||-1$ be the size of $W_i$ minus one, and order the elements of it from $0$ upwards: so the set is ordered as $w_{i0}<w_{i1}<\dots <w_{i{n}_i}$.

Then here is how we construct a utility function $U$ that extends the partial order:

• For all $i\in I$, $k\in N$, set $U\left(w_{ik}\right)$ to $2k-n_i$.

This means that if $w$ is incomparable with all other worlds (ie, is not relevant to the partial preference), the $U\left(w\right)=0$, and that all chains $W_i$ have utilities $U\left(w_{i0}\right)=-n_i$, $U\left(w_{i1}\right)=-n_i+2$, $\dots$, $U\left(w_{i{n}_i}\right)=n_i$. So they are symmetric around $0$.

The general case

Here I’ll give a way of generalising the above procedure to the case of any preorder. Note that this situation should only come up very rarely, since most preorders derived from mental models will be more sensible. Still, for completeness, here is a process that extends the simple model:

First, to get rid of circular preferences, project the set of worlds $W$ to $\overline{W}$, by using the equivalence relation $w\cong w^{\prime }$ means $w\le w^{\prime }$ and $w^{\prime }\le w$. Call this projection $p$. The preorder on $W$ descends via $p$ to a partial order. So we now work in $\overline{W}$, which has no circular preferences. Then if we assign a utility $U$ to $\overline{W}$, we can extend this to $W$ by setting $U\left(w\right)=U\left(p\right(w\left)\right)$.

Now working in $\overline{W}$, define a link between two (equivalence class of) worlds $w$ and $w^{\prime }$. Write $w\leftarrow w$ to say that $w<w^{\prime }$, and that there does not exist any world $v\in \overline{W}$ with $w<v<w^{\prime }$.

Now, decompose $\overline{W}$ as collection of disjoint sets ${\bigcup }_{i\in I}{W}_i$ (for some indexing set $I$). Two worlds $w$ and $w^{\prime }$ are in the set $W_i$ if you can get from one to another following links; ie if there exists worlds $w_{ik}$ with $w=w_{i0}$ and $w^{\prime }=w_{il}$ and for all $k$, either $w_{ik}\leftarrow w_{i(k+1)}$ or $w_{i(k+1)}\leftarrow w_{ik}$.

Let $n_i$ be the number of links in $W_i$. We’ll now assign utility to elements of $W_i$, as a constrained optimisation process; in the following, all worlds are assumed to be in $W_i$:

• minimise $g\left(U\right)={\sum }_{w\leftarrow w^{\prime }}\left(U\right(w^{\prime })-U(w){)}^2$, subject to the constraints that:

1. if $w<w^{\prime }$, then $U\left(w\right)\le U\left(w^{\prime }\right)$.

2. ${\sum }_{w\leftarrow w^{\prime }}U\left(w^{\prime }\right)-U\left(w\right)=2n_i$,

3. ${\sum }_{w}U\left(w\right)=0$.

As long as $U$ is not constant on $W_i$, then conditions 2. and 3. just fix a scaling and a translation of $U$. Condition 1. means that condition 2. is equivalent to ${\sum }_{w\leftarrow w^{\prime }}|U\left(w^{\prime }\right)-U\left(w\right)|=2n_i$, since $U\left(w\right)\le U\left(w^{\prime }\right)$ for all $w<w^{\prime }$, which includes all $w\leftarrow w^{\prime }$.

This is a convex optimisation problem in the values of the $U\left(w\right)$, since $g\left(U\right)$ is convex in these values. Note that it is not strictly convex, since translations leave it unchanged: $g\left(U\right)=g(U+c)$. Nevertheless, it can be seen^[1] that this equation is strictly convex on the subspace defined by condition 3. Therefore there is a single solution to the minimisation problem above.

Extending the sensible case

It’s not hard to see that this extends the sensible model above, which has $U\left(w^{\prime }\right)-U\left(w\right)=2$ for all $w\leftarrow w^{\prime }$ (a little more work is required to show that having all those values equal minimises the sum ${\sum }_{w\leftarrow w^{\prime }}\left(U\right(w^{\prime })-U(w){)}^2$).

The final version of partial preferences

Is this the final version of partial preferences? No, certainly not. But to get a better generalisation, we’re going to have to have a look at how people actually model things inside their brains and thought processes. Hence the question of how best to model partial models will be an empirical one. But this very general definition will suffice for the moment.

---

1. ↩︎

   Very rough argument: choose some ordering for the worlds in $W_i$, write $x_i$ for $U\left(w_i\right)$, and set $\overline{x}=(x_0,\dots x_m)$. Then, since $g$ is a quadratic with only quadratic terms, we can write it as its own Hessian: $g\left(\overline{x}\right)={\overline{x}}^T\frac{H\left(g\right)}{2}\overline{x}$.

   Now assume that ${\overline{x}}^T\frac{H\left(g\right)}{2}\overline{x}=0$, for $\overline{x}=(r_0,r_1,\dots r_m)$. However, $g$ is the sum of non-negative terms, so this is only possible if all of the ${\sum }_{w\leftarrow w^{\prime }}\left(U\right(w^{\prime })-U(w){)}^2$ are zero. This is only possible if $U\left(w^{\prime }\right)=U\left(w\right)$ whenever $w\leftarrow w^{\prime }$; thus, since $W_i$ is connected by links, $U$ must be constant on $W_i$. In other words, only $\overline{x}=(r,r,\dots r)$ allows ${\overline{x}}^T\frac{H\left(g\right)}{2}\overline{x}=0$.

   Thus $H\left(g\right)$ has only one zero eigenvector, corresponding to translations. Since condition 3. precludes additional translations, $H\left(g\right)$ is strictly positive definite on the subspace it defines. Hence $g$ is strictly convex on this space.

[Hazard]

Just noting that my understanding is that this putting a formalism on what we mean when we say “All things being equal, I prefer more X than less X”

[Rohin Shah]

See also CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements (though note it doesn’t turn into a utility function, which as I understand it is a key desideratum).

[DavidHolmes]

Thanks for pointing me to this updated version :-). This seems a really neat trick for writing down a utility function that is compatible with the given preorder. I thought a bit more about when/​to what extent such a utility function will be unique, in particular if you are given not only the data of a preorder, but also some information on the strengths of the preferences. This ended up a bit too long for a comment, so I wrote a few things in outline here:

https://​​www.lesswrong.com/​​posts/​​7ncFy84ReMFW7TDG6/​​categorial-preferences-and-utility-functions

It may be quite irrelevant to what you’re aiming for here, but I thought it was maybe worth writing down just in case.

[Rohin Shah]

I am very confused by the math in this post:

Why must a preorder decompose into disjoint ordered chains? If I have a partial preference $w_1<w_3$ and another partial preference $w_2<w_3$ how do those induce disjoint ordered chains where worlds between chains are incomparable? Perhaps you are asking us to assume that the preorder decomposes into disjoint ordered chains?

How do cycles vanish in $\overline{W}$? Can you work through the example where the partial preference expressed by the human is $w_1<w_2<w_3<w_1$?

we can extend this to $\overline{W}$ by setting U(w)=U(p(w)).

I think this is extending to $W$?

which has $||U\left(w\text{'}\right)-U\left(w\right)||$ for all $w\leftarrow w\text{'}$.

Should that be $||U\left(w^{\prime }\right)-U\left(w\right)||=2$?

[Stuart_Armstrong]

Thanks, corrected a few typos.

Why must a preorder decompose into disjoint ordered chains?

They don’t have to; I’m saying that sensible partial preferences (eg $P$) should do so. I then see how I’d deal with sensible preorders, then generalise to all preorders in the next section.

How do cycles vanish in $\overline{W}$? Can you work through the example where the partial preference expressed by the human is $w_1<w_2<w_3<w_1$?

Note that what you’ve written is impossible as $w<w^{\prime }$ means $w\le w^{\prime }$ but not $w^{\prime }\le w$. A preorder is transitive, so the best you can get is $w_1\le w_2\le w_3\le w_1$.

Then projecting down (via $p$) to $\overline{W}$ will project all these $w_i$ down to the same element. That’s why there are no cycles, because all cycles go to points.

Then we need to check some math. Define $\le$ on $\overline{W}$ by $p\left(w\right)\le p\left(w^{\prime }\right)$ iff $w\le w^{\prime }$.

This is well defined (independently of which $w$ and $w^{\prime }$ we use to represent $p\left(w\right)$ and $p\left(w^{\prime }\right)$), because if $p\left(w^{\prime \prime }\right)=p\left(w\right)$, then $w^{\prime \prime }\le w$, so, by transitivity, $w^{\prime \prime }\le w^{\prime }$. The same argument works for $w^{\prime }$.

We now want to show the $\le$ is a partial order on $\overline{W}$. It’s transitive, because if $p\left(w\right)\le p\left(w^{\prime }\right)$ and $p\left(w^{\prime }\right)\le p\left(w^{\prime \prime }\right)$, then $w\le w^{\prime }\le w^{\prime \prime }$, and the transitivity in $W$ implies $w\le w^{\prime \prime }$ and hence $p\left(w\right)\le p\left(w^{\prime \prime }\right)$.

That shows it’s a preorder. To show partial order, we need to show there are no cycles. So, if $p\left(w\right)\le p\left(w^{\prime }\right)$ and $p\left(w^{\prime }\right)\le p\left(w\right)$, then $w\le w^{\prime }$ and $w^{\prime }\le w$, hence, by definition of $p$, $p\left(w\right)=p\left(w^{\prime }\right)$. So it’s a partial order.

[Rohin Shah]

Thanks!

[Hazard]

For cycles, it looks like the projection to $\overline{W}$ is akin to taking all the worlds that form a given cycle, and compressing them into a single world.

In your example, it’s true $w_i<w_j$ and $w_j<w_i$ when $i\ne j$. That’s the condition for equivalence in the project, so you have that $w_1=w_2=w_3$. If you’re thinking about the ordering as a directed graph, you can collapse those worlds to a single point and not mess up the ordering.

[Rohin Shah]

Ah yes, that makes sense, thanks! I didn’t realize what $\overline{W}$ was the set of equivalence classes of $W$

[Hazard]

For the disjoint chain part, first imagine all the worlds in the from $(n,v)$ and split them into equivalence classes based on equality of $v$. The preference $P$ can only compare two worlds that are in the same equivalence class, so each equivalence class will be totally ordered, but no class will be comparable to any other (hence decomposition into disjoint chains).

[Rohin Shah]

I thought the (n, v) thing was just an example. If all the worlds are meant to be represented via (n, v), then it seems like you are only ever allowed to give a partial preference based on whatever feature n represents, and you can never talk about any of the other features in v. This seems bad.

(I do agree that if you only give partial preferences on (n, v) worlds in the way you describe, then you get a decomposition into disjoint chains.)

[Hazard]

I do believe the OP is talking about partial pref on (n,v) form worlds. Yeah, this seems bad in the “How do I act when looking at different v?” sense, but I get the sense that it’s not supposed to answer that question. Or at least Stuart plans to build a lot from here before it will answer that sort of question.

[Rohin Shah]

That makes the math make sense, but I really object to calling this the “sensible” case.

[Rohin Shah]

Suppose I express a partial preference over “good worlds” and another one over “bad worlds”, for example “when everyone’s needs for food, water and shelter are met, then it is better for there to be more social connection” and “when I am living in extreme poverty, I prefer to be in a country with a good social safety net”. These talk about mutually exclusive worlds, and so lead to two distinct ordered chains. Then, on average you assign the same utility to a good world and a bad world, which seems very bad. How do we avoid this issue?

[Stuart_Armstrong]

By adding in a third preference, which explicitely says that extreme poverty is worse than having all needs met.

These are just pieces of the total utility, remember. Even if they are full preferences, they are not all our preferences.

[DavidHolmes]

This seems really neat, but it seems quite sensitive to how one defines the worlds under consideration, and whether one counts slightly different worlds as actually distinct. Let me try to illustrate this with an example.

Suppose we have a $W$ consisting of 7 worlds, $W=\{A,B,C,D,X,Y,W\}$, with preferences
$$A<B<C<D,X<Y<Z$$ and no other non-trivial preferences. Then (from the `sensible case’), I think we get the following utilities:
$A\mapsto -3$
$X\mapsto -2$
$B\mapsto -1$
$Y\mapsto 0$
$C\mapsto 1$
$Z\mapsto 2$
$D\mapsto 3$.

Suppose now that I create two new copies $X^{\prime }$, $X^{\prime \prime }$ of the world $X$ which each differ by the position of a single atom, so as to give me (extremely weak!) preferences $X^{\prime \prime }<X^{\prime }<X$, so all the non-trivial preferences in the new $W$ are now summarised as $$A<B<C<D,X^{\prime \prime }<X^{\prime }<X<Y<Z.$$

Then the resulting utilities are (I think):
$X^{\prime \prime }\mapsto -4$
$A\mapsto -3$
$X^{\prime }\mapsto -2$
$B\mapsto -1$
$X\mapsto 0$
$C\mapsto 1$
$Y\mapsto 2$
$D\mapsto 3$
$Z\mapsto 4$.

In particular, before adding in these ‘trivial copies’ we had $U\left(Z\right)<U\left(D\right)$, and now we get $U\left(D\right)<U\left(Z\right)$. Is this a problem? It depends on the situation, but to me it suggests that, if using this approach, one needs to be careful in how the worlds are specified, and the ‘fine-grainedness’ needs to be roughly the same everywhere.

[Stuart_Armstrong]

Each partial preference is meant to represent a single mental model inside the human, with all preferences weighted the same (so there can’t be “extremely weak” preferences, compared with other preference in the same partial preference). Things like “increased income is better”, “more people smiling is better”, “being embarrassed on stage is the worse”.

We can imagine a partial preference with more internal structure, maybe internal weights, but I’d simply see that as two separate partial preferences. So we’d have the utilities you gave to $A$ through to $Z$ for one partial preference (actually, my formula doubles the numbers you gave), and $X^{\prime \prime }\to -2$, $X^{\prime }\to 0$, $X\to 2$ for the other partial preference—which has a very low weight by assumption. So the order of $Z$ and $D$ is not affected.

EDIT: I’m pretty sure we can generalise my method for different weights of preferences, by changing the formula that sums the squares of utility difference.

[DavidHolmes]

(actually, my formula doubles the numbers you gave)

Are you sure? Suppose we take $W=W_1\bigsqcup W_2$ with $W_1=\{A,B,C,D\}$, $W_2=\{X,Y,Z\}$, then $n_1=3$, so the values for $W_1$ should be $-3,-1,1,3$ as I gave them. And similarly for $W_2$, giving values $-2,0,2$. Or else I have mis-understood your definition?

I’d simply see that as two separate partial preferences

Just to be clear, by “separate partial preference” you mean a separate preorder, on a set of objects which may or may not have some overlap with the objects we considered so far? Then somehow the work is just postponed to the point where we try to combine partial preferences?

EDIT (in reply to your edit): I guess e.g. keeping conditions 1,2,3 the same and instead minimising
$g\left(G\right)={\sum }_{w\leftarrow w^{\prime }}{\lambda }_{w\leftarrow w^{\prime }}\left(U\right(w^{\prime })-U(w){)}^2,$
where ${\lambda }_{w\leftarrow w^{\prime }}\in R_{>0}$ is proportion to the reciprocal of the strength of the preference? Of course there are lots of variants on this!

[Stuart_Armstrong]

Yep, sorry, I saw −3, −2, −1, etc… and concluded you weren’t doing the 2 jumps; my bad!

Then somehow the work is just postponed to the point where we try to combine partial preferences?

Yes. But unless we have other partial preferences or meta-preferences, then the only resonable way of combining them is just to add them, after weighting.

I like your reciprocal weighting formula. It seems to have good properties.