Summarizing Conditional Preference Networks

Abstract

Preference modeling has been studied extensively in the literature, and has applications in recommender systems and automated decision-making. The eventual objective of working with preference models is to be able to reason about preferences over objects, often referred to as outcomes. In most of the literature, each outcome is described as an assignment of values to a set of attributes. Representing and reasoning about preferences over outcomes calls for efficient preference models. In this thesis, we focus on one such model, Con- ditional Preference Networks (CP-nets). A CP-net is a graphical model that captures the preferences of an individual using a directed graph, with vertices representing attributes and edges representing dependency relations between attributes. Information about the preferential dependence/independence be- tween attributes can be leveraged to efficiently order outcomes without exhaus- tively comparing all attributes in a pair of outcomes. In most existing studies, it is assumed that each individual user has their unique CP-net representing their preferences. In this thesis, we propose an approach to aggregate the preferences of multiple users via a single CP-net, while minimizing disagree- ment with individual users. We assume that each user has their preferences represented via a separable CP-net, i.e., a CP-net without any edges between attributes. Our goal is to represent the preferences of a group of users using a single CP-net, referred to as a summary CP-net. We present two algorithms that assume all the input CP-nets are separable, with results on correctness and complexity for each algorithm. We also present a discussion on some important properties of CP-nets and the impact these have on our algorithms.