Nathalie Chetcuti-Sperandio

Sylvain Lagrue

How to Choose Weightings to Avoid Collisions in a Restricted Penalty Logic

Penalty Logic is a natural and commonsense Knowledge Representation technique to deal with potentially inconsistent beliefs. Penalty Logic allows some kind of compensation between different pieces of information. But one of the main and less studied flaws of Penalty Logic is the influence of the choice of weights on inference: the same pieces of information can provide extremely different results just by changing some weights. This paper concentrates on weightings and on the problem of collisions between interpretations which yield weak conclusions. It focuses more particularly on a family of weightings, the σ-weightings. We show that some of these weightings avoid collisions but that in the meanwhile they disable the mechanism of compensation (and so the interest) of Penalty Logic. We establish then that two of them are suitable for avoiding collisions and maintaining compensation. We obtain their logical characterizations while considering the weightings only and not the associated formulas. Finally, we propose an original weighting, the Paralex Weighting, that improves even more the previous weightings.

Introduction

Penalty Logic is a natural and commonsense Knowledge Representation technique to deal with potentially inconsistent beliefs. It has been proposed in [START_REF] Pinkas | Propositional non-monotonic reasoning and inconsistency in symmetrical neural networks[END_REF]1995) and developed in (Dupin de [START_REF] De Saint-Cyr | Penalty logic and its link with dempster-shafer theory[END_REF]. Penalty logic provides an intuitive framework to deal with weighted formulas. A penalty is associated with each interpretation: this penalty is the sum of the weights of the formulas falsified by the interpretation. Thus, the main characteristic of this formalism is its ability to compensate by additivity of the weights: if the most preferred piece of information is falsified by an interpretation, the interpretation is not automatically rejected.

However this formalism is well-known to be syntaxdependent as far as formulas are concerned. Moreover, one of the main and less studied flaws of Penalty Logic is the influence of the choice of weights on inference: the same pieces of information can provide extremely different results just by changing some weights. But an expert cannot take into account the processes of compensation and Copyright c 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. deduction of Penalty Logic when he encodes his beliefs: when they do not represent an additive measure (such as money), the weights he provides are often artificial. It is easier for an expert to represent a cost than the reliability of testimonies, opinions or judgments. Many qualitative methods have been provided to deal with prioritized information only (without any weight). Different strategies can be applied, like best-out ordering [START_REF] Benferhat | Inconsistency management and prioritized syntax-based entailment[END_REF], discrimin ordering [START_REF] Brewka | Preferred subtheories: an extended logical framework for default reasoning[END_REF][START_REF] Geffner | Default Reasoning: Causal and Conditional Theories[END_REF][START_REF] Benferhat | Inconsistency management and prioritized syntax-based entailment[END_REF], leximin ordering [START_REF] Lehman | Another perspective on default reasoning[END_REF][START_REF] Benferhat | Inconsistency management and prioritized syntax-based entailment[END_REF] or linear ordering [START_REF] Nebel | Base revision operations and schemes: semantics, representation and complexity[END_REF]. But none of these formalisms allows compensation like Penalty Logic: falsifying several formulas of less importance can be equal to falsifying a formula of greater importance. Moreover, none of these methods treats the central problem of this paper: collision avoiding.

This paper concentrates on weightings and on the problem of collisions between interpretations. Two interpretations are said to collide if their κ-values (the value of the κ-function associated with the interpretations) are equal. In this case, interpretations cannot be sorted out and the conclusion can be excessively cautious. If two interpretations falsify formulas of different importance, they should ideally have different κ-values in order to avoid weak conclusions. We show in this paper how to improve the results of Penalty Logic just by considering the choice of weightings.

This paper provides a survey of different natural weightings that can automatically be generated from the initial weighted beliefs provided by the expert. We show that some of these weightings increase the risk of collision. Others avoid collisions but in the meanwhile they disable the mechanism of compensation (and so the interest) of Penalty Logic. We study more particularly a family of weightings, the σ-weightings. We establish then that two of them are suitable for avoiding collisions and maintaining compensation. We obtain their logical characterizations while considering these weightings only and not the associated formulas. But they compare interpretations with respect to the minimal (least important) formulas that they falsify. That is the reason why we propose finally an original weighting, called Paralex Weighting, that solves this problem.

The first section provides some usual methods for dealing with ranked information and Penalty Logic. The second section presents the problem of collisions for Penalty Logic and provides a complete study of a natural weighting: Arithmetic Weighting. The next section proposes a survey of different possible weightings and focuses more particularly on a family of weightings, the σ-weightings. We show that three of them, 2-repetition, Parabolic Weighting and Paralex Weighting lead to interesting properties in terms of collision avoiding and compensation.

Preliminaries

In this paper, we consider a finite propositional language L composed of atoms a, b, ... and of the usual connectives ∨, ∧, →, ↔ (representing respectively conjunction, disjunction, material implication and equivalence). The set of interpretations (or possible worlds) based on L is denoted by Ω and ω represents one element of Ω. The logical consequence is denoted by |= and the set of models of a formula ϕ is denoted by M od(ϕ), i.e. M od(ϕ) = {ω ∈ Ω : ω |= ϕ}. The symbol ⊤ represents a formula that is always true (M od(⊤) = Ω) and the symbol ⊥ represents a formula that is always false (M od(⊥) = ∅).

Ranked Belief Bases and Penalty Logic

The basic considered inputs for Penalty Logic are ranked belief bases. A ranked belief base B is a set of weighted formulas such that B = { ϕ i , r i }. Weights take their values into the set of positive integers N. The greater is the weight, the more important is the formula. Weight +∞ is devoted to express integrity constraints, i.e. formulas that cannot be violated.

From a ranked belief base B, one can define a weighting on interpretations by considering the weights of the formulas that they falsify. Definition 1 (κ-functions) Let B be a ranked belief base. A κ-function is a function that maps Ω to N ∪ {+∞} such that:

κ ⊙ (ω) = 0 if ω |= B *
ϕ,r ∈F alse B (ω) r elsewhere where B * is the weight-free counterpart of B. ⊙ represents a given numeric operator and F alse B (ω) = { ϕ, r ∈ B : ω |= ϕ}.

From a κ-function, a total preorder on the set of interpretations Ω can be defined as follows:

ω ≤ κ⊙ ω ′ iff κ ⊙ (ω) ≤ κ ⊙ (ω ′ ).
Contrary to formulas, the least interpretations are the preferred ones. Hence propositional semantic consequence can be extended: a formula is a consequence of a ranked belief base, if and only if its models contain all the κ-preferred models. More formally: Definition 2 Let B be a ranked belief base and ϕ a propositional formula, then:

B |= κ⊙ ϕ iff M in(Ω, ≤ κ⊙ ) ⊆ M od(ϕ).
The main two operators that can be found in the literature are the max operator (max) and the sum operator (Σ). The first one provides the semantics of Ordinal Conditional Functions [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic state[END_REF][START_REF] Williams | Transmutations of knowledge systems[END_REF]) and the semantics of Possibilistic Logic [START_REF] Dubois | Possibilistic logic[END_REF], the second one provides the semantics of Penalty Logic [START_REF] Pinkas | Reasoning, nonmonotonicity and learning in connectionist networks that capture propositional knowledge[END_REF][START_REF] De Saint-Cyr | Penalty logic and its link with dempster-shafer theory[END_REF]. The preorder on interpretations induced by κ max is equivalent to the best-out ordering [START_REF] Benferhat | Inconsistency management and prioritized syntax-based entailment[END_REF]. Actually, when considering operator max, the weighting is not really important: only the relative order between interpretations is significant.

Example 3 Let B be a ranked belief base such that B = {(a ∧ b, 3), (¬a, 2), (¬b, 1)}. Table 1 summarizes the different κ-functions using respectively max and Σ operator.

ω i ∈ Ω a b κ max (ω i ) κ Σ (ω i ) ω 0 0 0 3 3 ω 1 0 1 3 4 ω 2 1 0 3 5 ω 3 1 1 2 3 Table 1: Example of κ max (ω) and κ Σ (ω)
For instance, ω 1 falsifies two formulas ((a ∧ b, 3) and (¬a, 2)), then κ max (ω 1 ) = 3 and κ Σ (ω 1 ) = 3 + 2 = 5. κ max induces the following orders on the set of interpretations:

ω 3 < κmax ω 0 ≈ κmax ω 1 ≈ κmax ω 2 , whereas κ Σ induces: ω 3 ≈ κΣ ω 0 < κΣ ω 2 < κΣ ω 1 .
We have, for instance, B |= κmax a, because:

M in(Ω, ≤ κmax ) = {ω 3 } ⊆ {ω 2 , ω 3 } = M od(a).
Moreover, we have B |= κΣ a ∨ ¬b, because:

M in(Ω, ≤ κΣ ) = {ω 0 , ω 3 } ⊆ {ω 0 , ω 2 , ω 3 } = M od(a∨¬b).
Note that in the general case, there is no link between both orders and the obtained conclusions can be completely disjoint. Possibilistic logic provides more stable result (i.e. it is less affected by a modification of the weights), whereas Penalty Logic considers the lowest strata and is less affected by the problem of inheritance blocking and by the drowning problem [START_REF] Benferhat | Inconsistency management and prioritized syntax-based entailment[END_REF]. In Possibilistic Logic, an interpretation falsifying the most important formula is automatically excluded whereas in Penalty Logic, it can be saved.

The sum operator is the key component of the semantics of Penalty Logic [START_REF] Pinkas | Reasoning, nonmonotonicity and learning in connectionist networks that capture propositional knowledge[END_REF][START_REF] De Saint-Cyr | Penalty logic and its link with dempster-shafer theory[END_REF] and the preorder between interpretations induced by κ Σ strongly depends on the provided weights.

In the remainder of this paper, we only consider the sum operator, therefore we write κ for κ Σ .

Repeating the Information

Penalty Logic is well-known to be syntax-dependent. Contrary to Possibilistic Logic for instance, the repetition of information may have an impact on the provided inferences. We will illustrate the influence of repeating information with an example, but we need first to define the semantic equivalence between two ranked belief bases. Two ranked belief bases are said to be semantically equivalent if and only if they induce the same κ-function. More formally: Definition 4 Let B 1 and B 2 be two ranked belief bases and κ B1 (resp. κ B2 ) the κ-function associated with B 1 (resp. B 2 ). Then B 1 is said to be semantically equivalent to B 2 , denoted by B 1 ≡ κ B 2 , iff:

κ B1 = κ B2 .
Example 5 Let B 1 , B 2 and B 3 be three ranked belief bases such that:

B 1 = { a, 4 , b, 4 , a, 2 , ¬a ∨ ¬b, 1 } B 2 = { a, 6 , b, 4 , ¬a ∨ ¬b, 1 } B 3 = { a ∧ b, 4 , a, 2 , ¬a ∨ ¬b, 1 }
Table 2 shows the three κ-functions associated with each ranked belief base. One can remark that B 1 and B 2 are semantically equivalent, but B 3 is neither equivalent to B 1 nor to B 2 .

ω i ∈ Ω a b κ B1 (ω i ) κ B2 (ω i ) κ B3 (ω i ) ω 0 0 0 10 10 6 ω 1 0 1 6 6 6 ω 2 1 0 4 4 4 ω 3 1 1 1 1 1 Table 2: κ B1 , κ B2 and κ B3
The previous example illustrates two characteristics of Penalty Logic. The first one is that when the same formula appears several times with different weights, one can replace these occurrences with the formula coupled to the sum of its weights without changing the induced κ-functions (see B 1 and B 2 Example 5).

Moreover we only consider in this paper sets of couples ϕ, r . Actually, Penalty Logic can be defined more widely on multisets (or bags) of weighted formulas. But each repetition of couples can be replaced with only one equivalent weighted formula without any change on κfunction.

The second feature of Penalty Logic is that, contrary to Possibilistic Logic, two different formulas with the same rank cannot be replaced by the conjunction of these formulas (see B 1 and B 3 in Example 5): Penalty Logic is very dependent on the syntax (see [START_REF] Konieczny | Reasoning under inconsistency: The forgotten connective[END_REF] for a global discussion on the difference between the two connectors: "∧" and ",").

How to Choose a Weighting ?

As mentioned in the introduction, the conclusions obtained by Penalty Logic from a ranked belief base are strongly dependent on the chosen weights. But an expert cannot take into account the processes of compensation and deduction of Penalty Logic when he encodes his beliefs: the weights he provides are often artificial. For instance, it is easier for an expert to provide only an order between his beliefs, or consecutive positive natural numbers (like 1, 2, 3, 4, ...) to express the reliability on each pieces of belief of information.

On the Incidence of the Weighting

Let us illustrate the incidence of the weights by considering a ranked belief base B such that B = { a ∧ b, 3 , ¬a, 2 , ¬b, 1 }. Three possible weightings induced by B and preserving the order between the weights are described in table 3.

W B1 W B2 W B3 a ∧ b 3 4 4 ¬a 2 2 3 ¬b 1 1 2 Table 3: Compatible Weightings
From them, we define W B , which is the ordered set of the weights that appear into a ranked belief base:

W B = {r : ϕ, r ∈ B}.
The first weighting is a "natural" weighting: if there are n different strata, then the preferred stratum is associated with n, the next one with n-1 and so on. The second weighting is a "power" weighting: the least preferred stratum has weight 1, while the next one is associated with the double of the previous stratum and so on. The last weighting is just a shift of the first weighting (1 was added to each weight).

These three ranked belief bases induce three different κfunctions given in Table 4. They are obviously not semantically equivalent. Moreover, the three κ-functions produce three different sets of conclusions: {ω 0 , ω 3 }, {ω 3 } and {ω 0 }. From the second set, one can deduce a, from the third one, one can deduce ¬a and from the first one, one can deduce neither a nor ¬a.

a b κ W B 1 κ W B 2 κ W B 3 ω 0 0 0 3 4 4 ω 1 0 1 4 5 6 ω 2 1 0 5 6 7 ω 3 1 1 3 3 5 Table 4: induced κ Wi

On the Incidence of Collisions

According to Definition 2, the inference of Penalty Logic is based on the interpretations that have a minimal κ-value. The greater is the set of κ-minimal interpretations, the poorer and less informative are the inferences produced: all the inferred information have to contain all the κ-minimal interpretations. Intuitively, the set of preferred interpretations has to be as small as possible in order to be as precise as possible.

Let B be a ranked belief base, and ω, ω ′ be two interpretations, then ω and ω ′ collide iff:

κ(ω) = κ(ω ′ ).
If two interpretations falsify exactly the same formulas, by definition of κ, they have the same κ-value. On the contrary if they falsify formulas of different importance, they should ideally be associated with different κ-values, in order to avoid collisions. This notion of Collision Freedom can be characterized as follows:

(C CF ) ∀ω, ω ′ ∈ Ω, κ(ω) = κ(ω ′ ) iff F alse B (ω) = F alse B (ω ′ ). 1
Note that, by definition, weight 0 can never be involved in a collision: two interpretations violating no formula have a 0 weight and falsify the same set of formulas -the empty setso they cannot be in collision. We illustrate this concept of collision with the following example.

Example 6 Let B be a new ranked belief base such that

B = { a ∨ b, 6 , a ↔ b, 4 , ¬a, 3 , ¬b, 2 , ¬a ∨ ¬b, 1 , a ∧ ¬b, 1 }. Table 5 represents the induced κ- function κ B . a b κ B ω 0 0 0 7 = 6 + 1 ω 1 0 1 7 = 4 + 2 + 1 ω 2 1 0 7 = 4 + 3 ω 3 1 1 7 = 3 + 2 + 1 + 1

Table 5: An extreme example of collision

In this case, all the interpretations collide and one can only deduce ⊤ from B, which is the poorest possible inference.

In the previous example all the interpretations are considered equally preferred. However, two of them (ω 0 and ω 2 ) falsify less formulas than the others. Considering these interpretations only, one can deduce ¬b. This remark leads us to introduce the criterion of Majority Preservation:

(C MP ) |F alse B (ω)| < |F alse B (ω ′ )| implies ω < κ ω ′ ,
where |E| represents the cardinality of the set E. This criterion states that an interpretation falsifying less formulas than another one must be preferred: it allows some kind of compensation, like Penalty Logic.

A Study Case: Arithmetic Weighting

In order to leave out the logical structures of information and consider only the weighting, we impose the following restriction in the sequel of this paper: each weight appears only one time in a given base. In other words, two formulas cannot have the same weight. The expert can only express that two formulas are considered equally preferred by combining them with a conjunction. The expert can be proposed a set of weights, denoted by W n , from which he can choose the weights for his n formulas.

From a weighting W n , we can compute all the possible values mapped to a κ-function. This set of values, denoted by W n Σ , is such that, for each n ≤ |A|:

W n Σ = a∈A a : A ⊆ W n .
Note that, since weightings are applied to formulas, not to interpretations, the weight 0 has no interest: it does not occur in the calculus of penalties, so it does not belong to the considered weightings.

Studying possible collisions is equivalent to searching for different sums of elements of W n (standing for different sets of formulas) leading to the same value.

A natural idea in order to choose a weighting is to consider the sequence of the first n positive integers, corresponding to n proposed formulas:

W arith,n = (1, 2, 3, 4, ..., n).
This weighting is called Arithmetic Weighting, because it derives from an arithmetic progression. The most preferred formula is associated with n while the least preferred formula is associated with 1. As a matter of fact, this naïve weighting is one of the worst weightings in terms of collisions. Figure 1 presents the number of collisions for each possible value with n = 17. Notice that this curve characterizes a binomial law and that values 76 and 77 can be obtained by exactly 2410 different summations.

It can be shown that the maximal number of collisions occurs for the median of W arith,n Σ = (1, 2, 3, ..., n(n + 1)/2), namely ⌊n(n + 1)/4⌋, where ⌊x⌋ is the integer part of x.

(1 + x)(1 + x 2 )(1 + x 3 )...(1 + x n ).
For instance, let n = 4. The expansion of (1 + x)(1 + x 2 )(1 + x 3 )(1 + x 4 ) is:

1 + x + x 2 + 2x 3 + 2x 4 + 2x 5 + 2x 6 + 2x 7 + x 8 + x 9 + x 10 .
The monomial 2x 3 means that there are two ways to produce 3.

It can be easily shown that, for any n, only six values do not lead to collision: 0 (representing the case where no formula is falsified), 1, 2 and, symmetrically,

n i=1 i = n(n + 1), n-2 i=1 i and n-1 i=1 i.
All the other values are obtainable by at least two different summations of weights, thus leading to collision. Although often used, Arithmetic Weighting is not a suitable weighting for the criterion of Collision Freedom.

The family of σ-weightings

The previous section shows that arithmetic weighting is too naïve and leads to poor and less informative results in terms of inference.

We gather in this section weightings that have common properties and we call this family the σ-weightings. Each member of this family is built upon a σ-sequence, the elements of which are summations of preceding elements. A σ-sequence is itself based on a sequence Φ which gives the number of elements to sum. Following is the generic definition of a σ-sequence:

σ = σ 1 = 1, σ i = i-1
j=i-Φi-1 σ j . where Φ i is the i th term of the sequence Φ.

Let us illustrate this family with a well-known sequence: Fibonacci numbers.

Example 7 (Fibonacci numbers) Let us consider the following sequence:

Φ F ibo = (1, 2, 2, 2, 2, 2, 2, ...).
We can compute the σ-sequence based on Φ F ibo and denoted by σ F ibo : σ F ibo = (1, 1, 2, 3, 5, 8, 13, 21, ...).

For instance, to compute σ

F ibo 3 , we consider Φ F ibo 2 = 2 and compute 2 j=3-2=1 σ j = σ F ibo 1 + σ F ibo 2 = 1 + 1 = 2.
This sequence happens to be the Fibonacci numbers. Similarly the sequence Φ T ribo = (1, 2, 3, 3, 3, ...) generates the sequence often called Tribonacci numbers, in which each element is the sum of its three predecessors.

Note that in the general case neither Fibonacci numbers nor Tribonacci numbers have good properties as regards collisions, since every weight (except the first ones) is the sum of the two (or three) previous weights.

Lexicographic sequence

We study in this section another sequence based on: , 2, 3, 4, 5, 6, ...).

Φ lex = (1
This sequence can be computed directly, without any iteration, with the simple relation: Φ lex i = i. The σ-sequence generated from Φ lex can directly be used as a weighting: , 2, 4, 8, 16, 32, 64, 128...).

σ lex = (1
In this case, we obtain the successive powers of 2 and Penalty Logic turns out to have exactly the same behavior as Lexicographic Inference [START_REF] De Saint | Gestion de l'évolutif et de l'incertain en logiques pondérées[END_REF]. An interpretation ω is preferred to another interpretation ω ′ if and only if ω and ω ′ falsify the same weighted formulas down to some weight r, where ω ′ falsifies a formula satisfied by ω.

More formally:

Proposition 8 Let B be a ranked belief base such that |B| = n and such that

W B = {σ lex i : i ≤ n}. Then, κ B (ω) < κ B (ω ′ ) iff ∃r such that: (i) ϕ, r ∈ B and ω |= ϕ but ω ′ |= ϕ (ii) ∀ ϕ, r ′ ∈ B such that r ′ > r, ω |= ϕ iff ω ′ |= ϕ.
As a corollary of this proposition, any ranked belief base B such that W B = σ lex n is collision-free. Actually if two interpretations falsify different sets of formulas, their κ-values are the sums of different powers of 2.

Proposition 9 Let B be a ranked belief base such that

|B| = n and W B = {σ lex i : i ≤ n} then B satisfies C CF .
This weighting avoids collisions but in the meanwhile it disables the mechanism of compensation (and so the interest) of Penalty Logic, as it is shown by the following example.

Example 10 Let B be a ranked belief base such that 6 gives the induced κ-function. a b κ B ω 0 0 0 14 = 8 + 4 + 2 ω 1 0 1 13 = 8 + 4 + 1 ω 2 1 0 24 = 16 + 8 ω 3 1 1 16 = 16

W B = {σ lex i : i ≤ 5} and B = { ¬a, 16 , a ∧ b, 8 , a, 4 , a ∨ b, 2 , a ∨ ¬b, 1 }. Table

Table 6: Lexicographic Weighting

The two preferred interpretations are the interpretations that falsify as many formulas as possible, namely ω 0 and ω 1 . One can observe that ω 3 is rejected whereas it falsifies only one formula (¬a), which, moreover, is not a constraint integrity.

We introduce now three weightings that avoid collisions and allow some kind of compensation.

2-repetition sequence

We first present a σ-sequence initially proposed in [START_REF] Stern | Aufgaben[END_REF] for Weighted Voting Systems. It is based on the following generating sequence: , 2, 2, 3, 3, 4, 4, 5, 5, ...).

Φ rep = (1
This sequence contains consecutively all the integers repeated twice, except for 1. Any term of this sequence can be computed directly with the following formula: Φ rep i = 1 + ⌊i/2⌋. The first terms of the corresponding σ-sequence are: , 2, 3, 6, 11, 22, 42, 84, 165, 330, 654, 1308, ...).

σ rep = (1, 1
This sequence increases more quickly than Fibonacci Numbers. We do not use this sequence directly as a weighting, but use instead sums of its elements to build one:

W rep,n i = n j=n-i+1 σ rep j .
In other words, if one needs n different weights, σ rep n is associated with the lowest weight, σ rep n +σ rep n-1 with the second lowest one and the greatest weight is the sum of all σ rep i such that i ≤ n. The weighting W rep,n is a powerful weighting: not only does it satisfy C CF , but it also allows compensation by satisfying the criterion C M P .

Proposition 11 Let B be a ranked belief base such that |B| = n and W B = W rep,n then B satisfies C CF and C M P .

An unexpected result occurs when two interpretations falsify exactly the same number of formulas. Then these interpretations are ordered with respect to the minimal weight of the different formulas they falsify. This is the criterion of Reverse Lexicographic Cardinality.

(C RLC ) if |F alse B (ω)| = |F alse B (ω ′ )| then ω < κ ω ′ iff min{r : ϕ, r ∈ F alse B (ω) \ F alse B (ω ′ )} < min{r ′ : ϕ ′ , r ′ ∈ F alse B (ω ′ ) \ F alse B (ω)}.
Proposition 12 Let B be a ranked belief base such that |B| = n and W B = W rep,n then B satisfies C RLC .

Let us illustrate these propositions with the following example.

Example 13 (continued) Let us again consider the same ranked belief base B as in Example 10, with the same order between formulas, but with a different weighting, based on W rep,n . As W rep,5 = {6, 9, 11, 12, 13}, now B = { ¬a, 13 , a ∧ b, 12 , a, 11 , a ∨ b, 9 , a ∨ ¬b, 6 }. Table 8 provides the induced κ-function.

The order between interpretations induced by the κfunction is more convincing. They are ordered with respect to the number of formulas they falsify first. Hence, the preferred interpretation is ω 3 . a b κ B ω 0 0 0 32 = 12 + 11 + 9 ω 1 0 1 29 = 12 + 11 + 6 ω 2 1 0 25 = 13 + 12 ω 3 1 1 13 = 13

Parabolic Sequence

The parabolic sequence has been proposed more recently [START_REF] Alvarez Rodriguez | Étude des propriétés d'une suite numérique liée à un problème de vote pondéré[END_REF]. The aim of the Parabolic Weighting is to refine the 2-repetition sequence to provide a minimal collision-free weighting. This weighting is based on a well-known sequence, the Parabolic Sequence. , 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ...).

Φ parab = (1
Each integer n in this sequence appears n times. One remarks that this sequence is equivalent to Φ rep for their first five terms, but then Φ parab increases much more slowly than 2-repetition sequence. Each element of this sequence is directly computable with the following formula: [START_REF] Knuth | The Art of Computer Programming[END_REF]). Historically the name of Parabolic Sequence comes from this formula. The first terms of the associated σ-sequence are: 1, 2, 3, 6, 11, 20, 40, 77, 148, 285, 570, ...).

Φ parab i = ⌊(1 + √ 8i -7)/2⌋
σ parab = (1,
The construction of the weighting induced by Φ parab is similar to the construction of the weighting W rep,n :

W parab,n i = n j=n-i+1 σ parab j .
Table 9 presents the Parabolic Weighting from 1 to 9 formulas. The first six lines are identical to 2-repetition weighting first six lines, but the weightings diverge for n > 5. Moreover, one remarks that for n > 5, W parab,n is lesser than W rep,n . In fact, it has been shown in [START_REF] Alvarez Rodriguez | Étude des propriétés d'une suite numérique liée à un problème de vote pondéré[END_REF] that the first weight of W parab,n is the minimal first weight for a collision-free weighting with n elements: one cannot find a collision-free weighting with a lesser first element. Next, we present a weighting that satisfies a more natural criterion: the criterion of Lexicographic Cardinality.

n W parab,

Paralex Weighting

The criterion C RLC is not satisfactory. It would be more intuitive to consider the most important formula falsified by an interpretation in order to decide between two interpretations falsifying the same number of formulas. We provide in this section an original weighting that compares interpretations falsifying the same number of formulas with respect to the maximal falsified formula. This property is represented by the following criterion of Lexicographic Cardinality:

(C LC ) if |F alse B (ω)| = |F alse B (ω ′ )| then ω < κ ω ′ iff max{r : ϕ, r ∈ F alse B (ω) \ F alse B (ω ′ )} < max{r ′ : ϕ ′ , r ′ ∈ F alse B (ω ′ ) \ F alse B (ω)}.
Obviously, 2-repetition and Parabolic Weightings do not satisfy this property. For this purpose, we build another weighting, W paralex,n upon σ parab :

W paralex,n 1 = n j=⌊(n+1)/2⌋ σ parab j , W paralex,n i = W paralex,n i-1 + σ parab i-1 .
Indeed, the Paralex Weighting W paralex,n is related to Parabolic Sequence. It starts with the sum of the first elements of σ parab , then for each weight its successor is the sum of the current weight with the current element of σ parab . Table 10 Note that, contrary to Parabolic Weighting, the lowest weight is not minimal. For instance, for n = 5, experimental results show that the minimal weighting is {7, 8, 9, 11, 14}. This weighting is obtained by considering all possible weightings. This systematic computing is not tractable and can only be used with small values of n: actually, we must enumerate the sums of all the subsets of the considered weightings. Paralex Weighting is not minimal, but it offers an efficient method to ensure C CF , C M P and C LC .

Let us illustrate the difference between Paralex Weighting and 2-repetition/Parabolic Weigthings with the following example. Both weightings induce the two different κ-functions described in Table 12. In both cases, ω 0 is the least preferred interpretation: it falsifies one more formula than the other interpretations. However, κ paralex B prefers ω 1 to ω 3 , because ω 3 falsifies a more important formula than ω 1 . On the contrary, κ Table 12: Induced κ-functions

The relative order between interpretations induced by Parabolic and 2-repetition weightings is the following one:

ω 3 < κ rep/parab B ω 2 < κ rep/parab B ω 1 < κ rep/parab B ω 0 ,
while the order induced by Paralex Weighting is:

ω 1 < κ paralex B ω 2 < κ paralex B ω 3 < κ paralex B ω 0 .
The order between interpretations induced by κ P aralex B is the most convincing one. Indeed κ rep/parab B considers that ω 3 is the preferred interpretation, from which one can deduce a and b. This interpretation falsifies as many formulas (namely two) as ω 1 and ω 2 , but it falsifies the most important formula, a → ¬b.

On the contrary, κ P aralex B associates the minimal penalty, namely 46, with the interpretation ω 1 . From this interpretation, one can deduce ¬a and b, which is consistent with a → ¬b.

Conclusion and perspectives

This paper offers several solutions to a fundamental problem that has never been addressed in the literature: the problem of collisions between interpretations in Penalty Logic. Collisions are a weakening agent for conclusions. Two main factors prevail in collision process: the logical expression of beliefs and the weighting itself. This paper focuses on the choice of weightings for Penalty Logic in order to respect the criterion of Collision Freedom, while keeping the capacity of compensation of Penalty Logic.

This paper provides a survey of mostly used weightings. Most naïve weightings have no interesting logical properties and do not prevent the occurrence of collisions. Others, like Lexicographic Weighting, avoid collisions but in the meanwhile disable the mechanism of compensation (and so the interest) of Penalty Logic. We present finally three powerful and easily tractable weightings: 2-repetition, Parabolic and Paralex Weightings, that are Collision-Free and that deal with the number of formulas falsified by interpretations.

But some questions remain open, such as the question of the existence of a minimal and tractable weighting satisfying C CF , C M P and C LC or such as finding a way to deal with several formulas equally weighted. The criterion C M P has been chosen in order to have the most precise conclusions as possible. But other criteria, like set inclusion, could be studied.

Moreover, the different weightings presented in this paper can be used in other logical frameworks than Penalty Logic. For instance, they could be exploited in belief merging, where they could be used for distance modeling and for solving some problems of manipulation.

Figure 1 :

 1 Figure 1: Collisions for Arithmetic Weighting with n = 17 In fact, considering the problem of collision with Arithmetic Weighting is equivalent to a well-known problem in Number Theory: the partition of integer n into distinct parts from 1 to n (Hardy & Wright 1979). Hence the number of collisions for each value of W arith,n Σ is related to the expansion of:

  rep/parab Bprefers ω 3 to ω 1 , because ω 3 falsifies a lesser formula than ω 1 .

Table 7 :

 7 Table 7 presents the first nine weightings. W rep,n for n < 10

	n					W rep,n
	1	1
	2	1	2
	3	2	3	4
	4	3	5	6	7
	5	6	9	11	12	13
	6 11	17	20	22	23	24
	7 22	33	39	42	44	45	46
	8 42	64	75	81	84	86	87	88
	9 84 126 148 159 165 168 170 171 172

Table 8 :

 8 2-repetition Weighting

Table 9 :

 9 W parab,n for n < 10 Like 2-Repetition Weighting, Parabolic Weighting respects the criteria of Collision Free and of Majority Preservation, but also Reverse Lexicographic Cardinality: Proposition 14 Let B be a ranked belief base such that |B| = n and W B = W parab,n then B satisfies C CF , C M P and C RLC .

	n

Table 10 :

 10 presents Paralex Weightings for n < 10. One can remark that weights diverge from W parab,n when n ≥ 3. W paralex,n for n < 10As expected, this weighting satisfies the properties of Collision Freedom, Majority Preserving and Lexicographic Cardinality.Proposition 15 Let B be a ranked belief base such that |B| = n and W B = W paralex,n then B satisfies C CF , C M P and C LC .

	n				W paralex,n
	1	1
	2	1	2
	3	3	4	5
	4	5	6	7	9
	5	11	12	13	15	18
	6	20	21	22	24	27	33
	7	40	41	42	44	47	53	64
	8	77	78	79	81	84	90 101 121
	9 154 155 156 158 161 167 178 198 238

Table 11 :

 11 Example 16 Let us consider the ranked belief base B described in table 11 with two different weightings. One can note that for n = 6, W rep,n = W parab,n . Two different weightings

	ϕ	W paralex,6 W rep,6 /W parab,6
	a → ¬b b	33 27	24 23
	a	24	22
	a ∨ ¬b ¬a ∨ b a ↔ ¬b	22 21 20	20 17 11

F alseB(ω) is defined in Definition 1.

Acknowledgments

We would like to thank the anonymous reviewers for their constructive and helpful comments. This work is partially supported by the ANR project jeunes chercheurs #JC05-41940 Planevo.