\documentclass[twoside,11pt]{article}

\usepackage{epsfig,graphics,latexsym}
\usepackage{amsmath,amssymb,theorem,enumerate}
\usepackage{jair}
\usepackage{theapa}
\usepackage{array}
\usepackage{wasysym}
\usepackage{multirow}
\usepackage{stmaryrd}
\usepackage{float}

\usepackage{graphicx}


%% XY-pic
\input xy
\xyoption{all}



%\input{macros}
\newcommand{\scite}{\citeyear}
\newcommand{\CP}{\emph{ceteris paribus}}
\newcommand{\PI}{\textit{PI}}
\newcommand{\CPI}{\textit{CPI}}
\newcommand{\cmplet}{\textit{Comp}}
\newcommand{\Dom}{\textit{Dom}}
\newcommand{\Assg}{\textit{Asst}}
\newcommand{\Pa}{\textit{Pa}}
\newcommand{\CPT}{\textit{CPT}}
\newcommand{\itree}{T}
\newcommand{\wtree}{T^{-1}}
\newcommand{\dquery}[1]{#1\models^{?}}

\newcommand{\mynote}[1]{\begin{center}\fbox{\parbox{5in}{#1}}\end{center}}

\newcommand{\blackslug}{\mbox{\hskip 1pt \vrule width 4pt height 8pt 
   depth 1.5pt \hskip 1pt}}
% \newcommand{\QED}{\quad\blackslug\lower 8.5pt\null\par}
\newcommand{\QED}{\quad$\square$\lower 8.5pt\null\par}



\newenvironment{proof}{{\noindent\bf Proof:}}{{\QED}}
\newenvironment{proofa}{{\noindent\bf Proof:}}{\ \\}
\newenvironment{nproof}[1]{{\noindent\bf Proof (#1):}}{{\QED\ \\}}

\newenvironment{atheorem}[1]{{\vspace{0.4cm}\noindent\bf Theorem~\ref{#1}}~~}
                            {\\}
\newenvironment{alemma}[1]{{\vspace{0.4cm}\noindent\bf Lemma~\ref{#1}}~~}
                            {\\}

{\theorembodyfont{\rmfamily}\newtheorem{defn}{Definition}}
{\theorembodyfont{\rmfamily}\newtheorem{example}{Example}}

%OLDER MACROS
% \newenvironment{proof}{\begin{quotation}{\bf Proof: }}{\QED
%   \end{quotation}}

% %\newcommand{\proof}{\par\penalty-1000\vskip .5 pt\noindent{\bf Proof\/: }}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calA}{\mathcal{A}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\bfX}{\mathbf{X}} %
\newcommand{\bfx}{\mathbf{x}} %
\newcommand{\bfY}{\mathbf{Y}} %
\newcommand{\bfy}{\mathbf{y}} %
\newcommand{\bfZ}{\mathbf{Z}} %
\newcommand{\bfz}{\mathbf{z}} %
\newcommand{\bfV}{\mathbf{V}} %
\newcommand{\bfv}{\mathbf{v}} %
\newcommand{\bfU}{\mathbf{U}} %
\newcommand{\bfu}{\mathbf{u}} %
\newcommand{\bfW}{\mathbf{W}} %
\newcommand{\bfw}{\mathbf{w}} %
\newcommand{\bfA}{\mathbf{A}} %
\newcommand{\bfB}{\mathbf{B}} %
\newcommand{\bfC}{\mathbf{C}} %

% \newtheorem{exmpl}{Example}
\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newcommand{\tuple}[1]{\left<#1\right>}
\newcommand{\stuple}[1]{\langle #1\rangle}

\newcommand{\pref}{\succ}
\newcommand{\prefeq}{\succeq}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Fonts
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\defemb#1#2{\expandafter\def\csname #1\endcsname
                              {\relax\ifmmode #2\else\hbox{$#2$}\fi}}

\defemb{bp}{{\bf p}}
\defemb{bU}{{\bf U}}
\defemb{bu}{{\bf u}}
\defemb{bV}{{\bf V}}
\defemb{bW}{{\bf W}}
\defemb{bw}{{\bf w}}
\defemb{bX}{{\bf X}}
\defemb{bx}{{\bf x}}
\defemb{bY}{{\bf Y}}
\defemb{by}{{\bf y}}
\defemb{bZ}{{\bf Z}}
\defemb{bz}{{\bf z}}

                            
\defemb{cA}{{\cal A}}
\defemb{cB}{{\cal B}}
\defemb{cC}{{\cal C}}
\defemb{cc}{{\cal c}}
\defemb{cD}{{\cal D}}
\defemb{cE}{{\cal E}}
\defemb{cF}{{\cal F}}
\defemb{cf}{{\cal f}}

\defemb{cG}{{\cal G}}
\defemb{GG}{{\cal G}}

\defemb{cI}{{\cal I}}
\defemb{cK}{{\cal K}}
\defemb{cP}{{\cal P}}
\defemb{cL}{{\cal L}}
\defemb{cN}{{\cal N}}
\defemb{cM}{{\cal M}}
\defemb{cR}{{\cal R}}

\defemb{cS}{{\cal S}}
\defemb{SS}{{\cal S}}

\defemb{cT}{{\cal T}}
\defemb{cV}{{\cal V}}
\defemb{cU}{{\cal U}}
\defemb{cO}{{\cal O}}
\defemb{cH}{{\cal H}}
\defemb{cX}{{\cal X}}
\defemb{cY}{{\cal Y}}
\defemb{cZ}{{\cal Z}}

\defemb{sP}{{\sf P}}
\defemb{sG}{{\sf G}}
\defemb{sU}{{\sf U}}
\defemb{sE}{{\sf E}}
\defemb{sI}{{\sf I}}
\defemb{su}{{\sf u}}
\defemb{se}{{\sf e}}
\defemb{ss}{{\sf s}}
\defemb{st}{{\sf t}}
\defemb{sp}{{\sf p}}
\defemb{si}{{\sf i}}
\defemb{sb}{{\sf b}}
\defemb{sw}{{\sf w}}
\defemb{sA}{{\sf A}}
\defemb{sB}{{\sf B}}
\defemb{sa}{{\sf a}}
\defemb{sb}{{\sf b}}
\defemb{scc}{{\sf c}}
\defemb{sd}{{\sf d}}



\defemb{tta}{{\tt a}}
\defemb{ttb}{{\tt b}}
\defemb{ttc}{{\tt c}}
\defemb{ttd}{{\tt d}}
\defemb{tte}{{\tt e}}
\defemb{ttf}{{\tt f}}

\defemb{bara}{{\bar{a}}}
\defemb{barb}{{\bar{b}}}
\defemb{barc}{{\bar{c}}}
\defemb{bard}{{\bar{d}}}
\defemb{bare}{{\bar{e}}}
\defemb{barf}{{\bar{f}}}
\defemb{barv}{{\bar{v}}}
\defemb{barx}{{\bar{x}}}

\defemb{bbarx}{{\bar{\bar{x}}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Development-only auxiliary tools
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\update}[1]{\textsf{\textbf{*#1*}}\marginpar{\textbf{\textsf{\sc
        UPDATE}}}}
\newcommand{\remark}[1]{\marginpar{\textbf{\textsf{\sc
        #1}}}}
\newcommand{\commentout}[1]{}
\newcommand{\removed}[1]{{\bf #1}}
\newcommand{\carmel}[1]{
  {\footnotesize
  \begin{center}
  \fbox{
    \begin{minipage}{4in}
      carmel: #1
    \end{minipage}    
    }
  \end{center}
  }
}

\newcommand{\todo}[1]{\textbf{**}\marginpar{\fbox{\textsf{{\tiny
\begin{tabular}{l}
#1
\end{tabular}}}}}}

\newcommand{\sset}[1]{
  \left\{ \begin{array}{l}#1\end{array} \right.}
\newcommand{\argmax}{\operatornamewithlimits{argmax}}
\newcommand{\argmin}{\operatornamewithlimits{argmin}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Commands
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newcommand{\strips}{\textsc{strips}}
\newcommand{\var}{X}

\newcommand{\parents}{\textsf{pred}}
\newcommand{\sons}{\textsf{succ}}
\newcommand{\lparents}{pred}
\newcommand{\lsons}{succ}

\newcommand{\Can}{\textsf{Can}}
\newcommand{\newCan}{\textsf{newCan}}
\newcommand{\FeasibleMust}{\textsf{FeasibleMust}}
\newcommand{\Req}{\textsf{Req}}
\newcommand{\newReq}{\textsf{newReq}}
\newcommand{\Neighbors}{\textsf{LockResult}}
\newcommand{\neighb}{\sigma}
\newcommand{\Max}{\textsf{Max}}
\newcommand{\Must}{\textsf{Must}}
\newcommand{\newMust}{\textsf{newMust}}
\newcommand{\minplan}{\textsf{MinPlanSize}}
\newcommand{\maxplan}{\textsf{MaxPlanSize}}
\newcommand{\mps}{\textsf{MPS}}
\newcommand{\numberofpaths}{\textsf{\rho}}

\newcommand{\val}{\vartheta}
\newcommand{\myvalue}{{\mathsf{val}}}
\newcommand{\POP}{{\sf PolytreePOP}}

%% Consistency
%% -----------

\newcommand{\MaxReq}{\textsf{MaxFlip}}
%\newcommand{\MaxReq}{\textsf{MaxReq}}
\newcommand{\MaxCan}{\textsf{MaxCan}}
\newcommand{\newMaxReq}{\textsf{newMaxReq}}
\newcommand{\FeasibleMaxReq}{\textsf{MaxReq}}
\newcommand{\MinFS}{\textsf{MinFS}}


%% Layout
%% ------

\newcommand{\pccss}{CPML\ }
% \newcommand{\gdecision}{{\sf General-Reconfiguration}}
% \newcommand{\decision}{{\sf Reconfiguration}}
% \newcommand{\decisionc}{{\sf ConstrainedReconfiguration}}
\newcommand{\gdecision}{{\sf Optimize\&Present}}
\newcommand{\decision}{{\sf Q-Optimize\&Present}}
\newcommand{\decisionc}{{\sf Constrained-Q-Optimize\&Present}}
\newcommand{\ilpsolve}{{\sf ILPsolver}}
\newcommand{\optimum}{BestConfiguration\ }


\newlength{\myparskip}
\newlength{\myparindent}
\setlength{\myparskip}{\parskip}
\setlength{\myparindent}{\parindent}
\newenvironment{myitemize}%         % close together top-level itemized list
   {\begin{list}{\labelitemi}{%
    \setlength{\parsep}{0cm}%
    \setlength{\itemsep}{0cm}%
    \setlength{\topsep}{0cm}%
    \setlength{\parskip}{0cm}%
    \setlength{\partopsep}{0cm}%
    \setlength{\listparindent}{\myparindent}%
   }}%
   {\end{list}}


\newcommand{\Cons}{\mbox{\it Cons}}
\newcommand{\FindMax}{\mbox{\it FindMax}}
\newcommand{\Out}{\mbox{\it Out}}
\newcommand{\Sat}{\mbox{\it Sat}}
\newcommand{\Unsat}{\mbox{\it Unsat}}
\newcommand{\true}{\mbox{\it true}}

\newcommand{\negn}{\overline}

\def\nat{{\mathbb N}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\jairheading{21}{2004}{135--191}{03/03}{02/04}
\ShortHeadings{CP-Nets}
{Boutilier, Brafman, Domshlak, Hoos \& Poole}
\firstpageno{135}



\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title{CP-nets: A Tool for Representing and Reasoning with Conditional
  \emph{Ceteris Paribus} Preference Statements}

\author{\name Craig Boutilier \email cebly@cs.toronto.edu\\
\addr  Department of Computer Science \\
       University of Toronto \\
       Toronto, ON, M5S 3H8, Canada
\AND
\name Ronen I. Brafman \email brafman@cs.bgu.ac.il \\
\addr Department of Computer Science \\
     Ben-Gurion University \\
      Beer Sheva, Israel 84105
\AND
%carmelfinal -- it is about the time to start using the new address :-)
\name Carmel Domshlak \email dcarmel@cs.cornell.edu \\
\addr Department of Computer Science \\
      Cornell University \\
      Ithaca, NY 14853, USA
%\name Carmel Domshlak \email dcarmel@cs.bgu.ac.il \\
% \addr Department of Computer Science \\
%       Ben-Gurion University \\
%       Beer Sheva, Israel 84105
\AND
\name Holger H. Hoos \email hoos@cs.ubc.ca \\
\addr Department of Computer Science \\
      University of British Columbia \\
      Vancouver, BC, V6T 1Z4, Canada
\AND
\name David Poole \email poole@cs.ubc.ca \\
\addr Department of Computer Science \\
      University of British Columbia \\
      Vancouver, BC, V6T 1Z4, Canada
}


\maketitle


\begin{abstract}
  Information about user preferences plays a key role in automated
  decision making. In many domains it is desirable to assess such
  preferences in a qualitative rather than quantitative way.  In this
  paper, we propose a qualitative graphical representation of
  preferences that reflects conditional dependence and independence of
  preference statements under a \emph{ceteris paribus} (all else being
  equal) interpretation.  Such a representation is often compact and
  arguably quite natural in many circumstances.  We provide a formal
  semantics for this model, and describe how the structure of the
  network can be exploited in several inference tasks, such as
  determining whether one outcome dominates (is preferred to) another,
  ordering a set outcomes according to the preference relation, and
  constructing the best outcome subject to available evidence.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

Extracting preference information from users is generally an arduous
process, and human decision analysts have developed sophisticated
techniques to help elicit this information \cite{howard:readings}.  A
key goal in the study of computer-based decision support is the
construction of tools that allow the preference elicitation process to
be automated, either partially or fully. Methods for extracting,
representing and reasoning about the preferences of naive users are
particularly important in AI applications, ranging from collaborative
filtering \cite{maes:aaai94} and recommender systems
\cite{haddawy:recommender98} to product configuration
\cite{damb-birm:AIEng} and medical decision making
\cite{getoor:uai98}. In many of these applications users cannot be
expected to have the patience (or sometimes the ability) to provide
detailed preference relations or utility functions.  Typical users may
not be able to provide much more than qualitative rankings of fairly
circumscribed outcomes.

In this paper we describe a novel graphical representation, {\em CP-nets},
that can be used for specifying preference relations in a relatively
compact, intuitive, and structured manner using conditional {\em
  ceteris paribus\/} (all else being equal) preference statements.
CP-nets can be used to specify different types of preference
relations, such as a preference ordering over potential decision outcomes
or a likelihood ordering over possible states of the world,
for example, as in
Shoham's~\scite{shoham:ijcai87} preference semantics. 
However, it is mainly
the first type---preferences over the outcomes of decisions---that motivates 
the development of CP-nets.  The inference
techniques for CP-nets described in this paper focus on two 
important, related questions: how to perform preferential comparison
between outcomes, and how to find the optimal outcome 
given a partial assignment to the problem attributes.

Ideally, a preference representation should capture statements that
are natural for users to assess, be reasonably compact, and support
effective inference.  Our conditional \CP\ semantics requires that the
user specify, for any specific attribute $A$ of interest, which other
attributes can impact her preferences for values of $A$. For each
instantiation of the relevant attributes---the \emph{parents} of
$A$---the user must specify her preference ordering over values of $A$
conditional on the parents assuming the instantiated values; for
instance, $a_1$ may be preferred to $a_2$ when $b_1$ and $c_2$ hold.
Such a preference is given a \CP\ interpretation: $a_1$ is preferred
to $a_2$ given $b_1$ and $c_2$ {\em all else being equal}. In other
words, for any fixed instantiation of the remaining attributes, an
outcome where $a_1$ holds is preferred to one where $a_2$ holds
(assuming $b_1$ and $c_2$).  Such statements are arguably quite
natural and appear in several places (e.g., in e-commerce
applications).  For instance, the product selection service offered by
Active Buyer's Guide\footnote{See {\tt www.activebuyersguide.com}.}
asks for (unconditional) \CP\ statements in assessing a user's
preference for various products. The tools there also ask for certain
semi-quantitative information about preferences. Conditional
expressions offer even greater flexibility.

Preference elicitation is a complex task and is a key focus of work in
decision analysis \cite{keeney-raiffa,howard:readings,french},
especially elicitation involving non-expert users.  Automating the
process of preference extraction can be very difficult.  There has
been considerable work on exploiting the structure of preferences and
utility functions in a way that allows them to be appropriately
decomposed
\cite{keeney-raiffa,bacchus-grove:uai95,bacchus-grove:kr96,lamura-shoham:uai99}.
For instance, if certain attributes are {\em preferentially
independent} of others \cite{keeney-raiffa}, one can assign degrees of
preference to these attribute values without worrying about other
attribute values.  Furthermore, if one assumes more stringent
conditions, often one can construct an additive value function in
which each attribute contributes
%ronen Proper English?
to overall preference to a specific``degree'' (the {\em weight} of
that attribute) \cite{keeney-raiffa}.  For instance, it is common in
some engineering design problems to make such assumptions and simply
require users to assess the weights \cite{damb-birm:AIEng}.  This
allows the direct tradeoffs between values of different attributes to
be assessed concisely.  Case-based approaches have also recently been
considered \cite{haddawy:uai98}.

Models such as these make the preference elicitation process easier by
imposing specific requirements on the form of the utility or
preference function. We consider our CP-net representation to
offer an appropriate tradeoff between allowing flexible preference
expression and imposing a particular preference structure.
Specifically, unlike much of the work cited above, CP-nets capture
conditional preference statements.

The remainder of the paper is organized as follows.
Section~\ref{sec:model} provides background on preference orderings, and
important notions such as preferential independence and conditional
\CP\ preference statements. We then define CP-nets,
discussing their semantics and expressive
power in depth, and some of the model's properties.  In
Section~\ref{sec:outcomes} we present an algorithm for outcome
optimization in CP-nets and provide an example
of an application of CP-nets that
illustrates the optimization process.
Section~\ref{sec:dominance} introduces two kinds of queries for
preferential comparison, namely, ordering and dominance queries, and
investigates their computational
properties. Section~\ref{sec:techniques} discusses several general
techniques for answering dominance queries that exploit the
structure of a CP-net. In Section~\ref{sec:partial} we discuss the
applicability of our complexity results and algorithms to
a slight generalization of
CP-nets that allow incompletely specified local preferences and/or
statements of preferential indifference. Finally, in
Section~\ref{sec:conclude} we examine some related work and
applications of CP-nets, and discuss a number of interesting
directions for future theoretical research and applications.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

\section{Model Definition}
\label{sec:model}

Philosophical treatment of many intuitive qualitative preferential
statements began in 1957 in a pioneering work of Halld\'{e}n
\scite{Halden:57}, and was continued by Casta\~{n}eda
\scite{Castaneda:58}, von Wright \scite{vWright:63,vWright:72}, Kron
and Milovanovi\'{c} \scite{Kron:Milovanovic:75}, Trapp
\scite{Trapp:85}, and Hansson \scite{Hansson:96}.  The reason for such
an intensive analysis of these statements is expressed concisely in
the opening of Hansson's \scite{Hansson:96} paper:

\begin{center}
  \begin{minipage}{5in}
    When discussing with my wife what table to buy for our living
      room, I said: ``A round table is better than a square one.'' By
      this I did not mean that irrespectively of their other
      properties, any round table is better than any square-shaped
      table. Rather, I meant that any round table is better (for our
      living room) than any square table that does not differ
      significantly in its other characteristics, such as height, sort
      of wood, finishing, price, etc. This is preference {\em ceteris
        paribus} or ``everything else being equal''. \emph{Most of the
      preferences that we express or act upon seem to be of this
      type.} [Emphasis added.]
  \end{minipage}
\end{center}


An important property of {\em ceteris paribus} preferential
statements is their intuitive nature for users of all types.
%carmel2: changed below.
% The work of philosophers in this area has not
% escaped the attention of AI researchers. For example, 
% Doyle and Wellman~\scite{DoyleWellman.AAAI95}
% base their logic of relative desire on von Wright's
% logic of preferences.%
% \footnote{Doyle and Wellman's logic of relative desire contains, in
%   addition, a more powerful notion of {\em contextual equivalence} relation
%   between the propositions.  This notion allows them to support more
%   complicated inferences than those exhibited by von Wright's logic.}
Independently of the work of philosophers in this area,
reasoning about {\em ceteris paribus} statements has drawn the
attention of AI researchers.  For example, Doyle {\em et
al.}~\scite{DoyleShohamWellman.91} introduced a {\em logic of relative
desire} to treat preference statements under a {\em ceteris paribus}
assumption. This logic 
%carmelfinal --- I would like to be more careful here.
bears some similarity to
% is similar to 
von Wright's~\scite{vWright:63} logic of
preferences, but supports more complicated inferences.%
\footnote{For a more detailed 
discussion on this issue, we refer the reader
to~\citeA{DoyleWellman.AAAI95}.}
%carmel2: end of change
However, to the best of our knowledge, no serious attempt has been made to
exploit {\em preferential independence} for the compact and efficient
representation of such {\em ceteris paribus} statements.  In this paper, we
take steps toward structured modeling of qualitative {\em ceteris paribus}
preferential statements.


We start by defining the notion of a (qualitative) preference
relation and a number of basic preference independence concepts,
followed by the introduction of CP-nets and their semantics.

\subsection{Preference Relations}
\label{sec:prefs}

We focus our attention on single-stage decision problems with complete
information, ignoring in this paper any issues that arise in
multi-stage, sequential decision analysis and any considerations of risk that
arise in the context of uncertainty.%
\footnote{Such issues
include assigning preferences to {\em sequences} of outcome 
states, assessing uncertainty in beliefs and system dynamics, and 
assessing the user's attitude towards risk.}
%
We begin with an outline of relevant notions from
decision theory. We assume that the world can be in one
of a number of {\em states} $\calS$ and at each state $s$ there are
a number of {\em actions} $\calA_{s}$ that can be performed. Each
action, when performed at a state, has a specific {\em outcome}
(we do not concern ourselves with uncertainty in action effects
or knowledge of the state). The set of all outcomes is denoted
%carmelfinal -- added ``by''
by $\calO$. A {\em preference ranking} is
a total preorder $\prefeq$ over the set of outcomes: $o_1 \prefeq o_2$
means that outcome $o_1$ is equally or more preferred to the
decision maker than $o_2$. We use $o_1 \pref o_2$
to denote the fact that outcome $o_1$ is strictly more preferred by the
decision maker than $o_2$ (i.e., $o_1 \prefeq o_2$ and  $o_2\not
\prefeq o_1$), while $o_1 \sim o_2$
denotes that the decision maker is indifferent to $o_1$ and $o_2$
%carmel -- changed below (otherwise it is not a TOTAL preorder)
(i.e., $o_1 \prefeq o_2$ and  $o_2\prefeq o_1$).
% (i.e., $o_1 \not\prefeq o_2$ and  $o_2\not\prefeq o_1$). 
We will use the terms preference \emph{ordering} and \emph{relation}
interchangeably with \emph{ranking}.

The aim of 
decision making under certainty 
is, given knowledge of a specific state, to choose the action that
has the most preferred outcome. We note that the ordering
$\prefeq$ will vary across decision makers. For instance,
two customers might have radically different preferences
for computer system configurations that a sales program is helping
them construct. 

Often, for a state $s$, certain outcomes in $\calO$ cannot result from 
any action $a \in \calA_{s}$: those outcomes 
that can be obtained
are called {\em feasible outcomes} (given $s$). In many instances,
the mapping from states and actions to outcomes can be quite complex. In 
other decision scenarios, actions and outcomes may be equated:
a user is allowed to directly select a feasible outcome (e.g., select
a product with a desirable combination of attributes). Often
states play no role (i.e., there is a single state).

% hh>> minor changes, to correct problem in formalism:
One thing that makes decision problems difficult is the fact that outcomes
of actions and preferences are 
%carmelfinal
usually not
% not usually 
represented so directly.
For example, actions may be represented as a set of constraints
over a set of decision variables.
We focus here on preferences. We assume a set of {\em variables}
(or \emph{features} or \emph{attributes}) $\bfV = \{ X_1, \ldots, X_n \}$ over 
which the decision maker 
has preferences. Each variable $X_i$ is associated with a domain 
$\Dom(X_i) = \{ x^i_1, \ldots, x^i_{n_i} \}$ of {\em values} 
it can take.  
An \emph{assignment} $\bfx$ of values to a set $\bfX\subseteq \bfV$ 
of variables (also called an instantiation of $\bfX$)
is a function that maps each variable in $\bfX$ to
an element of its domain; if 
$\bfX=\bfV$, $\bfx$ is a \emph{complete assignment},
otherwise $\bfx$ is called a \emph{partial assignment}.
We denote the set of all assignments to $\bfX\subseteq \bfV$
by $\Assg(\bfX)$.
If $\bfx$ and $\bfy$ are assignments to disjoint
sets $\bfX$ and $\bfY$, respectively ($\bfX\cap \bfY = \emptyset$),
we denote the combination of $\bfx$ and $\bfy$ by $\bfx\bfy$.
If $\bfX\cup \bfY = \bfV$, 
we call $\bfx\bfy$ a \emph{completion} of 
assignment $\bfx$. 
We denote by $\cmplet(\bfx)$ the set of completions of $\bfx$.
Complete assignments correspond directly to the outcomes over which
a user possesses preferences. 
%ceb2: defined this notation
For any outcome $o$, we denote by $o[X]$ the value $x\in\Dom(X)$
assigned to variable $X$ by that outcome. 
%ceb2: decided to omit this notation, and always use o[X_i] for consistency
% We sometimes write
% $o[i]$ for $o[X_i]$ when variables are indexed.
%carmel2: I changed o[i] to o[X_i] in all of the remaining places.

Given a problem defined over
$n$ variables with domains $\Dom(X_1), \ldots, \Dom(X_n)$,
there are $|Dom(X_1)| \times \cdots \times |\Dom(X_n)|$ assignments.  Thus
direct assessment of a preference function is usually infeasible due to the
exponential number of outcomes.  Fortunately, a preference function can be
specified (or partially specified) concisely if it exhibits sufficient
structure.  We describe certain standard
types of structure here, referring to
Keeney and Raiffa \scite{keeney-raiffa} for a detailed description 
of these (and other) structural
forms and a discussion of their implications. 
A set of variables $\bfX$ is {\em preferentially independent} 
of its complement $\bfY = \bfV - \bfX$ iff, for
all $\bfx_{1}, \bfx_{2} \in \bf\Assg(X)$ and $\bfy_{1}, \bfy_{2} \in
\Assg(\bfY)$, we have
$$\bfx_{1}\bfy_{1} \succeq \bfx_{2}\bfy_{1} \;\mbox{ iff }\;
\bfx_{1}\bfy_{2} \succeq \bfx_{2}\bfy_{2}.$$
In other words, the structure of the preference relation over
assignments
to $\bfX$, when all other variables are held fixed, is the same no matter
what values these other variables take. If the
relation above holds, we say $\bfx_{1}$ is
preferred to $\bfx_{2}$ {\em ceteris paribus}.
Thus, one can assess the relative preferences over
assignments to $\bfX$ once, knowing these preferences do not change
as other attributes vary.  

We define
conditional preferential independence analogously. Let $\bfX$, $\bfY$,
and $\bfZ$ be nonempty sets that partition $\bfV$. 
%carmelfinal --- should not be a symmetric relation
$\bfX$ is \emph{conditionally preferentially independent} of $\bfY$
% $\bfX$ and $\bfY$ are \emph{conditionally preferentially independent} 
given an assignment $\bfz$ to $\bfZ$
% (denoted $\CPI(\bfX,\bfz,\bfY)$) 
iff, for all $\bfx_{1}, \bfx_{2} \in \Assg(\bfX)$ and
$\bfy_{1}, \bfy_{2} \in \Assg(\bfY)$, we have
%hhfinal: changed (for clarity, as discussed with david)
$$\bfx_{1}\bfy_1\bfz \succeq \bfx_{2}\bfy_{1}\bfz \;\mbox{ iff }\;
\bfx_{1}\bfy_{2}\bfz \succeq \bfx_{2}\bfy_{2}\bfz.$$
%$$\bfx_{1}\bfz\bfy_1 \succeq \bfx_{2}\bfz\bfy_{1} \;\mbox{ iff }\;
%\bfx_{1}\bfz\bfy_{2} \succeq \bfx_{2}\bfz\bfy_{2}.$$
In other words,
%carmelfinal --- same as above
$\bfX$ is preferentially independent of $\bfY$
% the preferential independence of $\bfX$ and $\bfY$ holds 
when $\bfZ$ is assigned $\bfz$. 
%carmelfinal --- same as above
If $\bfX$ is conditionally preferentially independent of $\bfY$
%If $\bfX$ and $\bfY$ are conditionally preferentially independent 
for all $\bfz \in \Assg(\bfZ)$, then $\bfX$
%carmelfinal --- same as above
is \emph{conditionally preferentially independent} of $\bfY$
%and $\bfY$ are \emph{conditionally preferentially independent} 
given the set of variables $\bfZ$.

Note that the {\em ceteris paribus} component of these definitions
ensures that the statements one makes are relatively weak. In
particular, they do not imply a stance on specific value tradeoffs.
Consider two variables $A$ and $B$ that are preferentially independent,
so that the preferences for values of $A$ and $B$ can be assessed
separately; for instance, suppose $a_1 \pref a_2$ and $b_1 \pref b_2$.
Clearly, $a_{1}b_{1}$ is the most preferred outcome and $a_{2}b_{2}$
is the least; but if feasibility constraints make $a_{1}b_{1}$
impossible, we must be satisfied with one of $a_{1}b_{2}$ or
$a_{2}b_{1}$. We cannot tell which is most preferred using these
separate assessments. However, under stronger conditions (e.g., {\em
  additive preferential independence}) one can construct an additive
value function in which weights are assigned to different attributes
(or attribute groups). Such a decomposition of a preference function
allows one to identify the most preferred outcomes rather readily, and
this, as well as some other special forms of preference structure, are
especially appropriate when attributes take on numerical values.
For an extensive discussion of various special forms of preference
functions we refer to Keeney and Raiffa \scite{keeney-raiffa}, as well as 
Bacchus and Grove \scite{bacchus-grove:uai95,bacchus-grove:kr96} and Shoham
\scite{Shoham.UAI97}. 


\subsection{CP-Networks}
\label{sec:cpnets}

Our representation for preferences is graphical in nature, and
exploits conditional preferential independence in structuring 
preferences of a user.  The model is similar to a Bayesian network \cite{pearl}
on the surface; however, the nature of the relation between nodes
within a network is generally quite weak (e.g., compared with the
probabilistic relations in Bayes nets). Others have defined graphical
representations of preference relations; for instance Bacchus and
Grove \scite{bacchus-grove:uai95,bacchus-grove:kr96} have shown some
strong results pertaining to undirected graphical representations of
additive independence. Our representation and semantics is rather
distinct, and our main aim in using the graph is to capture statements
of {\em qualitative} conditional preferential independence.  We note
that reasoning about \CP\ statements has been explored in AI
\cite{DoyleShohamWellman.91,DoyleWellman.AAAI91,DoyleWellman.AAAI95},
though not in the context of network representations or exploiting 
preferential independence in a computational fashion.

For each variable $X_i$, we ask the user to identify a set of {\em
  parent} variables $\Pa(X_i)$ that can affect her preference over
various values of $X_i$. That is, given a particular value assignment to
$\Pa(X_i)$, the user should be able to determine a preference order for
the values of $X_i$, all other things being equal.  Formally, given
$\Pa(X_i)$ we have that $X_i$ 
is conditionally preferentially independent
of $\bfV - (\Pa(X_i) \cup \{X_i\})$.  Given this information, we ask the
user to explicitly specify her preferences over the values of $X_i$ for all
instantiations of the variable set $\Pa(X_i)$.  We use the above
information to create an annotated directed graph in which
nodes stand for the problem variables, and every node $X_i$ has $\Pa(X_i)$
as its immediate ancestors. The node $X_i$ is annotated with a
{\em conditional preference table} (CPT) describing the user's
preferences over the values of the variable $X_i$ given every combination of parent
values. In other words, letting $\Pa(X_i) = \bfU$, for each assignment
$\bfu\in\Assg(\bfU)$, we assume that a total preorder $\prefeq^i_{\bfu}$
is provided over the domain of $X_i$: for any two values $x$ and
$x$, either $x \pref^j_\bfu x'$, $x' \pref^j_\bfu x$, or $x
\sim^j_\bfu x'$. For simplicity of presentation, we ignore indifference in
our algorithms. Though treatment of indifference is straightforward semantically,
consistency of arbitrary networks with indifference cannot be assumed,
as we discuss in Section~\ref{sec:indifference}.  Likewise, we assume
that CPTs for all variables are fully specified, though
we discuss partially specified CPTs in Section~\ref{sec:partial}.

We call these structures {\em conditional preference networks} or
\emph{CP-networks} (CP-nets, for short).
\begin{defn}
 A {\em CP-net} over variables $\bV = \{ X_1, \ldots, X_n \}$ is a
  directed graph $G$ over $X_1, \ldots, X_n$ whose nodes are annotated
  with conditional preference tables $\CPT(X_i)$ for each $X_i \in\bV$.  
  Each conditional preference table $\CPT(X_i)$ associates a total order
%hhfinal: notation for pref order from CPT was inconsistent throughout - changed
%       as per discussion with david:
$\pref^i_\bfu$ with each instantiation $\bu$ of $X_i$'s
%  $\succ_i(\bu_i)$ with each instantiation $\bu_i$ of $X_i$'s
  parents $Pa(X_i) = \bU$.
\end{defn}

%ceb: this comment not appropriate here
% Moreover, even cyclic CP-nets cannot express all possible
% total preference orderings, as can be shown by a simple counting argument.

We illustrate the CP-net semantics and some of its consequences with
several small examples.  For ease of presentation, all variables
in these examples are boolean, though our semantics is defined for
features with arbitrary finite domains.

\begin{example}[{\sf My Dinner I}]
  \label{ex:cpn1}
  Consider the simple CP-net in Figure~\ref{f:ex:cpn1}(a) that expresses
  my preference over dinner configurations. This network consist of
  two variables $S$ and $W$, standing for the soup and wine,
  respectively. Now, I strictly prefer fish soup ($S_f$) to vegetable soup ($S_v$),
  while my preference between red ($W_r$) and white ($W_w$) wine is conditioned
  on the soup to be served: I prefer red wine if served a vegetable soup,
  and white wine if served a fish soup.
  
  Figure~\ref{f:ex:cpn1}(b) shows the \emph{preference graph} over
  outcomes induced by this CP-net.  An arc in this graph directed from 
  outcome $o_i$ to $o_j$ indicates that a preference for $o_j$ over $o_i$
  can be determined directly from one of the CPTs in the CP-net. For
  example, the fact that $S_v \wedge W_r$ is preferred to $S_v \wedge W_w$
  (as indicated by the direct arc between them) is a direct consequence of
  the semantics of $\CPT(W)$.  The top element ($S_v \wedge W_w$)
  is the worst outcome while the bottom element ($S_f \wedge W_w$) is the
  best. $\square$
\end{example}




\begin{figure}
  \begin{center}
    \mbox{
      \begin{tabular}{cc}
      \begin{minipage}{2.5in}
        \begin{tabular}{cc}
          \multirow{4}{0.5in}{
            \def\objectsizestyle{\scriptstyle}
            \xymatrix @R=35pt@C=8pt{
              *++[o]=<1.5pc>[F]{S} \ar[d]\\
              *++[o]=<1.5pc>[F]{W}
              }
            } &
          \fbox{
            {\footnotesize
              $S_{f} \succ S_{v}$
              }}\\
          \ \\
          \ \\
          &
          {\footnotesize
            \setlength{\extrarowheight}{2pt}
            \begin{tabular}{|c|c|}
              \hline
              $S_f$ & $W_w\succ W_r$\\
              \hline
              $S_v$ & $W_r \succ W_w$\\
              \hline
            \end{tabular}
            }\\
          \ \\
          \ \\
          \ \\
          (a)\\
        \end{tabular}
      \end{minipage}&
      \begin{minipage}{1.5in}
        \begin{tabular}{c}
          \def\objectsizestyle{\scriptstyle}
          \xymatrix @R=20pt{
            *+[F-:<3pt>]{S_v\wedge W_w} \ar[d] \ar@/^4pc/[ddd]\\
            *+[F-:<3pt>]{S_v\wedge W_r} \ar[d]\\
            *+[F-:<3pt>]{S_f\wedge W_r}\ar[d]\\
            *+[F-:<3pt>]{S_f\wedge W_w}
            }\\
           \ \\
           (b)
        \end{tabular}
      \end{minipage}
    \end{tabular}
    }
\end{center}
%\caption{Illustration for Example~\ref{ex:cpn1}.}
\caption{(a) CP-net for ``My Dinner I'': Soup and Wine; (b) the induced
  preference graph.}
\label{f:ex:cpn1}
\end{figure}

\begin{example}[{\sf My Dinner II}]
  \label{ex:cpn2}  
  Figure~\ref{f:ex:cpn2}(a) extends the {\em chain} CP-net of
  Example~\ref{ex:cpn1} by adding the main course $M$ as another
  variable. In this example, my preference over the 
  options for the
  main course is clear: I strictly prefer a meat course $M_{mc}$ to a
  fish course $M_{fc}$.  In addition, I prefer not to have two fish
  courses in one dinner; thus my preference between vegetable and
  fish soup is conditioned on the main course: I prefer to open with
  fish soup if the main course is meat, and with vegetable soup
  if the main course is fish. As in Example~\ref{ex:cpn1},
  Figure~\ref{f:ex:cpn2}(b) shows the corresponding induced preference
  graph over outcomes. $\square$
\end{example}


\begin{figure}
%  \begin{center}
    \mbox{
      \begin{tabular}{cc}
      \begin{minipage}{2.2in}
        \begin{tabular}{cc}
          \multirow{7}{0.5in}{
            \def\objectsizestyle{\scriptstyle}
            \xymatrix @R=35pt@C=8pt{
              *++[o]=<1.5pc>[F]{M} \ar[d]\\
              *++[o]=<1.5pc>[F]{S} \ar[d]\\
              *++[o]=<1.5pc>[F]{W}
              }
            } &
          \fbox{
            {\footnotesize
              $M_{mc} \succ M_{fc}$
              }}\\
          \ \\
          \ \\
          &
          {\footnotesize
            \setlength{\extrarowheight}{2pt}
            \begin{tabular}{|c|c|}
              \hline
              $M_{mc}$ & $S_f \succ S_v$\\
              \hline
              $M_{fc}$ & $S_v \succ S_f$\\
              \hline
            \end{tabular}
            }\\
          \ \\
          \ \\
          &
          {\footnotesize
            \setlength{\extrarowheight}{2pt}
            \begin{tabular}{|c|c|}
              \hline
              $S_f$ & $W_w\succ W_r$\\
              \hline
              $S_v$ & $W_r \succ W_w$\\
              \hline
            \end{tabular}
            }\\
          \ \\
          \ \\
          \ \\
          (a)
        \end{tabular}
      \end{minipage}&
      \begin{minipage}{1.5in}
        {\scriptsize
        \begin{tabular}{c}
          \def\objectsizestyle{\scriptstyle}
          \xymatrix @R=25pt{
            & *+[F-:<3pt>]{M_{fc} \wedge S_f \wedge W_r} \ar[d]
                 \ar@/_1.5pc/[lddd] \ar@/^11pc/[ldddddd]\\
            & *+[F-:<3pt>]{M_{fc} \wedge S_f \wedge  W_w} \ar[d] \ar@/^5.5pc/[dddddd]\\
            & *+[F-:<3pt>]{M_{fc} \wedge S_v \wedge W_w} \ar[dd] \ar[ld]\\
            *+[F-:<3pt>]{M_{fc} \wedge S_v \wedge W_r} \ar[dd]\\
            & *+[F-:<3pt>]{M_{mc} \wedge S_v \wedge W_w} \ar[ld] \ar[ddd]\\
            *+[F-:<3pt>]{M_{mc} \wedge S_v \wedge W_r} \ar[d]\\
            *+[F-:<3pt>]{M_{mc} \wedge S_f \wedge  W_r} \ar[dr]\\
            & *+[F-:<3pt>]{M_{mc} \wedge S_f\wedge W_w}
            }\\
           \ \\
           (b)
        \end{tabular}
        }
      \end{minipage}
    \end{tabular}
    }
\caption{(a) CP-net for ``My Dinner II''; (b) the induced preference graph.}
\label{f:ex:cpn2}
\end{figure}


\begin{example}[{\sf Evening Dress}]
  \label{ex:cpn3}
  Figure~\ref{f:ex:cpn3}(a) illustrates another CP-net that expresses my
  preferences for evening dress. It consists of three
  variables $J$, $P$, and $S$, standing for the jacket, pants, and
  shirt, respectively.  I unconditionally prefer black to white as a
  color for both the jacket and the pants, while my preference between
  the red and white shirts is conditioned on the {\em combination} of
  jacket and pants: if they have the same color, then a white shirt
  will make my outfit too colorless, thus I prefer a red shirt.
  Otherwise, if the jacket and the pants are of different colors, then
  a red shirt will probably make my outfit too flashy, thus I
  prefer a white shirt. Figure~\ref{f:ex:cpn3}(b) shows the
  corresponding preference graph. $\square$
\end{example}







\subsection{Semantics}
\label{sec:semantics}


The semantics of a CP-net is straightforward. It is defined in terms
of the set of preference rankings that are consistent with the
set of preference constraints imposed by its CPTs.

\begin{defn}
Let $N$ be a CP-net over variables $\bfV$, $X_i\in\bfV$ be some variable, 
and $\bfU \subset \bfV$ be the parents of $X_i$ in $N$. Let $\bfY =
\bfV - (\bfU \cup \{X_i\})$.
Let $\pref^i_\bfu$ be the ordering over $\Dom(X_i)$
dictated by $\CPT(X_i)$ for any 
instantiation $\bfu\in\Assg(\bfU)$ of $X_i$'s parents. 
Finally let $\pref$ be a preference ranking over $\Assg(\bfV)$.

A preference ranking $\pref$ {\em satisfies} $\pref^i_\bfu$ iff
we have---for all $\bfy\in\Assg(\bfY)$ and all $x , x' \in\Dom(X_i)$---
$\bfy{x}\bfu \pref \bfy{x'}\bfu$ whenever $x \pref^i_\bfu x'$.
%
A preference ranking $\pref$ {\em satisfies} the CPT $\CPT(X_i)$ iff
it satisfies $\pref^i_\bfu$ for each $\bfu\in\Assg(\bfU)$.
%
A preference ranking $\pref$ {\em satisfies} the CP-net $N$ iff
is satisfies $\CPT(X_i)$ for each variable $X_i$.

\begin{figure}
% \begin{center}
    \mbox{
    \begin{tabular}{cc}
      \begin{minipage}{2in}
      \begin{tabular}{ccc}
        {\footnotesize
        \fbox{
          $J_{b} \succ J_{w}$
          }} & &
        \fbox{
          {\footnotesize
          $P_{b} \succ P_{w}$
          }}\\
        \ \\
      \multicolumn{3}{c}{
      \def\objectsizestyle{\scriptstyle}
      \xymatrix @C=8pt{
        *++[o]=<1.5pc>[F]{J} \ar[dr] & & *++[o]=<1.5pc>[F]{P}\ar[dl]\\
        & *++[o]=<1.5pc>[F]{S}
        }}\\
        \ \\
        \multicolumn{3}{c}{
          {\footnotesize
        \setlength{\extrarowheight}{2pt}
        \begin{tabular}{|c|c|}
          \hline
          $J_b \wedge P_b$ & $S_r \succ S_w$\\
          \hline
          $J_w \wedge P_b$ & $S_w \succ S_r$\\
          \hline
          $J_b \wedge P_w$ & $S_w \succ S_r$\\
          \hline
          $J_w \wedge P_w$ & $S_r \succ S_w$\\
          \hline
        \end{tabular}
        }}\\
        \ \\
        \ \\
        & (a)\\
      \end{tabular}
      \end{minipage} &
      \begin{minipage}{1.5in}
        {\scriptsize
        \begin{tabular}{c}
          \def\objectsizestyle{\scriptstyle}
          \xymatrix @R=35pt{
            & *+[F-:<3pt>]{J_w \wedge P_w \wedge S_w} \ar[d]
               \ar@/_2pc/[dddl] \ar@/_4pc/[ddd]\\
            & *+[F-:<3pt>]{J_w \wedge P_w \wedge S_r} \ar[d] \ar@/^0.5pc/[dr]\\
            & *+[F-:<3pt>]{J_w \wedge P_b \wedge S_r} \ar[d] \ar@/^3pc/[ddd] &
              *+[F-:<3pt>]{J_b \wedge P_w \wedge S_r} \ar@/^1.5pc/[dddl] \ar[dll] \\
            *+[F-:<3pt>]{J_b \wedge P_w \wedge S_w} \ar[dr] &
            *+[F-:<3pt>]{J_w \wedge P_b \wedge S_w} \ar[d] \\
            & *+[F-:<3pt>]{J_b \wedge P_b \wedge S_w} \ar[d]\\
            & *+[F-:<3pt>]{J_b \wedge P_b \wedge S_r}
            }\\
           \ \\
           (b)
        \end{tabular}
        }
      \end{minipage}
    \end{tabular}
    }
%  \end{center}
  \caption{(a) CP-Net for ``Evening Dress'': Jacket, Pants and Shirt;
           (b) the induced preference graph.}
%  \caption{Illustration for Example~\ref{ex:cpn3}.}
  \label{f:ex:cpn3}
\end{figure}









A CP-net $N$ is {\em satisfiable} iff there is some preference ranking
$\pref$ that satisfies it.
\end{defn}
Thus a network $N$ is satisfied by $\pref$ iff $\pref$ satisfies each of
the conditional preferences expressed in the CPTs of $N$ under the
\CP\ interpretation.

\begin{thm}\label{sat-lemma}
Every acyclic CP-net is satisfiable.
\end{thm}

\begin{proof}
We prove this constructively by building a satisfying preference
ordering. This proof is by induction on the number of variables. The theorem
trivially holds for one variable, as the total ordering is specified
directly by the CP-net.

Suppose the theorem holds for all CP-nets with fewer than $n$ variables. Let
$N$ be a network with $n$ variables. If $N$ is acyclic, there is at least
one variable with no parents; let $X$ be such a variable. Let
$x_1\pref x_2\pref \dots\pref x_k$ be the ordering over $\Dom(X)$
dictated by $CPT(X)$.  For each $x_i$, construct a CP-net, $N_i$,  with the $n-1$
variables $\bfV - \{X\}$ by removing $X$ from the initial CP-net, and for
each variable $Y$ that is a child of $X$, revising its
CPT by restricting each row to $X = x_i$.
By the inductive hypothesis, we can construct a preference ordering
$\pref_i$ for each of the reduced CP-nets $N_i$.

We can now construct a preference ordering for the original network $N$
as follows.  We rank every outcome with $X = x_i$ as preferred to any outcome
with $X = x_j$ if $x_i \pref x_j$ in $\CPT(X)$. For any outcomes 
with identical values $x_i$ of $X$, we rank them according to the ordering
$\pref_i$ associated with $N_i$ (ignoring the value of $X$).
It is easy to see that this preference ordering satisfies $N$.
\end{proof}



For example, consider the CP-net of Example~\ref{ex:cpn1}
(Figure~\ref{f:ex:cpn1}).  Somewhat surprisingly, the information captured by
this network is sufficient to totally order the outcomes:
\[
   S_f\wedge W_w \;\; \succ \;\;  S_f\wedge W_r \;\; \succ\;\;  S_v\wedge W_r \;\; \succ  \;\; S_v\wedge W_w 
\]
since this is the only ranking that satisfies this CP-net.  However,
%carmel2: added ``this'' in the line below
this need not be the case---in general, a satisfiable CP-net can be
satisfied by more than one ranking. For instance, consider the CP-net
in Figure~\ref{f:ex:cpn2.2}.\footnote{This is the network
from Example~\ref{ex:cpn2} (``My Dinner II'') with the variables renamed.} 
There are two rankings that satisfy this network:
\begin{eqnarray*}
   abc \succ ab\barc \succ a\barb\barc \succ a\barb c \succ \bara\barb\barc \succ
     \bara\barb c \succ \bara bc \succ \bara b\barc\\
   abc \succ ab\barc \succ a\barb\barc \succ \bara\barb\barc \succ a\barb c \succ 
     \bara\barb c \succ \bara bc \succ \bara b\barc
\end{eqnarray*}


\begin{figure}
  \begin{center}
    \mbox{
      \begin{tabular}{cc}
      \begin{minipage}{2.5in}
        \begin{tabular}{cc}
          \multirow{7}{0.5in}{
            \def\objectsizestyle{\scriptstyle}
            \xymatrix @R=35pt@C=8pt{
              *++[o]=<1.5pc>[F]{A} \ar[d]\\
              *++[o]=<1.5pc>[F]{B} \ar[d]\\
              *++[o]=<1.5pc>[F]{C}
              }
            } &
          \fbox{
            {\footnotesize
              $a \succ \bara$
              }}\\
          \ \\
          \ \\
          &
          {\footnotesize
            \setlength{\extrarowheight}{2pt}
            \begin{tabular}{|c|c|}
              \hline
              $a$ & $b \succ \barb$\\
              \hline
              $\bara$ & $\barb \succ b$\\
              \hline
            \end{tabular}
            }\\
          \ \\
          \ \\
          &
          {\footnotesize
            \setlength{\extrarowheight}{2pt}
            \begin{tabular}{|c|c|}
              \hline
              $b$ & $c \succ \barc$\\
              \hline
              $\barb$ & $\barc \succ c$\\
              \hline
            \end{tabular}
            }\\
          \ \\
          \ \\
          \ \\
          (a)
        \end{tabular}
      \end{minipage}&
      \begin{minipage}{1.5in}
        \begin{tabular}{c}
          \def\objectsizestyle{\scriptstyle}
          \xymatrix @R=15pt{
            & \bar{a}b\bar{c} \ar[d] \ar[lddd] \ar@/_5pc/[ldddddd]\\
            & \bar{a}bc \ar[d] \ar@/^2.5pc/[dddddd]\\
            & \bar{a}\bar{b}c \ar[dd] \ar[ld]\\
            \bar{a}\bar{b}\bar{c} \ar[dd]\\
            & a\bar{b}c \ar[ld] \ar[ddd]\\
            a\bar{b}\bar{c} \ar[d]\\
            ab\bar{c} \ar[dr]\\
            & abc
            }\\
           \ \\
           (b)
        \end{tabular}
      \end{minipage}
    \end{tabular}
    }
\end{center}

\caption{A simple chain-structured CP-network.}
\label{f:ex:cpn2.2}
\end{figure}


Preferential entailment in a CP-net is defined in a standard way.
\begin{defn}
Let $N$ be a CP-net over variables $\bfV$, and $o, o' \in \Assg(\bfV)$
be any two outcomes. $N$ \emph{entails} $o \pref o'$ (i.e., that
outcome $o$ is preferred to $o'$), written $N \models o\pref o'$, iff
$o\pref o'$ holds in every preference ordering that satisfies $N$.
\end{defn}

\begin{lemma}\label{lemma:transitive}
Preferential entailment is transitive. That is, if $N \models o\pref o'$
and $N \models o'\pref o''$ then $N \models o\pref o''$. 
\end{lemma}

\begin{proof}
If $N \models o\pref o'$ and $N \models o'\pref o''$ then 
$o\pref o'$ and $o'\pref o''$ in all preference rankings satisfying
$N$. As each of these rankings is transitive, we must have 
$o\pref o''$ in all satisfying rankings.
\end{proof}

For example, consider the CP-net $N$ in 
Figure~\ref{f:ex:cpn2.2}(a) and the following
three outcomes: $o = a b \barc$, $o' = a \barb \barc$, and $o'' = a
\barb c$.  The outcomes $o$ and $o'$ assign the same values to all
variables except of $B$. In addition, given the value of
$\Pa(B) = \{A\}$ in $o$ and $o'$,
the value of $B$ in $o$ ($B=b$) is preferred to
the value of $B$ ($B=\barb$) in $o'$, all else being equal.  
Therefore, we have that
$N \models o \succ o'$. In the case of $o'$ and
$o''$, the same argument with respect to the variable $C$ will show
that $N \models o' \succ o''$ as well. Observe
that $o \succ o''$ cannot be derived directly from the CPTs of $N$.
However, from Lemma~\ref{lemma:transitive}, it follows that this relation
can be inferred by taking the transitive closure of the direct relations
$o \succ o'$ and $o' \succ o''$.

Notice that, given a CP-net, we can assess each outcome in terms of
the conditional preferences it violates. For example, in the CP-net
of Example~\ref{ex:cpn1}: the outcome $S_f \wedge W_w$ violates none of
the preference constraints; $S_f \wedge W_r$ violates the conditional
preference for $W$; $S_v \wedge W_r$ violates the preference for $S$; and
$S_v \wedge W_w$ violates both.  Somewhat surprisingly, the
{\em ceteris paribus} semantics implicitly ensures 
that violating the preference
for $S$ is worse than violating that for $W$, since
$S_f \wedge W_r \succ S_v \wedge W_r$. That is, the parent 
preferences have higher
priority than the child preferences. This property has important
implications for inference as we will see below.


\subsection{Cyclic Networks}
\label{sec:cycles}

As mentioned, nothing in the semantics of the CP-net model forces it to be
acyclic. However, according to Theorem~\ref{sat-lemma}, the acyclicity of the
network automatically confers an important property to the model: the network
is satisfiable (i.e., there exists a preference ordering that satisfies all
\emph{ceteris paribus} preference assertions imposed by the CPTs).

For cyclic CP-nets, the situation is much more complicated. For example,
consider a binary-valued cyclic CP-net structure in Figure~\ref{fig:f1}(e).
%ceb2: not needed
% This
% network is defined over the variables $\{A,B\}$, where $A$ depends on
% $B$ and $B$ depends on $A$ ($\Dom(A)=\{a_1,a_2\}$ and
% $\Dom(B)=\{b_1,b_2\}$). 
%ceb2: rephrased
If the CPTs for this network are specified as in Figure~\ref{fig:f1}(a), then the induced
preference graph (see Figure~\ref{fig:f1}(b)) can be extended to a complete
preference ordering consistently.  However, if the CPTs are specified as in
Figure~\ref{fig:f1}(c), then the network is unsatisfiable 
(the induced preference graph, shown in Figure~\ref{fig:f1}(d) cannot be completed
consistently).  This example shows that the consistency of cyclic CP-nets is
not guaranteed, and depends on the actual nature of the CPTs.

\begin{figure}[htb]
    \begin{tabular}{ccc}
      \begin{minipage}{2in}
        \begin{eqnarray*}
          &&a_1: b_1 \succ b_2\\
          &&a_2 : b_2 \succ b_1 \\
          &&b_1: a_1 \succ a_2\\
          &&b_2 : a_2 \succ a_1
        \end{eqnarray*}
      \end{minipage}
      & 
      \begin{minipage}{1.6in}
        \mbox{
          \xymatrix{
            a_2b_1 \ar[d] \ar[dr] & a_1b_2 \ar[d] \ar[dl] \\
            a_1b_1 & a_2b_2
            }
          }
      \end{minipage}
      &
      \multirow{6}{0.6in}{
        \mbox{
        \xymatrix @R=75pt{
          *++[o]=<1.5pc>[F]{A} \ar@/_10pt/[d] \\
          *++[o]=<1.5pc>[F]{B} \ar@/_10pt/[u]
          }
        }
        }\\
      \ \\
      (a) & (b)\\ 
      \begin{minipage}{2in}
        \begin{eqnarray*}
          &&a_1: b_1 \succ b_2\\
          &&a_2 : b_2 \succ b_1 \\
          &&b_1: a_2 \succ a_1\\
          &&b_2 : a_1 \succ a_2
        \end{eqnarray*}
      \end{minipage}
      &
      \begin{minipage}{1.6in}
        \mbox{
          \xymatrix{
            a_1b_1 \ar[r] & a_1b_2 \ar[d]\\
            a_2 b_1 \ar[u] & a_2b_2 \ar[l]
            }
          }
      \end{minipage}\\
      \ \\
      (c) & (d) & (e)\\
    \end{tabular}\\
  \caption{Examples of a satisfiable and 
           an unsatisfiable cyclic CP-net over binary variables.}
  \label{fig:f1}
\end{figure}

Recently, initial results on consistency testing for cyclic CP-nets were
presented by Domshlak and Brafman \scite{Domshlak:Brafman:kr02}.  
In particular, a wide
class of cyclic, binary-valued CP-nets was identified
to be efficiently testable for
consistency. However, these results cover only part of the spectrum,
and further research on cyclic CP-nets is needed.

Beyond the open computational questions that cyclic CP-nets raise,
their usefulness requires further analysis.  One can argue
that it is possible to cluster the variables to preserve acyclicity.
Although this approach is technically feasible and probably useful in
many domains, it cannot provide a general solution.  First, such 
clustering will affect the space requirements of problem description
and thus, it will generally degrade the efficiency of reasoning
about preferences. Second, in certain domains, it may be more natural
to express cyclic preferences even if an acyclic representation could
be used. 
For example, this seems to be the case in
work on preference-based presentation of
web page content \cite{Domshlak:Brafman:Shimony:ijcai01}, where it is
argued that the preferred presentation of a certain component of a web page
may depend on the presentation of its neighbors in the page, whose
preferred presentation depend on its presentation, and so on.

%ronen1 changed
%One could argue that preferences naturally exhibit cyclic structure
%and that acyclic net are of theoretical interest only. From the
%experience we have had so far, this does not appear to be the
%case. 
One could argue that preferences naturally exhibit cyclic structure
and that acyclic nets are of theoretical interest only. Our experience
indicates the opposite. 
Acyclic CP-nets are shown to be effective and natural in the
above-mentioned work on web page presentation
\cite{Domshlak:Brafman:Shimony:ijcai01}, as well as in a related
project that deals with the presentation of multi-media content in a
medical domain \cite{Gudes:Domshlak:Orlov:mdde02}---a more extensive
example from this latter domain is presented in the next
section. 
%ronen1 added
Moreover, in other domains, we have found it difficult to generate
intuitively reasonable cyclic networks. This is due to the fact that a cycle
implies that all variables in it are equally important. Typically,
this is not the case.
%end
Thus, because of the apparent utility of acyclic networks,
the fact that we can use composite variables made by clustering primitive
variables, and the additional complexity
involved in cyclic networks, we consider only acyclic CP-nets in the
remainder of this paper. 
%ceb3: added to placate reviewer
However, further investigation of cyclic
CP-nets, as well as a characterization of the different classes of
utility functions that can be represented by cyclic and acyclic networks,
remains of interest.






\subsection{Indifference}
\label{sec:indifference}

We have so far assumed that the preference constraints in each CPT
of a CP-net totally order the outcomes of the variable in
question. Specifically, for any variable $X_i$ with
parents $\bfU$, and any $\bfu\in\Assg(\bfU)$, we assume that
$\pref^i_\bfu$ is a total order over $\Dom(X_i)$.
The general definition of a CP-net can allow an arbitrary
total preorder $\prefeq^i_\bfu$ over $\Dom(X_i)$, thus allowing
the user to express indifference between two values of variable
$X$, say $x$ and $x'$, given $\bfu$. We denote this by
$x \sim x'$ in $\CPT(X)$.

It turns out that the \CP\ semantics is quite strong when we
say that two variable values are equally preferred.
\begin{example}
Consider the following two CPTs for a network over variables
$A$ and $B$, with $A$ being a parent of $B$:
 \begin{gather*}
 a \sim \negn a; \\
 a: b \pref \negn b ;\;\;\; \negn a : \negn b \pref b; 
 \end{gather*}
These assert that the user is indifferent between $a$ and $\negn a$,
but should $a$ hold, prefers $b$, and should $\negn a$ hold, prefers
$\negn b$.
We can derive the following preferences over outcomes:
$$ab \pref a \negn b \prefeq \negn a \negn b \pref  \negn a b \prefeq ab$$
These statements are not consistent with any preference ranking,
hence this network is not satisfiable.
One way to interpret this is that if someone really did
have the preferences:
 $$a: b \pref \negn b ;\;\;\; \negn a : \negn b \pref b; $$
they cannot be indifferent between $a$ and $\negn a$, \CP{}. $\square$
\end{example}

This points to a potential difficulty with the use of indifference
in CP-nets. One must be careful not to express indifference between
two values of a variable ($A$ in this case), yet express a 
(strict) conditional preference for a child of that variable ($B$)
that depends on the values for which the user is indifferent.
Intuitively, in this case, it seems that the user is expressing
the fact that they would like the value of $B$ to match that of
$A$ (with respect to their ``sign''), but intends no preference
for $ab$ over $\negn a \negn b$ (or vice versa). If this is the
case, then making $A$ a parent of $B$ expresses that the preference
for $B$ is subsidiary to that of $A$, which is not the intent.
In this case, either a cyclic network (indeed the satisfiable
network discussed in Section~\ref{sec:cycles}) or the clustering
of variables $A$ and $B$ seems appropriate.

Despite this, indifference can be used safely as follows.  Let $X_i$
be any variable in network $N$ with parents $\bfU$, and let $X_j$ be
any child of $X_i$. Let $\bfY$ denote the remaining parents of $X_j$
(those excluding $X_i$).  Suppose that for some $\bfu\in\Assg(\bfU)$,
and $x, x' \in \Dom(X_i)$, we have $x \sim x'$ in $\prefeq^i_\bfu$.
Then as long as the local orderings in $\CPT(X_j)$ for a fixed
instantiation of $\bfY$ are identical whether $x$ or $x'$ holds, then the
network $N$ is satisfiable. More precisely, if $\prefeq^j_{x\bfy} =
\prefeq^j_{x'\bfy}$ for each $\bfy\in\Assg(\bfY)$, then network $N$ is
satisfiable. Thus, if we are indifferent between $x$ and $x'$, then
our preferences over values of $X_i$'s children, should exhibit
indifference whether the context includes $x$ or $x'$.%
\footnote{This restriction can be relaxed somewhat if we
take into account the fact that some of $X_j$'s parents could lie in
the set $\bfU$, in which case these rankings need  not agree for {\em
every} indifference pair $x$ and $x'$.}

For simplicity of presentation, for the remainder of the paper we
continue to assume that preference constraints in each CPT of a CP-net
totally order the outcomes of the variable in question.  However, in
Section~\ref{sec:partial}, we do discuss the applicability of our results
to satisfiable CP-nets that capture statements of preferential indifference.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Outcome Optimization}
\label{sec:outcomes}

One of the principal properties of CP-nets is that, given a CP-net
$N$, we can easily determine the best outcome among those preference
rankings that satisfy $N$. We call such a query an \emph{outcome
optimization} query. This turns to be a simple task in CP-nets. 

\subsection{An Algorithm for Outcome Optimization}

Intuitively, to generate an optimal outcome we simply need to sweep through
the network from top to bottom (i.e., from ancestors to descendents)
setting each variable to its most preferred value given the
instantiation of its parents.  Indeed, while the network does not
generally determine a unique ranking, it does determine a unique best
outcome (assuming no indifference).  More generally, suppose we are
given evidence constraining possible outcomes in the form of an
instantiation $\bfz$ of some subset $\bfZ \subseteq \bfV$ of the
network variables.  Determining the best completion of $\bfz$ (that
is, the best outcome consistent with $\bfz$) can be achieved in a
similar fashion, as we now outline.

Outcome optimization queries can be answered using the
following {\em forward sweep} procedure, taking time linear in the
number of variables.  Assume a partial instantiation
$\bfz\in\Assg(\bfZ)$, and the goal of determining the (unique) $o \in
\cmplet(\bfz)$ such that $N \models o \pref o'$ for all $o' \in
\cmplet(\bfz) - \{o\}$.  This can be effected by a straightforward
sweep through the network. Let $X_1,\ldots, X_n$ be any topological
ordering of the network variables. We set $\bfZ = \bfz$, and
instantiate each $X_i \not\in\bfZ$ in turn to its maximal value given
the instantiation of its parents. This procedure exploits the
considerable power of both the {\em ceteris paribus} semantics and the
graphical modeling of the preferential statements to easily
find an optimal outcome given certain observed evidence (or imposed conjunctive
constraints).
\begin{lemma}
  The forward sweep procedure constructs the most preferred outcome
  in $\cmplet(\bfz)$.
\end{lemma}

\begin{proof}
  Let $\bfv_{\bfz}$ be any outcome in the set of completions of
  $\bfz$.  Define a sequence of outcomes $\bfv_i$, $0 \leq i \leq n$,
  as follows: (a) $\bfv_0 = \bfv_{\bfz}$; (b)
  if $X_i \not\in \bfZ$, $\bfv_i$ is constructed by setting the value
  of $X_i$ to its most preferred value given the instantiation of its
  parents in $\bfv_{i-1}$, with all other variables retaining their
  values from $\bfv_{i-1}$; (c) if $X_i \in \bfZ$, then $\bfv_i = \bfv_{i-1}$.
  By construction, $\bfv_i \succeq \bfv_{i-1}$. The last outcome $\bfv_n$ is
  precisely that constructed by the forward sweep algorithm.
  Notice that we arrive at the same
  outcome irrespective of our starting point $\bfv_{\bfz}$
  (by assumption, there can be no ties). Since $\bfv_n \succeq \bfv_\bfz$ 
  for any outcome $\bfv_\bfz$
  consistent with the evidence, the forward sweep procedure yields the
  optimal outcome.
\end{proof}




\subsection{An Example Application}
\label{S:multimedia}

We now turn to an illustration of the use of CP-nets in
the context of a CP-net based system for adaptive multimedia document
presentation. Applications based on this system for the presentation
of web-based content and multi-media medical data were recently presented
by~\citeA{Domshlak:Brafman:Shimony:ijcai01} and
\citeA{Gudes:Domshlak:Orlov:mdde02}.
Through this example we demonstrate the simplicity of
preference specification using CP-nets, the utility of acyclic networks,
and the use of the optimization algorithm described above.

%carmel2: the first word : Our --> The
The system consists of two tools---the authoring tool, and the
viewing tool. The central part of the authoring tool is a module for
the specification of a CP-net corresponding to the created
and/or edited multimedia
document. Using this CP-net, a content provider express her preferences
regarding the presentation of the document content.  For example, the
content provider may prefer that some material be presented if and only
if some other material is not presented.  The result of such
preference-based multimedia document design is a meta-document specifying
both {\em what to present} and {\em how to present it}.

The description of the content provider's 
preferences, as captured by an acyclic
CP-net, becomes a static part of the document, and sets the
parameters for its initial presentation. Given such a document, the
viewing tool is responsible for reasoning about these preferences;
specifically, it must determine an optimal reconfiguration of the
document context after interaction of the viewer with the document. 
In this process, the user's $k$ most recent content choices are viewed 
as constraints of the form {\em ``these items must appear as I specified''}.
Subject to these constraints, an optimal document presentation with respect 
to the content provider's CP-net must then be generated. Thus, for each 
particular session, the actual presentation changes dynamically based on 
the user's choices. More precisely, whenever new user input is 
obtained, the optimization algorithm
constructs the best presentation of all document components
with respect to the content provider's preferences among those
presentations that conform to the user's recent viewing choices.  This
process uses the forward sweep procedure described above.


\begin{figure}
    \begin{tabular}{cccc}
      \includegraphics[width=2in]{mm-images/plainCTImage.ps} &
      \includegraphics[width=1in]{mm-images/plainXrayImage.ps} &
      \includegraphics[width=0.8in]{mm-images/segmentedXray.ps} &
      \includegraphics[width=2in]{mm-images/show.ps}\\
      \ \\
      (a) & (b) & (c) & (d)\\
    \end{tabular}
  \caption{Document components in Multimedia Document example.}
  \label{ex:mm-domains}
\end{figure}


\begin{example}[{\sf Multimedia Document}]
  Consider a medical record that consists of six components: two
  components correspond to a set of medical tests conducted in 2001---an 
  X-ray image and textual notes of a physician---and four
  components correspond to a set of medical tests from 2002---a 
  CT (computerized tomography) image, an X-ray image, a
  graph illustrating results of electromyography, and textual
  notes of a physician. For the purposes of illustration, we assume the
  preferences of a content
  provider (e.g., the latter physician) over the presentation options of
  these components can be captured using the CP-net shown in 
  Figure~\ref{fig:mm-cpn}. The specific details of the preferences---the 
  nature of the preferential dependencies and the precise details of the
  CPTs are summarized as follows:

  \begin{itemize}
  \item {\sf CT-image} [CT image, 2002] consist of four CT images of
    different parts of the body,  and it is shown in
    Figure~\ref{ex:mm-domains}(a). There are six presentation options
    for {\sf CT-image}: it can be either completely presented
    (${\mathsf{ct}}_{plain}$), or completely hidden
    (${\mathsf{ct}}_{hide}$), or presented by a zoom-in on one of its
    four parts (${\mathsf{ct}}_{lt}$, ${\mathsf{ct}}_{rt}$,
    ${\mathsf{ct}}_{lb}$, and ${\mathsf{ct}}_{rb}$, standing for
    left-top, right-top, left-bottom, and right-bottom parts, respectively).
    The physician's preference over the presentation options of {\sf
      CT-image} is unconditional:
    
    \begin{center}
    \begin{tabular}{|c|}
      \hline
      ${\mathsf{ct}}_{hide} \succ {\mathsf{ct}}_{lt} \succ {\mathsf{ct}}_{rt}
      \succ {\mathsf{ct}}_{lb} \succ {\mathsf{ct}}_{rb} \succ {\mathsf{ct}}_{plain}$\\
      \hline
    \end{tabular}
    \end{center}
        
\begin{figure}
  \begin{center}
    \mbox{
      \xymatrix @R=35pt@C=8pt{
        *+[F-:<3pt>]{{\mathsf{CT\!-\!image}}} \ar[dd] \ar[dr] \ar@/_3pc/[ddd]\\
        & *+[F-:<3pt>]{{\mathsf{X\!-\!ray}}} \ar[dl] \ar[d]\\
        *+[F-:<3pt>]{{\mathsf{Graph}}} \ar[d] & *+[F-:<3pt>]{{\mathsf{X\!-\!ray\!-\!old}}} \ar[d]\\
        *+[F-:<3pt>]{{\mathsf{Notes}}} & *+[F-:<3pt>]{{\mathsf{Notes\!-\!old}}}
        }
      }
  \end{center}
    \caption{Multimedia Document CP-net.}
    \label{fig:mm-cpn}
\end{figure}

\item {\sf X-ray} [X-ray, 2002] can be either hidden
  (${\mathsf{xray}}_{hide}$), or presented as is
  (${\mathsf{xray}}_{plain}$), or presented after a segmentation
  (${\mathsf{xray}}_{segm}$); the image and its segmentation are
  depicted in Figures~\ref{ex:mm-domains}(b)
  and~\ref{ex:mm-domains}(c), respectively. The preference over the
  presentation options of {\sf X-ray} depends on the presentation of
  {\sf CT-image}:
    
    \begin{center}
    \begin{tabular}{|c|c|}
      \hline
      ${\mathsf{ct}}_{plain}$ & ${\mathsf{xray}}_{hide} \succ
           {\mathsf{xray}}_{plain} \succ  {\mathsf{xray}}_{segm}$\\
      \hline
      $\neg ({\mathsf{ct}}_{plain} \vee {\mathsf{ct}}_{hide})$ &
           ${\mathsf{xray}}_{plain} \succ {\mathsf{xray}}_{segm} \succ
           {\mathsf{xray}}_{hide}$\\
      \hline
      ${\mathsf{ct}}_{hide}$ &  ${\mathsf{xray}}_{segm} \succ {\mathsf{xray}}_{plain}
          \succ {\mathsf{xray}}_{hide}$\\
      \hline
    \end{tabular}
    \end{center}
    
  \item {\sf Graph} [Electromyography, 2002] is shown in
    Figure~\ref{ex:mm-domains}(d), and it can be either presented
    (${\mathsf{graph}}_{plain}$), or hidden
    (${\mathsf{graph}}_{hide}$). The preference over the presentation
    options of {\sf Graph} depends on the presentation of both {\sf
      CT-image} and {\sf X-ray}:

    \begin{center}
    \begin{tabular}{|c|c|}
      \hline
      $({\mathsf{ct}}_{lt} \vee {\mathsf{ct}}_{rt}
      \vee {\mathsf{ct}}_{lb} \vee {\mathsf{ct}}_{rb}) \vee
        {\mathsf{xray}}_{segm}$ & ${\mathsf{graph}}_{plain} \succ {\mathsf{graph}}_{hide}$\\
      \hline
      ${\mathrm{otherwise}}$ & ${\mathsf{graph}}_{hide} \succ
              {\mathsf{graph}}_{plain} $\\
      \hline
    \end{tabular}
    \end{center}
    
  \item {\sf Notes} [Textual notes, 2002] can be either fully
    presented (${\mathsf{notes}}_{plain}$), or summarized
    (${\mathsf{notes}}_{summ}$), or omitted all together
    (${\mathsf{notes}}_{hide}$). The preference over the presentation
    options of {\sf Notes} depends on the presentation of both {\sf
      CT-image} and {\sf Graph}:
    
    \begin{center}
    \begin{tabular}{|c|c|}
      \hline
      ${\mathsf{ct}}_{hide}$ & ${\mathsf{notes}}_{hide} \succ {\mathsf{notes}}_{summ}
                  \succ {\mathsf{notes}}_{plain}$\\
      \hline
      $\neg ({\mathsf{ct}}_{hide}) \wedge {\mathsf{graph}}_{plain}$ &
          ${\mathsf{notes}}_{summ} \succ  {\mathsf{notes}}_{plain} \succ
          {\mathsf{notes}}_{hide}$\\
      \hline
      ${\mathrm{otherwise}}$ & ${\mathsf{notes}}_{hide} \succ {\mathsf{notes}}_{summ}
      \succ {\mathsf{graph}}_{plain}$\\
      \hline
    \end{tabular}
    \end{center}
    
  \item {\sf X-ray-old} [X-ray, 2001] can be either hidden
    (${\mathsf{xray\!-\!old}}_{hide}$), or presented as is
    (${\mathsf{xray\!-\!old}}_{plain}$); the image is depicted below. The
    preference over the presentation options of {\sf X-ray-old} depends on
    the presentation of {\sf X-ray}:

    \begin{center}
      \begin{tabular}{m{2in}m{0.2in}m{3in}}
        \fbox{
        \includegraphics[width=2in]{mm-images/plainXrayB.ps}} & &
        \begin{tabular}{|c|c|}
          \hline
          ${\mathsf{xray}}_{hide}$ & ${\mathsf{xray\!-\!old}}_{hide} \succ
          {\mathsf{xray\!-\!old}}_{plain}$\\
          \hline
          $\neg ({\mathsf{xray}}_{hide})$ &
          ${\mathsf{xray\!-\!old}}_{plain} \succ {\mathsf{xray\!-\!old}}_{hide}$\\
          \hline
        \end{tabular}
      \end{tabular}
    \end{center}

    
\begin{figure}
  \begin{center}
    \begin{tabular}{m{2in}m{3in}}
      \begin{minipage}{1.5in}
        {\scriptsize
        \def\objectsizestyle{\scriptstyle}
        \xymatrix @R=20pt@C=8pt{
        *+[F-:<3pt>]{{\mathsf{ct}}_{hide}} \ar[dd] \ar[dr] \ar@/_3pc/[ddd]\\
        & *+[F-:<3pt>]{{\mathsf{xray}}_{segm}} \ar[dl] \ar[d]\\
        *+[F-:<3pt>]{{\mathsf{graph}}_{plain}} \ar[d] &
            *+[F-:<3pt>]{{\mathsf{xray\!-\!old}}_{plain}} \ar[d]\\
        *+[F-:<3pt>]{{\mathsf{notes}}_{plain}} & *+[F-:<3pt>]{{\mathsf{notes\!-\!old}}_{hide}}
        }
      }
      \end{minipage} &
      \includegraphics[width=2in]{mm-images/snapshot1.ps}\\
      \multicolumn{2}{c}{
        (a)
        }\\
      \ \\
      \begin{minipage}{1.5in}
        {\scriptsize
        \def\objectsizestyle{\scriptstyle}
        \xymatrix @R=20pt@C=8pt{
        *+[F-,:<3pt>]{{\mathsf{ct}}_{rt}} \ar[dd] \ar[dr] \ar@/_3pc/[ddd]\\
        & *+[F-:<3pt>]{{\mathsf{xray}}_{plain}} \ar[dl] \ar[d]\\
        *+[F-:<3pt>]{{\mathsf{graph}}_{plain}} \ar[d] &
            *+[F-:<3pt>]{{\mathsf{xray\!-\!old}}_{plain}} \ar[d]\\
        *+[F-:<3pt>]{{\mathsf{notes}}_{summ}} & *+[F-:<3pt>]{{\mathsf{notes\!-\!old}}_{hide}}
        }
      }
      \end{minipage} &
      \includegraphics[width=3in]{mm-images/snapshot2.ps}\\
      \multicolumn{2}{c}{
        (b)
        }\\
      \ \\
      \begin{minipage}{1.5in}
        {\scriptsize
        \def\objectsizestyle{\scriptstyle}
        \xymatrix @R=20pt@C=8pt{
        *+[F-,:<3pt>]{{\mathsf{ct}}_{rt}} \ar[dd] \ar[dr] \ar@/_3pc/[ddd]\\
        & *+[F-,:<3pt>]{{\mathsf{xray}}_{hide}} \ar[dl] \ar[d]\\
        *+[F-:<3pt>]{{\mathsf{graph}}_{plain}} \ar[d] &
            *+[F-:<3pt>]{{\mathsf{xray\!-\!old}}_{hide}} \ar[d]\\
        *+[F-:<3pt>]{{\mathsf{notes}}_{summ}} & *+[F-:<3pt>]{{\mathsf{notes\!-\!old}}_{plain}}
        }
      }
      \end{minipage} &
      \includegraphics[width=2.4in]{mm-images/snapshot5.ps}\\
      \multicolumn{2}{c}{
        (c)
        }\\
      \ \\
      \begin{minipage}{1.5in}
        {\scriptsize
        \def\objectsizestyle{\scriptstyle}
        \xymatrix @R=20pt@C=8pt{
        *+[F-,:<3pt>]{{\mathsf{ct}}_{plain}} \ar[dd] \ar[dr] \ar@/_3pc/[ddd]\\
        & *+[F-,:<3pt>]{{\mathsf{xray}}_{hide}} \ar[dl] \ar[d]\\
        *+[F-:<3pt>]{{\mathsf{graph}}_{hide}} \ar[d] &
            *+[F-:<3pt>]{{\mathsf{xray\!-\!old}}_{hide}} \ar[d]\\
        *+[F-:<3pt>]{{\mathsf{notes}}_{hide}} & *+[F-:<3pt>]{{\mathsf{notes\!-\!old}}_{plain}}
        }
      }
      \end{minipage} &
      \includegraphics[width=1in]{mm-images/snapshot6.ps}\\
      \multicolumn{2}{c}{
        (d)
        }
    \end{tabular}      
  \end{center}
  \caption{Document presentations after various user choices.}
  \label{fig:snapshots}
\end{figure}

    
  \item {\sf Notes-old} [Textual notes, 2001] can be either 
    presented (${\mathsf{notes\!-\!old}}_{plain}$), or omitted all together
    (${\mathsf{notes\!-\!old}}_{hide}$). The preference over the presentation
    options of {\sf Notes-old} depends on the presentation of {\sf X-ray-old}:

    \begin{center}
    \begin{tabular}{|c|c|}
      \hline
      ${\mathsf{xray\!-\!old}}_{hide}$ & ${\mathsf{notes\!-\!old}}_{plain} \succ
                                      {\mathsf{notes\!-\!old}}_{hide}$\\
      \hline
      ${\mathsf{xray\!-\!old}}_{plain}$ & ${\mathsf{notes\!-\!old}}_{hide} \succ
                                       {\mathsf{notes\!-\!old}}_{plain} $\\
      \hline
    \end{tabular}
    \end{center}  
  \end{itemize}
  $\square$
\end{example}

At the beginning of a viewing session, the initial presentation of the
document, depicted in Figure~\ref{fig:snapshots}(a), is determined
using the forward sweep procedure with $\bZ = \emptyset$: each
component is set to its preferred presentation given the presentation
of its immediate parents in the CP-net.  For example, {\sf
  CT-image} is hidden, since it is the most preferred option for this
component. Subsequently, the {\sf X-ray} image is presented segmented,
since {\sf CT-image} is not presented, and, in turn, the
electromyography {\sf Graph} is presented because of the above
decision on the presentation options for {\sf CT-image} and {\sf
  X-ray}. Suppose that the viewer chooses to look at the right-top
part of the {\sf CT-image}.%
\footnote{A document explorer (which is a
 part of the viewing tool) is not illustrated here in order to make
 the snapshots smaller.}
%
In terms of the forward sweep procedure,
this choice sets $\bZ=\{{\mathsf{CT\!-\!image}}\}$, and
$\bz = \{{\mathsf{ct}}_{rt}\}$. The result of the forward sweep
procedure appears in Figure~\ref{fig:snapshots}(b); here and in what
follows, the shaded nodes stand for the evidence-constrained variables
$\bZ$. Now, the {\sf X-ray} image is presented without segmentation
because of a zoom-in on the right-top part of {\sf CT-image}, and
{\sf Notes} are summarized since both the electromyography {\sf
  Graph} is presented, and {\sf CT-image} is not hidden.

Suppose that the viewer consequently chooses to hide the {\sf
  X-ray} image. If the number of recent viewer choices taken to constrain
the presentation is greater than one, then this choice
will set
$\bZ=\{{\mathsf{CT\!-\!image}},{\mathsf{X\!-\!ray}}\}$, and $\bz =
\{{\mathsf{ct}}_{rt},{\mathsf{xray}}_{hide}\}$. The result of the
forward sweep procedure appears in Figure~\ref{fig:snapshots}(c).
If consequently the viewer chooses to see the whole {\sf CT-image},
then $\bz=\{{\mathsf{ct}}_{plain},{\mathsf{xray}}_{hide}\}$, and the
updated presentation is shown in
Figure~\ref{fig:snapshots}(d).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Comparing Outcomes}
\label{sec:dominance}

%ceb2: Much of section 5 (intro) and 5.1 has been rewritten. The rest
%  has had more mundane edits, but terminology and notation has been
%  changed throughout to match 5/5.1

Outcome optimization is not the only task that should be
supported by a preference representation model.  Another basic
query with respect to such a model is {\em preferential comparison}
between outcomes. Two outcomes $o$ and $o'$ can stand in one of
three possible relations with respect to a CP-net $N$: either
$N\models o\succ o'$; or $N\models o' \succ o$; or 
$N\not\models o \succ o'$ and $N\not\models o' \succ o$.\footnote{Recall
that, for the time being, we do not consider CP-nets with indifference
in CPTs; hence two outcomes cannot be proven equally preferred.}
The third case, specifically, means that the network $N$ does not contain
enough information to prove that either outcome is preferred to the other
(i.e., there exist preference orderings satisfying $N$ in which
$o\succ o'$ and in which $o' \succ o$). There are two distinct
ways in which we can compare two outcomes using a CP-net:
\begin{enumerate}
\item {\em Dominance queries} -- Given a CP-net $N$ and a pair of
  outcomes $o$ and $o'$, ask whether $N\models o \succ o'$. If this relation
  holds, $o$ is preferred $o'$, and we say that $o$ {\em dominates} 
  $o'$ with respect to $N$.
\item {\em Ordering queries} -- Given a CP-net $N$ and a pair of
outcomes $o$ and $o'$, ask if $N\not\models o' \succ o$. If this
relation holds, there exists a preference ordering consistent
with $N$ in which $o \succ o'$. In other words, it is consistent with
the knowledge expressed by $N$ to order $o$ ``over'' $o'$ (i.e., assert
that $o$ is preferred to $o'$).  In such a case we say $o$ is 
\emph{consistently orderable over} $o'$ with respect to $N$.
\end{enumerate}

Ordering queries are clearly weaker than dominance queries. Indeed,
if $N\models o \succ o'$, then $N\not\models o' \succ o$. But it may
be the case that $N\not\models o' \succ o$ even though
%carmel2: models --> not models
$N\not\models o \succ o'$.
% $N\models o \succ o'$.
While dominance queries are typically more useful, ordering queries
are sufficient in many applications where one may be satisfied knowing 
only that outcome $o$ can be consistently ordered over $o'$.
For example, consider a set of products that a human or automated seller
would like to present to a customer in some non-increasing order 
of customer preference.
%carmel2: below: reason --> no reason
There seems to be no reason to use the strong 
dominance relation to sort such products.
%
%ceb2: this is out of place
% % We begin this section by showing that ordering queries with respect 
% to acyclic CP-nets can
% be answered in time linear in the number of variables.
% % carmel -- sentence below has been added.
% In addition, we show that a set of outcomes can be sorted in a non-increasing
% order with respect to an acyclic CP-net using ordering queries only.
% ---------------------------------------
%
In some applications, dominance queries cannot be replaced by 
ordering queries. For instance, dominance queries
were shown to be an integral part of constraint-based preferential
optimization in CP-nets~\cite{bbgp:spring97}.  

We begin by showing that 
ordering queries with respect to acyclic CP-nets can
be answered in time linear in the number of variables.
In addition, we show that a set of outcomes can be sorted in a
consistent non-increasing order with respect to an acyclic CP-net 
using ordering queries only.  We then provide a 
complexity analysis of dominance queries.  First, we introduce and
study a particular form of reasoning, namely search for flipping
sequences, that can be used to answer dominance queries.
Using this technique, and focusing on binary-valued
CP-nets, we show connections between the structure of the CP-net
graph and the worst-case complexity of dominance queries. 
We discuss dominance queries in more detail in Section~\ref{sec:techniques},
where we present some general search techniques for
flipping sequences.


\subsection{Ordering Queries Are Easy}
\label{S:initial-dominance}

Here we show that ordering queries with respect to acyclic (not necessarily
binary-valued) CP-nets can be answered in time linear in the number of
variables. The corresponding algorithm exploits the graphical structure of the
model.
% carmel -- sentence below has been added.
Likewise, we show that with acyclic CP-nets, we can construct a non-increasing
ordering over outcomes, consistent with a CP-net, using only
ordering queries.

\begin{cor}
  \label{col:weak-dom}
  Let $N$ be an acyclic CP-net, and $o,o'$ be a pair of outcomes.
  %ceb2: removed this phrase here and elsewhere. This is how outcomes 
  %are defined... hence redundant.
  % over the variables of $N$. 
  If there exists a variable $X$ in $N$, such that:
  \begin{enumerate}
  \item $o$ and $o'$ assign the same values to all ancestors of $X$ in
    $N$, and
  \item given the assignment provided by $o$ (and $o'$) to $\Pa(X)$,
    $o$ assigns a more preferred value to $X$ than that assigned by $o'$
  \end{enumerate}
  then $N \not\models o' \succ o$.
\end{cor}

\begin{proof}
  The construction in Theorem~\ref{sat-lemma} provides a preference
  ordering satisfying $N$ such that $o \pref o'$. Thus $o'\pref o$ is 
  not true in all models of $N$, and is not a consequence of $N$.
\end{proof}

Corollary~\ref{col:weak-dom} presents a condition which is sufficient
but not necessary for the truth of the ordering query 
$N\not\models o' \succ o$.
For instance, consider Example~\ref{ex:cpn2}, and let 
$o=M_{mc}\wedge S_v \wedge W_w$ and
$o'=M_{fc}\wedge S_v\wedge W_r$. These two outcomes are incomparable
according to the CP-network (i.e., neither can be proven to be preferred
%carmelfinal: \succ below replaced \prec, and ``more'' replaced ``less''
to the other), but $o \not\succ o'$ cannot be deduced using the conditions
of Corollary~\ref{col:weak-dom}, because $M$ is the root
variable of this chain CP-net, and $o$ assigns it a more
%less
preferred
value than that assigned by $o'$.

Despite the fact that the condition provided by
Corollary~\ref{col:weak-dom} for $N\not\models o' \succ o$ is not 
necessary for consistent orderability, we can show that it is 
sufficient to provide a consistent ordering of any pair of outcomes.
\begin{thm}
  \label{t:weak-dom}
  Given an acyclic CP-net $N$, and
  %ronen1 - shoved my nose in too
  %%carmel2: rephrased
  %a pair of outcomes $o$ and $o'$,
  %the complexity of determining truth of at least one of the 
  %%two outcomes $o$ and $o'$ over the variables of $N$,
  %% the complexity of determining at truth of least one of the 
  two outcomes $o$ and $o'$ over the variables of $N$,
  the complexity of determining truth of at least one of the 
  ordering queries, $N\not\models o' \succ o$ or $N\not\models o \succ o'$,
  is $O(n)$.
\end{thm}

\begin{proof}
%  Clearly, given an acyclic CP-net $N$, and a pair of outcomes $o$
%  and $o'$, the condition posed by Corollary~\ref{col:weak-dom} can be
%  checked in $O(n)$ by a simple top-down traversal of $N$.
%  We now show that, given two different outcomes $o$ and $o'$ with
%  respect to an (acyclic) CP-net $N$, either $o \not\prec o'$, or $o'
%  \not\prec o$, or both, can be deduced using the condition in
%  Corollary~\ref{col:weak-dom}.
  % We accomplish the proof of the theorem by showing that, given two
%   different outcomes $o$ and $o'$ with respect to an acyclic CP-net
%   $N$, either $o \not\prec o'$, or $o' \not\prec o$, or both, can be
%   deduced using the condition in Corollary~\ref{col:weak-dom}.
%  
%  The proof is straightforward: Consider the variables $\bV
%  =\{X_1,\ldots,X_n\}$ numbered according to a topological order
%  induced by the graph of $N$. Since $o\neq o'$, there exist $1 \leq
%  i \leq n$, such that $o[i] \neq o'[i]$, and $o[j] = o'[j]$ for all
%  $j \leq i$.  Thus, $o$ and $o'$ assign the same values to all
%  ancestors of $X_i$ in $N$.  Now, if $o[i] \succ o'[i]$, given the
%  assignment provided by $o$ (and $o'$) to $\Pa(X_i) \subseteq
%  \{X_1,\ldots,X_{i-1}\}$, then the condition of
%  Corollary~\ref{col:weak-dom} induces $N \models o \not\prec o'$.
%  Otherwise, if $o[i] \prec o'[i]$, given the assignment provided by
%  $o$ (and $o'$) to $\Pa(X_i)$, then the condition of
%  Corollary~\ref{col:weak-dom} induces $N \models o' \not\prec o$.
%  
%ceb2: made more precise
  For any variable $X_i$, let $\Pa(X_i) = \bfU$ in $N$ and
  $\bfu$ and $\bfu$ denote the assignment to $\bfU$ made by
  outcomes $o$ and $o'$, respectively.
  All variables $X_i$, such that $o$ and $o'$ assign 
  %carmelfinal -- I added below (seems to be essential for correctness of the rest).
  different values to $X_i$ but 
  %
  the same values to all ancestors of $X_i$ in $N$, can be identified
  in $O(n)$ time by a top-down traversal of $N$. (Note that $\bfu =
  \bfu'$ for all such $X_i$). If for all such $X_i$ we have that
  $o[X_i] \succ^i_{\bfu} o'[X_i]$, then using
  Corollary~\ref{col:weak-dom} we can deduce that $N\not\models o'
  \succ o$.  Otherwise, there exist two variables of this type,
  $X_{i}$ and $X_{j}$, for which $o[X_i] \succ^i_{\bfu} o'[X_i]$ and
  $o[X_j] \prec^i_{\bfu} o'[X_j]$; in this case,
  Corollary~\ref{col:weak-dom} implies that both $N\not\models o'
  \succ o$ and $N\not\models o \succ o'$
\end{proof}

%ceb2: New stuff, notation to help make the ideas below clearer
Corollary~\ref{col:weak-dom} provides an effective algorithm for answering
ordering queries; however, its computational efficiency comes at
a price: it is sound---if the algorithm says that $o$ is consistently
orderable over $o'$, then indeed, $N\not\models o' \succ o$; but
it is incomplete---if it provides a negative response to 
query $N\not\models o' \succ o$, it still may be the case that
$N\not\models o' \succ o$.
Theorem~\ref{t:weak-dom} provides an effective algorithm that
is sound, and ``partially complete'' in the sense that it will
return a positive answer for at least one of
$N\not\models o' \succ o$ or $N\not\models o \succ o'$. In other words,
it will allow us to determine that at least one outcome can be
consistently ordered over the other.

Though the incompleteness of the algorithm for single
ordering queries is problematic, the partial completeness of
the algorithm for paired queries is sufficient to allow one to find
a consistent ordering of all outcomes in polynomial time, at least in
the case of an acyclic CP-net. We first introduce some notation.
We write $N\vdash_{oq} o \gg o'$ to represent that the algorithm
for paired ordering queries tells us that $N\not\models o' \succ o$ holds
(i.e., $o$ is consistently orderable over $o'$) but $N\not\models o' \succ o$
does not (i.e., $o'$ is not orderable over $o$). When $N\vdash_{oq} o \gg o'$,
we can be assured that $o$ is indeed orderable over $o'$; but due to
the incompleteness of the algorithm, we cannot be sure that $o'$ is
not orderable over $o$. We write $N\vdash_{oq} o \simeq o'$ to denote that
the algorithm returns a positive response for both ordering queries
(i.e., it tells us that both outcomes are consistently orderable over
the other). The soundness of the algorithm ensures that both outcomes
can indeed be consistently preferred in this case. Note that partial completeness
ensures that either $N\vdash_{oq} o \gg o'$, $N\vdash_{oq} o' \gg o$,
or $N\vdash_{oq} o \simeq o'$. This will be sufficient to allow
us to produce a consistent ordering of any set of outcomes.

\begin{thm}
  \label{t:weak-dom2}
  Given an acyclic CP-net $N$ over the variable set $\bV$, and a set of
  outcomes $o_1,\ldots,o_m$ over $\bV$, ordering these outcomes consistently
  with $N$ can be done using ordering queries only.
\end{thm}

%ceb2: rewrote
\begin{proof}
  Define two binary relations over outcomes: $o \gg o'$ iff
  $N\vdash_{oq} o \gg o'$ and $o \simeq o'$ iff $N\vdash_{oq} o \simeq o'$.
%hhfinal: \simeq notation introduced here is not used in the proof!
  We first show that the 
  %ceb2: technically, the closure of \gg is shown asymm, not *just*
  %  \gg itself. This is stronger (and necessary)
  transitive closure of the
  relation $\gg$ is asymmetric.  Assume to the contrary that there 
  exists a set of outcomes $o_1,\ldots,o_k$ such that:
  \begin{equation}
    \label{e:assym}
    o_1 \gg o_2 \gg \cdots \gg o_k \gg o_1
  \end{equation}
  For $1 \leq i \leq k$, let $V(o_i)$ be the set of all variables $X$ such
  that the value assigned to $X$ by $o_i$ can be improved given the assignment
  provided by $o_i$ to $\Pa(X)$. Let $N_i$ be the subgraph of
  $N$ consisting of those variables in $V(o_i)$ and their descendants in $N$.
  Observe that Corollary~\ref{col:weak-dom} implies $N_i \subseteq N_{i+1}$
  for $1 \leq i < k$, and $N_k \subseteq N_1$. To see this, notice that 
  if, for some $i$, we have
  $N_i \not\subseteq N_{i+1}$, then there exists a variable $X$ such that: (i)
  all ancestors of $X$ are assigned their most preferred values by both
  $o_i$ and $o_{i+1}$; and (ii) given $o_{i}[\Pa(X)] = o_{i+1}[\Pa(X)]$, $X$
  is assigned its most preferred value by $o_{i+1}$ and one of its less
  preferred values by $o_{i}$. However, in this case, an ordering query will
  determine $N\not\models o_{i} \succ o_{i+1}$, which contradicts our 
  assumption that $o_{i} \gg o_{i+1}$.
  
  If one of the graph containment relations 
  $N_i \subseteq N_{i+1}$ is strict, the initial
  assumption~(\ref{e:assym}) is trivially contradicted. Therefore, we are 
  left with the case of:
  \[
    N_1 = N_2 = \cdots = N_k = N'
  \]
  Recalling that $N'$ is acyclic, consider a variable $X_j \in N'$ that has no
  ancestors in $N'$. Let $\bfU = \Pa(X_j)$ be the parents of $X_j$ in the original
  network $N$ (note that $\bfU \cap N' = \emptyset$).
  By construction of the $N_i$ we have:
  \[
  o_1[\bfU] = o_2[\bfU] = \cdots = o_k[\bfU] = \bfu
  \]
  This must be the case since all the ancestors of $X_j$ are assigned to 
  their unique optimal assignment (of which $\bfu$ is a part) since
  none of these variables is improvable. This entails
  \[
  o_1[X_j] \succ^j_{\bfu} o_2[X_j] \succ^j_{\bfu} \cdots \succ^j_{\bfu} 
         o_k[X_j] \succ^j_{\bfu} o_1[X_j],
  \]
  which is inconsistent with the definition of a CP-net.

  We exploit the asymmetric nature of the relation $\gg$ as follows.
  If $N\models o \succ o'$, then we must have $o \gg o'$.  Therefore, 
  the relation $\succ_N$ representing the induced preference graph of
  $N$ is a subset of $\gg$.  
  % ceb2: This is irrelevant since we don't allow indifference in CPTs
  % On the other hand, if $o \sim o'$, then
  % we may have either $o \gg o'$ , or $o' \gg o$, or $o \simeq
  % o'$. 
  Thus any total ordering of $o_1,\ldots,o_m$
  consistent with $\gg$ will be consistent with $\succ_N$.  
\end{proof}

% carmel -- rephrasing below
An immediate consequence of Theorems~\ref{t:weak-dom} and~\ref{t:weak-dom2} is
that, given a set of $m$ outcomes and a CP-net $N$, the
complexity of ordering these outcomes consistently with the preference 
graph induced by $N$ is $O(nm^2)$ (i.e., the cost of comparing every pair
of outcomes and ordering them accordingly).


\subsection{Dominance Queries and Flipping Sequences}
\label{sec:flipping}


The \CP\ semantics of CP-nets allows one to directly use information
in the CPT of a variable $X$ to alter or {\em flip} the value of
$X$ within an outcome to directly obtain an improved (preferred)
or worsened (dispreferred) outcome. A {\em sequence of improving flips}
from one outcome to another provides a proof that one outcome
is preferred, or dispreferred, to another in all 
rankings satisfying the network. Before defining this notion more precisely,
we illustrate the intuitions with an example.

\begin{example}
  \label{ex:abcflip}
  Consider again the CP-net from Figure~\ref{f:ex:cpn2.2}.  The
  following are the only two rankings that satisfy this network:
  \begin{eqnarray*}
    abc \succ ab\barc \succ a\barb\barc \succ \overbrace{a\barb c \succ \bara\barb\barc} \succ
    \bara\barb c \succ \bara bc \succ \bara b\barc\\
    abc \succ ab\barc \succ a\barb\barc \succ \underbrace{\bara\barb\barc \succ a\barb c} \succ 
    \bara\barb c \succ \bara bc \succ \bara b\barc
  \end{eqnarray*}
  Thus, the only two outcomes not totally ordered are $\negn a\negn
  b\negn c$ and $a\negn bc$.  Notice that if we remove either $\negn a\negn
  b\negn c$ or $a\negn bc$ from each of these chains of
  outcomes, we can move from one outcome to the next in the chain by
  {\em flipping} the value of exactly one variable according to the
  preference information in its CPT given the instantiation of its
  parents.  For example, to move from the first outcome in these
  sequences ($abc$) to the second ($ab\negn c$), we use the fact that
  $c \pref \negn c$ given $b$ to ``prove'' that the second outcome is
  dispreferred to the first; that is we {\em flip} $C$ to a less
  preferred value given the instantiation $b$ of its parent $B$.
  Conversely, we can move backwards through this sequence by flipping
  $\negn c$ in the second outcome to $c$, thereby obtaining the more
  preferred first outcome.
  
  Recall that Corollary~\ref{col:weak-dom} demonstrates that violating
  the preference constraints for a parent variable is less preferred than
  violating the preference constraints for any of its children. This
  ``greater importance'' of parent variables is implicit in the
  {\em ceteris paribus} semantics.  Now consider the two outcomes
  $\negn a\negn b\negn c$ and $a\negn bc$, which are unordered by the 
  CP-net in
  Figure~\ref{f:ex:cpn2.2}.  The outcome $\bara \barb \barc$ violates
  the preference over the values of $A$, while the outcome $a \barb c$
  violates the preferences over the values of $B$ and $C$; and $A$ is
  an ancestor of both $B$ and $C$.  The semantics of CP-nets does not
  specify which of these outcomes is preferred---intuitively, though the
  preference for $A$ has higher priority than $B$ or $C$, two or more
  violations of lower priority preferences may not be preferred to the
  violation of a single higher priority preference.  $\square$
\end{example}

For any two outcomes $o$ and $o'$, every improving
flipping sequence from $o'$ to $o$ uniquely corresponds to some
directed path from the node $o'$ to the node $o$ in the preference
graph induced by the CP-net.  For instance, consider the CP-net
in Figure~\ref{f:ex:cpn3.3}(a), which is exactly the network
of the ``Evening Dress'' example (Example~\ref{ex:cpn3}), with 
simpler 
%ronen1 changed
%renaming.
variable names.
There are four alternative flipping sequences
from the outcome $\bar{a}\bar{b}c$ to the outcome $abc$,
corresponding to the four paths between these outcomes in 
the induced preference graph,
depicted in Figure~\ref{f:ex:cpn3.3}(b):
\begin{equation}
  \begin{split}
    & \bar{a}\bar{b}c \rightarrow a\bar{b}c \rightarrow abc\\
    & \bar{a}\bar{b}c \rightarrow a\bar{b}c \rightarrow a\bar{b}\bar{c}
       \rightarrow ab\bar{c} \rightarrow abc\\
    & \bar{a}\bar{b}c \rightarrow \bar{a}bc \rightarrow abc\\
    & \bar{a}\bar{b}c \rightarrow \bar{a}bc \rightarrow \bar{a}b\bar{c}
      \rightarrow ab\bar{c} \rightarrow abc \notag 
  \end{split}
\end{equation}
Therefore, $abc \succ \bar{a}\bar{b}c$ is a consequence of this CP-net.  
In contrast, there is no flipping sequence (directed
path) from $\bar{a}bc$ to $a\bar{b}\bar{c}$, hence these two outcomes
are incomparable.

\begin{figure}
  \begin{center}
    \mbox{
    \begin{tabular}{cc}
      \begin{minipage}{2.5in}
      \begin{tabular}{ccc}
        {\footnotesize
        \fbox{
          $a \succ \bar{a}$
          }} & &
        \fbox{
          {\footnotesize
          $b \succ \bar{b}$
          }}\\
        \ \\
      \multicolumn{3}{c}{
      \def\objectsizestyle{\scriptstyle}
      \xymatrix @C=8pt{
        *++[o]=<1.5pc>[F]{A} \ar[dr] & & *++[o]=<1.5pc>[F]{B}\ar[dl]\\
        & *++[o]=<1.5pc>[F]{C}
        }}\\
        \ \\
        \multicolumn{3}{c}{
          {\footnotesize
        \setlength{\extrarowheight}{2pt}
        \begin{tabular}{|c|c|}
          \hline
          $ab$ & $c \succ \bar{c}$\\
          \hline
          $a\bar{b}$ & $\bar{c} \succ c$\\
          \hline
          $\bar{a}b$ & $\bar{c} \succ c$\\
          \hline
          $\bar{a}\bar{b}$ & $c \succ \bar{c}$\\
          \hline
        \end{tabular}
        }}\\
        \ \\
        \ \\
        & (a)\\
      \end{tabular}
      \end{minipage} &
      \begin{minipage}{1.5in}
        \begin{tabular}{c}
          \def\objectsizestyle{\scriptstyle}
          \xymatrix @R=15pt{
            & \bar{a}\bar{b}\bar{c} \ar[d] \ar@/_1pc/[dddl] \ar@/_2.4pc/[dddd]\\
            & \bar{a}\bar{b}c \ar[d] \ar@/^0.5pc/[dr]\\
            & \bar{a}bc \ar[d] \ar@/^1.5pc/[ddd] & a\bar{b}c \ar@/^1pc/[dddl] \ar[dll] \\
            a\bar{b}\bar{c} \ar[dr] & \bar{a}b\bar{c} \ar[d] \\
            & ab\bar{c} \ar[d]\\
            & abc
            }\\
           \ \\
           (b)
        \end{tabular}
      \end{minipage}
    \end{tabular}
    }
  \end{center}
  \caption{``Evening Dress'' CP-net from Example~\ref{ex:cpn2} with simpler names.}
  \label{f:ex:cpn3.3}
\end{figure}


These examples suggest that the construction of such a flipping
sequence can be used to prove dominance.
\begin{defn}
  Let $N$ be a CP-net over variables $\bfV$, with $X_i \in \bfV$, $\bfU$
  the parents of $X_i$, and $\bfY = \bfV - (\bfU \cup \{ X_i\})$.  Let
  $\bfu x \bfy \in \Assg(\bfV)$ be any outcome, where $x \in \Dom(X_i)$,
  $\bfu \in \Assg(\bfU)$, and $\bfy \in \Assg(\bfY)$. An
  \emph{improving flip} of outcome $\bfu x \bfy$ with respect to
  variable $X_i$ is any outcome $\bfu x' \bfy$ such that 
  $x' \pref^i_\bfu x$.
  (Note that an improving flip w.r.t.\ $X_i$ does not exist if
  $x$ is the most preferred value of $X_i$ given $\bfu$.)
  
  An \emph{improving flipping sequence} with respect to $N$ is any
  sequence of outcomes $o_1,\ldots,o_k$ such that, for each $i < k$,
  $o_{i+1}$ is an improving flip of $o_i$ with respect to some
  variable.  An improving flipping sequence from an outcome $o$ to an
  outcome $o'$ is any improving sequence $o_1,\ldots,o_k$ with $o_1 = o$
  and $o_k = o'$.
\end{defn}

One can define {\em worsening flips} and {\em worsening flipping
sequences} in an entirely analogous way. Obviously, any worsening
flipping sequence is the reverse of an improving flipping sequence,
and vice versa.

There are two important things to notice about the examples above. First,
an improving (or worsening) flipping sequence can be used to show that
one outcome is better than another.
Second, preference violations are worse (i.e., have a larger negative 
impact on the preference of an outcome) the higher up they are in the network,
%carmel2: added ``always'' (otherwise it sounds like ``we always cannot'')
although we cannot compare always two (or more) lower level violations
to violation of a single ancestor constraint. 
These observations underlie the inference algorithms below.


\begin{thm}[soundness] 
\label{thm:sound}
If there is an improving flipping sequence for CP-net $N$
%carmel2: rephrased
from outcome $o$ to $o'$,
% between outcome $o$ and $o'$
then $N \models o' \pref  o$.
\end{thm}

\begin{proof}
If there is an improving flip from
%carmel2: rephrased
outcome $o_1$ to another outcome $o_2$ then 
%any outcome $o_1$ to another $o_2$ then 
$N \models o_2 \pref  o_1$ by the definition of $\models$.
The theorem follows from the transitivity of preferential entailment 
(Lemma~\ref{lemma:transitive}).
\end{proof}

\begin{thm}[completeness] 
\label{thm:complete}
If $N$ is an acyclic CP-net and there is no
improving flipping sequence for $N$ from outcome $o$ to $o'$,
then $N \not \models o' \pref o$.
\end{thm}

\begin{proof}
%hh> revised version of proof:
%
% proof sketch: 
% introduce G
% show: any extension of G satisfies N
%
% N \models o' \pref o
% => o' \pref o in every pref ordering satisfying N (def \models)
% => there is an improving flipping sequence from o to o'
% therefore, if not exists ifs from o to o'
% can add edge "o' -> o" => pref ord with o \pref o', contradiction
%
Let $G$ be a graph whose nodes are all outcomes
(i.e., complete assignments to the variable set $\bfV$),
with a directed edge from $o_1$ to $o_2$ iff
there is an improving flip of $o_1$ to $o_2$ sanctioned
by network $N$. 
Clearly, directed paths in $G$ are equivalent to improving
flipping sequences with respect to $N$.

Next, we show that any total preference ordering $\pref$
that respects the paths in $G$
(that is, if there is a path from $o_1$ to $o_2$ in $G$,
then we have $o_2 \pref o_1$)
satisfies network $N$: if $\pref$
does not satisfy $N$, there must exist some variable $X$ with
parents $\bfU$, instantiation $\bfu\in\Assg(\bfU)$, values
$x, x' \in \Dom(X)$, and instantiation $\bfy$ of the remaining
variables $\bfY = \bfV - (\bfU \cup \{X\})$, such that:
\begin{enumerate}[(a)]
\item $\bfu{x}\bfy \pref \bfu{x'}\bfy$;
\item but $\CPT(X)$ dictates that $x' \pref x$ given $\bfu$.
\end{enumerate}
This is a direct consequence of the definition of satisfaction.
However, if $N$ requires that $x' \pref x$ given $\bfu$, there
%hhfinal: was incorrect:
%is a direct flip from $x'\bfu\bfy$ to $x\bfu\bfy$, contradicting
is a direct flip from $x\bfu\bfy$ to $x'\bfu\bfy$, contradicting
the fact that $\pref$ extends the graph $G$. 

Based on this observation, we can now prove the theorem:
If there is no improving flipping sequence from $o$ to $o'$, then there
is no directed path in $G$ from $o$ to $o'$.
Therefore, there exists a preference ordering $\pref$
respecting the paths in $G$ in which $o \pref o'$.
But this preference ordering also satisfies $N$,
which implies $N \not \models o' \pref o$.
%<<hh
%
%Clearly, if there is no improving flipping sequence from $o$ to $o'$ then
%there is no directed path from $o$ to $o'$ in $G$.
%
%Let $\pref$ be any total ordering of outcomes that respects the
%paths in $G$ (that is, if there is a path from $o_1$ to $o_2$,
%then we have $o_2 \pref o_1$). We can show that any such
%preference ranking $\pref$ satisfies $N$. For if $\pref$
%does not satisfy $N$, there must exist some variable $X$ with
%parents $\bfU$, instantiation $\bfu\in\Assg(\bfU)$, values
%$x, x' \in \Dom(X)$, and instantiation $\bfy$ of the remaining
%variables $\bfY = \bfV - (\bfU \cup \{X\})$, such that:
%\begin{enumerate}[(a)]
%\item $x\bfu\bfy \pref x'\bfu\bfy$;
%\item but $\CPT(X)$ dictates that $x' \pref x$ given $\bfu$.
%\end{enumerate}
%This is a direct consequence of the definition of satisfaction.
%However, if $N$ requires that $x' \pref x$ given $\bfu$, there
%is a direct flip from $x'\bfu\bfy$ to $x\bfu\bfy$, contradicting
%the fact that $\pref$ extends the graph $G$. Thus, any preference
%ordering extending $G$ satisfies $N$.
%
%Thus, if there is no improving sequence from $o$ to $o'$, then there
%is no directed path in $G$ from $o$ to $o'$, implying the
%existence of some preference ordering $\pref$, satisfying $N$,
%in which $o \pref o'$. Thus $N \not \models o' \pref o$.
%
% \mynote{ceb: This proof really presupposes what it proves by assuming that
% the lattice defines the set of consistent rankings. It's true, but
% needs a two sentence argument.}
% 
% First let us construct a lattice of outcomes where $o_1 \pref o_2$ iff
% there is an improving flipping sequence based on $N$ from $o_2$ to
% $o_1$. Any preference order that is consistent with the partial order
% defined by the lattice is consistent with $N$. If there is no
% improving flipping sequence between $o$ to $o'$ then we can add an arc
% in the lattice and make $o \pref o'$. This new partial ordering can be
% extended to a total preorder satisfying $N$ in which $o \pref
% o'$. So $o'\pref o$ cannot be true in all preference orderings
% satisfying with $N$.
\end{proof}


\subsection{Flipping Sequences as Plans}
\label{sec:plans}

Searching for flipping sequences can be seen as a type of planning
problem: given  a CP-net $N$, and a variable $X$
with parents $\Pa(X)$ in $N$, each row in $CPT(X)$ is a
conditional preference statement of the form
\[\bfu: x_1 \pref x_2 \pref \cdots \pref x_d\]
where $\bu \in \Assg (\Pa(X))$, and $d=|\Dom (X)|$. Such a statement
can be converted into a set of planning operators for improving the value
of $X$. In particular, this conditional preference statement
can be converted into a set of $d-1$ planning operators of the form (for
$1 < i \leq d$):
\begin{description}
\item[Preconditions:] $ \bfu \wedge x_i$
\item[Postconditions:] \ \
  \begin{description}
  \item[Delete list:] $x_i$
  \item[Add list:] $x_{i-1}$
  \end{description}
\end{description}
This corresponds to the action of improving $x_i$ to $x_{i-1}$ 
in the context of $\bfu$. (An ``inverse'' set of operators would be created 
for worsening sequences).

Given a query $N \models {\bf x} \pref {\bf y}$, we treat ${\bf y}$ as 
the start state and ${\bf x}$ as the goal state of a planning
problem. It is readily apparent
that the query is a consequence of the CP-net if and only if there
is a plan for the associated planning problem, since a plan corresponds to a
flipping sequence.

The planning problem over multi-valued variables with discrete, finite domains
is known to be {\sc pspace}-complete~\cite{Backstrom:Nebel:ci95}, and it
remains {\sc pspace}-complete under the assumption that all the variables are
binary~\cite{Bylander.AI.94} (i.e., planning problems in \strips\ formalism
with negative effects). However, this upper bound is not very informative with
respect to dominance queries, since the planning problems generated from them
will generally look quite different in form from standard AI planning problems,
as there are many more actions, and each action is directed toward achieving a
particular proposition and requires very specific preconditions.  Thus
dominance queries with respect to binary-valued CP-nets correspond to a
specific class of \strips\ planning problems, the complexity of which was
recently analyzed by Domshlak and
Brafman~\scite{Domshlak:Brafman:aips01,Domshlak:Brafman:p-jair03}.  We now
explain this relationship.

%ceb2: prevail -> prevailing
%carmel2: I agree, but this is the way
%         these conditions are called in planning ... anyway, I don't really
%         care about it :-)
First, we divide the preconditions of every operator in a planning
problem into two types: {\em prevailing\/} conditions, which are variable
values that are required prior to the execution of the operator and
are not affected by the operator, and {\em preconditions\/}, which
{\em are\/} affected by the operator. Second, we introduce the notion
of a {\em causal graph}~\cite{knoblock:aij94}, a directed graph whose 
nodes stand for
the problem variables. An edge $(X,Y)$ appears in the causal graph
if and only if some operator that changes the value of $Y$ has a
prevailing condition involving $X$. 

The complexity analysis of Brafman and Domshlak
\scite{Domshlak:Brafman:p-jair03} addresses
planning problems with binary variables, unary operators (i.e., operators
that affect only a single variable), and acyclic causal graphs.
In the planning problem generated for a dominance query
with respect to a binary-valued  CP-net, we have:
\begin{enumerate}
\item all the operators are unary, because each flip improves the value
  of a single variable; and
\item the causal graph of the problem is exactly the graph of the
  CP-net, since the values of $\Pa(X)$ required by a value flip of $X$
  are exactly the prevailing conditions of the corresponding planning
  operator.
\end{enumerate}
Therefore, in our computational analysis of dominance queries for
binary-valued acyclic CP-nets we can use some of the results and
techniques of~\citeA{Domshlak:Brafman:p-jair03}.


\subsection{Complexity of Dominance Queries for Binary-valued, Acyclic CP-nets}
\label{sec:complexity}

In this section we analyze the complexity of dominance testing with respect to
binary-valued CP-nets, showing a connection between the structure of the CP-net
graph and the worst-case complexity of dominance queries. In particular, we
show that:
\begin{itemize}
\item When a binary-valued  CP-net forms a directed tree, the complexity
  of dominance testing is quadratic in the number of variables.
\item When a binary-valued  CP-net forms a polytree (i.e.,
  the  induced undirected
  graph is acyclic), dominance testing is polynomial in the size
  of the CP-net description.
\item When a binary-valued CP-net is directed-path singly connected (i.e.,
  there is
  at most one directed path between any pair of nodes), dominance testing is
  {\sc np}-complete. The problem remains hard even if node in-degree in the
  network is bounded by a low constant.
\item Dominance testing for binary-valued CP-nets remains 
%in {\sc np} 
%hhfinal: changed to:
  {\sc np}-complete
  if the number of alternative paths between any pair of nodes in a CP-net is
  polynomially bounded.
\end{itemize}

The exact complexity of dominance testing in multiply connected,
binary-valued, acyclic CP-nets remains an open problem---at this stage it is
not clear whether this problem is in {\sc np} or harder.

In what follows, we make the assumption that the number of parents for
each variable (i.e., node in-degree in the CP-net) is bounded by some
constant. This assumption is justified as the CPTs are part of the
problem description, and the size of a $CPT(X)$ is exponential in
$|\Pa(X)|$.

\subsubsection{Some General Properties}

We start with some notation and two useful lemmas.  First, given a
CP-net $N$ and a pair of outcomes $o, o'$ with respect to $N$, an
improving flipping sequence $F$ from $o'$ to $o$ will be called 
{\em irreducible} if any subsequence $F'$ of $F$ obtained by
deletion of any entries except the endpoints $o, o'$ of $F$
is not an improving flipping sequence.\footnote{Note that removing
any proper initial or final subsequence of $F$ results in a
valid flipping sequence. We refer here to the deletion of
arbitrary elements from the sequence, \emph{excluding} the endpoints.}

Given a CP-net $N$, let $\cF$ be the set of {\em all}
irreducible improving flipping sequences among outcomes.
We denote by $\MaxReq(X_i)$ the maximal number of times that
a variable $X_i$ changes its value in any flipping sequence in $\cF$. 
Formally, let
${\mathsf{Flip}}(F,X_i)$ be the number of value flips of $X_i$ in the flipping
sequence $F$. Then,
\[
  \MaxReq(X_i) = \max_{F\in\cF}{\{{\mathsf{Flip}}(F,X_i)\}}
\]

Lemma~\ref{l0} below formalizes our first observation about irreducible
flipping sequences with respect to binary-valued  CP-nets.
\begin{lemma}
  \label{l0}
  For every variable $X_i$ in a binary-valued  CP-net $N$, we have:
  \[
    \MaxReq (X_i) \leq \;\;\;1\ +\ \sum_{X_j : X_i \in \Pa(X_j)} \MaxReq (X_j)
  \]
\end{lemma}

\begin{proof}
  Let $F$ be an irreducible flipping sequence with respect to $N$
  (from some outcome $o'$ to some outcome $o$), such that $\MaxReq
  (X_i) = {\mathsf{Flip}}(F,X_i)$. Consider the subsequence
  $F'=f_1,f_2,\ldots,f_k\subseteq F$ that consists of all value
%hhfinal: <- changed \subset and to \subseteq 
  flips of the children of $X_i$ in $N$. Observe that:
  (i) every $f_l \in F'$ {\em requires} $X_i$ to take one of its two
  possible values; and (ii) no value flip in $F-F'$ depends on the
  value of $X_i$.
  
  Now, for $ 1 \leq l < k$, if $f_l$ and $f_{l+1}$ require the same
  value of $X_i$, then there are no value flips of $X_i$ in $F$
  between $f_l$ and $f_{l+1}$: If there are such flips, they are
  simply redundant, and this contradicts our assumption that $F$ is
  irreducible. 
  (Recall that $f_l$ and $f_{l+1}$ are adjacent in $F'$, but may be separated
  by several flips in the original sequence $F$.)
  Alternatively, if $f_l$ and $f_{l+1}$ require different
  values of $X_i$, due to the irreducibility of $F$, there
  is exactly one value flip of $X_i$ in $F$ between $f_l$ and
  $f_{l+1}$. Similarly we can show that there is at most one value flip of
  $X_i$ in $F$ before $f_1$, and there is at most one value flip of
  $X_i$ in $F$ after $f_k$.  The latter flip is necessary when $f_k$ requires
  $X_i$ to take the value $\neg o[X_i]$, thus, after ``supporting'' the
  immediate successors, $X_i$ still should flip its value once, in
  order to obtain the value required by $o$.

  The above implies that:
  \[
  \MaxReq (X_i)\ =\ {\mathsf{Flip}}(F,X_i) \ \leq\ 1 + \sum_{X_j : X_i \in
    \Pa(X_j)}{{\mathsf{Flip}}(F,X_j)}
  \]
  and thus, by definition of $\MaxReq$, we have:
  \[
  \MaxReq (X_i) \ \leq \ 1 + \sum_{X_j : X_i \in \Pa(X_j)} \MaxReq (X_j)
  \]
\end{proof}

%carmel2: new terminology
Adopting the terminology
of~\citeA{Domshlak:Shimony:flairs03} and 
\citeA{Shimony:Domshlak:singly}, a directed
acyclic graph $G$ is {\em directed-path singly connected} if, for every pair of
nodes $s,t\in G$, there is at most one directed path from $s$ to $t$.  Using
Lemma~\ref{l0}, we can prove that if a binary-valued CP-net forms a
directed-path singly connected DAG then, for every variable $X_i$, $\MaxReq
(X_i)$ can be bounded by $n$ (the number of variables).

\begin{lemma}
\label{l1}
If a binary-valued  CP-net $N$ forms a directed-path singly connected DAG, then,
for every variable $X_i \in N$, we have:
\[
\MaxReq (X_i) \leq n
\]
where $n$ is the number of variables in $N$.
\end{lemma}

\begin{proof}
  In what follows, denote $\MaxReq (X_i)$ in $N$ as $\MaxReq_{N}
  (X_i)$.  The proof is by induction on $n$. For $n=1$ it is obvious
  that $\MaxReq (X_1) \leq 1$.  Assume that
  when a binary-valued, directed-path singly connected CP-net 
  $N$ consists of $n-1$
  variables, then, for every $X_i \in N$,
  \[
  \MaxReq_{N} (X_i) \leq n-1
  \]
  
  Let $N'$ be some binary-valued, directed-path singly connected CP-net over
  $n$ variables.  Without loss of generality, let the variables $\{X_1,\ldots
  X_{n}\}$ of $N'$ be topologically ordered based on the (acyclic) graph of
  $N'$. Clearly, $X_n$ is a leaf node, and we will denote by $N$ the CP-net
  obtained by removing $X_n$ from $N'$. From Lemma~\ref{l0}, we have:
  \[
     \MaxReq_{N'} (X_n) \leq 1
  \]
  Observe that there are no directed paths between any predecessors of $X_n$ in
  $N'$, since $N'$ is assumed to be directed-path singly connected. Therefore,
  by Lemma~\ref{l0}, for each 
%hhfinal: changed (for clarity):
  %{\em immediate} predecessor 
  parent $X_i$ of $X_n$ in
  $N'$, we have:
  \[
     \MaxReq_{N'} (X_i) \leq \MaxReq_{N} (X_i) + \MaxReq_{N'} (X_n)
  \]
  and thus:
  \[
     \MaxReq_{N'} (X_i) \leq \MaxReq_{N} (X_i) + 1
  \]

  
  Generally, since $N$ is directed-path singly connected, for each
  variable $X_i\in N'$,
  \begin{eqnarray*}
    \MaxReq_{N'} (X_i) \leq \sset{\MaxReq_{N} (X_i) + 1,
      \ \ \ \mathrm{if}\ \mathrm{there}\ \mathrm{is}\ \mathrm{a}\ \mathrm{path}\ \mathrm{from}\
      \mathnormal{X_i}\ \mathrm{to}\ \mathnormal{X_n}\\
      \MaxReq_{N} (X_i),\ \ \ \ \ \ \ \ \mathrm{otherwise} }
  \end{eqnarray*}
  and thus, for each $X_i\in N'$, we have:
  \begin{eqnarray*}
    \MaxReq_{N'} (X_i) \leq n
  \end{eqnarray*}
\end{proof}




\subsubsection{Tree-structured CP-nets}

We start by presenting a flipping sequence search algorithm for the
class of binary-valued, tree-structured CP-nets, and prove 
its correctness. Then
we show that the time complexity of this algorithm is 
$O(n^2)$, and show that this
is actually a lower bound for flipping-sequence search
over binary-valued, tree-structured CP-nets.

Figure~\ref{fig:tree} presents our {\sf TreeDT} algorithm for
binary-valued, tree-structured CP-nets. Informally, {\sf TreeDT} starts by
initializing all the variables in $\bV$ to their values in the
(purported) less preferred outcome $o'$, and continues with an
incremental, {\em bottom-up} conversion of this initial assignment to
the assignment induced by the (purported) more preferred outcome $o$.
Each step starts by iteratively removing from $N$ all leaf variables
(i.e., its maximal fringe or canopy) that are already 
consistent with $o$. If at some iteration
this step removes all variables in $N$, then all
variables are assigned to their values in $o$, and thus the
required improving flipping sequence from $o'$ to $o$ has been
generated.

Otherwise, let $N'$ stand for the updated $N$ (with nodes
removed). A node $X \in N'$ is a {\em candidate} variable if:
(i) the value of $X$ can be flipped; and (ii) no descendant of $X$
in $N'$ can have its value flipped, given the current assignment to 
the variables of $N'$. We then
flip the value of an {\em arbitrary} candidate variable (if one exists)
and repeat with node removal; or we report that there is no improving 
flipping sequence from $o'$ to $o$ if there are no candidate variables.

The {\sf TreeDT} algorithm is deterministic and
backtrack-free.  Below we show that {\sf TreeDT} is complete 
for binary-valued, tree-structured CP-nets,
and generates only irreducible flipping
sequences---thus the time complexity of {\sf TreeDT} is $O(n^2)$.
The fact that it generates irreducible flipping sequences ensures
its soundness (since by generating only valid flipping sequences it
can only provide correct positive answers to dominance queries).


\begin{figure}
\begin{center}
\fbox{
\begin{minipage}{\textwidth}
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\= \kill
\underline{{\sf TreeDT}} 
($\llbracket N\models  o\succ o'\rrbracket$)\\
Initialize the variables in $\bV$ to outcome $o'$.\\
Loop:\\ 
  \> Iteratively remove all leaf variables from $\bV$ that have assigned to\\
  \>\> them their values in $o$.\\
  \> If $\bV = \emptyset$, then return {\em yes}.\\
  \> Find a variable $X$ s.t. its value can be improved, and no 
     value of its\\
  \>\>  descendants in $N$ can be improved, given the current
     assignment to $\bV$.\\
  \> If no such variable was found, then return {\em no}.\\
  \>\> Otherwise, change the value of $X$.
\end{tabbing}
\end{minipage}
}
\caption{Flipping sequence search algorithm for binary-valued, tree-structured CP-nets} \label{fig:tree}
\end{center}
\end{figure}

%carmelfinal -- changed below from lemma to theorem (otherwise looks weird).
\begin{thm}
  \label{l:tree-complete}
  The algorithm {\sf TreeDT} is sound and complete for binary-valued,
  tree-structured CP-nets.
\end{thm}

\begin{proof}
  Consider an execution of {\sf TreeDT} on a dominance query 
  $N\models o \succ o'$ with respect to a binary-valued,
  tree-structured CP-net $N$.
  
  First, suppose we iteratively remove from the tree any leaf
  variables that have as values those required by the target
  outcome $o$. It is easy to see that this
  does not affect the completeness of the
  algorithm: because $N$ is acyclic, the variables in the
  fringe are not the ancestors of any other variables. Hence, the
  value of the variables in the fringe does not influence our
  ability to flip the values of any other variables (hence it does
  not remove any improving flipping sequence from consideration).
  
  Second, consider a variable $X$ such that, after iteratively
  removing variables as above, its value can be improved, yet none of
  its descendents in $N$ can be improved, given the current
  assignment $\bfv$ to $\bV$. If $X$ is a leaf node, then changing its
  value does not influence our ability to flip values of any other
  variables. In addition, the current value $\bfv[X]$ of $X$ is
  different from $o[X]$, otherwise $X$ would have been part of the
  removed fringe. Therefore, the (improving) change of $X$'s value
  at this point is 
  necessary in any improving flipping sequence.
  Alternatively, suppose that $X$ is not a leaf node.  Since the leaf
  nodes in the subtree of $N$ rooted at $X$ were not a part of the removed
  fringe, (at least) their values remain to be changed.  Because $N$
  is a tree, $X$ completely separates its descendents in $N$ from all
  other variables; so no improving flip in the subtree of $X$
  will be possible until we change the value of $X$. Hence the
  value of $X$ must be changed in any flipping sequence from this
  point before the value of any descendent of $X$.
  
  What remains to be shown is that when there are several
  candidate variables that can be flipped, it does not matter which one we
  flip first. 
  %ceb2: stated below... redundant
  % This follows from the fact that two such variables
  % in a tree cannot influence one another, nor can one influence any
  % descendent of the other. 
  If there is more than one candidate
  variable, each one of them will have to be flipped at some
  point---each such flip is necessary for flipping the children
  of the corresponding variable. However, any changes made to one of
  these candidates or below it has no affect on the other candidates
  or their descendants.  Thus, the evaluation order of the candidate
  flips is irrelevant, and cannot prevent us from finding a flipping
  sequence if one exists.

  Thus the algorithm is complete.
  %ceb2: added
  The soundness of the algorithm should be clear from the proof as well.
  The flip generated at each step of the algorithm is a valid improving
  flip given the current outcome $\bfv$.
\end{proof}

\begin{thm}
  The time complexity of the flipping-sequence search over binary-valued,
  tree-structured CP-nets is $O(n^2)$, where $n$ is the number of variables in
  the CP-net.
\end{thm}

\begin{proof}
  Since the algorithm {\sf TreeDT} is backtrack-free, the only thing that
  remains to be shown in addition to Lemma~\ref{l1}
  and Theorem~\ref{l:tree-complete} is that (on binary-valued, tree-structured CP-nets)
  {\sf TreeDT} generates only irreducible flipping sequences.
  However, the proof of this subclaim is straightforward since
  we have already shown that:
  \begin{enumerate}
  \item {\sf TreeDT} flips the value of each variable $X$ either to
    achieve the value of $X$ in the (purported) more preferred outcome
    of the query, or to allow the required value flips of the
    descendants of $X$, and
  \item The role of the latter flips of $X$ cannot be fulfilled by
    value flips of any other variables.
  \end{enumerate}
  Therefore, given an improving flipping sequence $F$ generated by
  {\sf TreeDT}, removing any subset of value flips from $F$ makes
  $F$ either illegal, or its ends are not $(o',o)$, respectively.
  Hence, any improving flipping sequence generated by
  the {\sf TreeDT} algorithm is irreducible.
\end{proof}

Theorem~\ref{t:tree} below shows that even when limiting ourselves
to {\em chain} binary-valued
CP-nets, there are dominance queries whose minimal flipping
sequences have quadratic length. Thus {\sf TreeDT} is asymptotically optimal.


\begin{thm}
\label{t:tree}
$\Theta (n^2)$ is a lower bound for the flipping-sequence search over
binary-valued tree-structured CP-nets.
\end{thm}

\begin{proofa}
  For the proof see Appendix~\ref{sec:appendixa}.
  The proof is by example, providing a dominance query on a binary-valued, tree
  CP-net for which the size of a minimal flipping sequence is $\Theta(n^2)$.
\end{proofa}









\subsubsection{Polytree CP-nets}
\label{S:polytree}
%carmel2: first sentence rephrased
DAGs with no cycles in the underlying
undirected graphs, also known as {\em polytrees}, offer a minimal extension of
directed trees.  Unfortunately, the {\sf TreeDT} procedure is not complete for
polytree CP-nets unless extended with some form of backtracking (even when
restricted to binary variables). This is due to the fact that several parents
of a given node may each be allowed to have their values flipped, but only one
of the choices may lead to the target outcome while the others lead to a dead
end. For instance, consider the CP-net $N$ from Figure~\ref{f:ex:cpn3.3} and
the query $N\models a\barb\barc \succ \bara\barb c$.  Starting with the outcome
$\bara\barb c$, in the first iteration of {\sf TreeDT}, we have the choice of
flipping either $A$ or $B$. If $B$ is chosen, the assignment is changed to
$\bara b c$. However, this cannot lead to the target, since there is no way to
flip $B$ back to $\barb$. Thus, a dead end is reached. On the other hand, if
$A$ is chosen then {\sf TreeDT} will successfully generate the improving
flipping sequence $\bara\barb c \rightarrow a\barb c \rightarrow a \barb\barc$.
Thus, an incorrect choice of improving variable may require backtracking.

However, dominance testing for binary-valued, polytree CP-nets remains
polynomial time, although the algorithm for its solution is more
complicated than {\sf TreeDT}. An algorithm is adapted from the
corresponding algorithm for planning problems with binary variables,
unary operators, and polytree causal graphs described by
Domshlak and Brafman \scite{Domshlak:Brafman:p-jair03}.

\begin{thm}
\label{t:polytree}
Dominance testing for binary-valued, polytree CP-nets is in {\sc p}.
\end{thm}

\begin{proof}
  According to the reduction from the CP-net dominance queries to
  the classical planning problems (see Section~\ref{sec:plans}),
  every dominance query with respect to a binary-valued, polytree CP-net can be
  compiled into a propositional planning problem with unary operators
  and polytree causal graph. An algorithm for the latter problem is
  presented by~\citeA{Domshlak:Brafman:p-jair03}, and the time complexity of this
  algorithm is $O(2^{2\kappa}n^{2\kappa+3})$, where $\kappa$ is the maximal
  in-degree of the causal graph.
  
  Recall our assumption that the in-degree of the CP-net
  is bounded by some constant (in this case, $\kappa$). 
  This assumption is justified
  as the CPTs are part of the problem description, and the size of a
  $CPT(X)$ is exponential in $|\Pa(X)|$. Therefore, the complexity of
  the algorithm of~\citeA{Domshlak:Brafman:p-jair03} on CP-nets is
  polynomial in the size the CP-net.
\end{proof}

\subsubsection{Intractable dominance queries}
\label{S:restr-connect}

While dominance testing for binary-valued, polytree CP-nets is
polynomial, we can show that for binary-valued, directed-path singly connected
CP-nets, this problem is 
%ceb2: added footnote
{\sc np}-complete.\footnote{While every polytree is directed-path singly
  connected, the converse is not true.}  This can be proved using a
CP-net-oriented extension of the proof for the corresponding claim with respect
to planning problems \cite{Domshlak:Brafman:p-jair03}. These results also
entail that dominance testing for binary-valued CP-nets remains in {\sc np} if
the number of distinct paths between any pair of nodes in the CP-net is
polynomially bounded.

\begin{thm}
\label{t:bh-nphard}
Dominance testing for binary-valued, directed-path singly connected CP-nets is
{\sc np}-complete.
\end{thm}

\begin{proofa}
  For the proof see Appendix~\ref{sec:appendixa}.
\end{proofa}


An immediate extension of directed-path singly connected DAGs are {\em
  max-$\delta$-connected} DAGs: a directed graph is max-$\delta$-connected if
the number of different directed paths between any two nodes in the graph is
bounded by $\delta$.

\begin{thm}
\label{l:delta}
Dominance testing for binary-valued, max-$\delta$-connected CP-nets, where
$\delta$ is polynomially bounded in the size of the CP-net, is {\sc
  np}-complete.
\end{thm}

\begin{proofa}
  The theorem is immediately entailed by the corresponding result for planning
  of~\citeA{Domshlak:Brafman:p-jair03}; for the proof in terms of
  CP-nets, see Appendix~\ref{sec:appendixa}.
\end{proofa}

Theorem~\ref{t:bh-nphard} implies that dominance testing for binary-valued,
acyclic CP-nets is hard. However, the exact complexity of this problem
is still an open question---it is not clear whether this problem is
in {\sc np} or if it is harder.  Some preliminary analysis of this
problem~\cite{Domshlak:Brafman:kr02} shows a connection between the
complexity of the flipping sequence search for binary-valued, acyclic CP-nets and
the diameters of some specific graphs. A complementary result
with respect to these graphs \cite{Domshlak:jcomb02}, namely
recursively directed hypercubes, shows that dominance queries with
respect to binary-valued, acyclic CP-nets with {\em unbounded} node in-degree
may require flipping sequences of size exponential in $n$, where $n$ is
the number of variables in the CP-net.

It has been shown that the most
general class of planning problems with binary variables, unary
operators and acyclic causal graphs is harder than {\sc np}
\cite{Domshlak:Brafman:p-jair03}. However,
this result does not imply that answering dominance queries is harder
than {\sc np} as well, as we do not know of a reduction from this
class of planning problems into CP-nets.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Search Techniques for Dominance Queries}
\label{sec:techniques}

In the previous section we showed that dominance testing is generally
hard even for binary-valued CP-nets, and that tractable algorithms exist 
only for specific problem classes. However, CP-nets impose a
rich structure on preferences that can be exploited by various search
strategies and heuristics which often significantly reduce
search effort, and allow the effective solution of
many problem instances.
In this section we discuss the search for flipping sequences and
several rules that allow significant pruning of the search tree 
without impacting soundness or completeness of the search procedure. 
These rules are described
in the context of improving flipping sequences, but they can be applied to
worsening search {\em mutatis mutandis}.


\begin{figure}
  \begin{center}
    \mbox{
      \begin{tabular}{cc}
      \begin{minipage}{2in}
        \begin{tabular}{c}
          \def\objectsizestyle{\scriptstyle}
          \xymatrix @R=15pt{
            & \bar{a}b\bar{c} \ar[d] \ar[lddd] \ar@/_5pc/[ldddddd]\\
            & \bar{a}bc \ar[d] \ar@/^2.5pc/[dddddd]\\
            & \bar{a}\bar{b}c \ar[dd] \ar[ld]\\
            \bar{a}\bar{b}\bar{c} \ar[dd]\\
            & a\bar{b}c \ar[ld] \ar[ddd]\\
            a\bar{b}\bar{c} \ar[d]\\
            ab\bar{c} \ar[dr]\\
            & abc
            }
        \end{tabular}
      \end{minipage}
        &
      \begin{minipage}{2.5in}
        \begin{tabular}{c}
          \def\objectsizestyle{\scriptstyle}
          \xymatrix @R=15pt@C=15pt{
             & \bara b \barc \ar[dl] \ar[d] \ar[dr]\\
             ab\barc \ar[d] & \bara\barb\barc \ar[d] & \bara bc \ar[d] \ar[dr]\\
             abc & a\barb\barc \ar[d] & abc & \bara\barb c \ar[d] \ar[dr]\\
             & ab\barc \ar[d] & & a \barb c \ar[dl] \ar[d] & \bara\barb\barc \ar[d]\\
             & abc & abc & a \barb\barc \ar[d] & a \barb\barc \ar[d]\\
             & & & ab\barc \ar[d] & ab\barc \ar[d]\\
             & & & abc & abc
            }        
        \end{tabular}
      \end{minipage}\\
      \ \\
      (a) & (b)\\
      \ \\
      \begin{minipage}{3in}
        \begin{tabular}{c}
          \def\objectsizestyle{\scriptstyle}
          \xymatrix @R=15pt@C=15pt{
             & \bara b \barc \ar[dl] \ar@{.>}[d] \ar@{.>}[dr]\\
             ab\barc \ar[d] & \bara\barb\barc \ar@{.>}[d] & \bara bc \ar[d] \ar@{.>}[dr]\\
             abc & a\barb\barc \ar[d] & abc & \bara\barb c \ar@{.>}[d] \ar@{.>}[dr]\\
             & ab\barc \ar[d] & & a \barb c \ar[dl] \ar@{.>}[d] & \bara\barb\barc \ar@{.>}[d]\\
             & abc & abc & a \barb\barc \ar[d] & a \barb\barc \ar[d]\\
             & & & ab\barc \ar[d] & ab\barc \ar[d]\\
             & & & abc & abc
            }       
        \end{tabular}
      \end{minipage}
      &
      \begin{minipage}{1.7in}
        \vspace{-1.5in}
        \begin{tabular}{c}
          \def\objectsizestyle{\scriptstyle}
          \xymatrix @R=15pt@C=15pt{
             & \bara b \barc \ar[dl] \ar@{.>}[d]\\
             ab\barc & \bara\barb\barc \ar@{.>}[d]\\
             & a\barb\barc
            }       
        \end{tabular}
      \end{minipage}\\
      \ \\
      (c) & (d)\\
      \ \\
    \end{tabular}
    }
\end{center}

\caption{(a) The preference graph induced by a CP-net; (b) the  improving 
search tree $\itree (\bara b \barc)$; (c) paths to outcome $a\barb\barc$;
and (d) pruning $\itree (\bara b \barc)$ by suffix fixing.}
\label{fig:imp-tree}
\end{figure}


Given a CP-net $N$, and an outcome $o$, we define the {\em
  improving search tree} of $o$, $\itree(o)$, as follows: $\itree(o)$
is rooted at $o$, and the children of every node $o'$ in $\itree(o)$ 
are those outcomes that can be reached by a single improving flip
from $o'$.  It is easy to see that every rooted path in $\itree (o)$
corresponds to some improving flipping sequence from the outcome $o$
(with respect to $N$), and vice versa.\footnote{The corresponding
worsening search tree of $o$ can be defined similarly
using the worsening flips.}
For example, consider the preference graph shown in
Figure~\ref{fig:imp-tree}(a), which is induced by the
CP-net in Figure~\ref{f:ex:cpn2.2}.
Figure~\ref{fig:imp-tree}(b) depicts the improving search tree $\itree
(\bara b \barc)$ with respect to this preference graph. Clearly,
we can treat every dominance query $N\models o \succ o'$ as
searching $\itree(o')$ for a node associated with the outcome $o$,
starting from the root node $o'$. For instance, in the example above,
given the dominance query $N\models a\barb\barc \succ \bara b \barc$, 
any of the dotted paths shown in Figure~\ref{fig:imp-tree}(c) bring us 
to outcome $a\barb\barc$. However, taking a different direction
during the tree traversal would lead to a dead end, requiring backtracking
in order to find a suitable flipping sequence. Any generic search
algorithm can be used to traverse the improving search tree to find
an improving sequence that supports a dominance query.

\subsection{Suffix Fixing}

%ceb2: removed discussion of determinism: except for binary, this doesn't
%  always give rise to a single move.
% \emph{Suffix fixing} is a rule that allows to make deterministic 
% moves in $T(o')$
% (i.e., choose flips that need not be backtracked over) without loosing
% completeness of the search is {\em suffix fixing}.

%ceb2: rewrote to define suffix  fixing more precisely
\emph{Suffix fixing} is a rule that allows certain moves in $T(o)$
to be pruned from the search tree without impacting 
completeness of the search.  Let $N$ be a CP-net over the variables 
$\bV = \{X_1,\ldots,X_n\}$,
numbered according to an arbitrary topological ordering consistent
with the network $N$. 
We define an {\em $r$th suffix} of an outcome $o \in \Assg(\bV)$, 
%hhfinal: <- changed i -> r here and at all analogous places, since
%               is used in a different way in the proof of Lemma 19.
for any $r \geq 1$,
to be the subset of the outcome values $o[X_r] o[X_{r+1}]\cdots o[X_n]$. 
Notice that the $r$th suffix of an outcome depends
on the topological ordering of variables used. Finally, we
say that the $r$th suffixes of outcomes $o$ and $o'$ \emph{match}
iff $o[X_j] =  o'[X_j]$ for all $r\leq j \leq n$. 

Let $o^{\ast}$ be a node in an improving search tree $T(o')$, and let $o$ be
the target of the search; in other words, we are attempting to
find a flipping sequence that proves $N\models o \pref o'$. 
The \emph{suffix fixing rule} requires that if the $r$th suffix
of $o^{\ast}$ and $o$ matches, for 
%ronen1 changed
%any 
some value 
%
$r$, no neighbors of
$o^{\ast}$ can be explored whose $r$th suffix does not also match $o$.
This is equivalent to ruling out the exploration of any flipping 
sequences that destroy the suffix of an outcome that matches the 
target outcome $o$. The following lemma ensures that pruning such
branches of the search tree $T(o')$ when searching for a path to
$o$ does not affect completeness.
\begin{lemma}
  Let $N$ be a CP-net, and $o$ and $o^{\ast}$ be outcomes whose $r$th
  suffix matches (for any topologically consistent
  ordering $X_1, \cdots, X_n$ of the variables in $N$).
  If there is path in $T(o^{\ast})$ from root $o^{\ast}$ to $o$, then there is
  a path from root $o^{\ast}$ to $o$ such that every outcome on that path
  assigns the same values to $X_r, \cdots X_n$ (i.e., with the same
  suffix match).
\end{lemma}
\begin{proof}
  The proof is straightforward: Because $N$ is acyclic, no suffix
  variable is an ancestor of any non-suffix variables. Hence,
  the value of the suffix variables does not influence (for better or
  worse) our ability to flip values of the remaining variables.
\end{proof}

Suppose, given query $N\models o \pref o'$, there is a path 
in $T(o')$ to an outcome $o^{\ast}$ of the type mentioned in the lemma
above. Since the subtree of $T(o')$ rooted at $o^{\ast}$ is just $T(o^{\ast})$,
we are assured that if any path from $o'$ to $o$ passes through
$o^{\ast}$, there is a path from $o'$ to $o$ that passes through $o^{\ast}$ in
which the suffix of $o^{\ast}$ is preserved on the subpath from 
$o^{\ast}$ to $o$.  From this we conclude:
\begin{prop}
Any complete search algorithm for the improving search tree remains
complete if pruning using the suffix rule is used.
\end{prop}
The suffix fixing rule effectively prunes the search tree under a
node $o^{\ast}$ as described above to contain only paths that retain the suffix
values of the target $o$.  Though backtracking over 
choices that lead to $o^{\ast}$ may be required, as may those choices at $o^{\ast}$
that preserve suffixes, consideration of the full search tree under
$o^{\ast}$ will not be required (if there is a nontrivial suffix match). 
For example, the improving search tree 
$\itree(\bara b \barc)$ for the query 
$N\models a\barb\barc \succ \bara b \barc$ 
discussed above, pruned using the suffix fixing rule
%hhfinal: added (for clarity):
and the variable ordering $A,B,C$, appears in
Figure~\ref{fig:imp-tree}(d). As we can see, this pruning can dramatically
reduce the size of the effective search tree.

\subsection{Least-Variable Flipping}


An extension of the suffix fixing rule is the \emph{least-variable
flipping rule}, defined as follows.  Suppose we have a CP-net $N$, and a
query $N\models o \pref o'$. Let $o^{\ast}$ be an outcome, and for any
variable $X_j$, let $\bfu$ denote the instantiation of $\bfU = \Pa(X_j)$
in $o^{\ast}$. We say $X_j$ is a {\em least-improvable variable in $o^{\ast}$}
if there is some
value $x \in\Dom(X_j)$ such that $x \succ^j_{\bfu} o^{\ast}[X_j]$, and no
descendent of $X_j$ in $N$ has this property. Intuitively, a 
least-improvable variable is one that is the lowest in $N$ that can be 
flipped to produce an outcome that is preferred to $o^{\ast}$.
Naturally, there may be several such variables.
We say $X_j$ is least improvable \emph{with respect to the target $o$}
iff $X_j$ is the least improvable variable among those not part
of a suffix match with $o$. In other words, if some suffix of $o$ and
$o^{\ast}$ matches, we apply the definition of least-improvable variable,
restricting attention to those variables that are not part of the
matching suffix. The least-variable flipping rule requires that
the only neighbors of a node $o^{\ast}$ that can be expanded in the
search for an improving sequence with target $o$ are those in
which some least improvable variable with respect to $o$ is improved.

The following lemma ensures that for binary-valued, directed-path singly
connected CP-nets, pruning an improving search tree using the least-variable
rule does not affect the completeness of any search procedure.


\begin{lemma}
  \label{l:singly-lowest}
  Let $N$ be a binary-valued, directed-path singly connected CP-net,
  and $o$ and $o^{\ast}$ be outcomes whose $r$th
  suffix matches (for any topologically consistent
  ordering $X_1, \cdots, X_n$ of the variables in $N$).
  Let $\{o_1,\ldots,o_m\}$ ($m\leq n$) be the set of all
  outcomes reachable from $o^{\ast}$ via some least-variable flip that does 
  not affect the matched suffix. 
  If there is path in $T(o^{\ast})$ from root $o^{\ast}$ to $o$, then there is
  a path from some $o_s$ ($s\leq m$) to $o$.
%hhfinal: <- changed o_i -> o_s (since index i is used for X_i already)
\end{lemma}


\begin{proof}
Without loss of generality and based on our earlier
  observations, we can assume no suffix match between $o$ and $o^{\ast}$ (if
so, restricting attention to the set of non-suffix variables does not affect
our argument). 

Now assume, contradicting the statement of the theorem, that none of the 
least-variable flips $o_s$ of $o^{\ast}$ have a path to $o$, but there
does exist a path from $o^{\ast}$ to $o$. This implies that none of these 
least-variable flips involve leaf variables in the network $N$. Otherwise, we 
could flip the value of such a leaf variable at $o^{\ast}$ without {\em any} 
effect on our ability to flip other variables, and thus be able to
construct a path from $o^{\ast}$ to $o$ that passes through any of the
$o_s$ that flip leaves.

Now, consider a leaf variable $X_i$ in $N$.  Since we are dealing with
binary variables, on any irreducible flipping sequence from $o^{\ast}$ to
$o$ the value of $X_i$ should be flipped exactly once.  However, the
current assignment $o^{\ast}[\Pa(X_i)]$ does not allow us to perform this
flip (see observation above). Thus, we must achieve
another assignment to $\Pa(X_i)$ before we can flip the value of
$X_i$, making it a part of a suffix match.

Let $N_{X_i}$ be the subnetwork of $N$ induced by $X_i$ and all ancestors
of $X_i$ in $N$. Because $N$ is directed-path singly connected,
$N_{X_i}$ forms a tree, directed toward its root $X_i$.  Now we reduce
$N_{X_i}$ further by removing all subtrees $N_{X_j}$ of
$N_{X_i}$, such that no variable in $N_{X_j}$ can be flipped in $o^{\ast}$.
Note that this step cause no loss of generality, since (due to
acyclicity of $N$) the assignment $o^{\ast}$ to the variables in
$N_{X_j}$ cannot be flipped first in any improving flipping sequence
beginning with $o^{\ast}$. Likewise, let $X_{i_1},\ldots,X_{i_{m'}}$, $m'
\leq m$, be the variables corresponding to the least-variable flips of
$o^{\ast}$ in $N_{X_i}$, and, for $1 \leq k \leq m'$, let $\rho_{i_k}$
be the (single) directed path from $X_{i_k}$ to $X_i$.

Let $\Upsilon = \bigcup_{j=1}^{m'}\left( N_{X_{i_j}} \setminus
  \{X_{i_j}\} \right)$.  
%Because of the form of 
Because $N_{X_i}$ is a tree, 
%hhfinal: <- changed (to make more explicit)
for $1 \leq
j \leq m'$, the variable $X_{i_j}$ {\em separates} the
variables in $N_{X_{i_j}} \setminus \{X_{i_j}\}$ and the paths
$\rho_{i_1},\ldots,\rho_{i_{m'}}$.  Therefore:
\begin{enumerate}[(i)]
\item No set of flips of the variables in $\Upsilon$ will enable us to
  flip the values of the variables on
  $\rho_{i_1},\ldots,\rho_{i_{m'}}$; in particular a flip of $\Pa(X_i)$ cannot
  be enabled.
  Thus, to enable a flip of $X_i$, eventually we will have to 
  flip the value of
  at least one variable from $X_{i_1},\ldots,X_{i_{m'}}$.
\item No value flip of $X_{i_1},\ldots,X_{i_{m'}}$ will affect
  (neither positively nor negatively) our ability to flip the values
  of the variables in $\Upsilon$. Thus, if there is an improving
  flipping sequence from $o^{\ast}$ to $o$, then at least one such sequence
  starts with a value flip of a variable from
  $X_{i_1},\ldots,X_{i_{m'}}$.
\end{enumerate}
This last observation contradicts the assumption that there is a flipping
sequence from $o^{\ast}$ to $o$ that does not pass through at least
one $o_s$.
\end{proof}


The least-variable flipping rule does not distinguish the flips
of different candidate least improvable variables; it simply restricts flips
to such variables. In general, not all least-variable flips are 
suitable---some may lead to dead-ends, requiring backtracking
(a point illustrated in Section~\ref{S:polytree}). However, 
when we backtrack, we need only consider other least-variable
flips, not all flips, thus significantly reducing the size of
the search tree and the expected amount of backtracking.
We observe that the {\sf TreeDT} algorithm for binary-valued, tree-structured
CP-nets essentially implements the least-variable flipping rule,
which is, therefore, a complete and backtrack-free search procedure
for binary-valued, tree-structured networks.




% %ceb2: These two paras are redundant---deleted first
% % Examples~\ref{ex:mvchain1} and~\ref{ex:mvchain2} below show
% % that Lemma~\ref{l:singly-lowest} presents probably the widest class
% % of CP-nets for which the lowest-flips-only rule is complete:
% % Example~\ref{ex:mvchain1} shows that the lowest-flips-only rule does not
% % preserves completeness in binary-valued, multiply-connected CP-nets,
% % while Example~\ref{ex:mvchain2} shows the same for 
% % multi-valued, directed-path singly connected
% % CP-nets.

% Unfortunately, in multi-valued domains, even for tree-structured CP-nets the
% least-variable flipping rule is neither backtrack-free, nor complete;
% the former is illustrated in Example~\ref{ex:mvchain1}, the latter
% in Example~\ref{ex:mvchain2}.

%carmel2: the second paragraph above is not redundant --
%         it was just poorly written :-). Below see the rephrasing
%         of BOTH paras in one paragraph.
Examples~\ref{ex:mvchain1} and~\ref{ex:mvchain2} below show that
Lemma~\ref{l:singly-lowest} presents probably the widest class of CP-nets for
which the least-variable flipping rule is complete: Example~\ref{ex:mvchain1}
shows that the least-variable flipping rule does not preserve completeness in
binary-valued, max-2-connected CP-nets, while Example~\ref{ex:mvchain2} shows
the same for multi-valued, directed-path singly connected CP-nets.  Note that
the CP-net in Example~\ref{ex:mvchain2} forms a chain. Therefore,
binary-valued, tree-structured CP-nets are probably the widest class of CP-nets
for which the least-variable flipping rule is both complete and backtrack-free.


\begin{example}
  \label{ex:mvchain1}
  Consider the binary-valued CP-net in Figure~\ref{fig:ex:mvchain1},
  where Figure~\ref{fig:ex:mvchain1}(a) depicts the graph of the
  CP-net, and Figure~\ref{fig:ex:mvchain1}(b) shows the corresponding CPTs.
  Given query $N\models abcde \pref \bara\barb\barc\bard\bare$, we
  work in the improving tree rooted at $\bara\barb\barc\bard\bare$.
  The only least improvable variable that can be flipped at the root 
  outcome is $B$
  (while $A$ and $E$ can be flipped, they are not least improvable).
  Unfortunately, flipping $B$ to value $b$ leads to outcome
  $\bara b\barc\bard\bare$, from which the target $abcde$ is unreachable:
  \begin{enumerate}[(i)]
  \item In order to reach the target value $d$ for the variable $D$,
    first we should achieve the assignment $\barb \wedge c$ to the variables
    $B$ and $C$;
  \item Achieving the assignment $\barb \wedge c$ after the flip in question
    from $\barb$ to $b$ (given $\bara\wedge\bare$) is possible only 
    by restoring the value $\barb$ for $B$, which requires
    $a \wedge e$; and
  \item Flipping the value of $B$ from $b$ to $\barb$ given $a \wedge e$ will
    lead us to a situation in which we can no longer flip $B$, preventing
    us from achieving the target value $b$.
  \end{enumerate}
  Thus the least-variable flipping rule will not allow the discovery of
  an improving flipping sequence.
  
  On the other hand, there is a flipping sequence from
  $\bara\barb\barc\bard\bare$ to $abcde$ that proves the query:
  \[
    \bara\barb\barc\bard\bare \rightarrow a\barb\barc\bard\bare \rightarrow
    a\barb c\bard\bare \rightarrow a\barb cd\bare 
     \rightarrow abcd\bare \rightarrow abcde
  \]
This sequence requires that $A$ be flipped at the root, despite the fact that
it is not a least-improvable variable.  $\square$
\end{example}

\begin{figure}
  \begin{center}
  \begin{tabular}{cc}
    \begin{minipage}{2in}
      \mbox{
        \def\objectsizestyle{\scriptstyle}
        \xymatrix @R=35pt@C=8pt{
          *++[o]=<1.5pc>[F]{A} \ar[d]\ar[drr] & & *++[o]=<1.5pc>[F]{E}\ar[d]\\
          *++[o]=<1.5pc>[F]{C} \ar[dr] & & *++[o]=<1.5pc>[F]{B} \ar[dl]\\
          & *++[o]=<1.5pc>[F]{D}
          }
        }
    \end{minipage}
    &
    \begin{minipage}{2in}
      \begin{tabular}{|c|c|}
        \hline
        Variable & CPT\\
        \hline
        $A$ & $a \succ \bara$\\
        \hline
        $B$ &
        \begin{minipage}{1in}
          \ \\
          $a\wedge e\;\; :\;\; \barb \succ b$\\
          $\bara\vee \bare\;\; :\;\; b \succ \barb$\\
        \end{minipage}\\
        \hline
        $C$ &
        \begin{minipage}{1in}
          \ \\
          $a \;\; :\;\; c \succ \barc$\\
          $\bara \;\; :\;\; \barc \succ c$\\
        \end{minipage}\\
        \hline
        $D$ &
        \begin{minipage}{1in}
          \ \\
          $c\wedge \barb\;\; :\;\; d \succ \bard$\\
          $\barc\vee b\;\; :\;\; \bard \succ d$\\
        \end{minipage}\\
        \hline
        $E$ & $e \succ \bare$\\
        \hline
      \end{tabular}
    \end{minipage}\\
    \ \\
    (a) & (b)\\
  \end{tabular}
\end{center}
  \caption{A multiply connected CP-net for which the least-variable flipping
   rule causes incompleteness.}
  \label{fig:ex:mvchain1}
\end{figure}

\begin{example}
  \label{ex:mvchain2}
  Consider a chain CP-net with three variables $A$, $B$, and $C$, such
  that $A$ is the parent of $B$, and $B$ is the parent of
  $C$.  Suppose $A$ has domain $\{a,\negn a\}$, $B$ has domain
  $\{b_1,b_2,b_3\}$, and $C$ has domain $\{c,\negn c\}$, with the
  following conditional preferences:
\begin{gather*}
  {a \pref \negn a;}\\
  {a : b_3 \pref b_2 \pref b_1};\\
  {\negn a : b_3 \pref b_1 \pref b_2};\\
  b_1: c\pref \negn c \;\;\; b_2: \negn c\pref c;\;\;\;  b_3: c\pref \negn c 
\end{gather*}
Consider the query $N \models a b_3 \negn c \pref \negn a b_1 c$. The
value $c$ cannot be improved in the context of $b_1$, but $b_1$ can be
improved to $b_3$ in the context of $\negn a$; in fact this is the only
least-improvable variable flip for outcome $\negn a b_1 c$. 
Unfortunately, this flip leads to outcome $\negn a b_3 c$ from which no
path to the target $a b_3 \negn c$ exists. In contrast, flipping
the non-least-improving variable $A$ to $a$ first allows the discovery
of a successful improving path: after flipping $\negn a$ to $a$, we
change $b_1$ to $b_2$, $c$ to $\negn c$, and finally $b_2$ to $b_3$. $\square$
\end{example}

Though for multiply-connected networks, and networks with multi-valued 
variables, the least-variable flipping rule is not complete,
we believe that it can provide useful heuristic guidance in these cases.
The {\em least-variable-first heuristic} is a heuristic for ordering
children in an improving search tree---it requires that when
expanding a node $o^{\ast}$ (with respect to some target $o$), the children
corresponding to least-improving variables be explored first.
This will typically reduce the number of nodes expanded in the tree,
because the least-variable-first heuristic can be
viewed as embodying a form of {\em least commitment}. Flipping the
values of a least-improving variable can be seen as leaving maximum
flexibility in flipping the values of other variables. An upstream
variable limits the possible flipping sequences more drastically than
a downstream variable since altering a variable
does not limit the ability to flip the values of its non-descendants.

For multivalued networks,
%hhfinal: <- added (for clarity)
the least commitment strategy can be used to extend the
least-variable-first heuristic using the {\em least improving} rule:
alternative improving flips of the same least-improvable variable are
considered from the least improving flip to the most improving flip
(i.e., first the flip that leads to the {\em least preferred} improving
value is adopted).  This allows greater flexibility in the movement of
``downstream'' variables. While one can always further improve the
value of the variable in question from its less preferred value to a
more preferred value (provided that parent values are maintained),
``skipping'' values may prevent us from setting
descendants to their desired values. In fact, this was illustrated in
Example~\ref{ex:mvchain2}, 
where, after the crucial flip of variable $A$,
using the {\em least improving} rule as a
heuristic leads directly to the target outcome.



\subsection{Forward Pruning}

In a search procedure for an improving flipping sequence, no matter
whether this procedure adopts the above heuristics or not, one can use a
general {\em forward pruning} technique. This technique has a number of
desirable properties:
\begin{enumerate}[(a)]
\item it often quickly shows that no flipping sequence is possible;
\item it prunes the domains of the variables to reduce the flipping
search space;
\item it doesn't compromise soundness or completeness; and
\item it is relatively cheap: its time complexity is $O(nrd^2)$, where
  $n$ is the number of variables, $r$ is the maximum number of
  conditional preference rules for each variable, and $d$ is the size
  of the largest variable domain.
\end{enumerate}
The general idea is to sweep forward through the network, pruning any
values of a variable that cannot appear in any improving
flipping sequence for a given query. Intuitively, we consider
the set of flips possible, ignoring interdependence of the parents and the
number of times the parents can change their values.

We consider the variables in an order consistent with the network
topology (so that parents of a node are considered before the node).
For each variable $X_j$ with parents $\bfU$, we build a {\em domain
  transition graph} with nodes corresponding to the possible values
$x_i \in\Dom(X_j)$.  For each conditional preference relation
$\pref^j_\bfu$ over $\Dom(X_j)$ of the form: 
\[x^\bfu_1 \pref x^\bfu_2 \pref \cdots \pref x^\bfu_d\]
such that $\bfu$ contains only unpruned values of the parents $\bfU$
of $X_j$, we include directed arcs between the successive values in the
ordering $\pref^j_\bfu$ (i.e., an arc from $x_i$ to $x_{i-1}$, for each
$1 < i \leq d$).

When answering query $N\models o \succ o'$, we can prune any value
of $X_j$ that is not on a directed path from $o'[X_j]$ to $o[X_j]$ in the
domain transition graph for $X_j$. This can be implemented by running
the well-known Dijkstra's algorithm~\cite{clr:algorithms} twice: once
to find the nodes reachable from $o'[X_j]$ and again to find the nodes
that can reach $o[X_j]$. These sets of nodes can be intersected to find
the possible values for $X_j$ along any path from $o'[X_j]$ to $o[X_j]$ in
$\itree (o')$ (i.e., along any improving sequence from $o'[X_j]$ to
$o[X_j]$ with respect to $N$). If the intersection is empty, the
dominance query fails: there is no legal flipping sequence from
$o'[X_j]$ to $o[X_j]$.  This often results in quick failure for
straightforward queries, so that we only carry out the search for
non-obvious cases.

\begin{example}
Consider any CP-net $N$ in which $A$ and $B$ are both binary root
variables, and the preferences over the values of $A$ and $B$ are $a
\succ \bara$ and $b \succ \barb$. Given a query 
$N\models a\barb\ldots \succ \bara b \ldots$, first we consider $A$.  
The domain
transition graph for $A$ consists of an arc $\bara \rightarrow a$,
thus no values of $A$ are pruned. If the example were changed
slightly so that $A$ had a third value $\negn{\negn a}$, where $a
\pref \negn a\pref \negn {\negn a}$, then this third value could be
pruned from $A$, thus simplifying the tables for all the children of
$A$.

We then consider $B$, whose domain transition graph consists of a single
arc $\barb \rightarrow b$. Since the value of $B$ in the (purported)
more preferred outcome of the query ($\barb$) is not reachable in the
domain transition graph of $B$ from the value of $B$ in the
(purported) less preferred outcome of the query ($b$), the query
fails quickly without looking at the other variables.  $\square$
\end{example}



\section{Incompletely Specified Preferences and Indifference}
\label{sec:partial}

In many practical applications, one expects to see reluctance on
behalf of the user to provide complete CPTs or to totally order the
values of each variable in every possible context. Thus, it is natural
to ask how our results and techniques can be applied in these cases.

It turns out that all the results presented in this paper, except for
the linear time procedure for ordering queries, can be easily extended
to work both on CP-nets with partially specified CPTs, and on
satisfiable CP-nets 
that capture statements of preferential
indifference.  For instance, all the results presented in
Section~\ref{sec:complexity} with respect to {\em dominance queries}
remain applicable ``as is,'' because almost all of these results were shown
by Brafman and Domshlak~\scite{Domshlak:Brafman:p-jair03} to be valid in
more general setting of classical planning. The only case that was not
analyzed by Domshlak and Brafman is the case of tree
CP-nets.  However, the correctness of the {\sf TreeDT} procedure for
``extended'' CP-nets can be easily verified, and its complexity remains
quadratic. This stems from the fact that Lemma~\ref{l1} is valid in
the more general planning setting~\cite{Domshlak:Brafman:p-jair03}. The
only point that requires clarification is the difference between 
partial specification and indifference with respect to flipping
sequences: Given a variable $X$ with parents $\bU$, and two values
$x_1,x_2 \in \Dom(X)$, if $x_1$ and $x_2$ are equally preferred given
$\bu\in\Assg(\bU)$, then given $\bu$ we can flip the value of $X$ from
$x_1$ to $x_2$, and vice versa.  Alternatively, if $x_1$ and $x_2$ are
incomparable given $\bu\in\Assg(\bU)$, then given $\bu$ we cannot flip
the value of $X$ from $x_1$ to $x_2$, nor from $x_2$ to $x_1$.

The complexity of dominance testing in the context of indifference and
incompletely specified CPTs remains an open problem.  
%hhfinal: the following argument didn't make sense to me (or david):
%However, notice
%that indifference cannot make the problem harder, since indifference
%statements {\em strictly increase} our ability to flip the values of
%the variables. In addition,
However, Theorem~\ref{t:mv-dominance} below shows that the
flipping sequence search over multi-valued CP-nets with partially
specified preferences is not in {\sc np}, even if the CP-net forms a {\em
chain} and the variables are three-valued only.

\begin{thm}
  \label{t:mv-dominance}
  Flipping sequence search over multi-valued CP-nets with partially specified
  preferences is not in {\sc np}.
\end{thm}

\begin{proofa}
  For the proof see Appendix~\ref{sec:appendixa}.
\end{proofa}

Now, consider {\em outcome optimization} queries. When the CPTs
are allowed to be partially specified, or the statements of
indifference are allowed, the CP-net may induce more than one
nondominated outcome. For instance, consider again
Example~\ref{ex:cpn1} ({\sf My Dinner I}).  If the
preference for the type of wine given fish soup
is not specified, or the decision maker considers both red and white wine 
to go equally well with fish soup, then this CP-net induces two
nondominated outcomes: fish soup with white wine, and fish soup with
red wine.

The forward sweep procedure for the outcome optimization queries
presented in Section~\ref{sec:outcomes} can be easily extended for the
cases of partial specification and/or indifference by adding branching
on each variable $X$ for which the (already generated) assignment on
$\Pa(X)$ induces more than one nondominated value from $\Dom (X)$. The
complexity of the resulting algorithm is $O(n\alpha)$, where $n$ is the
number of variables in the CP-net, and $\alpha$ is the number of
nondominated outcomes induced by the CP-net. Of course, $\alpha$ can
be exponential in the size of the CP-net.%
\footnote{The tight upper bound of $\alpha=2^n$ can be shown for any 
  CP-net by simply leaving all CPTs unspecified.}
However, our adapted forward sweep procedure has the
{\em anytime} property---the solutions are generated
iteratively, and the time to add a new nondominated outcome
to the current set of generated solutions is $O(n)$. Therefore,
the complexity of generating $k$ nondominated solutions is linear
in $k$.

Finally, an important query that can be answered efficiently
in standard CP-nets is the {\em outcome ordering} query (see
Section~\ref{S:initial-dominance}). Although the basic
Corollary~\ref{col:weak-dom} remains valid in the case of CP-nets with
partial specifications or statements of indifference,
this is not the case for Theorem~\ref{t:weak-dom}.
%Recall that Theorem~\ref{t:weak-dom} was proved by showing that, given
%two different outcomes $o$ and $o'$ with respect to a CP-net $N$,
%either $o \not\prec o'$, or $o' \not\prec o$, or both, can be deduced
%using the condition in Corollary~\ref{col:weak-dom}. It turns out that
%this is not correct in case of CP-nets with partial preference
%specification or indifference, even if the variables are binary.
Therefore, the computational complexity of ordering queries for 
extended CP-nets remains an open question, and we conjecture that this
problem is hard.






\section{Concluding Remarks}
\label{sec:conclude}

In this paper we introduced CP-nets, a new graphical model for
representing qualitative preference orderings which reflects
conditional dependence and independence of preference statements under
a {\em ceteris paribus} semantics. This formal framework offers a
compact and arguably natural representation of preference information,
and allows us to efficiently answer some of the principal forms
of preference queries.

We described several types of queries and algorithms for answering
them with respect to a specific CP-net. In particular, outcome
optimization and outcome ordering queries were shown to be solvable in
time linear in the number of variables in the network. For the
dominance queries, however, the situation is more complicated. First,
we demonstrated the equivalence of answering dominance
queries with the task of determining existence of an improving (or
worsening) sequence of variable value flips with respect to the given
CP-net. Then, we reduced the latter task to a special subclass of
classical planning problems.  These insights
allowed us to show that, in general, answering dominance queries is
{\sc np}-hard, but that polynomial algorithms exist for tree and
polytree-structured, binary-valued CP-nets.

In addition, we presented several techniques that one can use in a
generic search procedure
for an improving flipping sequence. Some
of these techniques were shown to have no impact on soundness or
completeness of the search for any CP-net, while other techniques have
this property only for binary-valued CP-nets. However, we argued that
latter techniques can be modified into general purpose heuristics that
are likely to reduce significantly the size of the expanded search
tree.

Finally, we analyzed the applicability of our results for CP-nets that
allow partially specified preferences and/or capture statements of
indifference.


\subsection{Applications}

Our goal in developing the CP-nets formalism is
to facilitate the development of  applications. 
One such application---preference-driven, adaptive
multimedia document presentation---was recently developed at Ben-Gurion
University~\cite{Domshlak:Brafman:Shimony:ijcai01,Gudes:Domshlak:Orlov:mdde02}.
We described the central components of this system in
Section~\ref{S:multimedia}.  Another application in which both
conceptual and computational properties of CP-nets seem
to be useful is a distributed meeting scheduler. A basic prototype for
such a system has been implemented at Ben-Gurion
University~\cite{Domshlak:Brafman:soft01}. We are currently extending
this system, while working on the related theoretical issue of
multi-agent preference-based optimization.

Another potential application for qualitative preferences in general,
and thus for CP-nets in particular, is sorting a product database
according to user-specified preferences. This problem is highly
relevant in the context of electronic commerce.  Several rather
conceptually simplistic, though quite interesting, commercial
applications that rely on unconditional preference statements are
available on the World Wide Web; examples include Active Sales
Assistant{\footnotesize \texttrademark} (see {\tt www.activebuyersguide.com}) 
and 
Personalogic{\footnotesize \texttrademark} (see {\tt www.personalogic.com}).
The general idea
is to assist a user in selecting a specific product from a product database
according to her preferences. Here, it is very important to use
compact and natural representations for preference information.
CP-nets extend current models (which typically don't allow conditional
preference statements), yet offer efficiency in ordering a given set
of alternatives. Another important aspect of this problem is that the
given database precisely defines the products (represented as vectors
of attribute values) available, and preference information is only
required to the extent that it narrows
the choice of product to a sufficiently small selection of products 
from this database.  Both the
graphical properties of CP-nets underlying the efficiency of the
ordering queries, and the various dominance testing strategies, can be
exploited in this context to find a subset of products that are not
dominated by any other product in the database, given the
(conditional) preference information extracted from the user.  Here,
an interactive and dynamic approach appears to be most promising,
where the user is prompted for additional preference statements until
the ordering of the products in the database is sufficiently
constrained by the preference information to offer a reasonably small
selection of products.

Another growing application area for CP-nets is automated
constraint-based product configuration~\cite{Sabin:Weigel:ieee98}.
The task is to assemble a number of components that compose a product
such that given compatibility constraints are satisfied. A simple
example of this is the assembly of components for a computer system
where, for instance, the type of system bus constrains the choice of
video and sound cards.  While there has been a wide and growing body
of research in modeling configuration problems and efficient problem
solving methods, there is still a need for more work on modeling and
learning user preferences, and using these to achieve configurations
that are not only feasible, but also satisfactory from the user point
of view.  These issues are emphasized in many papers on
configuration~\cite{Freuder:OSullivan:conf01,Haag:ieee98,Junker:ijcai97,Junker:conf01,Soininen:Niemela:nm98},
especially when high-level configurators for specific, real-life
domains are discussed~\cite{Haag:ieee98}. The importance of
incorporating user preferences into the configuration problem stems
from the fact that many such problems are weakly constrained and have
numerous feasible solutions~\cite{damb-birm:AIEng}. The value of these
solutions, from the subjective point of view of a particular user, may
vary significantly.

CP-nets can be used to represent user preferences which will be
used together with compatibility constraints to search for most
preferred, feasible configurations.  In contrast to the database
sorting application above, here the set of possible vectors of feature
values (i.e., configurations) is not explicitly given, but implicitly
specified by the compatibility constraints. A CP-net based search
algorithm by~\citeA{bbgp:spring97} was specifically designed to address
this problem. For the description of this algorithm, as well as for
analysis of its computational properties we refer the reader
to~\citeA{bbgp:spring97,Domshlak:Brafman:soft01}. 


\subsection{Related Work}
A number of lines of research are related to CP-nets.  In addition to
the conceptual work in philosophy and philosophical logic described in
Section~\ref{sec:model}, in AI, Doyle and Wellman
\scite{DoyleWellman.AAAI91,DoyleWellman.AAAI95} explored \CP\
assertions and their logical properties.  However, their work did not
exploit the notions of preferential independence, and in particular
did not considered graphical representations of preference
statements. To the best of our knowledge, there are no computational
results known for this formalism.  Therefore, it is not
clear whether useful queries can be answered efficiently in
this framework.


On the surface, CP-nets are reminiscent of Bayesian
networks~\cite{pearl}, which are also graphical structures capturing
conditional independence assertions. Indeed, Bayesian networks and
their utilization of probabilistic independence provide important
motivation to our work, but the two structures differ considerably in
their properties and the type of information they present.

Motivated by the same considerations driving our work, Bacchus and
Grove \scite{bacchus-grove:uai95} and La Mura and Shoham
\scite{lamura-shoham:uai99} study different notions of independence and
their associated graphical representations. Both representations allow
for quantitative assessments, unlike CP-nets (at least in their
current form) and differ from CP-nets in the precise nature of the
independence concept studied. In particular, Bacchus and Grove
concentrate on the notion of {\em conditional additive independence.}
Additive independence is a very strong property, requiring that the
utility of an outcome be the sum of the ``utilities'' of the
different  variable values of the outcome.  Conditional additive
independence is a weaker requirement, and thus more promising in
practice. Bacchus and Grove show that the conditional additive
independence properties of a domain can be captured by an undirected
graph 
%hhfinal: changed slightly (to avoid confusion betw nodes and sets of nodes):
where for set of nodes $\bfA,\bfB,\bfC$, $\bfA$ is independent of 
$\bfB$ given $\bfC$ if $\bfC$ separates
between the nodes in $\bfA$ and $\bfB$.  La Mura and Shoham
\scite{lamura-shoham:uai99} define the concept of {\em u-independence}
using a \CP\ comparison operator over utilities. This
operator measures the ``intensity'' of preference for specific
values of certain variables given some fixed value for the other
variables and with respect to a fixed reference point. They also define
an undirected graphical structure, {\em expected utility networks}, in which
u-independence is represented using the notion of node separation.

Finally, recent work by Benferhat, Dubois and
Prade~\scite{Benferhat:Dubois:Prade:ai01} provides a preliminary investigation
of the potential of possibilistic logic in qualitative decision analysis, and
more specifically in qualitative preference representation.  The possibilistic
approach takes utilities into account, as well as probabilities, but provides a
qualitative approach to decision problems by replacing numeric preferences and
probabilities with linear orderings. For discussion of this approach to
utilities and preference representation,
see~\citeA{Benferhat:Dubois:Prade:ai01,Dubois:Godo:Prade:Zapico:98,Dubois:LeBerre:Prade:Sabbadin:98,Dubois:Prade:Sabbadin:97},
and for related qualitative models, see~\citeA{boutilier:kr94,tan-pearl:kr94}.




\subsection{Future Work}
We see a number of potential extensions to the work described in this
paper.  In particular, our work leaves a number of interesting open
theoretical questions. First, the worst case complexity of dominance
testing with respect to acyclic, binary-valued CP-nets needs to be
established---it is still an open question whether this problem is in
{\sc np}.  Second, the complexity of dominance queries with respect to
multi-valued CP-nets remains an open problem. Third, it is not clear
how hard ordering queries are for CP-nets that capture partial
preference specification and/or the statements of preferential
indifference. 
%ronen2 added following reviewer 
Finally, there is a need to understand the expressive
power of CP-nets better, specifically: what sort of 
partial orderings are
and are not representable by CP-nets; and among orderings 
representable by CP-nets, which ones are can only be represented by
a cyclic network.

Cyclic networks present another important challenge. Such networks can
arise in applications where a natural notion of neighborhood is
defined on the set of variables such that preferences for one variable
value depend on the value of its neighboring variables. In such cases,
the user may find it more natural to provide a cyclic preference
structure and we must be able to determine whether the specified
network is satisfiable.  
In addition, inference methods for such
networks need to be developed or, alternatively, methods for reducing
cyclic networks to acyclic networks without significant blow-up in
size. 
%ronen2 added
A number of recent papers have started to deal with this question,
with some interesting insights and results
%Recently, a some computational and conceptual results on cyclic
%preferential dependencies were introduced in~%
\cite{Domshlak:PhD,Domshlak:Brafman:kr02,BD:ijcai03,DRVW:ijcai03}.

We are working on various extensions of the framework presented here.
These extensions include the use of conditional preference statements
that contain a small amount of quantitative information.  Existing
applications (such as online interactive consumer guides) suggest that
a limited amount of such quantitative preference information might be
relatively easy to extract from the user in a natural way, and is very
useful for inducing stronger preference orderings.  Preliminary
work on this topic has been undertaken \cite{ucpnets:uai01}.

Another interesting extension of CP-nets are TCP-nets
\cite{Brafman:Domshlak:uai02}. TCP-nets add importance relations and
conditional relative importance statements to the the conditional 
\emph{ceteris paribus} statements supported by CP-nets. Conditional 
importance statements have
the form ``if $A=a$ then optimizing $B$ is more important to me than optimizing
$C$''. For example, ``If I will be flying at night, then having a better
seat is more important than getting a more preferred carrier.''


Finally, preference-based optimization presents an interesting tradeoff between
the amount of user interaction required for extracting preference information
and the amount of computation needed to determine the most preferred feature
vectors.  By asking very specific questions about particular, potentially
complex preferences, finding most preferred feature vectors can become much
easier. On the other hand, asking too many questions, especially those not
really necessary for establishing relevant preferences, will annoy the user and
make the system less usable. Thus, finding good tradeoffs between the amount of
user-interaction and computation time for answering queries---such as finding
most preferred items from a database of optimal configurations---seems to be a
promising direction for future research. This is related to the motivation
underlying goal programming \cite{dyer:mgmtsci72,ignizio:1982}.  The structure
of CP-nets can be exploited in determining preference elicitation strategies.
This has been explored in the context of CP-nets with quantitative information
\cite{ucpnets:uai01}; it remains to be seen how to use such techniques in a
purely qualitative setting.

\section*{Acknowledgments}

Some parts of this paper appeared in C. Boutilier, R. Brafman, H. Hoos,
and D. Poole, ``Reasoning with Conditional Ceteris Paribus Preference
Statements,'' \emph{Proceedings of the Fifteenth Conference on Uncertainty 
in Artificial Intelligence}, pp.71--80, Stockholm, 1999; and in
C. Domshlak and R. Brafman, ``CP-nets---Reasoning and Consistency Testing,''
\emph{Proceedings of the Eighth International Conference on
  Principles of Knowledge Representation and Reasoning},
pp.121--132, Toulouse, 2002.
Thanks to Chris Geib for his contributions to earlier, related models
of CP-nets, and to the anonymous referees for their many useful suggestions.
Boutilier, Hoos and Poole were supported by the Natural Sciences and
Engineering Research Council, and the Institute for Robotics and
Intelligent Systems. Brafman acknowledges the support of the
Paul Ivanier Center for Robotics Research and Production Management.

\appendix
\section{}
\label{sec:appendixa}


\begin{atheorem}{t:tree}
{\em $\Theta (n^2)$ is a lower bound for the flipping-sequence search over
binary-valued, tree-structured CP-nets.}
\end{atheorem}


\begin{proof}
  \label{page-t:tree}
The proof is by example of a dominance testing query over a binary-valued, tree 
CP-net for which the size of a minimal flipping sequence is $\Theta(n^2)$.

Consider the following CP-net $\cN$ defined over binary variables
$\{X_1,\ldots,X_n\}$, where $n = 2k+1$ for some $k\in{\Bbb N}$. 
The domain of each variable $X_i$ is $\cD(X_i)=\{x_i,\barx_i\}$.
For $1 \leq i \leq n$, $\Pa(X_i) = \{X_{i-1}\}$, thus $\cN$ forms
a directed chain.
The CPTs capturing the preferences over the values of $\{X_1,\ldots,X_n\}$ are
shown in Figure~\ref{table:tree2}(a).

\begin{figure}[ht]
\begin{center}
  \begin{tabular}{cc}
    \begin{tabular}{c}
    \begin{minipage}{2.5in}
  {\footnotesize
\begin{tabular}{|c|c|}
\hline
Variable & CPT\\
\hline
\hline
$i = 1$ & $x_i \succ x_i'$\\
\hline
$1 < i \leq k+1$ & 
\begin{minipage}{1in}
\begin{eqnarray*}
x_{i-1} &:& x_i \succ \barx_i\\
\barx_{i-1} &:& \barx_i \succ x_i\\
\end{eqnarray*}
\end{minipage}\\
\hline
$k+1 < i \leq n$ & 
\begin{minipage}{1in}
\begin{eqnarray*}
x_{i-1}  &:& \barx_i \succ x_i\\
\barx_{i-1} &:& x_i \succ \barx_i\\
\end{eqnarray*}
\end{minipage}\\
\hline
\end{tabular}
}
\end{minipage}\\
\ \\
(a)\\
\ \\
\begin{tabular}{c}
  $o  = x_1x_2x_3x_4x_5$\\
  $o' = \barx_1x_2\barx_3x_4\barx_5$
\end{tabular}
\end{tabular}
&
\begin{minipage}{2in}
  {\footnotesize
%    \def\objectsizestyle{\scriptstyle}
    \xymatrix{
      *++[o]=<1.5pc>[F]{X_1} \ar[d] & \barx_1 \ar[r]^{7} & x_1\\
      *++[o]=<1.5pc>[F]{X_2} \ar[d] & x_2 \ar[r]^{4} &  \barx_2 \ar[r]^{8} & x_2\\
      *++[o]=<1.5pc>[F]{X_3} \ar[d] & \barx_3 \ar[r]^{1} & x_3 \ar[r]^{5} & \barx_3 \ar[r]^{9} & x_3\\
      *++[o]=<1.5pc>[F]{X_4} \ar[d] & x_4 \ar[r]^{2} & \barx_4 \ar[r]^{6} & x_4\\
      *++[o]=<1.5pc>[F]{X_5}        & \barx_5 \ar[r]^{3} & x_5\\
      }
    }
\end{minipage}\\
\ \\
(b) & (c)
\end{tabular}
\end{center}
\caption{Illustration for the proof of Theorem~\ref{t:tree}:
  (a) CPTs for $n$ variables; (b) $o$ and $o'$ for $k=2$; and (c) flipping
  sequence for $k=2$.}
\label{table:tree2}
\end{figure}

Now consider the dominance testing query $\llbracket N \models o \succ
o' \rrbracket$, where, for $1\leq i\leq n$:
\begin{eqnarray*}
  o[X_i] & = & x_i\\
  o'[X_i] & = & \sset{
    x_i, \;\;\; i = 2m,\\
    \barx_i, \;\;\; i = 2m+1
    }\hspace{1cm} m \in \nat
\end{eqnarray*}
The length of the minimal (and actually the only) flipping sequence
from $o'$ to $o$ is $k^2+2k+1$, proving the required lower bound. The
$j$th flip on this sequence changes the value of the variable
$X_{k+1-\alpha+\beta}$, where:
\begin{eqnarray*}
  \alpha & = & \lfloor j/(k+1)\rfloor\\
  \beta & = & (j-1)\; {\mathrm{mod}\; (k+1)}
\end{eqnarray*}
Informally, the first $k+1$ flips change the values of $X_{k+1}, \ldots,
X_n$ (in this order), next $k+1$ flips change the values of $X_{k},
\ldots, X_{n-1}$, then $X_{k-1}, \ldots, X_{n-2}$, etc.  Finally, the
last $k+1$ flips change the values of $X_{1}, \ldots, X_{k+1}$.
There are $k+1$ such sets, of $k+1$ flips each, the length
of the above flipping sequence is thus $k^2 + 2k +1$.

Figure~\ref{table:tree2}(b-c) illustrates $o$ and $o'$, and the
corresponding flipping sequence for $k=2$ (i.e., $n=5$). In
Figure~\ref{table:tree2}(c), each variable $X_i$ is annotated with its
value flips along the flipping sequence: Arrows between the values
stand for the value flips, and the sequential numbers of the flips
along the flipping sequence appear as the arrow labels.

Now we prove that the size of the minimal flipping sequence for this
example (with $n=2k+1$) is $k^2+2k+1$. We divide the proof into two
steps, and show that on a minimal flipping sequence from $o'$ to
$o$:
\begin{enumerate}
\item For $1 \leq i \leq k+1$, every variable $X_{k+i}$ (last $k+1$
  variables) must change its value at least $k+2-i$ times, and
\item For $1 \leq j \leq k$, every variable $X_{j}$ (first $k$
  variables) must change its value at least $j$ times.
\end{enumerate}

\noindent (1) The proof of the first claim is by induction on $i$. For $i=k+1$, the
variable $X_{2k+1}$ (i.e., $X_n$) must change its value at least once since
$o[X_{2k+1}] \neq o'[X_{2k+1}]$.

Now, we assume the induction hypothesis that, for $l \leq i \leq k+1$,
every variable $X_{k+i}$ must change its value at least $k+2-i$ times,
and prove the claim for $X_{k+l-1}$.  Recall that
$X_{k+l-1}$ is the only parent of $X_{k+l}$, thus every pair of successive
flips of $X_{k+l}$ must require different values of $X_{k+l-1}$.

Assume that $k+l$ is even. Then, the first flip of $X_{k+l}$ is from
$x_{k+l}$ to $\barx_{k+l}$, requiring $X_{k+l-1}$ to take the value
$x_{k+l-1}$ while $o'[X_{k+l-1}] = \barx_{k+l-1}$.  Therefore, the first
flip of $X_{k+l}$ may be performed only after the first flip of
$X_{k+l-1}$, and therefore, before the flip number $k+2-l$ of $X_{k+l}$, the
variable $X_{k+l-1}$ will have to change its value at least $k+2-l$
times. Now, since $k+l$ is even, then so is $k+2-l$. Thus, after $k+2-l$
flips, the variable $X_{k+l-1}$ will be assigned the value $o'[X_{k+l-1}] =
\barx_{k+l-1}$.  However, $o[X_{k+l-1}] = x_{k+l-1}$, thus $X_{k+l-1}$
will have to change its value at least one more time. 

The proof for the case of $k+l$ odd is similar: The first flip of
$X_{k+l}$ is from $\barx_{k+l}$ to $x_{k+l}$, requiring $X_{k+l-1}$ to
take the value $\barx_{k+l-1}$ while $o'[X_{k+l-1}] = x_{k+l-1}$.
Therefore, before the flip number $k+2-l$ of $X_{k+l}$, the
variable $X_{k+l-1}$ will have to change its value at least $k+2-l$
times. Now, since $k+l$ is odd, then so is $k+2-l$. Thus, after $k+2-l$
flips, the variable $X_{k+l-1}$ will be assigned to the value $\barx_{k+l-1}$.
However, $o[X_{k+l-1}] = o'[X_{k+l-1}] = x_{k+l-1}$, thus $X_{k+l-1}$
will have to change its value at least one more time. Hence, we proved
that, for $i=l-1$, $X_{k+i}$ has to change its value at least $k+2-i$
(= $k+3-l$) times.

\ \\
\noindent (2) The proof of the second claim is by induction on $j$.  First, we show
that $X_k$ must change its value at least $k$ times. From the first
claim we have that $X_{k+1}$ changes its value at least $k+1$ times.
Therefore, since every pair of successive flips of $X_{k+1}$ requires
different values of $X_{k}$, the variable $X_{k}$ must change its
value at least $k$ times.

Now, we assume the induction hypothesis that, for $l \leq j \leq k$, every
variable $X_{j}$ must change its value at least $j$ times, and
prove the claim for $X_{l-1}$. Again, since every pair of successive
flips of $X_{l}$ requires different values of $X_{l-1}$, the variable
$X_{l-1}$ must change its value at least $l-1$ times.
\end{proof}




\begin{atheorem}{t:bh-nphard}
  {\em Dominance testing for binary-valued, directed-path singly connected CP-nets is
    {\sc np}-complete.}
\end{atheorem}

\begin{proof}
  \label{page-t:bh-nphard}
  First we show the membership in {\sc np}. Given a dominance query $\Pi =
  \llbracket N \models o \succ o'\rrbracket$, let $\MinFS (\Pi )$ denote the
  size of a minimal (= shortest) improving flipping sequence from $o'$ to $o$.
  Using the $\MaxReq$ property of the variables, the following upper bound for
  $\MinFS (\Pi )$ is straightforward from the Lemma~\ref{l1}:
  \begin{equation}
    \label{eq:ubound}
    \MinFS (\Pi )  \leq \sum_{X_i\in \bV} \MaxReq (X_i) \leq n^2
  \end{equation}
  Thus, if we guess a minimal improving flipping sequence for a given
  solvable problem, we can verify it in low order polynomial time.
  
  The proof of hardness is by reduction from {\sc
    3-sat}, i.e., problem of finding a satisfying assignment for a
  propositional formula in conjunctive normal form in which each
  conjunct (clause) has at most three literals.
  
  Let $\cF = c_1\wedge\ldots\wedge c_n$
  be a {\sc 3-sat} propositional formula, and 
  ${x_1,\ldots ,x_m}$ be the variables used in $\cF$.
  Our equivalent problem can be constructed as follows:
  \begin{itemize}
  \item $\bV = \{V_1,\bar{V}_1,\ldots ,V_m,\bar{V}_m\}\cup\{C_1,\ldots
    ,C_n\}$, where for $1\leq i \leq 2m+n$, the domain $\cD(X_i) =
    \{f,t\}$ ($f$ and $t$ stand for {\em false} and {\em true}, respectively).
  \item $Pa (V_i) = Pa (\bar{V}_i) = \emptyset$
  \item $Pa (C_i) =
    \{V_{i_1},\bar{V}_{i_1},V_{i_2},\bar{V}_{i_2},V_{i_3},\bar{V}_{i_3}\}$,
    where $x_{i_1},x_{i_2}$, and $x_{i_3}$ are the variables that
    participate in the $i$th clause of $\cF$.
  \item Outcome $o'$ assigns $f$ to all variables in $\bV$.
  \item Outcome $o$ assigns $t$ to all variables in $\bV$.
  \end{itemize}
  
  For any variable $V_i$ or $\bar{V}_i$, $1\leq i\leq m$, the value
  $t$ is (unconditionally) preferred to the value $f$. In turn, for
  $1\leq i\leq n$, the value $t$ is preferred to the value $f$
  for the variable $C_i$ if there exist a $j$, $1\leq j\leq 3$, such
  that:
  \begin{enumerate}
  \item $V_{i_j} \neq \bar{V}_{i_j}$
  \item if the literal $x_{i_j}$ (and not $\bar{x}_{i_j}$) belongs to
    the clause $c_i$ then $V_{i_j} = t$, otherwise $\bar{V}_{i_j} = t$
  \end{enumerate}
  For all other assignments to $\Pa(C_i)$, the value $f$ is 
  preferred to the value $t$ for the variable $C_i$.
  
  The constructed inference problem has a directed-path singly connected,
  binary-valued CP-net in which for $1 \leq i \leq n$, $|\Pa(X_i)| \leq 6$. Let us
  show that an improving flipping sequence from $o'$ to $o$ exists if and only
  if a satisfying assignment for $\cF$ can be found.
  
  $\Leftarrow$ Given a satisfying assignment $\phi$, the improving
  flipping sequence is as follows: First, for $1 \leq j \leq m$, if
  $x_j = t$ in $\phi$, then flip the value of the variable $V_j$ from
  $f$ to $t$.  Otherwise, if $x_j = f$ in $\phi$, then flip the value
  of the variable $\bar{V}_j$ from $f$ to $t$. The actual ordering of
  these flips is irrelevant since these variables are mutually
  independent.  Then, for $1 \leq i \leq n$, flip the value of
  $C_i$ from $f$ to $t$.
  % Such a value flip 
%   Such an ability is ensured from the construction of the
%   $C_i$'s CPT and the fact that $\phi$ is satisfying.
  Here also,
  the ordering of these flips is not significant. Finally, flip the
  values of all variables $V_j$ and $\bar{V}_j$ that still have the
  value $f$.
  
  $\Rightarrow$ Let $\cS$ be an improving flipping sequence from $o'$
  to $o$.  If the value of a variable $C_i$ is flipped on $\cS$ while
  variables $V_j,\bar{V}_j \in \Pa(C_i)$ had the values $t,f$, respectively,
  then variable $x_j$ is set to true
  in $\phi$.  Otherwise, if $C_i$ is flipped on $\cS$ while
  variables $V_j,\bar{V}_j \in \Pa(C_i)$ had the values $f,t$, respectively,
  then variable $x_j$ is set to
  false in $\phi$. Existence of such a $j$ is ensured by the construction
  of $CPT(C_i)$.
  
  In turn, for $1 \leq j \leq m$, neither $V_j$ nor $\bar{V}_j$ can
  achieve the value $f$ after achieving the value $t$. Hence, if there
  is an outcome $o_1\in\cS$ such that $\{V_j = t,\bar{V}_j = f\} \in
  o_1$, then there will be no outcome $o_2\in\cS$ such that $\{V_j =
  f,\bar{V}_j = t\} \in o_2$, and vice versa. This shows that the value of each
  variable $C_i$ is flipped on $\cS$ from $f$ to $t$ in a context consistent
  with $\phi$. Therefore, for each close $c_i$, there is a literal
  $l_{i_j} \in c_i$, $1 \leq j \leq 3$, such that $l_{i_j} \in \phi$.
\end{proof}


\begin{atheorem}{l:delta}
  {\em Dominance testing for binary-valued, max-$\delta$-connected CP-nets,
    where $\delta$ is polynomially bounded in the size of the CP-net, is {\sc
      np}-complete.}
\end{atheorem}

\begin{proof}
  \label{page-l:delta}
  We prove this theorem by showing that, for {\em any} acyclic, binary-valued
  CP-net $\cN$, and for any variable $X_i \in \cN$, we have:
  \begin{equation}
    \label{eq:rho1}
    \MaxReq (X_i) \leq 1\; +\; \sum_{j=i+1}^n \rho(X_i, X_j)
  \end{equation}
  where $\rho(X_i, X_j)$ denotes the total number of different, not
  necessary disjoint, paths from $X_i$ to $X_j$. For simplicity of
  presentation, we assume that the variables $\{X_1,\ldots,X_n\}$ of
  $\cN$ are numbered according to a topological order induced by the
  graph of $\cN$, and rewrite Eq.~\ref{eq:rho1} into:
  \begin{equation}
    \label{eq:rho}
    \MaxReq (X_i) \leq 1\; +\; \sum_{j=i+1}^n \rho(X_i, X_j)
  \end{equation}
% given a dominance testing problem $\Pi = \langle \cN, o,
% o'\rangle$ where $\cN$ is {\em any} acyclic, binary-valued CP-net, if
% there exists an improving flipping sequence from $o'$ to $o$ then, for $1
% \leq i \leq n$, where $n=|\bV|$, we have:


The proof is by induction on $i$. For $i = n$ it is obvious that
$\MaxReq (X_n) \leq 1$, since $X_n$ is a leaf node in $\cN$. Now we
assume that the lemma holds for any $i>k$, and prove it for $i=k$.
Without loss of generality, assume that there exist at least one
variable $X_j$ such that $X_k \in \Pa(X_j)$.  Otherwise, we simply have
that $\MaxReq(X_k) \leq 1$.

Denote by $\sons (X_k)$ the immediate successors of $X_k$ in $\cN$,
i.e.\ $X_{i_k} \in \sons (X_k)$ iff $X_k \in \Pa(X_{i_k})$. The proof
is straightforward:
\begin{eqnarray*}
%    \MaxReq (v_k) & \stackrel{Eq.~\ref{eq:must}}{\leq} &
  \MaxReq (X_k) & \stackrel{Lemma~\ref{l0}}{\leq} &
  1\ +\ \sum_{X_{i_k}\in\lsons (X_k)} \MaxReq (X_{i_k}) \leq \\
  &\stackrel{I.H.}{\leq} &
  1 + |\sons (X_k)| + \sum_{X_{i_k}\in\lsons (X_k)}{\sum_{\hspace{0.3cm}j=i_k+1}^{n}{\rho(X_{i_k},X_j)}} =\\
  & = & 1 + \sum_{j=k+1}^n \rho(X_k, X_j)
\end{eqnarray*}
Now, if a binary-valued CP-net is max-$\delta$-connected, and the variables
of a given problem $\Pi$ are considered in a topological ordering
induced by $\cN$, then from Eq.~\ref{eq:rho} it follows that, for any
variable $X_i \in \cN$, we have:
\begin{equation}
  \label{e:delta2}
  \MaxReq (X_i) \leq \delta n + 1
\end{equation}
Let $\MinFS (\Pi )$ denote the size of a minimal (= shortest)
improving flipping sequence for $\Pi$. From Eq.~\ref{e:delta2} follows
that $\MinFS (\Pi ) \leq \delta n^2+n$.  Hence, if $\delta$ is
polynomially bounded in the size of $\Pi$, then we can guess and
verify a minimal improving flipping sequence for $\Pi$ in polynomial
time, and thus this class of dominance testing queries is in {\sc np}.
\end{proof}









\begin{atheorem}{t:mv-dominance}
  {\em Flipping sequence search over multi-valued CP-nets with partially
    specified preferences is harder than {\sc np}.}
\end{atheorem}

\begin{proof}
  \label{page-t:mv-dominance}
  The proof is by example of a dominance query over a multi-valued,
  chain CP-net with partially specified preferences, for which the
  minimal flipping sequence is exponentially long.

Consider the following CP-net $\cN$ defined over three-valued
variables $\{X_1,\ldots,X_n\}$, where $n = 2k+1$ for some $k\in{\Bbb
  N}$.  The domain of each variable $X_i$ is
$\cD(X_i)=\{x_i,\barx_i,\bbarx_i\}$.  For $1 \leq i \leq n$, $\Pa(X_i)
= \{X_{i-1}\}$, thus $\cN$ forms a directed chain.  The CPTs capturing
the preferences over the values of $\{X_1,\ldots,X_n\}$ are shown in
Figure~\ref{table:mv1}.


\begin{figure}[ht]
\begin{center}
  \begin{tabular}{c}
    \begin{tabular}{|c|c|}
      \hline
      Variable & CPT\\
      \hline
      \hline
      $i = 1$ & $x_i \succ \barx_i \succ \bbarx_i$\\
      \hline
      $1 < i \leq k+1$ & 
      \begin{minipage}{2in}
        \begin{eqnarray*}
          x_{i-1} &:& x_i \succ \barx_i \succ \bbarx_i\\
          \barx_{i-1} &:& \bbarx_i \succ \barx_i \succ x_i\\
          \bbarx_{i-1} &:& x_i \succ \barx_i \succ \bbarx_i\\
        \end{eqnarray*}
      \end{minipage}\\
      \hline
      $k+1 < i \leq n$ & 
      \begin{minipage}{2in}
        \begin{eqnarray*}
          x_{i-1}  &:& \sset{\barx_i \succ x_i\\
            \barx_i \succ \bbarx_i}\\
          \bbarx_{i-1} &:& \sset{x_i \succ \barx_i\\
            \bbarx_i \succ \barx_i}\\
        \end{eqnarray*}
      \end{minipage}\\
      \hline
    \end{tabular}
  \end{tabular}
\end{center}
\caption{}
% \caption{Illustration for the proof of Theorem~\ref{t:tree}:
%   (a) CPTs for $n$ variables; (b) $o$ and $o'$ for $k=2$; and (c) flipping
%   sequence for $k=2$.}
\label{table:mv1}
\end{figure}


Now consider the dominance testing query $\llbracket N \models o \succ o'
\rrbracket$, where, for $1\leq i\leq n$, $o[X_i] = x_i$ and
$o'[X_i]=\bbarx_i$.  Let the sequence $\{a_i\}$ be defined as:
\begin{equation}
 \label{eq:seq-mv}
a_i =
  \begin{cases}
    2, & i=1\\
    2a_{i-1} + 2, & i \geq 2
  \end{cases}
\end{equation}
The length of a minimal flipping sequence from $o'$ to $o$ as above
is greater than:
\[
 \sum_{i=1}^k{a_i} > 2^{\frac{n}{2}}
\]
% \[
%  2\sum_{i=1}^k{a_i} \;+\; (a_{k} + 1) > 2^{\frac{n}{2}}
% \]
\begin{figure}[ht]
\begin{center}
\begin{minipage}{5in}
  {\footnotesize
%    \def\objectsizestyle{\scriptstyle}
    \xymatrix{
      *++[o]=<1.5pc>[F]{X_1} \ar[d] & \bbarx_1 \ar[r]^{10} & \barx_1 \ar[r]^{18} & x_1\\
      *++[o]=<1.5pc>[F]{X_2} \ar[d] & \bbarx_2 \ar[r]^{3} & \barx_2 \ar[r]^{7}
                            & x_2 \ar[r]^{11} & \barx_2 \ar[r]^{15}
                            & \bbarx_2 \ar[r]^{19} & \barx_2 \ar[r]^{22} & x_2\\
      *++[o]=<1.5pc>[F]{X_3} \ar[d] & \bbarx_3 \ar[r]^{1} & x_3 \ar[r]^{4}
                            & \bbarx_3 \ar[r]^{8} & x_3 \ar[r]^{12}
                            & \bbarx_3 \ar[r]^{16} & x_3 \ar[r]^{20}
                            & \bbarx_3 \ar[r]^{23} & x_3\\
      *++[o]=<1.5pc>[F]{X_4} \ar[d] & \bbarx_4 \ar[r]^{2} & \barx_4 \ar[r]^{5}
                            & x_4 \ar[r]^{9} & \barx_4 \ar[r]^{13} 
                            & \bbarx_4 \ar[r]^{17} & \barx_4 \ar[r]^{21} & x_4\\
      *++[o]=<1.5pc>[F]{X_5}        & \bbarx_5 \ar[r]^{6} & \barx_5 \ar[r]^{14} & x_5\\
      }
    }
\end{minipage}
\end{center}
\caption{}
% \caption{Illustration for the proof of Theorem~\ref{t:tree}:
%   (a) CPTs for $n$ variables; (b) $o$ and $o'$ for $k=2$; and (c) flipping
%   sequence for $k=2$.}
\label{table:mv2}
\end{figure}

Figure~\ref{table:mv2} illustrates the corresponding flipping sequence
for $k=2$ (i.e., $n=5$), where each variable $X_i$ is annotated with
its value flips along the flipping sequence: Arrows between the values
stand for the value flips, and the sequential numbers of the flips
along the flipping sequence appear as the arrow labels.

Now we prove that the size of the minimal flipping sequence for the
dominance query as above is greater than $\sum_{i=1}^k{a_i}$. We
divide the proof into four steps, where the first step shows the
necessity of $\sum_{i=1}^k{a_i}$ flips for any flipping sequence from
$o'$ to $o$ as above, and the subsequent three steps prove the
existence of a flipping sequence from $o'$ to $o$.
Recall that, since $N$ forms a chain, for $1 < i \leq n$, 
$X_{i-1}$ is the only parent of $X_{i}$, thus the value flips of $X_{i}$
depend only on the value of $X_{i-1}$.

The steps of the
proof are as follows:
\begin{enumerate}[(1)]
\item \label{step:mv1} On a flipping sequence from $o'$ to $o$, for $2 \geq i \leq
  k+1$, every variable $X_{k+i}$ (last $k$ variables) {\em must}
  change its value at least $a_{k+2-i}$ times, such that if
  $f_1^{k+i},\ldots,f_{a_{k+2-i}}^{k+i}$ is the corresponding
  sequence of flips of $X_i$, then, for $1 \leq j \leq a_{k+2-i}$, we
  have:
  \begin{equation}
    \label{eq:mv1}
    f_j^{k+i} =
      \begin{cases}
        \bbarx_i \rightarrow \barx_i,  & j=4k+1\\
        \barx_i  \rightarrow  x_i,     & j=4k+2\\
        x_i      \rightarrow \barx_i,  & j=4k+3\\
        \barx_i  \rightarrow \bbarx_i, & j=4k
      \end{cases}
      \;\;\;\;\;\;  \;\;\;\;\;\;k\in\nat
  \end{equation}
  
\item \label{step:mv2} For $1 \leq i \leq k$, every variable $X_{i}$ (first $k$
  variables) {\em can} change its value $a_i$ times, such that if
  $f_1^{i},\ldots,f_{a_{i}}^{i}$ is the corresponding sequence of
  flips of $X_i$, then, for $1 \leq j \leq a_{i}$, every flip $f_j^i$
  is consistent with Eq.~\ref{eq:mv1}.
  
\item \label{step:mv3} Given the sequence of flips for $X_k$ as in
  (\ref{step:mv2}), the variable $X_{k+1}$ {\em can} change its value
  $a_k+1$ times, such that if $f_1^{k+1},\ldots,f_{a_{k}+1}^{k+1}$ is
  the corresponding sequence of flips of $X_{k+1}$, then, for $1 \leq
  j \leq a_k+1$, we have:
  \begin{equation}
    \label{eq:mv2}
    f_j^{k+1} =
      \begin{cases}
        \bbarx_{k+1} \rightarrow x_{k+1},      & j=2k+1\\
        x_{k+1}      \rightarrow \bbarx_{k+1}, & j=2k
      \end{cases}
      \;\;\;\;\;\; k\in\nat
  \end{equation}

\item \label{step:mv4} The sequence of flips for $X_{k+2}$ as in (\ref{step:mv1})
  is feasible given the sequence of flips for $X_{k+1}$ as in (\ref{step:mv3}).
\end{enumerate}

\ \\
\noindent \underline{Step (1):} The proof is by induction on $i$. For $i=k+1$,
the variable $X_{2k+1}$ (i.e., $X_n$) must change its value at least
twice, since no value of $X_{2k}$ induces $\bbarx_{2k+1} \prec
x_{2k+1}$. The only way to change the value of $X_{2k+1}$ from
$\bbarx_{2k+1}$ to $x_{2k+1}$ is to flip $X_{2k+1}$ first from
$\bbarx_{2k+1}$ to $\barx_{2k+1}$, and then from $\barx_{2k+1}$ to
$x_{2k+1}$. Note that these flips are consistent with Eq.~\ref{eq:mv1}
and $a_{k+2-(k+1)}=a_1=2$, thus we established the induction base.

Now, we assume that the induction hypothesis that, for $2 < l \leq i \leq k+1$,
every variable $X_i$ must change its value at least $a_{k+2-i}$ times according to
Eq.~\ref{eq:mv1}, and prove this claim for $X_{k+l-1}$.

Consider the sequence of flips of $X_{k+l}$ that we assumed to be necessary, i.e.,
$f_1^{k+l},\ldots,f_{a_{k+2-l}}^{k+l}$. According to $CPT(X_{k+l})$ we have that:
\begin{enumerate}[(i)]
  \item every pair of successive flips of $X_{k+l}$ require different values
    of $X_{k+l-1}$,
  \item the required values of $X_{k+l-1}$ are
    $\{\bbarx_{k+l-1},x_{k+l-1}\}$, and
  \item the first flip of $X_{k+1}$ (from $\bbarx_{k+l}$ to $\barx_{k+l}$) requires
    $X_{k+l-1}=x_{k+l-1}$, while $o'[X_{k+l-1}] = \bbarx_{k+l-1}$.
\end{enumerate}
Therefore, $X_{k+l-1}$ must perform $a_{k+2-l}$ value changes from
$\bbarx_{k+l-1}$ to $x_{k+l-1}$ and back, in order to support the
required value changes of $X_{k+l}$. In addition, after supporting the
value changes of $X_{k+l}$, the variable $X_{k+l-1}$ must perform
another value change from $\bbarx_{k+l-1}$ to $x_{k+l-1}$, since
$a_{k+2-l}$ is even (see Eq.~\ref{eq:seq-mv}), while $o'[X_{k+l-1}] =
\bbarx_{k+l-1}$ and $o[X_{k+l-1}] = x_{k+l-1}$. Finally, according to $CPT(X_{k+l-1})$,
every value change of $X_{k+l-1}$ from $\bbarx_{k+l-1}$ to $x_{k+l-1}$
and from $x_{k+l-1}$ to $\bbarx_{k+l-1}$ consists of two flips: from the initial
value to $\barx_{k+l-1}$, and from $\barx_{k+l-1}$ to the target value.
Thus the proved that $X_{k+l-1}$ must perform at least $2(a_{k+2-l}+1) = a_{k+3-l}$
value changes, and that these value changes are consistent with Eq.~\ref{eq:mv1}.

\ \\
\noindent \underline{Step (2):} The proof is by induction on $i$. For $X_1$ the proof
is straightforward, since $o'[X_1] = \bbarx_1$, $o[X_1] = x_1$, and
$CPT(X_1)$ allows us to flip the value of $X_1$ from $\bbarx_1$ to
$\barx_1$, and then from $\barx_1$ to $x_1$.

Now we assume the induction hypothesis that, for $1 \leq i < k$, every
variable $X_i$ can change its value $a_i$ times according to
Eq.~\ref{eq:mv1}, and prove the claim for $X_{i+1}$. The proof is
apparent from $CPT(X_{i+1})$, the outcomes $o$ and $o'$ in query, and
the induction hypothesis. For every value achieved by $X_i$ along its
sequence of $a_i$ flips (including the initial value
$o'[X_i]=\bbarx_i$), $X_{i+1}$ can flip its value twice: Given
$X_i=\bbarx_i$ or $X_i=x_i$, we can flip the value of $X_{i+1}$ first
from $\bbarx_{i+1}$ to $\barx_{i+1}$, and then from $\barx_{i+1}$ to
$x_{i+1}$. Alternatively, given $X_i=\barx_i$, we can flip the value
of $X_{i+1}$ from $x_{i+1}$ to $\barx_{i+1}$, and then from
$\barx_{i+1}$ to $\bbarx_{i+1}$. Therefore, $X_{i+1}$ can flip its
value $2(a_i+1) = a_{i+1}$ times, and it is easy to see that these value flips
of $X_{i+1}$ are consistent with Eq.~\ref{eq:mv1}.


\ \\
\noindent \underline{Step (3):} Given the sequence of $a_k$ flips
$f_1^k,\ldots,f_{a_k}^k$ of $X_k$ as in Eq.~\ref{eq:mv1}, let
$\myvalue (f_j^k) \in \Dom(X_k)$ be the value of $X_k$ achieved by the
flip $f_j^k$, for $1 \leq j \leq a_k$. $CPT(X_{k+1})$ entails that,
for any triple of values of $X_k$ achieved by a triple of successive
flips $f_{j}^k,f_{j+1}^k,f_{j+2}^k$, $1 \leq j \leq a_k-2$, we have either:
\begin{eqnarray*}
  \myvalue (f_j^k)     \;\; & : & \;\; x_{k+1} \succ \bbarx_{k+1}\\
  \myvalue (f_{j+1}^k) \;\; & : & \;\; \bbarx_{k+1} \succ x_{k+1} \\
  \myvalue (f_{j+2}^k) \;\; & : & \;\; x_{k+1} \succ \bbarx_{k+1}
\end{eqnarray*}
or
\begin{eqnarray*}
  \myvalue (f_j^k)     \;\; & : & \;\; \bbarx_{k+1} \succ x_{k+1}\\
  \myvalue (f_{j+1}^k) \;\; & : & \;\; x_{k+1} \succ \bbarx_{k+1} \\
  \myvalue (f_{j+2}^k) \;\; & : & \;\; \bbarx_{k+1} \succ x_{k+1}
\end{eqnarray*}
In addition, we know that:
\[
  o'[X_k] = \bbarx_k \;\; : \;\; x_{k+1} \succ \bbarx_{k+1}
\]
and
\[
  \myvalue (f_1^k) = \barx_k \;\; : \;\; \bbarx_{k+1} \succ x_{k+1}
\]
The above entails that $X_{k+1}$ can change its value $a_k+1$ times
according to Eq.~\ref{eq:mv2}.

\ \\
\noindent \underline{Step (4):} The proof of this subclaim is straightforward
from $CPT(X_{k+2})$. Given the sequence of $X_{k+2}$ value flips
$f_1^{k+2},\ldots,f_{a_k}^{k+2}$ as in Eq.~\ref{eq:mv1}, observe that,
for $1 \leq j \leq a_k$, if $j=2k+1$ for some $k \in \nat$, then
$f_j^{k+2}$ can be supported by the value $x_{k+1}$ of $X_{k+1}$,
otherwise, if $j=2k$, $k \in \nat$, then $f_j^{k+2}$ can be supported
by the value $\bbarx_{k+1}$ of $X_{k+1}$. Now, since for $1 \leq l \leq a_k+1$,
\[
  \myvalue (f_l^{k+1}) =
    \begin{cases}
      x_{k+1},      & l=2m+1\\
      \bbarx_{k+1}, & l=2m
    \end{cases}
    \;\;\;\;\;\; m\in\nat
\]
it is apparent that the sequence of $a_k$ value flips of $X_{k+2}$ as
in Eq.~\ref{eq:mv1} is feasible given the sequence of $a_k + 1$ value
flips\footnote{In fact, only $a_k$ value flips of $X_{k+1}$ are used
  in order to perform $a_k$ value flips of $X_{k+2}$ as required. The
  last flip of $X_{k+1}$ is used in order to achieve the value
  $o[X_{k+1}]$ for $X_{k+1}$ after supporting $X_{k+2}$.} of $X_{k+1}$ as
in Eq.~\ref{eq:mv2}.


\ \\
The above entails that $N \models o \succ o'$, and that the size of
the minimal flipping sequence from $o'$ to $o$ in $N$ is
$\sum_{i=1}^k{a_i}$, which is greater than $2^{\frac{n}{2}}$.
In fact, it can be show that the value flips for $X_1,\ldots, X_{k+1}$, constructed
in steps~(\ref{step:mv2})-(\ref{step:mv3}), are the part of the minimal flipping sequence
from $o'$ to $o$, thus the length of this sequence is greater than:
\[
2\sum_{i=1}^k{a_i} \;+\; (a_{k} + 1) 
\]
However, the result achieved in step~(\ref{step:mv1}) already proves
our claim that there exist dominance queries on multi-valued CP-nets with
partially specified preferences, for which there are exponentially
sized minimal flipping sequences.
\end{proof}


\bibliographystyle{theapa} \bibliography{long,standard,new}



\end{document}

