This post is motivated by a recent post of Stuart Armstrong on going from preferences to a utility function. It was originally planned as a comment, but seems to have developed a bit of a life of its own. The ideas here came up in a discussion with Owen Biesel; all mistakes in this exposition are mine. I’m not very good with the typesetting engine here, so apologies for latex and other problems.
The basic ideas is as follows. Suppose we have a set Sof objects, and we are given some information on which objects are preferred to which other objects. Then we are interested in whether and in how many ways this data can be captured by a utility function. Our key innovation is that we assume not only the direction of preferences is given, but also some information on the strength of the preferences, in a manner which we will make precise below (weak preferences).
Basic on orders vs utility functions
We refer to the Order Theory page on Wikipedia for the definitions of reflexive, anti-symmetric, transitive and connexive binary relations. If S is a set and U:S→R is a function (`utility’), this induces a reflexive, transitive and connected binary relation (not anti-symmetric in general, unless U is injective).
Conversely, any reflexive, transitive, antisymmetric and connexive binary relation (a.k.a. total order) on a countable set S, this is induced by a utility function taking values in the rational numbers (link to proof); there is a more general discussion here.
Strength of preferences
In what follows, we fix a totally ordered abelian group G. To express a preference between to objects s1, s2 of our set S, one should give an element of G which expresses how strongly s1 is preferred to s2. The most natural example is to take G=Z, then:
Saying s1 is preferred to s2 with strength 1 means we slightly prefer s1 to s2;
Saying s1 is preferred to s2 with strength 0 means have no preference between s1 and s2;
Saying s1 is preferred to s2 with strength 2 means we prefer s1 to s2 more strongly;
Saying s1 is preferred to s2 with strength −1 means we slightly prefer s2 to s1.
Expressions of preference
We consider three ways of describing preferences among objects in a set S:
1. Weak Preference
Definition. A weak preference among elements of S consists of a collection of triples (s1,s2,g) with si∈S and g∈G.
A triple (s1,s2,g) is interpreted as meaning that s1 is preferred to s2 with strength g. This is the kind of data one might be provided with in practise; for example, someone tells you that they slightly prefer cats to dogs, but strongly prefers dogs to snakes (assigning numbers/elements of G to the strengths of the preferences).
2. Categorical preference
Definition. To give a categorical preference for elements ofS is to give a category with objects S, together with an enrichment over G.
This definition may seem a bit cryptic, but is close to a standard way of thinking of an order as an enrichment. For every two objects s1,s2∈S we assign an element of G (which we think of as telling us the strength of the preference for s1 over s2), subject to a bunch of compatibility conditions (for example it will imply that the preference for s over s is given by the unit of G). More details and expansion can be found in Lawvere’s Taking Categories Seriously.
3. Utility function
This is just a function U:S→R, and is interpreted in the usual way.
Goal
In practise, information is likely to be supplied in the form of a weak preference. Ultimately one wants a utility function to feed to some optimisation procedure. We will describe how to pass naturally from a weak to a categorical preference, and then see (under some hypotheses) that a categorial preferences induces an essentially-unique utility function.
We suppose throughout that S and G are fixed, with S finite for simplicity.
Weak preferences to categorial preferences
First, given a categorical preference, choosing a subset of arrows yields a weak preference. On the other hand, given a weak preference, we are interested in
Q1. whether this weak preference can arise from a categorical preference, and
Q2. if so, then from how many distinct categorical preferences can this weak preference arise.
Suppose we are given a weak preference W. First, for every triple (s1,s2,g), we adjoin to W the triple (s2,s1,−g); call the resulting weak prefernce W′. A cycle in W’ is a finite ordered sequence of triples ((s1,s2,g1),(s2,s3,g2),⋯,(sn,s1,gn)) , and such a cycle is closed if ∑ni=1gi=0G.
Claim 1: The weak preference W′can be extended to a categorical preference if and only if every cycle is closed.
Sketch of proof. Suppose we are given s1 and s2, and want to assign an element of G.If there is no path from s1 to s2 we can assign any element we want (we will use this observation later). If there is a path, then the group law in G determines a value of the preference of s1 over s2. The only way a problem might arise is if there are two (or more) paths from s1 to s2, but then the cycles are closed condition means that these paths will induce the same preference for s1 over s2. QED
We move on the the uniqueness question. Assume that W′ satisfies the `cycles are closed’ condition, and write π0(W′) for the set of connected components of W′.
Claim 2. The set of categorical preferences restricting to W′ is naturally in bijection with G#π0(W′)−1.
In particular, if W′ is connected then there is exactly one way to associate a categorical preference.
Sketch of proof. In the proof of claim 1, the only choice we made was when there was no path from s1 to s2. In that case we chose an element of G. QED
From categorical preferences to utility functions
Suppose we are given a categorical preference on S, i.e. the structure of a category enriched over G with object set S . Analogously to the above, we are interested in whether and in how many ways this can be induced by a utility function.
From now on, we assume that G is Archimedean , equivalently that it is isomorphic (as an ordered group) to a subgroup of R. This isomorphism is then necessarily unique up to scaling (Holder’s theorem).
Suppose first that we have a utility function U:S→R. Let G⊂R be a subgroup containing U(s1)−U(s2) for every s1,s2∈S. Then by assigning to the pair (s1,s2) the element U(s1)−U(s2)∈G we give S a categorical preference structure, with enrichment over G.
Again, we are interested in two questions:
Q1. given a categorical preference on S, does it arise from some utility function in the above fashion?
Q2. If the answer to Q1 is `yes’, then from` how many` utility functions can out categorical preference arise?
The answer to Q1 is always yes. First choose an embedding of G in R as a totally ordered group. Then choose some element s0∈S, and define U(s0)=0.The values of U on the other elements of S are then uniquely determined by the enriched category structure.
Q2 is almost as easy. The embedding of G in R is unique up to scaling, and the choice of U(s0) is just a translation. Hence the utility function U is unique up to translation and scaling.
Conclusion
In practise, we might be given the data of a weak preference. We have seen an easy way to check whether it can be extended to a categorical preference, and a simple description of all the resulting possible categorical preferences. A categorical preference always comes from a utility function, in a way which is unique up to translation and scaling.
In actual practise, it is not unlikely that the weak preference data will not come from a categorical preference (and thus not from a utility function). Then we should probably look for the `most reasonable’ associated categorical preference, how to do this is not so clear to me yet.
I find the fact that utility functions are only unique up to translation and scaling a bit awkward; maybe this notion of categorical preference captures the important data in a more canonical fashion?!
Categorial preferences and utility functions
This post is motivated by a recent post of Stuart Armstrong on going from preferences to a utility function. It was originally planned as a comment, but seems to have developed a bit of a life of its own. The ideas here came up in a discussion with Owen Biesel; all mistakes in this exposition are mine. I’m not very good with the typesetting engine here, so apologies for latex and other problems.
The basic ideas is as follows. Suppose we have a set Sof objects, and we are given some information on which objects are preferred to which other objects. Then we are interested in whether and in how many ways this data can be captured by a utility function. Our key innovation is that we assume not only the direction of preferences is given, but also some information on the strength of the preferences, in a manner which we will make precise below (weak preferences).
Basic on orders vs utility functions
We refer to the Order Theory page on Wikipedia for the definitions of reflexive, anti-symmetric, transitive and connexive binary relations. If S is a set and U:S→R is a function (`utility’), this induces a reflexive, transitive and connected binary relation (not anti-symmetric in general, unless U is injective).
Conversely, any reflexive, transitive, antisymmetric and connexive binary relation (a.k.a. total order) on a countable set S, this is induced by a utility function taking values in the rational numbers (link to proof); there is a more general discussion here.
Strength of preferences
In what follows, we fix a totally ordered abelian group G. To express a preference between to objects s1, s2 of our set S, one should give an element of G which expresses how strongly s1 is preferred to s2. The most natural example is to take G=Z, then:
Saying s1 is preferred to s2 with strength 1 means we slightly prefer s1 to s2;
Saying s1 is preferred to s2 with strength 0 means have no preference between s1 and s2;
Saying s1 is preferred to s2 with strength 2 means we prefer s1 to s2 more strongly;
Saying s1 is preferred to s2 with strength −1 means we slightly prefer s2 to s1.
Expressions of preference
We consider three ways of describing preferences among objects in a set S:
1. Weak Preference
Definition. A weak preference among elements of S consists of a collection of triples (s1,s2,g) with si∈S and g∈G.
A triple (s1,s2,g) is interpreted as meaning that s1 is preferred to s2 with strength g. This is the kind of data one might be provided with in practise; for example, someone tells you that they slightly prefer cats to dogs, but strongly prefers dogs to snakes (assigning numbers/elements of G to the strengths of the preferences).
2. Categorical preference
Definition. To give a categorical preference for elements of S is to give a category with objects S, together with an enrichment over G.
This definition may seem a bit cryptic, but is close to a standard way of thinking of an order as an enrichment. For every two objects s1,s2∈S we assign an element of G (which we think of as telling us the strength of the preference for s1 over s2), subject to a bunch of compatibility conditions (for example it will imply that the preference for s over s is given by the unit of G). More details and expansion can be found in Lawvere’s Taking Categories Seriously.
3. Utility function
This is just a function U:S→R, and is interpreted in the usual way.
Goal
In practise, information is likely to be supplied in the form of a weak preference. Ultimately one wants a utility function to feed to some optimisation procedure. We will describe how to pass naturally from a weak to a categorical preference, and then see (under some hypotheses) that a categorial preferences induces an essentially-unique utility function.
We suppose throughout that S and G are fixed, with S finite for simplicity.
Weak preferences to categorial preferences
First, given a categorical preference, choosing a subset of arrows yields a weak preference. On the other hand, given a weak preference, we are interested in
Q1. whether this weak preference can arise from a categorical preference, and
Q2. if so, then from how many distinct categorical preferences can this weak preference arise.
Suppose we are given a weak preference W. First, for every triple (s1,s2,g), we adjoin to W the triple (s2,s1,−g); call the resulting weak prefernce W′. A cycle in W’ is a finite ordered sequence of triples ((s1,s2,g1),(s2,s3,g2),⋯,(sn,s1,gn)) , and such a cycle is closed if ∑ni=1gi=0G.
Claim 1: The weak preference W′can be extended to a categorical preference if and only if every cycle is closed.
Sketch of proof. Suppose we are given s1 and s2, and want to assign an element of G.If there is no path from s1 to s2 we can assign any element we want (we will use this observation later). If there is a path, then the group law in G determines a value of the preference of s1 over s2. The only way a problem might arise is if there are two (or more) paths from s1 to s2, but then the cycles are closed condition means that these paths will induce the same preference for s1 over s2. QED
We move on the the uniqueness question. Assume that W′ satisfies the `cycles are closed’ condition, and write π0(W′) for the set of connected components of W′.
Claim 2. The set of categorical preferences restricting to W′ is naturally in bijection with G#π0(W′)−1.
In particular, if W′ is connected then there is exactly one way to associate a categorical preference.
Sketch of proof. In the proof of claim 1, the only choice we made was when there was no path from s1 to s2. In that case we chose an element of G. QED
From categorical preferences to utility functions
Suppose we are given a categorical preference on S, i.e. the structure of a category enriched over G with object set S . Analogously to the above, we are interested in whether and in how many ways this can be induced by a utility function.
From now on, we assume that G is Archimedean , equivalently that it is isomorphic (as an ordered group) to a subgroup of R. This isomorphism is then necessarily unique up to scaling (Holder’s theorem).
Suppose first that we have a utility function U:S→R. Let G⊂R be a subgroup containing U(s1)−U(s2) for every s1,s2∈S. Then by assigning to the pair (s1,s2) the element U(s1)−U(s2)∈G we give S a categorical preference structure, with enrichment over G.
Again, we are interested in two questions:
Q1. given a categorical preference on S, does it arise from some utility function in the above fashion?
Q2. If the answer to Q1 is `yes’, then from` how many` utility functions can out categorical preference arise?
The answer to Q1 is always yes. First choose an embedding of G in R as a totally ordered group. Then choose some element s0∈S, and define U(s0)=0.The values of U on the other elements of S are then uniquely determined by the enriched category structure.
Q2 is almost as easy. The embedding of G in R is unique up to scaling, and the choice of U(s0) is just a translation. Hence the utility function U is unique up to translation and scaling.
Conclusion
In practise, we might be given the data of a weak preference. We have seen an easy way to check whether it can be extended to a categorical preference, and a simple description of all the resulting possible categorical preferences. A categorical preference always comes from a utility function, in a way which is unique up to translation and scaling.
In actual practise, it is not unlikely that the weak preference data will not come from a categorical preference (and thus not from a utility function). Then we should probably look for the `most reasonable’ associated categorical preference, how to do this is not so clear to me yet.
I find the fact that utility functions are only unique up to translation and scaling a bit awkward; maybe this notion of categorical preference captures the important data in a more canonical fashion?!