Toy model piece #1: Partial preferences revisited

EDIT: This model is cur­rently ob­so­lete, see here for the most cur­rent ver­sion.

I’m work­ing to­wards a toy model that will illus­trate all the steps in the re­search agenda. It will start with some al­gorith­mic stand-in for the “hu­man”, and pro­ceed to cre­ate the , fol­low­ing all the steps in that re­search agenda. So I’ll be post­ing a se­ries of “toy model pieces”, that will then be ul­ti­mately com­bined in a full toy model. Along the way, I hope to get a bet­ter un­der­stand­ing of how to do the re­search agenda in prac­tice, and maybe even mod­ify that agenda based on in­sights mak­ing the toy model.

In this post, I’ll re­visit and re-for­mal­ise par­tial prefer­ences, and then trans­form them into util­ity func­tions.

The prob­lem with the old definition

My pre­vi­ous model of par­tial prefer­ences can’t cap­ture some very sim­ple men­tal mod­els, such as “the more peo­ple smile, the bet­ter the world is”.

This is be­cause the par­tial prefer­ence de­com­poses the space of wor­lds lo­cally as , fixes two val­ues and in , and only com­pares wor­lds of type and for fixed . This means that we can only com­pare wor­lds with the same value, and only two of these wor­lds can be com­pared: so we can’t say for three dis­tinct wor­lds. Thus we can’t say that three peo­ple smil­ing is bet­ter than two, which is bet­ter than one. Not be­ing able to cap­ture prefer­ences like is a ma­jor flaw.

New defi­ni­tion: preorder

So now model a par­tial prefer­ence as pre­order. A pre­order is a type of or­der­ing that is tran­si­tive (if and , then ) and re­flex­ive ( for all wor­lds ).

The pre­vi­ous type of par­tial prefer­ence can be made into a pre­order quite eas­ily: im­plies , and add for all wor­lds .

Now we can eas­ily ex­press “the more peo­ple smile, the bet­ter the world is”. Let be a world with smil­ing peo­ple in it, with rep­re­sent­ing all the other rele­vant vari­ables de­scribing the world. The is de­scribed by the pre­order:

• if and only if and .

For a gen­eral pre­order , define to mean but it not be­ing the case that .

Cir­cu­lar prefer­ences and util­ity functions

Un­for­tu­nately, un­like the pre­vi­ous par­tial prefer­ences, pre­orders can al­low for cir­cu­lar prefer­ences . In prac­tice, most sen­si­ble par­tial prefer­ences will not have cir­cu­lar prefer­ences, and will in­stead re­sem­ble : just a col­lec­tion of or­der­ings among sep­a­rate sets of wor­lds.

But, it will might be pos­si­ble to have cir­cu­lar par­tial prefer­ences, maybe of the type “in Aus­tralia, the cities gets nicer as you go clock­wise along the coast”.

So you need a way of deal­ing with cir­cu­lar prefer­ences, and with com­pli­cated sets of par­tial prefer­ences that might in­clude some cir­cu­lar prefer­ences.

We also want a way to trans­form all of these pre­orders into a full prefer­ence, given as a util­ity func­tion over all wor­lds. The re­search agenda calls for ag­gre­gat­ing similar prefer­ences be­fore mak­ing them into full prefer­ences, but we still need some way of do­ing this in the cases where we have a sin­gle par­tial prefer­ence. The rest of this sec­tion will show one way of do­ing this.

The sen­si­ble case

In the sim­plest case, we’d have a par­tial prefer­ence such as “these ten wor­lds are good, in this or­der”, and we’d map them to a util­ity func­tion with equal spaces be­tween each world. And we wouldn’t say these ten wor­lds were all bet­ter or all worse than the other wor­lds not men­tioned.

And we can do that, in the most likely and sen­si­ble case. Take and its pre­order (and ): un­der this par­tial prefer­ence, the wor­lds de­com­pose into sim­ple or­dered chains. That means that if is the set of wor­lds, then it de­com­poses as a dis­joint union (for some in­dex­ing set ). Th­ese sets are in­com­pa­rable: if and , then nei­ther nor .

More­over, each of these is to­tally or­dered by : so we can in­dex any by some nat­u­ral num­ber , as , and say that if and only if . Let be the size of minus one, and or­der the el­e­ments of it from up­wards: so the set is or­dered as .

Then here is how we con­struct a util­ity func­tion that ex­tends the par­tial or­der:

• For all , , set to .

This means that if is in­com­pa­rable with all other wor­lds (ie, is not rele­vant to the par­tial prefer­ence), the , and that all chains have util­ities , , , . So they are sym­met­ric around .

The gen­eral case

Here I’ll give a way of gen­er­al­is­ing the above pro­ce­dure to the case of any pre­order. Note that this situ­a­tion should only come up very rarely, since most pre­orders de­rived from men­tal mod­els will be more sen­si­ble. Still, for com­plete­ness, here is a pro­cess that ex­tends the sim­ple model:

First, to get rid of cir­cu­lar prefer­ences, pro­ject the set of wor­lds to , by us­ing the equiv­alence re­la­tion means and . Call this pro­jec­tion . The pre­order on de­scends via to a par­tial or­der. So we now work in , which has no cir­cu­lar prefer­ences. Then if we as­sign a util­ity to , we can ex­tend this to by set­ting .

Now work­ing in , define a link be­tween two (equiv­alence class of) wor­lds and . Write to say that , and that there does not ex­ist any world with .

Now, de­com­pose as col­lec­tion of dis­joint sets (for some in­dex­ing set ). Two wor­lds and are in the set if you can get from one to an­other fol­low­ing links; ie if there ex­ists wor­lds with and and for all , ei­ther or .

Let be the num­ber of links in . We’ll now as­sign util­ity to el­e­ments of , as a con­strained op­ti­mi­sa­tion pro­cess; in the fol­low­ing, all wor­lds are as­sumed to be in :

• min­imise , sub­ject to the con­straints that:

1. if , then .

2. ,

3. .

As long as is not con­stant on , then con­di­tions 2. and 3. just fix a scal­ing and a trans­la­tion of . Con­di­tion 1. means that con­di­tion 2. is equiv­a­lent to , since for all , which in­cludes all .

This is a con­vex op­ti­mi­sa­tion prob­lem in the val­ues of the , since is con­vex in these val­ues. Note that it is not strictly con­vex, since trans­la­tions leave it un­changed: . Nev­er­the­less, it can be seen[1] that this equa­tion is strictly con­vex on the sub­space defined by con­di­tion 3. There­fore there is a sin­gle solu­tion to the min­imi­sa­tion prob­lem above.

Ex­tend­ing the sen­si­ble case

It’s not hard to see that this ex­tends the sen­si­ble model above, which has for all (a lit­tle more work is re­quired to show that hav­ing all those val­ues equal min­imises the sum ).

The fi­nal ver­sion of par­tial preferences

Is this the fi­nal ver­sion of par­tial prefer­ences? No, cer­tainly not. But to get a bet­ter gen­er­al­i­sa­tion, we’re go­ing to have to have a look at how peo­ple ac­tu­ally model things in­side their brains and thought pro­cesses. Hence the ques­tion of how best to model par­tial mod­els will be an em­piri­cal one. But this very gen­eral defi­ni­tion will suffice for the mo­ment.

1. Very rough ar­gu­ment: choose some or­der­ing for the wor­lds in , write for , and set . Then, since is a quadratic with only quadratic terms, we can write it as its own Hes­sian: .

Now as­sume that , for . How­ever, is the sum of non-nega­tive terms, so this is only pos­si­ble if all of the are zero. This is only pos­si­ble if when­ever ; thus, since is con­nected by links, must be con­stant on . In other words, only al­lows .

Thus has only one zero eigen­vec­tor, cor­re­spond­ing to trans­la­tions. Since con­di­tion 3. pre­cludes ad­di­tional trans­la­tions, is strictly pos­i­tive definite on the sub­space it defines. Hence is strictly con­vex on this space. ↩︎

• Just not­ing that my un­der­stand­ing is that this putting a for­mal­ism on what we mean when we say “All things be­ing equal, I pre­fer more X than less X”

• Thanks for point­ing me to this up­dated ver­sion :-). This seems a re­ally neat trick for writ­ing down a util­ity func­tion that is com­pat­i­ble with the given pre­order. I thought a bit more about when/​to what ex­tent such a util­ity func­tion will be unique, in par­tic­u­lar if you are given not only the data of a pre­order, but also some in­for­ma­tion on the strengths of the prefer­ences. This ended up a bit too long for a com­ment, so I wrote a few things in out­line here:

https://​​www.less­wrong.com/​​posts/​​7ncFy84ReMFW7TDG6/​​cat­e­go­rial-prefer­ences-and-util­ity-functions

It may be quite ir­rele­vant to what you’re aiming for here, but I thought it was maybe worth writ­ing down just in case.

• I am very con­fused by the math in this post:

Why must a pre­order de­com­pose into dis­joint or­dered chains? If I have a par­tial prefer­ence and an­other par­tial prefer­ence how do those in­duce dis­joint or­dered chains where wor­lds be­tween chains are in­com­pa­rable? Per­haps you are ask­ing us to as­sume that the pre­order de­com­poses into dis­joint or­dered chains?

How do cy­cles van­ish in ? Can you work through the ex­am­ple where the par­tial prefer­ence ex­pressed by the hu­man is ?

we can ex­tend this to by set­ting U(w)=U(p(w)).

I think this is ex­tend­ing to ?

which has for all .

Should that be ?

• Thanks, cor­rected a few ty­pos.

Why must a pre­order de­com­pose into dis­joint or­dered chains?

They don’t have to; I’m say­ing that sen­si­ble par­tial prefer­ences (eg ) should do so. I then see how I’d deal with sen­si­ble pre­orders, then gen­er­al­ise to all pre­orders in the next sec­tion.

How do cy­cles van­ish in ? Can you work through the ex­am­ple where the par­tial prefer­ence ex­pressed by the hu­man is ?

Note that what you’ve writ­ten is im­pos­si­ble as means but not . A pre­order is tran­si­tive, so the best you can get is .

Then pro­ject­ing down (via ) to will pro­ject all these down to the same el­e­ment. That’s why there are no cy­cles, be­cause all cy­cles go to points.

Then we need to check some math. Define on by iff .

This is well defined (in­de­pen­dently of which and we use to rep­re­sent and ), be­cause if , then , so, by tran­si­tivity, . The same ar­gu­ment works for .

We now want to show the is a par­tial or­der on . It’s tran­si­tive, be­cause if and , then , and the tran­si­tivity in im­plies and hence .

That shows it’s a pre­order. To show par­tial or­der, we need to show there are no cy­cles. So, if and , then and , hence, by defi­ni­tion of , . So it’s a par­tial or­der.

• For cy­cles, it looks like the pro­jec­tion to is akin to tak­ing all the wor­lds that form a given cy­cle, and com­press­ing them into a sin­gle world.

In your ex­am­ple, it’s true and when . That’s the con­di­tion for equiv­alence in the pro­ject, so you have that . If you’re think­ing about the or­der­ing as a di­rected graph, you can col­lapse those wor­lds to a sin­gle point and not mess up the or­der­ing.

• Ah yes, that makes sense, thanks! I didn’t re­al­ize what was the set of equiv­alence classes of

• For the dis­joint chain part, first imag­ine all the wor­lds in the from and split them into equiv­alence classes based on equal­ity of . The prefer­ence can only com­pare two wor­lds that are in the same equiv­alence class, so each equiv­alence class will be to­tally or­dered, but no class will be com­pa­rable to any other (hence de­com­po­si­tion into dis­joint chains).

• I thought the (n, v) thing was just an ex­am­ple. If all the wor­lds are meant to be rep­re­sented via (n, v), then it seems like you are only ever al­lowed to give a par­tial prefer­ence based on what­ever fea­ture n rep­re­sents, and you can never talk about any of the other fea­tures in v. This seems bad.

(I do agree that if you only give par­tial prefer­ences on (n, v) wor­lds in the way you de­scribe, then you get a de­com­po­si­tion into dis­joint chains.)

• I do be­lieve the OP is talk­ing about par­tial pref on (n,v) form wor­lds. Yeah, this seems bad in the “How do I act when look­ing at differ­ent v?” sense, but I get the sense that it’s not sup­posed to an­swer that ques­tion. Or at least Stu­art plans to build a lot from here be­fore it will an­swer that sort of ques­tion.

• That makes the math make sense, but I re­ally ob­ject to call­ing this the “sen­si­ble” case.

• Sup­pose I ex­press a par­tial prefer­ence over “good wor­lds” and an­other one over “bad wor­lds”, for ex­am­ple “when ev­ery­one’s needs for food, wa­ter and shelter are met, then it is bet­ter for there to be more so­cial con­nec­tion” and “when I am liv­ing in ex­treme poverty, I pre­fer to be in a coun­try with a good so­cial safety net”. Th­ese talk about mu­tu­ally ex­clu­sive wor­lds, and so lead to two dis­tinct or­dered chains. Then, on av­er­age you as­sign the same util­ity to a good world and a bad world, which seems very bad. How do we avoid this is­sue?

• By adding in a third prefer­ence, which ex­plic­itely says that ex­treme poverty is worse than hav­ing all needs met.

Th­ese are just pieces of the to­tal util­ity, re­mem­ber. Even if they are full prefer­ences, they are not all our prefer­ences.

• This seems re­ally neat, but it seems quite sen­si­tive to how one defines the wor­lds un­der con­sid­er­a­tion, and whether one counts slightly differ­ent wor­lds as ac­tu­ally dis­tinct. Let me try to illus­trate this with an ex­am­ple.

Sup­pose we have a con­sist­ing of 7 wor­lds, , with prefer­ences
and no other non-triv­ial prefer­ences. Then (from the `sen­si­ble case’), I think we get the fol­low­ing util­ities:

.

Sup­pose now that I cre­ate two new copies , of the world which each differ by the po­si­tion of a sin­gle atom, so as to give me (ex­tremely weak!) prefer­ences , so all the non-triv­ial prefer­ences in the new are now sum­marised as

Then the re­sult­ing util­ities are (I think):

.

In par­tic­u­lar, be­fore adding in these ‘triv­ial copies’ we had , and now we get . Is this a prob­lem? It de­pends on the situ­a­tion, but to me it sug­gests that, if us­ing this ap­proach, one needs to be care­ful in how the wor­lds are speci­fied, and the ‘fine-grained­ness’ needs to be roughly the same ev­ery­where.

• Each par­tial prefer­ence is meant to rep­re­sent a sin­gle men­tal model in­side the hu­man, with all prefer­ences weighted the same (so there can’t be “ex­tremely weak” prefer­ences, com­pared with other prefer­ence in the same par­tial prefer­ence). Things like “in­creased in­come is bet­ter”, “more peo­ple smil­ing is bet­ter”, “be­ing em­bar­rassed on stage is the worse”.

We can imag­ine a par­tial prefer­ence with more in­ter­nal struc­ture, maybe in­ter­nal weights, but I’d sim­ply see that as two sep­a­rate par­tial prefer­ences. So we’d have the util­ities you gave to through to for one par­tial prefer­ence (ac­tu­ally, my for­mula dou­bles the num­bers you gave), and , , for the other par­tial prefer­ence—which has a very low weight by as­sump­tion. So the or­der of and is not af­fected.

EDIT: I’m pretty sure we can gen­er­al­ise my method for differ­ent weights of prefer­ences, by chang­ing the for­mula that sums the squares of util­ity differ­ence.

• (ac­tu­ally, my for­mula dou­bles the num­bers you gave)

Are you sure? Sup­pose we take with , , then , so the val­ues for should be as I gave them. And similarly for , giv­ing val­ues . Or else I have mis-un­der­stood your defi­ni­tion?

I’d sim­ply see that as two sep­a­rate par­tial preferences

Just to be clear, by “sep­a­rate par­tial prefer­ence” you mean a sep­a­rate pre­order, on a set of ob­jects which may or may not have some over­lap with the ob­jects we con­sid­ered so far? Then some­how the work is just post­poned to the point where we try to com­bine par­tial prefer­ences?

EDIT (in re­ply to your edit): I guess e.g. keep­ing con­di­tions 1,2,3 the same and in­stead min­imis­ing

where is pro­por­tion to the re­cip­ro­cal of the strength of the prefer­ence? Of course there are lots of var­i­ants on this!

• Yep, sorry, I saw −3, −2, −1, etc… and con­cluded you weren’t do­ing the 2 jumps; my bad!

Then some­how the work is just post­poned to the point where we try to com­bine par­tial prefer­ences?

Yes. But un­less we have other par­tial prefer­ences or meta-prefer­ences, then the only res­on­able way of com­bin­ing them is just to add them, af­ter weight­ing.

I like your re­cip­ro­cal weight­ing for­mula. It seems to have good prop­er­ties.