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 , 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 "the more people smile, the better the world is".
This is because the partial preference decomposes the space of worlds locally as , fixes two values and in , and only compares worlds of type and for fixed . This means that we can only compare worlds with the same value, and only two of these worlds can be compared: so we can't say 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 is a major flaw.
New definition: preorder
So now model a partial preference as preorder. A preorder is a type of ordering that is transitive (if and , then ) and reflexive ( for all worlds ).
The previous type of partial preference can be made into a preorder quite easily: implies , and add for all worlds .
Now we can easily express "the more people smile, the better the world is". Let be a world with smiling people in it, with representing all the other relevant variables describing the world. The is described by the preorder:
- if and only if and .
For a general preorder , define to mean but it not being the case that .
Circular preferences and utility functions
Unfortunately, unlike the previous partial preferences, preorders can allow for circular preferences . In practice, most sensible partial preferences will not have circular preferences, and will instead resemble : 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 and its preorder (and ): under this partial preference, the worlds decompose into simple ordered chains. That means that if is the set of worlds, then it decomposes as a disjoint union (for some indexing set ). These sets are incomparable: if and , then neither nor .
Moreover, each of these is totally ordered by : so we can index any by some natural number , as , and say that if and only if . Let be the size of minus one, and order the elements of it from upwards: so the set is ordered as .
Then here is how we construct a utility function that extends the partial order:
- For all , , set to .
This means that if is incomparable with all other worlds (ie, is not relevant to the partial preference), the , and that all chains have utilities , , , . So they are symmetric around .
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 to , by using the equivalence relation means and . Call this projection . The preorder on descends via to a partial order. So we now work in , which has no circular preferences. Then if we assign a utility to , we can extend this to by setting .
Now working in , define a link between two (equivalence class of) worlds and . Write to say that , and that there does not exist any world with .
Now, decompose as collection of disjoint sets (for some indexing set ). Two worlds and are in the set if you can get from one to another following links; ie if there exists worlds with and and for all , either or .
Let be the number of links in . We'll now assign utility to elements of , as a constrained optimisation process; in the following, all worlds are assumed to be in :
- minimise , subject to the constraints that:
- if , then .
As long as is not constant on , then conditions 2. and 3. just fix a scaling and a translation of . Condition 1. means that condition 2. is equivalent to , since for all , which includes all .
This is a convex optimisation problem in the values of the , since is convex in these values. Note that it is not strictly convex, since translations leave it unchanged: . Nevertheless, it can be seen 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 for all (a little more work is required to show that having all those values equal minimises the sum ).
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.
Very rough argument: choose some ordering for the worlds in , write for , and set . Then, since is a quadratic with only quadratic terms, we can write it as its own Hessian: .
Now assume that , for . However, is the sum of non-negative terms, so this is only possible if all of the are zero. This is only possible if whenever ; thus, since is connected by links, must be constant on . In other words, only allows .
Thus has only one zero eigenvector, corresponding to translations. Since condition 3. precludes additional translations, is strictly positive definite on the subspace it defines. Hence is strictly convex on this space. ↩︎