A bipolar constraint problem is BAC iff all its constraints are BAC.
If a bipolar constraint problem is not BAC, we can consider its negative and positive versions and achieve PAC and NAC on them. If both ×n and×p are idempotent, this can be seen as the application of functions which are monotone, inflationary, and idempotent on a suitable partial order. Thus usual algorithms based on chaotic iterations (Apt, 2003) can be used, with the assurance of terminating and having a unique equivalent result which is independent of the order in which constraints are considered. However, this can generate two versions of the problem (of which one is NAC and the other one is PAC) which could be impossible to reconcile into a single bipolar problem. In fact, the two new problems could associate both a positive preference and a negative one to the same domain element. Consider for example a domain value that has a positive preference p in the given bipolar problem. Then, the positive version will consider p, and the negative version will consider 2. Then, the two PAC and NAC algorithms could transform, respectively, p into p′ (higher than p) and 2 into n (smaller than 2). So this domain value will have both p′ and n, while by definition each domain value has just one preference.
Taking their compensation would return a problem which is not equivalent to the given one, since the compensation operator is not associative.
This problem can be solved by achieving only partial forms of PAC and NAC in a bipolar problem. The basic idea is to consider the given bipolar problem, apply the NAC and PAC algorithms to its negative and positive versions, and then mod-ify the preferences of the original problem only when the two new versions can be reconciled, that is, when at least one of the two new preferences is the indif-ference element. In fact, this means that, in one of the two consistency algorithms, no change has been made. If this holds, the other preference is used to modify the original one. This algorithm achieves a partial form of BAC, that we call p-BAC, and assures equivalence. More precisely:
Proposition 1 Consider a bipolar preference problem Q, its negative version neg(Q), and its positive version pos(Q). Apply NAC to neg(Q) and PAC to pos(Q), and de-note with N AC(neg(Q)) and P AC(pos(Q)) the new bipolar problems. Consider also the bipolar preference problem P BAC(Q) obtained from NAC(neg(Q)) and P AC(pos(Q)) as follows: every tuple associated with the indifference ele-ment in P AC (pos(Q)) (resp., NAC(neg(Q))) and a negative (resp., positive) preference n (resp., p) in N AC(neg(Q)) (resp., P AC(pos(Q))) has preference n (resp., p) in P BAC(Q), and every tuple associated with a positive preference p in P AC(pos(Q)) and a negative preference n in NAC(neg(Q)) has the same preference as in Q.
Then, P BAC(Q) is equivalent to Q.
Proof: In order to show that P BAC(Q) is equivalent to Q, we have to show that for every solution of Q, the preference of this solution in P BAC(Q) coincides with
the one in Q. Assume that s is a solution of Q with preference p× n, where p is a positive preference, n is a negative preference, and× is the compensation operator.
Then, by construction of pos(Q) and neg(Q), s has preference p in pos(Q) and n in neg(Q). Moreover, since ×n is idempotent, N AC(neg(Q)) is equivalent to neg(Q). Thus also in NAC(neg(Q)) the preference of s is n. Similarly, since ×p
is idempotent, P AC(pos(Q)) is equivalent to pos(Q) and so also in P AC(pos(Q)) the preference of s is p. By construction of P BAC(Q), we have that the preference
of s in P BAC(Q) is p × n. ⋄
Fig. 4. How to make a bipolar constraint p-BAC.
Example 10 In Figure 4 it is shown how to make a bipolar constraint partially Bipolar Arc-Consistent. Part (a) shows a bipolar preference problem with three constraints cX, cY, and cXY. Preferences are modelled by the bipolar preference structure (N = [−1, 0], P = [0, 1], + = max, ×, ⊥= −1, 2 = 0, ⊤ = 1), where× is such that ×p = max, ×n = min and ×np = sum. Since preferences are given independently in cX, cY and cXY, it is possible to give a low positive preference for a value of X (e.g., X = b) in cX, a negative preference for a value of Y (e.g., X = b) in CY, but an high positive preference for the combination of such values in cXY. In Part (b) we present the positive version of cXY, that becomes PAC by increasing the positive preference associated to X = b from +0.1 to +0.6.
Part (c) presents the negative version of cXY, that becomes NAC by decreasing the negative preference associated to X = a from −0.2 to −0.4. In Part (d) we show how to achieve p-BAC of cXY: we must reconcile the modified preferences obtained in Part (b) and in Part (c) when it is possible. Since in this example it is always possible to reconcile such preferences, we obtain a bipolar constraint which is not
only p-BAC, but also BAC. ⋄
In this approach we require idempotency of×pand×n. However, when such oper-ators are not idempotent, we can follow the approach used in the extended version of arc-consistency presented in (Cooper and Schiex, 2004; Bistarelli and Gadducci, 2006; Larrosa and Schiex, 2003).
Notice that our algorithm will possibly decrease some negative preferences and increase some positive preferences. Therefore, if we use constraint propagation to improve the bounds in a BB algorithm, it will actually sometimes produce worse bounds, due to the increase of the positive preferences. We will thus use only the propagation of negative preferences (that is, NAC) within a BB algorithm. Since the upper bound is just a combination of several preferences, and since preference combination is monotonic, lower preferences give a lower, and thus better, upper bound.
Even if PAC is not useful in a BB procedure, it could be useful (alone or with NAC) when we don’t want to follow a BB approach, but when we want to obtain prefer-ence values in the variables’ domain that are closer to the ones that can be really obtained. When we have bipolar preference problems with only positive prefer-ences, it is useful to perform only PAC, while when also negative preferences are present, it is useful to perform both PAC and NAC, and to reconcile their results if it is possible.
11 Related and future work
Bipolarity is an important topic in several fields, such as psychology (C. E. Osgood and Tannenbaum, 1957; J. T. Cacioppo and Berntson, 1997; P. Slovic and Mag-Gregor, 2002; Tversky and Kahneman, 1992) and multi-criteria decision making (Grabisch and Labreuche, 2005). Also, it has recently attracted interest in the AI community, especially in argumentation (L. Amgoud and Prade, 2005) and qual-itative reasoning (Benferhat et al., 2002, 2006; Dubois and Fargier, 2005, 2006).
These works consider how two alternatives should be compared, given for each a set of positive arguments and a set of negative ones, but they don’t analyze the question of combinatorial choice.
Our bipolar framework is in particular related to the usual ways to represent a bipo-lar scale in psychology: a bipobipo-lar univariate method (C. E. Osgood and Tannen-baum, 1957) and a unipolar bivariate method (J. T. Cacioppo and Berntson, 1997).
The first one (C. E. Osgood and Tannenbaum, 1957), which is the most similar to our approach, considers a scale with a central element ranging from negative ele-ments, which are lower than the neutral element, to positive ones, which are higher than negative elements. The second approach (J. T. Cacioppo and Berntson, 1997), instead, uses two independent unipolar scales for representing positive and negative aspects.
Although our approach is similar to the method in (C. E. Osgood and Tannenbaum, 1957), the scale we use for representing positive and negative preferences is not a unique scale with the neutral element in the exact middle. The positive and the negative scales may have a different granularity, since we want to let the user free
to choose whatever structure he wants, if it satisfies the properties mentioned in the definition of a bipolar preference structure.
Another work regarding bipolarity handling in constraint-based reasoning is pre-sented in (Fargier and Wilson, 2007). However, differently from our approach, it defines an algebraic structure to model bipolarity that follows the approach in (J. T. Cacioppo and Berntson, 1997) and not the one in (C. E. Osgood and Tannen-baum, 1957). The bipolar structure considered in (Fargier and Wilson, 2007) allows a combination between positive and negative preferences that may produce a pref-erence that is neither positive nor negative, that is not allowed in our approach.
Moreover, the operator to combine positive and negative preferences is assumed always to be associative, while we don’t force the user to choose only associative operators. However, if the user want to be sure to have a bipolar preference struc-ture with an associative combination operator, in our paper we have shown how to obtain it.
The approach in (J. T. Cacioppo and Berntson, 1997) allows one to express, for the same feature of an object, both a positive and a negative preference. Our current framework does not model this. However, tuples of preferences could be consid-ered, and this would allow having more than one preference value for each feature.
Bipolar reasoning and preferences have been considered also in the context of qual-itative reasoning. In (Benferhat et al., 2002, 2006) a bipolar preference model based on a fuzzy-possibilistic approach is described, where fuzzy preferences are consid-ered and negative preferences are interpreted as violations of constraints. Prece-dence is given to negative preference optimization, and positive preferences are only used to distinguish among the optimals found in the first phase, thus not al-lowing for compensation.
Another work related to bipolar scales is (Grabisch et al., 2003), which considers only totally ordered unipolar and bipolar preference scales. When the preferences are totally ordered, our operators×nand×p correspond respectively to the t-norm and t-conorm used in (Grabisch et al., 2003). Moreover, in (Grabisch et al., 2003) it is defined an operator, the uninorm, which can be seen as a restricted form of compensation and is forced to always be associative.
As future work, we plan to develop a solver for bipolar CSPs, which should be flexi-ble enough to accommodate for both associative and non-associative compensation operators. The outlined algorithms for BB, NAC, PAC, and p-BAC will also be im-plemented and tested over classes of bipolar problems. We also intend to consider the presence of uncertainty in bipolar problems, possibly using possibility theory to model such uncertainty, and to develop solving techniques for such scenarios. A first study in this direction has been presented in (Bistarelli et al., 2007b). Another line of future research is the generalization of other preference formalisms, such as CP-nets, to deal with bipolar preferences.
Acknowledgements
This work has been supported by Italian MIUR PRIN project “Constraints and Preferences” (n.2005015491).
References
Apt, K. R. (2003), Principles of Constraint Programming, Cambridge University Press.
Bacchus, F. and Grove, A. J. (1996), “Utility Independence in a Qualitative Deci-sion Theory,” in KR-96, pp. 542–552.
Benferhat, S., Dubois, D., Kaci, S., and Prade, H. (2002), “Bipolar representation and fusion of preferences in the possibilistic logic framework,” in Proceedings of KR-02, Morgan Kaufmann.
— (2006), “Bipolar possibility theory in prefrence modeling: representation, fu-sion and optimal solutions,” Information Fufu-sion, an Int. Journal on Multi-Sensor, Multi-Source Information Fusion.
Benferhat, S., Dubois, D., and Prade, H. (2001), “Towards a Possibilistic Logic Handling of Preferences,” Appl. Intell., 14, 303–317.
Bentham, J. (1789), An Introduction to the Principles of Morals and Legislation, Oxford University Press.
Bistarelli, S. (2004), Semirings for Soft Constraint Solving and Programming, vol.
2962 of LNCS, Springer.
Bistarelli, S. and Gadducci, F. (2006), “Enhancing Constraints Manipulation in Semiring-Based Formalisms,” in Proceedings of ECAI-06, IOS Press, pp. 63–
67.
Bistarelli, S., Montanari, U., and Rossi, F. (1997), “Semiring-based Constraint Solving and Optimization,” Journal of the ACM, 44, 201–236.
Bistarelli, S., Pini, M. S., Rossi, F., and Venable, K. B. (2006), “Bipolar preference problems,” in Proceedings of ECAI-06, IOS Press, pp. 705–706.
— (2007a), “Bipolar preference problems: framework, properties and solving tech-niques,” in Recent Advances in Constraints. Selected papers from 2006 ERCIM workshop on constraints, Springer LNAI, vol. 4651.
— (2007b), “Uncertainty in Bipolar Preference Problems,” in Proceedings of CP-07, Springer, vol. 4741 of LNCS, pp. 782–789.
Boutilier, C., Brafman, R. I., Hoos, H. H., and Poole, D. (1999), “Reasoning With Conditional Ceteris Paribus Preference Statements,” in Proceedings of UAI-99, eds. Laskey, K. B. and Prade, H., Morgan Kaufmann, pp. 71–80.
Bruns, W. and Herzog, J. C.-M. (1998), Rings, Cambridge University Press.
C. E. Osgood, G. J. S. and Tannenbaum, P. H. (1957), The Measurement of Mean-ing, University of Illinois Press, Chicago.
Cacioppo, J. T. and Berntson, G. G. (1999), “The affect system: architecture and
operating characteristics,” Current Directions in Psychological Science, 8, 133–
137.
Cooper, M. and Schiex, T. (2004), “Arc consistency for soft constraints,” AI Jour-nal, 154(1-2), 199–227.
Dechter, R. (2003), Constraint processing, Morgan Kaufmann.
Doyle, J., Shoham, Y., and Wellman, M. P. (1991), “A Logic of Relative Desire (Preliminary Report),” in Proceedings of ISMIS-91, Springer, vol. 542 of LNCS, pp. 16–31.
Dubois, D. and Fargier, H. (2005), “On the qualitative comparison of sets of posi-tive and negaposi-tive affects,” in Proceedings of ECSQARU-05, pp. 305–316.
— (2006), “Qualitative decision making with bipolar information,” in Proceedings of KR-06, pp. 175–186.
Ehrgott, M. and Gandibleux, X. (2002), Multiple Criteria Optimization. State of the art annotated bibliographic surveys, Kluwer Academic, Dordrecht.
Fargier, H. and Lang, J. (1993), “Uncertainty in Constraint Satisfaction Problems:
a Probalistic Approach,” in Proceedings of ECSQARU-93, Springer, vol. 747 of LNCS, pp. 97–104.
Fargier, H. and Wilson, N. (2007), “Algebraic Structures for Bipolar Constraint-Based Reasoning,” in Proceedings of ECSQARU-07, pp. 623–634.
Grabisch, M., de Baets, B., and Fodor, J. (2003), “The quest for rings on bipolar scales,” Int. Journ. of Uncertainty, Fuzziness and Knowledge-Based Systems.
Grabisch, M. and Labreuche, C. (2005), “Bi-capacities - parts I and II,” Fuzzy Sets and Systems, 151, 211–260.
J. T. Cacioppo, W. L. G. and Berntson, G. G. (1997), “Beyound bipolar conceptu-alizations and measures: the case of attitudes and evaluative space,” Personality and Social Psychology Review, 1, 3–25.
L. Amgoud, J. F. B. and Prade, H. (2005), “An argumentation-based approach to multiple criteria decision,” in Proceedings of ECSQARU-05, pp. 10–17.
Lang, J. (1996), “Conditional Desires and Utilities: an Alternative Logical Ap-proach to Qualitative Decision Theory,” in Proceedings of ECAI-96, pp. 318–
322.
Larrosa, J. and Schiex, T. (2003), “In the quest of the best form of local consistency for Weighted CSP,” in Proceedings of IJCAI-03, Morgan Kaufman, pp. 239–244.
P. Slovic, M. Finucane, E. P. and MagGregor, D. G. (2002), “Rational actors or rational fools? Implications of the affect heuristic for behavioural economics,”
The Journal of Socio-Economics, 31, 329–342.
Rossi, F., Van Beek, P., and Walsh, T. (2006), Handbook of constraint program-ming, Elsevier.
Ruttkay, Z. (1994), “Fuzzy Constraint Satisfaction,” in Proceedings 1st IEEE Con-ference on Evolutionary Computing, Orlando, pp. 542–547.
Schiex, T. (1992), “Possibilistic Constraint Satisfaction Problems or ”How to Han-dle Soft Constraints?”,” in Proceedings of UAI-92, Morgan Kaufmann, pp. 268–
275.
Schiex, T., Fargier, H., and Verfaillie, G. (1995), “Valued Constraint Satisfaction Problems: Hard and Easy Problems,” in Proceedings of IJCAI-95, Morgan
Kauf-mann, pp. 631–639.
Tversky, A. and Kahneman, D. (1992), “Advances in prospect theory: Cumulative representation of uncertainty,” Journal of Risk and Uncertainty, 5, 297–323.
Wellman, M. P. and Doyle, J. (1991), “Preferential Semantics for Goals,” in Pro-ceedings of AAAI, pp. 698–703.