Toy model piece #1: Partial preferences revisited

post by Stuart_Armstrong · 2019-07-29T16:35:19.561Z · LW · GW · 18 comments

Contents

  The problem with the old definition
  New definition: preorder
  Circular preferences and utility functions
    The sensible case
    The general case
    Extending the sensible case
  The final version of partial preferences
None
18 comments

EDIT: This model is currently obsolete, see here [LW · GW] for the most current version.

I'm working towards a toy model that will illustrate all the steps in the research agenda [LW · GW]. 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 [LW · GW], and then transform them into utility functions.

The problem with the old definition

My previous model [LW · GW] 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 [LW · GW] 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. ↩︎

18 comments

Comments sorted by top scores.