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. ↩︎