\documentclass{llncs}

\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{makeidx}

\def\pareto{\times}

\begin{document}
\mainmatter  

\title{Preferences in an Open World}
\author{Ulrich Junker}
%\date{}      
\institute{
\email{uli.junker@free.fr}
}

\maketitle
	
\begin{abstract}
\sloppy
We consider constructive approaches to decision making which allow incomplete preference orders over multiple criteria. Whereas additional preferences may be acquired during the decision making process, the set of criteria is usually kept fixed. In this paper, we study the addition of new criteria and examine how this may refine or even reverse the existing preferences. We identify essential changes in the preference order and show that these changes provide a compact representation of preference relations in an open world.
\end{abstract}

\section{Introduction}

We consider constructive approaches to decision making which allow incomplete preference orders over multiple criteria. Whereas additional preferences may be acquired during the decision making process, the set of criteria is usually kept fixed. We believe that this assumption is not realistic and that the discovery of new dimensions or the merging of different viewpoints may lead to the discovery of new preferences that could not be formulated within the more restricted viewpoints. 

In this paper, we propose a more realistic preference acquisition model. The key notion is that of enlarging given viewpoints. The notion of a viewpoint is used by \cite{bouyssou:06} to describe an independent way of analyzing, evaluating, and comparing alternative actions. In collaborative decision making, different agents want to make a common decision by comparing the outcomes of the actions. As different agents may prefer different outcomes, each agent has a particular viewpoint and these viewpoints have different preference relations. In multi-criteria decision making, multiple outcomes of the actions may be compared independently of each other. Each of these outcomes constitutes a criterion for evaluating and comparing the actions. For example, we may compare the available hotels for a night stop by criteria such as their price and their distance to the airport. Each of these criteria can constitute an independent viewpoint. In this case, any trade-off between the two criteria price and distance is as good as the other those trade-offs. However, multiple criteria can also be combined into a single viewpoint. If the decision maker has preferences between different price- and distance-combinations, then we encounter a viewpoint which maps the different actions to a combinatorial outcome space defined by price and distance.

In the same way as preferences may be acquired or discovered incrementally, it may also happen that new criteria are discovered during such an incremental decision making process. We thus enlarge an existing viewpoint to a new viewpoint by adding a new dimension to the original outcome space. For example, our decision maker may suddenly discover that the hotels around the airport differ much in quality. As a consequence, the two-dimensional outcome space over price and distance is replaced by a three-dimensional outcome space defined by price, distance, and quality. We can then lift the preferences on the original outcome space to the new outcome space in a ceteris-paribus manner. However, the enlarged viewpoint may refine and even reverse these preferences lifted from the original viewpoint. These changes between expected and actual preference orders provide crucial information for preference representation and reasoning.

The paper is organized as follows: section \ref{viewpoint-section} and \ref{combinatorial-section} recall background in decision making in terms of the concept of a viewpoint.  Section \ref{enlargement-section} introduces the new concept of enlarging a viewpoint. Sections \ref{reduction-section}
%, \ref{factorization-section} 
and \ref{compact-enlargement-section} study compact representations in terms of transitive reductions.


\section{Viewpoints with Incomplete Preferences}
\label{viewpoint-section}

We consider classic decision-making problems where a single decision has to be chosen from a set of actions ${\cal A}$. A {\em viewpoint} constitutes an independent way to analyze the actions and to evaluate and compare the outcomes of the actions  \cite{bouyssou:06}. We restrict our discussion to viewpoints where actions have a deterministic outcome. A viewpoint captures weak preferences between outcomes, i.e. certain outcomes are at least as preferred as other outcomes. We follow a constructive approach to decision making  where the preference relation between outcomes is incomplete initially and can successively be refined, for example by eliciting information from the decision maker. However, we suppose that the preference relation between outcomes is reflexive and transitive, i.e. an incomplete pre-order $\succsim$. This permits to model indifference, strict preferences, and incomparability between outcomes:

\begin{definition}
A {\em viewpoint} $v$ for a set of actions ${\cal A}$ is characterized by an outcome space $\Omega_v$, a criterion $z_v: {\cal A} \rightarrow \Omega_v$ which maps actions to their outcomes, and a pre-order $\succsim_v$ over $\Omega_v$ which defines weak preferences between outcomes.
\end{definition}

Two different viewpoints for the same set of actions may differ in their preferences, their criteria, and their outcome spaces. The first difference is encountered in collaborative decision making where multiple agents want to make a common decision, but compare the same outcomes of the actions differently. A good example is the choice of a restaurant by a group of people who have different preferences about the kind of food that is served. Hence, each agent has a separate viewpoint and these viewpoints map the actions to the same outcomes, but differ in their preference relations. The second difference is obtained if two viewpoints map the actions to different outcomes from the same outcome space. This occurs in robust decision making involving multiple scenarios. For example, optimistic scenarios may assume small delays for given flights, whereas pessimistic scenarios may assume large delays for the same flights. Each scenario constitutes a viewpoint and the viewpoints map the actions to the outcomes differently, but use the same preferences for comparing them. The third difference is encountered in multi-criteria decision making and multi-objective optimization \cite{ehrgott:00} where each viewpoint defines a distinct outcome space or dimension. For example, there may be a viewpoint considering the costs of a trip, another viewpoint for the comfort, and a third viewpoint for the interest of the trip.

We now discuss how to make rational decisions from a viewpoint with incomplete preferences. We recall that a pre-order $\succsim_v$ over $\Omega_v$ can be split into a strict preference relation $\succ_v$ and an indifference relation $\sim_v$.
An outcome $\omega_1$ is strictly preferred to an outcome $\omega_2$ iff $\omega_1$ is weakly preferred to $\omega_2$, but not vice versa. The outcomes $\omega_1$ and $\omega_2$ are indifferent iff $\omega_1$ is weakly preferred to $\omega_2$   
and $\omega_2$ is weakly preferred to $\omega_1$. The strict relation $\succ_v$ is a strict partial order and the indifference relation is an equivalence relation. Furthermore, two outcomes $\omega_1$ and $\omega_2$ are called comparable iff either  $\omega_1$ is weakly preferred to  $\omega_2$ or $\omega_2$ is weakly preferred to $\omega_1$. A pre-order $\succsim_v$ is called complete iff all pairs of outcomes are comparable.

In a constructive approach to decision making, preference relations are initially incomplete and are successively refined. This can be achieved by eliciting preferences actively from a user, by learning user preferences passively, or by constructing these preferences according to higher-level reflections. We thus encounter a sequence of viewpoints having the same criteria, but more and more refined preference relations with the purpose of reaching complete relations in the end of this construction process. We impose some constraints on the way a viewpoint $w$ may extend the preference relation of a viewpoint $v$. Firstly, we suppose that preferences are added, but not removed, meaning that the pre-order $\succsim_w$ is a superset of the pre-order $\succsim_v$. If we allow the addition of arbitrary preferences, we may end in viewpoints that are indifferent among all outcomes. Whereas the addition of new preferences preserves previous indifference relations between outcomes, it need not preserve a strict preference between an outcome $\omega_1$ and $\omega_2$ since a weak preference between $\omega_2$ and $\omega_1$ may be added. In order to preserve strict preferences, we forbid the addition of preferences among comparable outcomes:

\begin{definition}
A viewpoint $w$ is an {\em extension} of a viewpoint $v$ iff these viewpoints are defined for the same actions ${\cal A}$, agree in their outcome spaces and criteria,  i.e. $\Omega_v = \Omega_w$ and $z_v = z_w$, and the preference relations $\succsim_w$ and $\succsim_v$ agree on all outcomes that are comparable with respect to  $\succsim_v$.
\end{definition}

If the preference relation of a viewpoint $v$ is incomplete, we can define an extension with fewer incomparable outcomes by choosing a pair of incomparable outcomes $\omega_1$ and $\omega_2$ and by making them comparable. We can either establish a strict preference or an indifference. We thus obtain three ways of extending $\succsim_v$. We either add the pair $(\omega_1, \omega_2)$ or the pair $(\omega_2, \omega_1)$, or both pairs to $\succsim_v$, and determine the transitive closure of the result, which will be the pre-order $\succsim_w$ of a new viewpoint $w$ which has the same outcome space and criterion as $v$. It can be shown that this new viewpoint $w$ is an extension of $v$. 

%proof: we need properties of incomparability

An incomplete viewpoint can thus be made complete by a sequence of steps where each step transforms at least one pair of incomparable outcomes into a pair of comparable outcomes. It can therefore be shown that complete extensions of a viewpoint always exist. Moreover, incomplete viewpoints  have more than one complete extension.

Viewpoints with complete pre-orders satisfy the postulates of rational decision making. Complete viewpoints have an outcome that is at least as preferred as all outcomes. A rational decision of a complete viewpoint is an action that produces this optimal outcome. An incomplete viewpoint has multiple complete extensions. We say that a rational decision of an incomplete viewpoint is an action that leads to an optimal outcome in some complete extension of the viewpoint. It can be shown that an outcome is optimal in some complete extension of a viewpoint iff it is non-dominated in the viewpoint, i.e. there is no strictly preferred outcome in the viewpoint:

\begin{proposition}
Let $v$ be a viewpoint. An outcome $\omega^* \in \Omega_v$ is optimal in some complete extension $w$ of $v$, i.e. $\omega^* \succsim_w \omega$ for all $\omega \in \Omega_v$, iff there is no outcome $\omega \in \Omega_v$ s.t. $\omega \succ_v \omega^*$.
\end{proposition}


Thanks to this, it is not necessary to construct the complete extensions of a viewpoint to find its rational decisions. It is sufficient to find the non-dominated outcomes of the incomplete viewpoints and to determine the decisions that lead to these outcomes.


\section{Combinatorial Viewpoints}
\label{combinatorial-section}


So far we have considered examples for multiple viewpoints that have same criteria or that have distinct criteria. In this section, we explore a further possibility, namely that the criteria of two viewpoints partially overlap. This possibility may arise for combinatorial outcome spaces which are the Cartesian product of several 'dimensions' $\Omega_{v,1}, \ldots, \Omega_{v,n}$. 
Two viewpoints partially overlap if their outcome spaces share some dimension. We introduce the notion of a combinatorial viewpoint that exhibits this structure:

\begin{definition}
A {\em combinatorial viewpoint} $v$ for a set of actions ${\cal A}$ is characterized by $n_v$ outcome spaces $\Omega_{v,1}, \ldots, \Omega_{v,n_v}$, $n_v$ criteria $z_{v,i}: {\cal A} \rightarrow \Omega_{v,i}$ that map the actions to these outcome spaces,
and  a weak preorder $\succsim_v$ over the Cartesian product $\Omega_{v,1} \times \ldots \times \Omega_{v,n_v}$ of the outcome spaces.
\end{definition}

A combinatorial viewpoint $v$ corresponds to a standard viewpoint that has the combinatorial outcome space $\Omega_{v} := \Omega_{v,1} \times \ldots \times \Omega_{v,n_v}$ and the criterion $z_{v}: {\cal A} \rightarrow \Omega_{v}$ that maps an action $a$ to the vector $z(a) := (z_{v,1}(a), \ldots, z_{v,n_v}(a))$. Moreover, a standard viewpoint corresponds to a combinatorial viewpoint of single dimension.

There are many examples for combinatorial viewpoints in the real-world. In cooperative decision making, multiple agents may be regrouped in different interest groups. Each interest group constitutes a viewpoint. Each agent who is a member of the group defines a dimension of this combinatorial viewpoint. As the same agent can belong to multiple interest groups, these groups may have dimensions in common. Combinatorial viewpoints are also encountered in multi-criteria decision making as multiple criteria can be combined together.

This discussion shows that combinatorial viewpoints can be combined into larger viewpoints. In certain cases, they can also be decomposed into smaller viewpoints. Sometimes, it may be necessary to permute the dimensions and criteria of a viewpoint. We therefore define a three operations on viewpoints, namely decomposition, aggregation, and permutation.

If a combinatorial viewpoint $v$ has a group of criteria that are preferentially independent from the other criteria, we can extract this group of criteria and define a smaller viewpoint for it. Let $I$ be a set of indices from $1,\ldots,n_v$. If this set consists of the indices $i_1,\ldots,i_k$ and these indices are listed in increasing order, we denote the subspace for these indices by $\Omega_I := \Omega_{v,i_1} \times \ldots \times \Omega_{v,i_k}$. A vector $\alpha$ from $\Omega_I$ may replace the elements of a vector $\beta$ from $\Omega$  at indices $I$. We denote this by $r_I(\alpha,\beta)$. The $i$-th element of the resulting vector is equal to $\alpha_{j}$ if $i$ is equal to $i_j$ and it is equal to $\beta_i$ if $i$ is not in $I$. The criteria $z_{v, i_1},\ldots,z_{v, i_k}$ are preferentially independent from the remaining criteria iff all $\alpha,\beta$ in $\Omega_I$ and all $\gamma,\delta$ in $\Omega$ satisfy $r_I(\alpha,\beta) \succsim_v r_I(\beta,\gamma)$ if and only if $r_I(\alpha, \delta) \succsim_v r_i(\beta, \delta)$. We can therefore safely define a viewpoint $w$ that has the outcome spaces $\Omega_{v,i_1}, \ldots,\Omega_{v,i_k}$, the criteria $z_{v,i_1},\ldots,z_{v,i_k}$ and the preference order $\succsim_w$ such that $\alpha \succsim_w \beta$ iff $r_I(\alpha, \gamma) \succsim_v r_I(\beta, \gamma)$ for all $\gamma \in \Omega$. 

Two combinatorial viewpoints $v$ and $w$ can be aggregated into a viewpoint $u$ with $n_v+n_w$ dimensions by using the Pareto-dominance. The resulting Pareto-aggregation is new viewpoint that has all the outcome spaces $\Omega_{v,1}, \ldots, \Omega_{v,n_v}$, $\Omega_{w,1}, \ldots, \Omega_{w,n_w}$ and the criteria $z_{v,1}, \ldots, z_{v,n_v},z_{w,1}, \ldots, z_{w,n_w}$. Its pre-order $\succsim_u$ is the weak Pareto-dominance order for the pre-orders $\succsim_v$ and $\succsim_w$. Given an outcome  $\omega := (\omega_1,\ldots,\omega_{n_u})$ in $\Omega_u$, we denote the sub-vector $(\omega_i,\ldots,\omega_j)$ in $\Omega_u$ from index $i$ to $j$ by $\omega_{[i,j]}$. An outcome $\omega^*$ from $\Omega_u$ is weakly preferred to an outcome $\omega$ from $\Omega_u$, i.e. $\omega^* \succsim_u \omega$ iff $\omega^*_{[1,n_v]} \succsim_v \omega_{[1,n_v]}$ and $\omega^*_{[n_v+1,n_u]} \succsim_v \omega_{[n_v+1,n_u]}$.  Note that the criteria of viewpoint $v$ are preferentially independent from the criteria of viewpoint $w$ in the Pareto-aggregagtion and vice versa. Moreover, the weak Pareto-dominance order is the smallest relation that has this property.

\sloppy
Sometimes it is necessary to permute the criteria of the viewpoint. Let $\pi$ be a permutation of the indices $1,\ldots,n_v$. Applying this permutation to the viewpoint $v$ results into a new viewpoint $\pi(v)$. It has the outcome spaces $\Omega_{v,\pi_1}, \ldots, \Omega_{v,\pi_{n_v}}$, the criteria $z_{v,\pi_1}, \ldots, z_{v,\pi_{n_v}}$ and  a weak preorder $\succsim_{{\pi}(v)}$ such that $(\omega^*_{\pi_1},\ldots,\omega^*_{\pi_{n_v}}) \succsim_{{\pi}(v)} (\omega_{\pi_1},\ldots,\omega_{\pi_{n_v}})$ iff  $(\omega^*_1,\ldots,\omega^*_{n_v}) \succsim_v (\omega_{1},\ldots,\omega_{{n_v}})$. 

\section{Enlargement of Viewpoints}
\label{enlargement-section}

The field of multi-criteria decision aiding makes the assumption that all criteria are identified before the preference elicitation starts. The identification of these criteria or objectives is a substantial part of the decision analysis process as explained in the second chapter of Raiffa`s and Keeney's seminal work \cite{keeney-raiffa:76}. The criteria  define the world in which preferences will be elicited, learned, or constructed. The usual assumption is that this world is closed, meaning that neither new values, nor new dimensions can be added to the outcome space. Nevertheless, the discovery of new dimensions happens quite often if the decision maker deals with a new domain. In this case, the decision making process is unstructured and ill-framed and the decision maker learns step by step which criteria are important. If new criteria are discovered, we say that the current viewpoint is enlarged. We enlarge a viewpoint by adding new dimensions and criteria to it:

\begin{definition}
A combinatorial viewpoint $w$ for the set of actions ${\cal A}$ is an {\em enlargement} of a combinatorial viewpoint $v$  for the set of actions ${\cal A}$ iff $n_w \geq n_v$ and $\Omega_{v,i} = \Omega_{w,i}$ and $z_{v,i} =z_{w,i}$ for all $i = 1,\ldots,n_v$.
\end{definition}

The addition of new dimensions raises new questions concerning the preference elicitation. What should happen to the existing preferences that are defined over the existing dimensions when a new dimension is discovered? We may assume that the original criteria are preferentially independent from the new criteria. This assumption defines a default preference relation $\succsim_{v \rightarrow w}$ for an enlargement, namely $\alpha \succsim_{v \rightarrow w} \beta$ iff $\alpha_{[1,n_v]} \succsim_{v} \beta_{[1,n_v]}$ and $\alpha_{[n_v+1, n_w]} = \beta_{[n_v+1, n_w]}$. This relation is a pre-order.

However, the user may give additional preference information that either refines or overrides this default preference relation. Indeed, we can suppose that the discovery of a new dimension triggers a profound preference revision process which revisits the preferences of the original viewpoint. The decision maker can then state whether this preference holds for all, for some, or no value of the new dimension. In the first case, the decision maker sticks to the default order. In the second case, she should list the values of the third dimension for which the preference still holds. In the third case, she should completely reverse the preference. Moreover, the decision maker may not only modify the existing preferences, but also add new ones. Hence, an enlargement adds preferences to the default preference relation and removes others from it. 

The added preferences are obtained as set difference of the enlargement preferences and the default preference relation, i.e. $A := \{ (\alpha, \beta) \in \Omega_w^2 \mid \alpha \succsim_w \beta \;\mathrm{and}\; \beta \not\succsim_{v \rightarrow w} \alpha \}$. The removed preferences are obtained as set difference of the  the default preference relation and the enlargement preferences, i.e. $R := \{ (\alpha, \beta) \in \Omega_w^2 \mid \alpha \succsim_{v \rightarrow w} \beta \;\mathrm{and}\; \beta \not\succsim_w \alpha \}$. By definition, these two sets are disjoint and the pre-order $\succsim_w$ is obtained from the pre-order $\succsim_{v \rightarrow w}$ by removing $R$ and by adding $A$. Hence, the sets of added and removed preferences capture the important changes in the preference relation due to the revision process that is initiated by the discovery of a new dimension.

We can also define enlargements by combining two viewpoints $v$ and $w$. The combination has the outcome spaces and criteria of the viewpoints $v$ and $w$, but may have an arbitrary preference relation. The weak Pareto dominance relation based on $\succsim_v$ and $\succsim_w$ provides a default preference relation for the combination if no other preference information for the combination is given. The sets of added and removed preferences can be defined for this default preference relation as before.


\section{Compact Representations by Transitive Reductions}
\label{reduction-section}

In the remainder of the paper, we investigate compact representations for preference relations of viewpoints, starting with that of standard viewpoints. Compact representations can be obtained by exploiting the structure of a concept. Pre-orders can be split into a strict partial order and an equivalence relation. Equivalence relations can be represented in form of a set of equivalence classes. For each equivalence class, a representative is chosen and the classes are represented by mapping the elements of the considered outcome space to this representative. Strict partial orders can be represented by a directed acyclic graph such that the transitive closure of this graph is equal to the pre-order. The essential notion here is that of a transitive reduction of a graph.

A transitive reduction of a binary relation $R$ over $\Omega$ is a minimal subset of $R$ that has the same transitive closure as $R$  \cite{aho:72}. As the transitive reduction is minimal it does not contain a pair $(\alpha,\gamma)$ if it already contains the pairs $(\alpha,\beta)$ and $(\beta,\gamma)$. With other words, the transitive reduction is anti-transitive. Formally, a relation $R$ over $\Omega$  is {\em anti-transitive} iff for all $\alpha,\beta,\gamma \in \Omega$ the following property holds:
\begin{equation}
(\alpha,\beta) \in R \; \mathrm{and} \: (\beta,\gamma) \in R \; \mathrm{implies} \: (\alpha,\gamma) \notin R
\end{equation}

A transitive reduction establishes anti-transitivity, but unfortunately a transitive reduction need not be unique. For example, the relation $\{ (a,b), (a,c), (b,a), (b,c), (c,a), c,b) \}$ has two transitive reductions, namely $\{ (a,b), (b,c), (c,a) \}$ and
$\{ (a,c), (c,b), (b,a) \}$. Moreover the definition of a transitive reduction is not symmetrical to that of a transitive closure. The transitive closure $R^+$ of a binary relation $R$ is defined as the smallest superset of this relation that is transitive. In analogy, we define the {\em strong transitive reduction} $R^-$ of a binary relation $R$ as a greatest subset of this relation that is anti-transitive. This set is obtained by removing all transitive links from $R$:
\begin{equation}
R^- = R - \{ (\alpha,\beta) \in R \mid \mathrm{there\ is} \; \beta \in \Omega \; \mathrm{s.t.} \; (\alpha,\beta) \in R \; \mathrm{and} \: (\beta,\gamma) \in R \}
\end{equation}
As a consequence of this correspondence, the strong transitive reduction always exists and is unique. The strong transitive reduction of an anti-transitive relation is equal to this relation. Furthermore the strong transitive reduction is monotonic in the following sense: Let $R_1$ and $R_2$ be two binary relations over $\Omega$. If $R_1 \subseteq R_2$ then $R_1^- \subseteq R_2^-$.
The strong transitive reduction of a strict partial order is sufficient to represent the strict partial order:
\begin{proposition}
Let $\succ$ be a strict partial order over $\Omega$ and  $\succ^-$ be its strong transitive reduction. The transitive closure of $\succ^-$ is equal to $\succ$.
\end{proposition}
Moreover, the strong transitive reduction of a strict partial order is equal to the transitive reduction of the strict partial order. If a binary relation is anti-transitive and acyclic, then the strong transitive reduction of its transitive closure is equal to this binary relation.

The strong transitive reduction of a pre-order only represents the strict part of this pre-order and removes indifference:
\begin{proposition}
Let $\succsim$ be a pre-order over $\Omega$ and  $\succsim^-$ be its strong transitive reduction. The transitive closure of $\succsim^-$ is equal to the strict part $\succ$ of $\succsim$.
\end{proposition}
Usually, the available preference information will not be given in form of a pre-order, but in form of some binary relation $R$ over $\Omega$. The pre-order is then obtained as the reflexive transitive closure $R^*$ of this binary relation. According to the properties above, the strong transitive reduction $R^-$ extracts the strict preferences from $R$. Indeed, the transitive closure of $R^-$ is the strict part of $R^*$.  

The strong transitive reduction can be computed by standard graph algorithms. In a first step, the strongly connected components of $R$ can be computed by Tarjan`s algorithms. Each strongly connected component is an equivalence class in the indifference relation of $R^*$. After this, the graph without strongly connected components is constructed. This graph is a directed acyclic graph and represents the strict preferences. An algorithm for computing the transitive reduction can then be used. As the graph is acyclic its transitive closure is a strict partial order, meaning that the resulting transitive reduction is equal to the strong transitive reduction. 

We can thus determine a compact representation for viewpoint preferences by using standard graph algorithms. The notion of a strong transitive reduction gives a clear  characterization of this representation. 


\section{Compact Representations for Enlargements}
\label{compact-enlargement-section}

We now seek compact representations for enlargements. An enlargement$w$ of a combinatorial viewpoint $v$ adds a new dimension. The default preference order for the enlargement is the pre-order $\succsim_{v \rightarrow w}$ which simply assumes that the previous criteria are preferentially independent of the new criteria and that this is all what is known. However, the decision maker adds preferences to this default order and removes other preferences  from it in order to establish the new pre-order of $w$. Can we find compact representations of these change sets?

We are now interested to transform the strong transitive reduction $\succsim^-_{v \rightarrow w}$ of the default pre-order $\succsim_{v \rightarrow w}$ into the strong transitive reduction $\succsim_w^-$. We neglect here the question of the change of indifference classes as this is a relatively simple task. Existing classes may be split into disjoint subsets and some of these subsets may be merged into new classes. In the remainder of the section we focus on the question of how to represent changes in the strict preferences.

%First we examine some further properties of transitive reductions and closures. Given two binary relations $R_1$ and $R_2$, we 
%obtain $R_1^+ \cup R_2^+ \subseteq (R_1 \cup R_2)^+$  and $R_1- \cup R_2^- \subseteq (R_1 \cup R_2)^-$  by monotonicity of the closure and reduction operators. Similarly, we obtain $(R_1 \cap R_2)^+ \subseteq R_1^+ \cap R_2^+$ and $(R_1 \cap R_2)^- \subseteq R_1^- \cap R_2^-$. Concerning set difference, we are observing that $(R_1 - R_2)^+ \subseteq R_1^+ $  and
%$(R_1 - R_2)^- \subseteq R_1^- - R_2^-$.

Instead of using the original change sets, we now consider the changes in the strong transitive reductions of the pre-order of the enlargement and the default preference order. The removed preferences are $\Delta_{v - w} := \{ (\alpha, \beta) \in \Omega_w^2 \mid \alpha \succsim^-_{v \rightarrow w} \beta \;\mathrm{and}\; \beta \not\succsim^-_w \alpha \}$ and the added preferences are $\Delta_{w- v} := \{ (\alpha, \beta) \in \Omega_w^2 \mid \alpha \succsim^-_w \beta \;\mathrm{and}\; \beta \not\succsim^-_{v \rightarrow w} \alpha \}$. 

Both sets are anti-transitive and acyclic since they are subsets of a strong transitive reduction. Moreover, the added preferences $\Delta_{w- v}$ do not belong to the strong reduction of the default preference order $\succsim^-_{v \rightarrow w}$ and the removed preferences $\Delta_{v - w}$ belong to it. It is possible that the set of added preferences $\Delta_{w- v}$ contains a pair $(\alpha, \beta)$ although $\alpha \succ_{v \rightarrow w} \beta$ holds. In this case, the set of removed preferences  $\Delta_{v - w}$ must contain a preference from each chain $\gamma_1,\ldots,\gamma_k$ s.t. $\alpha = \gamma_1$, $\gamma_i  \succ^-_{v \rightarrow w} \gamma_{i+1}$ for $i =1,\ldots,k-1$, and $\gamma_k = \beta$ in order to respect the anti-transitivity of $\succsim_w^-$. Furthermore it is possible that the set of added preferences $\Delta_{w- v}$ contains a pair $(\alpha, \beta)$ although $\beta \succ_{v \rightarrow w} \alpha$ holds. In this case, the set of removed preferences  $\Delta_{v - w}$ must contain a preference from each chain $\gamma_1,\ldots,\gamma_k$ s.t. $\beta = \gamma_1$, $\gamma_i  \succ^-_{v \rightarrow w} \gamma_{i+1}$ for $i =1,\ldots,k-1$, and $\gamma_k = \alpha$ in order to respect the acyclicity  of $\succ^-_w$.

Vice versa, if two binary relations $\Delta_1$ and $\Delta_2$ respect those properties, then adding $\Delta_1$ to the default preference order and removing $\Delta_2$ from it results in an anti-transitive and acyclic relation $R$. The transitive closure of this relation is a strict partial order and the strong transitive reduction of this strict partial order is equal to $R$. This leads to the following representation theorem which describes how to modify the preference relation of an existing viewpoint. We here suppose that the viewpoint $v$ is an enlargement that has the default preference relation:

\begin{proposition}
Let $v$ be a combinatorial viewpoint, $\succ_v^-$ the strong transitive reduction of its strict preferences, and $\Delta_1$ and $\Delta_2$ be two binary relations over $\Omega_v$ such that the following properties hold:
\begin{enumerate}
\item $\Delta_1$ and $\Delta_2$ are anti-transitive and acyclic.
\item $\Delta_1$ is a subset of  $\succ_v^-$ and $\Delta_2$ is disjoint to $\succ_v^-$.
\item If  $\alpha \succ \beta$ for an $(\alpha, \beta) \in \Delta_2$ then for each chain $\gamma_1,\ldots,\gamma_k$ satisfying $\alpha = \gamma_1$, $\gamma_i  \succ_v^- \gamma_{i+1}$ for $i =1,\ldots,k-1$ and $\gamma_k = \beta$ there exists a $j$ s.t. 
 $(\gamma_j, \gamma_{i+1}) \in \Delta_1$.
\item If  $\alpha \succ \beta$ for an $(\beta, \alpha) \in \Delta_2$ then for each chain $\gamma_1,\ldots,\gamma_k$ satisfying $\alpha = \gamma_1$, $\gamma_i  \succ_v^- \gamma_{i+1}$ for $i =1,\ldots,k-1$ and $\gamma_k = \beta$ there exists a $j$ s.t. 
 $(\gamma_j, \gamma_{i+1}) \in \Delta_1$.
 \end{enumerate}
Then $\{ (\alpha,\beta) \in \Omega_v^2 \mid \alpha \succ_v^- \beta \} - \Delta_1 \cup \Delta_2$ is an anti-transitive and acyclic relation.
\end{proposition}




This proposition imposes conditions on the preferences that a decision maker may add to and remove from a default preference relation when discovering a new dimension. It ensures that the current viewpoint can be enlarged to a new viewpoint while keeping the representation of preferences compact and while minimizing the changes.
 
%
%\section{Compact Representations by Factorization}
%\label{factorization-section}

%computation: Tarjan's altgorithm computes a spanning forest and decomposes the edge set into tree edges, forward edges, cross edges and backward edges.

%
%factors: minimal independent parts

%each factor is described by a set of indices

%decomposing a viewpoint into factors

%original viewpoint can be obtained by Pareto-aggregation + permutation

%a note on transitive reductions

\section{Conclusion}

This paper considered constructive decision making processes which not only support incremental preference elicitation, but also the discovery of new criteria during this process. If this happens, a new dimension is added to the outcome space. By default, the existing preferences are interpreted as ceteris-paribus preferences on this new space meaning that they hold independent of the value of the new dimension. This interpretation results into a default preference relation on the new outcome space. As a new dimension has been discovered, the existing preferences may be revisited within a preference revision process. As a consequence, the decision maker may remove or modify existing preferences and add new ones. We have elaborated conditions on these change sets that ensure the validity of the resulting preference relation and a compact representation.

In the final version of the paper, we will extend this treatment of enlargements of viewpoints which are due to the combination of multiple viewpoints which have been independent so far. This may be useful in group decision making when two groups merge together for the purpose of lobbying. The merger may revise some of the existing group preferences. Inversely, this more general notion of enlargement also permits a compact representation of combinatorial viewpoints. If the criteria of such a viewpoint can be partitioned into mutually independent factors, then is it possible to decompose the viewpoint completely into smaller parts. If preferential independence is not guaranteed in general, then it may still be reasonable to perform the decomposition and to compare its Pareto-aggregation with the original viewpoint. If the change sets are small, then the decomposition and the change sets may provide a more compact representation of the original viewpoint.

This work has been started as an attempt to provide a clear meaning to the preference reversal approach in \cite{junker:aaai07}, which seeks to elaborate optimization method under change sets. Different forms of preference revision are also studied in \cite{chomicki:05}. Furthermore, operations for the enlargement and compaction of outcome spaces are introduced in \cite{wicker:08} for the purpose of defining similarity measures for preference orders. Further work is needed to establish the precise relationship between those approaches.

\bibliographystyle{plain}
\bibliography{pow}

\end{document}  