Enrique Miranda
email: mirandaenrique@uniovi.es

Sebastien Destercke
email: sebastien.destercke@hds.utc.fr

OVIEDO, SPAIN C-Calvo Sotelo, S/N

EXTREME POINTS OF THE CREDAL SETS GENERATED BY COMPARATIVE PROBABILITIES

Keywords: Comparative probabilities, credal sets, 2-monotone capacities, belief functions, extreme points, imprecise probability masses

When using convex probability sets (or, equivalently, lower previsions) as uncertainty models, identifying extreme points can help simplifying various computations or the use of some algorithms. In general, sets induced by specific models such as possibility distributions, linear vacuous mixtures or 2-monotone measures may have extreme points easier to compute than generic convex sets. In this paper, we study extreme points of another specific model: comparative probability orderings between the singletons of a finite space. We characterise these extreme points by mean of a graphical representation of the comparative model, and use them to study the properties of the lower probability induced by this set. By doing so, we show that 2-monotone capacities are not informative enough to handle this type of comparisons without a loss of information. In addition, we connect comparative probabilities with other uncertainty models, such as imprecise probability masses.

INTRODUCTION

In the last decades, there has been a growing interest in imprecise probability models as alternative models to probability in situations where the available information is vague or scarce. This type of models include for instance possibility measures [START_REF] Dubois | Possibility Theory[END_REF], belief functions [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], 2-and n-monotone capacities [START_REF] Choquet | Theory of capacities[END_REF][START_REF] Denneberg | Non-Additive Measure and Integral[END_REF]] and probability boxes [START_REF] Destercke | Unifying practical uncertainty representations: I generalised p-boxes[END_REF][START_REF] Ferson | Constructing probability boxes and Dempster-Shafer structures[END_REF].

All the examples above can be seen as particular cases of coherent lower and upper previsions [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF].

The adequacy of each of these models for a particular problem depends, among other things, on the interpretation we are giving to our uncertainty. In this paper, we consider a robust Bayesian interpretation [START_REF] Berger | An overview of robust Bayesian analysis[END_REF][START_REF] Good | Subjective probability as the measure of a non-measurable set[END_REF]: we assume the existence of a precise, but unknown, probability model, and work with the set of probability measures that are compatible with the available information. This gives rise to a credal set, as considered by [START_REF] Levi | The enterprise of knowledge[END_REF].

Here, we consider the case where the information is expressed by means of a comparative probability model [START_REF] De Finetti | Sul significato soggettivo della probabilità[END_REF], Koopman , 1940a,b]: we consider a finite possibility space X and assume that we are given judgements of the type "the probability of A is at least as great as that of B". Comparative probabilities have been deemed of particular interest within the context of subjective probability theory [START_REF] Fine | Theories of Probability[END_REF][START_REF] Fine | An argument for comparative probability[END_REF][START_REF] Fishburn | The axioms of subjective probability[END_REF][START_REF] Suppes | The measurement of belief[END_REF][START_REF] Walley | Varieties of modal (classificatory) and comparative probability[END_REF]; we also refer to [START_REF] Capotorti | Comparative uncertainty: theory and automation[END_REF][START_REF] Christian | Flippable pairs and subset comparisons in comparative probability orderings[END_REF][START_REF] Nehring | Imprecise probabilistic beliefs as a context for decision-making under ambiguity[END_REF] for some recent work and to Walley [1991, Section 4.5] for a study from the point of view of coherent lower previsions. One of their advantages is that they seem well suited for modelling qualitative judgements (e.g., expert opinions). Moreover, they have been shown to be more general than classificatory probabilities [START_REF] Walley | Varieties of modal (classificatory) and comparative probability[END_REF], and they can also be used to compare random quantities [START_REF] Cohen | Necessary and sufficient conditions for the existence and uniqueness of weak qualitative probability measures[END_REF].

In spite of this, there are only few works dealing with the numerical and practical aspects of comparative probabilities [START_REF] Regoli | Comparative probability and robustness[END_REF]. One reason for this is that it is not easy to summarize the set of probabilities associated with the comparative assessments, for instance by means of a lower and an upper probability, and this renders it difficult to handle the information about the probability of the events of interest. In this paper, we solve this problem for the specific case of comparisons between the probabilities of singletons. We do so by characterizing the comparative probability models by means of the extreme points of their associated sets of probabilities. Characterizing such extreme points is instrumental in a number of applications of imprecise probabilities, including inferences for graphical [START_REF] Cano | Algorithms for imprecise probabilities[END_REF] and statistical models [Walley , 1991, Sec. 8.5], and also to compute bounds of some functionals such as entropy [START_REF] Abellán | Upper entropy of credal sets. Applications to credal classification[END_REF]. It is a problem that has been studied for other types of imprecise probability models, such as 2-monotone capacities [START_REF] Chateauneuf | Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion[END_REF], possibility measures [START_REF] Miranda | Extreme points of credal sets generated by 2-alternating capacities[END_REF], probability intervals [START_REF] De Campos | Probability intervals: a tool for uncertain reasoning[END_REF] and belief functions [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]; however, as we shall detail later, there is only one partial result for the case we shall consider in this paper [START_REF] Gulordava | Empirical evaluation of credal classifiers. Master's thesis[END_REF].

After giving some preliminary results in Section 2, we show in Section 3 that, when the comparison judgements are made on the probabilities of the singletons, a graphical representation of these judgements makes it easy to derive the extreme points of the associated credal sets. In Section 4, we use this result to discuss some practical aspects of these models: we establish tight lower and upper bounds of the number of extreme points; investigate their relationship with other imprecise probability models; provide algorithms for the extraction of these extreme points; and discuss the computation of conditional lower probabilities and the merging of multiple comparison judgments. Some additional remarks related to the practical use of these models and their extensions are provided in Section 5.

PRELIMINARIES

Consider a finite space X = {x 1 , . . . , x n }, modelling the set of outcomes of some experiment. In this paper, we assume that our information about these outcomes can be modelled by means of comparative probability orderings of the states, i.e., statements of the type "the probability of x i is at least as great as that of x j ". Hence, we shall represent the available information by means of a subset L of {1, . . . , n} × {1, . . . , n} modelling the (pre)order relation between the states.

The set of probability measures compatible with this information is given by ( 1) P(L ) = {P ∈ P X : ∀(i, j) ∈ L , P(x i ) ≥ P(x j )},

where P X denotes the set of all probability measures on X . This set is called the natural extension of the ordering by Walley [1991, Section 4.5.1]. This can be equivalently stated by saying that we consider a preorder between the singletons and we want to characterise the set of probability measures P that agree with this order, in the sense that

x i x j ⇒ P(x i ) ≥ P(x j ).

For the purposes of this paper, it shall be useful to represent these assessments by means of a graph G = (X , L ) where the nodes are the elements of X and we draw an edge between x i and x j when (i, j) ∈ L .

Example 1. Consider the space X = {x 1 , . . . , x 5 } and the assessments L = {(1, 3), (1, 4), (2, 5), (4, 5)}.

The acyclic graph G associated with L is given by Figure 1.

x 1 x 3 x 4 x 2 x 5 FIGURE 1. Graph G of Example 1.
Note that the credal set P(L ) determined by Eq. ( 1) is always nonempty, because it includes for instance the uniform probability distribution. Further, the set P(L ) coincides with the set P(C (L )) determined by the transitive closure C (L ) of L , as the additional constraints of C (L ) are redundant with those of L : since any model in P(L ) (a probability measure) is transitive, so should be the relationship associated with L .

It is interesting to compare P(L ) with the set

P(L ) = {P ∈ P X : ∀(i, j) ∈ L , P(x i ) > P(x j )},
i.e., with the credal set associated with strict probability comparisons, which also appear sometimes in the literature [START_REF] Fishburn | The axioms of subjective probability[END_REF]. Since P(L ) is a convex polytope in R n , it follows from basic convex analysis that P(L ) corresponds to the closure of P(L ) when the latter set is non-empty, and this non-emptiness is easy to characterise.

Lemma 1. P(L ) = / 0 if and only if its associated graph G is acyclic.

Proof. "Only if": G cyclic means that there are at least two indices i, j such that P(x i ) > P(x j ) and P(x i ) < P(x j ), leading to an inconsistency. "If": if G is acyclic, then it can be associated with a preorder over the probability masses P(x i ). We can then take a linear extension of this preorder and associate it with a permutation σ of {1, . . . , n} such that P(x σ (1) ) < P(x σ (2) ) < . . . < P(x σ (n) ); then, it is easy to see that there exists a probability satisfying all these constraints: we may for instance consider the probability measure associated with the probability mass P(x

σ (i) ) = 1 /n -(n -i)ε for i = 1, . . . , n -1 and P(x σ (n) ) = 1 /n + ε + . . . + (n -1)ε with ε ∈ (0, 1 n 2 ).
Indeed, a cyclic graph G is incompatible with the irreflexive property that strict comparative assessments must satisfy. Nevertheless, in this paper we shall focus on non-strict comparative assessments, and for those the associated graph G may possess cycles, as we shall discuss later.

Note also that we can straightforwardly connect our current model with the axiomatic view of comparative probabilities [START_REF] De Finetti | Sul significato soggettivo della probabilità[END_REF]. From L , we can obtain a probability ordering over subsets of X such that A B whenever P(A) ≥ P(B) for all P ∈ P(L ). Using [Walley , 1991, Sec. 4.5.3.], this probability ordering satisfies a number of properties, in particular all axioms required by de Finetti [1931] except for the one of completeness. Hence, while we focus in this paper on the numerical aspects associated with specific comparative probabilities, we are completely inline with the axiomatic view.

EXTREME POINTS OF P(L )

In this section, we characterise the extreme points of the credal set P(L ) associated with a number of probability comparisons on the singletons. Consider a finite space X = {x 1 , . . . , x n } and a subset L of {1, . . . , n} × {1, . . . , n}, and let P(L ) be the set it determines by means of Eq. ( 1). Any of the probability measures in P(L ) is completely determined by its probability mass, and as a consequence it can be seen as an element of the n-dimensional Euclidean space (more specifically of the n -1 unit simplex). Then, P(L ) is a closed convex subset of R n in the Euclidean topology, which is equal to the closed convex hull of its set of extreme points. That is, we can characterize the set of functions P : X → [0, 1] such that (i, j) ∈ L ⇒ P(x i ) ≥ P(x j ) and ∑ x∈X P(x) = 1 by means of its extreme points 1 . Recall that P is an extreme point of P(L ) when for every P 1 , P 2 ∈ P(L ) and every α ∈ (0, 1),

P = αP 1 + (1 -α)P 2 ⇐⇒ P 1 = P 2 = P,
that is, when P cannot be expressed as the convex combination of two other points of P(L ). We shall determine these extreme points by means of the graphical representation we have established in Section 2. In order to do this, we consider a number of lemmas: Lemma 2. Any extreme point P of P(L ) corresponds to a uniform probability measure concentrated over some subset A ⊆ X .

Proof. The (linear) constraints determining P(L ) are:

C = {P(x i ) ≥ P(x j ) ∀(i, j) ∈ L } B = {0 ≤ P(x) ≤ 1 ∀x ∈ X } S = { ∑ x∈X P(x) = 1}
Also recall that, in order to determine an extreme point P of P(L ), its probability mass must saturate n = |X | linearly independent constraints delimiting P(L ) [Bertsimas and Tsitsiklis , 1997, Section 2.2.], that is, constraints in C ∪ B ∪ S . Clearly, S is always saturated. Now, let us show that in order to saturate n constraints, a probability measure P ∈ P(L ) must be uniform on some subset A ⊆ X . Without loss of generality, assume that there are elements P(x 1 ), . . . , P(x ) that are 1 In this respect, the problem under study is somewhat related to that in random utility representations, where a partial rank among the alternatives is established and the goal is to infer from it the probability of each alternative being optimal. See [START_REF] Fishburn | Binary choice probabilities and rankings[END_REF], [START_REF] Koopen | Random utility representation of binary choice probabilities: critical graphs yielding critical necessary conditions[END_REF] and [START_REF] Marschak | Binary choice constraints and random utility indicators[END_REF] for some works in this field. non-null. This means that, unless = 1, none of them saturates a constraint in B. The result then follows taking into account that:

• as the nprobabilities P(x +1 ), . . . , P(x n ) are zero, they saturate ninequalities in B (that are, by definition, linearly independent, as they bear on disjoint singletons); • saturating inequalities in C can only be done by equating some probabilities P(x i ) = P(x j ); • any set of m equal probabilities will saturate at most m -1 linearly independent inequalities in C , forming the chain

P(x 1 ) = . . . = P(x m ).
Note that, even if two null probabilities also saturate constraints in C , they will only saturate linearly dependent constraints, because the restrictions P(x i ) -P(x j ) ≥ 0, P(x i ) ≥ 0 and P(x j ) ≥ 0 are linearly dependent: P(x i ) -P(x j ) = 1 • P(x i ) + (-1) • P(x j ). Therefore we can omit those constraints in C that are saturated by null probabilities. This means that, if the non-null probabilities are not all equal, they saturate k < -1 linearly independent inequalities in C ; hence, in that case the total number of linearly independent inequalities in C ∪ B ∪ S that are saturated is

k + n -+ 1 < -1 + n -+ 1 = n.
Therefore, a probability measure P that is not uniform on some subset A ⊆ X cannot be an extreme point.

For every subset A of X , we shall denote by P A the uniform probability measure on A, which is determined by the values (2)

P A (x i ) = 1 |A| if x i ∈ A 0 otherwise
for any i ∈ {1, . . . , n}. Using the graph G , we can now characterize those subsets A ⊆ X for which P A is an extreme point of P(L ). For every x j ∈ X , we shall denote by H(x j ) the set of ancestors of x j , i.e., those nodes x i such that there is a directed path going from x i to x j in G . By an abuse of notation, we shall also consider that x j is an ancestor of itself, i.e., we shall assume that x j ∈ H(x j ) for all j. Finally, for every A ⊆ X , we shall denote H(A) := ∪ x∈A H(x). Using the terminology from [START_REF] Cozman | Credal networks[END_REF], we shall refer to H(A) as the top subnetwork of G generated by A. Our next result shows that we can restrict our attention to uniform probability measures on top subnetworks.

Lemma 3. If A = H(A), then P A is not an extreme point of P(L ).

Proof. If A is a proper subset of H(A), then we can find x i , x j ∈ X such that (i, j) ∈ L and x i ∈ H(A) \ A, x j ∈ A. Since (i, j) ∈ L , this means that we have made the assessment P(x i ) ≥ P(x j ). On the other hand, given the uniform probability distribution P A , it follows from Eq. (2) that

P A (x i ) = 0 < P A (x j ) = 1 |A| .
Hence, P A does not belong to P(L ) and as a consequence it cannot be an extreme point.

Example 2. Consider Example 1 and the set A = {x 2 , x 4 }. As H(A) = {x 1 , x 2 , x 4 } = A, the probability measure associated with the probability mass P(x 2 ) = P(x 4 ) = 1 /2 is not an extreme point.

In order to simplify the notation, we shall consider the set

H := { / 0 = B ⊆ X : B = H(A) for some A}.
Lemma 3 implies that we can focus on the elements of H in order to identify the extreme points. Our next result shows that not all of those sets will give rise to an extreme point of P(L ). Lemma 4. Consider a set B ∈ H . If there are B 1 , B 2 ∈ H such that B 1 ∩ B 2 = / 0 and B 1 ∪ B 2 = B, then P B is not an extreme point on P(L ).

Proof. First of all, let us show that for every B ∈ H , P B belongs to P(L ).

Consider any (i, j) ∈ L . There are two possibilities: if x j ∈ B, then since B is a top subnetwork also x i belongs to B, whence P B (x i ) = P B (x j ) = 1 |B| . On the other hand, if x j / ∈ B, then P B (x j ) = 0 ≤ P B (x i ), and therefore the constraint is also satisfied. Now, if B is the disjoint union of B 1 and B 2 , we can deduce from Eq. (2) that

P B = |B 1 | |B| P B 1 + |B 2 | |B| P B 2 ; since |B 1 | + |B 2 | = |B|,
we deduce that P B is a convex mixture of two different probabilities in P(L ), and as a consequence it cannot be an extreme point.

Example 3. Consider Example 1 and the set B = {x 1 , x 2 , x 4 }. Then given the sets

B 1 = {x 1 , x 4 }, B 2 = {x 2 }, it holds that B, B 1 , B 2 ∈ H , B 1 ∩ B 2 = / 0 and B 1 ∪ B 2 = B.
From this we can derive that P B = 2 /3P B 1 + 1 /3P B 2 and therefore it is not an extreme point of P(L ).

The top subnetwork associated with B ∈ H is not weakly connected 2 if and only if we can decompose it in the manner depicted in Lemma 4, 2 By weakly connected we mean that for every two nodes in the graph associated with B there is an undirected path between them. by considering its weakly connected components (i.e., the maximal weakly connected subsets). Thus, we can restrict our attention to weakly connected top subnetworks of G . This leads to the main result in this section, where we establish that any of these sets determines an extreme point of P(L ):

Theorem 1. The set of extreme points coincides with the set of probabilities P B generated by sets B ∈ H that cannot be decomposed as in Lemma 4.

Proof. From Lemmas 2 and 4 any extreme point of P(L ) corresponds to a uniform distribution P B , where B ∈ H cannot be decomposed as the disjoint union of other elements of H . Let us prove that, conversely, given a set B of this type the probability measure P B it determines is indeed an extreme point.

Assume ex absurdo that this is not the case for some set B. This means that there are m ≥ 2, B 1 , . . . , B m ∈ H and α 1 , . . . , α m > 0 s.t. ∑ m i=1 α i = 1 and

(3)

P B = α 1 P B 1 + . . . + α m P B m .
It must be B i ⊆ B for all i = 1, . . . , m: otherwise, there would be some node x j such that P B i (x j ) > 0 = P B (x j ), a contradiction with (3). We deduce also that B i must be a proper subset of B for all i = 1, . . . , m, or we would obtain that P B and P B i coincide.

Denote C = B \ B i . Then H(C) ⊆ B, whence

B = B i ∪C ⊆ B i ∪ H(C) ⊆ B
and therefore B = B i ∪ H(C). Since H(C) ∈ H , we deduce that it must be H(C) ∩ B i = / 0, since otherwise B would be the disjoint union of two elements of H , a contradiction with the assumptions we have made on B. Therefore, there is some x k ∈ C such that H(x k ) ∩ B i = / 0. Given x j ∈ B i ∩ H(x k ), we have that ( j, k) ∈ C (L ), and x j ∈ B i , x k / ∈ B i . As a consequence,

P B i (x j ) > P B i (x k ) = 0, whence m ∑ =1 α (P B (x j ) -P B (x k )) > 0 = P B (x j ) -P B (x k ),
taking into account that P B (x j ) -P B (x k ) ≥ 0 for every = 1, . . . , m because P B belongs to P(L ). This is a contradiction. Hence, Eq. (3) does not hold and therefore P B is an extreme point.

Remark 1. An interesting related result has been established by [START_REF] Gulordava | Empirical evaluation of credal classifiers. Master's thesis[END_REF], in the context of credal classification. There, it is considered the credal set determined by the comparisons of the probabilities of the states, and it is computed the lower probability of the set A of elements with no predecessor in G . In order to determine this lower probability, she provides results analogous to our Lemmas 2 and 3, and then in [Gulordava , 2010, Theorem B.2.2] she establishes which elements in P(L ) attain the lower probability of A.

Our previous result subsumes these results, in the sense that we give the explicit form of the extreme points (from which we may determine also the lower probability of any other set, as well as the lower prevision induced by a comparative probability model). Note moreover that we have shown that not all the uniform probability distributions P H(A) determine an extreme point of P(L ).

Example 4. The extreme points generated by Example 1 are summarized in Table 1:

p B x 1 x 2 x 3 x 4 x 5 {x 1 } 1 0 0 0 0 {x 2 } 0 1 0 0 0 {x 1 , x 3 } 1 /2 0 1 /2 0 0 {x 1 , x 4 } 1 /2 0 0 1 /2 0 {x 1 , x 2 , x 4 , x 5 } 1 /4 1 /4 0 1 /4 1 /4 {x 1 , x 3 , x 4 } 1 /3 0 1 /3 1 /3 0 {x 1 , x 2 , x 3 , x 4 , x 5 } 1 /5 1 /5 1 /5 1 /5 1 /5 TABLE 1. Extreme points of Example 1.
To conclude this section, we discuss briefly a couple of ways in which the procedure above may be simplified. On the one hand, when the graph G is not weakly connected, we can decompose it as a union of its weakly connected components G 1 , . . . , G k . Each of these components G i will be a graph on the elements of a respective subset X i of X , and the sets {X 1 , . . . , X k } will form a partition of X . Then we can characterise the extreme points associated with G i in the form given by Theorem 1, and extend them from X i to X by assigning zero mass to the elements of X \ X i . The extreme points associated with G will be the union of the sets of extreme points obtained in this way. This is formalised in the following result: Proposition 2. Let P i ⊆ P X i be the set of extreme points associated with the graph G i by means of Theorem 1. Then the extreme points of P(L ) are given by

∪ k i=1 {ext i (P i ) : P i ∈ P i },
where ext i (P i ) is the element of P X given by

(4) ext i (P i )(x j ) = P i (x j ) if x j ∈ X i 0 otherwise.
Proof. It suffices to note that a subset of G can only be weakly connected when it is included in one of the weakly connected components G i . Then, the set of weakly connected top subnetworks of G is given by the union of the weakly connected top subnetworks of G 1 , . . . , G k . Each of these subnetworks determines a probability measure in one of X 1 , . . . , X k that is in a one-to-one correspondence with a probability measure on X , in the manner depicted in Eq. ( 4).

On the other hand, we can also assume without loss of generality that the graph G associated with our set of assessments L is acyclic. When this is not the case, we have some assumptions of equality P(x i ) = P(x j ) between the probabilities of two elements x i , x j in our possibility space.

If we define the equivalence relationship

(5)

x i Rx j ⇐⇒ P(x i ) = P(x j ) ∀P ∈ P(L ),
then we can consider a representative x i for each equivalence class, so that we end up with a subset X of X . If we denote n i = |[x i ] R | the number of elements in the equivalence class associated with x i , then it holds that

∑ x i ∈X n i = n = |X |. Let (6) L := {(i, j) ∈ C (L ) : x i , x j ∈ X },
be the set of comparative probability assessments on this subset of X , and let G be its associated (acyclic) graph.

Proposition 3. There is a one-to-one correspondence between the extreme points of P(L ) and of P(L ).

This shows that there is a one-to-one correspondence between the weakly connected top subnetworks of G and those of G , and as a consequence between the extreme points of P(L ) and those of P(L ).

The following example illustrates this procedure:

Example 5. Consider the space X = {x 1 , x 2 , x 3 , x 4 }, and the assessments

L = {(1, 2), (2, 3), (2, 1), (3, 4)}. x 1 x 3 x 4 x 2 G x 1 x 3 x 4 G FIGURE 2.

Graphs associated with L and L

We see that the associated graph (Figure 2) has a cycle between x 1 and x 2 . Hence, we can consider the alternative graph G related to the space X = {x 1 , x 3 , x 4 } and the assessments L = {(1, 3), (3, 4), (1, 4)} determined by Eq. ( 6) (note that the assessment (1,4) is actually redundant).

It follows from Theorem 1 that the extreme points of P(L ) are given by Table 2:

p B x 1 x 3 x 4 {x 1 } 1 0 0 {x 1 , x 3 } 1 /2 1 /2 0 {x 1 , x 3 , x 4 } 1 /3 1 /3 1 /3 TABLE 2. Extreme points of P(L )
and from this we deduce the extreme points of P(L ) given by Table 3.

p exp(B) x 1 x 2 x 3 x 4 {x 1 , x 2 } 1 /2 1 /2 0 0 {x 1 , x 2 , x 3 } 1 /3 1 /3 1 /3 0 {x 1 , x 2 , x 3 , x 4 } 1 /4 1 /4 1 /4 1 /4 TABLE 3. Extreme points of P(L )
Note that all these extreme points correspond again to uniform probability distributions.

Remark 2. The comments above imply that for every x i ∈ X its associated top subnetwork B i = H({x i }) ∈ H determines an extreme point of P(L ): if it was the disjoint union of two top subnetworks C 1 ,C 2 then at least one of them should include x i , and as a consequence also B i , a contradiction. When G is acyclic, all these top subnetworks are different.

Remark 3. When G is weakly connected and acyclic, any top subnetwork B ∈ H associated with an extreme point in the manner detailed in Theorem 1 is in correspondence with a set A of strongly disconnected3 but weakly connected nodes in G , by means of the equality B = H(A): this set is given by the nodes in B that have no successor in B, i.e., the leaves in the associated sub-graph. That this set is non-empty follows from the fact that G is acyclic, and then it is trivial that H(A) = B. To see that any extreme point is associated with only one set of strongly disconnected nodes, note that it is impossible for two distinct sets of strongly disconnected nodes A, A to satisfy H(A) = H(A ) (and thus determine the same extreme point):

if x i ∈ A \ A , then since x i ∈ H(A) = H(A ) there must be some x j ∈ A such that x i ∈ H(x j ); but x j ∈ H(A ) = H(A) implies that there is some x k ∈ A such that x j ∈ H(x k ).
Note that it cannot be x k = x i , because then we would obtain that x i ∈ H(x j ) and x j ∈ H(x i ), meaning that there is a cycle involving x i , x j , a contradiction. On the other hand, if x i = x j then we obtain that x i ∈ H(x k ), which contradicts the assumption that the nodes in A are strongly disconnected.

On the other hand, when G is a weakly connected and acyclic graph, there is a one-to-one correspondence between sets of strongly disconnected nodes and the antichains of the partial order induced by L , not counting / 0 as an antichain. This means that the number of antichains of G is an upper bound of the number of extreme points of P(L ). Note however, that not all sets of strongly disconnected nodes give rise to an extreme point, because it is also necessary that the associated top subnetwork is non-decomposable, as we have established in Lemma 4.

PRACTICAL ASPECTS

In this section, we explore various practical aspects (number and extraction of extreme points, n-monotonicity properties, conditioning, merging of information) of comparative probability models on singletons.

4.1. Number of extreme points. Since extreme points correspond to uniform distributions over certain subsets A ⊆ X , we immediately see that an upper bound of the number of extreme points is 2 |X | -1. Note that this is significantly lower than the maximal number of extreme points generated by lower coherent probabilities, known to be |X |! [START_REF] Wallner | Extreme points of coherent probabilities in finite spaces[END_REF]. We next show that this number of extreme points can be reduced even further:

Theorem 4. The maximal number of extreme points of P(L ) is 2 (|X |-1) .
Proof. Consider first of all the case where the graph G is weakly connected and acyclic.

Remark 3 tells us that the number of extreme points of P(L ) corresponding to a weakly connected and acyclic graph G is bounded above by its number of antichains. Therefore, determining the maximal number of antichains of G provides an upper bound on the number of extreme points. Dilworth's Theorem [START_REF] Dilworth | A decomposition theorem for partially ordered sets[END_REF] tells us that for a finite partially ordered set whose maximal antichain has cardinality a, there exists a minimum number a of disjoint chains of elements partitioning the set X . Every antichain contains at most one element of these disjoint chains, and assuming they have c 1 , . . . , c a elements, the number of antichains (excluding the empty set) is at most

(7) (c 1 + 1)(c 2 + 1) . . . (c a + 1) -1
Taking this idea into account, we can also bound the number of antichains by the number above as soon as there is a partition of disjoint chains (even if may be different from a) of elements partitioning the set X , with respective cardinalities c 1 , . . . , c . We shall use this to prove that the number of antichains is bounded by 2 |X |-1 . In this respect, we shall use that for every natural number k ≥ 3 it holds that k + 1 ≤ 2 k-1 , and for k = 1, 2 it holds that k + 1 ≤ 2 k . There are two possibilities:

(a) Assume first of all that there is a partition of X made up of chains of respective lengths c 1 , . . . , c , and that c j ≥ 3 for j = 1, . . . , i. Then by Eq. ( 7) the maximal number of antichains is bounded by

(c 1 + 1)(c 2 + 1) . . . (c + 1) ≤ 2 ∑ i j=1 c j -1 • 2 ∑ j=i+1 c j ≤ 2 (∑ j=1 c j )-1 = 2 |X |-1 ,
taking into account that i ≥ 1. (b) If there is no chain with length greater than or equal to 3, then it is possible to find a partition of X made up of chains of respective lengths c 1 , . . . , c , and such that c j = 2 for j = 1, . . . , i and c j = 1 for j = i + 1, . . . , . Note that it must be i ≥ 1 because we are assuming that the graph G is connected. Eq. ( 7) gives us the upper bound 3 i • 2 |X |-2i -1 for the number of antichains. However, since G is connected, given j ∈ {i + 1, . . . , } the node in c j must be a successor of at least one of the top elements of c 1 , . . . , c i . Hence given any non-empty subset of {c i+1 , . . . , c }, there is at least one selection of nodes in {c 1 , . . . , c i } for which the combination does not produce an antichain. This allows us to reduce the number of antichains by 2 |X |-2i -1, meaning that the upper bound can be refined into

3 i • 2 |X |-2i -1 -(2 |X |-2i -1) = (3 i -1)2 |X |-2i ≤ 2 |X |-1 ,
taking into account that 3 i -1 ≤ 2 2i-1 for any natural number i ≥ 1. To see that the bound given by the theorem above can indeed be reached, consider the case where a single modal value is provided4 , that is, of L = {(1, j) : j = 2, . . . , |X |}. Figure 3 illustrates the situation for five elements. In this case, the extreme points are obtained by the top subnetwork induced by x 1 and all non-empty subsets of {x 2 , . . . , x |X | } (whose number is 2 |X |-1 -1); that is there are 2 |X |-1 extreme points.

x 1 x 2 x 3 x 4 x 5 FIGURE 3. Graph G for x 1 =modal value
Next, if G is weakly connected but has cycles, we consider the equivalence relationship in Eq. ( 5), and let X be a subset of X obtained by considering one element from each equivalence class. If we let L be given by Eq. ( 6), then there is a one-to-one correspondence between the extreme points of P(L ) and those of P(L ). Applying the first part of the proof, we conclude that the number of extreme points is bounded by

2 |X |-1 ≤ 2 |X |-1 .
Finally, if the graph G is not weakly connected, we can express it as the union of its weakly connected components G 1 , . . . , G k , which determine a partition {X 1 , . . . , X k }. The number of extreme points of P(L ) is equal to the sum of the number of extreme points of P(L i ) for i = 1, . . . , k, where P(L i ) is the set of probability measures associated with G i . Applying the previous part, this number is bounded by

2 |X 1 |-1 + • • • + 2 |X k |-1 ≤ 2 ∑ k i=1 |X i |-1 = 2 |X |-1 , taking into account that the function f (x) = 2 x is subadditive.
Interestingly, the bound given in Theorem 4 is the same as the number of extreme points of the set of probability measures dominated by a possibility measure, as shown by Miranda et al. [2003, Section 5], and it is smaller than the one (|X |!) for the number of extreme points associated with belief functions [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]. Our intuition for this is that possibility measures also determine an order between the singletons, by means of their associated possibility distributions.

On the other hand, the number of extreme points can be much lower. To see this, consider the equivalence relationship given by Eq. ( 5), and let X be a subset of X obtained by considering one element from each equivalent class. The ideas in Remark 2 lead easily to the following result:

Proposition 5. The minimum number of extreme points of P(L ) is |X |.

Proof. Let L be given by Eq. ( 6). Then we have seen that there is a oneto-one correspondence between the extreme points of P(L ) and those of P(L ). On the other hand, by Remark 2 every x i ∈ X determines a different extreme point of P(L ) by means of the top subnetwork it generates in the graph G . Thus, there are at least |X | extreme points for any L .

Two typical examples where this minimal number of extreme points is reached is the case where L = / 0, in which case the extreme points are all Dirac measures, and the case where L forms a complete ordering of singletons {x 1 , . . . , x n } (treated by Kofler [1989, P. 26] and Walley [1991, P. 195]).

Remark 4. In particular it follows from our results that if we consider a comparative probability ordering between the singletons, the only case in which the set P(L ) has only one element is when

{(1, 2), (2, 3), . . . , (n -1, n), (n, 1)} ⊆ C (L ),
that is, when all the elements x 1 , . . . , x n of X are believed to be equally likely. In that case, the only agreeing probability measure is the uniform one, given by P(

x 1 ) = P(x 2 ) = • • • = P(x n ) = 1
n . In any other case, there is not a unique probability compatible with the assessments; in other words, a comparative probability model on the singletons is not complete, in the sense of [START_REF] De Finetti | Sul significato soggettivo della probabilità[END_REF] and [START_REF] Scott | Measurement structures and linear inequalities[END_REF], unless the associated graph has a cycle involving all the nodes. 4.2. Extraction Algorithm. Using the results of Section 3, we can propose a pseudo-algorithm to extract extreme points from a weakly-connected acyclic graph G , summarised in Algorithm 1. It uses the fact that nondecomposable top subnetworks are in correspondence with sets of strongly disconnected nodes, as we have explained in Remark 3. Graphs with cycles or that are not weakly connected can be handled by considering equivalence classes or weakly-connected sub-graphs, as explained in Section 3 (Propositions 2 and 3). Finding such weakly connected components is a well-known and easily solvable problem [Hopcroft and Tarjan , 1973]. Implementing Algorithm 1 mainly requires being able, for a given set B, to check whether elements of B are strongly disconnected and to compute H(B). An instrumental tool to do this is the matrix M corresponding to the transitive closure C (L ) ⊆ {1, . . . , n} × {1, . . . , n} of L , with M(i, j) = 1 iff (i, j) ∈ C (L ). M can be efficiently computed by applying Warshall's algorithm [START_REF] Warshall | A theorem on boolean matrices[END_REF] to the matrix L given by L(i, j) = 1 iff (i, j) ∈ L .

Once this is done, checking whether two elements x i , x j are strongly disconnected can be done in linear time. Checking that B is made of strongly disconnected elements is equivalent to check whether all pairs of elements x i , x j ∈ B are strongly disconnected, hence at most in quadratic time. As H(B) = ∪ x∈B H(x), computing H(B) is also linear. This means that the complexity of the loop going from Line 10 to 13 in Algorithm 1 is quadratic.

Algorithm 1 also tries to minimize the number of sets of nodes to check by reducing the search to top subnetworks generated by sets of strongly disconnected nodes, rather than making a naive search among all subsets B ⊆ X . However, the algorithm would still have to check, at worst, an exponential number of sets. An interesting study would be to compare Algorithm 1, which takes advantage of the particular structure of the model, with classical vertex enumeration techniques [START_REF] Avis | A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra[END_REF]] also known to be polynomial for a fixed number of vertices. 4.3. n-monotonicity. Next, we investigate in more detail the set of probabilities P(L ) from the point of view of the theory of coherent lower previsions developed by [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]. Since the set P(L ) is a closed convex set of probabilities, its lower envelope P on events, given by ( 8)

P(A) = min{P(A) : P ∈ P(L )} ∀A ⊆ X
is a coherent lower probability. As such, it can be given a behavioural interpretation in terms of acceptable betting rates. Coherent lower probabilities include as particular cases most of the imprecise probability models that we can find in the literature, such as 2monotone capacities, belief functions, or necessity measures; see [START_REF] Walley | Towards a unified theory of imprecise probability[END_REF] for more details. In particular, a coherent lower probability is 2monotone when for any A, B ⊆ X we have ( 9)

P(A ∪ B) + P(A ∩ B) ≥ P(A) + P(B).
It is called n-monotone when for any A 1 , . . . , A n ⊆ X we have that

P(∪ n i=1 A i ) ≥ ∑ / 0 =I⊆{1,...,n} (-1) |I|+1 P(∩ i∈I A i ),
and if it is n-monotone for every n, then it is called a belief function [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], and it is determined by a Möbius inverse m : 2 X → [0, 1] by means of the formula ( 10)

P(A) = ∑ B⊆A m(B) ∀A ⊆ X .
The mapping m is such that m( / 0) = 0 and ∑ E⊆X m(E) = 1, and it can be seen as a probability mass defined over subsets. The sets B for which m(B) > 0 are called the focal elements of the belief function P; when they are nested, the belief function is minimum-preserving (i.e., it satisfies P(A ∩ B) = min{P(A), P(B)} for every pair of subsets A, B), and it is called a necessity measure.

Belief functions have been shown of interest in the context of evidential reasoning, and also in connection with random sets [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]. On the other hand, 2-monotone capacities are also called convex functions or Choquet capacities of order 2 [START_REF] Choquet | Theory of capacities[END_REF][START_REF] Denneberg | Non-Additive Measure and Integral[END_REF]. When |X | ≤ 3, it was showed by [START_REF] Walley | Coherent lower (and upper) probabilities[END_REF] that a coherent lower probability on 2 X is always 2-monotone but not necessarily 3-monotone.

Interestingly, the particular coherent lower probabilities induced by a comparative probability model on the singletons are always belief functions (i.e., n-monotone for every n) when |X | = 3: Proposition 6. If |X | = 3, then the lower probability induced by a comparative probability ordering on the singletons by means of (8) is a belief function.

Proof. First of all, if the graph G associated with L is weakly connected and acyclic, there are three possibilities (except for permutations of the states):

• L = {(1, 2), (2, 3)}. From Theorem 1, we deduce that the extreme points of P(L ) are determined by the set of probability masses {(1, 0, 0), (0.5, 0.5, 0), ( 1 3 , 1 3 , 1 3 )}. Then the lower probability associated with this credal set is the belief function with Möbius inverse

m({x 1 }) = 1 3 = m({x 1 , x 2 }), m({x 1 , x 3 }) = 1 6 = m({x 1 , x 2 , x 3 }).
• L = {(1, 2), (1, 3)}. Again by Theorem 1, the extreme points of P(L ) are associated with the probability masses

(1, 0, 0), (0.5, 0.5, 0), (0.5, 0, 0.5), (

1 3 , 1 3 , 1 3
) .

Then the lower probability associated with this credal set is the belief function with Möbius inverse

m({x 1 }) = 1 3 = m({x 1 , x 2 , x 3 }), m({x 1 , x 2 }) = 1 6 = m({x 1 , x 3 }).
• L = {(1, 3), (2, 3)}. By Theorem 1, the extreme points of P(L ) are associated with the probability masses

(1, 0, 0), (0, 1, 0), ( 1 3 , 1 3 , 1 3
) .

Then the lower probability associated with this credal set is the belief function with Möbius inverse

m({x 1 , x 2 }) = 2 3 , m({x 1 , x 2 , x 3 }) = 1 3 .
On the other hand, if the graph G is acyclic but is not connected, there are two possible scenarios (again, except for permutations of the states):

• L = / 0. Then the extreme points of P(L ) are associated with the probability masses {(1, 0, 0), (0, 1, 0), (0, 0, 1)} .

The lower probability associated with this credal set is the belief function with Möbius inverse

m({x 1 , x 2 , x 3 }) = 1. • L = {(1, 2)}.
Then the extreme points of P(L ) are associated with the probability masses {(1, 0, 0), (0.5, 0.5, 0), (0, 0, 1)} .

Then the lower probability associated with this credal set is the belief function with Möbius inverse m({x 1 , x 3 }) = 0.5, m({x 1 , x 2 , x 3 }) = 0.5.

Finally, when the graph has cycles, there can be four possible cases:

• L = {(1, 2), (2, 3), (3, 1)}.
Then there is only one compatible probability measure (that is in particular a belief function): the one determined by P(x 1 ) = P(x 2 ) = P(x 3 ) = 1 3 . • L = {(1, 2), (2, 1)}. In that case the extreme points of P(L ) are associated with the probability masses {(0.5, 0.5, 0), (0, 0, 1)} .

Then the lower probability associated with this credal set is the belief function with Möbius inverse m({x 1 , x 3 }) = m({x 2 , x 3 }) = 0.5.

• L = {(1, 2), (2, 1), (2, 3)}. Then the extreme points of P(L ) are associated with the probability masses (0.5, 0.5, 0), (

1 3 , 1 3 , 1 3
) .

Then the lower probability associated with this credal set is the belief function with Möbius inverse

m({x 1 }) = m({x 2 }) = 1 3 , m({x 1 , x 3 }) = m({x 2 , x 3 }) = 1 6 .
• L = {(1, 2), (2, 1), (3, 2)}. Then the extreme points of P(L ) are associated with the probability masses

(0, 0, 1), ( 1 3 , 1 3 , 1 3
) .

Then the lower probability associated with this credal set is the belief function with Möbius inverse

m({x 3 }) = 1 3 , m({x 1 , x 3 }) = m({x 2 , x 3 }) = 1 3 .
Note that the lower probability determined by ( 8) need not be a necessity measure: as we can see in the proof of Proposition 6, in not all cases the focal elements of the belief function are nested.

Next we show that Proposition 6 does not extend to the case when |X | ≥ 4, because the coherent lower probabilities induced by comparative probability models need not even be 2-monotone.

Example 6. Consider the space X = {x 1 , x 2 , x 3 , x 4 } and the assessments L = {(1, 2), (1, 3), (2, 4), (3, 4)} represented by Figure 4.

x 1 x 2 x 4 x 3 FIGURE 4. Graph G of Example 6
From Theorem 1, the extreme points of P(L ) are the probability measures determined by the probability masses

( 1 4 , 1 4 , 1 4 , 1 4 ), ( 1 2 , 1 2 , 0, 0), ( 1 2 , 0, 1 2 , 0), ( 1 3 , 1 3 , 1 3 , 0), (1, 0, 0, 0) ;
as a consequence, if we consider the events A = {x 1 , x 3 } and B = {x 1 , x 4 }, we see that

P(A ∪ B) + P(A ∩ B) = 1 /2 + 1 /4 < P(A) + P(B) = 1 /2 + 1 /3.
Hence, P violates the 2-monotonicity condition.

This implies that belief functions, which are in particular 2-monotone, are not expressive enough to represent comparative probability models.

On the other hand, from a convex set of probability measures we can also determine lower and upper expectation functionals. Similarly to Eq. ( 8), the real-valued functional P given by ( 11)

P( f ) = min{P( f ) : P ∈ P(L )}
for any function f : X → R is called a coherent lower prevision. Here, we are also using P to denote the expectation functional associated with the probability measure P, given by P( f

) = ∑ x∈X f (x)p(x).
Coherent lower previsions can also be given a behavioural interpretation, in terms of acceptable buying prices. Within that context, the coherent lower prevision P defined above corresponds to the natural extension of the assessment that the functions {I x i -I x j : (i, j) ∈ L } are almost-desirable; see Walley [1991, Section 3.7] for more details on the correspondence with desirability.

Interestingly, although a coherent lower prevision always determines a unique coherent lower probability (its restriction to events), a coherent lower probability may have more than one extension to a coherent lower prevision, and in this sense the latter can be seen as a more expressive model. This is the reason why lower previsions are often preferred to lower probabilities. Next, we investigate in more detail the properties of the coherent lower previsions induced by a comparative probability model.

Similarly to Eq. ( 9), a coherent lower prevision is called 2-monotone when for any f , g : X → R,

P( f ∨ g) + P( f ∧ g) ≥ P( f ) + P(g),
where ∨ denotes the point-wise maximum and ∧ denotes the point-wise minimum. 2-monotone lower previsions have been studied in detail by de [START_REF] De Cooman | n-Monotone exact functionals[END_REF] and [START_REF] Walley | Coherent lower (and upper) probabilities[END_REF]. In particular, it was established by de Cooman et al. [2008, Theorem 15] that the property of 2-monotonicity is equivalent to comonotone additivity, which means that

P( f + g) = P( f ) + P(g) ∀ f , g comonotone,
and where f and g are said to be comonotone when for every x i , x j ∈ X it holds that

( f (x i ) -f (x j ))(g(x i ) -g(x j )) ≥ 0.
2-monotone lower previsions are interesting, because, unlike general coherent lower previsions, they can be calculated as the Choquet integral with respect to the lower probability that is their restriction to events (hence easing computations). However, we can prove that if |X | ≥ 3 the coherent lower prevision associated with a comparative probability is not 2-monotone except for trivial cases:

Theorem 7. Consider a space X with |X | ≥ 3, and let L be a number of probability comparisons on the elements of X . Let P be the coherent lower prevision determined by (11). Then:

P 2-monotone ⇔ either (i)L = / 0 or (ii) (i, j) ∈ C (L ) ∀i, j ∈ {1, . . . , n}.
Proof. First of all, if L = / 0, then the lower prevision it induces is the vacuous one, given by P( f ) = min f for every gamble f , which is 2-monotone. On the other hand, if (i, j) ∈ C (L ) for every i, j ∈ {1, . . . , n} then the only element of P(L ) is the uniform probability distribution, associated with the probability mass p(

x 1 ) = p(x 2 ) = • • • = p(x n ) = 1 n , which is also 2- monotone.
Let us show that in any other case P is not 2-monotone. Assume exabsurdo that it is. Then by de [START_REF] De Cooman | n-Monotone exact functionals[END_REF] it corresponds to the Choquet integral with respect to its restriction to events, which is a 2monotone lower probability. Let Q denote this lower probability. Given (i, j) in the non-empty set L , it should be 0 ≤ P(I x i -I x j ) = (C)

I x i -I x j dQ = 1Q({x i }) + 1Q(X \ {x j }) -1 = Q({x i }) -Q({x j }),
where Q is the upper probability that is conjugate to Q, and corresponds to the upper envelope of the set P(L ). Now, it follows from Theorem 1 that

Q({x i }) = min{P B ({x i }) : B non-decomposable top subnetwork}.
This means in particular that Q({x i }) ∈ {0, 1 j : j ∈ 1, ..., |X |}. As a consequence, if there is a top subnetwork B that does not include x i , neither does any of the non-decomposable top subnetworks it includes, and we obtain that Q({x i }) = P B ({x i }) = 0. In particular, this happens when G is not weakly connected: then given x k in a different weakly connected component of G than x i , we have that

Q({x i }) ≤ P H(x k ) ({x i }) = 0.
On the other hand, if G is weakly connected and x i belongs to all the nondecomposable top subnetworks, then

Q({x i }) = 1
|B| , where B is the largest non-decomposable top subnetwork. This is given by X : it is obviously a top subnetwork (generated by itself) and it is non-decomposable because we are assuming that the graph G is weakly connected. Thus, in that case

Q({x i }) = P X ({x i }) = 1 n . P(x 1 ) P(x 2 ) P(x 3 ) FIGURE 5. Remark 5 illustration for L = {(3, 1), (2, 1)} We conclude that Q({x i }) = 1 n if (i, k) ∈ C (L ) ∀k ∈ {1, . . . , n} 0 otherwise. Similarly, Q({x j }) = P H(x j ) ({x j }) = 1 |H(x j )| ≥ 1
n , and from this we deduce that a necessary condition for the 2-monotonicity of P is that

(12) (i, j) ∈ L ⇒ (i, k), (k, j) ∈ C (L ) ∀k ∈ {1, . . . , n},
taking into account that we should have H(x j ) = X and that x i is a predecessor of any node in G in order to get Q({x i }) = Q({x j }) = 1 n . Let us now use this condition to show that if L is non-empty and P(L ) has more than one element, then its associated lower prevision is not 2monotone. Take (i, j) ∈ L . We reason ex-absurdo. Assume that the associated lower prevision P is 2-monotone, and that therefore Eq. ( 12) is satisfied. Then it must be C (L ) ⊇ {( , j), ( , k) : , k ∈ {1, . . . , n} \ { j}}.

On the other hand, for any k = j it must be ( j, k) / ∈ C (L ), since otherwise we would obtain C (L ) = {( , k) : , k ∈ {1, . . . , n}} and P(L ) would have only one element, which is ruled out by assumption. From this we can conclude that ( 13)

C (L ) = {( , j), ( , k) : , k ∈ {1, . . . , n} \ { j}}.
But this is incompatible with Eq. ( 12): given k = i, j, the fact that (i, k) ∈ C (L ) implies that there is some = k such that ( , k) ∈ L , and then if Eq. ( 12) held we should have ( j, k) ∈ C (L ), a contradiction with Eq. ( 13). We conclude that Eq. ( 12) cannot hold and as a consequence that P is not 2-monotone.

Remark 5. Using a geometrical approach, we can easily see that the coherent lower prevision associated with a comparative probability model is not 2-monotone when X has three elements and G is weakly connected and acyclic5 : P will be 2-monotone if and only if its associated credal set {P : P ≥ P} coincides with the one determined by the restriction of P to events, i.e., if it is the subset of the 2-unit simplex determined by the restrictions P(A) ∈ [P(A), P(A)] for every A ⊆ X . Then it can be checked that any of these restrictions is parallel to one of the sides of the simplex, while the restrictions of the comparative probability model are of the type p(x i )p(x j ) ≥ 0, and correspond to a bisector; and the intersections of the subsets of the simplex determined by these bisectors will not determine a credal set whose sides are parallel to the sides of the simplex, except in the two particular cases considered in Theorem 7: when the credal set is equal to P(L ) (meaning that L = / 0) or when P(L ) has only one element (meaning that C (L ) includes {(1, 2), (2, 3), (3, 1)}). These two cases cannot hold when the graph G is weakly connected and acyclic. A similar reasoning may be done on higher dimensions. Figure 5 provides an illustration for the assessments L = {(3, 1), (2, 1)}, where it is easy to see that the bisector lines delimiting of the probability set are not parallel to the triangle sides.

We refer to [START_REF] Fujishige | Submodular functions and optimization[END_REF][START_REF] Kroupa | Geometry of possibility measures on finite sets[END_REF][START_REF] Shapley | Cores of convex games[END_REF] for more information on the geometric approach to credal sets.

Conditioning.

A classical operation when dealing with uncertainty is that of conditioning. Here we will study the problem of computing lower conditional probabilities P(A|B) from the credal set P(L ). Out of the many possible notions we can consider in this case, we think that the most intuitive under the robust Bayesian interpretation we are considering in this paper is that of regular extension [Walley , 1991, Appendix J], that produces ( 14)

P(A|B) = inf P∈P(L ) {P(A|B) : P(B) > 0},
where P(A|B) is obtained from P by means of Bayes' rule. We refer to [de Campos et al. , 1990, Fagin andHalpern , 1991b] and [START_REF] Jaffray | Bayesian updating and belief functions[END_REF] for some works on this conditioning rule.

In order to apply this definition, we need the existence of some probability measure P in P(L ) such that P(B) > 0 (or, in other words, that the upper probability P(B) is positive); but this is no restriction in the case of comparative probabilities, because there will always be an extreme point P of P(L ) for which P(B) > 0: it suffices to consider P H(x i ) with x i ∈ B. On the contrary, the lower probability P(B) will be positive if and only if B intersects all top subnetworks.

To reach the conditional lower probability P(A|B) given by Eq. ( 14), we need to find the extreme point for which P(B) is positive and the fraction P(A∩B) /P(B) minimal. Provided G is acyclic (graphs with cycles can be dealt with by considering equivalence classes, as described at the end of Section 3), this can be done easily by the procedure described in Algorithm 2. Finding the value ( 14) comes down to finding the non-decomposable top subnetwork D ∈ H minimizing the value (15)

P D (A ∩ B) P D (B) = |D ∩ B ∩ A| |D ∩ B| .
Taking into account Remark 3, it holds that D = H(C), for some set C of strongly disconnected nodes in G . Note that it is sufficient to focus on sets

C such that C ⊆ B \ A or C ⊆ B ∩ A: • as H(C) ∩ B = H(H(C) ∩ B) ∩ B, it is sufficient to focus on sets C ⊆ B; • for any set C such that C ∩ (B \ A) = / 0 and C ∩ B ∩ A = / 0, we can decrease the ratio |H(C)∩B∩A| /|H(C)∩B| by picking an element x ∈ C ∩ B ∩ A and considering the set C = (C \ {x}) ∪ (H({x}) \ {x}). Note that C = /
0 because it includes the set C \ {x}, which is itself nonempty because it must have a non-empty intersection with B \ A. Taking into account that x is strongly disconnected from C \ {x}, we obtain that H(C ) = H(C) \ {x}. Then since x ∈ A ∩ B, both the numerator and denominator are decreased by one, meaning that the ratio (15) decreases. This means that focusing on subsets of B \ A and of B ∩ A is sufficient to retrieve the solution.

Algorithm 2: Conditional Probability computation

Input: Set L of comparisons Output: Lower conditional probability P(A|B)

with A ⊂ B 1 Cond ← 1 ; 2 foreach Non-empty set C ⊆ B \ A or C ⊆ A ∩ B do 3 Value ← |H(C)∩(A∩B)| /|H(C)∩B| ; 4 if Value < Cond then Cond← Value ; 5 Return Cond ;
Next, we will characterize the conditional set ( 16)

P B (L ) = {P(•|B) : P ∈ P(L ), P(B) > 0}
obtained by the regular extension. Any of the elements of the set P B (L ) can equivalently be seen as a probability measure on P(B). Using this correspondence, we shall proceed to show that P B (L ) is again induced by a comparative probability. Given a set L of comparisons, we will denote by C (G ) the graph associated with its transitive closure C (L ). We will denote by L B ⊆ B × B the relation obtained from C (L ) by ( 17)

L B = {(i, j) : (i, j) ∈ C (L ), x i , x j ∈ B}, that is, L B is the relation C (L ) restricted to elements in B.
We will denote by G B the graph corresponding to L B . Figure 6 shows the graph obtained by transitive closure for Example 1, as well as G {x 1 ,x 2 ,x 5 } .

x 1

x 3 x 4 x 2 x 5 x 1 x 2 x 5 FIGURE 6. Graphs C (G ) and G {x 1 ,x 2 ,x 5 } obtained from Example 1
Theorem 8. Consider a space X and let L be a set of probability comparisons. Consider a conditioning event B, and let L B be given by Eq. (17). Then P B (L ) = P(L B ),

where P(L B ) is the credal set associated with L B by (1) and P B (L ) is given by Eq. (16).

Proof. Let us show the double inclusion between these two sets. On the one hand, given x i , x j ∈ B such that (i, j) ∈ C (L ), it follows from transitivity that P(x i ) ≥ P(x j ) for every P ∈ P(L ). In particular, if P ∈ P(L ) satisfies P(B) > 0 then P(•|B) will satisfy

P({x i }|B) = P({x i }) P(B) ≥ P({x j }) P(B) = P({x j }|B) ∀x i , x j ∈ B s.t. (i, j) ∈ C (L ),
and since P(B|B) = 1 we deduce that P(•|B) belongs to P(L B ). Thus, P B (L ) ⊆ P(L B ).

Conversely, consider P ∈ P(L B ) and let p : X → [0, 1] be given by p (x i ) := max{P({x j }) :

x j ∈ B, (i, j) ∈ C (L )} if x i ∈ H(B) 0 otherwise.
This function satisfies by construction that p (x i ) ≥ p (x j ) for every (i, j) ∈ L . If we now consider the probability measure Q given by

Q(C) = ∑ x i ∈C p (x i ) ∑ x j ∈X p (x j )
∀C ⊆ X , it follows from the reasoning above that Q ∈ P(L ). Moreover, by construction we have that Q(•|B) = P. Thus, P(L B ) ⊆ P B (L ) and from this we deduce that the two sets are equal.

Theorem 8 tells us that computing the conditional lower prevision obtained through regular extension is easy for the specific model studied here. 4.5. Multiple source merging. When multiple sources provide different comparisons, for instance when two different experts provide assessments L 1 and L 2 , it becomes necessary to merge them in a single representation. The two most common ways are the conjunction and disjunction rules, which respectively come down to computing P(L 1 ) ∩ P(L 2 ) and CH(P(L 1 ) ∪ P(L 2 )) where CH denotes the convex hull (note that the disjunction usually produces non-convex probability sets). Our next two results demonstrate that simple operations on L 1 and L 2 can provide exact or approximate results of these operations.

Proposition 9. The conjunctively merged set P(L 1 ) ∩ P(L 2 ) is such that

P(L 1 ) ∩ P(L 2 ) = P(L 1 ∪ L 2 ) with L 1 ∪ L 2 = {(i, j) : (i, j) ∈ L 1 or (i, j) ∈ L 2 }
Proof. It is sufficient to note that L 1 ∪ L 2 is the set of all constraints inducing P(L 1 ) and P(L 2 ).

For the disjunction, the same strategy only gives us an approximation.

Proposition 10. The disjunctively merged set CH(P(L 1 ) ∪ P(L 2 )) is such that

(18) CH(P(L 1 ) ∪ P(L 2 )) ⊆ P(C (L 1 ) ∩ C (L 2 )).
Proof. It suffices to note that P(

L i ) = P(C (L i )) ⊆ P(C (L 1 ) ∩ C (L 2 )) for i = 1, 2.
The inclusion in Eq. ( 18) can be strict, as our next example shows. In fact, CH(P(L 1 ) ∪ P(L 2 )) will usually not be representable by means of comparative probabilities.

Example 7. Consider the possibility space X = {x 1 , x 2 , x 3 } and the assessments L 1 = {(1, 2), (2, 3)} and L 2 = {(3, 2), (2, 1)}. We have C (L 1 ) ∩ C (L 2 ) = / 0, hence the induced probability set P(C (L 1 ) ∩ C (L 2 )) is the set of all possible probability masses, while CH(P(L 1 ) ∪ P(L 2 )) does not include the Dirac measure P({x 2 }) = 1 (that is neither an extreme point of P(L 1 ) nor of P(L 2 )).

It is interesting to note that, from Zaffalon and Miranda [2003, Theorem 6] the union of two credal sets P(L 1 ) and P(L 2 ) is again a convex set if and only if the lower envelope of the intersection P(L 1 ) ∩ P(L 2 ) equals the maximum of the lower envelopes of P(L 1 ) and P(L 2 ).

EXAMPLES AND EXTENSIONS

In this section, we propose some particular examples of situations where singleton comparisons can be used, and discuss some possible extensions. 5.1. Modal and least probable values. An immediate example is the case where we know only the modal value of the underlying probability distribution. In this case, if x i is the modal value, the set of one-to-one comparisons is given by L = {(i, j) : j ∈ {1, . . . , n}, j = i} and the corresponding graph is illustrated by Figure 3. Note that if an expert provides a set M of most probable values, the corresponding comparative probability model would be given by L = {(i, j) :

x i ∈ M, x j ∈ X \ M}.
Another example is when a least probable value is given, for example x i , in which case L = {( j, i) : j ∈ {1, . . . , n}, j = i} and the number of extreme points is |X | (the uniform generated by H(x i ) and the Dirac measure on other points). See Figure 7 for an illustration. In the case where the known least probable singletons belong to a set M, the corresponding model is

L = {( j, i) : x i ∈ M, x j ∈ X \ M}. x 1 x 2 x 3 x 4 x 5 FIGURE 7
. Graph G for x 1 =least probable value 5.2. Imprecise mass functions. Comparative probability models can also be related to the work on imprecise mass functions discussed for example by [START_REF] Augustin | Generalized basic probability assignments[END_REF] and [START_REF] Denoeux | Reasoning with imprecise belief structures[END_REF].

Recall that a belief function P on the power set of X is uniquely determined by its associated Möbius inverse m, by means of Eq. ( 10). The Möbius inverse m(A) of a set A represents the weight of the available evidence supporting that the outcome of the experiment belongs to E. It holds that ∑ A⊆X m(A) = 1, so we may regard m as the probability mass of some probability measure on 2 2 X .

We can then use our results to build imprecise probability masses. If we have assessments of the type m(A i ) ≥ m(A j ), we may consider the set of functions compatible with these assessments. This is a convex set (bearing on subsets of X ) whose extreme points can be determined by means of Theorem 1. By means of Eq. ( 10), each of these extreme points is the Möbius inverse of some belief function, that in turn is equivalent to a convex set of probability measures on 2 X . Note that this convex set of masses also induces a convex set of probabilities. To see that, simply note that a convex set of convex sets is convex, and that each Möbius inverse corresponds to a convex set of probabilities (we refer to [START_REF] Augustin | Generalized basic probability assignments[END_REF] for further details about convex sets of Möbius inverses).

Let us illustrate this idea with two examples. Inner/outer measures. [Fagin and Halpern , 1991a] The situation above can arise when X is partitioned into n sets A 1 , . . . , A n and where a probability value P(A i ) is associated with each set A i . Practical cases where this partitioning may occur include continuous variables discretized in (multivariate) histograms, or cases where some grouping of cases makes sense.

The assessments P(A i ), i = 1, . . . , n induce a set of probabilities (whose lower and upper envelopes are called inner/outer measures) on the power set of X that can be described by m(A i ) = P(A i ): the set of probabilities that dominate the belief function determined by the Möbius inverse m on the power set of {A 1 , . . . , A n }. Indeed, it can be checked that the lower and upper envelopes of this set correspond to the inner and outer measures determined by the belief function.

In this framework, making comparative statements between the probabilities P(A i ) of the elements of the discretized space comes down to making comparative statements between the masses m(A i ), and the set of extreme masses can then be derived using our results.

Example 8. Let X = {x 1 , . . . , x 5 } with the partition

A 1 = {x 1 , x 5 }, A 2 = {x 2 } and A 3 = {x 3 , x 4 }. Then the statements m(A 3 ) ≥ m(A 2 ), m(A 3 ) ≥ m(A 1 ) induce the set M with the following extreme points m B A 1 A 2 A 3 {A 3 } 0 0 1 {A 1 , A 3 } 1 /2 0 1 /2 {A 2 , A 3 } 0 1 /2 1 /2 {A 1 , A 2 , A 3 } 1 /3 1 /3 1 /3
Note that, in the case where the partition counts n elements and is such that A i = {x i }, we retrieve the comparative probabilities studied in the previous sections. The results of Section 4.3 and Example 6 then show that, in general, a convex set of Möbius inverses will not induce a belief function (because it will not induce in general a 2-monotone set function, as Example 6 shows, and a belief function is n-monotone for every n). Possibility measures. A second example is the case of possibility measures. A possibility measure is the upper probability that is conjugate to a necessity measure. It is thus induced by a Möbius inverse that gives positive weights only to a collection of nested sets. Without loss of generality, we can consider that these sets are A i = {x 1 , . . . , x i } and that m(A) > 0 only if A = A i for some i.

Such a model may be derived by ordering elements from the most plausible (x 1 ) to the least plausible (x n ) and then constructing sets A i . However, in practice, specifying possibility values for each element (which is equivalent to specifying the values m(A i )) can be difficult. To avoid this issue, we can use the previous results to get a set M of Möbius inverses. In this specific case, the obtained model can still be represented by a possibility measure, as the supremum of possibility measures is still a possibility measure (note that possibility measures correspond to upper envelopes of a set of probability measures, instead of the lower envelopes we have considered throughout).

Imagine for instance that an expert is asked to provide such a ranking of plausible values, and is then asked about his own confidence about this ranking. If the expert is quite confident, it seems fair to conclude that he would give more weight to the precise information m(A 1 ) than to more imprecise ones. In practice, we can translate this information by m(A 1 ) ≥ . . . ≥ m(A n ), from which it is easy to extract extreme points. Sets of possibility measures have also been recently investigated from a qualitative perspective by [START_REF] Dubois | Qualitative Capacities as Imprecise Possibilities[END_REF].

Numerical modelling of partial preferences.

A problem where our results may prove useful is the numerical handling of partial preferences; these arise often in multi-criteria decision making [START_REF] Boutilier | Cp-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF][START_REF] Labreuche | On the robustness for the Choquet integral[END_REF] or in preference learning [START_REF] Fürnkranz | Preference learning[END_REF]Hüllermeier , 2010, Lu and[START_REF] Lu | Learning mallows models with pairwise preferences[END_REF].

Consider a set X = {x 1 , . . . , x n } of n different items, and a binary relation L over them defining a preorder that can be represented through a directed graph G . Our results allow to provide a numerical representation of such a preorder as a set of extreme points, or in terms of a set of complete pre-orders compatible with the preorder L : each element within P(L ) provides a pre-order over the elements of X that is compatible with L .

This also provides us with a straightforward method to sample linear extensions of L (that is, linear orders compatible with L ): if p 1 , . . . , p E are the extreme points of P(L ), a sampling of E positive weights w 1 , . . . , w E summing up to one (by sampling a uniform Dirichlet distribution, for instance) provides a mass p = ∑ E i=1 w i p i corresponding to a linear extension. This view of our results can also be linked to the d-permutaedron, that is the closed convex hull of all d-dimensional permutation vectors, as our results allow to characterize the set of complete preorders consistent with L by means of extreme points in the unit simplex. Exploring such links would bring us closer to results related to binary choices or random utilities [START_REF] Zhang | Binary choice, subset choice, random utility, and ranking: A unified perspective using the permutahedron[END_REF], the latter concerning probabilities over ranks, while our results focus on ranks over singleton probabilities. 5.4. Extension to general comparative probability models: some comments. The most important extension of our work would be to consider arbitrary comparative probability models, where we allow for comparisons between any pair of events (the case of partitions is treated in Section 5.2), that is to allow any comparison P(A) ≥ P(B) with A, B ⊆ X . These are the models studied extensively by Koopman [1940a], [START_REF] Suppes | The measurement of belief[END_REF] and [START_REF] Walley | Varieties of modal (classificatory) and comparative probability[END_REF], amongst others. Most of the axiomatic work is based on de Finetti [1931].

When considering comparative probability models, we can assume that the sets A, B we compare are disjoint, since the assessments P(A) ≥ P(B) and P(A \ B) ≥ P(B \ A) are equivalent by additivity of P. However, the existence of a probability compatible with the assessments is no longer trivial, and therefore the associated set P(L ) may be empty [Kraft et al. , 1959, Section 4]. Using the terminology from [START_REF] Kaplan | Joint orders in comparative probability[END_REF], this means that it does not necessarily hold that the comparative ordering is additive. 6When P(L ) is non-empty, then it is a closed convex set that is characterized by its finite number of extreme points. However, as the next example shows, we cannot expect the extreme points of such assessments to be as simple as the extreme points generated by the comparison of the probabilities of the states. In particular, the extreme points of the associated credal sets will not be necessarily related to uniform probability distributions over some subsets, and finding an easy graphical representation from which they could be extracted seems hard.

Example 9. Consider the space X = {x 1 , x 2 , x 3 } and the following assessments:

• P({x 2 }) ≥ P({x 1 })

• P({x 1 , x 2 }) ≥ P({x 3 }) (or, equivalently, P({x 3 }) ≤ 1 /2). And let P be the credal set of the probabilities satisfying these assessments. The extreme points of P are summarised in Table 4. p x 1 x 2 x 3 0 1 0 1 /2 1 /2 0 1 /4 1 /4 1 /2 0 1 /2 1 /2 The set of probabilities P(L ) is uniquely determined by the lower prevision P it generates by means of Eq. ( 11). However, Theorem 7 implies that this lower prevision derived from P(L ) will not be 2-monotone in general, and as consequence it will not correspond to the Choquet integral with respect to its restriction to events. In other words, the lower probability that we can derive by means of the formula Q(A) := min{P(A) : P ∈ P(L )} will only allow us to provide in general an outer approximation of the set P(L ): there are probability measures that do not belong to P(L ) but dominate nonetheless Q.

Another (quite rough) outer approximation is to consider the set of comparative probability assessments on the singletons that are implied by L , and to characterise the associated credal set by means of our results in this paper.

CONCLUSIONS

Comparative probabilities are a useful approach to modelling uncertain information about a probability measure, especially when the available information is of a qualitative nature. However, most works in the literature about these models have focused on axiomatising those comparative probability models that can be associated with a set of probability measures. In this paper, we have focused on the particular case where the comparisons are established between the probabilities of the singletons, and we have deepened the link between comparative probability models and imprecise probabilities, by: (a) characterising the structure of the set of probability measures associated with a comparative probability model, and (b) studying the properties of the lower probability induced by this set. We have shown that this lower probability may not be 2-monotone, from which it follows that 2-monotone capacities (and in particular belief functions, or possibility measures) are not expressive enough to be able to deal with this type of qualitative information.

We have characterised the extreme points of the credal set associated with a comparative probability model, and shown that the number of extreme points can be as high as two to the power of |X | -1. This is comparable to the maximal number of extreme points of credal sets induced by possibility measures, and smaller than those induced by 2-monotone capacities or belief functions.

We have also suggested some practical situations where comparative probabilities can be useful (elicitation of modal or least probable values, imprecise probability masses, . . . ). However, this model remains quite simple and of limited expressiveness, and it would be desirable to study to which extent the results presented in this paper can help to solve the same problem applied to general comparisons between disjoint events (illustrated in Section 5.4). Some useful work in this sense may be done by means of Walley's work on n-coherence [Walley , 1991, Appendix B]. In particular, it would be interesting to see if our results help to characterise weighted comparative models on the singletons (that is, assessments of the type "the probability of x i is at least twice that of x j ", for instance), or probability ratios [Walley , 1991, Section 4.6.2], [START_REF] Piatti | Building knowledge-based expert systems by credal networks: a tutorial[END_REF]. Although it is not difficult to see that in that case the extreme points may not correspond to uniform distributions and that the set of agreeing probabilities may even be empty, we think that weighted graphs, and the arguments provided at the end of Section 3, may prove useful here.

Another important open problem would be to provide algorithms for the computation of the lower prevision induced by a comparative probability model, and to study in detail the applications of these results in fields such as qualitative decision making.

One interesting issue is to characterise the differences between strict preferences, i.e., p(x i ) > p(x j ) over non-strict ones in terms of uncertainty representation. This would require a richer language than lower previsions, such as for instance sets of desirable gambles [Walley , 1991, Section 3.7], since, as we have mentioned in Section 2, both strict and non-strict preferences determine the same lower prevision when G is acyclic. In this sense, it would also be interesting to investigate the connections between comparative probability models and the choice functions considered in [START_REF] Seidenfeld | Coherent choice functions under uncertainty[END_REF], which seem better suited to deal with open sets of probabilities.

Finally, a more practical perspective is to run numerical experiments to check whether Algorithm 1 is competitive when compared to classical algorithms used to extract extreme points of polytopes. This could be done with the Improb Python Library (https://pypi.python.org/pypi/improb/) or directly with the lrs package ( http://cgm.cs.mcgill.ca/ ~avis/C/lrslib/lrslib.html).

TABLE 4 .

 4 Extreme points of Example 9.

Proof. First of all, note that for any C ⊆ X whose associated graph is a top subnetwork of G , it holds thatC = ∪ x i ∈C [x i ] R .For any B ⊆ X , we can defineexp(B) = ∪ x i ∈B [x i ] R ⊆ X .Then the graph associated with a set B ⊆ X is a weakly connected topsubnetwork of G if and only if the graph associated with exp(B) ⊆ X is a weakly connected top-subnetwork of G . Conversely, if C ⊆ X determines a weakly connected top subnetwork in G , then B := C ∩ X determines a weakly connected top subnetwork in G , and moreover exp(B) = C.

Two nodes in the graph are strongly disconnected if there is no directed path between them.

This is an instance of a naive tree.

We thank Erik Quaeghebeur for pointing this out to us.

The notion of additivity is referred to as the existence of an almost agreeing probability by[START_REF] Fishburn | The axioms of subjective probability[END_REF].

ACKNOWLEDGEMENTS

The research in this paper has been supported by project MTM2010-17844 and has been carried in the framework of the Labex MS2T, project ANR-11-IDEX-0004-02. We would like to thank Marco Zaffalon for making us aware of the work carried out by Gulordava [2010], as well as for other useful suggestions. We also thank Erik Quaeghebeur and Alessandro Antonucci for some stimulating discussions, and the anonymous reviewers and the editor for their careful reading of several versions of the paper and their useful comments.