Research Abstracts - 2006

Quantitative Tradeoffs Between Multiple Dependent Variables

Michael McGeachie & Jon Doyle

Tradeoffs in Diverse Disciplines

Quantitative and qualitative tradeoffs are types of preference that compare benefits of one option to different benefits of another option. I may say that the average price of a meal is less important than the time to get to a restaurant. I may feel that a reduction in one hour of travel time or layover time is worth an increase of $50 in plane ticket prices. Such statements are commonplace in decision analysis [6]. In artificial intelligence, Brafman and Domshlak [2] have presented methods for expressing qualitative tradeoffs between qualitative variables and integrating these with constrained ceteris paribus preferences. In that system one can express, to use an example, that satisfying my preference for the main course is more important than satisfying my preference for the dessert. Economists have long considered the tradeoffs people make in assessing their decision-making behavior. Microeconomic theory considers the utility a consumer derives from purchasing a mix of commodities, and the tradeoffs this consumer makes between them. Much economic analysis of preferences proceeds from analysis of the partial derivatives of the utility function with respect to these different commodities.

Drawing from all three disciplines, our work expands methods of using partial derivatives as tradeoffs by introducing the gradient to analyze tradeoffs between groups of variables. We combine this novel specification of quantitative tradeoffs with two formalisms of qualitative preferences "other things being equal," the logical language of [4] and the graphical langauge of CP-Nets [1].

Utility and Tradeoffs

In economics, tradeoffs between two commodities have been studied in terms of the marginal impact of each commodity on utility. In such formulations, the partial derivative of the utility function, u, with respect to an attribute f, is known as the marginal utility of f, a quantity whose magnitude is meaningful only when u is a cardinal utility function. The marginal utility of f₁ divided by the marginal utility of f₂ is a meaningful quantity when u is ordinal or cardinal, and is variously called the rate of commodity substitution of f₂ for f₁ and the marginal rate of substitution of f₁ for f₂.

Suppose that there are two attributes, f₁, f₂, such that the preferences over f₂ depend on the values of f₁. Let us assume that f₁ represents having fish or meat for dinner, and f₂ represents having red or white wine with the meal. A common stipulation is that if one is having fish, then one prefers white wine, but if one eats red meat, then one prefers a red wine accompaniment. Let u₁ be a subutility function representing the utility derived from the meal, including both f₁ and f₂. Then suppose that f₃ represents the time it takes to arrive at the restaurant. Generally one prefers a shorter transit time, and there may well be tradeoffs people are willing to make between the quality of the restaurant and the time required to get there.

This situation sets up a tradeoff between one attribute and a group of attributes. Tradeoffs between two single attributes are straightforward: one compares a specified or normalized amount of one attribute to the other, which is exactly how the marginal rate of substitution is used. When considering tradeoffs between attribute sets, we consider these to be between the subspaces defined by the attribute sets: one compares a fixed or specific measure of increase in {f₁, f₂}-space to a corresponding measure in {f₃}-space, in this example. Given a subspace G and a subutility function over that subspace, u_G, the gradient of that subspace at some point x in G is a vector based at x pointing in the direction of maximum increase of u_G in that subspace, and the length of that vector is the magnitude of that increase. These are the concepts we use in representing utility tradeoffs between spaces.

Conditioning a Utility Function by Quantitative Tradeoffs

Quantitative tradeoffs between groups of attributes can be phrased in terms of the magnitudes of the gradients of utility in those subspaces.  Given a utility function u we state tradeoffs between a set of attributes G and another set H  by stating that the inequality holds at all x , where |z|₁ is the L₁-norm of a vector z, and for a set of attributes G, p_G(z) is the projection of the vector  z to the attributes G. This is a definition that reduces to the usual economic notion of rate of commodity substitution when G and H are each single attributes.

A collection of such tradeoff statements places several constraints on the possible utility functions that satisfy the set of tradeoffs.  We have shown that these are linear constraints and can be efficiently computed.  Further, we can combine these constraints with other, qualitative, preference statements, specifically the CP-Nets of [1] and the arbitrary ceteris paribus preference statements of [4].  Both preference representation paradigms have had systems proposed for compiling quantitative utility functions from their qualitative preferences (Brafman, Domshlak, and Kogan [3] in the case of CP-Nets and McGeachie and Doyle [5] in the case of arbitrary ceteris paribus statements), and we show that these compilation methods can be extended to provide methods for including our quantitative tradeoff statements as stated above.

We have developed a novel method for enriching two systems of ceteris paribus preferences with quantitative tradeoffs between groups of features. These preference systems can then be compiled into quantitative utility functions using modifications of existing techniques.

Future Work

The basis of our contribution is the interpretation of tradeoff preference as a gradient of the utility function. Even so, our use of the magnitude of the gradient of the utility function to calibrate the relative utilities of two subspaces is a heuristic choice. There could be other measures defined for this purpose, such as some kind of average-case improvement measure, for example, that tries to capture the average case outcome.

Another avenue for future work is in greater integration with existing preference reasoning systems. For example, the quantitative tradeoff statements described in this work are incompatible with the qualitative tradeoffs used in TCP-Nets, but perhaps there is some minor modifications to one or the other system that render them compatible.

Research Support

Michael McGeachie is supported in part by the National Multi-Protocol Ensemble for Self-Scaling Systems for Health (NMESH) grant N01-LM-3-3515.

References:

[1] C. Boutilier, R. Brafman, H. Hoos, and D. Poole. Reasoning with conditional ceteris paribus preference statements. In Proceedings of Uncertainty in Artificial Intelligence, pp 71--80. 1999.

[2] R. I. Brafman and C. Domshlak. Introducing Variable Importance Tradeoffs into CP-Nets. In The Proceedings of the Eighteenth Conference on Uncertainty in AI. 2002.

[3] R. I. Brafman, C. Domshlak, and T. Kogan. Compact Value-Function Representations for Qualitative Preferences. In The Proceedings of Uncertainty in AI, pp. 51--59, Arlington, Virginia. AUAI Press, 2004.

[4] Jon Doyle, Yoav Shoham and Michael P. Wellman. A logic of relative desire (preliminary report). In Z. Ras, ed, Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems, Lecture Notes in Computer Science, pp. 16--31. Berlin, Springer-Verlag. 1991.

[5] Michael McGeachie and Jon Doyle. Efficient utility functions for ceteris paribus preferences. In Proceedings of the 18th National Conference on Artificial Intelligence, pp. 279--284, Edmonton, Alberta, 2002.

[6] Howard Raiffa. Decision Analysis: Introductory Lectures on Choices Under Uncertainty. Addison-Wesley. Reading, Massachusetts. 1968.