Felipe Aguirre
email: felipeam86@gmail.com

Sébastien Destercke
email: sebastien.destercke@hds.utc.fr

Didier Dubois
email: dubois@irit.fr

Mohamed Sallak
email: mohamed.sallak@hds.utc.fr

Christelle Jacob
email: jacob.christelle.11@gmail.com

Inclusion-exclusion principle for belief functions

Keywords: belief function, inclusion-exclusion principle, reliability analysis, boolean formula, independence

published or not. The documents may come

Introduction

Probability theory is the most well-known approach to model uncertainty. However, even when the existence of a single probability measure is assumed, it often happens that its distribution is only partially known. This is particularly the case in the presence of severe uncertainty (few samples, imprecise or unreliable data, etc.) or when subjective beliefs are elicited (e.g., from experts). Some authors use a selection principle that brings us back to a precise distribution (e.g., maximum entropy [START_REF] Jaynes | Probability Theory: The Logic of Science[END_REF]). But other ones [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF][START_REF] Shafer | A mathematical Theory of Evidence[END_REF][START_REF] Dubois | Possibility Theory: An Approach to Computerized Processing of Uncertainty[END_REF] have argued that in some situations involving imprecision or incompleteness, uncertainty cannot be modelled faithfully by a single probability measure. The same authors have advocated the need for frameworks accommodating imprecision, their efforts resulting in different frameworks such as possibility theory [START_REF] Dubois | Possibility Theory: An Approach to Computerized Processing of Uncertainty[END_REF], belief functions [START_REF] Shafer | A mathematical Theory of Evidence[END_REF], imprecise probabilities [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF], info-gap theory [START_REF] Ben-Haim | Info-gap Decision Theory: Decisions Under Severe Uncertainty[END_REF], etc. that are formally connected [START_REF] Walley | Measures of uncertainty in expert systems[END_REF][START_REF] Dubois | Formal representations of uncertainty[END_REF]. Regardless of interpretive issues, the formal setting of belief functions offers a good compromise between expressiveness and calculability, as it is more general than probability theory, yet in many cases remains more tractable than imprecise probability approaches.

Nevertheless using belief functions is often more computationally demanding than using probabilities. Indeed, its higher level of generality prevents the use of some properties, valid in probability theory, that help simplify calculations. This is the case, for instance, for the well known and useful inclusion-exclusion principle (also known as the Sylvester-Poincaré equality).

Given a space X , a probability measure P over this space and any collection A n = {A 1 , . . . , A n |A i ⊆ X } of measurable subsets of X , the inclusion-exclusion principle states that

P(∪ n i=1 A i ) = ∑ I ⊆A n (-1) |I |+1 P(∩ A∈I A) (1)
where |I | is the cardinality of I . This equality allows us to easily compute the probability of ∪ n i=1 A i , when the events A i are stochastically independent, or when their intersections are disjoint. This principle has been applied to numerous problems, including the evaluation of the reliability of complex systems. It does not hold for belief functions, and only an inequality remains. However, it is useful to investigate whether or not an equality can be restored for specific families A n of events, in particular the ones encountered in applications to diagnosis and reliability. The main contribution of this paper is to give a positive answer to this question and to provide conditions characterizing the families of events for which the inclusion-exclusion principle still holds in the belief function setting.

This paper is organized as follows. First, Section 2 provides sufficient and necessary conditions under which the inclusion-exclusion principle holds for belief functions in general spaces; it is explained why the question may be more difficult for the conjugate plausibility functions. Section 3 then studies how the results apply to the practically interesting case where events A i and focal elements are Cartesian products in a multidimensional space. Section 4 investigates the particular case of binary spaces, and considers the calculation of the degree of belief and plausibility of a Boolean formula expressed in Disjunctive Normal Form (DNF). Section 5 then shows that specific events described by means of monotone functions over a Cartesian product of totally ordered discrete spaces meet the conditions for the inclusion-exclusion principle to hold. Section 6 is devoted to illustrative applications of the preceding results to the field of reliability analysis (both for the binary and non-binary cases), in which the use of belief functions is natural and the need for efficient computation schemes is an important issue. Finally, Section 7 compares our results with those obtained when assuming stochastic independence between ill-known probabilities, displaying those cases for which these results coincide and those for which they disagree.

This work extends the results concerning the computation of uncertainty bounds within the belief function framework previously presented in [START_REF] Jacob | Evaluating the uncertainty of a Boolean formula with belief functions[END_REF][START_REF] Aguirre | Inclusion/exclusion principle for belief functions[END_REF]. In particular, we provide full proofs as well as additional examples. We also discuss the application of the inclusion/exclusion principle to plausibilities, as well as a comparison of our approach with other types of independence notions proposed for imprecise probabilities (two issues not tackled in [START_REF] Jacob | Evaluating the uncertainty of a Boolean formula with belief functions[END_REF][START_REF] Aguirre | Inclusion/exclusion principle for belief functions[END_REF]).

General Additivity Conditions for Belief Functions

After introducing some notation and the basics of belief functions (Section 2.1), we explore in Section 2.2 general conditions for families of subsets for which the inclusion-exclusion principle holds for belief functions. We then look more closely at the specific case where the focal elements of belief functions are Cartesian products of subsets. Readers not interested in technical details and familiar with belief functions may directly move to Section 3.

Setting

A mass distribution [START_REF] Shafer | A mathematical Theory of Evidence[END_REF] defined on a (finite) space X is a mapping m : 2 X → [0, 1] from the power set of X to the unit interval such that m( / 0) = 0 and ∑ E⊆X m(E) = 1. A set E that receives a strictly positive mass is called a focal element, and the set of focal elements of m is denoted by F m . The mass function m can be seen as a probability distribution over sets, in this sense it captures both probabilities and sets: any probability p can be modelled by a mass m such that m({x}) = p(x) and any set E can be modelled by the mass m(E) = 1. In the setting of belief functions, a focal element is understood as a piece of incomplete information of the form x ∈ E for some parameter x of interest. Then m(E) can be understood as the probability that all that is known about x is that x ∈ E; in other words, m(E) is a probability mass that should be divided over elements of E but is not, due to a lack of information.

From the mapping m are usually defined two set-functions, the belief and the plausibility functions, respectively defined for any A ⊆ X as

Bel(A) = ∑ E⊆A m(E), ( 2
)
Pl(A) = ∑ E∩A = / 0 m(E) = 1 -Bel(A c ), (3)
with A c the complement of A. They satisfy Bel(A) ≤ Pl(A). The belief function, which sums all masses of subsets that imply A, measures how much event A is certain, while the plausibility function, which sums all masses of subsets consistent with A, measures how much the event A is possible. Within the so-called theory of evidence [START_REF] Shafer | A mathematical Theory of Evidence[END_REF], belief and plausibility functions are interpreted as confidence degrees about the event A, and are not necessarily related to probabilities. However, the mass distribution m can also be interpreted as the random set corresponding to an imprecisely observed random variable [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF], and the measures Bel and Pl can be interpreted as describing a set of probabilities, that is, we can associate to them a set P(Bel) such that

P(Bel) = {P|∀A, Bel(A) ≤ P(A) ≤ Pl(A)}
is the set of all probabilities bounded by Bel and Pl. The belief function can then be computed as a lower probability Bel(A) = inf P∈P(Bel) P(A) and the plausibility function likewise as an upper probability. Note that, since Bel and Pl are conjugate (Bel(A) = 1 -Pl(A c )), we can restrict our attention to one of them.

Consider now a collection of events A n = {A 1 , . . . , A n |A i ⊆ X } of subsets of X and a mass distribution m from which a belief function Bel can be computed. For any collection A n the inequality [START_REF] Shafer | A mathematical Theory of Evidence[END_REF]

Bel(∪ n i=1 A i ) ≥ ∑ I ⊆A n (-1) |I |+1 Bel(∩ A∈I A) (4)
is valid. This property is called order-n supermodularity, and belief functions are super-modular for any n > 0. While the inclusion-exclusion property (1) of probabilities is a mere consequence of the additivity axiom (for n = 2), supermodularity of order n does not imply supermodularity of order n + 1; and the supermodularity property valid at any order is characteristic of belief functions.

If Equation ( 4) is an equality for some family A n , we say that the belief function is additive for this collection, or A n -additive, for short. Equation ( 4) is to be compared to Equation [START_REF] Aguirre | Inclusion/exclusion principle for belief functions[END_REF]. Note that in the following we can assume without loss of generality that for any i, j, A i ⊆ A j , i.e, there is no pairwise inclusion relation between the sets of A n (otherwise A i can be suppressed from Equation ( 4)). Then the family A n is said to be proper.

General necessary and sufficient conditions

In the case of two events A 1 and A 2 , neither of which is included in the other, the basic condition for the inclusion-exclusion law to hold is that focal elements in A 1 ∪ A 2 should only lie (be included) in A 1 or A 2 . Indeed, otherwise, if there exists an event

E ⊆ A 1 ∪ A 2 with E ⊆ A 1 , E ⊆ A 2 and m(E) > 0, then Bel(A 1 ∪ A 2 ) ≥ m(E) + Bel(A 1 ) + Bel(A 2 ) -Bel(A 1 ∩ A 2 ) > Bel(A 1 ) + Bel(A 2 ) -Bel(A 1 ∩ A 2 ).
This means that, in order to ensure {A 1 , A 2 }-additivity, one must check that

F m ∩ 2 A 1 ∪A 2 = F m ∩ 2 A 1 ∪ 2 A 2 (5)
where 2 C denotes the set of subsets of C. So, one must check that for all events

E ∈ F m such that E ⊆ (A 1 ∪ A 2 ), either E ⊆ A 1 or E ⊆ A 2 , or equivalently Lemma 1. A belief function is additive for {A 1 , A 2 } if and only if for all events E ⊆ A 1 ∪ A 2 such that (A 1 \ A 2 ) ∩ E = / 0 and (A 2 \ A 1 ) ∩ E = / 0 then m(E) = 0.
Proof. Immediate, as E overlaps A 1 and A 2 without being included in one of them if and only if

(A 1 \ A 2 ) ∩ E = / 0 and (A 2 \ A 1 ) ∩ E = / 0.
Note that if {A 1 , A 2 } is not proper, the belief function is trivially additive for it. Figure 1 provides an illustration of a focal element that makes a belief function nonadditive for events A 1 and A 2 . This result can be extended to the case where A n = {A 1 , . . . , A n |A i ⊆ X } in a quite straightforward way:

Proposition 1. F m ∩ 2 A 1 ∪...∪A n = F m ∩ 2 A 1 ∪ . . . ∪ 2 A n ⇔ ∀E ⊆ (A 1 ∪ . . . ∪ A n ), if E ∈ F m then ∃A i , A j with (A i \ A j ) ∩ E = / 0 and (A j \ A i ) ∩ E = / 0. A 1 A 2 E Figure 1: Focal element E of non-additive belief function for {A 1 , A 2 } Proof. F m ∩ 2 A 1 ∪...∪A n = F m ∩ 2 A 1 ∪ . . . ∪ 2 A n if and only if ∃E ∈ F m ∩ 2 A 1 ∪...∪A n \ 2 A 1 ∪ . . . ∪ 2 A n if and only if ∃E ⊆ (A 1 ∪ . . . ∪ A n ), E ∈ F m such that ∀i = 1, . . . , n, E ⊆ A i if and only if ∃i = j, E ∈ F m , E ⊆ A i , E ⊆ A j , E ∩ A i = / 0, E ∩ A j = / 0 if and only if ∃i = j, E ∈ F m , with (A i \ A j ) ∩ E = / 0 and (A j \ A i ) ∩ E = / 0
So, based on Proposition 1, we have:

Theorem 2. The equality Bel(∪ n i=1 A i ) = ∑ I ⊆A n (-1) |I |+1 Bel(∩ A∈I A) (6)

holds if and only if for all E

⊆ (A 1 ∪ . . . ∪ A n ), if m(E) > 0 then there is no pair A i , A j with (A i \ A j ) ∩ E = / 0 and (A j \ A i ) ∩ E = / 0.
Theorem 2 shows that going from A 2 -additivity to A n -additivity is straightforward, as ensuring A n -additivity comes down to checking the conditions of A 2 -additivity for every pair of subsets in A n . This feature makes the verification of the property rather inexpensive. Finally, note that if the family A n is not proper, it means A j ⊆ A i for some i = j and it is then impossible that ∃E, (A i \ A j ) ∩ E = / 0 and (A j \ A i ) ∩ E = / 0. So, we can dispense with checking the condition for those pairs of sets.

Inclusion-exclusion for plausibilities

Note that by duality one also can write a form of inclusion-exclusion property for plausibility functions:

Pl(∩ n i=1 B i ) = ∑ I ⊆B n (-1) |I |+1 Pl(∪ B∈I B) (7)
for a family of sets B n = {A c i : A i ∈ A n } where A n satisfies the condition of Proposition 1. Although Equation [START_REF] Chang | Reliability evaluation of multi-state systems subject to imperfect coverage using OBDD[END_REF] provides us with a kind of inclusion-exclusion property for plausibilities, it does not provide insight about the conditions under which the equality

Pl(∪ n i=1 A i ) = ∑ I ⊆A n (-1) |I |+1 Pl(∩ A∈I A) (8)
holds. In this section, we will investigate this issue, concluding that the case of plausibility functions is harder to deal with, and less practically interesting than the case of belief functions.

A 1 A 2 E Figure 2: Focal element E of non-additive plausibility function for {A 1 , A 2 }
Let us first deal with two events A 1 and A 2 . In this case, any focal element E overlapping A 1 ∪ A 2 should not overlap A 1 and A 2 without overlapping A 1 ∩ A 2 , otherwise let E be the non-empty set of focal elements that overlap A 1 and A 2 without overlapping A 1 ∩ A 2 . It is then clear that Pl is strictly submodular, i.e.:

Pl(A 1 ∪ A 2 ) + ∑ E∈E m(E) = Pl(A 1 ) + Pl(A 2 ) -Pl(A 1 ∩ A 2 ).
and additivity fails. This leads us to the following condition for a plausibility function to be A 2 -additive.

Lemma 2. A plausibility function is

A 2 -additive for A 2 = {A 1 , A 2 } if and only if ∀E ∩ (A 1 ∪ A 2 ) = / 0 such that E ∩ (A 1 \ A 2 ) = / 0, E ∩ (A 2 \ A 1 ) = / 0 and E ∩ (A 1 ∩ A 2 ) = / 0, then m(E) = 0.
It should be noted that this condition is similar to, but quite different from the one in Lemma 1, as any set overlapping A 1 ∩ A 2 but not included in A 1 ∩ A 2 can receive a positive mass without leading to a violation of A 2 -additivity for the associated plausibility function. This is not the case for belief functions: for instance, the focal element of Figure 1 is not in contradiction with Lemma 2 (plausibility could still be A 2 -additive). Figure 2 pictures a focal element that would make the plausibility not A 2 -additive.

Nevertheless, the condition for A 2 -additivity in Lemma 2 can be equivalently expressed as follows

F m ∩ 2 (A c 1 ∪A c 2 ) = F m ∩ 2 A c 1 ∪ 2 A c 2 ,
which can be deduced from Equation (5), using the fact that for two subsets A 1 , A 2 , the A 2 -additivity of a plausibility function is equivalent to the A 2 -additivity of the dual belief function for

A c 1 , A c 2 (clearly, Pl(A 1 ∪ A 2 ) = Pl(A 1 ) + Pl(A 2 ) -Pl(A 1 ∩ A 2 ) is the same equation as Bel(A c 1 ∪ A c 2 ) = Bel(A c 1 ) + Bel(A c 2 ) -Bel(A c 1 ∩ A c 2 )
). However, the situation for plausibility functions is more involved than the one for belief functions, and Lemma 2 cannot be straightforwardly extended to the case of n events, as the A 3 -additivity of a plausibility function for A 1 , A 2 , A 3 :

Pl(A 1 ∪ A 2 ∪ A 3 ) = ∑ A i Pl(A i ) term 1 -∑ A i ,A j Pl(A i ∩ A j ) term 2 + Pl(A 1 ∩ A 2 ∩ A 3 ) term 3 . ( 9
) A 1 A 2 A 3 3.a A 1 A 2 A 3 3.b A 1 A 2 A 3 3.c
F m ∩ 2 (A c 1 ∪A c 2 ∪A c 3 ) = F m ∩ 2 A c 1 ∪ 2 A c 2 ∪ 2 A c 3
no longer ensures the A 3 -additivity of the plausibility function. 3.a, is focal, the mass of this element is counted once in the left-hand side of Equation ( 9), twice in term 1 and zero times in terms 2 and 3 of the right-hand side, so A 3 -additivity fails for this plausibility function on these sets.

For instance if E = (A 1 \ (A 2 ∪ A 3 )) ∪ (A 2 \ (A 1 ∪ A 3 )), a subset of A c 3 pictured in Figure
Also, in the case of plausibility functions, we cannot expect A n -additivity to follow from A 2 -additivity between all pairs of events. Consider indeed the following possible focal elements:

• E is included in ((A 1 ∩ A 2 ) \ A 3 ) ∪ ((A 2 ∩ A 3 ) \ A 1 ) (pictured in
∩ (A 1 \ A 3 ) = / 0, E ∩ (A 3 \ A 1 ) = / 0 and E ∩ (A 1 ∩ A 3 ) = / 0,
showing that it does not satisfy Lemma 2 for the pair A 1 , A 3 , and that this feature does not forbid A 3 -additivity to hold for plausibilities; 3.c): such an element is counted once in the left-hand side of Eq. ( 9), thrice in term 1, thrice in term 2 and zero times in term 3 of the right-hand side, hence A 3 -additivity does not hold if m(E) > 0. But E satisfies Lemma 2 for all three pairs, which proves not sufficient to ensure A 3 -additivity for plausibilities.

• E is included in ∪ i = j =k ((A i ∩ A j ) \ A k ) (pictured in Figure
This suggests that obtaining easy-to-check conditions for A n -additivity to hold for plausibility in a general setting will be difficult, if not impossible. Of course, one can check for a given collection A n that every focal element E ∈ F m overlapping ∪ A∈A n A is counted once in the right-and left-hand side of ( 8), yet such a tedious verification would defeat the purpose of using the inclusion-exclusion principle as a practical means to achieve efficient computations.

For this reason, we shall not deal with general conditions for the inclusion-exclusion principle to hold for plausibility functions. Yet we will mention those cases (which turn

X 1 X 2 x 1 1 x 1 2 x 1 3 x 2 1 x 2 2 x 2 3 X 1 X 2 x 1 1 x 1 2 x 1 3 x 2 1 x 2 2 x 2 3 X 1 X 2 x 1 1 x 1 2 x 1 3 x 2 1 x 2 2 x 2 3
Figure 4: Two possible decompositions of an event A into rectangular subsets out to be often met in practice) when the conjugacy Equation ( 3) with respect to belief functions can be exploited to compute Pl(∪ n i=1 A i ).

When focal elements are Cartesian products

The previous section has formulated general conditions for A n -additivity to hold for a given family of sets. In this section, we investigate a practically important particular case where focal elements and events A i , i = 1, . . . , n are Cartesian products. That is, we assume that X = X 1 × . . . × X D := X 1:D is the product of finite spaces X i , i = 1, . . . , D. We will call the spaces X i dimensions. We will denote by x i the value of a variable (e.g., the state of a component, the value of a propositional variable) on X i .

Given A ⊆ X , we will denote by A i the projection of A on X i . Let us call rectangular a subset A ⊆ X that can be expressed as the Cartesian product A = A 1 × . . . × A D of its projections (in general, only A ⊆ A 1 × . . . × A D holds for all subsets A). A rectangular subset A is completely characterized by its projections.

In the following, we derive conditions for the n-additivity property over families A n containing rectangular sets only, when the focal elements of mass functions defined on X are also rectangular (to simplify the proofs, we will also assume that all rectangular sets are focal elements).

Assuming focal elements to be rectangular is a restrictive assumption, as they cannot be freely manipulated and decomposed in different ways, but we discuss in Section 3.3 those (many) practical situations where such focal elements will appear. However, assuming that the collection of sets A n = {A 1 , . . . , A n } over which the belief value Bel(∪ n i=1 A n ) must be evaluated is not very restrictive, at least in the finite case. Indeed, any such set A i ⊆ X can then be decomposed into a (non-unique) finite union of (not necessarily disjoint) rectangular subsets. To see this, note that there exists an elementary way to always achieve such a decomposition: one can always decompose A as the union of its singletons, each of them being a degenerate rectangular subset. Figure 4 illustrates two possible decompositions of the same subset A. However, we shall see that such a decomposition is not always very interesting for applying the inclusionexclusion principle. The results of this section also provide conditions under which such a decomposition will allow one to apply the inclusion-exclusion principle.

Two sets, two dimensions

Let us first explore the case n = 2 and D = 2, that is

A 2 = {A 1 , A 2 } with A i = A 1 i × A 2 i for i = 1, 2.
The main idea in this case is that if A 1 \ A 2 and A 2 \ A 1 are rectangular with disjoint projections, then 2-additivity holds for belief functions, and this property is characteristic. Lemma 3. If A 1 and A 2 are rectangular and have disjoint projections on dimensions X 1 , X 2 , then there is no rectangular subset of A 1 ∪ A 2 overlapping both A 1 and A 2 .

Proof.

Consider C = C 1 ×C 2 overlapping both A 1 and A 2 . So there is (a 1 , a 2 ) ∈ A 1 ∩C and b 1 × b 2 ∈ A 2 ∩ C. Since C is rectangular, (a 1 , b 2 ) and (b 1 , a 2 ) ∈ C. However if C ⊆ A 1 ∪ A 2 then (a 1 , b 2 ) ∈ A 1 ∪ A 2 and either b 2 ∈ A 2 1 or a 1 ∈ A 1 2 . Since a 1 ∈ A 1 1 and b 2 ∈ A 2
2 by assumption, it would mean that projections of A 1 and A 2 are not disjoint, which leads to a contradiction.

We can now characterise under which conditions 2-additivity holds for belief functions

Theorem 3. 2-additivity applied to a proper family

A 2 = {A 1 , A 2 }

of rectangular sets holds for belief functions having rectangular focal elements if and only if one of the following conditions holds

1. A 1 1 ∩ A 1 2 = A 2 1 ∩ A 2 2 = / 0 2. A 1 1 ⊆ A 1 2 and A 2 2 ⊆ A 2 1 (or A 1 1 ⊇ A 1 2 and A 2 2 ⊇ A 2 1 ,

changing both inclusion directions).

Proof. First note that inclusions of Condition 2 can be considered as strict, as we have assumed A 1 , A 2 to not be included in each other, in which case the result immediately follows from

A 1 ∪ A 2 = A 1 if A 1 ⊆ A 2 or from A 1 ∪ A 2 = A 2 if A 2 ⊆ A 1 .
⇐:

1. If A 1 1 ∩A 1 2 = A 2 1 ∩A 2 2 = / 0, A 1 and
A 2 are disjoint, as well as their projections. Then by Lemma 3, all rectangular subsets included in A 1 ∪ A 2 are either included in A 1 or in A 2 , hence Lemma 1 applies and 2-additivity holds for belief functions.

2. A 1 1 ⊂ A 1 2 and A 2 2 ⊂ A 2 1 imply that A 1 \A 2 = A 1 1 ×(A 2 1 \A 2 2 ) and A 2 \A 1 = (A 1 2 \A 1 1 )× A 2 2 .
As A 1 \A 2 and A 2 \A 1 are rectangular and have disjoint projections, Lemma 3 and Lemma 1 apply (as above) and 2-additivity holds for belief functions. ⇒:

X 1 X 2 x 1 1 x 1 2 x 1 3 x 2 1 x 2 2 x 2 3 X 1 X 2 x 1 1 x 1 2 x 1 3 x 2 1 x 2 2 x 2 3 A 1 A 2 Figure 5: Situations satisfying Theorem 3 X 1 X 2 x 1 1 x 1 2 x 1 3 x 2 1 x 2 2 x 2 3 X 1 X 2 x 1 1 x 1 2 x 1 3 x 2 1 x 2 2 x 2 3 A 1 A 2 Figure 6: Situations not satisfying Theorem 3 1. Suppose A 1 ∩ A 2 = / 0 with A 1 1 ∩ A 1 2 = / 0. Then (A 1 1 ∩ A 1 2 ) × (A 2 1 ∪ A 2 2 ) is rectan- gular, not contained in A 1 nor A 2 but contained in A 1 ∪ A 2 , showing that the focal element (A 1 1 ∩ A 1 2 ) × (A 2 1 ∪ A 2 2 )
does not satisfy Lemma 1 and therefore that 2-additivity does not hold.

Suppose

A 1 1 ⊂ A 1 2 but A 2 2 ⊂ A 2 1 . Again, (A 1 1 ∩ A 1 2 ) × (A 2 1 ∪ A 2 2 ) = A 1 1 × (A 2 1 ∪ A 2 2 ) is rectangular, neither contained in A 1 nor A 2 but contained in A 1 ∪ A 2 ,

The multidimensional case

We can now proceed to extend Theorem 3 to the case of any number D of dimensions. However, this extension will not be as straightforward as going from Lemma 1 to Proposition 1, and we need first to characterize when the union of two singletons is rectangular. We will call such rectangular unions minimal rectangles. A singleton is a degenerate example of a minimal rectangle.

one i ∈ [1 : D] such that a i = b i Proof. ⇒: If a i = b i for only one i, then {a, b} = {a 1 } × . . . × {a i , b i } × . . . {a D } is rectangular.
⇐: Let us now consider the case where a i = b i and a j = b j for i = j. In this case, {a, b} = {(a 1 , . . . , a i , . . . , a j , . . . , a D ), (a 1 , . . . , b i , . . . , b j , . . . , a D )}.

The projections of {a, b} on the dimensions of X are {a k , b k }, and we know that {a i , b i } as well as {a j , b j }, do not reduce to singletons. Hence, the Cartesian product of the projections of {a, b} contains the set {a 1 } × . . . × {a i , b i } × {a j , b j } × . . . × {a n }, that contains elements not in {a, b} (e.g. (a 1 , . . . , b i , . . . , a j , . . . , a D )). Since {a, b} is not characterised by its projections on dimensions X i , it is not rectangular, and this finishes the proof.

As mentioned before, any set can be decomposed into rectangular sets, and in particular any rectangular set can be decomposed into minimal rectangles. Also, any rectangular set that is not a singleton will at least contain one minimal rectangle, implying that there always exist at least two singletons of a rectangular set forming a minimal rectangle (we will use this in subsequent proofs). Let us now show how Theorem 3 can be extended to D dimensions.

Theorem 4. 2-additivity holds for a proper family

A 2 = {A 1 , A 2 }

of rectangular sets for belief functions having rectangular focal elements if and only if one of the following conditions holds

1. ∃ distinct p, q ∈ {1, . . . , D} such that A p 1 ∩ A p 2 = A q 1 ∩ A q 2 = / 0 2. ∀i ∈ {1, . . . , D} either A i 1 ⊆ A i 2 or A i 2 ⊆ A i 1
Proof. Again, we can consider that there is at least two distinct p, q ∈ {1, . . . , D} such that inclusions A p 1 ⊂ A p 2 and A q 2 ⊂ A q 1 of Condition 2 are strict, as we have assumed A 1 , A 2 to not be included in each other (as in Theorem 3 and for the same reasons).

⇐:

1. Any two a 1 ∈ A 1 and a 2 ∈ A 2 will be such that

a i 1 ∈ A i 1 and a i 2 ∈ A i 2 must be distinct for i = p, q since A p 1 ∩ A p 2 = A q 1 ∩ A q 2 = / 0.
By Lemma 4, this means that there is no pair a 1 ∈ A 1 and a 2 ∈ A 2 forming a minimal rectangle. This implies that there is no minimal rectangle included in A 1 ∪ A 2 , and therefore no rectangular subset. It follows that each rectangular subset included in A 1 ∪ A 2 is either included in A 1 or in A 2 , hence Lemma 1 applies and 2-additivity holds for belief functions. 2. Let us denote by P the set of indices p such that A p 1 ⊂ A p 2 and by Q the set of indices q such that A q 2 ⊂ A q 1 . Now, let us consider two singletons

a 1 ∈ A 1 \ A 2 and a 2 ∈ A 2 \ A 1 . Then • ∃p ∈ P such that a p 1 ∈ A p 1 \ A p 2 , otherwise a 1 is included in A 1 ∩ A 2 • ∃q ∈ Q such that a q 2 ∈ A q 2 \ A q 1 , otherwise a 2 is included in A 1 ∩ A 2 but since a q 1 ∈ A q
1 and a p 2 ∈ A p 2 by definition, a 1 and a 2 must differ at least on two dimensions, hence by Lemma 4 one cannot form a minimal rectangle outside A 1 ∩ A 2 , that is, by picking pairs of singletons in A 1 \ A 2 and A 2 \ A 1 . As above, this implies that Lemma 1 is satisfied and that 2-additivity holds. ⇒:

1. Suppose A 1 ∩ A 2 = / 0 with A q 1 ∩ A q 2 = / 0 only for q. Then the following rectangular set contained in A 1 ∪ A 2 (A 1 1 ∩ A 1 2 ) × • • • × (A q-1 1 ∩ A q-1 2 ) × (A q 1 ∪ A q 2 ) × (A q+1 1 ∩ A q+1 2 ) . . . × (A D 1 ∩ A D 2 )
is neither contained in A 1 nor A 2 , so 2-additivity will not hold (by Lemma 1) 2. suppose A 1 ∩ A 2 = / 0 and A q 1 ⊆ A q 2 , A q 1 ⊇ A q 2 for some q. Again,

(A 1 1 ∩ A 1 2 ) × • • • × (A q-1 1 ∩ A q-1 2 ) × (A q 1 ∪ A q 2 ) × (A q+1 1 ∩ A q+1 2 ) . . . × (A D 1 ∩ A D 2 )
is rectangular, neither contained in A 1 nor A 2 but contained in A 1 ∪ A 2 , so 2additivity will not hold (by Lemma 1).

Using Proposition 1, the extension to n-additivity in D dimensions is straightforward:

Theorem 5. n-additivity holds for a proper family A n = {A 1 , . . . , A n } of rectangular sets for belief functions having rectangular focal elements if and only if, for each pair A i , A j , one of the following conditions holds

1. ∃ distinct p, q ∈ {1, . . . , D} such that A p i ∩ A p j = A q i ∩ A q j = / 0 2. ∀ℓ ∈ {1, . . . , D} either A ℓ i ⊆ A ℓ j or A ℓ j ⊆ A ℓ i
Note that the second condition is insensitive to set-complements, hence the following result:

Corollary 6. n-additivity holds on both

A n = {A 1 , . . . , A n } and A - n = {A c 1 , . . . , A c n } for belief functions whenever for each pair A i , A j , ∀ℓ ∈ {1, . . . , D} either A ℓ i ⊆ A ℓ j or A ℓ j ⊆ A ℓ i .

On the practical importance of rectangular focal elements

While limiting ourselves to rectangular subsets in A is not especially restrictive, the assumption that focal elements have to be restricted to rectangular sets may seem restrictive (as we are not free to cut any focal element into rectangular subsets). However, such mass assignments actually appear in many practical situations. They can result for example from the combination of marginal masses m i defined on each dimension X i , i = 1, . . . , D under an assumption of (random set) independence [START_REF] Couso | A survey of concepts of independence for imprecise probabilities[END_REF]. In this case, the joint mass assigned to each rectangular set E is

m(E) = D ∏ i=1 m i (E i ). (10)
Additionally, the random set independent assumption makes the computation of the belief and plausibility functions of any rectangular set A easier, as they factorize in the following way:

Bel(A) = D ∏ i=1 Bel i (A i ), (11)
Pl(A) = D ∏ i=1 Pl i (A i ), (12)
where Bel i , Pl i are the belief/plausibility measures induced by m i . An interesting fact is that since the proofs of Section 3 only require focal elements and events to be Cartesian products, they also apply to the cases of unknown or partially known dependence, as long as these latter cases can be expressed by linear constraints imposed on the joint mass [START_REF] Baudrit | Comparing methods for joint objective and subjective uncertainty propagation with an example in a risk assessment[END_REF]. Considering more generic models than belief functions is also possible, e.g. lower probabilities. Then the positivity of the mass functions m i no longer holds, but the approach can be carried out without modifying our results since the product of (possibly negative) masses in such approaches preserves the approximation properties of random set independence [START_REF] Destercke | Independence and 2-monotonicity: Nice to have, hard to keep[END_REF].

The following sections explore and discuss specific cases of interest where the inclusion-exclusion property applies.

The case of Boolean formulas

In this section, we explore the case where spaces X i are binary. In particular, conditions are laid bare for applying the inclusion-exclusion property to Boolean formulas expressed in Disjunctive Normal Form (DNF). We also discuss the problem of estimating plausibilities of Boolean formulas using the inclusion-exclusion property.

In propositional logic, each dimension X i is of the form {x i , ¬x i }. It can be associated to a Boolean variable also denoted by x i , and X 1:D is also called the set of interpretations of the propositional language generated by the set of variables x i . In this case, x i is understood as an atomic proposition, while ¬x i denotes its negation. An element of X i is called a literal (x i is a positive one and ¬x i a negative one). Any rectangular set A ⊆ X 1:D can then be interpreted as a conjunction of literals (it is often called a partial model), and given a collection of n such partial models A n = {A 1 , . . . , A n }, the event A 1 ∪ . . . ∪ A n is a Boolean formula expressed in Disjunctive Normal Form (DNF -a disjunction of conjunctions). All Boolean formulas can be written in such a form.

A convenient representation of a partial model A is in the form of an orthopair [8] (P, N) of disjoint subsets of indices of variables P, N ⊆ [1 : D] such that A (P,N) = k∈P x k ∧ k∈N ¬x k . Then an element in X 1:D is of the form k∈P x k ∧ k∈P c ¬x k , i.e. corresponds to an orthopair (P, P c ).

We consider belief functions generated by focal elements having the form of partial models. To this end, we consider that the uncertainty over each Boolean variable x i is described by a belief function Bel i . As X i is binary, its mass function m i only needs two numbers to be defined. Indeed, it is enough to know l i = Bel i ({x i }) and u i = Pl i ({x i }) ≥ l i (for instance a probability interval [START_REF] Campos | Probability intervals: a tool for uncertain reasoning[END_REF]) to characterise the marginal mass function m i since:

• Bel i ({x i }) = l i = m i ({x i }); • Pl i ({x i }) = 1 -Bel i ({¬x i }) = u i =⇒ m i ({¬x i }) = Bel i ({¬x i }) = 1 -u i ; • The sum of masses is m i ({x i }) + m i ({¬x i }) + m i (X i ) = 1, so m i (X i ) = u i -l i .
Given D independent marginal masses m i on X i , i = 1, . . . , D, the joint mass m on X 1:D can be computed as follows for any partial model A (P,N) , applying Equation (10):

m(A (P,N) ) = ∏ i∈P l i ∏ i∈N (1 -u i ) ∏ i / ∈P∪N (u i -l i ) . (13)
We can then give explicit expressions for the belief and plausibility of conjunctions or disjunctions of literals in terms of marginal mass functions:

Proposition 7. The belief of a conjunction C (P,N) = k∈P x k ∧ k∈N ¬x k , and that of a disjunction D (P,N) = k∈P x k ∨ k∈N ¬x k of literals forming an orthopair (P, N) are respectively given by:

Bel(C (P,N) ) = ∏ i∈P l i ∏ i∈N (1 -u i ), (14)
Bel(D (P,N) ) = 1 -∏ i∈P (1 -l i ) ∏ i∈N u i . ( 15
)
Proof. Bel(C (P,N) ) can be obtained by applying Equation [START_REF] Campos | Probability intervals: a tool for uncertain reasoning[END_REF] to C (P,N) . For Bel(D (P,N) ), we have

Pl(C (N,P) ) = Pl(∧ i∈N x i ∧ ∧ i∈P ¬x i ) = ∏ i∈N (1 -l i ) ∏ i∈P u i = 1 -(1 -∏ i∈N (1 -l i ) ∏ i∈P u i ) = 1 -Bel(∨ i∈N ¬x i ∨ ∨ i∈P x i ) = 1 -Bel(D (P,N) )
with the second equality following from Equation [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF].

Using the fact that Bel(C (N,P) ) = 1 -Pl(D (P,N) ), we can deduce

Pl(D (P,N) ) = 1 -∏ i∈P l i ∏ i∈N (1 -u i ).
We can particularize Theorem 5 to the case of Boolean formulas, and identify conditions under which the belief or the plausibility of a DNF can be easily estimated using the inclusion-exclusion Equality [START_REF] Aguirre | Inclusion/exclusion principle for belief functions[END_REF]. Let us see how the conditions exhibited in this theorem can be expressed in the Boolean case.

Consider the first condition of Theorem 5 ∃p = q ∈ {1, . . . , D} such that A p i ∩ A p j = A q i ∩ A q j = / 0.

Note that when spaces are binary,

A p i = {x p } (if p ∈ P i ), or A p i = {¬x p } (if p ∈ N i ), or yet A p i = X i (if p ∈ P i ∪ N i ). A i ∩ A j = /
0 therefore means that for some index p, p ∈ (P i ∩ N j ) ∪ (P j ∩ N i ) (there are two opposite literals in the conjunction).

The condition can thus be rewritten as follows, using orthopairs (P i , N i ) and (P j , N j ): ∃p = q ∈ {1, . . . , D} such that p, q ∈ (P i ∩ N j ) ∪ (P j ∩ N i ).

Example 1. Consider the equivalence connective

x 1 ⇔ x 2 = (x 1 ∧ x 2 ) ∨ (¬x 1 ∧ ¬x 2 ) so that A 1 = x 1 ∧ x 2 and A 2 = ¬x 1 ∧ ¬x 2 . We have P 1 = {1, 2}, N 1 = / 0, P 2 = / 0, N 2 = {1, 2}. So, p = 1 ∈ P 1 ∩ N 2 , q = 2 ∈ P 1 ∩ N 2 ,
hence the condition is satisfied and Bel(x 1 ⇐⇒ x 2 ) = Bel(x 1 ∧ x 2 ) + Bel(¬x 1 ∧ ¬x 2 ) (the remaining term is Bel( / 0)). Likewise, the exclusive or :

x 1 ⊕ x 2 = (x 1 ∧ ¬x 2 ) ∨ (¬x 1 ∧ x 2 ) so that A 1 = x 1 ∧ ¬x 2 and A 2 = ¬x 1 ∧ x 2 . We have P 1 = {1}, N 1 = {2}, P 2 = {2}, N 2 = {2}. So, p = 1 ∈ P 1 ∩ N 2 , q = 2 ∈ N 1 ∩ P 2 and Bel(x 1 ⊕ x 2 ) = Bel(x 1 ∧ ¬x 2 ) + Bel(¬x 1 ∧ x 2 ) (again, the remaining term is Bel( / 0)).
The second condition of Theorem 5 reads ∀ℓ ∈ {1, . . . , D} either A ℓ i ⊆ A ℓ j or A ℓ j ⊆ A ℓ i and the condition A ℓ i ⊆ A ℓ j can be expressed in the Boolean case as:

ℓ ∈ (P i ∩ N c j ) ∪ (N i ∩ P c j ) ∪ (P c i ∩ N c i ∩ P c j ∩ N c j ).
The condition can thus be rewritten as follows, using orthopairs (P i , N i ) and (P j , N j ):

P i ∩ N j = / 0 and P j ∩ N i = / 0
Example 2. Consider the disjunction x 1 ∨ x 2 , where A 1 = x 1 and A 2 = x 2 , so that

P 1 = {1}, P 2 = {2}, N 1 = N 2 = / 0. So Bel(x 1 ∨ x 2 ) = Bel(x 1 ) + Bel(x 2 ) -Bel(x 1 ∧ x 2 ). Likewise for implication, x 1 → x 2 = ¬x 1 ∨x 2 , where A 1 = ¬x 1 and A 2 = x 2 , so that N 1 = {1}, P 2 = {2}, P 1 = N 2 = / 0. So Bel(x 1 → x 2 ) = Bel(¬x 1 ) + Bel(x 2 ) -Bel(¬x 1 ∧ x 2 ).
We can summarize the above results as Proposition 8. The set of partial models

A n = {A 1 , .

. . , A n } satisfies the inclusionexclusion principle if and only if, for any pair A i , A j one of the two following conditions is satisfied:

• ∃p = q ∈ {1, . . . , D} such that p, q ∈ (P i ∩ N j ) ∪ (P j ∩ N i ).

• P i ∩ N j = / 0 and P j ∩ N i = / 0

This condition tells us that for any pair of partial models, :

• either conjunctions A i , A j contain at least two opposite literals,

• or events A i , A j have a non-empty intersection and have a common model.

As a consequence we can compute the belief of any logical formula that obeys the conditions of Proposition 8 in terms of the belief and plausibilities of atoms x i . Example 3. Consider the formula (x 1 ∧¬x 2 )∨(¬x 1 ∧x 2 )∨x 3 , with

A 1 = x 1 ∧¬x 2 , A 2 = ¬x 1 ∧ x 2 , A 3 = x 3 . We have P 1 = {1}, N 1 = {2}, P 2 = {2}, N 2 = {1}, P 3 = {3}, N 3 = /
0. Thus it satisfies Proposition 8, and

Bel((x 1 ∧ ¬x 2 ) ∨ (¬x 1 ∧ x 2 ) ∨ x 3 ) = Bel(x 1 ∧ ¬x 2 ) + Bel(¬x 1 ∧ x 2 ) + Bel(x 3 ) -Bel(x 1 ∧ ¬x 2 ∧ x 3 ) -Bel(¬x 1 ∧ x 2 ∧ x 3 )
(other belief values are equal to 0 since referring to contradictory Boolean expressions)

=l 1 (1 -u 2 ) + (1 -u 1 )l 2 + l 3 (1 -l 1 (1 -u 2 ) -(1 -u 1 )l 2 )
The conditions of Proposition 8 allow us to check, once a formula has been put in DNF, whether or not the inclusion-exclusion principle applies. Important particular cases where it applies are disjunctions of partial models C i having only positive (resp. negative) literals, of the form C 1 ∨ ... ∨C n , where N 1 = . . . = N n = / 0 (resp. P 1 = . . . = P n = / 0). This is the typical Boolean formula obtained in fault tree analysis, where elementary failures are modelled by positive literals, and the general failure event is due to the simultaneous occurrence of some subsets of elementary failures (see Section 6.1). Namely, we have

Bel(C 1 ∨ ... ∨C n ) = n ∑ i=1 Bel(C i ) - n-1 ∑ i=1 n ∑ j=i+1 Bel(C i ∧C j ) + n-2 ∑ i=1 n-1 ∑ j=i+1 n ∑ k= j+1 Bel(C i ∧C j ∧C k ) -... + (-1) m+1 Bel(C 1 ∧ ... ∧C n ), (16)
where the terms on the right-hand side can be computed from belief values of atoms as Bel(C (P, / 0) ) = ∏ i∈P l i as per Proposition 7. More generally, the inclusion-exclusion principle applies to disjunctions of partial models which can, via a renaming, be rewritten as a disjunction of conjunctions of positive literals: namely, whenever a single variable never appears in a positive and negative form in two of the conjunctions. This is equivalent to the second condition of Proposition 8. Then, of course, values 1u i must be used in place of l i for negative literals.

For such Boolean formulas, the inclusion-exclusion principle can also be used to also estimate the plausibility of C 1 ∨...∨C n . Indeed, consider the formula ∨ i∈[1:n] ∧ k∈P i x i possibly obtained after a renaming, then

¬ ∨ i∈[1:n] ∧ k∈P i x i = ∧ i∈[1:n] ¬ ∧ j∈P i x j = ∧ i∈[1:n] ∨ j∈P i ¬x j = ∨ k∈P 1 ו••×P n ∧ j∈[1:n] ¬x k j using distributivity,
where k ranges on n-tuples of indices (one component per conjunction C i ). Namely, starting with a DNF involving conjunctions of positive literals, ∧ i∈[1:n] ∨ j∈P i ¬x j is turned into a DNF with only negative literals, to which the second condition of Proposition 8 applies, and

Pl ∨ i∈[1:n] ∧ k∈P i x i = 1 -Bel ∨ k∈P 1 ו••×P n ] ∧ j∈[1:n] ¬x k i .
On the other hand, it is not always possible to put the complement of every formula satisfying the second condition of Proposition 8 in a DNF form that also satisfies Proposition 8.

Example 4. Consider the equivalence formula between three elements, that is the formula F = (¬x 1 ∧ ¬x 2 ∧ ¬x 3 ) ∨ (x 1 ∧ x 2 ∧ x 3 ). It satisfies Proposition 8, but its negation

¬F = (x 1 ∧ ¬x 2 ) ∨ (x 2 ∧ ¬x 3 ) ∨ (x 3 ∧ ¬x 1 ), (17)
once put in DNF form, does not satisfy Proposition 8 (each pair of conjunctions possesses only one variable with opposite literal). However, the negation of other formulas such as logical equivalence between two elements possesses a DNF form ¬(

x 1 ⇔ x 2 ) = (x 1 ∧ ¬x 2 ) ∨ (¬x 1 ∧ x 2 ) that satisfies Proposition 8.
Example 5. As another example where the inclusion-exclusion principle cannot be applied, consider the formula x 1 ∨ (¬x 1 ∧ x 2 ) (which is just the disjunction x 1 ∨ x 2 we already considered above). It does not hold that Bel(

x 1 ∨ (¬x 1 ∧ x 2 )) = Bel(x 1 ) + Bel(¬x 1 ∧ x 2 ) = l 1 + (1 -u 1 )l 2 .
Indeed the latter sum neglects m(x 2 ) = (u 1l 1 )l 2 , since x 2 is a focal element that implies x 1 ∨ x 2 but neither x 1 nor ¬x 1 ∧ x 2 . However, computing Bel(

x 1 ∨ x 2 ) is obvious as 1 -(1 -l 1 )(1 -l 2 ) from Proposition 7.
The last remark suggests that normal forms that are very useful to compute the probability of a Boolean formula efficiently, such as BDD [START_REF] Bryant | Symbolic Boolean manipulation with ordered binary-decision diagrams[END_REF] may be useless to speed up the computation of its belief and plausibility degrees. For instance, x 1 ∨ (¬x 1 ∧ x 2 ) is a binary decision diagram (BDD) for the disjunction, and this form prevents Bel(x 1 ∨ x 2 ) from being properly computed by standard methods as the inclusion-exclusion principle fails in this case. The question whether any Boolean formula can be re-expressed in a form satisfying Proposition 8 is answered to the negative by Formula [START_REF] Dubois | Formal representations of uncertainty[END_REF], which provides a counterexample to this claim.

The case of events defined by monotone functions

In this section, we show that the inclusion-exclusion principle can be applied to evaluate some events of interest defined by means of monotone functions on Cartesian products of discrete linearly ordered spaces. Such functions are commonly used in problems such as multi-criteria decision making [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid. 4OR[END_REF], reliability assessments [START_REF] Destercke | An extension of universal generating function in multi-state systems considering epistemic uncertainties[END_REF] or optimization problems [START_REF] Fortin | Criticality analysis of activity networks under interval uncertainty[END_REF].

We assume that we have some function φ : X 1:D → Y where variables x j , j = 1, . . . , D take their values on a finite linearly ordered space X j = {x j 1 , . . . , x j k j } of k j elements. We denote by ≤ j the order relation on X j and assume (without loss of generality) that elements are indexed such that x j i < j x j k iff i < k. We also assume that the output space Y is ordered and we denote by ≤ Y the order on Y , assuming an indexing such that y i < Y y k iff i < k. Given two elements x, z ∈ X 1:D , we simply write x ≤ z if x j ≤ j z j for j = 1, . . . , n, and x < z if moreover x j < j z j for at least one j.

We assume that the function is non-decreasing in each of its variables x j , that is

φ (x 1 i 1 , . . . , x ℓ i ℓ , . . . , x D i D ) ≤ Y φ (x 1 i 1 , . . . , x ℓ i ′ ℓ , . . . , x D i D ) (18)
iff i ℓ ≤ i ′ ℓ . Note that a function monotone in each variable x j can always be transformed into a non-decreasing one, since if φ is decreasing in X i , it becomes non-decreasing in x i when considering the reverse ordering of ≤ j (i.e., x j i < x j k iff k < i). We now consider the problem where we want to estimate the uncertainty of some event {φ ≥ d} (or {φ < d}, that can obtained by duality). Evaluating the uncertainty over such events is instrumental in a number of applications, from checking whether a threshold can be trespassed in risk analysis [START_REF] Baudrit | Joint propagation and exploitation of probabilistic and possibilistic information in risk assessment[END_REF] to computing level sets when solving the Choquet integral, e.g., in multi-criteria decision making [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid. 4OR[END_REF]. Given a value d ∈ Y , let us define the concept of minimal path and minimal cut vectors. Let {p 1 , . . . , p n } be the set of all minimal path vectors of some function φ for a given threshold demand d. We denote by A p i = {x ∈ X 1:D |x ≥ p i } the event corresponding to the set of configurations dominating the minimal path vector p i and by A n = {A p 1 , . . . , A p n } the set of events induced by minimal path vectors. Note that each set

A p i = × D j=1 {x j |x j ≥ j p j i } (19)
is rectangular, hence we can use results from Section 3.

Lemma 5. The collection of rectangular sets A n induced by minimal path vectors satisfies Theorem 5

Proof. Consider two events A p i , A p j induced by minimal path vectors and a dimension ℓ, then clearly either

{x ℓ ≥ ℓ p ℓ i } ⊆ {x ℓ ≥ ℓ p ℓ j } (A ℓ p i ⊆ A ℓ p j ) or {x ℓ ≥ ℓ p ℓ i } ⊇ {x ℓ ≥ ℓ p ℓ j } (A ℓ p i ⊇ A ℓ p j ).
It can be checked that {x ∈ X 1:D |φ (x) ≥ d} = ∪ n i=1 A p i . We can therefore write the inclusion-exclusion formula for belief functions:

Bel(φ (x) ≥ d) = Bel(A p 1 ∪ . . . ∪ A p n ) = ∑ I ⊆A n (-1) |I |+1 Bel(∩ A∈I A), = 1 -Pl(φ (x) < d)
Under the assumption of random set independence, computing each term simplifies into

Bel(A p j ) = D ∏ i=1 Bel({x i ≥ p i j }) Bel(A p j ∩ . . . ∩ A p k ) = D ∏ i=1 Bel({x i ≥ max(p i j , . . . , p i k )})
The computation of Bel(φ (x) < d) can be carried out similarly by using minimal cut vectors. Let c 1 , . . . , c m be the set of all minimal cut vectors of φ for threshold d.

Then A c i = {x ∈ X 1:D |x ≤ c i } = × D j=1 {x j |x j ≤ j c j i }
is rectangular and we have the following result, whose proof is similar to the one of Lemma 5.

Lemma 6. The collections of rectangular sets A m induced by minimal cut vectors satisfy Theorem 5

Denoting A m = {A c 1 , . . . , A c m } the set of events induced by minimal cut vectors, we have that {x ∈ X 1:D |φ (x) < d} = ∪ m i=1 A c i , hence applying the inclusion-exclusion formula for belief functions gives

Bel(φ (x) < d) = Bel(A c 1 ∪ . . . ∪ A c m ) = ∑ I ⊆A m (-1) |I |+1 Bel(∩ A∈I A), = 1 -Pl(φ (x) ≥ d).
This also shows that the inclusion-exclusion formula can be used to estimate both belief and plausibilities of events of the type {φ ≥ d} and {φ < d} when φ is monotone.

Application in reliability analysis

In this section, we illustrate how our results can be used in the particular field of reliability analysis, as this field is typically concerned with monotone and potentially large systems for which marginal uncertainty models are specified on components. We first deal with binary systems before addressing the case of Multi-State Systems (MSS).

Reliability of binary systems

In classical system reliability, X i are the states of some component, and the system state depends on the joint state of elements. We will consider the most common case in which X i = {x i , ¬x i } is binary, x i being a Boolean variable meaning that component i works, ¬x i that it failed. The structure function φ : X → {0, 1} specifies when the system works (φ = 1) and when it does not. The problem is then to evaluate, from the joint mass m, the values Bel(φ -1 (1)) = 1 -Pl(φ -1 (0)) and Bel(φ -1 (0)) = 1 -Pl(φ -1 (1)). This is a special case of the one addressed in Section 4.

In the binary case, a minimal path p can be expressed as a subset S p ⊆ [1 : D] (the counterpart of a minimal vector path in Section 5). It indicates a minimal set of elements that must be in working state, in the sense that if only those components are working, then the system is guaranteed to work but will fail if one of them fails. For example, S p = {1, 2} states that φ (x 1 , x 2 , . . . ) = 1 whatever the values of the other components. Note that two minimal paths p 1 and p 2 are such that S p 1 ⊆ S p 2 and S p 2 ⊆ S p 1 , otherwise one of the two is not minimal.

A minimal path p specifies a partial model (a conjunction of literals) A p with no negative literal (an orthopair (P, N) = (S p , / 0) in the notations of Section 4). If p 1 , . . . , p n are the minimal paths of a system, then φ -1 (1) is the disjunction A p 1 ∨ . . . ∨ A p n . This means that computing our belief in the fact that a system will work is given by

Bel(φ -1 (1)) = Bel(A p 1 ∨ . . . ∨ A p n ). (20)
That A p 1 ∨ . . . ∨ A p n satisfies Proposition 8 is immediate, as only positive literals appear in the formulas.

The same reasoning can be carried out for minimal cuts c to obtain Bel(φ -1 (0)). In this case we can specify a set of m minimal cuts, a minimal cut c being encoded as a subset S c ⊆ [1 : D] indicating a minimal set of components such that, if all of them fail, then the system is guaranteed to fail. For example, S c = {1, 2} states that φ (¬x 1 , ¬x 2 , . . . ) = 0 whatever the values of the other components. As for minimal paths, a minimal cut c specifies partial models (P, N) such that P = / 0 and N = S c . Given the minimal paths p 1 , . . . , p n and cuts c 1 , . . . , c m of a system, the whole reliability of the system can be computed as

Bel(φ -1 (1)) = ∑ I ⊆[1:n] (-1) |I |+1 Bel(∩ i∈I A p i ), (21)
Bel(φ -1 (0)) = ∑ I ⊆[1:m] (-1) |I |+1 Bel(∩ i∈I A c i ) (22)
These equations are particularly easy to evaluate using Equation ( 14).

Example 6. Let us take the example of a bridge system, pictured in Figure 7. Note that this system is complex, in the sense that it cannot be reduced to a set of parallel and series connections.

The minimal paths and cuts of this system are the following (we only write p i for S p i , etc.):

p 1 = {1, 2} c 1 = {1, 4} p 2 = {4, 5}] c 2 = {2, 5} p 3 = {1, 3, 5} c 3 = {1, 3, 5} p 4 = {2, 3, 4} c 4 = {2, 3, 4} 20
x 1

x 2 x 3 x 4 x 5 Pl(x i ) 0.72 0.79 0.88 0.92 0.91 Bel(x i ) 0.70 0.75 0.80 0.85 0.90 The uncertainty information on component states is given in Table 1. Equations ( 21) and ( 22) can then be computed efficiently. For example, the degree of belief associated to the event A p 1 ∩ A p 2 induced by the minimal paths p 1 , p 2 is

Bel(A p 1 ∩ A p 2 ) = Bel({x 1 })Bel({x 2 })Bel({x 4 })Bel({x 5 }).
The final reliability of the bridge system is [Bel(φ -1 (1)), Pl(φ -1 (1))] = [0.92, 0.96] using the results of the two previous sections.

Multi-State Systems (MSS) reliability

In the previous subsection, we made the usual assumption in system reliability analysis that components can assume 2 states: failed or working. Multi-State Systems (MSS) reliability goes beyond this assumption. It allows each component to be in one of multiple (exclusive) states. For example, a power station may have four different states corresponding to generating electricity at 0, 25, 50, 75 and 100 percent of its full capacity.

In recent years, multi-state system reliability analysis has received considerable attention, yet less than binary systems. The complexity in MSS analysis is due to the non-binary nature of the system and its components. There are many solutions to reduce this complexity, such as Markov methods [START_REF] Ushakov | Handbook of Reliability Engineering[END_REF][START_REF] Chang | Reliability evaluation of multi-state systems subject to imperfect coverage using OBDD[END_REF], discrete event simulation, among others. We refer to Lisnianski and Levitin [START_REF] Lisnianski | Multi-State System Reliability: Assessment, Optimization and Applications[END_REF] for a detailed review of the problem. MSS analysed in this section are such that

• the components are s-independent, meaning that the occurrence of one component state change event has no influence on the occurrence of the other state change event;

• the states of each component of the MSS are mutually exclusive, i.e. at any time, any component is in one of its states;

• the MSS is coherent (if one state component efficiency increases, the overall efficiency increases).

Let us now show that for such systems, we can define minimal path sets and minimal cut sets that satisfy the inclusion-exclusion principle.

Minimal path sets and minimal cut sets of MSS

In reliability analysis, variables x j , j = 1, . . . , D correspond to the D components of the system and the value x j i is the ith state of component j. Typically, states are ordered according to their performance rates, hence we can assume the spaces X j The structure function φ : X1:D → Y maps the system states to the global system performance. Our assumption that the system is coherent means that the function φ is non-decreasing, in the sense of Equation [START_REF] Fetz | Sets of joint probability measures generated by weighted marginal focal sets[END_REF]. Note that, in this work and for simplicity, the term "multi-state system" is used to designate systems where both components and system performance take several possible states (such systems being usually called multi-state systems with multi-state components).

As the structure function of a MSS is monotone, we can directly apply the results from Section 5 to estimate uncertainty bounds about the event {φ ≥ d}, where d ∈ Y . Estimating such an uncertainty is a typical task in multi-state reliability analysis, as it amounts to estimating the degree of certainty that a system will guarantee a level d of performance. This is illustrated in the next section.

Example

Let us now illustrate our approach on a complete example, inspired from Ding and Lisnianski [START_REF] Ding | Fuzzy multi-state system: General definition and performance assessment[END_REF]. The results of the belief function approach will be compared to the ones obtained using the UGF 1 probability interval approach proposed by Li et al. [START_REF] Li | Interval-valued reliability analysis of multi-state systems[END_REF] 2 .

In this example, we aim to evaluate the availability of a flow transmission system design presented in Figure 8 and made of three pipes. The flow is transmitted from left to right and the performance of a pipe is measured by its transmission capacity (tons per minute). It is supposed that elements 1 and 2 have three states: a state of total failure corresponding to a capacity of 0, a state of full capacity and a state of partial failure. Element 3 only has two states: a state of total failure and a state of full capacity. All performance levels are precise.

The state performance levels and the state probabilities of the flow transmitter system are given in Table 3. In Li et al. [START_REF] Li | Interval-valued reliability analysis of multi-state systems[END_REF], these probabilities are obtained with the imprecise Dirichlet model [START_REF] Bernard | An introduction to the imprecise Dirichlet model for multinomial data[END_REF]. We aim to estimate the availability of the system when d = 1.5. The minimal paths are

p 1 = {x 1 1 , x 2 2 , x 3 2 } = {0, 1.5, 4}, p 2 = {x 1 3 , x 2 1 , x 3 2 } = {1.5, 0, 4}.
A p 1 ∩ A p 2 = {1.5} × {1.5, 2} × {4}.
Applying the inclusion-exclusion formula for a demand level d = 1.5, we obtain

Bel(φ ≥ 1.5) = Bel(A p 1 ) + Bel(A p 2 ) -Bel(A p 1 ∩ A p 2 )
For example, we have approach uses an interval arithmetic approach, which is known to provide quite conservative approximations in the presence of repeated variables (as is often the case when using the inclusion-exclusion principle).

Bel(A p 1 ) = Bel({0, 1, 1.5} × {1.5, 2} × {4}) = Bel({0, 1, 1.5}) • Bel({1.5, 2}) • Bel({4}) = 1

Comparison with strong independence

It should be noticed, as shown by Jacob et al. [START_REF] Jacob | Evaluating the uncertainty of a Boolean formula with belief functions[END_REF], that using random set independence should not be confused with an assumption of stochastic independence between ill-known probabilities. In this section, we will compare the previously used notion of random set independence to the one of strong independence, which can be interpreted as a robust version (i.e., applied to sets of probabilities) of the notion of stochastic independence. We will then discuss the effects of using one independence notion in place of the other in the previously treated problems.

construction is more constrained than the former, hence P SI ⊆ P(Bel 1:D ) (already in Couso et al. [START_REF] Couso | Independence concepts in evidence theory[END_REF]). Among other things, this implies that the lower probabilities are such that P SI (A) ≥ P m 1:D (A) for any A ⊆ X 1:D , meaning that random set independence can be used to outer-approximate strong independence. Also recall that such lower probabilities are obtained for extreme points of the set, hence for such inferences working with P SI or its convex closure P SI makes no difference.

P SI (A) = inf
The two notions also have different interpretations: random set independence can be associated to an independence of sources providing the uncertainty, making no claim about the possible interaction between variables of different marginal spaces, while strong independence can be interpreted as an extension of stochastic independence between random variables when probabilities are partially known. The next example illustrates the inequality P SI (A) ≥ P m 1:D (A) as well as how the selection process to obtain a probability reaching the lower bound is different in the two cases.

Example 7. Let X 1 = {x 1 , ¬x 1 } and X 2 = {x 2 , ¬x 2 } be two Boolean frames with [l 1 , u 1 ] = [0.6, 0.8] and [l 2 , u 2 ] = [0.2, 0.4] corresponding to the masses m 1 (x 1 ) = 0.6, m 1 (¬x 1 ) = 0.2, m 1 (X 1 ) = 0.2, m 2 (x 2 ) = 0.2, m 2 (¬x 2 ) = 0.6, m 2 (X 1 ) = 0.2,
which themselves induce probability sets P(Bel 1 ) and P(Bel 2 ). Consider now the problem of finding the lower probability of the event E = {(x 1 , ¬x 2 ), (¬x 1 , x 2 )} (corresponding to the Boolean formula (x 1 ∧ ¬x 2 ) ∨ (¬x 1 ∧ x 2 )). In the case of strong independence, this comes down to find the extreme points within P(Bel 1 ) and P(Bel 2 ) whose stochastic product induces the lowest value on P(E). This is obtained by considering p 1 (x 1 ) = l 1 = 1p 1 (¬x 1 ) = 0.6 and p 2 (x 2 ) = u 2 = 1p 2 (¬x 2 ) = 0.4 that induce

P SI (E) = p 1 (x 1 ) • p 2 (¬x 2 ) + p 1 (¬x 1 ) • p 2 (x 2 ) = 0.6 • 0.6 + 0.4 • 0.4 = 0.52.
Within the focal elements of m 1 and m 2 , these two extreme points corresponds to selections

• s X 1 = ¬x 1 that transfers m 1 (X 1 ) to ¬x 1 and • s X 2 = x 2 that transfers m 2 (X 2 ) to x 2 .
When considering random set independence, one first have to build the joint random set m 1:2 such that

m 1:2 (x 1 × x 2 ) = 0.12, m1 : 2(¬x 1 × x 2 ) = 0.04, m1 : 2(X 1 × x 2 ) = 0.04, m 1:2 (x 1 × ¬x 2 ) = 0.36, m1 : 2(¬x 1 × ¬x 2 ) = 0.12, m1 : 2(X 1 × ¬x 2 ) = 0.12, m 1:2 (x 1 × X 2 ) = 0.12, m1 : 2(¬x 1 × X 2 ) = 0.04, m1 : 2(X 1 × X 2 ) = 0.04,
and that induces the credal set P(Bel 1:2 ). We have

P m 1:2 (E) = Bel 1:2 (E) = m 1:2 ({x 1 }× {¬x 2 }) + m 1 (¬x 1 × {x 2 }) = 0.
(E) = P m 1:2 (E) is obtained for the selection • s x 1 ×X 2 = (x 1 , x 2 ) that transfers m 1:2 (x 1 × X 2 ) to (x 1 , x 2 ), • s ¬x 1 ×X 2 = (¬x 1 , ¬x 2 ) that transfers m 1:2 (¬x 1 × X 2 ) to (¬x 1 , ¬x 2 ), • s X 1 ×x 2 = (x 1 , x 2 ) that transfers m 1:2 (X 1 × x 2 ) to (x 1 , x 2 ), • s X 1 ׬x 2 = (¬x 1 , ¬x 2 ) that transfers m 1:2 (X 1 × ¬x 2 ) to (¬x 1 , ¬x 2 ) and • s X 1 ×X 2 = (x 1 , x 2 ) that transfers m 1:2 (X 1 × X 2 ) to (x 1 , x 2 ).
The joint probability p 1:2 resulting from this selection is

p 1:2 (x 1 × x 2 ) = 0.32, p 1:2 (¬x 1 × x 2 ) = 0.04, p 1:2 (x 1 × ¬x 2 ) = 0.36, p 1:2 (¬x 1 × ¬x 2 ) = 0.28,
which cannot be expressed as a product of extreme points of P(Bel 1 ) and P(Bel 2 ), and is therefore not included in P SI .

Example 7 clearly shows the difference of meaning between the two notions: in the strong independence case, fixing the element of X 1 does not influence the selection on X 2 , while in the random set independence case, obtaining the lower bound implies considering a very strong relation between the selections (e.g., fixing x 1 implies selecting x 2 whenever possible).

Consequences for Boolean formulas

Assume we have a formula F in DNF A 1 ∨ . . . ∨ A n with A i ∧ A j = ⊥, i.e. the sets of models of A i , A j are disjoint. Such formulas, in the form of a disjunction of exclusive conjunctions of literals (it can be at worst, just the disjunction of models of F) can be obtained by using the Shannon decomposition of F (the basic notion from which BDDs are derived). In this case, assuming stochastic independence between variables/atoms, the probability of F reads

P(A 1 ∨ . . . ∨ A n ) = P(F) = n ∑ i=1 [ ∏ j∈P i P(x j ) ∏ j ∈N i (1 -P(x i ))]. (24)
When the probabilities P(x i ) ∈ [l i , u i ] of atoms are incompletely known, bounds [P * (F), P * (F)] for P(F) can be obtained by interval analysis of (24) [START_REF] Jacob | Uncertainty handling in quantitative BDDbased fault-tree analysis by interval computation[END_REF]. As Equation ( 24) is a multilinear function 3 , it is locally monotone in each of its variables (it is either increasing or decreasing in P(x i ) once the probabilities of other atoms are fixed). This means that each bound P * (F), P * (F) is attained for some vertex of the hypercube × n i=1 [l i , u i ]. We have that [P * (F), P * (F)] = [P SI (F), P SI (F)], since selecting the right vertices comes down to making the right selection for each marginal, selection l i corresponding to s X i = ¬x i and u i to s

X i = x i .
This also means that, in practice, we will have [P * (F), P * (F)] = [P SI (F), P SI (F)] ⊆ [Bel 1:D (F), Pl 1:D (F)]. However, a noticeable exception is when each variable will always appear either in a positive or negative way in the expression of a Boolean formula. Proposition 9. If the logical expression F is a disjunction of conjunctive terms {A 1 , . . . , A n } such that ∀i = j, P i ∩N j = / 0 and P j ∩N i = / 0, then [Bel 1:D (F), Pl 1:D (F)] = [P SI (F), P SI (F)]

Proof. Without loss of generality, assume that all variables appear in a positive way (we just have to rename those appearing in a negative way). Consider the case of two dimensions, then the lower bound P SI (F) is reached by selecting s X i = ¬x i for i = 1, 2. Similarly, the extreme point reaching Bel 1:2 (F) for any joint set E = E 1 × E 2 is obtained by selecting negative literals whenever possible.

A similar reasoning can be used for higher dimensions and for the upper bounds.

Such a situation occurs for connectives like the conjunction, disjunction or implication, and more generally for all expressions that obey condition 2 of Proposition 8.

In such cases the choice of the dependency assumption (between variables or sources) has no influence on the output interval. The fact that in such cases the same results are obtained by both approaches does not make the belief function analysis redundant: it shows that the results induced by the stochastic independence assumption are valid even when this assumption is relaxed (the independence assumption of mass functions is indeed weaker), for some kinds of Boolean formulas.

On the contrary, expressions satisfying condition 1 of Proposition 8 correspond to non-monotonic functions, like for the Equivalence and the Exclusive Or [START_REF] Jacob | Uncertainty handling in quantitative BDDbased fault-tree analysis by interval computation[END_REF]. In this case, an exhaustive computation for all combinations of interval boundaries must be carried out in the case of interval analysis and strong independence, while the computation of the belief and plausibility are still very simple, but provably less precise than the result of interval analysis. Pl(x 1 ⊕ x 2 ) = 1 -Bel(x 1 ⇐⇒ x 2 ) = u 1 + u 2l 1 l 2u 1 u 2 = 0.8 P * (x 1 ⊕ x 2 ) = min(l 1 (1u 2 ) + u 2 (1l 1 ), l 1 (1l 2 ) + l 2 (1l 1 ), u 1 (1u 2 ) + u 2 (1u 1 ), l 2 (1u 1 ) + l 1 (1u 2 )) = 0.44

P * (x 1 ⊕ x 2 ) = max(l 1 (1 -u 2 ) + u 2 (1 -l 1 ), l 1 (1 -l 2 ) + l 2 (1 -l 1 ), u 1 (1 -u 2 ) + u 2 (1 -u 1 ), l 2 (1 -u 1 ) + l 1 (1 -u 2 )) = 0.56
Example 7 is also of this kind.

Extension to the multivariate case

Let us now deal with the non-binary case and with conditions of Theorem 5. Using the fact that P SI ⊆ P(Bel 1:D ) and Example 7, it is clear that bounds computed using P SI and P(Bel 1:D ) will not coincide if events in A n satisfy condition 2 of Theorem 5, as they already fail to coincide in the binary case. In the case of the first condition, however, we can give a result similar to Proposition 9. (25) Given the relation recalled in Section 7.1 between random set independence and strong independence, this expression coincides with P SI ( n i=1 A i ) if and only if the lower bounds Bel j (∩ A∈I A j ) on a given dimension X j are all be obtained using the same extreme point of the marginal model P(Bel j ), irrespectively of the subset I . This comes down to showing that these lower bounds can be attained, for any subset I , by a unique selection s E k in the focal elements E k ∈ F m j of m j .

Consider a given dimension j. According to condition 2 of Theorem 5, the sets A j i are nested (since for a given j and two i, k ∈ [1 : D] either A j i ⊆ A j k or A j i ⊇ A j k ). Let us re-order them increasingly according to the permutation denoted by () so that / 0 = A j (0) ⊆ A j (1) ⊆ . . . ⊆ A j (n) ⊆ A j (n+1) = X j

Consider now a focal element E k of F m j , then there is some i such that A j (i) ⊂ E k ⊆ A j (i+1) , and we then choose a selection s E k ∈ A j (i+1) \ A j (i) . This implies that s E k ∈ A (i) if and only if E k ⊆ A (i) . If we do such a selection for any E k and take the corresponding probability measure P j , we have that

P j (A j i ) = ∑ s E k ∈A j i m j (E k ) = ∑ E k ⊆A j i m j (E k ) = Bel j (A j i ).
Since P j corresponds to a single extreme point of P(Bel j ) that does not depend on the subset I , this finishes the proof.

Although such a situation will not always appear, this result directly applies to the case of monotone functions φ treated in Section 5, showing that in this particular case, choosing between assumptions of random set independence or of strong independence will not change our inferences about events of the kind {φ ≥ d} and {φ < d}. In practice, this means that in those cases we can either use tools originating from evidence theory, imprecise probability theory or interval analysis to carry out computations (whichever is the most suited to the situation).

Conclusion

In this work, we have studied families of events for which the principle of exclusion/inclusion applies to belief functions. Although the framework we have retained may look restrictive at first glance, it can be applied to a number of practical situations, and we have shown that one particular application is the evaluation of system reliability (both in the binary and multi-state cases).

Such results facilitate computations and are particularly useful when probabilistic data are imprecise. An interesting perspective to this study is to look for conditions under which other uncertainty theories (e.g., general lower probabilities) satisfy the exclusion/inclusion principle. Further potential applications of our results include the study of other problems of reliability analysis, such as importance measures used to detect critical components.

Figure 3 :

 3 Figure 3: Plausibility A 3 -additivity illustration

Figure 3 .

 3 b): such an element is counted once in the left-hand side of Equation (9), thrice in term 1, twice in term 2 and zero times in term 3 of the right-hand side, hence we can have m(E) > 0 without violating A 3 -additivity. Yet, set E is such that E

  hence 2-additivity does not hold.

Figure 5

 5 Figure 5 and 6 show various situations where conditions of Theorem 3 are satisfied and not satisfied, respectively.

Lemma 4 .

 4 Let a = (a 1 , . . . , a D ) and b = (b 1 , . . . , b D ) be two distinct elements in X . Then, {a, b} forms a minimal rectangle if and only if there is only

Definition 1 .

 1 A minimal path (MP) vector p for value d, induced by a function φ , is an element p ∈ X 1:D such that φ (p) ≥ d and φ (y) < d for any y < p. Definition 2. A minimal cut (MC) vector c for value d, induced by a function φ , is an element c ∈ X 1:D such that φ (c) < d and φ (y) ≥ d for any y > c.

3 •Figure 7 :

 37 Figure 7: Bridge system

1 2 3 Figure 8 :

 138 Figure 8: Flow transmission system

  φ (x 1 , x 2 , x 3 )

  • 0.895 • 0.958 = 0.8574 and Bel(A p 2 ), Bel(A p 1 ∩ A p 2 ) can be computed similarly. Finally we get Bel(φ ≥ 1.5) = 0.8574 + 0.7654 -0.6851 = 0.9377 and by duality with Bel(φ < 1.5), we get Pl(φ ≥ 1.5) = 1 -Bel(φ < 1.5) = 0.9523. The availability A s of the flow transmission system for a demand level d = 1.5 is given by A s = [0.9377, 0.9523]. The use of the interval UGF method proposed by Li et al. [24] leads to A s IUGF = [0.9215, 0.9855]. Note that we always have [Bel(A), Pl(A)] ⊆ A s IUGF , as the Li et al.

  ) and P m 1:D (A) = Bel 1:D (A) = inf P∈P(Bel 1:D ) P(A)

  [START_REF] Ben-Haim | Info-gap Decision Theory: Decisions Under Severe Uncertainty[END_REF] and we indeed have P SI (E) > P m 1:D (E). The extreme point of P(Bel 1:2 ) whose probability P

Example 8 .

 8 Namely, consider the Exclusive Orx 1 ⊕ x 2 = (x 1 ∧ ¬x 2 ) ∨ (¬x 1 ∧ x 2 ) and P(x 1 ) ∈ [0.3, 0.8], P(x 2 ) ∈ [0.4, 0.6]. Then Bel(x 1 ⊕ x 2 ) = l 1 (1u 2 ) + l 2 (1u 1 ) = 0.2

Proposition 10 .

 10 Let A n be a collection of events satisfying condition 2 of Theorem 5. Then, the following equality [Bel 1:D ( Bel 1:D , Pl 1:D and P SI , P SI the lower/upper bounds obtained using, respectively, the joint models P(Bel 1:D ) and P SI .Proof. If A n satisfies condition 2 of Theorem 5, we have thatBel 1:D ( n i=1 A i ) = ∑ I ⊆A n (-1) |I |+1 Bel(∩ A∈I A) = ∑ I ⊆A n (-1) |I |+1 D ∏ j=1Bel j (∩ A∈I A j ).

Table 1 :

 1 Binary reliability uncertainty.

Table 2 :

 2 Performance rates of the oil transmission system The set A p 1 and A p 2 of vectors a such that a ≥ p 1 , b ≥ p 2 are A p 1 = {0, 1, 1.5} × {1.5, 2} × {4} and A p 2 = {1.5} × {0, 1.5, 2} × {4}, and their intersection A p 1 ∩ A p 2 of vectors c such that c ≥ p 1 ∧ p 2 (with ∧ = min) is

Universal Generating Function

A comparison of Li et al.[START_REF] Li | Interval-valued reliability analysis of multi-state systems[END_REF] and Ding and Lisnianski[START_REF] Ding | Fuzzy multi-state system: General definition and performance assessment[END_REF] can be found in Li et al.[START_REF] Li | Interval-valued reliability analysis of multi-state systems[END_REF]

A multivariate function is multilinear if it is linear in each of its variables.

Acknowledgments

This work was partially carried out in the framework of the Labex MS2T (Reference ANR-11-IDEX-0004-02). C. Jacob acknowledges support by @MOST Prototype, a joint project of Airbus, IRIT, LAAS, ONERA and ISAE.

1.5 0 g j 3 1.5 2 4

Table 3: Parameters of the flow transmission system

Two distinct independence notions

So far, we have mainly considered that the joint mass over X 1:D was obtained by combining marginal masses m i using Equation [START_REF] Couso | A survey of concepts of independence for imprecise probabilities[END_REF]. It corresponds to the notion of random set independence. Yet, within the imprecise probabilistic literature, there are many other notions of independence available [START_REF] Couso | A survey of concepts of independence for imprecise probabilities[END_REF][START_REF] Couso | Independence concepts in evidence theory[END_REF], and it is out of the scope of this paper to discuss all of them. In this section, we will compare our results with those that would be obtained using a robust version of stochastic independence, usually called strong independence.

If P(Bel i ) denotes the set of probabilities compatible with m i on dimension i, then the joint model P SI obtained by applying stochastic independence to elements of P(Bel i ), i = 1, . . . , n is

Assuming strong independence consists in representing our knowledge by means of the convex hull of P SI , that we will denote by P SI . Particularly interesting elements of P SI are its extreme points, that are obtained by computing the product of extreme points of P(Bel i ), i = 1, . . . , n (hence extreme points of P SI are also in P SI ).

In the particular case where a probability set P(Bel) is induced by a mass function m on 2 X , its extreme points can be obtained in the following way: specify (select), for each focal element A ∈ F m , an element s A ∈ A and take the probability measure P such that P({x}) = ∑ A∈F m m(A)1 (s A =x) . This comes down to taking a convex mixture of Dirac measures located at s A ∈ A, weighted by masses m(A).

Let us denote by P(Bel 1:D ) the set of probabilities induced by considering the joint mass m 1:D obtained by Equation [START_REF] Couso | A survey of concepts of independence for imprecise probabilities[END_REF]. This corresponds to the random set independence assumption. To build extreme points P(Bel 1:D ), a D-tuple s E has to be specified (selected) in each set E = × D i=1 E i with E i ∈ F m i , while to build extreme points of P SI , one has to specify elements s E i within each marginal model m i , then take the product of corresponding probabilities. One can check [START_REF] Fetz | Sets of joint probability measures generated by weighted marginal focal sets[END_REF] that the latter


Frank Leipold
email: frank.leipold@eads.net

Jörg Eberspächer
email: joerg.eberspaecher@tum.de

Distributed resource reservation for beacon based MAC protocols

Wireless connected devices become increasingly popular in a large variety of applications. Consumer electronics most certainly is the field with the most wireless innovations in the past years; but also other areas, such as medical equipment, vehicular on-board networks or maintenance services, experience an increasing demand for wireless communication. Additionally the networks should just work and require as little maintenance as possible. Hence future WLAN and WPAN must be self-configuring, self-healing and distributed to provide flexible usage. Assuming a homogeneous distributed MAC protocol with a beacon based reservation mechanism, a radio resource reservation algorithm is developed to fulfil the delay and data rate requirements from the devices. It uses a game theoretic approach to achieve infrastructure-less design and still provides fair resource allocation. Changes in the radio channel, failing devices or links and mobile nodes are detected and a reorganisation of resources is calculated.

Introduction

The constantly increasing performance demands for wireless high speed connections is the motor to further enhance existing technologies and to invent new and innovative communication interfaces. For wireless local area networks (WLAN) several candidates have been developed in the past years. The recently approved IEEE 802.11n standard achieves up to 600 Mbits/s, by using MIMO (multipleinput-multiple-output) technology.

High data rates can also be easily achieved by using ultra wideband (UWB) as the bandwidth of more than 500 MHz provides plenty resources. The WiMedia standard [START_REF]ECMA-368: High Rate Ultra Wideband PHY and MAC Standard -3nd Edition[END_REF] is capable of 480 Mbit/s with one single channel. The recently published upgrade even allows 1024 Mbit/s. This is done with one single antenna (hence no MIMO), which implies less complex transceivers.

One significant difference between WiFi and high-speed UWB is the transmit range. Due to the strict power limitations of at most -41.3 dBm/MHz for UWB, defined from the FCC [START_REF] Eberspächer | Report and Order[END_REF], and mostly followed by other regulatory organisations, high data rate UWB has a typical range of about 10 meters. It also underlies more intense spatial limitations given by walls and other obstacles. This is often interpreted as a handicap of UWB, but it actually also implies two significant advantages. First it reduces the congestion in the wireless channel. For instance the IEEE 802.11b/g technology is currently often used in home applications. But the standard has only three non-overlapping channels (respectively four in Japan). Thus in apartment houses, where most flats have their own WiFi access point (AP), the channels are very crowded as the technology can achieve 20 to 100 meters transmit range even in indoor scenarios. With UWB the radio signals are almost confined to the individual apartments and the contentions for the wireless channels get relaxed. There will be less wireless systems sharing the common resources. The second advantage is the reduced risks of being eavesdropped. The attacker must be in very close proximity to successfully receive the UWB signals. Eavesdropping becomes much more difficult and the risk of falling victim to an attack declines.

Even though WiMedia is a fully distributed algorithm, without any coordinating nodes such as a WiFi-access-points, the network still has service providing access points, for instance a node that is connected to a LAN and operates as a bridge between the LAN and the WiMedia network to enable access to the Internet. These WiMedia (or UWB) APs do not have any special role in terms of the PHY or MAC protocol.

Using UWB for WLAN applications requires a larger number of APs. For the office scenario about each room requires at least one AP, depending on the size of the room. This makes the network management more complex. For now usually the WiFi networks are managed by maintenance personnel, but with a large number of APs to manage, this becomes a very complicated task. Several automated resource management algorithms for WLAN systems have been proposed yet. For WiMedia little work has been done on this subject. With its completely distributed algorithms the existing approaches can not be used efficiently.

In an earlier work [START_REF] Leipold | Requirements for Radio Resource Management in Multicell WiMedia Networks[END_REF] an integer optimization algorithm was presented to calculate the optimal AP placement and resource allocation plan for WiMedia networks. It is very complex and time consuming algorithm that will run during the design phase of the network. But during the operation of the network changes to the wireless channel will occur and a fast adaptation to the new conditions must be made. Depending on the size of the network a centralised optimisation may take too long. A distributed approach is preferred.

Our applications target wireless on-board networks for public transportation vehicles, such as aircraft. Cabin management systems, containing reading lights, signs, speakers, small displays, shall be connected wireless to reduce production and maintenance costs and to make the cabin layout more flexible. UWB currently is the most promising technology that provides a very robust radio channel for the aircraft environment [START_REF] Chuang | UWB Radiowave Propagation within the Passenger Cabin of a Boeing 737-200 Aircraft[END_REF], high data-rates and no licensing problems. Furthermore the network shall have self-healing capabilities and adapt quickly to failures and changes. Therefore the resource management algorithm should be distributed and enable the network to operate with the best possible configuration even when some parts are failing completely.

The network management of the public transportation scenario is not very different from an office environment or home consumer electronics. Therefore the gained results in this paper can be easily applied to other situations, where devices must be connected to service access points.

The rest of this paper is organised as followed. Section 2 describes features of WiMedia relevant to this work. Section 3 describes briefly game theory and some related research. In section 4 the distributed resource management algorithm is presented. Finally section 5 concludes this paper.

Unique WiMedia features

The WiMedia standard and also other possible standards that use a distributed beacon based MAC implementation, has some unique features, which are of value for the resource management.

WiMedia is completely infrastructure-less, meaning all nodes have the same physical and MAC capabilities. Unlike in other common protocols there is no coordinator or MAC level access point. The protocol uses periodic superframes containing a beacon period and a data period; see Figure 1(a). All nodes allocate a beacon slot in the beacon period, regardless if they have to transmit user data or not. This slot is fix over time and changes only in rare conditions. For DRP (distributed reservation protocol) channel access the beacons are used to announce transmissions and reserve parts of the data period, the so called MAS (media access slots). Conflicts are identified early and collisions can be mostly avoided. The only collisions may occur in the beacon slot allocation process.

The beacons contain details of all upcoming transmission in the data period. This means a single node knows when a neighbour communicates with another node. This feature makes WiMedia not susceptible to the hidden station problem and it does not need RTS/CTS messages.

With the beaconing a hard limitation of WiMedia applies. The beacon period has only 96 beacon slots with two slots reserved for special functions. This means no more than 94 nodes must be within range on the same channel. The group of nodes within transmit range of a subject node is called beacon group (BG). Each node includes the members of the BG and the respective beacon slot ids into its own beacon; hence it is broadcasting this information to the surrounding nodes. Furthermore the standard also defines the extended beacon group (EBG), which is the set of nodes representing the neighbour's neighbours. Figure 1(b) shows the BG and the EBG of a node. A newly activated node picks a beacon slot that is not occupied by a node of the BG nor from the EBG. This rule implies that for any given node the beacon slot ids of the BG members must be unique, otherwise they would cause collisions. For the EBG members the ids can be identical, because the subject node can not listen to them, but must not transmit at the same time as it would cause collision at the node that has the subject node and the EBG-node in its BG. The consequence of overlapping areas in WiMedia is the extension of the EBG. When a border node is within range of two APs, it will add parts of the second AP nodes to its BG, which again appear in the EBG of the first AP. Hence overlaps increase the extended beacon group size and therewith limit the maximal node density.

The beacon group size is directly related to the node density and transmission range as slots may only be occupied by one node. The extended beacon group size additionally depends on the activation sequence of the network, as for a single node the neighbour's neighbours beacon slots may be identical.

Game theory for resource management

For the distributed resource management algorithm presented in this work, one key feature is to have a fair resource allocation. Nodes should not act selfishness and occupy wastefully available resources. The objective of the algorithm is to maximize the overall efficiency of the network. Hence nodes must not only take their own situation into account, but also those of the surrounding nodes.

The game theory is capable of defining fair and distributed algorithms. It originates from economics in the 40's, but has also been applied to biology, engineering, political science, computer science, and philosophy. The problem is defined in a strategic game with a set of rational players. Each player tries to maximise its payoff function by choosing the best strategy and also by taking the actions of the other players into account. Usually the players strategies will result in an equilibrium, for instance the Nash equilibrium, where no player can change the own strategy without decreasing its payoff. Many different types of games have been developed: cooperative or non-cooperative, symmetric or asymmetric, zero-sum or non-zero-sum, simultaneous or sequential, just to name a few.

Game theory has been proposed for resource management in wireless networks for all kinds of technologies. For IEEE 802.11 the authors of [START_REF] Berlemann | Radio resource sharing games: enabling QoS support in unlicensed bands[END_REF] present a game to share the available radio channels. The payoff function based on transmission delay, channel access length and throughput. In [START_REF] Han | Power minimization for multi-cell OFDM networks using distributed non-cooperative game approach[END_REF] an algorithm for OFDM based communication is described that minimizes the transmission power, while still achieving the QoS requirements of the system. For IEEE 802.16 networks [START_REF] Niyato | Radio resource management games in wireless networks: an approach to bandwidth allocation and admission control for polling service in IEEE 802.16[END_REF] presents a game definition to control the amount of bandwidth given to new connections, with respect to delay, throughput and other QoS parameters in the network.

Even though the amount of available resource management algorithms based on game theory is huge, no one handles a comparable system to that of a Wi-Media network. The distributed beaconing mechanism and DRP channel access scheme is unique. The priority for a WiMedia network lies in the efficient MAS allocation. To utilise the WiMedia features a new resource management algorithm is required.

Algorithm

The resource management algorithm assumes APs with fix locations. Furthermore the network consists of a wired backbone that connects the APs. The APs provide the service for wireless end devices to get access to the wired back bone network.

The MAC mechanism for the WiMedia nodes shall be DRP. For the aircraft scenario DRP is essential, as it provides guaranteed resources to the end devices. The QoS requirements for end devices are defined in required data rate and maximum time delay. Assuming only one MAS is reserved per end device and taken into account the 64 ms of a superframe, the delay of an message over the UWB link can be nearly 64 ms. For applications with smaller delay requirements, the resource management algorithm must reserve two or more MAS per end device with maximum gaps between the MAS. The possible delays will be reduced.

Despite the mentioned DRP reservation scheme the network may also use the alternative channel access PCA (prioritized contention access) for non critical applications. MAS that are not completely used by the owing device can be released and used for PCA, a CSMA like access scheme. This way the unused MAS sections can still be used for applications where collisions can be tolerated.

The following two lists show input and output parameters of the algorithm:

Input parameters • Link quality • Devices per AP • BG/EBG size • Bandwidth utilisation • Delay requirements Output parameters • Channel allocation • MAS reservation
The link quality is given in RSSI (received signal strength indicator) or LQE (link quality estimator). Both are defined in the WiMedia standard and should be accessible from the application layer.

It is assumed that an optimal configuration of the network is known. This can be obtained from calculations in the design phase of the network. These calculations are usually very intensive and take a long time. Therefore they can not be performed in-time during the operation of the network.

Efficiency in a WiMedia network using DRP can be defined as the configuration with the minimal used MAS, which again implies the minimal usage of resources and maximum remaining bandwidth. In the following notation O n stands for the number of owned MAS from node n. A node owns a MAS when it has reserved this MAS for transmissions or reception in the beacon period. R n stands for the number of reserved beacon slots in the beacon period of node n. This can be own MAS, MAS owned by surrounding nodes or MAS marked as occupied from alien nodes. Furthermore the raised indices o and e indicate if the value is the optimal solution, or the effectively current allocation. Finally the second raised indices r or i show if the value must be an integer or a real. The integer notation represents the number of owned or reserved MAS. The real notation indicates how much of that MAS will actually be used according to the data rate requirements. Two examples will demonstrate the notation: O o,i n are the owned MAS slots by node n for the optimal solution and integer counting, R e,r n are the effectively used MAS of node n in real counting. The effectiveness of the nodes is defined in two different ways. For the end devices the effectiveness is:

E ED n = O o,r n O e,r n 0, if data rate or delay requirements fail (1)
An effectiveness of 1 is the optimal solution; for sub-optimal solutions the numerator increases and the effectiveness closes zero. The notation in real values is used, to get a difference in the equations for increased transmit data rates, but still only using one MAS. For instance a node with low bandwidth requirements must always reserve at least one MAS. This can mean that even for the lowest possible and highest possible data rate still only one MAS is required. To reward nodes switching to a higher transmit data rate and thereby less occupy the channel, a real notation for the number of owned MAS is used. A higher data rate E ED n will change the efficiency of that end device to the positive. For APs the effectiveness uses the sum of the number of used MAS (integer counting). An AP has to maintain reservations to the end devices, which can only be done in complete MAS slots. Consider a node with low bandwidth requirements, but strict timing delays. Optimally it could operate with two MAS slots. But due to already existing reservations no combination of two MAS might be available to satisfy the timing requirements. Hence a combination of three MAS must be used. If using the real counting of MAS, as for the end devices, no difference of the AP effectiveness would be measurable; the summed effectively used MAS portion would stay the same. But with the integer counting the extra MAS is measurable. The effectiveness of an AP is defined as:

E AP n =        R o,d n R e,d n R o,d n AR e,d n
, if 90-100% of the available MAS required 0, if more than 100% of the available MAS required

(2)
The parameter A in the numerator for the case of 90-100% MAS utilisation must be greater 1. It artificially degrades the efficiency and prevents an AP of being overloaded and shifts AP assignments from end devices to surrounding APs if possible.

The utility function of each node is the sum of the efficiency of all nodes (end devices and APs) within range. Each node tries to maximize the utility function. For an end device the utility function is:

U n = E ED n + o∈D E ED o + p∈A E AP p (3)
For an AP the utility function is:

U n = E AP n + o∈D E ED o + p∈P E AP p (4)
D is the set of end devices on the same channel that are in range of node n. In analogue P is the set of APs on the same channel in range of node n.

Each node (AP and end device) has an algorithm implemented to calculate the MAS reservations, depending on the selected channels. This algorithm takes the APs as subject nodes and iterates the end device nodes in range and on the same channel. The end device with the earliest delay requirement will be served first and gets assigned the closest MAS to or below the delay. This is repeated, until all nodes have enough MAS to satisfy the delay, afterwards random MAS are assigned, to match possible data rate requirements. Each node must have at least one MAS per superframe.

To provide the required information of the surrounding nodes, the QoS requirements, neighbourhood relation and currently superframe structure is exchanged on a two-hop distance.

Each end device can choose which AP in range it selects. The decision uses the utilisation function. An end device compares the existing utilisation value and the to be obtained value when changing the AP by calculating the MAS reservations and utilisation value of the new setup. An access point change is only done, when an utilisation gain exists.

Analogous the APs also recalculate the MAS reservation and utility value, with changing channel selection.

Finally the processes for the end devices and APs of the distributed resource management algorithm based on game theory are as followed:

End device 1. Scan all channels for APs 2. Calculate MAS reservations and U n for channels with APs in range 3. Select the channel with the best U n 4. Periodically rescan other channels Access point 1. Select channel (no AP or AP with worst RSSI) 2. Try to increase U n by investigating possible channel change 3. Select channel with best U n 4. Periodically recalculate Mobile nodes are also supported. Therefore the optimal solution is calculated without them. Later, the mobile nodes are included in the system as a regular end device. They will leads to a constantly higher utilisation value, but still the algorithm finds the same fair solution.

Conclusions

In this work a resource management algorithm based on game theory for high data rate UWB networks was presented. The network consists of service access points, which provide access for wireless end devices to a wired network, such as LAN or Internet. The algorithm achieves a fair distribution of resources and adapts to changes in the radio channel or topology. Network efficiency is based on the number of used MAS slots, which also encompass bandwidth and timing requirements. The MAS reservation algorithm is essential for scenarios with high MAS utilisation, as the efficiency of the overall algorithm is tightly coupled to the efficiency of the MAS reservation for large loads.

The distributed approach does not require a dedicated node to compute the network parameters. Hence whatever parts of the network are failing, the network still tries to connect as many nodes to the APs as possible. The algorithm can be used in various applications: on-board networks, office and home WLAN or ad-hoc communication.

Fig. 1 .

 1 Fig. 1. WiMedia beacon groups: Figure (a) shows the beacon period and data period of a superframe. In (b) the relation of the beacon group and the extended beacon group are shown.