2.6 Ranking Functions

Another approach to representing uncertainty, somewhat similar in spirit to possibility measures, is given by what are called (ordinal) ranking functions. I consider a slightly simplified version here. A ranking function κ again assigns to every set a number, but this time the number is a natural number or infinity; that is, κ : 2^W → 풩^*, where 풩^* = 풩 ∪ {∞}. The numbers can be thought of as denoting degrees of surprise; that is, κ(U) is the degree of surprise the agent would feel if the actual world were in U. The higher the number, the greater the degree of surprise. 0 denotes "unsurprising", 1 denotes "somewhat surprising", 2 denotes "quite surprising", and so on; ∞ denotes "so surprising as to be impossible." For example, the uncertainty corresponding to tossing a coin with bias 1/3 can be captured by a ranking function such as κ(heads) = κ(tails) = 0 and κ(edge) = 3, where edge is the event that the coin lands on edge.

Given this intuition, it should not be surprising that ranking functions are required to satisfy the following three properties:

Rk1. κ(∅) =∞.
Rk2. κ(W) = 0.
Rk3. κ(U ∪ V) = min(κ(U), κ(V)) if U and V are disjoint.

(Again, Rk3 holds even if U and V are not disjoint; see Exercise 2.31.) Thus, with ranking functions, ∞ and 0 play the role played by 0 and 1 in probability and possibility, and min plays the role of + in probability and max in possibility.

As with probability and possibility, a ranking function is characterized by its behavior on singletons in finite spaces; κ(U) = min_u∈U κ(u). To ensure that Rk2 holds, it must be the case that min_w∈W κ(w) = 0; that is, at least one element in W must have a rank of 0. And again, if W is infinite, this is no longer necessarily true. For example, if W = 풩, a ranking function that gives rank 0 to all infinite sets and rank ∞ to all finite sets satisfies Rk1–3.

To ensure that the behavior of rank is determined by singletons even in infinite sets, Rk3 is typically strengthened in a way analogous to Poss3⁺:

Rk3⁺. For all index sets I, If the sets U_i, i ∊ I, are pairwise disjoint, then κ(∪_{i ∊ I}, U_i) = min{κ(U_i) : i ∊ I}.

In infinite domains, it may also be reasonable to allow ranks that are infinite ordinals, not just natural numbers or ∞. (The ordinal numbers go beyond the natural numbers and deal with different types of infinity.) However, I do not pursue this issue.

Ranking functions as defined here can in fact be viewed as possibility measures in a straightforward way. Given a ranking function κ, define the possibility measure Poss_κ by taking Poss_κ(U) = 1/(1 + κ(U)). (Poss^κ(U) = 0 if κ(U) =∞.) It is easy to see that Poss_κ is indeed a possibility measure (Exercise 2.39). This suggests that possibility measures can be given a degree-of-surprise interpretation similar in spirit to that given to ranking functions, except that the degrees of surprise now range over [0, 1], not the natural numbers.

Ranking functions can also be viewed as providing a way of doing order-of-magnitude probabilistic reasoning. Given a finite set W of possible worlds, choose ε so that ε is significantly smaller than 1. (I am keeping the meaning of "significantly smaller" deliberately vague for now.) Sets U such that κ(U) = k can be thought of as having probability roughly ε^k—more precisely, of having probability αε^k for some positive α that is significantly smaller than 1/ε (so that αε^k is significantly smaller than ε^k−1). With this interpretation, the assumptions that κ(W) = 0 and κ(U ∪ U′) = min(κ(U), κ(U′)) make perfect probabilistic sense.

The vagueness regarding the meaning of "significantly smaller" can be removed by using nonstandard probability measures. It can be shown that there exist what are called non-Archimedean fields, fields that contain the real numbers and also infinitesimals, where an infinitesimal is an element that is positive but smaller than any positive real number. If ε is such an infinitesimal, then αε < 1 for all positive real numbers α. (If αε were greater than 1, then ε would be greater than 1/α, contradicting the assumption that ε is less than all positive real numbers.) Since multiplication is defined in non-Archimedean fields, if ε is an infinitesimal, then so is ε^k for all k > 0. Moreover, since αε < 1for all positive real numbers α, it follows that αε^k <ε^k−1 for all real numbers α.

Define a nonstandard probability measure to be a function associating with sets an element of a non-Archimedean field in the interval [0, 1] that satisfies P1 and P2. Fix an infinitesimal ε and a nonstandard probability measure μ. Define κ(U) to be the smallest natural number k such that μ(U)>αε^k for some standard real α > 0. It can be shown that this definition of κ satisfies Rk1–3 (Exercise 2.40). However, in more practical order-of-magnitude reasoning, it may make more sense to think of ε as a very small positive real number, rather than as an infinitesimal.