key: cord-0044867-ge3a1dph
authors: Erreygers, Alexander; Miranda, Enrique
title: A Study of the Set of Probability Measures Compatible with Comparative Judgements
date: 2020-05-15
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50143-3_13
sha: ed8ca261ed3b7ee46603f6791764ed8ed46bb8cb
doc_id: 44867
cord_uid: ge3a1dph

We consider a set of comparative probability judgements over a finite possibility space and study the structure of the set of probability measures that are compatible with them. We relate the existence of some compatible probability measure to Walley’s behavioural theory of imprecise probabilities, and introduce a graphical representation that allows us to bound, and in some cases determine, the extreme points of the set of compatible measures. In doing this, we generalise some earlier work by Miranda and Destercke on elementary comparisons.

The elicitation of probability measures can be cumbersome in situations of imprecise or ambiguous information. To deal with this problem, a number of approaches have been put forward in the literature: we may work for instance with sets of probability measures, or credal sets; consider lower and/or upper bounds of the 'true' probability measure, representing the information in terms of non-additive measures; or model the information in terms of its behavioural implications. These different models are often referred to with the common term imprecise probabilities [1] .

On the other hand, when the available information comes from expert judgements it may be easier to model it in terms of comparative assessments of the form 'event A is at least as probable as event B.' This leads to comparative probabilities, that were studied first by de Finetti [5] and later by other authors such as Koopman [9] , Good [7] or Savage [15] . For a recent thorough overview, as well as an extensive philosophical justification and a summary of the most important results, we refer to [8] . In this paper, we consider a collection of comparative probability judgements over a finite possibility space and study the structure of the set of compatible probability measures. Specifically, we shall investigate in which cases this set is non-empty, the number of its extreme points and their features, and the properties of its associated lower probability. While most earlier work on comparative probabilities has mainly focused on the complete case-that is, the case where any two events are compared-ours is not the first study of the incomplete one; in this respect, the most influential works for this paper are those of Walley [17, Section 4.5] and Miranda and Destercke [11] . Our present contribution has the same goals as that of Miranda and Destercke, but our setting is more general: where they exclusively focused on the specific case of comparisons between elementary events, we generalise some of their results to the case of comparisons between arbitrary events.

The paper is organised as follows. We start with a formal introduction of comparative assessments in Sect. 2, and subsequently discuss the compatibility problem and show that it can be easily tackled using Walley's theory of lower previsions. From Sect. 3 on, we study the set of extreme points of the associated credal set. To that end, we introduce a graphical representation in Sect. 4; this representation allows us to determine the number of extreme points in a number of special cases in Sect. 5, where we also argue that this approach cannot be extended to the general case. We conclude in Sect. 6 with some additional comments and remarks. Due to space constraints, proofs have been omitted.

Consider a finite possibility space X with cardinality n, and a (finite) number m of comparative judgements of the form 'event A is at least as likely as event B.' For ease of notation, we will represent the i-th judgement as a pair (A i , B i ) of events-that is, subsets of the possibility space X . Finally, we collect all m judgements in the comparative assessment

Equivalently, the comparative judgements can be represented in terms of a (possibly partial) binary relation on 2 X , the power set of the possibility space X , with A B being equivalent to (A, B) ∈ C . Miranda and Destercke [11] exclusively dealt with comparative assessments that consist of comparative judgements that concern singletons, or equivalently, are a subset of {({x}, {y}): x, y ∈ X }. We follow them in calling such comparative assessments elementary.

Throughout this contribution we will use a running example to illustrate much of the introduced concepts. Let Σ X denote the set of all probability mass functions on X . We follow the authors of [8, 11, 13, 17] in considering the set

of all probability mass functions that are compatible with the comparative judgements. Following Levi [10] , we call M C the comparative credal set.

Given a set C of comparative judgements, we should first of all determine whether or not there is at least one compatible probability measure-that is, if the comparative credal set M C is non-empty. In the case of elementary judgements [11] , this is trivial because the uniform probability distribution is compatible with any elementary comparative assessment. Unfortunately, when more elaborate judgements are allowed this is no longer the case, as is demonstrated by the following example. It follows immediately from these judgements that any compatible probability mass function p should satisfy p(1) ≥ 1 /2, p(2) ≥ 1 /2 and p(3) ≥ 1 /2. However, this is clearly impossible, whence M C = ∅.

The existence of a compatible probability measure was characterized in [16, Theorem 4.1] in the case of complete comparative assessments and in [14, Proposition 4] and [13, Section 2] in the case of partial comparative assessments; see also [17, Section 4.5.2] . In this section, we use Walley's result to establish a connection with the theory of sets of desirable gambles, from which we shall derive a number of additional results. We refer to [17] for a detailed account of the theory.

A gamble f is a real-valued map on our finite possibility space X . The set of all gambles on X is denoted by L, and dominance between gambles is understood pointwise. Within L we may consider the subset L + := {f ∈ L : f ≥ 0, f = 0} of non-negative gambles, that in particular includes the indicator I A of some event A ⊆ X , taking value 1 on A and 0 elsewhere.

It is often convenient to think of a gamble f as an uncertain reward expressed in units of some linear utility scale: in case the outcome of our experiment is x, our subject receives the-possibly negative-pay-off f (x). With this interpretation, our subject can specify a set of almost desirable gambles K, being some set of gambles-or uncertain rewards-that she considers acceptable. Such a set K of almost desirable gambles can be extended to include gambles that are implied by rational behaviour; the least-committal of these extensions is the natural extension of K, which is defined as D K := posi(K ∪ L + ), where we consider the topological closure under the supremum norm and the posi operator is defined for any set of gambles K ⊆ L as

with N the set of natural numbers-that is, not including zero. We say that a set of almost desirable gambles K avoids sure loss if and only if max f ≥ 0 for all f ∈ D K , and that it is coherent when K = D K . It turns out that D K is coherent if and only if K avoids sure loss, and that K avoids sure loss if and only if there exists a probability mass function p such that x∈X f (x)p(x) ≥ 0 for every f ∈ K. As a consequence, the compatibility of C is equivalent to verifying that

avoids sure loss, which immediately leads to the following proposition-see also [14, Proposition 4] , [13, Section 2] or [17, Lemma 3.3.2].

Any set of gambles K ⊆ L determines a lower prevision P K on L defined as

and a conjugate upper prevision P K defined as P K (f ) := −P K (−f ) for all f ∈ L. The lower prevision P K and its conjugate upper prevision P K are coherent if and only if K is coherent. Throughout this contribution, we let P C and P C denote the lower and upper previsions determined by D K C . We can use P C to verify whether or not a comparative judgement is saturated and/or redundant:

This means that we should first analyse if each constraint (A i , B i ) can be expressed as a positive linear combination of the other constraints in C ; if this is the case, we can remove (A i , B i ) from our set of assessments. Once we have removed all these redundancies, any constraint that cannot be expressed as a linear combination of the other constraints together with trivial assessments of the type (A, ∅) with ∅ = A ⊆ X will be saturated by some p ∈ M C when the latter set is non-empty.

It follows immediately from the properties of probability mass functions that the comparative credal set M C defined in Eq. (1) is a convex polytope as it is the intersection of n + m + 1 half spaces. It is well-known that if a convex polytope is non-empty, it is completely defined by its extreme points. A bound on the number of extreme points follows from McMullen's theorem [4] :

It is also possible to establish an upper bound on the number of extreme points that is independent on the number of comparative judgements; its proof is a relatively straightforward modification of the proofs of [3, Theorem 4.4] or [18, Theorem 5.13 ].

To give a sense of the absolute and relative performance of these bounds, we reconsider our running example.

Running Example. One can easily verify that the extreme points of the credal set M C are Our upper bound on the number of extreme points depends on the cardinality of the space n and the number m of comparative assessments; thus, the bound can be made tighter if we remove constraints that are redundant because they are implied by other constraints and the monotonicity and additivity properties of probability measures. For instance, we may assume without loss of generality that

This allows us to bound the cardinality of C :

Similarly, we may assume without loss of generality that any (A, B) ∈ C cannot be made redundant in the following senses:

(transitivity)

Nevertheless, it is more fruitful to detect redundant constraints using the theory of coherent lower previsions, as we did in Proposition 2. In this manner, given an initial (finite) set C of comparative assessments, we may proceed iteratively and remove all the redundant constraints, and then use Eq. (3) to bound the number of extreme points of the comparative credal set M C .

Essential for the results established in [11] is the representation of the elementary comparative assessments as a digraph. In the non-elementary case, such a graphical representation will also be helpful. Throughout this contribution we use the graph theoretic terminology as defined in [6] ; we do allow ourselves one difference, however: we prefer to use nodes instead of vertices.

Miranda and Destercke [11] proposed a straightforward but powerful representation of the elementary comparative assessment C as a digraph: the atoms of the possibility space correspond to the nodes, and a directed edge is added from x to y for every ({x}, {y}) ∈ C . The extreme points of the credal set are then obtained through the top subnetworks generated by certain sets of nodes [11, Theorem 1]. Because we do not limit ourselves to elementary comparative judgements, we cannot simply take over their construction. One straightforward generalisation of the aforementioned construction is to add a directed edge from x to y if there is a comparative judgement (A, B) ∈ C with x ∈ A and y ∈ B. However, this approach is not terribly useful because there is loss of information: clearly, the digraph alone does not contain sufficient information to reconstruct the comparative judgements it represents. To overcome this loss of information and to end up with one-to-one correspondence, we borrow a trick from Miranda and Zaffalon [12] and add dummy nodes to our graph.

We represent the assessment C as a digraph G as follows. First, we add one node for every atom x in the possibility space X . Next, for every comparison (A i , B i ) in the assessment C , we add an auxiliary node ξ i , and we add a directed edge from every atom x in A i to this auxiliary node ξ i and a directed edge from the auxiliary node ξ i to every atom y in B i . Formally, the set of nodes is N := X ∪ {ξ 1 , . . . , ξ m } and the set of directed edges is

Running Example. The corresponding digraph G is depicted in Fig. 1.   Fig. 1 . The digraph G of the running example Fix some node ν in the digraph G. Following [11] , we use H(ν) to denote the set that consists of the node ν itself and all of its predecessors, being those nodes ν such that there is a directed path from ν to ν. Following [2, 11] , for any subset N of the set of nodes N , we let H(N ) := ∪ ν∈N H(ν) be the so-called top subnetwork generated by N . We will exclusively be concerned with the restriction of these top subnetworks to non-auxiliary nodes; therefore, we define H ( 

The following results are straightforward observations that follow almost immediately from our graphical representation G of the comparative assessment C . The first lemma gives a useful sufficient condition for the existence of a compatible probability measure. Lemma 1. If the digraph G has a node with zero indegree , then M C = ∅.

To facilitate the statement of the following and future results, we introduce some additional notation. For any non-empty event A ⊆ X , we denote the uniform distribution over A as p A . In the particular case that the event A is the singleton {x}, we also speak of the degenerate distribution on x. The second lemma links atoms without predecessors with extreme points that are degenerate distributions. Running Example. Observe that the node 1 is the only node with zero indegree. Then, Lemmas 1 and 2 imply that (i) the comparative credal set M C is nonempty; and (ii) the degenerate distribution on 1 is an extreme point because

Our next result uses the well-known fact-see for instance [ [11, Proposition 2] that the extreme points of the comparative credal set can be obtained by determining the extreme points of the (elementary assessments induced by the) connected components separately. Our next result generalises this to general comparative assessments. G 1 , . . . , G k . For every connected component G i , we denote its set of non-auxiliary nodes by X i and we let C i be the comparative assessment with possibility space X i that is in one-to-one correspondence with G i . Then

where extend(p i ) is the cylindrical extension of p i to X that is obtained by assigning zero mass to X \ X i .

Because of this result, without loss of generality we can restrict our attention in the remainder to digraphs G that are connected. It is also immediate to establish the following result.

In the language of Sect. 2, this means that P C (I Ai\Ai+1 ) = 0 if A i+1 ⊂ A i , so any atom in A i \ A i+1 will always have zero mass. Hence, we can simplify the digraph G by removing nodes that are sure to have zero mass: (i) any atom in A i \ A i+1 with A i+1 ⊂ A i ; and (ii) if these removals result in the formation of one or more extra disconnected components, the entirety of those disconnected components that used to be connected exclusively by incoming directed edges from (the direct successors of) the previously removed atoms.

Remark 1. This graphical representation also allows us to simplify somewhat the study of the compatibility problem and the extreme points in the following manner. We define a relationship R between the elements of X as xRy if and only if there is a directed cycle going through x and y. It is easy to see that R is an equivalence relationship. Hence, we may consider the different equivalence classes and the directed edges between them that can be derived from G, leading to a new acyclic digraph G on the equivalence classes. Let G i denote the subdigraph associated with the i-th equivalence class and C i the corresponding subset of comparative judgements. Observe that -the set M C is non-empty if and only if at least one of the sets M C i is nonempty, where the associated graph G i has no predecessors in G ; -if a subgraph G i is such that M C i is empty, then for each of its successors G j any element of M C gives zero probability to the nodes in G j .

This also allows us to remove redundant parts of the graph.

If a digraph is free of directed cycles, then we call it acyclic [6, Section 4.2]. Any acyclic digraph has at least one node with zero indegree [6, Lemma 4.1]. Therefore, the following result is an immediate corollary of Lemma 1; alternatively, it is also a corollary of Propositions 8 and 10.

On the other hand, a digraph is acyclic if and only if it has a topological ordering, sometimes also called an acyclic numbering [6, Proposition 4.1] . This necessary and sufficient condition allows us to establish the following result.

is an ordering x 1 , . . . , x n of the atoms of the possibility space X such that

Running Example. It is easy to verify using Fig. 1 that the graph G is acyclic, and we have seen that the comparative credal set is non-empty. Furthermore, the ordering of Proposition 7 is clearly 1, 2, 3, 4.

Our graphical representation also has implications when we consider a strict preference relation, where A B is to be interpreted as 'the event A is more likely than event B.' For a given set C of comparative judgements, we now consider the set

of probability mass functions that are compatible with the strict comparative judgements. Since the set M C is a polytope, it follows that it is the closure of M > C , provided that this latter set is non-empty. In our case, we can prove something stronger: that M > C is the topological interior of M C .

In our next result, we establish a necessary and sufficient condition for M > C to be non-empty.

Let C be a finite set of strict comparative assessments. Then the following are equivalent:

In the case of elementary comparisons, it was established in [11, Lemma 1] that M > C is non-empty if and only if the digraph C is acyclic. In the general case, the lack of directed cycles turns out to be sufficient as well. On the other hand, a necessary condition for M > C to be non-empty is that we cannot derive from C a cycle of the type A 1 A 2 · · · A k A 1 . This is equivalent to the graph being acyclic in the case of elementary probability comparisons, and this is what leads to [11, Lemma 1] ; however, the two conditions are not equivalent in the general case.

As we have often mentioned before, Miranda and Destercke [11] show that in the case of elementary comparative assessments, the extreme points of the comparative credal set can be determined using the graphical representation. More specifically, they show that: E1. all the extreme points of M C correspond to uniform probability distributions [11, Lemma 2] ; E2. if C ⊆ X is the support of an extreme point, then C = H (C) [11, Lemma 3]; E3. there are at most 2 n−1 extreme points, and this bound is tight [11, Theorem 4] .

Unfortunately, these observations do not hold in the case of non-elementary comparative assessments, as is illustrated by the following example. We learn from Example 2 that (E1) does not hold because p 4 is not a uniform distribution; (E2) does not hold because the support of p 1 is {1, 2, 4} but H ({1, 2, 4}) = {1, 2, 3, 4, 5}; and (E3) does not hold because there are more than 2 5−1 = 16 extreme points. In fact, we see that a comparative credal set can have more than 2 n extreme points. Consequently, we cannot use the strategy of [11, Algorithm 1]-that is, construct the possible supports and use the uniform distribution over them-to immediately determine the extreme points of the comparative credal set for some general comparative assessment. That being said, we have nevertheless identified some special cases other than the elementary one in which we can generate the extreme points procedurally.

As a first special case, we consider a straightforward extension of [11] using a multi-level approach. At the core of this special case are some nested partitions of the possibility space and the restriction that the comparative judgements can only concern events that are on the same level of the nested partitions and belong to the same part of the partition in the previous level. We will here only explain the two-level case in detail; extending the approach to multiple levels is straightforward.

Let C 1 , . . . , C k be a partition of the possibility space X . A comparative assessment C is two-level over this partition if it can be partitioned as Observe that if such a decomposition exists, then we can interpret C as an elementary comparative assessment with possibility space X := {C 1 , . . . , C k } and, for all i ∈ {1, . . . , k}, we can interpret C i as an elementary comparative assessment with possibility space C i . Hence, we may use the algorithm described in [11] to determine the extreme points of the comparative credal sets corresponding to these elementary comparative assessments, which we shall denote by M el , M el,1 , . . . , M el,k , respectively. The following result establishes that we can combine these extreme points to obtain the extreme points of the original comparative credal set M C . Furthermore, as corollary of Proposition 11 and [11, Theorem 4] we obtain the following bound on the number of extreme points.

Consider a comparative assessment C that is two-level over some partition. Then |ext(M C )| ≤ 2 n−1 .

Recall from Sect. 4.4 that the absence of cycles simplifies things if we are interested in the compatibility with strict comparative judgements. Hence, it does not seem all too far-fetched that determining the (number of) extreme points of the comparative credal set induced by a (non-strict) comparative assessment also simplifies under the absence of cycles. As will become clear in the remainder, this is only certainly so in some special cases.

First, we revisit the three main points of [11] that we recalled at the beginning of this section in the case of acyclic graphs. Our running example shows that also in the acyclic case (E1) does not hold because p 7 , p 8 and p 9 are not uniform; (E2) does not hold because p 3 has support C 3 := {1, 3} but H (C 3 ) = {1, 2, 3} = C 3 ; and (E3) does not hold because there can be more than 2 4−1 = 8 extreme points. Furthermore, since different extreme points can have the same support-in our running example, this is the case for p 7 , p 8 and p 9 -there is no reason why the number of extreme points should be bounded above by 2 n . Nevertheless, and despite our rather extensive search, we have not succeeded in finding an example of a comparative assessment C with an acyclic digraph G that has a comparative credal set with more than 2 n extreme points. This is in contrast with the cyclic case, as we have shown in Example 2.

While the absence of cycles alone does not seem to allow us to efficiently determine the extreme points, there are two interesting special cases that permit us to do so. Essential to both these special cases is a specific class of subdigraphs of the digraph G. To define this class, we first need to introduce two concepts from graph theory. The first concept is that of the root of a digraph H: a node ν such that for any other node ν , there is a directed path from ν to ν . The second concept is that of an arborescence: a digraph that has a root and whose underlying graph is a tree. We now call a subdigraph G of the digraph G an extreme arborescence if (i) it is an arborescence whose root x has no predecessors in the digraph G; and (ii) each of its auxiliary nodes has one direct predecessor and one direct successor.

Important to note here is that all extreme arborescences can be easily procedurally generated. In essence, one needs to (i) select a node x without predecessors in the original digraph G; (ii) either stop or, if possible, (a) add one of the outgoing edges of x and the auxiliary node ξ in which it ends, (b) add one of the outgoing edges of ξ and the atom y such that y is not already in the arborescence; (iii) repeat step (ii) but with x being any of the atoms already in the arborescence. Singular Assessments. The first special case of acyclic digraphs concerns representing digraphs where every atom has at most one direct predecessor. We call a comparative assessment C singular if |{(A, B) ∈ C : x ∈ B}| ≤ 1 for all x ∈ X .

We see for instance that the comparative assessment in our running example is not singular, since 4 appears in both the assessments ( In case it is, we can establish the following: Theorem 1. Consider a singular assessment C such that the associated digraph G is acyclic. Then every extreme point p of M C corresponds to a unique extreme arborescence G ⊆ G and vice versa, in the sense that p is the unique probability mass function that saturates the comparative constraints associated with the auxiliary nodes in G and the non-negativity constraints associated with the atoms that are not in G .

Because we can procedurally generate all extreme arborescences, it follows that we can use Theorem 1 to generate all extreme points of the comparative credal set. Another consequence of Theorem 1 is that we can establish a lower and upper bound on the number of extreme points in the singular case. Theorem 2. Consider a singular assessment C such that the associated digraph G is acyclic. Then n ≤ |ext(M C )| ≤ 2 n−1 .

These lower and upper bounds are reached, as we can see from [11, Section 4.1] .

Arborescences. Finally, we consider the case that the digraph G is an arborescence. Clearly, for this it is necessary that C is singular and that |A| = 1 for every (A, B) ∈ C . As arborescences are special types of acyclic digraphs, we can strengthen Theorem 1 to be-in some sense-similar to [11, Theorem 1] .

Consider and assessment C such that the associate graph is an arborescence. Then the set of extreme points of M C consists of the uniform distributions on H (C), where C is any set of atoms such that, for all x, y ∈ C, the closest common predecessor of x and y is a non-auxiliary node.

We also observe that the bound on the number of extreme points established in Theorem 2 is still valid. To see that this result does not extend to all singular assessments, it suffices to take the extreme points of the assessment depicted in Fig. 2 .

Although we find the results in this paper promising, there are some open problems that call for additional research, which should help towards making this model more operative for practical purposes. First and foremost, we would like to deepen the study of the acyclic case, and in particular to determine the number and the shape of the extreme points in other particular cases. In addition, a bound on the number of linearly independent constraints, in the manner hinted at in Sect. 3, should let us get a better bound on the number of extreme points. Finally, we should also look for graph decompositions that allow to work more efficiently with comparative judgements.

Introduction to Imprecise Probabilities. Wiley Series in Probability and Statistics

Credal networks

On the number of extreme points of the core of a transferable utility game

The complexity of vertex enumeration methods

Sul significato soggettivo della probabilità

Graphs Theory and Applications: With Exercises and Problems

Probability and the Weighting of Evidence

Comparative probabilities. In: The Open Handbook of Formal Epistemology

The axioms and algebra of intuitive probability

The Enterprise of Knowledge

Extreme points of the credal sets generated by comparative probabilities

Coherence graphs

Comparative probability and robustness

On the foundations of decision making under partial information

The Foundations of Statistics

Measurement structures and linear inequalities

Statistical Reasoning with Imprecise Probabilities

Extreme points of coherent probabilities in finite spaces

Acknowledgement. Enrique Miranda's research was supported by projects PGC2018-098623-B-I00 and IDI/2018/000176.