REU: Small: Qualitative Preferences: Merging Paradigms, Extending the Language, Reasoning about Incomplete Outcomes

Summary: Preferences are one of the most fundamental attributes of human reasoning and decision making. They appear whenever a choice between alternatives is to be made. Buying a car we consider factors such as safety. economy, convenience, appearance. Ordering a dinner we take into account what we like and how hungry we are. Not surprisingly, preferences have received extensive attention in AI. The most common approach in decision theory involves preferences expressed numerically in teffils of utility functions, while optimization over different choices takes into account the probability distribution over possible states of the world. The problem is that building good utility functions is recognized as difficult, error-prone and time consuming, and eliciting adequate probability distributions is even more questionable. Therefore, an alternative approach in which preferences are represented in qualitative teffils has been gaining attention in the AI community in the past two decades. The research we propose to conduct aims to advance that area, commonly referred to as qualitative decision theory. More specifically, it is concerned with approaches where preferences are expressed in teffils of simple and intuitive qualitative statements directly about properties of alternative outcomes (belief sets, product configurations, plans, etc.). We focus on two recent fOffilalisms for representing and reasoning about qualitative preferences that show significant promise: CP-nets and answer-set optimization (ASO) programs. Both CP-nets and ASO programs offer representations for several classes of preference problems, but each has major limitations. Our research program is designed to address these limitations, by developing a fOffilalism of ASO(CP) programs that extend both ASO programs and CP-nets by exploiting key properties of both. Its goal is to address fundamental theoretical and implementational questions concerning representing and reasoning about preferences. Our major research objectives are: to introduce formally ASO(CP) programs by integrating into ASO programs generalized conditional (ceteris paribus) preferences of CP-nets; to develop theory of ASO(CP) programs, in particular, to establish expressivity of ASO(CP) programs, to study properties of preorders that can be defined by means of ASO(CP) programs, and to address relevant computational issues; to investigate a crucial problem of preference equivalence, essential for automated preference manipulation; to study an extension of ASO(CP) programs to the case of incompletely specified outcomes, essential for practical applications; and, to extend ASO(CP) programs to the first-order language extended with aggregate operators . . .T.he project will have significant scientific merits. Representing preferences qualitatively and optlmlzmg over such preferences is a fundamental problem of qualitative decision theory. By integrating and advancing understanding of major types of common preferences that are captured by ASO programs and CP-nets, this project will produce theoretical and practical advances in representation and reasomng about preferences, bringing it to the point where it can be effectively used in practical decisIOn support systems . .