The most common approach in decision theory involves preferences expressed numerically in terms of utility functions, while optimization over different choices takes into account the probability distribution over possible states of the world. An alternative approach represents preferences in qualitative terms, and is motivated, in part, by difficulties in building good utility functions, ascertaining accurate probability distributions, and related problems.
This project is advancing qualitative decision theory by focusing on two promising formalisms for representing and reasoning about qualitative preferences: conditional preference networks (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. This project addresses these limitations by developing a formalism. ASO(CP) programs, which extend both ASO programs and CP-nets by exploiting key properties of both. The project's major objectives are: to introduce formally ASO(CP) programs by integrating into ASO programs generalized conditional (ceteris paribus) preferences of CP-nets; 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.
Representing preferences qualitatively and optimizing 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 reasoning about preferences, bringing it to the point where it can be effectively used in practical decision support systems.
Representing and reasoning about preferences are fundamental to decision making and so, of significant interest to artificial intelligence. When the choice is only among relatively few outcomes (alternatives), representations in terms of explicit enumerations of the preference order are feasible and lend themselves well to formal analysis. However, in many applications outcomes come from combinatorial domains, that is, they are described as combinations of values of issues (also referred to as variables or attributes), Because of the combinatorial size of the space of such outcomes, explicit enumerations of their elements are impractical. Instead, we have to resort to formalisms supporting intuitive and, ideally, concise implicit descriptions of the order. One of the key foci of the project was one of such formalisms, the language of answer-set optimization (ASO) programs. The languge can be used in many practial scenarious that combine hard constraints with preferences. Preferences may come from a single agent or from a group of agents. They may be of the same importance or they may be ranked. Among the key outcomes of this project concerning ASO programs are the complexity results and algorithms to compute sets of optimal outcomes subject to additional constraints (similar to each other, similar to a given outcome, or dissimilar from each other). An observation that many problems studied in the social choice area have natural counterparts for ASO programs is another important outcome of the project. We generalized some of those social choice problems, namely manipultion and bribery, to the setting of ASO programs and obtained results characterizing possibility of manipulation and bribery, and the complexity of determining whether either is possible. This research further strengthens an inherent connection between preference representation and reasoning and social choice. We also studied a fundamental property of ASO programs, their strong equivalence. Speaking informally, we described situations when some group of preferences and hard constraints can be replaced by another, equivalent one. The term "strong" indicates that the rewriting works no matter what context the preferences are used in. Using these results, we also established the complexity of determining whether two ASO programs are equivalent. Our work on graphical models resulted in several formalisms similar to CP-nets but lending themselves to simpler reasoning. These models are based on a concept of a decision trees. Our study was motivated by existing work on lexicographic preference trees. We extended that work by proposing partial preference trees and preference trees as more expressive formalisms. The main feature of these formalisms is their intuitive nature suggesting that they may provide useful and effective models of preferences that are formed and held by humans. We studied reasoning tasks for theories in these languages, obtained complexity results and proposed practical computational techniques. In a project concerning the combinatorial domain of subsets of a given universe, we investigated formalisms to describe ways preferences on a set of elements can be lifted to preferences on subsets of that set. Some of the techniques we proposed exploit the ceteris paribus paradigm from CP-nets and can capture a large class of such liftings. In another project, related to preferences but not falling in the main stream of our research, we studied criteria of optimality that could narrow down a class of abductive explanations. This work resulted in a novel way of defining optimal explanations that limits the so called degrees of freedom or, informally, arbitrary choices made when committing to an explanation. The concerp of the constrained explanation is the first significant new criterion of quality proposed in the area of abduction in several years. Among important outcomes of the project are new courses on preferences and social choice developd by the PI and offered to students of the University of Kentucky and Warsaw University of Technology. Elements of preference reasoning in the context of voting are incorporated into a new course on networks in social and economical settings that has been approved as part of The University of Kentucky Core (our name for general education courses) in the area of quantitative reasoning. It will be offered for the first time in Spring 2015. The project contributed to the development of the human capital bu providing mentoring as well as research opportunities to three undergraduate students and four PhD students. Two of these students were the integral part of the team and made significant contributions to the project. They are expected to graduate in Spring 2016.
