Computer Science Mathematics
ComputerScience,1970-2008-Computer Science-1999.jsonl.gz.gz
Computer Science
af6a1c1515736e22872016b0c453e40509aa5057
A Hybrid Approach to Reasoning with Partially Elicited Preference Models

Classical Decision Theory provides a normative framework for representing and reasoning about complex preferences. Straightforward application of this theory to automate decision making is difficult due to high elicitation cost. In response to this problem, researchers have recently developed a number of qualitative, logic-oriented approaches for representing and reasoning about references. While effectively addressing some expressiveness issues, these logics have not proven powerful enough for building practical automated decision making systems. In this paper we present a hybrid approach to preference elicitation and decision making that is grounded in classical multi-attribute utility theory, but can make effective use of the expressive power of qualitative approaches. Specifically, assuming a partially specified multilinear utility function, we show how comparative statements about classes of decision alternatives can be used to further constrain the utility function and thus identify sup-optimal alternatives. This work demonstrates that quantitative and qualitative approaches can be synergistically integrated to provide effective and flexible decision support.


INTRODUCTION
Within the field of automated decision making, similar to the early days when probability theory was consid ered epistemologically inadequate, utility theory these days faces several epistemological problems of its own. In particular, it is often quite difficult to elicit the re quired utility function, especially when the outcomes of the decisions are complex. While  for eliciting a complete utility function from a user, doing so may be neither practical nor desirable. First, a large elicitation overhead may not be commensurate with the task at hand. Second, since people's prefer ences tend to change over time, we may wish to repre sent only that core of preferences that is relatively sta ble over some desired time period. Thus we would like to develop techniques for partially eliciting preferences and for reasoning with partially specified preferences in order to eliminate suboptimal decision alternatives.
Practitioners of decision theory have addressed the issue of eliciting utility functions by developing a comprehensive framework, generally known as multi attribute utility theory (MAUT) [10]. Lying at the heart of MAUT is the notion of utility independence, one of the first notions introduced to exploit qual itative, structural aspects of preference. Suppose that decision outcomes can be described by a set X = {XI> X2, ••• ,X,.} of attributes, meaning that an outcome x is a value assignment (X1 = Xt . X 2 = x 2 , ... ,X,. = X n ) to the attributes, a set Y C X is said to be utility independent of its complement X-Y, or Ul for short, if the preference over probability distribu tions P whose marginals over X-Y are a fixed, degen erate distribution Px-Y does not depend on Px_y.
Utility independence occurs quite often in real-life de cision making situations, and in general can be de tected easily. When a set of attributes Y is UI, a simple theorem shows that we can write the utility function u(x) as an expression that consists of two functions over X -Y and one function over Y, achieving a re duction of dimensionality (and hence complexity). In particular, if every subset Y of X is UI, a condition called mutual utility independence (M UI), then we can write u(x) either in a multiplicative form: n u(x) = IT (1 + k;u;(x;)), i=l or in an additive form: n u(x) = L k;u;(x;), i=l where u; are so-called sub-utility functions that cap ture the decision maker's preference with regard to attribute X; when holding the attributes X;,i "# i at some fixed level, and k; are constants that ensure proper global scaling 1 • Whenever MUI is applicable, the utility function can be obtained in the following two steps:  2In fact, in the case when there are more than 3 at tributes, assessment of MLUFs is usually abandoned [10].
placing a sizable elicitation burden on herself and on the decision maker.
Our perception is that in real-world applications of decision theory, decision analysts often choose the for mer option: to assume MUI. In this paper, we pro pose to study MLUFs 3 . Because complete elicitation of MLUFs is impractical, we set out to develop tech niques to reason with partially elicited MLUFs. In particular, these techniques are designed to identify sub-optimal decision alternatives without assessing all the 2n -1 scaling coefficients (expected utilities thus are not explicitly computed). The premises of these techniques are the following:  In Section 2, we show that the above assumptions can be captured by a polyhedral cone that constrains the unknown scaling coefficients ky. We then use standard optimization techniques to deduce further preferential information such as induced dominance and potential op timality from this constraint. An inherent benefit of these techniques is that they can be used to detect inconsistency in the prefence information elicited from the user. (We note that previously, Hazen presented a preference cone approach for reasoning with partially specified additive or multiplicative utility functions (9), which is similar to the approach presented in this pa per.) The key assumption in this approach is (iii), which ass umes that the decision maker can provide prefer ential comparisons between (real or fictious) decision consequences. This assumption is an integral part of interactive approaches to decision making (12,9,11).
The rationale for making this assumption is that there are certain circumstances where it might be easier for the decision maker to express preferences among de cision consequences than to introspect about the at tributes describing each one. For example, in express ing preferences about movies, most people can readily express their preferences over two films they have seen in the past but may have difficulty describing prefer ences over attributes like director, leading actor, or costum designer. In fact, most people would not even recognize the names of the costume designers, even when they may have a preference for films with nice costumes.
The more comparisons the decision maker can provide, the more conclusive inference can be made. In partic ular, if the decision maker can provide a succint, qual itative statement about her preference that implicitly encoded a set of comparision statements, then we may be able to quickly identify a large set of sub-optimal alternatives.
To capture such preferential statements and derive ef ficient inference mechanisms using them is one of the aims of the field of qualitative decision theory. Recent work from this fi eld has attempted to address the elici tation problem by providing formal languages in which partial preference information can be conveniently ex pressed [5,6,15,3,1]. For example, the languages pro posed by Doyle and Wellman [6] and by Tan and Pearl [15] attempt to provide a semantic to ceteris paribus (all else being equal) comparative statements. These are preferential statements concerning classes of deci sion consequences.
While these languages have successfully addressed a number of expressiveness issues, the inferential mech anisms available have not been sufficiently powerful for building practical decision making systems. In Section 3, we propose using ceteris paribus comparative state ments, as presented in [6], as a means to represent com parative statements made by the decision maker, to be used in conjunction with the assumptions (i), (ii), and (iii) described above. This combination provides us with a fl exible representation for eliciting preferences and an inferrential mechanism to effectively eliminate decision alternatives. The resulting hybrid framework is intended to strike a balance between logic-oriented (generally too weak), and numeric-oriented (generally too cost-intensive) approaches.
The rest of this paper is organized as follows. In Sec tion 2, we develop the preference cone framework to reason with partial MLUF and pairwise comparisions.
In Section 3, we propose to intergrate qualitative pref erential comparisons to the this framework and provide an example to illustrate this idea. We finish with dis-Reasoning with Partial Preference Models 265 cussion of related work and future research issues.

REASONING WITH PARTIALLY ELICITED MULTI-LINEAR UTILIT Y FUNCTIONS USING POLYHEDRAL CONES
In this section we explore the idea of using explicit pairwise comparisons of decision consequences to iden tify sub-optimal alternatives, as outlined in the Intro duction. The premises of this analysis are assumptions (i), (ii), (iii).

LINEAR CONSTRAINTS ON THE SCALING COEFFICIENTS OF MLUFS
First, note that the multilinear form of the utility func tion, as formalized in Equation (1) does not fully cap ture the assumption that the attributes X; are UI; the multilinear form is only a necessary but not sufficient condition for X; to be UI. We need to add constraints on the scaling coefficients ky in order to obtain a nec essary and sufficient condition.
Ta ke, for example, the assumption that X; is UI. Let Thus to say that X; is UI is equivalent to say that the coefficient for u; ( x;) in this linear function must be non-negative. Formally, this means L k {x;}uz tz(x);::: 0. (2)

Z�X-{X;}
Moreover, this inequality must be satisfied for any value assignment to the attributes in the set X-{X;}. Inversely, if this constraint is satisfied, then X; is UI. In other words, the utility independence of the attributes X; is precisely captured by the multilinear form as in Equation ( 1), with the additional linear, homogeneous constraints about the scaling constants, as expressed in Inequality ( 2).
To further simplify the expositions, we introduce the following notations. Let k denote the &-dimensional ( d = 2n -1) vector with components ky, 0 f. Y � X. For any i = 1, 2, ... , n, let s' denote the same dimension vector whose components are functions s� : X -t !R, 0 f. Y � X, defined as: Note that the functions s�(x) do not depend on x;, the i-th component of x. Inequality ( 2) can thus be written as (k, s'(x)) ::; 0, Vi= 1, 2, ... , n; x, where (., .) denotes the inner product of two vectors.
One may at first think that these constraints are by themselves strong enough to imply non-trivial prefer ences over decision alternatives. However, the results that we were able to obtain in our previous work [7], presented in the theorem below, suggest that further preferences can be deduced in only very special cases. (a) the utility junction is additive, or (b) in the probability distributions p and q, the attributes X;, when viewed as random variables, are probabilistically independent.
Furthermore, the inference is not sound if the utility junction is multiplicative.

LINEAR CONSTRAINTS FOR PAffiWISE COMPARISONS
In order to be able to infer a pairwise preference, we need to impose very strong conditions, either about the form of the utility function (it must be additive), or about alternatives (they must be probabilistically independent}, in addition to having the local domi nances. When these conditions do not hold, we need other sources of preferential information in order to be able to identify sub-optimal alternatives and to nar row down the set of candidate alternatives. One such source is pairwise comparison statements made by the decision maker. Note that the statement p ::$ q translates into the fol lowing inequalities: where tp (respectively tq) denotes the (2n -I) dimensional vector whose components are ty(p) (re spectively t11(q)). This last inequality is also a linear, homogeneous constraint over the unknown constants ky.

SOME BASIC CONCEPTS OF CONVEX CONE ANALYSIS
Before we continue our analysis, we provide a brief review of some basic concepts of convex cone analysis.

Polyhedra, Cones, and Polyhedral Cones
The d-dimension Euclidean Space is the vector space !Rd equipped with the inner product(). Given a vector n, and a E !R, the set 11a = {x/(n,x) =a} is called a hyperplane, the set n;; = { x/ (n, x) :::; a} is called a closed hal/space with outward normal n. For simplicity of notations, the subscript a is omitted when a = 0.
The intersection of a finite number of closed halfspaces is called a polyhedron.
with apex 0. In this paper, cones are all 0-apexed, unless indicated otherwise. Given a set W � !Rd, the set of all points that can be expressed as non-negative linear combinations of points of W can be shown to be a convex cone, and is denoted by Cw. This cone is called the convex cone generated by W and can be equivalently defined as the smallest convex cone con taining W. A cone that is also a polyhedron is called a polyhedral cone. It is well-known that polyhedral cones are precisely convex cones generated by finite sets of points, and can be shown to be closed.

Dual Cones
Given a set w � �. let w· be defined as w· := {YI(x,y) $ 0, 'v'x E W}. W* is easily shown to be a convex cone and is refered to as the dual cone of W. For example, if W contains a single point n, then the dual cone of W is n-, the closed halfspace with outward normal n.
The following theorem is standard in convex cone anal ysis. Assuming that the domain of each attribute X; is fi nite, the above inequalities are equivalent to a finite set of linear homogeneous constraints over the scaling coefficients ky. From now on, we denote these con straints as follows { (k, w;) ::; Olj = l..m}, and denote W = {w;li = l..m}. Thus, the utility function u, when represented as a vector k with coordinates ky, must lie in the intersection of the closed halfspaces with outward normal w;: m kEK:= n w j .

j= l
This intersection is a polyhedral cone, which is the dual cone K = W* of W. Using Theorem 2, we have that K* = w•• = Cw, i.e., the dual cone of K, the set of admissible k, is the polyhedral cone generated by the constraint vectors w; (see Figure 1).

Induced Dominance
The above analysis i=ediately leads to the following result that can be used to test for induced dominance.
Reasoning with Partial Preference Models 267 Figure 1: A 2-dimensional illustration of Theorem 3.

Here W = {wbw2}·
Theorem 3 Given a pair of alternatives (p, q), we can deduce p ::5 q iff tp -tq E Cw. The "only if " part means that if tp -tq ¢ Cw, then there exists k E K such that (k, tp -tq) > 0, i.e. p >-q under such k.
Below is an algorithm for testing induced dominance. This "inference rule" is sound and complete based on the above theorem.

Complexity Analysis
The complexity of Algorithm 1 is determined by the complexity of determining the generators {k 1 ll} of the polyhedral cone K (step 1). These vectors are out ward normal vectors of the ( d-1 )-dimension facets of the polyhedron Cw. This problem is essentially the same problem as finding the facet normals of the con vex hull of a set of points in the (d-I)-dimension space, which can be solved in time O(m r d /21 -1 ) using algorithms from computational geometry [14). Here, m is the number of the elements of W, and d = 2" -1 is the dimension of the space (which is the number of the scaling coefficients).
To conclude this section, we note that in complex de cision making problems, the decision maker may easily exhibit inconsistent preferences. For example, she may assert a set of comparative statements that results in an empty preference cone (K = 0). In sucll situa tions, we would like the system to restore consistency by eliminating one or more "problematic" compara tive statements. But how to identify sucll problematic statements is an open question and needs further re search and experiment. 3

INTERGRATING QUALITATIVE COMPARATIVE STATEMENTS
In the previous section we have shown how compar ative statements about decision consequences can be exploited to test for induced dominance and potential optimality. Since there are 2" -1 unknown scaling coefficients, cllances are that we would need an inor dinately large number of pair-wise comparisions from the decision maker in order to make useful inferences.
Qualitative preference logics such as those proposed by Doyle and Wellman [5,6) and Tan and Pearl [15) provide languages that can express comparative state ments about classes of decision consequences. Sucll a qualitative expression of preferences gives us a large number of pair-wise preferences among individual de cision conequences, which can be used to effectively constrain the space of utility functions.
In this section we give an example to illustrate this idea. In this example, the state space has three propo sitional attributes {X1,X2,X3} with domains {0,1}. Suppose also that the attributes are utility indepen dent in sucll a way that for eacll attribute, 1 is the prefered value. This means that the sub-utility func tions u;(x;) for the attributes are given by u;(x;) = x;. The overall utility function can be written as u(x1,x2,xa) = k1x1 + k2x2 + kaxa + k12X1X2 + k13X1X3 + �3X2X3 + k123X1X2X3.
Next, we translate the assumption about utility inde pendence of the attributes into constraints about the scaling constants. Let us consider attribute X1. To say that X1 is UI is equivalent to say that the overall utility function u(x1, x2, xa) = (k1 + k12X2 + k1axa + k123X2xa)x1 + �x2 + kaxa + k2ax2xa, when viewed as a linear function of x1 must have pos itive coefficient for X1, i.e.
Considering all value assigments for x2 and x3, the UI ass umption for xl implies the following inequalities involving the scaling constants: The utility independence for X2 and Xa can be ex pressed similarly: Note that the inequality k1 > 0 is equivalent to the comparison statement (0, 0, 0) -< (1, 0, 0), and the in equality k1 +k12 > 0 is equivalent to (0, 1, 0) -< (1, 1, 0). Now suppose that the decision maker states that she prefers to have (x1 = 1, X2 = 0) to (x1 = 0, x2 = 1), all else being equal, i.e. regardless of the value of x3. This statement is equivalent to the following constraints: (6) Using Algorithm 1 with the Constraints ( 3), (4), (5), and (6), we will be able to obtain that, for example, In contrast, in this paper, the consequences of deci sions are uncertain. Furthermore, in work in MCDM, the value function is usually assumed to have some tractable form such as (in increasing order of gener ality) linear (16], quasiconcave (12,13], or monotonic (11]. In this paper, the decision maker's utilty func tion is assumed to have multi-linear form. Since multi linear functions can be non-monotonic (see Theorem However, the inference mechanisms offered by these languages remain rather weak.
It is thus highly desirable to develope a framework that can exploit different strengths of these different quantitative and qualitative approaches. In this paper, we attempt to provide such a framework. Assuming a multi-linear utility function with known sub-utility functions, we show how ceteris paribus comparative statements by the decision maker can be used to infer further preferential information such as induced pair wise preference and sub-optimality.

269
There are several issues that we plan to address in this framework. The first issue is efficiency. Note that the time complexity of Algorithm 1 is exponen tial (O(mf"/21-I )). The base of this upper bound, which is the number of the constraint vectors w;, can be large. A possible solution for this is to investi gate ways to effectively use sets of comparisions, repre sented by qualitative logical constructs. For example, a ceteris paribus comparison, which is equivalent to a set of comparisions between individual decision conse quences, can sometimes be captured by a single linear inequality involving certain (but not all) scaling coef ficients. This would result in fewer constraint vectors.
With regard to the exponent of the upper bound, since in practice, the number of attributes ( n) is usually very small (3-8), we expect the exponent (rd/21-1) not to exceed 127. We can also try to exploit further util ity independencies, if applicable, to reduce the num ber of scaling coefficients and to reduce the exponent.
For example, if Y is UI of X -Y and IYI = r, then the number of scaling coefficients can be reduced to 2r + 2n-r+I -4. If both Y and X -Y are UI of the other, then the number can be reduced to 2r + 2n-r-2 (Keeney & Raiffa 1976 (10], Chapter 6.10.3). Finally, we point out that since the motivation of our work is to reduce the elicitation time, which in most cases is much larger than the computation time, this approach to reasoning with partial preference information could sometimes provide an attractive option despite the in volved computational complexity.
Second, instead of working with only the supplied pref erences, we may want the system to take the initiative and ask the user to make comparisons between deci sion consequences, or sets of decision consequences (us ing some qualitative logical constructs). To this end, the most interesting issue is identifying the questions whose answers would lead to the most conclusive infer ence, e.g., induced optimality of a particular decision alternative, or induced sub-optimality of a large num ber of decision alternatives 5• A difficulty with this approach is that the user may not be able to answer some of those queries.
Finally, it is interesting to see if this approach to rea soning with partially elicited preference information can be intergrated into the case-based framework to preference elicitation advocated in our recent work [8] (see also (4]). In this framework, the system maintains a population of users with their preferences partially or completely specified in a given domain. When en countering a new user, called A, the system first elicits some preference information from A, and then deter mines which user in the population has the preference 50ur previous work [7] has addressed this issue in a special case when the utility function is additive. structure that is closest to A's. The preference struc ture of that user will be used to determine an initial default representation (or working model) of A's pref erences. We can use the techniques presented in this paper to elicit some initial preference information from the decision maker and to eliminate some sub-optimal decision alternatives. If the set of remaining decision candidates is still large, the system can use the case based approach to make recommendations for the de cision maker.