Bipolar possibility theory in preference modeling: Representation, fusion and optimal solutions

Contents

1. 1  Introduction 2
2. 1.1 Aim ................................ 2
4. 2  Representing positive and negative preferences 3
5. 2.1  Syntactic specification of bipolar preferences . . . . . . . . . . 3
6. 2.2  Modeling negative preferences in possibilistic logic . . . . . . . 32.2.1 Definition1 ........................ 42.2.2 Feasibility ......................... 4
8. 2.3  Representing positive preferences in the logic of guaranteedpossibility ............................. 52.3.1 Definition2 ........................ 52.3.2 Guaranteedpossibility .................. 5
10. 2.4  Coherence between positive and negative preferences . . . . . 62.4.1 Definition3 ........................ 62.4.2 Proposition1 ....................... 6

3 Merging multiple agents preferences in a bipolar representa-tion

6

1. 3.1  Fusionofnegativepreferences .................. 7
2. 3.2  Fusionofpositivepreferences .................. 73.2.1 Proposition2 ....................... 7
3. 3.3  Restoring consistency as characterizing best solutions . . . . . 8

4 Finding best solutions according to negative and positivepreferences 84.1 Binarynegativeandpositivepreferences . . . . . . . . . . . . 8

5 Conclusion

9

1

1 Introduction

Many researchers in Artificial Intelligence have tackled the issue of represent-ing preferences of an agent. One approach is the bipolar view in preferencemodeling, which classifies preferences into two categories: positives prefer-ences and negative preferences. Positive preferences are the ones that theagent desires, and considers to be satisfactory. On the other hand, negativepreferences represent what is unacceptable for the agent or what he rejects.Positive preferences are considered to be weak, since they do not excludesolutions, but only suggest the best ones instead. For example, in a threeday summer school conference, each speaker should list their preferences forscheduling their talk. The available time slots are on Monday, Tuesday andWednesday, and can occur either in the morning or in the afternoon. Nowthe speaker can provide two types of preferences. The first one, which is neg-ative preferences, specifies the unacceptable slots for the speaker with somelevel of tolerance. For instance, a speaker may strongly refuse to give thetalk on Monday due to family reasons, and weakly refuse to give the talk onWednesday. Now, scheduling the talk on Tuesday morning or afternoon, ispreferred, while Monday is totally unacceptable. The second type is positivepreferences, where the speaker, for instance, prefers to give the talk earlyin the morning over giving it in the afternoon. Negative preferences inducea first ranking on all feasible solutions, while positive preferences induce asecond ranking on all possible solutions.

1.1 Aim

Having both the positive and negative sets of preferences, the aim is touse them conjointly and compactly to reach the best solutions, and achieveconsistency among the two sets. Back to the example, the best solution is toschedule the talk on Tuesday morning. Moreover, if there is an emergencyand the buildings cannot be opened in the morning, then scheduling the talkon Tuesday in the afternoon, though not the best solution, is a tolerated one.This is not the case if for instance the buildings are closed on Tuesday andWednesday. Then, there is no feasible solution. Negative preferences excludeunacceptable solutions, while positive preferences discriminate between thetolerated ones.

2

2 Representing positive and negative prefer-ences

Let L be a propositional language over an alphabet P of atoms. Let Sdenote the set of all classical interpretations. s ε S and represents a solutiondescribed in terms of positive and negative preferences.

2.1 Syntactic specification of bipolar preferences

In this part, bipolar representation of preferences at the syntactic level, isproposed. Two sets of inequality constraints will be used to represent theagent’s preferences. The first set expresses the positive preferences as follows:

wj is a propositional formula that encodes a desire or a wish. ∆ returns alevel of satisfaction. bj lies in a finite totally ordered scale L+ contained inthe interval (0,1]. ∆(wj)=1, represents maximal possible satisfaction, and∆(wj)=0, is neutral.

The second set expresses the negative preferences as follows:

ri is a propositional formula that must be violated. R stands for rejection.ai lies in a finite totally ordered scale L− contained in the interval (0,1].R(ri)=1, means that the agent gives highest priority to the rejection of ri,and R(ri)=0, is neutral.

2.2 Modeling negative preferences in possibilistic logic

πR(s) is a measure of how tolerable a solution s is, given R, the set of negativepreferences of the agent. The possibilistic logic provides a natural frameworkto model negative preferences, as well as representing tolerability of a solutionat the semantic level. πR(s)=1, means that s is fully tolerated, and πR(s)=0,means that s is totally unacceptable. In general, πR(s) > πR(s’) says that s ismore tolerated than s’. For example if the agent strongly rejects a propositionr, and a solution s falsifies this r, then s is fully tolerated. Conversely, if s

3

satisfies r, then s is totally unacceptable. The more general case occurswhen r is rejected to some degree. s remains fully tolerated, if it falsifies r.However, if s satisfies r, then the higher a is, the less tolerated s becomes,where R(r)≥a. In the case of two propositions r1 and r2, there are threescenarios. First, if s falsifies both, then s is fully tolerated. Second, if ssatisfies r1 and falsifies r2, then s is measured in terms of how tolerable r1 is,as before. Third, if s satisfies both r1 and r2, then s is measured in terms ofthe least tolerable r among r1 and r2.

2.2.1 Definition 1

This definition simply shows that, given the set of negative preferences ofan agent, πR(s) is measured in terms of a proposition ri being the mostintolerable one in the set, and is equal to 1-ai in this case.
The paper uses the following set to represent rejection statements, where thepair (¬ri,ai) represents the constraint R(ri)≥ai.

2.2.2 Feasibility

A tolerated solution s is not necessarily feasible. For example, if someonewishes to buy an apartment, s could be ”buy a small and large apartment”.Despite s being a tolerated solution, it is not a feasible one, since large andsmall are contradictory. The set of feasible solutions is expressed as follows:

fk represents propositional formulas. 1 is a degree expressing that fk is astrict constraint. Therefore, a solution s is feasible, if it satisfies all formulasin the set F. Thus, tolerated solutions are models of feasible ones.

4

2.3 Representing positive preferences in the logic ofguaranteed possibility

Positive preferences of an agent need to be described in terms of how desirablethey are. This can be done by giving a weight to a solution s, such that thisweight measures the desirability of that solution. δW (s) > δW (s’) means thats is more desirable to the agent than s’. The set of positive preferences canbe represented as follows:

[wj,bj] represents that a solution s is desirable at least with degree bj, if itsatisfies wj. For [w1,b1] and [w2,b2], if s satisfies both w1 and w2, then it isdesirable with max(b1,b2).

2.3.1 Definition 2

Given the set of positive preferences of the agent W, δW (s) is the maximumweight of some wj where s satisfies wj . By adding a new preference to the setW, δW (s) can only get higher. While πR(s) measures how tolerable a solutionis to the agent, δW (s) measures how satisfactory that solution is. δW (s)=0means the agent is neutral and πR(s)=0 means that s is impossible.

2.3.2 Guaranteed possibility

The possibilistic logic, previously discussed, cannot encode the set of posi-tive preferences, hence the use of of a third-set function called guaranteedpossibility denoted by ∆. ∆(w) ≥ b guarantees that any solution satisfyingw has a satisfaction level of at least b.

5

2.4 Coherence between positive and negative prefer-ences

Despite the set of positive preferences and the set of negative preferencesbeing independent, a solution should be consistent with both sets. Namely,a solution cannot be unacceptable and desired at the same time.

A solution satisfying at least one positive preference, should falsify all nega-tive preferences.

2.4.1 Definition 3

In general, a solution being satisfactory with some degree, should be toleratedwith at least the same degree.

2.4.2 Proposition 1

The set of positive preferences and the set of negative preferences are said tobe coherent if and only if,

3 Merging multiple agents preferences in abipolar representation

The merging process results in the pair (R⊕R ,W⊕W ). R⊕R represents theresult of merging the negative preferences of several agents, and W⊕W is theresult of merging the agent’s positive preferences. This paper discusses therevision of positive preferences when there is an incoherence with the negativepreferences.

6

3.1 Fusion of negative preferences

The fusion of negative preferences of n agents, denoted by {R1,...,Rn}, isa function from [0, 1]n to [0,1]. The concept is, if a solution s is somehowrejected by an agent, it should be rejected by other agents with the samedegree after merging. If {a1,...,an} denote the level of tolerability of eachagent, then after merging, s will be tolerated with ⊕R{a1,...,an}. ⊕R is afunction having the following natural properties:

1. ⊕R(1,...,1) = 1.
2. Monotonicity property, that is, for every i ranging from 1 to n, where
3. ai ≥bi,⊕R{a1,...,an}≥⊕R{b1,...,bn}.
5. ⊕R(1,...,1,a,1,...,1) = a. If one agent partially rejects a solution, thenthe merging should result in a solution with tolerability degree no morethan a. So, if a = 0, then ⊕R{a1,...,an} = 0.

3.2 Fusion of positive preferences

Let W1, ..., Wm be the sets of positive preferences of m agents, and δW 1,...,δW mbe their associated positive possibility distribution. ⊕W is a merging operatorhaving the following properties:

1.2.

3.2.1

⊕W (0,...,0) = 0. If no solution is satisfactory to any agent, then itshould not be satisfactory after merging.

Monotonicity property, that is, for every j ranging from 1 to m, whereaj ≥ bj, ⊕W{a1,...,am} ≥ ⊕R{b1,...,bm}.

Proposition 2

Let W1 = {[wi,ai]: i=1,...,n} and W2 = {[wj′,bj]: j=1,...,m}, and δW1 andδW2 be their associated positive possibility distributions respectively.

7

Combining δW1 and δW2 results in a less constrained solution. The agentsare said to be highly cooperative, if an agent adds to his positive preferences,other agents’ positive preferences, as long as they do not conflict with whatis tolerated for him. Therefore, Wmax = W1 ∪ W2.

3.3 Restoring consistency as characterizing best solu-tions

The consistency of the pair(Wi,Ri) is not enough to say that (W,R) is coher-ent, where W and R are the results of merging all Wi and Rj respectively.In order for Wi and Rj to be coherent, δW (s) ≤ πR(s) must be satisfied. Ifthey are incompatible for any reason, one of δW or πR should be revised.Since πR is difficult to alter, as it represents what is tolerated, δW is chosento be revised. The intuition is to decrease δW to the level of πR. This can berepresented as, ∀s,δWrev (s) = min(δW (s),πR(s)).

4 Finding best solutions according to nega-tive and positive preferences

Given the set of feasible solutions F, the set of positive preferences W andthe set of negative preferences R, a description of the preferred solutions isdiscussed. Such solutions should be feasible, respect all negative preferencesand satisfy as many positive preferences as possible.

4.1 Binary negative and positive preferences

Assuming no weights are used for negative and positive preferences. So, anegative preference present in R is totally rejected, and a positive preferencepresent in W is fully desired. The order is to consider solutions present inF, then exclude some of these based on what is presented by R, and finallyrefine solutions with respect to W. This presentation is assuming that Ris consistent, while W does not have to, otherwise there are no feasible ortolerated solutions. SR is used to denote the set of all possible solutionssatisfying R. There are three approaches for selecting the preferred solution:

8

1. Conjunctive selection, which aims to satisfying all positive prefer-ences. So, a solution s has to satisfy every single preference in W. Thisis, clearly, too demanding, and contradicts with the essence of positivepreferences, by treating them as negative preferences.

2. Disjunctive selection, which aims to satisfying at least one positivepreference, and is fine with neglecting all positive preferences.

3. Cardinality-based selection, which aims to satisfying as many pos-itive preferences as possible. So, as more positive preferences are satis-fied by s, s becomes more preferable.

5 Conclusion

The idea of representing preferences as positive and negative, is madeuse of in this paper, by treating them as two separate sets. Eachpreference in both sets can be measured by some weight, that denoteshow tolerable or desirable that preference is. The coherence of both setsis then discussed, as well as the feasibility of a solution. Then, mergingthe two sets of multiple agents is discussed, with restoring consistencyamong them, if needed. Finally, after having a set of tolerated andfeasible solutions, the process of picking the best solutions is discussed.

9

‍