\documentstyle[12pt,twoside]{report}
\newcommand{\mf}[2]{#2}
\setlength{\unitlength}{1mm}
\linethickness{.4mm}
\renewcommand{\topfraction}{.8}
\renewcommand{\textfraction}{.15}
\raggedbottom

\begin{document}

\begin{titlepage}
\begin{center}
{\bf \LARGE Reasoning About Preference Models}\\[2cm]
{\small by}\\[.3cm]
Michael Paul Wellman\\[4cm]
May 1985

\vfill
\copyright\ Massachusetts Institute of Technology 1985 \\[4cm]
This research was supported (in part) by the National Institutes of
Health Grant No. NIH-5-R24-RR01320-02.
\end{center}
\end{titlepage}

\pagestyle{plain}
\pagenumbering{roman}

\addcontentsline{toc}{chapter}{Abstract}
\begin{center}
{\bf \Large Reasoning About Preference Models}\\
\bigskip
{\small by}

Michael Paul Wellman \\ [.3cm]

This report is a modified version of a thesis 
submitted to the Department of Electrical Engineering and Computer Science
on May 21, 1985 in partial fulfillment of the requirements for the
Degree of Master of Science
\end{center}

\begin{flushleft}
\bf Abstract
\end{flushleft}

Programs that make decisions need mechanisms for representing and reasoning
about the desirability of the
possible consequences of their choices.  This work is an exploration of
{\it preference models} based on utility theory.  The framework presented
is distinguished by a {\it qualitative} view of preferences and a
{\it knowledge-based} approach to the application of utility theory.  The 
design for a comprehensive preference modeler is implemented in part by the
{\it U\/}tility {\it R\/}easoning {\it P\/}ackage ({\sc urp}), a collection
of facilities for constructing and analyzing preference models.

Qualitative mathematical reasoning techniques are employed to develop
{\it partial} specifications of single-attribute utility functions from
qualitative preference assertions.  Functions are described in terms of
gross behaviors, symbolic forms, and parametric constraints.  Appropriate
dominance-testing algorithms
are chosen from a knowledge base of stochastic dominance routines based
on qualitative properties of the utility function.  {\sc Urp} constructs
multiattribute utility functions from a set
of independence conditions by applying proof rules from a knowledge base
containing the important decomposition theorems from the literature.
Proof rules describe the
logical relations among independence conditions and functional forms.
Hierarchical decompositions are structured automatically.

Flexible model construction provides the potential for interpreting preference
choices under a procedure
that does not depend on the underlying utility model.  Model-independent
interpretation enables assessment under a wide range of descriptive
theories of preference choice.  Domain-specific preference knowledge is
incorporated in {\sc urp} by tying domain concepts to the
modeler's {\it technical vocabulary}.
Development of a health preference knowledge base illustrates how
preference modeling could be included in a knowledge-based system for a
particular application.


\begin{flushleft}
{\bf Thesis Advisor:} Peter Szolovits\\
{\bf Title:}  Associate Professor of Computer Science \\[.2cm]
{\bf Keywords:} utility theory, decision making, mathematical modeling,
preferences, qualitative reasoning, knowledge-based systems,
multiattribute utility, stochastic dominance, utility assessment, medical
decision making
\end{flushleft}

\clearpage

\addcontentsline{toc}{chapter}{Acknowledgements}
\begin{center}
{\bf \LARGE Acknowledgements} \\[1cm]
\end{center}

\noindent
Alvin Drake and Ralph Keeney for some early advice and
encouragement.

\vspace{.2cm} \noindent
David Bell for much of the same and for looking over part of the
knowledge base.

\vspace{.2cm} \noindent
Members, past and present, of the Division of Clinical Decision Making
at Tufts-New England Medical Center for two years of lively case
discussions and for putting up with my medical ignorance.  Special
thanks to Van Dunn for the medical example, and to Jim Hollenberg for
helping me select and set up the case as well as for many fruitful
discussions about AI and Decision Analysis.  And to Stephen Pauker for
general tutelage, and for keeping me somewhat closer to the real world.

\vspace{.2cm} \noindent
Kathe Unrath for eliminating some of the stylistic monstrosities from
this document.

\vspace{.2cm} \noindent
The members of the Clinical Decision Making Group at MIT for lots of
good discussions, stimulating ideas, and in general for providing a nice
place to work.  Particular thanks to Zak Kohane for many heated
discussions about this project and for helpful suggestions on several drafts,
to Elisha
Sacks for draft-reading and for helping me to get the {\sc qm} package to do
what I needed, and to Robert Kunstaetter for tolerating my naive medical
questions and some of my more outrageous arguments.

\vspace{.2cm} \noindent
Peter Szolovits, my advisor, for continued support and guidance.

\clearpage

\pagestyle{headings}
\tableofcontents
\newpage
\addcontentsline{toc}{chapter}{List of Figures}
\listoffigures \vfill
\addcontentsline{toc}{chapter}{List of Tables}
\listoftables \vfill
\newpage

\renewcommand{\baselinestretch}{1.1}
\large
\normalsize

\pagenumbering{arabic}

\chapter{Introduction}

The work described in this thesis is an investigation of an approach
toward representing and reasoning about preferences in a machine.  These
preferences ``belong'' to some agent (person, institution, society)
called the {\it decision maker}.  We wish to encode them in a
computer program so that it may be more effective in helping the agent
make decisions, or even in making decisions for the agent by proxy.

Decision scientists have long been concerned with formal models of preference,
and have assembled over the years an impressive body of theory which bears
directly on the enterprise of representing preferences in computers.  Attempts
to employ these models in decision-making computer programs, however, have met
with only limited success, mainly because the implementations have incorporated
a highly restricted view of the formal preference theories.  Taking such a view
is difficult to avoid using conventional programming strategies.

This project arose out of the observation that utility theory (like
many mathematical modeling disciplines) is tremendously richer and remarkably
more flexible than reflected in any program performing utility analysis.  This
observation, together with advances in knowledge-based programming technology
and qualitative reasoning methods from artificial intelligence, suggests the
approach related in this thesis.

\section{Preferences}

People make decisions to influence the course of events in ways that
they deem desirable.  Different actions make the various possible outcomes more
or less
likely to obtain; choosing among available acts is an exercise in selecting
probable futures.  It seems important, then, that computer programs that
make decisions or help humans to do so should have some means to
reason about the desirability of the possible consequences of these decisions.

Mainstream AI research---while enormously concerned with representing
beliefs and states of knowledge---has for all practical purposes ignored
the issue of preferences.  Note that goals as employed by AI planning programs
do not function as expressions of preference; at the very best they can be said
to name the most desired outcome.  More often, goals are used to describe
intentions or desired
reasoning states, which are nothing at all like desired states of the
world.\footnote{Doyle~\cite{Doyl80} discusses the importance of
distinguishing between desires and intentions in a decision making program.}
Furthermore, in most real decision-making or planning situations it is
necessary to consider possible outcomes other than the one most preferred.
The program must be able to compare the desirability of various
partially satisfied or uncertain goals, which may not be related to the
absolute goal by any identifiable distance metric.

\section{Preference Models}

This work is an exploration of the use of {\it preference models} as a basis
for reasoning about desires in decision making.  Let us define a {\it prospect}
to be a probability distribution over consequences, or {\it outcomes}.  The
underlying assumption of preference modeling is
that there exists a {\it preference relation}, denoted by $\succ$, which orders
the set of prospects.  A preference model is a
structure used to represent this order relation.

Preference models can be used to answer questions of the form ``Is $x$
preferred to $y$?'' where $x$ and $y$ are prospects relevant to the
decision being considered.  The decidability of such questions depends on
the degree to which the preference model is specified.  In general, a
preference model will characterize only a subset of the true preference
relation it represents.
Thus, any partial description of a preference order may be termed a preference
model.

The ultimate goal of this effort is to develop a representation for preference
models that will accommodate arbitrary amounts and types of information
about the preference relation, and a reasoning capacity that will enable us to
reconstruct as much as possible of the relation from whatever information is
available.  A formal characterization of the sorts of information
that may be incorporated in preference models and the language used to describe
it may be called a {\it preference calculus}.  While I cannot claim to provide
a sufficiently formal or principled development, this work may be viewed
as a step toward the definition of a useful preference calculus.

The next major step (which requires a leap of faith, since I do not intend to
provide detailed justification here) is that the foundations for this
preference calculus are to be found in utility theory.  A fundamental result of
this theory is that, given a few appealing axioms,\footnote{By appealing, I
mean that they generally express properties that one would like to conform to
in decision making.  This is not to say
that these axioms are totally accepted.  However, it is not my intention
to enter the debate at this point.  A particularly lucid axiomatic development
of expected utility can be found in Savage's important work~\cite{Sava72}.
Alternative axiomatizations are provided by Fishburn~\cite{Fish82}.  The
original existence proof is due to von Neumann and Morganstern~\cite{von}.}
there exists a {\it utility function} which maps prospects to real
numbers (called {\it utilities}\/) in such a way that the utility of any
prospect is equal to the sum of
the utility of each certain outcome weighted by its probability in that
prospect.  Utilities rank the prospects by preference; $u(p_1) > u(p_2)$ if and
only if $p_1 \succ p_2$.  If we base
our preference model on the notion of a utility function, we can
exploit a large body of results from utility theory, and more general
analytical techniques from the mathematics of functions.
This thesis is largely an account of some of these possible exploitations.

Formally, a utility function $u$ maps states of the world (outcomes) $x$ in the
{\it outcome space} $X = X_1\times\cdots\times X_n$ to real numbers in
such a way that the optimal decision is the one that maximizes the expected
value of this function.  Often $x$ is expressed as a vector of attributes,
$(x_1,x_2,\ldots,x_n), x_i\in X_i$, where the values of the $x_i$s totally
describe the aspects of the outcome pertinent to the decision.

While a major preference modeling effort is often undertaken for the sake
of the {\it insight} it brings to decision making, I will be primarily
concerned with the use of preference models for the
analysis of a particular decision.\footnote{Although, as will be explained
later, I believe that models created using this methodology offer the potential
for greater insight due to their deep, explicit qualitative
structure.  And there is no reason to believe that any of the insight-yielding
characteristics that are inherent in traditional utility analysis efforts will
not carry over to this methodology.  Unfortunately, I do not know how to prove
an insight theorem.}  For
our purposes, a decision involves a choice among a set of strategies, each of
which is associated with some resulting outcome $x \in X$ (or more generally,
a prospect $p \in P$, where $P$, the {\it decision space} is the
set of simple probability distributions over $X$).  To make the decision, we
must figure out which strategy has the greatest expected utility.

\section{The Basic Approach}

The main features that distinguish the attitude toward utility modeling
developed here from traditional computerized utility modeling are its
qualitative view of preference structures and
its knowledge-based approach to the encoding of utility-theoretic
concepts.  Taken together, these features result in a system which emphasizes
model structuring over model parameterization.  This attitude has been embodied
in a collection of programs and overall framework
for preference modeling called {\sc urp} (for {\it U\/}tility
{\it R\/}easoning {\it P\/}ackage).  The sections immediately below describe
features of the general attitude; descriptions of the actual {\sc urp}
framework and programs make up the remainder of this thesis.

\subsection{Qualitative View of Preferences}

An important novelty of the approach described here is in the qualitative
mechanisms
used to analyze preference structures.  Utility analysis is usually considered
a primarily quantitative\footnote{It is difficult to avoid the confusion
inherent in words like {\it qualitative} and {\it quantitative}.  Naturally,
all mathematical models are composed of relationships among quantities, and in
that sense they are
quantitative.  But it is important to distinguish qualitative
{\it descriptions} of quantities from numeric descriptions.  A symbolic
expression is just one
form of qualitative description.  The term {\it qualitative}
as used here is almost always meant in contrast to {\it numeric}, or more
generally in opposition to excess precision of any sort.} task, and previous
utility modeling aids (basically assessment tools) have reflected
that bias.  I believe that the emphasis on numerical computation has tended to
obscure the more important modeling and analysis issues, just as
implementations of mathematical
models often hide the central qualitative structure of the problems they are
supposed to represent.  Recent work in artificial intelligence (that of
Kuipers~\cite{Kuip84}, Forbus~\cite{Forb}, and Sacks~\cite{Sack85b},
for example) has shown that it is often possible to reason effectively about
the qualitative behaviors of mathematical structures without resorting to
overly precise descriptions.  Such a capability would be enormously useful
for utility analysis, because (as with any kind of psychological measurement)
virtually any numeric data is uncomfortably precise.  A more complete account
of the potential advantages is given in section~\ref{u-per}.

This qualitative view meshes nicely with the notion of a preference model as
a {\it partial} description of a preference order.  The view is supported
by {\sc urp} in its tendency to
focus on propositions about the utility structure rather than on
direct specification of components making up the structure.  Specific methods
contributing to this focus are described below.

\subsection{Knowledge-Based Approach to Utility Theory}

The second major distinction in how {\sc urp} models preferences is that it
relies on utility theory knowledge expressed in a (relatively) declarative
format, rather than compiled into analysis procedures.
Encoding utility-theoretic concepts in explicit knowledge structures 
leads to advantages in flexibility, extensibility, and explainability,
which will be noted as we get into specifics.  For now
I will just mention that the process of building {\sc urp} has resulted in
the collection of a large corpus of
utility-theoretic knowledge, encoded in a uniform representation,
{\it executable} by {\sc urp}'s interpreter.  The creation
of this knowledge base (especially that pertaining to multiattribute
decomposition) may be a worthwhile exercise in its own right.

\section{Model Construction and Analysis}

A high-level view of the {\sc urp} preference modeling framework is depicted in
figure~\ref{h-l-view}.  Given a probabilistic model of the alternative
strategies, the program will produce decisions based on a specification
of preferences.  The probabilistic model is given as $(p_1,\ldots,p_m)$,
where $p_i$, the result of the $i$th strategy, is a prospect in $P$ (that is, a
simple probability distribution over the outcome space, $X$\/).

\begin{figure}[htbp]
\begin{picture}(150,60)
\put(10,33){\shortstack{qualitative \\ assertions}}
\put(28,36){\vector(1,0){7}}
\put(10,21){\shortstack{preference \\ choices}}
\put(28,24){\vector(1,0){7}}
\put(35,20){\framebox(20,20)}
\put(55,30){\vector(1,0){5}}
\put(62,27){\shortstack{preference \\ model}}
\put(80,30){\vector(1,0){5}}
\put(55,47){\shortstack{probabilistic \\ model}}
\put(75,50){\line(1,0){20}}
\put(95,50){\vector(0,-1){10}}
\put(85,20){\framebox(20,20)}
\put(105,30){\vector(1,0){5}}
\put(110,25){\makebox(20,10){decision}}
\put(95,20){\line(0,-1){8}}
\put(95,12){\line(-1,0){50}}
\put(45,12){\vector(0,1){8}}
\put(45,13){\makebox(50,10)[b]{control link}}
\put(30,0){\makebox(40,10)[b]{construction}}
\put(70,0){\makebox(40,10)[b]{analysis}}
\end{picture}
\caption{A high-level view of the program's behavior}\label{h-l-view}
\end{figure}

Preference specifications are in terms of the same basic variables as the
probabilistic model: the attributes $X_1,\ldots,X_n$.  The two main
categories of specifications are qualitative utility assertions and
preference choices.  Qualitative utility assertions are propositions that
refer to preference conditions for attributes or sets of attributes.
Some illustrative examples, stated in English (rather than
{\sc urp}ese\footnote{It will soon be demonstrated that {\sc urp}ese is
closely related to the technical language of utility theory.}), with the
$j$s and $Y$s standing for attributes and attribute sets, respectively:
\begin{itemize}
\item Preference for prospects over attributes in $Y_1$ is independent of the
	fixed value of the rest of the attributes
\item All other things equal, higher levels of (numeric) attribute $j_1$ are
	preferred
\item The attributes in $Y_2$ are complementary
\item The marginal value of equal increments of attribute $j_2$ is
        decreasing with $j_2$
\item An additive form is valid for the utility function over $Y_3$
\end{itemize}
The implications of these assertions on the preference model will be made
clearer below.

Preference choices are assertions similar to those generated by the standard
lottery technique of utility assessment, where the assessor is required to
report preferences in hypothetical choices among simplified prospects.  The
form and use of preference choices is the subject of chapter~\ref{assess-c}.

The output of the first black box of figure~\ref{h-l-view} is a data
structure representing the current
preference model.  The model is a collection of assertions about the utility
structure, containing some combination of functional constraints, algebraic forms, parametric constraints, and other qualitative properties.  Because the
model is the central object of reasoning activity, it
is useful to separate the process into two components: {\it model construction}
and {\it model analysis}.  This is a natural distinction, because the two
activities use very different types of knowledge and inference mechanisms.  The
processes are not totally independent, of course, since we construct models
in the first place for purposes of analysis.  Therefore, there must be a
control link tying the results of the analysis to the goals of the
construction.

\subsection{Model Construction}

Several mechanisms are employed to construct preference models from
the qualitative properties and preference choices input.  Of course,
by my definition these raw input assertions alone can constitute a
preference model, but we are typically more interested in higher-level
inferences we can make from these premises.

{\sc Urp}'s most completely developed model construction mechanisms deal with
assertions about {\it independence axioms} and {\it qualitative behaviors}
of single-attribute utility functions.  Examples of {\sc urp}'s reasoning in
these areas are given in the next chapter; deeper analyses of these
mechanisms appear in chapters \ref{q-behavior-r}
and~\ref{theorem}.

\subsection{Model Analysis}

The goal of the model analysis module is to determine which of the available
strategies yields the highest expected utility given a probabilistic model
and a preference model.  This will not always be possible, either because
the expressions for expected utility are underconstrained, or because the
analyzer is not powerful
enough to recognize the dominance of an expression.\footnote{One expression
{\it dominates} another if its value is greater for any allowable assignment of
the parameters.}  If the procedure
succeeds in proving that one alternative is optimal, the process is
finished.  Otherwise, it is necessary to refine the preference model.  Examples
of refinement goals are to constrain
a certain parameter or set of parameters, to determine the applicability of
a functional constraint such as monotonicity or concavity, or to find a
simpler utility function that has fewer parameters.

\section{Status of the Implementation}

This thesis report describes both a design for a comprehensive preference
modeler and an implementation that realizes part of that design.  I use
``{\sc urp}'' to refer to both of these at times; where it may be unclear
I explicitly distinguish the {\it implemented} {\sc urp} from the {\sc
urp} {\it framework}.
I have taken the implementation to a point that demonstrates the
feasibility and potential of the approach, and at the same time provides
some interesting and useful capabilities.  Throughout this thesis I
point out parts of the implemented {\sc urp} that need to be extended, and
discuss ways in which the program could be improved.

Development of the complete preference modeling system as envisioned
here could potentially require an effort similar in size to the {\sc
macsyma} project.  Because the system revolves around a task rather than
a particular method, a comprehensive program would be composed of a multitude
of separate mechanisms and representations.  Indeed, even the implemented
portion of {\sc urp} includes several distinct components.  Coordinating
the use of these separate programs for a central task is a considerable
engineering problem in itself.

The usefulness of the implemented part is illustrated by the example of
chapter~\ref{r-exam}.  There it is shown that the program is able
to reduce the set of admissible options from those considered in an actual
medical decision based on weak, qualitative assumptions about the
patient's preference structure.  Various kinds of reasoning about the
qualitative properties themselves and how they relate to the utility
function are also demonstrated.  Though the program cannot always take
advantage of the inferences it makes about the function for decision
making, a decision analyst would find these facilities useful for
developing utility models that could then be used in conventional
decision analysis tools (along the lines of the program described by
Pauker and Kassirer~\cite{PaukKass81}, in routine use at Tufts-New
England Medical Center).

The facilities implemented for multiattribute decomposition are limited to
model-structuring.  To use a multiattribute model
generated by {\sc urp} for an actual analysis, one would have to
transfer the model to a package that performs multiattribute assessment
and evaluation.\footnote{For example, Keeney and Sicherman's
{\sc mufcap}~\cite{KeenSich}
can accept as input many of the models that might be constructed by {\sc urp}.
Though using a conventional utility analysis package sacrifices some of
the advantages of the {\sc urp} framework (the ability to reason about
partially specified functions, for example), there is still substantial
benefit to structuring the model using {\sc urp}.}  Utility theorists
may also find the program useful for exploring novel decompositions based
on different combinations of axioms.  One can test the implications of
new results in multiattribute utility by encoding them as {\sc urp}
independence concepts and theorems, adding them to the existing
knowledge base.

The main objective of this work has been to demonstrate that the
overall approach to preference modeling is feasible and worthwhile.  An
assessment of how this project has satisfied that goal is deferred to the
concluding section.

\section{Guide to the Thesis}

This introductory chapter has served as an abstract description of the
preference modeling task, and as an overview of the approach to preference
modeling embodied by this project.  The rest of this thesis describes the
{\sc urp} preference modeling framework in greater detail: including
working representations and mechanisms as well as unimplemented components that
have been worked out to some degree.

Chapter~\ref{r-exam} provides the setting for the rest of the
thesis by describing
a medical decision example and illustrating some preference modeling
capabilities of {\sc urp}.  The case exemplifies the kind of decision problem
of interest: a situation where there are several feasible strategies, none of
which is obviously the best course of action.  The example also serves to
provide a context for the more detailed descriptions of {\sc urp}'s mechanisms
that follow.

The next chapter describes the first of two major
preference modeling mechanisms implemented in {\sc urp}: reasoning about
the qualitative behavior of single-attribute utility functions.  {\sc Urp}'s
mechanisms for relating these behaviors to the mathematical structure of
the utility function is discussed, with emphasis on qualitative mathematical
reasoning methods employed.  The utility-theoretic content of {\sc urp}'s
single-attribute knowledge is delimited.  Deriving decisions based on
{\sc urp}'s representation of single-attribute functions is the subject of
chapter~\ref{s-do},
which also includes a discussion of dominance-testing procedures incorporated
into the {\sc urp} framework.

The following two chapters deal with {\sc urp}'s facilities for multiattribute
decomposition.  Chapter~\ref{theorem} describes the program's
use of independence conditions to derive multiattribute functional forms,
based on proofs of their validity generated from a knowledge base of
decomposition theorems.  This chapter describes the theorem language as well
as the interpreter that uses the proof rules to derive the functional forms.
The knowledge base itself is described in chapter~\ref{knowledge-base}, an
in-depth discussion of the multiattribute utility theory known to {\sc urp}.
There I describe the concepts appearing in the knowledge base, and provide
rationale for their inclusion.  I also argue that
the knowledge base covers a substantial portion of the important decomposition
results developed by utility theorists.

In chapter~\ref{assess-c} I discuss how
assessment based on hypothetical preference choices---the mainstay
of traditional utility analysis programs---may be incorporated in the {\sc urp}
framework.  The major point of the chapter is how {\sc urp}'s flexible model
structuring capabilities and capacity for reasoning about
incompletely specified models leads to less restrictive assessment.  Of
particular interest
are the ability to work with ad hoc constraints, and the intriguing notion
of interpretation under descriptive theories of preference choice.

Representation of domain-specific preference knowledge is the subject of
chapter~\ref{domain-p}.  There I argue that concepts from a
domain-independent modeling system must be encoded in a technical vocabulary,
and therefore are not necessarily intuitive for modeling in particular
application domains.  This problem is remedied by the construction of a
domain/modeling concept mapping, in the form of a knowledge base.  The
chapter includes a substantial development of a knowledge base of health
preferences, encoded in {\sc urp}'s technical vocabulary.

The concluding chapter~(\ref{con-c}) contains the usual stuff
of which conclusions are made: limitations,
comparison with related work, future directions, and a summary of
contributions.  The contributions are partitioned into three areas, each
speaking
to a different (though possibly overlapping) potential audience for this work:
\begin{enumerate}
\item Preferences in decision making programs
\item Utility analysis
\item Expert systems for mathematical modeling
\end{enumerate}
Skipping ahead to the concluding chapter (especially the perspectives and
contributions sections) before reading much further in the thesis is
recommended for those in need of further motivation for undertaking this
approach to preference modeling.

Finally, the {\sc urp} knowledge base is presented in the appendices.  The
knowledge base specification, in conjunction with informal procedural
descriptions from the body of
this document, should provide sufficient information to reproduce (and
improve upon) the preference modeling capability described herein.

\chapter{A Medical Decision Example}\label{r-exam}

In this chapter I present the outline of a medical decision problem that
typifies the kind of decision to which {\sc urp} might be applied.  After
setting up the problem, I work through some exercises in preference modeling
that could be performed in an application of {\sc urp} to this
problem.  Remember that the purpose of this exercise is to demonstrate
{\sc urp}'s capabilities; I am not making suggestions about the patient's
actual preferences
in this case.  It is not at all important to understand the medical context
of this decision to appreciate the preference modeling facilities.  Therefore,
my description of the case focuses on the structure of the problem at the
expense of (clinically important) details of the medical situation.

\section{The Decision Problem}

The case is taken from a clinical decision consult performed by Dunn at
the Division of Clinical Decision Making at Tufts-New England Medical
Center~\cite{Dunn}.  It is a representative example of the many routine
clinical decision analyses performed by members of that group~\cite{Divi} over
the past eight years.

\subsection{Case Description}

The patient is a 72-year-old white male with a large abdominal aortic
aneurysm (AAA) and a history of coronary artery disease (CAD) and 
cerebrovascular disease (CVD).  There are potential treatments for each of
these problems: aneurysm resection (removal) for the AAA, coronary artery
bypass
graft (CABG) surgery to fix the CAD, and carotid endarterectomy to relieve
the CVD.  His most pressing problem is the aneurysm;
without surgery to repair the AAA his prognosis is poor.  However, his
underlying CAD and CVD place him at a greatly increased risk for death
or disabling stroke during the AAA surgery.  The question is whether to go
ahead and operate to repair the aneurysm anyway, or to try and fix the
patient's coronary artery and carotid problems first.  Five primary options
were considered in the analysis:
\begin{enumerate}
\item {\bf no-repair}:  Do nothing.
\item {\bf aaa}:  Perform surgery to repair the aneurysm only.
\item {\bf cabg}:  Perform cardiac catheterization to determine the extent
and operability of CAD.  Perform CABG, if
indicated, to reduce AAA operative mortality.  Then resect the aneurysm.
\item {\bf endart}:  Perform carotid arteriography to determine the severity
of CVD.  If severe and operable, perform carotid
endarterectomy to reduce likelihood of disabling stroke during AAA surgery.
Then resect the aneurysm.
\item {\bf both}:  Perform both tests and whichever procedures (CABG and/or
endarterectomy) are indicated, followed by aneurysm resection.
\end{enumerate}

In addition, two variations were identified: {\bf cabg*} and {\bf both*},
which differ from their counterparts above in their criteria for performing
CABG.  In the variation strategies, bypass surgery is not performed for
three-vessel CAD.

\subsection{The Analysis}

In the original analysis, the decision criterion was expected survival, with
disabling stroke treated like immediate death.  A large probability tree
was constructed, resulting in a probability distribution over expected
lifetimes (a prospect) for each strategy.  The expectation for years of life
for each prospect is given in table~\ref{base}.

\begin{table}[htbp]
\centering
\begin{tabular}{lc}
\underline{strategy} & \underline{life expectancy (years)} \\[.3cm]
{\bf no-repair} & 2.7 \\
{\bf aaa} & 5.1 \\
{\bf cabg} & 7.0 \\
{\bf endart} & 5.2 \\
{\bf both} & 7.4 \\
{\bf cabg*} & 6.2 \\
{\bf both*} & 6.5
\end{tabular}
\caption{Baseline life expectancies for each strategy}
\label{base}
\end{table}

Survival was computed using the DEALE model of life expectancy~\cite{BeckKass}.
Each terminal node in the decision tree is associated with a DEALE parameter,
which approximates the life expectancy for that outcome.  For now and in the
remainder of this chapter I will treat this parameter as if it represented the
actual lifetime of the patient for the outcome in question; the implications
of that treatment and a further discussion of the DEALE model is deferred to
section~\ref{deale}.

The analysis also included a substantial amount of sensitivity analysis and
discussion, concluding that {\bf cabg} and {\bf both} were the preferred
strategies, with {\bf both} offering a marginal advantage over {\bf cabg}.

\section[Qualitative Single-Attribute Utility]
{Qualitative Reasoning About Single-Attribute Utility}
\label{behavior-x}

For the remainder of this chapter, I will take the baseline probabilistic model
developed for this case as given, and use {\sc urp} to explore a
variety of preference modeling issues.  The outcome space ($X$) is the set of
values possible for {\it life-years}:\footnote{Even though the name of the
outcome attribute is ``{\it life-years},'' I will continue to use ``$x$'' in
mathematical expressions for notational convenience.}
the positive real numbers, perhaps bounded by a
practical maximum for this patient.  For disabling stroke, $x$ is zero
regardless of lifetime.

The preference model used in the original analysis is simply maximization of
life expectancy, $u(x) = x$.  This function implies that all prospects offering
the same expected value for life years are equally preferred.  For example, one
would be indifferent between living five years for certain and flipping a fair
coin
for ten years versus immediate death.  We can apply this model using {\sc urp},
but it would be much more interesting to explore the range of less-restrictive
models that the program is able to generate and reason about.  Though
less-restrictive models will in general yield fewer conclusions, the
conclusions that they do imply are based on weaker assumptions.

Construction of single-attribute utility functions often begins with the
specification of qualitative behaviors of the function.  In this case, an
obvious qualitative property of preference for {\it life-years} is
that ``more is better.''  In other words, the utility function is increasing
in {\it life-years}.  This can be represented in {\sc urp} via the assertion
\begin{itemize}
\item[] ({\bf monotonic-increasing} {\it life-years})
\end{itemize}
This assertion, although based on trivial intuition, tells us quite a bit about
the utility function.  The outcomes (under certainty) are now totally ordered
with respect to preference, and it is even possible to rank some nontrivial
uncertain prospects (as we will see in the next section).
Moreover, {\sc urp} can make use of this information in the context of
particular functional forms: both for consistency checking and for deriving
constraints on parameters.

Some qualitative properties uniquely determine an analytical form for the
utility function.  Suppose we know something about the risk attitude of
the patient in this case, namely that
\begin{itemize}
\item[] ({\bf constant-risk-posture} {\it life-years})
\end{itemize}
holds.\footnote{To launch into a discussion of the utility-theoretic principles
of risk attitude would take us too far away from the point at hand.  For now
it should suffice to take {\bf constant-risk-posture} as a generic qualitative
property that it might make sense to assert (or for the program to infer from
other information).  The purpose of this chapter is to convey
a general feel for the types of reasoning performed by the program.  A deeper
discussion of the utility theory involved is reserved for
chapter~\ref{q-behavior-r}.}  From this, {\sc urp} concludes
\begin{equation}\label{con-risk}
u(x) = ae^{-cx}+b
\end{equation}
An analysis of this function (with the help of Sacks's {\sc qm}~\cite{Sack85a})
reveals that it is only increasing if $a$ and $c$ are of opposite sign.  This
fact is recorded, and may be employed in further inference.

Asserting the qualitative behavior {\bf risk-averse} is equivalent to saying
that the utility function is concave.  The function $u$
(equation~\ref{con-risk}) is concave if and only if $a<0$; from the
monotonicity assertion above {\sc urp} can also deduce that $c$ must be
positive.

If instead {\bf risk-neutral} holds, {\sc urp} determines that the
utility function must be $u(x)=ax+b$, with $a>0$ if preferences are increasing.
Usually we would also scale $u$ from zero to one, giving the equalities
$u(0)=0$ and $u(1000)=1$.\footnote{In this example we have arbitrarily set the
upper bound for {\it life-years} to 1000 (measured in hundredths of a year).
Note that we only know that this
is the ``best'' value because {\bf monotonic-increasing} was asserted.}  Using
this, {\sc urp} can solve for $a$ and $b$, giving
\begin{equation}\label{neutral}
u(x)=10^{-3}x
\end{equation}
Note that this function implies a strategy equivalent to the ``maximization of
life expectancy'' criterion used in the original decision analysis for this
case.\footnote{If
$f$ is a utility function for $x$, any function $g$ such that
$g(x) = af(x) + b, a > 0$, has the property that
$f(x) > f(y) \Leftrightarrow g(x) > g(y)$.  In this case we say that $f$ and
$g$ are {\it strategically equivalent} utility functions.  Given that utilities
are finitely bounded, it is always possible to generate a utility function
strategically equivalent to $f$ having any finite range.  Thus, arbitrary
scaling from zero to one is allowed, and it was really not necessary to solve
for $a$ and $b$ in this case.  When using $u$ as part of a multiattribute
function, however, these constants will matter.}  Using {\sc urp}, the
risk neutrality assumption is explicit and easily retractable.

Reasoning about qualitative behaviors of utility functions can also work in the
opposite direction.  We can assert that a particular functional form holds
(perhaps based on some well-studied utility model) and ask {\sc urp} about its
qualitative behavior.  Figure~\ref{b-session} illustrates an example
terminal interaction (user input follows the
``{\tt -->}'' prompts, my comments are in italics)
where the user asserts a utility function for {\it life-years} of the form
$u(x) = (x+b)^{-c}$, with $b$ positive and $-1<c<0$.\footnote{Naturally, only
users experienced in utility analysis would use {\sc urp} in this fashion.
More realistically, these forms would come from some other program using
{\sc urp} and would be invisible to the user.}  Here {\sc urp} was able
to determine that preference is increasing and decreasingly risk averse.
Without the constraint on $c$, {\sc urp} can only determine that the function
is monotonic (in one direction or the other).

\renewcommand{\baselinestretch}{1.1}
\large
\normalsize
\begin{figure}[htbp]
\begin{verbatim}
command --> ASSERT-FUNC-FORM
attribute --> life-years
Start of interval --> 0    end of interval --> 1000
\end{verbatim}
\begin{quote} \it
All behavior and functional form assertions may be specified over arbitrary
intervals of the utility function.  Here I chose an upper bound of 1000
(hundredths of a year), a reasonable maximum for this patient.
\end{quote}
\begin{verbatim}
Enter the functional form for the utility function 
   --> (expt (+ x b) (- c))
Setting functional form for attribute a to:
     1
  --------
         C
  (X + B)
\end{verbatim}
\begin{quote} \it
Functional form specifications may be built up from the standard operators,
written in prefix notation.  The form is displayed in a more reasonable form
to catch typographical errors.
\end{quote}
\begin{verbatim}
  Enter constraint --> (> b 0)
  Enter constraint --> (< c 0)
  Enter constraint --> (> c -1)
  Enter constraint --> ()
\end{verbatim}
\begin{quote} \it
Before analysis, the user enters constraints on the parameters of the function.
Finally, we ask {\sc urp} to determine which of the qualitative behaviors it
knows about apply to this function.
\end{quote}
\begin{verbatim}
command --> DESCRIBE-BEHAVIORS
attribute --> life-years

 MONOTONIC-INCREASING holds
 RISK-AVERSE holds
 DECREASING-RISK-AVERSE holds
 INCREASING-PROPORTIONAL-RISK-POSTURE holds
\end{verbatim}
\caption{Determining the qualitative behavior of an asserted functional form}
\label{b-session}
\end{figure}
\renewcommand{\baselinestretch}{1.1}
\large
\normalsize

The manipulations of qualitative behaviors I have been presenting in this
section do not really have much to do with the particular medical example we
are discussing.  Rather, the exercise is meant as an illustration of what
qualitative behaviors look like and a demonstration of some of the things we
can do with them in {\sc urp}.  They
can be extremely useful for decision making when they determine a functional
form (as {\bf risk-neutral} and {\bf constant-risk-posture} do above), or
constrain a pre-existing functional form.  A further use of qualitative
behaviors for deriving decisions is illustrated in the next section, on
dominance testing.  Discussion of the general value of reasoning based on
qualitative assumptions pervades this thesis, particularly the conclusion.

\section{Dominance Testing}\label{d-testing}

The ultimate goal of the preference modeling task is to show that certain
strategies are preferred to others.  Since our incomplete preference models do
not admit the calculation of unique preference measures, we must resort to more
general {\it dominance-testing} routines to prove that a particular strategy
is best for all admissible utility functions.  The general dominance problem
is discussed in section~\ref{dominance}.

Recall from above that when {\bf risk-neutral} is assumed (as in the Tufts
consult) the function $u$ is completely determined.  In such a situation,
{\sc urp} would choose the option which maximized equation~\ref{neutral},
in this case the strategy {\bf both}.  Of course, if we always had such strong
constraints we would not need a program with the generality of {\sc urp}.

In the more common (and more interesting) case, we will have only a constrained
analytical form, or perhaps not even that.  Fortunately, there are often
conclusions we can reach with only very weak qualitative restrictions on the
utility function.  Researchers in the field of {\it stochastic
dominance}~\cite{Whit} have developed a collection of criteria under which
prospects can be shown to be ordered for certain classes of utility functions.
Each {\it dominance algorithm} is associated with a well-defined class of
utility functions $U$.  When run on the prospects $p_1$ and $p_2$, the
algorithm returns {\bf true} only if $p_1 \succ p_2$ for all $u\in U$.
A deeper discussion of stochastic dominance and how it is used in {\sc urp}
appears in chapter~\ref{s-do}.

For example {\it first-order dominance}\footnote{Fishburn and
Vickson~\cite{FishVick} describe this as well as all other dominance conditions
mentioned here.} is associated with the class of monotonically increasing
utility
functions.  Therefore, whenever we know that preference for an attribute is
monotonically increasing, we can use the first-order dominance algorithm to
partially order prospects over that attribute.  {\it Second-order dominance}
applies to the concave ({\bf risk-averse}) utility functions.

Figure~\ref{d-diagram} depicts the results of applying the first- and
second-order dominance algorithms on the prospects associated with the
strategies in our medical example.  In the diagram, there is a single
arrow from strategy $A$ to strategy $B$ if and only if $A$
first-order-dominates $B$.  Double arrows represent second-order
dominance.  As we can see, several of these strategies considered may be
eliminated with relatively weak restrictions on the utility function for
{\it life-years}.

\begin{figure}[htbp]
\begin{picture}(150,70)
\put(55,55){\framebox(20,10){\bf both}}
\put(10,30){\framebox(20,10){\bf aaa}}
\put(40,30){\framebox(20,10){\bf cabg*}}
\put(70,30){\framebox(20,10){\bf endart}}
\put(100,30){\framebox(20,10){\bf both*}}
\put(55,5){\framebox(20,10){\bf cabg}}
\put(105,5){\framebox(25,10){\bf no-repair}}
\put(40,35){\vector(-1,0){10}}
\put(60,34.5){\vector(1,0){10}}
\put(60,35.5){\vector(1,0){10}}
%\multiput(61.5,34)(1.5,0){5}{\line(0,1){2}}
\put(100,35){\vector(-1,0){10}}
\put(65,15){\vector(-1,1){15}}
\put(65,15){\vector(1,1){15}}
\put(63,15){\vector(-3,1){45}}
\put(65.5,15){\vector(3,1){45}}
\put(67.5,15){\vector(3,1){45}}
\put(64,55){\vector(-1,-1){15}}
\put(65,55){\vector(-1,-1){15}}
\put(65,55){\vector(1,-1){15}}
\put(63,55){\vector(-3,-1){45}}
\put(67,55){\vector(3,-1){45}}
\end{picture}
\caption{Dominance relations in the medical example}
\label{d-diagram}
\end{figure}

It is interesting to note in figure~\ref{d-diagram} that four of
the seven options are ruled out under the trivial assumption that more
{\it life-years} are preferred to less.  The second-order links are
redundant in this example, but they are still useful to record just in case
some of the options are unavailable for some reason.  These relations hold
as long as the patient is not risk prone for length of life---usually
considered a very reasonable assumption.  An in-depth discussion of why
a person may or may not be risk averse for {\it life-years} is given in
section~\ref{averse-life} below.  Note that the only undominated options
are {\bf cabg}, {\bf both}, and {\bf no-repair}.  The first two are not
surprising, since they are the strategies recommended by the original
consult.  And even though {\bf no-repair} is by far the worst strategy with
regard to expected lifetime, the fact that it is undominated makes sense.
It is the only strategy that does not include an immediate surgical
procedure, and therefore the only one that does not present a significant
risk of immediate death.  A utility function that placed a large value on
life in the very short term (perhaps an extremely risk averse form) would rank
{\bf no-repair} the highest---such utility functions may be consistent with the
conditions of first- and second-order dominance.  In this case, establishing
that the patient is not {\it extremely} risk averse (a relatively easy task
from the
perspective of assessment) should eliminate {\bf no-repair} as a viable option.

In other cases, it may turn out that first- and second-order dominance
conditions are not sufficient to rank the competing strategies.  Such a
result would indicate that stronger assumptions about the preference
model are required.  Note that application of a particular functional
form (such as $u(x)=x$ used in the consult) would not uncover this kind
of sensitivity in the model.  

\section{Multiattribute Utility}\label{m-extension}

In this section I explore the possibilities of extending the analysis of this
case to include other factors in addition to {\it life-years}.  Consideration
of outcomes with more than one dimension requires the construction of a
{\it multiattribute} utility function.  {\sc Urp} has considerable
facilities for structuring multiattribute models, however there are no
implemented procedures for mathematical reasoning
about these models.  Though multiattribute utility is not useful for
determining decisions in {\sc urp}, expertise in structuring these models
is useful and interesting in its own right.

It is easy to imagine decision-making criteria other than length-of-life that
may be important to consider in this case.  I have already mentioned that
there is a possibility that the patient will suffer a disabling stroke;
he may not be indifferent between this outcome and immediate death.  The
strategies include major surgical procedures which can have a significant
impact on the patient's quality of life, in addition to their influence on
survival.  Finally, financial cost may enter into the decision, as the
various strategies differ greatly in that dimension.

The attributes we will consider for this example, then, are
length-of-life, whether or not the patient suffers a disabling stroke, the
morbidity (pain and discomfort) associated with the major surgical procedures
(CABG and carotid endarterectomy), and financial cost.  For the remainder of
this discussion I will use the attribute names and shortened notation given
in table~\ref{at-names}.

\begin{table}[htbp]
\centering
\begin{tabular}{l@{$\;\;\equiv\;\;$}l}
$X_1$ & {\it life-years} \\*
$X_2$ & {\it disabling-stroke?} \\*
$X_3$ & {\it endart-morbidity} \\*
$X_4$ & {\it cabg-morbidity} \\*
$X_5$ & {\it cost}
\end{tabular}
\caption{Notation for utility attributes in the medical decision example}
\label{at-names}
\end{table}

The rest of this discussion is concerned with finding a form for the
multiattribute utility function $u(x_1,\ldots,x_5)$.  Finding a form
consists of decomposing the multivariate function into combinations
of functions of smaller dimension, usually culminating in utility
functions of a single attribute.  {\sc Urp} contains a substantial knowledge
base of specifications for these decompositions, and theorems that
prescribe the conditions under which they
are valid.  These conditions are usually expressed as independence axioms
which constrain the way in which preferences over subsets of the attributes
may interact.  Independence axioms, theorems, and decomposition in general
are discussed at length in chapters \ref{theorem}
and~\ref{knowledge-base}.

The following example illustrates one possible way in which {\sc urp}'s
knowledge about independence axioms may be used for this medical decision
situation.  Suppose that we are willing to make some independence
judgments\footnote{Once again, defining what these particular independence
concepts mean would take us too far afield at this point.  For now I am
just trying to convey a feel for the kinds of reasoning {\sc urp} performs
in multiattribute decomposition.} about
preference over the attributes $X_1,\ldots,X_5$.  In particular, we assert:
\begin{enumerate}
\item ({\bf utility-independence} ($X_2$ $X_3$ $X_4$ $X_5$) ($X_1$))
\label{x-1-ass}
\item ({\bf utility-independence} ($X_1$ $X_3$ $X_4$ $X_5$) ($X_2$))
\label{x-2-ass}
\item ({\bf utility-independence} ($X_1$ $X_2$ $X_4$ $X_5$) ($X_3$))
\item ({\bf utility-independence} ($X_1$ $X_2$ $X_3$ $X_5$) ($X_4$))
\item ({\bf utility-independence} ($X_1$ $X_2$ $X_3$ $X_4$) ($X_5$))
\label{x-5-ass}
\end{enumerate}
{\sc urp} can quickly determine that a valid decomposition structure is:
\begin{enumerate}
\item ({\bf multiplicative-form} ($X_1$ $X_2$ $X_3$ $X_4$ $X_5$))
\label{m-con}
\end{enumerate}
Assumptions \ref{x-1-ass} through~\ref{x-5-ass} above say that
preferences over prospects involving any four of the attributes do not depend
on the fixed value of the fifth.  These are fairly strong assumptions, and
indeed, the multiplicative utility function is one
of the simpler multiattribute forms known to {\sc urp}.
Decomposition conclusions such as this can be graphically displayed
in the form of figure~\ref{h-result-1}.

\begin{figure}[htbp]
\begin{picture}(100,28)
\put(62,25){$X$}
\put(64,24){\line(0,-1){3}}
\put(42,10){\framebox(44,11){multiplicative}}
\put(46,10){\line(0,-1){3}}
\put(55,10){\line(0,-1){3}}
\put(64,10){\line(0,-1){3}}
\put(73,10){\line(0,-1){3}}
\put(82,10){\line(0,-1){3}}
\put(43,3){$X_1$}
\put(52,3){$X_2$}
\put(61,3){$X_3$}
\put(70,3){$X_4$}
\put(79,3){$X_5$}
\end{picture}
\caption{$X$ decomposed via the multiplicative functional form}
\label{h-result-1}
\end{figure}

Now, suppose we decide that some  of the original assumptions do not hold after
all, because relative preference for outcomes containing $X_3,\ldots,X_5$
depends
crucially on length of life and the presence or absence of stroke.  For
example, the patient might be more willing
to trade possible short-term morbidities (attributes $X_3$ and $X_4$) for a
reduced chance of disabling stroke ($X_2$) if he is going to live longer.
Similarly, tradeoffs between morbidities and length of life may be different
for patients who have suffered disabling strokes.
Therefore, we must retract assumptions \ref{x-1-ass} and~\ref{x-2-ass}.  Since
all {\sc urp}
assumptions are maintained as propositions in an underlying truth maintenance
system (part of McAllester's {\it R}\/easoning {\it U}\/tility
{\it P}\/ackage~\cite{McAl}, or {\sc rup}) 
such modular assertion and retraction is easy to perform.  {\sc Urp} determines
that the multiplicative form is no longer valid for $X$ (retracting
conclusion~\ref{m-con}).

Perhaps we are willing to make additional assumptions in lieu of
\ref{x-1-ass} and~\ref{x-2-ass}.  In particular, suppose we assert that
preference for morbidities and costs are invariant when both $X_1$ and
$X_2$ are fixed, and that preference for lotteries containing $X_1$,
$X_4$, and $X_5$ does not depend on the other attributes.
\begin{enumerate}
\addtocounter{enumerate}{5}
\item ({\bf utility-independence} ($X_3$ $X_4$ $X_5$) ($X_1$ $X_2$))
\item ({\bf utility-independence} ($X_1$ $X_4$ $X_5$) ($X_2$ $X_3$))
\end{enumerate}
With these replacement assumptions, the multilinear form
is valid, as are several other propositions, including conclusion~3.
\begin{enumerate}
\addtocounter{enumerate}{1}
\item ({\bf multilinear-form} ($X_1$ $X_2$ $X_3$ $X_4$ $X_5$))
\item ({\bf utility-independence} ($X_4$ $X_5$) ($X_1$ $X_2$ $X_3$))
\end{enumerate}
Another alternative is to decompose $X$ hierarchically, combining
the attributes $X_1$, $X_2$, and $X_3$ into a single vector attribute, $W_0$.
Attributes $X_4$ and $X_5$ are similarly combined to form the vector $W_1$.
The utility independence of $W_1$ from $W_0$ (conclusion~3)
directly validates a two-attribute functional form which I will refer to as
the ``UI form.''  To complete the decomposition we need to find a
multiattribute form for the attributes composing $W_0$ and $W_1$.  This is
accomplished
by applying the usual procedure recursively to a subset of the original
universe of attributes.  In this case,
{\sc urp} is able to determine that a multiplicative utility function is valid
for $W_0$ and that the UI form is valid  for $W_1$.
\begin{enumerate}
\addtocounter{enumerate}{3}
\item ({\bf multiplicative-form} ($X_1$ $X_2$ $X_3$))
\item ({\bf utility-independence} ($X_4$) ($X_5$))
\end{enumerate}
The resulting decompositions are depicted in figure~\ref{h-result-2}.

\begin{figure}[htbp]
\begin{picture}(110,40)(8,0)
\put(42,31){$X$}
\put(44,30){\line(0,-1){3}}
\put(22,16){\framebox(44,11){multilinear}}
\put(26,16){\line(0,-1){3}}
\put(35,16){\line(0,-1){3}}
\put(44,16){\line(0,-1){3}}
\put(53,16){\line(0,-1){3}}
\put(62,16){\line(0,-1){3}}
\put(23,9){$X_1$}
\put(32,9){$X_2$}
\put(41,9){$X_3$}
\put(50,9){$X_4$}
\put(59,9){$X_5$}

\put(112,38){$X$}
\put(114,37){\line(0,-1){3}}
\put(99,26){\framebox(30,8){UI form}}
\put(103.5,26){\line(0,-1){3}}
\put(124.5,26){\line(0,-1){3}}
\put(101,19){$W_1$}
\put(122,19){$W_0$}
\put(103.5,18){\line(0,-1){2}}
\put(124.5,18){\line(0,-1){2}}
\put(86,8){\framebox(24,8){UI form}}
\put(91,8){\line(0,-1){3}}
\put(105,8){\line(0,-1){3}}
\put(88,1){$X_4$}
\put(102,1){$X_5$}
\put(115,8){\framebox(30,8){multiplicative}}
\put(119,8){\line(0,-1){3}}
\put(130,8){\line(0,-1){3}}
\put(141,8){\line(0,-1){3}}
\put(116,1){$X_1$}
\put(127,1){$X_2$}
\put(138,1){$X_3$}

\end{picture}
\caption{Two possible decompositions for $X$ based on assumptions 3 through~7}
\label{h-result-2}
\end{figure}

In this case, there exists a simple single-level decomposition using the
multilinear form and a two-level decomposition requiring intermediate
vector attributes (introduced automatically by {\sc urp}).  But while the
hierarchy for the decomposition on the left-hand side of figure
\ref{h-result-2} is simpler, the utility function
corresponding to the multilinear
form for $X$ contains 30 ($2^5-2$) independent scaling constants compared
to only seven (three for the multiplicative decomposition of $W_0$ and two each
for the UI forms) for the decomposition on the right.
Based on this simple metric, the second decomposition would be chosen for the
preference model.

Similarly, we could retract any of the other assumptions, perhaps replacing
them with weaker or stronger independence conditions described in {\sc urp}'s
knowledge base.  Each time a replacement is made {\sc urp} restructures the
preference model
according to which utility functions are justified by the assumptions.  Through
automatic hierarchical decomposition, the program is able to construct
models ranging over a continuum of possible structures.

\chapter{Reasoning About Qualitative Behaviors}
\label{q-behavior-r}

Utility theorists have developed a large vocabulary for describing general
properties of utility functions that helps bridge the gap between intuition
and mathematics.  A major goal in the {\sc urp} project has been to show
that it is possible to perform the greatest bulk of reasoning about preferences
in terms of these properties, and that conclusions based on them will be more
satisfying than those derived
under a purely quantitative approach.  Qualitative behaviors of
single-attribute utility functions make up one very
important category of qualitative property, but they are by no means the only
type.  This chapter describes {\sc urp}'s facilities for reasoning about them,
with special emphasis on mechanisms
necessary to produce the example of section~\ref{behavior-x}.
Reasoning about independence axioms---the second major type of qualitative
property used by {\sc urp}---is the subject of
chapter~\ref{theorem}.

\section[Functions in {\sc Urp}]{Functions in U{\sc RP}}\label{urp-functions}

Recall that an {\sc urp} preference model consists of a collection of
assertions about a multiattribute utility function.  Multiattribute utility
functions themselves are often defined in terms of other utility functions,
usually culminating in single-attribute functions.  In reasoning about
overall preferences, we consider various properties of the unidimensional
functions as well as the possible decomposition patterns.  It is fairly obvious
that functions are a central
object of all of this reasoning, and that a large fraction of assertions about
utility structure can be expressed in terms of properties of particular
functions making up that structure.

For the remainder of this discussion I will use the term {\it function} to
mean the object in {\sc urp} that {\it specifies} a function of a single
numeric variable.  Since
these specifications are incomplete, we cannot in general manipulate them as
we could explicit mathematical functions.  Nonetheless, there is a substantial
variety of kinds of reasoning we can perform with them.

While {\sc urp} employs functions other than utility functions (such as risk
functions, to be discussed below), these
special functions are
the main objects of concern.  A utility function $u$ is a mapping from $Y$ to
$\left[0,1\right]$, where $y \in Y$ describes some part of the outcome space.
More formally, $Y = Y_1 \times\cdots\times Y_m$, where
$\{Y_1,\ldots,Y_m\}$ is a subset of $\{X_1,\ldots,X_n\}$.  In the
unidimensional
case (the one we are most concerned with here), $y$ will be the value of
a single attribute, and we will say $u_i: X_i \rightarrow \left[0,1\right]$.

Two components of a function are therefore its domain and range.  There are
always two distinguished points in the domain, the most and least preferred,
denoted by $y^*$ and $y_*$, respectively.  These may or may not be known, or
there may be constraints on the possibilities.  There may be other outcomes
which are indifferent (equally preferred) to $y^*$ or $y_*$.

Three other function components restrict the possible mappings between the
domain and range:
{\it functional forms}, {\it evaluations}, and {\it qualitative behaviors}.
Each of these is described in greater detail below.  Representation for
{\sc urp} functions is based on the {\sc qm} package developed by
Sacks~\cite{Sack85a}.  Much of the mathematical reasoning about functions is
performed by {\sc qm}, described in section~\ref{q-math}.

\subsection{Functional Forms}

The {\it functional form} is an expression which describes the computation of
the function's value from the input.  This description is built from standard
arithmetic operations and conditional expressions, over numbers and symbolic
parameters.  Symbolic parameters may be associated with arbitrary constraints
or relations to other {\sc urp} objects.

Functions that have different symbolic forms over different slices of
their domain are represented by piecewise function intervals.  Piecewise
functions fit in naturally with {\sc qm}'s analysis of functions as collections
of monotonic intervals.

\subsection{Evaluations}

{\it Evaluations} are objects that represent the value of the function at
specific points.  Like symbolic parameters, these objects may be defined
by arbitrary relations to other objects in the system.  A function may include
any number of these evaluations.  Evaluations typically become useful in
reasoning about utility assertions in the form of preference choices.  Utility
functions all include the two special evaluations $u(y_*) = 0$ and
$u(y^*) = 1$.

\subsection{Qualitative Behaviors}

{\it Qualitative behaviors}\footnote{Behaviors of functions are a specific type
of property that may be expressed qualitatively in {\sc urp}.  When it is clear
that we are talking about functions,
the terms {\it qualitative properties} and {\it qualitative behaviors} may be
used interchangeably.} are overall constraints on a function's
characteristics that can be described by a single proposition.  Part of the
value of these constraints is that they restrict the possibilities for the
other components of {\sc urp} functions: functional forms and evaluations, as
well as the subcomponents making up these objects.  The qualitative behaviors
are treated as first-class components because they may have significant
interactions (that is, certain combinations of behaviors may have special
interpretations) and because their meaning may vary for different functional
forms.  Some qualitative properties (including {\bf monotonic-increasing})
were illustrated in the example of section~\ref{behavior-x}.  A list
of the qualitative properties of unidimensional utility functions currently
represented in {\sc urp} is given in appendix~\ref{q-appendix}.

Most of these qualitative behaviors only have meaning if the domain of the
function is a set of numeric values, such as subranges of reals or integers.
If $Y$ is made up of non-numeric values (such as vectors or discrete
categories) {\sc urp}
may apply a mapping from the members of $Y$ to some numeric domain.  Discrete
categories, for example, would map to an index set of integers.\footnote{It
may even be reasonable for {\sc urp} to change this
mapping dynamically during preference modeling.  For example, it will usually
be most useful to map the categories in a way that preserves preference
order---which may not be known at the outset.}
Then the program can use the same qualitative propositions to describe the
index set, taking care to make the correct type conversions when making
inferences about the utility function from them.  These issues are discussed
more fully in section~\ref{measure-discussion}.

\section{Manipulating Qualitative Behaviors}

\subsection{Qualitative Behavior Assertions}\label{q-assertions}

Like assertions about independence axioms, qualitative behavior assertions are
handled by {\sc rup}.  A qualitative behavior assertion is a two-place
predicate, where the arguments indicate the utility attribute and an interval
of values over which the behavior applies (the interval is omitted in
the notation below when the behavior holds over the entire domain of the
attribute).  Logical relations among the qualitative behaviors are specified
and maintained by {\sc rup}.  Inference across intervals
is handled specially, for reasons of efficiency.  Some illustrative
logical relations are given in figure~\ref{q-properties-f}.

\begin{figure}[htbp]
\begin{tabbing}
({\bf risk-neutral} ?f ?i) $\Leftrightarrow$
  \` ({\bf constant-proportional-risk-posture} ?f ?i) \\
  \` $\wedge$ ({\bf constant-risk-posture} ?f ?i)  \\ [.2cm]

({\bf monotonic} ?f ?i) $\Leftrightarrow$ \\
  \` ({\bf monotonic-nonincreasing} ?f ?i) $\vee$ ({\bf monotonic-nondecreasing} ?f ?i) \\ [.2cm]

({\bf decreasing-risk-aversion} ?f ?i) $\Leftrightarrow$ \\
  \` ({\bf decreasing-risk-posture} ?f ?i) $\wedge$ ({\bf risk-averse} ?f ?i)
\end{tabbing}
\caption{Logical relations among qualitative behaviors of functions}
\label{q-properties-f}
\end{figure}

In {\sc urp}, a behavior that
is fully characterized by a combination of lower-level behaviors is treated
as a terminological definition, resulting in simpler specification of the
logical relations and mathematical properties of the behavior.

\subsection{Qualitative Behaviors and Function Components}\label{q-b}

The mechanisms by which qualitative behaviors affect other function components
are a bit more complex than the logical relations above.  Qualitative behaviors
can determine the functional
form, they can constrain parameters of a particular form, or they can restrict
the value of evaluations.  There are two alternate implementation
approaches; {\sc urp} employs a combination of these.

\subsubsection*{Surface-Level Approach}

The simplest approach is to associate each significant combination of
qualitative behaviors with its implications for the functional form.  For
example, the knowledge base of a purely surface-level reasoner would contain
many logical statements looking something like
\begin{quote}
({\bf risk-neutral} ?f) $\Leftrightarrow$
	{\it functional-form}\/(?f) = {\bf linear-form}
\end{quote}
where the structure of {\bf linear-form} is specified elsewhere as $ax+b$.
Also associated with {\bf linear-form} would be the implications of various
other qualitative properties on the parameters.  For example, if
$u(x) = ax + b$, then
\begin{quote}
({\bf monotonic-increasing} $u$) $\Leftrightarrow a > 0$.
\end{quote}

These sorts of inference are easily handled by the TMS within {\sc rup}.  The
implications that result in a functional form are part of the original
knowledge base, instantiated at the same time as the function object.
The implications from functional forms and further qualitative behaviors to
parametric constraints are implemented as pattern-directed inference rules,
activated only when the
functional form is established.  These noticers also contain {\sc lisp} code to
directly modify the data structures representing the function object.

\subsubsection*{A Deeper Mathematical Approach}

The problem with the above approach is that it does not capture the deeper
mathematical meaning of the qualitative behavior assertions.  Because of
this, it is necessary to anticipate the effect of every qualitative behavior
on every different functional form and combination of qualitatively significant
parametric constraints.

For example, consider the interaction between the
useful qualitative behavior {\bf constant-risk-averse} and the sign of the
slope of a monotonic utility function, $u$.  Reasoning at the surface level,
the knowledge base would have to contain separate rules to determine the
functional form given {\bf constant-risk-averse} and each of the two
direction possibilities.  In this case, the two rules would be:
\begin{enumerate}
\item ({\bf monotonic-increasing} $u$) $\Leftrightarrow
	u(x) = ae^{-cx}+b, a<0, c>0$
\item ({\bf monotonic-decreasing} $u$) $\Leftrightarrow
	u(x) = ae^{-cx}+b, a<0, c<0$
\end{enumerate}

As shown, the two functions differ only in the sign of the exponent.
Similar symmetries will be explicitly represented in describing the
interactions of the two types of monotonicity with other qualitative
behaviors ({\bf risk-neutral} and {\bf constant-risk-prone}, for example).
Other
natural symmetries (or other simple structural relationships) are also ignored
by the surface-reasoning system, such as that between risk aversion and
proneness, increasing and decreasing risk postures, etc.

This duplication is particularly irritating because we are
failing to take advantage of the very elegant structure of the concepts
underlying the qualitative behaviors useful in utility theory.\footnote{This
structure is
apparent on a simple perusal of the list of qualitative behaviors given in
appendix~\ref{q-appendix}.}  The alternative is to represent these qualitative
behaviors in terms of their mathematical
interpretations.  These concepts generally have a strict mathematical
definition which is largely independent of the other qualitative behaviors that
apply in a particular case.

Let us look at risk aversion, since most of the unidimensional qualitative
behaviors defined thus far deal with that phenomenon.  The risk aversion
function $r$ associated with a monotonically increasing utility function $u$
is defined as
\begin{equation}\label{risk-up}
r(x) = \frac{-u''(x)}{u'(x)}
\end{equation}
For monotonically decreasing utility functions, the risk aversion function is
called $q$, with
\begin{equation}\label{risk-down}
q(x) = \frac{u''(x)}{u'(x)}
\end{equation}
For the rest of this discussion, all references to $r$ are meant to indicate
$q$ for decreasing functions (non-monotonic functions are ignored for the time
being).

With this definition, risk aversion has a simple meaning.  The assertion
({\bf risk-averse} $u$) is now equivalent to saying that for all $x$,
$r(x)$ is positive.\footnote{Actually, for this example, all we really need to
know is that $u$ is concave (that is, the second derivative is negative).
Thus, we may consider risk aversion for even nonmonotonic functions.
For higher-order risk properties it will be necessary to reason in terms
of the risk function $r$.}  Given
the relationship between $r$ and $u$, this piece of
information is sufficient for all inference that was possible in reasoning
about risk aversion on the surface level.  More importantly, representing
the assertion at this level provides for greater orthogonality between
qualitative behaviors.  Now, for example, the effect of asserting
({\bf constant-risk-posture} $u$) is simply to add the fact that $r(x) = c$,
for some constant $c$.  Taken together, it is quickly seen that $c > 0$.

Not quite as quickly, it would also be possible for the system to derive
the functional form directly from these mathematical descriptions of the
qualitative behaviors.  Substituting the definition of $r$, we get a
differential equation
\[u''(x) + cu'(x) = 0\]
which can be solved to determine the functional form of $u$
(here $ae^{-cx} + b$, with $a<0$ and $c>0$, as above).  So we see that it may
not even be
necessary to explicitly include relations from qualitative behaviors to
functional forms at the surface level at all.

Of course, this is how utility theorists determined these functional forms
in the first place.  The results, usually along with the derivations, appear
in textbooks.  But it also seems wrong to have to perform this derivation
each time we encounter this combination of qualitative behaviors.  After all,
the notion of constant risk aversion was deemed important enough to give
it its own name, so there must be some reason to think of it at that surface
level.  Even though utility analysts are mathematically oriented, my bet is
that they would prefer to memorize functional forms or look them up in
reference books than to derive them from first principles each time.

Having come full circle, the answer to the choice of approaches seems clearer.
For useful combinations of qualitative behaviors, it is worthwhile as well
as legitimate to enumerate their effects on functional forms and parameters
directly.  However, because {\sc urp} may encounter previously unanticipated
combinations of these behaviors, it is necessary to develop a deeper
mathematical representation for their meaning.  As {\sc qm} has proven
powerful enough to determine parameter constraints from qualitative behaviors,
and vice-versa, {\sc urp} uses it for deep reasoning about parameters.
Functional forms are generated from surface-level relationships.

\section{Qualitative Mathematics}\label{q-math}

{\sc Urp}'s mechanisms for reasoning about the qualitative mathematical
behavior of functions are based on the Qualitative Mathematics package
({\sc qm}) developed by Sacks~\cite{Sack85a}.  {\sc Qm} uses calculus and
other mathematical techniques to analyze the behavior of piecewise continuous
functions of real numbers.  While designed primarily for reasoning about
the dynamic behavior of physical systems, {\sc qm}'s representations and
capabilities for manipulation of function objects have proved quite useful
for analyzing the behavior of utility functions.  This section briefly
describes some aspects of {\sc qm}, and how some of the program's mechanisms
have been adapted for use in {\sc urp}.

\subsection{Functions in QM}

{\sc Qm} represents a function as a collection of
intervals on which it is continuous and monotonic.  Each interval (called
a {\it fun-int}\/) is a
data structure which records such information as the function's form,
inverse, derivatives, and boundary points.  {\sc Qm} constructs these
representations from a closed-form expression made up of symbolic
parameters (possibly constrained), standard arithmetic operations, and a
variable.  Since a function may have different qualitative behaviors for
different values of its parameters, {\sc qm} generates separate function
objects for each distinct case, recording the parameter ranges for which
it is appropriate.  The algorithms and data structures are described in
full detail in Sacks's original thesis report~\cite{Sack85a}.

\subsection{Partially Specified Functions}

In applying {\sc qm} to the analysis of utility functions in {\sc urp}, it
was necessary to extend the function object representation to handle a
broader range of incomplete specifications.  We often have quite a lot of
information about an {\sc urp} utility function (qualitative behaviors,
constraints on evaluations) without an analytic expression.  Existing {\sc qm}
data structures can accommodate the expression of this partial knowledge
with only slight augmentation.  For example, it was necessary to add a
facility for specification of information about evaluations, and for
expressing disjunctions of possible directions for the function on an
interval.

\subsection{Encoding Function Behaviors}\label{encoding-b}

For reasoning about qualitative behaviors as in section~\ref{q-b}, we have
to relate the behaviors to mathematical properties represented by {\sc qm}
functions.  Fortunately, many of the behaviors of interest for utility
functions are directly included in the function object data structure, or
are easily computed from it.  In particular, direction and convexity have
built-in predicates in {\sc qm}.

Given an incompletely specified function and a behavior, we would like to know
whether the function exhibits that behavior, and what implications an assertion
that the behavior holds would have on the function specification.
Each {\sc urp} qualitative behavior is encoded as a set of three procedures,
operating on a function object and an interval (range of domain values):
\begin{enumerate}
\item A possibility predicate ({\it pos}\/), which is true if the behavior
{\it possibly} holds over the indicated interval of the function
\item A necessity predicate ({\it nec}\/), which is true if the behavior
{\it necessarily} holds over the function interval
\item An enforcer procedure ({\it enf}\/), which constrains the function object
to observe the behavior over the interval
\end{enumerate}
These procedures are encoded as (generally short) fragments of {\sc lisp}
code.  As mentioned above, some behaviors are completely defined in terms of
other
behaviors, and therefore do not require their own procedure specifications.

For example, the {\it nec} predicate for {\bf risk-averse} simply checks that
all {\sc qm} {\it fun-ints} over the interval of interest are marked
{\it concave}.  Similarly, the {\it pos} predicate checks that none are
{\it convex}.  The {\it enf}\/ procedure marks as concave any {\it fun-int} of
unknown
convexity.  Some of the {\it enf}\/ procedures corresponding to other behaviors
are significantly more complicated.

An {\sc urp} function object in general includes a list of possible {\sc qm}
functions representing it.  This disjunctive form allows for conditioning
dependent on the value of parameters of the analytical form.  Because the
{\sc urp} behavior procedures described above work for individual {\sc qm}
function objects, a predicate over the entire {\sc urp} function is a
conjunction of {\it nec} predicates or a disjunction of {\it pos}\/s.
Enforcing a behavior over an interval involves discarding any of the
possible {\sc qm} functions that is inconsistent with the behavior (that
is, not {\it pos}\/), and applying the {\it enf}\/ procedure to each one
remaining.

Thus, one way that constraints on parameters of symbolic forms are determined
is by elimination of cases generated by {\sc qm}.  For the types of behaviors
implemented and the functional forms analyzed in tests of the program,
{\sc qm} generates all of the necessary distinguishing cases.  We should
expect this to work as long as the qualitative behaviors that are
important for utility correspond to qualitative properties of functions
known to {\sc qm}.  In {\sc urp}, all of the behaviors are first-class
{\sc qm} concepts of the utility function or of functions derived from the
utility function.

\subsection{Enforcing a Functional Form}

The behaviors in {\sc urp} that determine a symbolic form for the utility
function are particularly useful.  There are three of these, shown
with their associated forms in table~\ref{u-form-t}.

\begin{table}
\centering
\begin{tabular}{l|cc}
Behavior & Form name & Expression \\
\hline \\ [.1cm]
 {\bf risk-neutral} & linear & $ax+b$ \\
\hline {\bf constant-risk-posture} & exponential & $ae^{-cx}+b$ \\
\hline {\bf constant-proportional-risk-posture} & power & $ax^{1-c} + b$ \\
\hspace{1em} (two possibilities) & log & $a(\log x) + b$
\end{tabular}
\caption{Qualitative behaviors that imply single-attribute functional forms}
\label{u-form-t}
\end{table}

When one of these behaviors is asserted, {\sc qm} creates a list of possible
function objects representing the function (differing in parameter ranges).
{\sc Urp} merges these objects with the current incomplete description of
the utility function, discarding the {\sc qm} possibilities which are
inconsistent with what is already known.  For the forms appearing in
the table, direction and convexity information constrains the values (usually
the sign) of parameters $a$ and $c$.

\subsection{Risk Functions}

To reason about the risk properties of utility functions (which most of
the defined behaviors describe), {\sc urp} analyzes the risk functions
defined in equations \ref{risk-up} and~\ref{risk-down}.  {\sc Qm} is
used to generate a function object corresponding to the ratio of the
second and first derivatives, created from symbolic expressions already
computed by {\sc qm}.  Thus, behaviors dealing with high-order risk
properties correspond to qualitative properties of the risk function $r$.
For example, {\bf increasing-risk-averse} holds if and only if $r$ is
positive (or equivalently, $u$ is concave) and increasing.

Similarly, behaviors dealing with proportional risk posture are treated
as qualitative properties of the function $\rho(x)=xr(x)$.

\subsection{Describing Behaviors}

Using {\sc qm} in conjunction with the {\it pos}, {\it nec}, and {\it enf}\/
mechanism, it is possible to assert and analyze a wide range of combinations
of qualitative behaviors, functional forms, and parametric constraints.  To
test this capability, I tried the system on all of the single-attribute
utility functions appearing as examples and exercises in chapter~4 of
Keeney and Raiffa~\cite{KeenRaif}.  Of these 18 diverse functions, {\sc urp}
was able to generate correct behavior descriptions of the sort depicted in
figure~\ref{b-session} for all but one.\footnote{This exception only
failed in the analysis of the proportional risk behavior, due to a fairly
complex expression for the proportional risk function.  As a further note
of interest, the system uncovered a typographical (sign) error in table~4.5 of
the aforementioned text.}  In addition to testing for behaviors, the system
may be used to derive constraints on parameters for all of these functions,
or to display the risk or proportional risk functions associated with them.

\section{Qualitative $\Rightarrow$ Intuitive?}\label{1-step}

The preceding discussion illustrated some of the qualitative properties
{\sc urp}
knows about and how they influence the mathematical utility model.  An
assumption that has been implicit throughout is that reasoning in terms of
qualitative behaviors is somehow more intuitive than the usual numeric
approach.  The reader may reasonably protest, however, that the above
properties are not very intuitive (except perhaps to utility experts) and
therefore not necessarily helpful.  I would contend, though,
that they are only one step away from being intuitive.  That is, each
property (risk aversion, proportional risk aversion, etc.)\ will have a
more intuitive interpretation in the context of a particular attribute
or decision domain.  {\sc Urp} uses the technical terminology because
it is more general and more concise.  Nevertheless, I will concede that
a system that cannot tie utility-theoretic concepts to domain principles
will not be very useful to a decision maker unfamiliar with utility theory.
This issue will be addressed at length below in chapter~\ref{domain-p}, about
preference knowledge for specific application domains.

\chapter{Stochastic Dominance}\label{s-do}

Although the qualitative analysis of utility function behaviors is interesting
in its own right for the insight it provides into the structure of preferences,
we are at least as interested in the implications these qualitative
behaviors have for particular decision situations.  As we have seen, {\sc urp}
can represent a wide range of partial specifications for utility functions,
incorporating constraints from different sources into a central function
object.  The use of this function object as a basis for prescribing
decisions raises some interesting questions.  In this chapter I discuss the
general problem, outline some approaches, and describe the mechanisms
employed by {\sc urp}.  Possibilities for extending {\sc urp}'s
capabilities in this area are also discussed.

\section{Dominance}\label{dominance}

\subsection{The General Case}

Testing for the dominance of prospect $p_1$ over
prospect $p_2$ is a search for a proof that $u(p_1) > u(p_2)$ given all the
known constraints on $u$.  Taking the definition of expected utility, this
is equivalent to
\begin{equation}\label{dominance-e}
\sum_{x\in X} p_1(x)u(x) > \sum_{x\in X} p_2(x)u(x) 
\end{equation}
where $p_i(x)$ is the probability of outcome $x$ in prospect $p_i$.  In the
most general case, $u$ is specified to an arbitrary level of completeness
and the search for a dominance proof is arbitrarily difficult.  Therefore,
the basic strategy is to avoid the general case by recognizing features of
$u$ which indicate the relevance of special-purpose strategies.  But since
a wide range of different special-purpose strategies may be employed depending
on the features of $u$, the overall system approaches
generality as more feature-strategy combinations are incorporated.

\subsection{The Case of Known Functional Forms}\label{known-forms}

An enormous improvement from the general case is obtained when we have a
symbolic form for the utility function.  In this situation the
inequality~\ref{dominance-e} is a closed-form expression, annotated by any
known constraints on the parameters of $u$.  Overall behavior information
or constraints on evaluations of $u$ at specific points may also be known,
but these are harder to use if they are not translated to parametric
constraints.  Though {\sc urp} is often able to generate these constraints
from qualitative behaviors (as described in section~\ref{q-math} above),
there are many situations where it cannot, or where the information is simply
not expressible in this form.

Even when functional forms are known, dominance-proving is a hard problem---one
that has long concerned mathematicians, operations researchers, and those
developing symbolic algebraic reasoners, among others.\footnote{The volume
by Hardy, Littlewood, and P\'{o}lya~\cite{Hard} is an early, comprehensive work
devoted entirely to the problem of determining that one mathematical expression
dominates another.  While their interests are of course much different than
ours here, it illustrates the extent of mathematical activity in the subject.}
Its difficulty
will depend on the structure of the inequality expression we are trying to
prove.  Since each side of~\ref{dominance-e} is a linear combination of utility
function evaluations, the expression's complexity is totally determined
by the complexity of $u$.  Thus, examinations of $u$'s form will indicate
which constraint algorithms will be tractable and correct, or which may
be most likely to give us a good answer.  Choosing these algorithms and
incorporating them into {\sc urp} is an important area for future research.
As we will see in section~\ref{a-constraints}, similar problems arise in
reasoning about hypothetical preference choices for assessment.

There are some simple tricks we can employ to make the problem somewhat easier.
First, we may perform any positive linear transformation of $u$ that would
simplify
the dominance expression.  This will often eliminate one or two parameters
(which are usually only included to allow linear transformations for scaling
purposes anyway).  Thus, the {\tt linear} form implied by the behavior
{\bf risk-neutral} can be seen to order all prospects trivially by expected
value.

Second, we may simplify the prospects themselves by removing common
components.  That is, we generate new prospects $p_{1'}$ and $p_{2'}$, where
\begin{equation}\label{common-c}
   \begin{array}{l@{\;\;=\;\;}r}
	p_{1'}(x) & {\rm MAX} \left[ 0,\; p_1(x)-p_2(x)\right] \\
	p_{2'}(x) & {\rm MAX} \left[ 0,\; p_2(x)-p_1(x)\right]
   \end{array}
\end{equation}
Of course, this transformation applies regardless of $u$.

Finally, note that deciding the preference order of certain outcomes is
usually considerably easier than proving dominance among uncertain prospects.
Typically we rely on monotonicity assertions, or transitivity with respect
to known ordered pairs.  While this may seem a trivial matter, ordering of
certain outcomes is a common operation in testing for dominance of more complex
prospects.

\section{Stochastic Dominance}

In the section above I suggested that the way to structure our dominance
testing is to match specific strategies to features of the utility function.
The next step, then, is to identify the useful features and develop their
associated strategies.  Fortunately, there is a substantial body of research
in the field of {\it stochastic dominance} \cite{Bawa}~\cite{Whit} which is
devoted to precisely this problem.  Though developed primarily with
applications to finance and economics in mind, stochastic dominance results
apply to utility functions in general.  Typically, these results associate
algorithms for dominance-testing with well-specified classes of utility
functions for which they are valid.  The dominance-testing procedures are
specified solely in terms of the prospects to be ranked.

Fishburn and Vickson~\cite{FishVick} describe four major stochastic dominance
results, providing successively stronger dominance-proving power while placing
greater restrictions on the class of utility functions $U$\/ they hold for.
Table~\ref{s-d-t} lists these dominance categories along with the properties
of the utility functions $u\in U$.

\begin{table}[htbp]
\centering
\begin{tabular}{l|l}
{\it Dominance Type} & {\it Properties of} $U$ \\
\hline \\[.1cm]
first-order & {\bf monotonic-increasing} \\
\hline second-order & {\bf monotonic-increasing}, \\
& {\bf risk-averse} \\
\hline third-order & {\bf monotonic-increasing}, \\
& {\bf risk-averse}, \\
& positive third derivative \\
\hline DARA & {\bf monotonic-increasing}, \\
& {\bf decreasing-risk-averse}
\end{tabular}
\caption{Four dominance categories with their associated utility function
classes}\label{s-d-t}
\end{table}

Notice that all of the utility-class specifications---with the exception of
third-order dominance\footnote{This deficiency is not serious; including
the third derivative's sign as a new qualitative behavior would
be a simple matter.}---can be
completely described in terms of qualitative behaviors already defined in
{\sc urp}.  Thus {\sc urp} is able to determine which dominance algorithms
are valid for arbitrarily specified utility functions, and to indicate the
implications for $u$ of adding the assumptions necessary for a technique to
be applicable.  This capability underscores the value of reasoning directly in
terms of qualitative behaviors for single-attribute utility.

\section[Encoding Dominance Routines in {\sc Urp}]
{Encoding Dominance Routines in U{\sc RP}}\label{d-routines}

A dominance test in the {\sc urp} knowledge base is an association between
an algorithm and a set of applicability criteria.  An algorithm---coded
directly in a general-purpose programming language---is a predicate.
Given prospects $p_1$ and $p_2$, the predicate returns {\bf true} if and
only if it can determine that $p_1$ dominates $p_2$.  The applicability
criteria define the class of utility functions and the structure of the
prospects that the algorithm is designed for.

A sample {\sc urp} dominance test specification is depicted in
figure~\ref{d-test-s}.  It may be considered for outcomes measured on
{\it interval} scales (explained below in section~\ref{measure-discussion}).
The input prospects must be described by {\it simple} probability
distributions.
Though these are the only kinds of prospects supported in {\sc urp},
it would undoubtedly prove useful to describe uncertain outcomes
with distributions having analytical (possibly continuous) forms.  Several
dominance algorithms in the literature are specifically designed for
probability distributions of particular parametric classes (normal or
log-normal, for example).

\begin{figure}[htbp]
\begin{tt}
\begin{verbatim}
   (def-dominance-test  SECOND-ORDER
     :source             "Fishburn and Vickson"
     :outcome-type       '(interval)
     :prob-dist-type     'simple
     :preconditions      '(:totally-ordered?)
     :utility-conditions '(monotonic risk-averse)
     :algorithm          'second-order-dom?)
\end{verbatim}
\end{tt}
\caption{A dominance test specification in {\sc urp}}
\label{d-test-s}
\end{figure}

It is helpful to observe that the utility function criteria given in
table~\ref{s-d-t} are overly restrictive---the dominance tests are actually
applicable under more general circumstances.  For example, first-order
dominance is applicable whenever our specification for $u$ gives a total
ordering on the outcomes (or at least those appearing in the prospects under
consideration).  Thus, the first-order conditions are
satisfied by monotonically decreasing utility functions, and even by
some functions that are nonmonotonic but nevertheless order the relevant
outcomes.

Before running the second-order dominance algorithm (the {\sc lisp}
function named {\tt second-order-dom?}), {\sc urp} must verify that
the outcomes appearing in $p_1$ and $p_2$ are totally ordered in preference by
the incompletely specified $u$.  This precondition is necessary because the
algorithm applies a ``$\succ$'' predicate in the course of its processing.  In
usual descriptions of the dominance criteria (as above), the condition
{\bf monotonic-increasing} is required so that the program can
substitute the $>$ relation over real numbers for $\succ$.  With a flexible
coding of the algorithm that employs the preference order relation
directly, we avoid this unnecessary requirement.\footnote{In generalizing
these conditions, it is necessary to make sure that the condition is not
otherwise essential to the dominance proof.  In this case the criterion
{\bf monotonic} is substituted for {\bf monotonic-increasing}.  For first-order
dominance monotonicity is not necessary at all.}

The utility conditions specify the class of utility functions $u$ must
belong to, here the {\bf monotonic} (either direction) and {\bf risk-averse}
functions.  These conditions may be tested with the {\sc urp} {\it nec}
predicates associated with the behaviors.

Only a few dominance tests have been specified (and the algorithms coded) for
use by {\sc urp}.  These are the first-, second-, and third-order
dominance classes defined by Fishburn and Vickson~\cite{FishVick}.  {\sc Urp}
also may try ``zero-order'' dominance, which holds only if the worst possible
outcome in $p_1$ is preferred to the best in $p_2$.  This test does not even
require total ordering, just the ability to pick the worst and best from
$p_1$ and $p_2$ and to order that pair.  Naturally, zero-order dominance holds
in only the most trivial of cases.  I would argue, though, that it is useful to
be able to recognize the degree of triviality of a particular case.

These mechanisms, in conjunction with qualitative behavior assertions, are
sufficient to work out the medical decision example of section~\ref{d-testing}.
Applying all of {\sc urp}'s dominance tests to the prospects
represented by the competing strategies results in the
dominance diagram of figure~\ref{d-diagram}.

If none of the applicable dominance tests are sufficient to order the
prospects, {\sc urp} must resort to more general methods.  In the current
state of implementation, this rarely results in a successful dominance proof.

\section{Multiattribute Dominance}

Any discussion of dominance testing in the multiattribute case is
necessarily speculative, since {\sc urp} does not support qualitative
behaviors for multiattribute functions, or any mathematical reasoning
about such functions.  Nevertheless, it is worthwhile to note some of the
promising approaches which may be undertaken in a more complete preference
modeling system.

Though stochastic dominance research has been mainly concerned with the
unidimensional case, recent efforts have extended the techniques to certain
multiattribute situations.  Since the dominance algorithms are associated
with specific forms of the multiattribute decomposition, {\sc urp}'s
reasoning facilities regarding multiattribute structure will be very useful
for selecting appropriate tests.  For example, Mosler~\cite{Mosl} reviews
dominance conditions for additive decompositions\footnote{The meaning of
these terms and {\sc urp}'s facilities for multiattribute decomposition
are described below in chapters \ref{theorem} and~\ref{knowledge-base}.}
and develops criteria for multiplicative and certain multilinear forms.
These latter two forms can be defined in terms of utility independence axioms,
which are prominent concepts in {\sc urp}.

Sarin~\cite{Sari} developed his {\it evaluation and bound} procedure to take
advantage of partial information about the parameters and conditional functions
making up a multiattribute utility function (additive or multiplicative).  The
procedure is particularly useful for deriving bounds on additive forms.  He
found that this partial information was often sufficient to prove dominance in
realistic cases.  This finding is consistent with some psychological
results (such as the study of Schoemaker and Waid~\cite{SchoemakerWaid}),
which suggest that precise numerical weights are often not critical to the
predictive validity of linear models.

Recently, Kirkwood and Sarin~\cite{KirkSari} showed how multiattribute
prospects could be ranked with only ordering information regarding the
parameters of additive or multiplicative functions.  Ordering information is
a particularly useful (and quite weak) type of constraint, since it often
corresponds to ``natural'' qualitative behaviors.

I expect that these results could be incorporated into the {\sc urp}
framework in a similar manner to the single-attribute stochastic dominance
facilities described above.

\chapter[Reasoning with Utility Theorems]
{Reasoning with Multiattribute Utility Theorems}\label{theorem}

In this chapter I describe {\sc urp}'s facilities for representing
and using knowledge about multiattribute utility decompositions to select
a multiattribute utility function.  The structure of theorems that can be
represented in
this framework is defined, and the mechanisms for accomplishing the example
of section~\ref{m-extension} are explained.

These explanations may be excessively detailed at times, particularly in
the discussions of theorem interpretation and set-membership constraint
propagation (section~\ref{interpretation}).  The reader is encouraged to skim
over sections which seem to be at a low level of description.

\section{Representing Independence Axioms}

An independence axiom is a relation on attribute sets that restricts the
possible interactions of preferences over outcomes described by those
attributes.  The rich axiomatic structure of multiattribute utility theory
is one of its strongest attractions and one of the greatest motivations
for this approach.   As the fundamental building blocks for reasoning about
utility structures, independence axioms play a central role in {\sc urp}.
Representation and manipulation of these objects has been an important focus
of {\sc urp}'s design.

\subsection{Axiom Schemata}\label{axiom-rep}

Figure~\ref{axiom-schema} depicts a typical independence axiom schema.  There
are 22 axioms known to {\sc urp}, but
not all of these are actually used in theorems.  A complete list of
these is given in appendix~\ref{schema-ax}; descriptions of the axioms
appear in the next chapter.  The source
and definition slots contain information strictly for human eyes.  Other slots
hold specifications for argument types, logical properties, and relations
to other axioms.

\renewcommand{\baselinestretch}{1.0}
\large
\normalsize

\begin{figure}[htbp]
\begin{tt}
\begin{tabbing}
mmm\= (def\= :special-case-of '(\= \+ \kill
(defaxiom 'utility-independence \\
\> :source ``Keeney \& Raiffa p.\ 284'' \\
\> :definition {\it textual definition} \\
\> :special-case-of '(preferential-independence \\
\>\> generalized-utility-independence \\
\>\> interpolation-independence) \\
\> :arg-count 2 \\
\> :arg-relns '((exclusive-nonempty-subsets 1 2)) \\
\> :rel-prop nil)
\end{tabbing}
\end{tt}
\caption{A sample axiom schema}\label{axiom-schema}
\end{figure}

\renewcommand{\baselinestretch}{1.1}
\large
\normalsize

The {\bf arg-count} and {\bf arg-relns} slots specify the syntactically legal
arguments to the relation.  For example, utility independence is a relation
of two attribute sets, which must be exclusive and nonempty.  This information
is used to type-check user assertions, and to constrain the generation of
subgoals during theorem interpretation (described below).

The {\bf special-case-of} list enumerates the independence axioms that are
strict generalizations of the axiom.  Using this, {\sc urp} can conclude, for
example, that
\begin{quote}
({\bf utility-independence} $Y$ $Z$) $\Rightarrow$ ({\bf preferential-independence} $Y$ $Z$)
\end{quote}
for any $Y$ and $Z$.  {\sc Urp} only makes such deductions, however, when the
more general relation is an active goal.  The special-case-of mechanism is much
more efficient than using separate theorems for each special case.

The final slot is used to specify any special properties of the relation which
may be exploited for more efficient reasoning.  Valid {\bf rel-prop}s include
symmetry, transitivity, and other relation properties of that ilk.

\subsection[Axioms as {\sc Rup} Propositions]{Axioms as R{\sc UP} Propositions}

All inferences about independence axioms are performed in {\sc rup}.  Axiom
instances exist as nodes in the truth maintenance system, with the name of
the axiom serving as the predicate
name.  Logical relations between the nodes are
set up by {\sc urp}, either by noticers corresponding to special-case-of
conditions and rel-props, or during theorem interpretation.

Assertions and retractions of independence conditions are handled directly by
{\sc rup}, with certain events in the data base triggering conditions in
{\sc urp}.  {\sc Rup}'s dependency-tracing facility is also useful for
generating justifications for the program's conclusions.

\section{Representing Theorems}\label{theorem-rep}

Multiattribute utility theorems make up a large part of the utility-theoretic
knowledge used by {\sc urp}.   These theorems, developed by
researchers over the past fifteen years or so, relate combinations of
independence axioms to multiattribute utility forms.  Many of the theorems
can be found in review articles by Farquhar \cite{Farq77}~\cite{Farq80} (with
a theoretical emphasis), the textbook of Keeney and Raiffa~\cite{KeenRaif}
(a more methodological treatment), and separately throughout the literature.

I have developed a representation language for specifying these theorems
so that they can be interpreted by {\sc urp}.  There were three principal
language design objectives: flexibility, interpretability, and clarity.
The first objective refers to the desire to be able to represent a large
portion of the available utility theorems.  Second, the language should express
theorems in a manner easily interpreted by {\sc urp}.  Finally, they should
be fairly easy to read by humans.  The result is a simple language with
a highly constrained logic-like/{\sc lisp}-ish syntax, which tries as much
as possible to state the theorems as they appear in the literature.

An example of an {\sc urp} theorem is shown in figure~\ref{sample-theorem}.
This theorem is used by the program to derive utility independence
relations from others already known to the system.  It corresponds to
theorem~6.7 of Keeney and Raiffa, and resembles their language quite
closely.  The rest of the theorems are given in
appendix~\ref{theorem-ax}.  Chapter~\ref{knowledge-base} contains
descriptions of the content of the theorems.

\renewcommand{\baselinestretch}{1.0}
\begin{figure}[htbp]
\begin{small}
\begin{verbatim}
(deftheorem 'theorem009
  :source "Keeney & Raiffa p. 316"
  :premise '(for-some-set X
               (for-some-set Y1 in (subset X)
                  (for-some-set Y2 in (overlapping-subset Y1 X)
                     ((utility-independence Y1 (difference X Y1))
                      (utility-independence Y2 (difference X Y2))))))
  :consequent '((utility-independence (union Y1 Y2)
                                      (difference X (union Y1 Y2)))
                (utility-independence (intersection Y1 Y2)
                                      (difference X (intersection Y1 Y2)))
                (utility-independence (sym-difference Y1 Y2)
                                      (difference X
                                                  (sym-difference Y1 Y2)))
                (utility-independence (difference Y1 Y2)
                                      (difference X (difference Y1 Y2)))
                (utility-independence (difference Y2 Y1)
                                      (difference X (difference Y2 Y1)))))
\end{verbatim}
\end{small}
\caption{A sample {\sc urp} multiattribute utility theorem}
\label{sample-theorem}
\end{figure}
\renewcommand{\baselinestretch}{1.1}
\large
\normalsize

Here I will only point out some of the main features of the language.
A theorem consists of a premise and a consequent, each of which specifies
a collection of axioms.  The defining expressions may contain variables,
either free or bound by universal or existential quantifiers.  Variables
stand for either attributes or sets of attributes, distinguished by
context.  Expressions also contain axiom names and constraint terms
(union, difference, and overlapping-subset, for example).

In theorem009, {\tt X} {\tt Y1} and {\tt Y2} are existentially quantified set
variables.  The consequent
clause consists of the conjunction of five utility independence axioms,
which contain no variables not appearing in the premise.  {\sc Urp} can
make an inference from this theorem if it can find bindings of {\tt Y1},
{\tt Y2}, and {\tt X} which satisfy the premise and the type constraints of
the consequents.  In that case, it would
conclude each of the five consequents computed from those bindings.

The constraint expressions may appear in quantification domains or in
arguments to the axioms.  An expression consisting of a constraint name and
$k$ arguments can be thought of as a $(k+1)$-ary relation holding on the
arguments and the value of the expression.  For quantification domains
any relation is usually valid, but for axiom arguments the value must be
a function of the expression arguments.\footnote{This is not strictly required,
since typing information implicit in the axiom arguments may be sufficient
to uniquely determine the expression's value even if the expression itself
is not.}

\section{Goal-directed Inference}\label{interpretation}

The theorem specification language does not restrict the direction of
{\sc urp}'s reasoning about the theorems.  While a forward-chaining
interpretation
of the theorems is easiest, when used exclusively it will result in too many
inferences which
are redundant or irrelevant with respect to the particular problem
at hand.  The alternative is for the program to reason backward from the goals
it is trying to prove.  While a backward-chaining approach is prone to the same
combinatorial
problems, it seems to be more controllable for the types of problems {\sc urp}
is faced with.  Therefore, {\sc urp}
contains a fairly sophisticated facility for generating subgoals to pursue
when presented with a theorem and a higher-level goal.

\subsection{Interpreting Theorems}

Interpretation of a theorem in a context consists of reducing the premise and
consequent to conjunctions of axiom instances.  Such a reduction can
be readily converted to a logical implication in {\sc rup}.  Often, a
single interpretation operation in {\sc urp} will result in several of
these reductions.

This reduction is accomplished by binding the theorem variables to the
attributes and sets appropriate for the reasoning context, and instantiating
the relations appearing in the arguments of the utility axioms.  Naturally,
the bindings and relations must satisfy the logical structure of the theorem
clauses.  The theorem interpretation problem can thus be stated succinctly
as follows: given a theorem and some binding constraints, find all
distinct conjunctions of legal axiom instances that satisfy the logical
structure
of the theorem.  Distinctness is defined in terms of the effect of adding
the implication constraint to {\sc rup}'s database.\footnote{But we can test
for distinctness without using {\sc rup}.}

The solution cannot be computed directly since the constraint terms do not
generally have inverse functions.  Exhaustive enumeration of variable bindings
is also out of the
question since the number of such bindings is exponential in the number of
attributes.  Therefore, {\sc urp} has resorted to a fairly complex mechanism
based on constraint propagation to generate the variable bindings.  The
mechanism is fully implemented as described in the next section.

\subsection{Set-Membership Constraint Propagation}\label{m-constraint}

As {\sc urp} interprets a theorem, each variable it encounters becomes a node
in a constraint propagation network.  There are two types of nodes,
representing sets and elements (in our domain, the elements are always utility
attributes).  For most of this discussion we will consider only set nodes.

In its least constrained state, a set may be any subset of the attributes.
Since we know the $n$ attributes at theorem interpretation time, it would
be possible to enumerate these $2^n$ possibilities.  Their number decreases
markedly with partial information about which elements
are in or outside of the set.  To represent this partial information, each node
contains an {\bf in} and
an {\bf out} list, which hold the elements that are known to be in each
of these categories.  A set node is maximally constrained when all of the
elements in the universe appear in either its {\bf in} or {\bf out} list; this
uniquely determines the set it represents.  Naturally, an element cannot be on
both lists of the same set node.

Nodes also maintain upper and lower bounds on their cardinality ({\bf max-size}
and {\bf min-size}, respectively).  Cardinality is restricted directly by the
size of the universe and the {\bf in} and {\bf out} lists, and also indirectly
through external constraints.  For example, axiom arguments are usually
required to be nonempty attribute sets.  Such external constraints are often
useful for determining set membership through elimination reasoning.

\subsubsection*{Constraints}

In the network, set nodes are connected by constraints---objects which enforce
some relation among the sets they connect.  These relations restrict the
combinations of elements each set may contain.  The two primitive constraints
are {\bf union} and {\bf complement}; all of the other terms appearing in
theorems are defined in terms of these.  Often, it is necessary to create
intermediate set nodes (which do not correspond to any variable) in order to
build the more complex constraints.  The complex constraints currently defined
are given in appendix~\ref{constraint-appendix}.

Let us look, for example, at the {\bf union} constraint.  The expression
({\bf union} {\tt Y1 Y2}) denotes a set $Z$ such that $Z = Y_1 \cup Y_2$.  Say
that we indeed have three nodes in our network labeled {\tt Y1}, {\tt Y2}, and
{\tt Z}, and a {\bf union} constraint connecting them in that manner.  The
constraint enforces the logical properties given in figure~\ref{union-f}.
The predicates {\it in} and {\it out} used in the figure denote the presence of
an element on the {\bf in} or {\bf out} list, respectively, and the functions
{\it max-size} and {\it min-size} give cardinality bounds on the set.

\renewcommand{\baselinestretch}{1.0}
\large
\normalsize

\begin{figure}[htbp]
For any $a$:
\begin{enumerate}
\item $in({\tt Y1},a) \rightarrow in({\tt Z},a)$
\item $in({\tt Y2},a) \rightarrow in({\tt Z},a)$
\item $out({\tt Z},a) \rightarrow \left[ out({\tt Y1},a) \wedge out({\tt Y2},a)\right]$ \label{out-condition}
\item $\left[ out({\tt Y1},a) \wedge out({\tt Y2},a)\right] \rightarrow out({\tt Z},a)$
\item $\left[ in({\tt Z},a) \wedge out({\tt Y1},a)\right] \rightarrow in({\tt Y2},a)$
\item $\left[ in({\tt Z},a) \wedge out({\tt Y2},a)\right] \rightarrow in({\tt Y1},a)$
\item {\it min-size}({\tt Z}) $\geq$ MAX [{\it min-size}({\tt Y1}),{\it min-size}({\tt Y2})]
\item {\it max-size}({\tt Y1}) $\leq$ {\it max-size}({\tt Z})
\item {\it max-size}({\tt Y2}) $\leq$ {\it max-size}({\tt Z})
\item {\it max-size}({\tt Z}) $\leq$ {\it max-size}({\tt Y1}) $+$ {\it max-size}({\tt Y2})
\end{enumerate}
\caption{Properties enforced by the {\bf union} constraint,
	${\tt Z} = {\tt Y1} \cup {\tt Y2}$}
\label{union-f}
\end{figure}
\renewcommand{\baselinestretch}{1.1}
\large
\normalsize

The constraint is enforced by propagation.  Whenever a set node adds an element
to either the {\bf in} or {\bf out} list, it communicates that fact to each
constraint it participates in.  The {\bf union} constraint, in turn, checks
each of the above relations which may have been affected by the change, and
performs any changes to the set nodes necessary to satisfy the condition.
Since changes are only made in the direction of further constraint (adding
elements to the {\bf in} or {\bf out} lists, tightening the cardinality
bounds), the set node operations are determined unambiguously.

The list of properties enforced by the {\bf complement} constraint is easily
constructed by analogy to {\bf union}.

This constraint propagation scheme was inspired by the network paradigm of
Sussman and Steele~\cite{Suss}, and bears a close resemblance to the
type of constraint propagation developed by Waltz~\cite{Walt}.  The
similarity to Waltz is in the meaning of the nodes of the network.  A
set node really represents a space of possible sets restricted by the
{\bf in} and {\bf out} lists and the cardinality bounds.  As in Waltz's
line-labeling domain, our combinatorial space is represented compactly,
and small incremental restrictions in a single node often reduce the
overall size of this space substantially.

The theorem language also provides for variables and constraints that
refer to single attributes and relate them to sets.  The mechanisms for
dealing with these are similar to those dealing with sets, but are more
complex.  This additional complexity arises because it is necessary to
maintain separate contexts corresponding to the possible bindings of
universally
quantified attribute variables.  I will not discuss this mechanism in any
detail beyond the simple claim that it works for all of {\sc urp}'s
theorems.

\subsubsection*{Hypothetical Reasoning}

As we will see in the example, it is sometimes necessary to make tentative
assertions about set membership, due to the incompleteness of our constraint
reasoning technique.  This incompleteness arises in two ways.  The first is
the limited expressive power of our representation for sets.  With only
{\bf in} and {\bf out} lists and cardinality bounds we cannot in general
express disjunctions of membership relations.  For example, it is not
possible to say ``$a \in S \vee b \in S$,'' unless by coincidence this is
required by cardinality bounds.  Such a condition may be implied by the
network (in that assertions that one is {\it out} will result in the other
being placed {\it in}\/), but is not observable from the set node in isolation.

The other source of incompleteness is the locality of the constraints.
Suppose, for example, we have three {\bf union} constraints:
\begin{enumerate}
\item $A\cup B = S_1$
\item $A\cup C = S_1$
\item $B\cup C = S_2$
\end{enumerate}
and are told that the element $a$ is a member of the set $S_2$ but does not
appear in $A$.  A global analysis of the system would result in the conclusion
that $a$ must be a member of $B$, $C$, and $S_1$, since all elements not in
$A$ must be in both or neither of $B$ and $C$.  Examination  of each constraint
individually, on the other hand, does not lead to this conclusion.

We can solve this problem with hypothetical reasoning.  If we arbitrarily
hypothesized in the above example the relation $out(B,a)$, the system would
go on to conclude $out(S_1,a)$, $out(C,a)$, and therefore $out(S_2,a)$ from
the local constraints.  This last conclusion, however, contradicts one of
the original specifications.  Since all of this reasoning arose from the
$out(B,a)$ assumption, we are allowed to withdraw all of these conclusions
and assert the assumption's negation, $in(B,a)$, as well as all it implies.

Unfortunately, not all of these difficulties are resolved with single
assumptions.  In {\sc urp}'s current implementation, the constraint system
maintains a stack of hypothesis levels, and backtracks chronologically when
contradictions arise.  A dependency-directed backtracking mechanism would be
much more elegant and efficient, but the expected benefit was not deemed worth
the extra implementation effort in the short run.  After all, this thesis is
supposed to be about preferences, not set membership.

\subsection{An Example Theorem Interpretation}

We are now ready to work through a small example demonstrating theorem
interpretation.  We will use theorem009, displayed earlier in figure
\ref{sample-theorem}.  For the example, we will only look at the first
consequent clause: the one with ({\bf union} {\tt Y1}~{\tt Y2}) as its
first argument.  Suppose our current goal is to conclude
\begin{quote}
({\bf utility-independence} ($X_1$ $X_2$ $X_3$) ($X_4$ $X_5$))
\end{quote}
where $X_1,\ldots,X_5$ are utility attributes (not necessarily the only ones).
The interpretation task is to generate all possible bindings for {\tt Y1},
{\tt Y2}, and {\tt X} which satisfy the premise pattern of theorem009.

The interpretation module would first parse the theorem and set up a
set-membership constraint propagation network.  This network contains set nodes
for {\tt Y1}, {\tt Y2}, and~{\tt X}, as well some internal nodes created
during unification or in decomposing complex constraints.  For this example,
we need two internal nodes
\begin{itemize}
\item $A_1 = \{X_1,X_2,X_3\}$
\item $A_2 = \{X_4,X_5\}$
\end{itemize}
to stand for the arguments to the goal axiom (there will be other internal
nodes as well, but these appear at a lower level of description).  The network
is defined by the following relations:
\begin{itemize}
\item {\it union}$(Y_1,Y_2,A_1)$
\item {\it difference}$(X,A_1,A_2)$
\item {\it subset}$(Y_1,X)$
\item {\it overlapping-subset}$(Y_2,Y_1,X)$
\end{itemize}
which are all defined in terms of the primitive constraints {\bf union} and
{\bf complement}.

Figure~\ref{network-f} illustrates the network and the propagation of
values.  The network starts with the definitions for $A_1$ and $A_2$ as given,
and proceeds to fill in as much of the table as possible.  Propagation
through the {\bf union} constraint results in $X_4$ and $X_5$ being placed
{\it out} of $Y_1$ and $Y_2$, by condition~\ref{out-condition} of
figure~\ref{union-f}.  Similarly, $X_4$ and $X_5$ must be {\it in} $X$ since
they are {\it in} $A_2$ and $X - A_1 = A_2$.  These are the only conclusions
possible from local propagation.  Employing hypothetical reasoning, however,
we are able to show by contradiction that $X_1$, $X_2$, and $X_3$ must be
{\it in} $X$.

\begin{figure}[htbp]
\begin{large}
\begin{tabular}{lr|ccccc|}
Constraint Network & --- & $X_1$? & $X_2$? & $X_3$? & $X_4$? & $X_5$? \\ [.15cm]
\hline & & & & & & \multicolumn{1}{c|}{}
\\ [.5cm]
& $\bullet A_1$ & IN & IN & IN & OUT & OUT \\ [1cm]
{\sc diff} & $\bullet A_2$ & OUT & OUT & OUT & IN & IN \\ [1cm]
\hspace{3em} {\sc union} & $\bullet Y_1$ & ? & ? & ? & out & out \\ [1cm]
\hspace{2em} {\sc o-s} & $\bullet Y_2$ & ? & ? & ? & out & out \\ [1cm]
& $\bullet X$ & (in) & (in) & (in) & in & in \\ [.2cm]
\hline
\multicolumn{7}{r|}{\small IN: given;\hspace{1em} in: derived from propagation;\hspace{1em} (in): derived by contradiction}
\end{tabular}
\end{large}
\caption{Restricting possible bindings using constraint propagation}
\label{network-f}
\end{figure}

This leaves only six unknowns in the table, and therefore $2^6$ possible
bindings for the three theorem variables.  This is a substantial improvement
over the $2^{15}$ enumerations required by the most naive
approach.\footnote{The
improvement is actually better, since the universe of attributes may have been
larger than the five appearing in this goal.  Such additional attributes would
not contribute to the complexity of the constraint computation, but would
enormously increase the cost of a straight enumeration.}  Of these
$2^6$ possible combinations, it turns out that only six are consistent with the
network.  Note that we do not have to enumerate even these $2^6$, since
the space is pruned as we notice contradictions arising from partial
assignments.  As
mentioned above, a mechanism that recorded dependencies would perform even
better.

The interpretation is completed as we instantiate the theorem premise for
each possible binding.  At this point we notice that the six consistent
bindings yield only three distinct axiom conjunctions.  The resulting
implications are added to {\sc rup}'s database, and the appropriate subgoals
are recorded in {\sc urp}'s control structure.  The binding patterns are
memoized, so that interpretation of the theorem for a goal with the same
argument structure (for this example a {\bf utility-independence} axiom
with three attributes in the first argument and two in the second) may
proceed without requiring any of this set-membership reasoning.

\section{Control of Reasoning}\label{control}

Given a set of independence axioms and a goal axiom to establish, the control
task faced by the system is to choose a path through the {\sc urp} theorems
that can prove the desired result.
{\sc Urp} has no set overall control structure, since it has no set mode of
usage.  The default control structure can perform the sort of utility function
choice
task demonstrated in section~\ref{m-extension}.  The knowledge structures and
subgoaling
(that is, theorem interpretation) procedures have been designed to work within
a wide variety of conceivable reasoning strategies.

\subsection{Default Control Mechanisms}

Typically, the top level goal in reasoning with multiattribute utility theorems
would be to find a functional form for a set of attributes (the {\it find}
task), or to test the validity of a particular functional form (the
{\it verify} task).  {\sc Urp}
maintains a goal structure, which is a tree when traversed in terms of
subgoal expressions, but will generally contain cycles when traversed through
individual axioms in the expressions.  Goals may be proposed by the user,
generated as subgoals during theorem interpretation, or suggested by other
modules of {\sc urp} itself.  In a complete system, the mathematical reasoning
facility would often request that a particular functional form be pursued.

Search of the goal graph may also be controlled in various ways.  {\sc Urp}
may proceed on its own based on a rudimentary best-first heuristic, by explicit
direction from the user, or through other sorts of heuristic control.
The implemented {\sc urp} relies mainly on the best-first method, though it is
relatively simple to exert manual control or to implement top-level driving
procedures to focus the search according to some pattern.

Control for the {\it find} task is a bit more open-ended than for {\it verify}.
Usually, a {\it find} task will contain several instances of {\it verify}
tasks as subgoals.  Under the default control procedure, {\sc urp} first
tries to establish that one of the $n$-attribute functional forms is valid
over the whole universe of attributes.  To do so, it successively applies
{\it verify} to the axioms representing the multiattribute forms.  In
restricted situations, it will notice that certain forms are hopeless due
to the absence of particular classes of premises.  Increasing the
sophistication of this mechanism would go a long way toward improving the
efficiency of {\sc urp} in the decomposition task.

\subsection{Hierarchical Decomposition}

Failing to find a direct decomposition after some effort (or failing to find
a sufficiently simple one), the system uses
forward reasoning to assert a two-attribute form from one of the independence
conditions that is already known to the system (as a premise or by
inference).\footnote{As described in the next chapter, several two-argument
independence axioms directly validate two-attribute utility functions.  These
forms are given in appendix section~\ref{2-forms}.}
This decomposition form holds over two vector attributes corresponding to
the arguments of the independence condition used to justify the form.  For
example, to use the independence condition
\begin{quote}
({\bf value-independence} ($X_1$ $X_2$ $X_3$) ($X_4$ $X_5$))
\end{quote}
for a binary decomposition, {\sc urp} would introduce the two vector attributes
$W_0=X_1\times X_2\times X_3$ and $W_1=X_4\times X_5$.  {\sc Urp} then
pursues as subgoals the tasks of finding multiattribute forms for $W_0$ and
$W_1$.  If this search is unsuccessful, {\sc urp} can try a different binary
decomposition or pursue the $n$-attribute form further.

In restarting the search for a multiattribute form for the original set of
attributes, it may be useful to automatically aggregate sets of attributes
for which forms are known.  For example, if a form for $W_0$ above was
determined, our new problem is to find a form for $\{W_0,X_4,X_5\}$.  Note
that $W_0$ is treated just like its expansion in determining the truth value
of axioms it appears in.  However, the vector is treated like a single
attribute for the purposes of set operations in theorem interpretation.
The distinction between vectors and sets of attributes is defined more
precisely in section~\ref{at}.

\subsection{Heuristic Control}\label{h-control}

The possibility of providing some kind of declarative heuristic control
language for defining search strategies has not been adequately explored.  Such
a capability would be desired, since the implemented scheme follows
many obviously useless paths.  There is reason to think that heuristics could
help, because there is usually some structure to the kinds of axioms that are
asserted, and to combinations of theorems that bridge commonly-occuring
inference gaps.  And providing this language should not be very difficult,
since the theorem interpreter is coded to allow a fine-grained control over
inference primitives.

One weakness of the implemented scheme is that the system cannot recognize when
it is performing hopeless search.  This is not a problem if axioms are actually
asserted to be not true; {\sc urp} will not bother trying to verify a
proposition it can prove to be false.\footnote{It is not clear, though, that
{\sc urp} is as proficient at finding falsity proofs as at finding
validating proofs.}  The major difficulty is when there is a lack of asserted
axioms.  This is where forward-directed control and higher-level heuristic
knowledge will become useful for containing the excessive backtracking, or at
least for initially focusing the search.  

Despite these problems, performance appears to be acceptable.  In the
examples tested, the system verifies true propositions with a reasonable amount
of effort.  Once a significant piece of the proposition space has been
explored, retraction and addition of new axioms are handled quickly.

\chapter[The Decomposition Knowledge Base]
{The Multiattribute Decomposition Knowledge Base}\label{knowledge-base}

One of the motivations for this project was the opportunity to develop a
formalization of utility-theoretic knowledge in a uniform representation.  In
constructing the {\sc urp} knowledge base,
I have tried to capture this knowledge in a form that would lead to competent
and efficient model construction while at the same time preserving the
structure of the field as reflected in its literature.  This chapter is an
attempt to describe the contents of the portion of {\sc urp}'s knowledge base
dealing with multiattribute decomposition.  It serves to delimit the extent of
the program's knowledge, with explanations for the terminology used and
rationale for some important design decisions.

Because the discussion will be focused on issues of utility theory rather than
on reasoning mechanisms or representations, the reader who is not
primarily concerned with utility should not hesitate to skip this chapter.  The
intended audience consists of those who are interested in examining an encoding
of utility-theoretic
concepts, or others who may want to validate, correct, modify, or extend
the {\sc urp} knowledge base.  It is provided to
document the components of utility theory selected, and to justify the
structures chosen to embody those components.  While a knowledge-based system
should ideally be ``self-documenting,'' this is rarely the case in actuality,
and {\sc urp} is no exception.

A note on the status of the implementation: all of the concepts described
in this chapter have been represented in the knowledge base (given in
appendices \ref{schema-ax}, \ref{theorem-ax},
and~\ref{m-form-ax}), and a working interpreter for the theorem language
exists.  The capability of the system is described in
sections \ref{interpretation} and~\ref{control}.  Achieving the performance
specified in section~\ref{task} below would require further work.

\section{Formalization}

It may be argued that the knowledge of multiattribute utility theory is already
formalized.
The basic results of the field are expressed in mathematical terminology that
is standard and unambiguous.  Nevertheless, there is a great difference between
formal description for human interpretation and formal description for
automatic interpretation by computer.  In writing a formal description for a
human, we can be comfortable in assuming a certain forgiveness for minor abuses
of the strictest conventions.  Some of my points in this section and further
below will have the flavor of nitpicking; in such cases recall that computers
are the most notorious of nitpickers.

A formal description for automatic interpretation by computer must
be coupled with a specification for a procedure which operates on that
description.  Any meaning assigned to the declarative representation only
arises from how it is manipulated by that procedure.  For our purposes, it will
suffice to talk about the meaning of a representation in terms of the
inferences that can be made by {\sc urp} as a result of its inclusion in the
knowledge base.  To be clear about what is meant by an inference, I will try to
specify precisely the classes of questions {\sc urp} is expected to answer
about each segment of its knowledge base.

This formalization exercise is a necessary part of building a system like
{\sc urp}.  But the development of a utility-theoretic
knowledge base has benefits independent of its use by a consultation
program.  At the very least it enforces consistent terminology for its
concepts.  Although this is usually a minor problem,\footnote{An inevitable
one for any young, dynamic discipline.  Utility theory
probably suffers less from this malady than most other technical fields.}
there is potential for confusion in concepts with more than one name
(for example, value and additive independence, multilinear and quasi-additive
forms) names with more than one concept, or similar/dissimilar names for
dissimilar/similar concepts.

A related issue is the burial of knowledge in terminology.  In a literature
designed for human interpretation, part of the meaning of concepts may be
contained in the names used to describe them.  In a computer program, the
name is just a symbol like any other, with no linguistic connection to
other knowledge.  All concept connections are explicit.

Another strict requirement for a computer representation is a consistent
notion of data types.  In the literature it is possible to refer to objects
such as attribute sets or independence conditions without being perfectly
precise about their semantic types.  In the discussion below
I will demonstrate the possible ambiguities or inconsistencies that may arise
in such cases.
Note that in general these ambiguities would present no problem to any
reasoner with common sense (which includes most humans but not {\sc urp}).

In developing a computer representation there is a strong incentive to keep
the interpreter as simple and as general as possible.  This in turn motivates
the drive for a well-structured and uniform knowledge representation, since
structure in the representation can often substitute directly for special-case
mechanisms in the interpreter.  This is desirable, because the declarative
representation will be much more transparent than the interpreting procedure.
Therefore, the representational formalism developed may contain structure which
was not apparent in the original descriptions.  An example of this is the means
by which vector
attributes combine with conditional independence concepts to yield hierarchical
decompositions without special procedures for that concept.

The segment of utility-theoretic knowledge dealing with decomposition of
multiattribute functions is the segment which I have had the most success in
formalizing.  This is undoubtedly due to its rich axiomatic structure---the
characteristic which first suggested this undertaking, in fact.
Experience in building this knowledge base should be useful for similar
endeavors in other mathematical modeling disciplines.

\section{The Extent of U{\sc RP}'s Knowledge}

\subsection{The Decomposition Task}\label{task}

The task performed by {\sc urp} is best defined by a description of the class
of questions it should be able to answer about multiattribute decomposition.
The questions are expressed in terms of {\sc urp} concepts (that is, axioms
and attributes) and are answered with respect to the theorems contained in the
knowledge base.

Questions are of the following general form:
\begin{tabbing}
mmmm\= Hypothesize:m\= \+ \kill
Given:\> A set of axiom assertions, $G$ \\
Hypothesize:\> A set of axiom assertions, $H$ \\
Question:\> Does $G$ entail $H$? (written $G \vdash H$)
\end{tabbing}

In the most usual case, $H$ will represent some decomposition of the
multiattribute problem culminating in a functional form or a hierarchy of
forms.  An axiom assertion is defined as a pair consisting of an instance of
an {\sc urp} axiom (where the arguments are of correct type) and a value of
{\bf true} or {\bf false}.  The sets $G$ and $H$ may be of any size.  A
question with a null $H$ 
may be construed as ``Is $G$ consistent?''  The analogous interpretation for
a null $G$ would be ``Is $H$ tautological?''  This, however, would never be
the case for a conjunction of {\sc urp} axioms.

The main variation of this question form is to allow one of $G$ or $H$ to be
unspecified or only partially specified.  For unspecified $H$ the task is to
find a decomposition which is entailed by the assertions in $G$.  The user
may fix some constraints on the allowable decompositions, or specify optimality
conditions.  The most obvious optimality condition is to minimize the number
of conditional utility functions and scaling constants to be assessed.
Examples of prespecified constraints include:
\begin{itemize}
\item Restriction to single-attribute conditionals at base-level
\item Prestructuring of hierarchy (specification of all allowable vector
	attributes)
\item Maximum number of scaling constants and/or conditional functions
\end{itemize}

If the user leaves $G$ unspecified, {\sc urp}'s task is to find a minimal
set of axioms that would entail $H$.  As above, the notion of minimality may
be subject to some specification by the user.

A final variation would be to give {\sc urp} two sets such that $G \vdash H$
and ask it to try to weaken $G$ or strengthen $H$ while still preserving the
``$\vdash$'' relation.  This should be substantially easier than finding the
minimal/optimal set in the first place.

I do not claim that {\sc urp} will always be able to find these minimal $G$s
or optimal $H$s, or even that it will even find any that exist.  Though
an exhaustive algorithm would always succeed in finding these, the space
is so large as to require heuristic search techniques.  An {\sc urp}
augmented to handle the ``find'' task should be good enough to answer
questions of the first type with
reasonable efficiency in the majority of cases, and should be fairly
proficient at weakening/strengthening questions of the last type.

The final component of the decomposition task is
explanation.  Given a conclusion that $G \vdash H$, {\sc urp} is able
to trace its deductions, reporting the theorems employed at each step.

\subsection{Coverage}

{\sc Urp}'s knowledge about multiattribute decompositions has been gathered
from a variety of sources.  The most important of these have been
Keeney and Raiffa \cite{KeenRaif}, Farquhar \cite{Farq77},
Bell \cite{Bell79b}, and
Fishburn and Keeney \cite{FishKeen74}.  Other sources will be listed in
the sections discussing their specific contributions.

It is difficult to characterize the subset of knowledge that is represented
in {\sc urp}.  I claim that the program completely covers the decomposition
results appearing in chapter six of Keeney and Raiffa's text, in the sense
that it should be able to answer any ``$G \vdash H$?'' question that is
answerable solely by applying theorems from that chapter.  It should also be
able to find answers to
unspecified $G$s and $H$s at least as good as those findable from the text.
All of the independence concepts mentioned
there are expressible in {\sc urp}, and all functional forms are represented.
Hierarchical decomposition using conditional independence is performed without
any prestructuring.  Note, however, that I am not making any claims at the
moment about {\sc urp}'s efficiency in performing this reasoning.  And note
that {\sc urp} only performs the decomposition; it does not assess the
scaling constants and conditional utilities necessary to completely specify 
the function.

The knowledge base also contains many concepts not appearing in Keeney and
Raiffa.  In principle, I believe that this knowledge covers any multiattribute
decomposition that has been used in real applications to date (this does not
include special-purpose decompositions for things like time streams).
Currently, however, I do not claim completeness over any other part
of the literature.

The knowledge base contains considerable redundancy.  In general there are
several paths to the same result ($H$), using different theorems
or the same theorem instantiated for different patterns.  Some theorems, in
fact, could be removed without changing the class of decompositions that
{\sc urp} would be able to determine.  These redundancies are retained because
they often provide shortcuts in {\sc urp}'s inference, or refer to aggregate
concepts that are useful in structuring preferences.  I have generally taken
the attitude that high-level theorems appearing in the literature deserve
inclusion even if their content is subsumed by lower-level theorems because,
after all, some utility theorist had a reason for thinking they were useful.

\section{Attributes}\label{at}

In the standard notation and terminology, we say that the outcome space $X$
is equal to the cross product of the sets of possible values for each
attribute.  That is, $X = X_1 \times \cdots \times X_n$.  In this context it
is clear that each $X_i$ is a set corresponding to an attribute $i$.  It
would seem, then, that an attribute should be referred to by an index
according to which dimension of the outcome space it corresponds.  But in
literature usage the symbol $X_i$ is often used to refer to the attribute
itself.\footnote{Or even to the {\it objective} for which the attribute is a
measure.}  Here $X_i$ is a name for the attribute, not a set.  Using sets
for names would present problems if more than one attribute had the same domain
of values.

A collection of attributes may be referred to as a single {\it vector}
attribute.  The set of values possible for a vector attribute $Y$ is the
cross product of its constituent attributes,
$Y = X_{i_1} \times \cdots \times X_{i_k}$.  But once again, we will take the
symbol $Y$ to be the {\it name} of the vector attribute only.  For
multiattribute decomposition, {\sc urp} treats vector attributes exactly like
scalar attributes.

It is important in {\sc urp} to make a distinction between a vector attribute
and a set of attributes.  The problem arises in using theorems that perform
set operations on the ``arguments'' of independence axioms.  While
conceptually the two objects are identical, in the course of its reasoning
{\sc urp} must distinguish between situations when a symbol $Y$ stands for a
vector attribute and when it stands for a set of attributes.  Only in the
latter case is it permissible to perform set operations on the object.  Also
note that while vector attributes may be nested (that is, it is permissible
to have a vector containing vectors) arbitrarily, the members of attribute sets
are all attributes, not attribute sets (though these attributes may be
vectors.)

One limitation of {\sc urp} that should be remedied is that it does
not provide for {\it subrange} attributes.  A subrange attribute can be used to
indicate that a certain axiom is only applicable over a limited portion of the
outcome space.  Such assertions are a natural generalization of independence
relations over entire attribute value ranges, and form the basis for the
{\it multivalent} decompositions proposed by Farquhar~\cite{Farq81}.
Mechanisms for handling
assertions of independence conditions over intervals would be similar to
{\sc urp}'s facilities for handling assertions of qualitative behaviors
over arbitrary intervals.

\section{Independence Axioms}

Probably the central knowledge base design decision in {\sc urp} was the
separation of knowledge about multiattribute decompositions into independence
conditions, functional forms, and theorems relating them.  The rationale for
this structure is fairly obvious, given the large technical vocabulary
developed for describing these conditions and the large number of papers in
the literature which prove various theorems relating the conditions to each
other and to functional forms.

Sorting through the literature, I found that a wide variety of independence
concepts had been identified, that a few of these seemed most important
(or at least most useful), and that there was some variation in the
terminology or mathematical formalisms used to describe these concepts.  This
variation underscores the potential benefit to be gained from an effort
to build a uniform representation.

An independence axiom is a specification for a relation defined over a fixed
number of {\it arguments} which may be attributes or sets of attributes.  The
type and number of arguments varies among axioms.  Note that in the literature
these axioms are sometimes considered relations on subspaces of the outcome
space, which corresponds to the view of attributes as value domains for
dimensions of that space.

\subsection{special-case-of}

Many of the {\sc urp} independence axioms are linked together by the
{\bf special-case-of} property.  An axiom denoting relation $A$ is a
special case of the axiom denoting relation $B$ if $A \subseteq B$.  Note
that this requires that the two axioms have the same number of arguments, and
that the type restrictions on $A$ are at least as strong as those on
$B$.\footnote{More generally, we would like to allow the arguments of $B$ to
be computable from $A$'s, rather than requiring them to be identical.  This
would be useful
in the case of conditional independence, for example, since there the axiom
is related to a {\it class} of general cases.}

The {\bf special-case-of} property is useful because it lets us make inferences
from the hierarchical structure of the axioms without applying theorems.  In
defining theorems, therefore, we use the weakest version of the axiom in the
premise and the strongest in the consequent.  The results are always applicable
for axioms stronger than the premise and/or weaker than the consequent.

\subsection{rel-prop}

The {\bf rel-prop} list of an axiom contains the special properties of the
relation defined by that axiom.  Possible special properties include symmetry,
transitivity, or other mathematical concepts of relations.  These
properties are not used very much in the {\sc urp} knowledge base.

In sections below I will describe the particular axioms defined in
{\sc urp}.  A complete listing of {\sc urp}'s axiom definitions is given in
appendix~\ref{schema-ax}.

\section{Theorems}

An {\sc urp} theorem specifies a pattern of implications between sets of
axioms.  Theorems are used to capture knowledge that links combinations of
independence conditions to each other and to functional forms.  The two main
components of theorems, the {\it premise} and {\it consequent}, each represent
a conjunction of axioms when the variables are bound to specific legal
values.

Theorems in the
{\sc urp} knowledge base have been drawn from numerous sources.  Many of these
will be discussed in sections below, usually along with the axioms they deal
with.  A complete listing of {\sc urp}'s theorem definitions appears in
appendix~\ref{theorem-ax}.

\subsection*{Restrictions}

Some theorems (and some axioms) are annotated with restrictions on the
applicability of the result.  These restrictions are informal and are never
checked by {\sc urp}.  Usually they refer to highly technical conditions for
which the knowledge base does not contain concepts.  For example, many theorems
and axioms require {\it essentiality} of the attributes (informally,
that they matter to the decision), convexity of the
space of attribute levels, or some other technical condition.  I have not been
consistent in recording all of these qualifications.

\section{Multiattribute Functional Forms}

Functional forms are symbolic specifications for the mathematical functions
which represent different multiattribute decompositions.  Each form is
associated with a particular independence axiom whose truth value determines
its validity for the arguments of that axiom.  The forms can be
instantiated for any number of attributes, including scalars and vectors.
A complete listing
of the functional forms in the {\sc urp} knowledge base is given in
appendix~\ref{m-form-ax}.  Recall that {\sc urp} does not
perform any reasoning based on the mathematical structure specified with those
forms.

\section{Preferential and Utility Independence}

{\it Preferential independence} (PI) and {\it utility independence} (UI) in
{\sc urp} have the standard definitions given in Fishburn and
Keeney~\cite{FishKeen74},
Farquhar~\cite{Farq77}, and elsewhere.  Intuitively, ({\bf PI} $Y$ $Z$) holds
if preferences for certain outcomes described by attribute $Y$ do not depend on
the fixed value of attribute $Z$.  UI expresses the analogous condition for
preferences over lotteries on $Y$.  A more formal expression of these
statements is given below in equations~\ref{ui-imp}
and~\ref{pi-imp} on page~\pageref{ui-imp}.  Members of the
relation are
pairs of mutually exclusive sets of attributes, where the first is PI (or UI)
of the other.  Utility independence is a special case of preferential
independence.

Utility independence is directly connected to a two-attribute utility function,
as described in Fishburn~\cite{Fish74} and
elsewhere.\footnote{Bell~\cite{Bell79b} provides a very useful table which
gives the most important
two-attribute functions in conditional form, along with their associated
independence concepts.}  Since sets of
attributes may be translated to single vector attributes, each UI assertion
can be a step in a hierarchical decomposition of functional forms.

PI and UI are the axioms appearing most commonly in {\sc urp} theorems.
Theorems~1, 2, 5, and 12 relate UI directly to aggregate conditions (see
section~\ref{aggregate} below).  Theorems~9 and 33 build UI
conditions from combinations of other UI conditions.  Theorem~10 is the PI
analog of theorem~9.
Combinations of UI with weaker conditions are used to imply other UI conditions
in theorems~18, 19, and 20.  Weaker conditions (including PI) alone are
sufficient for a UI conclusion using theorem~21.  UI appears with implicit
(strong) conditional UI (see section \ref{c-independence}) in
theorems~23, 24, 29, and 30.  Theorems~25 and 26 define various relations among
UI, PI, and their explicit (weak) conditional versions.  The implicit and
explicit forms of conditionalizing are related in theorems~27 and 28.  Recall
that these theorems can be found in appendix~\ref{theorem-ax} in
numerical order.

I have not included the concept of risk independence~\cite{Keen73} in the
knowledge base since it is a special case of utility independence for
increasing, twice-differentiable scalar attributes that does not seem to offer
any stronger conclusions or explanatory power.

\section{Value Independence}

Like PI and UI, {\it value independence} (VI) figures prominently in
{\sc urp}'s knowledge base.  The definition of VI is taken from Fishburn
and Keeney~\cite{FishKeen74}, and is equivalent to definitions appearing
elsewhere.  Informally, VI holds between two attributes if only their marginal
probability distributions are relevant.  The concept of VI appears to be
equivalent to additive independence
as described in Keeney and Raiffa~\cite{KeenRaif}.  Value independence is
a symmetric\footnote{In fact, VI is the
only relation with a special {\bf rel-prop} defined in {\sc urp}.
Relation properties, like {\bf special-case-of} properties, simplify the
reasoning
by bypassing the theorem application mechanism.} relation on pairs of mutually
exclusive attribute sets, and is a special case of UI (and of PI, etc., since
{\bf special-case-of} is a transitive property).  This differs from usages of
VI where the relation is over an unspecified number of attribute sets (such as
the definition in Farquhar~\cite{Farq77} and the usage of additive
independence in Keeney and Raiffa~\cite{KeenRaif}).  {\sc Urp} uses the
name {\it additive independence} for the concept of VI over sets of (possibly
vector) attributes.

Theorem~17 provides a way to build VI assertions from other VI assertions
combined with a weaker axiom.  VI is related to a functional form in theorem
22.

\section{Joint Independence}\label{joint-independence}

In multiattribute decomposition, there is often special relevance to an
independence condition that holds in both directions.  Rather than define
a special axiom and provide theorems defining such conditions, I have built
a construct into the theorem language to facilitate expression of this concept.
Wherever the qualifier ``joint'' precedes the name of an independence
axiom, the expression denotes the conjunction of two relations---one for each
ordering of the arguments.  For example, the expression
({\bf joint utility-independence} $Y$ $Z$) can be considered an abbreviation
for the two expressions ({\bf utility-independence} $Y$ $Z$) and
({\bf utility-independence} $Z$ $Y$).

\section{Conditional Independence}\label{c-independence}

Several independence axioms can be associated with conditioning concepts which
enable consideration of independence conditions among non-exhaustive subsets
of the outcome space.  {\sc Urp} has axioms for conditional VI, UI,
and PI.

Keeney and Raiffa~\cite{KeenRaif} discuss two kinds of conditional
independence.  Consider a partition of the attributes into three nonempty
sets, $Y_1$, $Y_2$, and $Y_3$.  Saying that conditional ``foo'' independence
(FI), for example, holds for $Y_1$ and $Y_2$ given $Y_3$ means that for
{\it any} fixed value
$y_3'\in Y_3$, $Y_1$ is FI of $Y_2$.  An assertion that conditional FI holds
for $Y_1$ and $Y_2$ given
$y_3'$ means that for the {\it particular} value $y_3'\in Y_3$, $Y_1$ is FI of
$Y_2$.  Clearly the first kind of conditional independence is a stronger
assertion.\footnote{Bell~\cite{Bell77} means this strong version when he
refers to conditional utility independence.}

In the {\sc urp} knowledge base, conditional independence is associated with
the weaker version.  It appears to me that there is no real reason to treat
the strong version of conditional FI any differently from FI in the context of
a restricted universe
of attributes.  That is, any conclusions that are derivable from
({\bf FI} $Y_1$ $Y_2$) in a problem where all the attributes are in $Y_1$ and
$Y_2$ are also valid for a problem with additional attributes as long as it is
understood that the result is conditional on ``the rest of the attributes.''
In other words, {\sc urp} treats the implied conditional as if it were working
on a problem of smaller dimension.

{\it Conditional independence} in {\sc urp}, then, is a relation on three
exclusive
sets of attributes.  The assertion ({\bf conditional-FI} $Y_1$ $Y_2$ $Y_3$)
means
that {\it there exists some} $y_3' \in Y_3$ such that $Y_1$ and $Y_2$ are FI
when the rest of the attributes are fixed at that level.  For applying the
theorems, it is not necessary to know what that level is, just that
it exists.  To assess the functions and scaling constants, however, it is
necessary to know the conditioning value.

This treatment of conditional independence is not a completely
satisfactory one because it does not truly represent the concept of
conditionalization directly.  It was necessary to include separate conditioning
axioms for each independence concept, even though the notion of conditioning
is orthogonal to the concept being conditioned.  Nevertheless, this option
was chosen over the more fundamental change in {\sc urp}'s framework that
would be necessary to avoid the duplication.  Reimplementations of {\sc
urp} should provide a better long run solution.

\section{Weaker Axioms}\label{weak-axioms}

In addition to UI, PI, and VI, Fishburn and Keeney~\cite{FishKeen74}
discuss four axioms that are strictly weaker conditions on preference
interaction.  Two of these, called {\it generalized} PI and UI (GPI and GUI),
are slight modifications of the
base axioms that allow for restricted kinds of choice reversals.  Another paper
by Fishburn and Keeney~\cite{FishKeen75} discusses GUI in greater detail.

GUI appears as one of the consequents of theorem~19.  It is used as a premise
in combination with some PI conditions to conclude some UI conditions in
theorem~21.  Theorem~31 builds GUI conditions from other GUI conditions.
GUI conditions alone are sufficient to validate a multiattribute form in
applications of theorem~32.  GPI axioms do not appear in any
{\sc urp} theorem.

The other two axioms, {\it indifference independence} and {\it weak
indifference
independence} (WII), concern riskless preferences and are less restrictive than
any of the above.  Indifference independence does not appear to be very useful
(and does not appear in any {\sc urp} theorems), but WII seems to be a
valid substitute for PI in many situations.

WII is applied in theorems~17, 18, and 19.  In each case, WII
combines with stronger axioms (VI and UI) to conclude different instances of
these stronger axioms.

\section{Interpolation Independence}\label{interpolation}

{\it Interpolation independence} (II), as described by Bell \cite{Bell78}
\cite{Bell79a} \cite{Bell79b}, is a relatively weak restriction on
the interaction of preferences under risk that nevertheless provides
substantial power in the decomposition of multiattribute utility functions.
Briefly, II holds between $Y$ and $Z$ when the collection of conditional
utility functions for $y$ given $z$ is related by a function of $z$ alone.
This condition is stated more clearly in the assertion of
equation~\ref{ii-imp} on page~\pageref{ii-imp}.
Joint II is directly related to a two-attribute decomposition which is defined
in {\sc urp}, and combinations of joint II conditions are sufficient to justify
the multilinear generalization functional form (theorem~16).

Though {\sc urp} is able to generate these II decompositions, it does not have
the ability to execute the interpolation-based assessment
procedure that Bell~\cite{Bell79a} advocates.  This procedure provides a
way to converge on increasingly accurate representations of the utility
function for cases where II is only an approximation.  {\sc Urp} does not
provide for such approximation techniques, but it is easy to envision an
adaptation which would accommodate their implementation.  This point is
discussed further in section~\ref{algorithms}.

\section{Aggregate Conditions}\label{aggregate}

All of the axioms discussed so far have been binary or ternary relations on
sets of attributes.  It is often useful to specify relations that hold over an
unspecified number of arguments; for this purpose {\sc urp} contains several
axioms whose argument is a single set of attributes.  As always, hierarchy is
maintained by aggregating scalar attributes into vectors.

Many of these axioms relate directly to multiattribute functional forms.
Theorem~1 describes sufficient conditions for applicability of the
{\it multilinear} form.  Sufficient conditions for the {\it multiplicative}
form---a special case of the multilinear form---are given in theorems~3 and 32.
The most usual justification for this form is {\it mutual utility independence}
(MUI), which is a consequent of theorems~2 and 5.  MUI can be used to conclude
individual UI conditions by application of theorem~12.

The additive independence axiom does not appear in any theorems, but is
the precondition for applicability of the additive form for the multiattribute
utility function.  Additive independence is a special case of MUI.

Theorem~14 relates {\it generalized bilateral independence} to the
{\it bilateral} form, but these concepts are not well-developed in {\sc urp}.
The same goes for the concept of an {\it additive value function}, the
consequent of theorem~13.  Finally, the {\it multilinear generalization} form
is valid under combinations of joint interpolation independence conditions, as
defined in theorem~16.

\section{Axioms not Implemented}

There remain a few {\sc urp} axioms that do not figure in any of
{\sc urp}'s reasoning, but are retained for future expansion of the knowledge
base.  It is expected that indifference independence, GPI, {\it bilateral
independence}, {\it parametric independence}~\cite{Kirk}, and
{\it mutual preferential independence} will become useful as
the {\sc urp} knowledge base is developed.

A further gap exists in independence conditions and decomposition approaches
that are entirely absent from {\sc urp}.  Of these, the multivalent structures
\cite{Farq81} mentioned above and fractional hypercube models
\cite{Farq75} probably merit some attention.  Another possibility
is risk invariance as developed by Willig~\cite{Will}.  The additive
and multiplicative generalizations described by Bell~\cite{Bell79a} would
also be useful, but {\sc urp} cannot express the preconditions
concerning corner constants.

The multiattribute decomposition knowledge base (as well as the rest of
{\sc urp}) is in a prototype stage.  I like to view the implemented
version as only a basis for a potentially more solid and complete encapsulation
of important results from utility theory.

\section{Assessing the Decomposed Function}

As mentioned earlier, {\sc urp} contains a substantial amount of expertise
in choosing a multiattribute decomposition, but almost none regarding
assessment of the resulting function.  In order for the program to be useful
to a utility analyst, it should provide a lot more help in this portion of
the model construction task.  The absence of this capability in the implemented
{\sc urp} system is due to lack of time; the present framework should be able
to accommodate the necessary knowledge.  In this section I examine the
possibilities for inclusion of better multiattribute assessment facilities
within {\sc urp}.  Issues of single-attribute assessment are the subject
of chapter~\ref{assess-c}.

\subsection{Assessing Scaling Constants and Conditional Functions}

The only representation of scaling constants and conditional
functions in {\sc urp} is in the specification language for multiattribute
functional forms.  The specification only defines these objects as components
of the multiattribute decomposition, specifying their values in terms of
lower level objects such as evaluations of the function at specific points.
The specification does not provide any clue about how to go about finding or
constraining the values for these objects.

An automatic assessment facility would model-independent definitions for
these
components, including partial procedures for determining their values.
Assessment of conditional utility functions should
be a straightforward modification of the methods for single attribute
assessment described in chapter~\ref{assess-c}.

\subsection{Relation of Axioms to Conditional Functions}

As far as {\sc urp} is concerned, independence axioms are only
important to the extent that they may be applied in decomposition theorems.
Since these axioms are often defined in terms of what they imply for
conditional preference orderings, it seems that we are missing important
information by limiting their use in this fashion.  For example, the
proposition ({\bf UI} $Y$ $Z$) has the assertional import of
\begin{equation}\label{ui-imp}
\forall y\in Y, \forall z',z''\in Z \left[ u(y|z') = u(y|z'')\right]
\end{equation}
An assertion of ({\bf PI} $Y$ $Z$) means
\begin{equation}\label{pi-imp}
\forall y',y''\in Y, \forall z',z''\in Z \left[ u(y',z') > u(y'',z')
	\Rightarrow u(y',z'') > u(y'',z'')\right]
\end{equation}
Finally, ({\bf II} $Y$ $Z$) is true if and only if
\begin{equation}\label{ii-imp}
\forall y\in Y, \forall z,z',z''\in Z \left[ u(y|z) =
	\theta(z)u(y|z') + (1-\theta(z))u(y|z'')\right]
\end{equation}
from Bell's definition~\cite{Bell79b}.
Other independence conditions have implications for conditional functions
of a similar structure.  These conditions should lend substantial constraint
to the values permissible for these functions.

\subsection{Encoding of Assessment Algorithms}\label{algorithms}

In section~\ref{interpolation} I pointed out that the {\sc urp} knowledge base
does not capture
assessment procedures that are often associated with particular decompositions.
This has been partly intentional, since an aim of this project has been to
avoid rigid algorithms in favor of more flexible use of preference
specification.  Nevertheless, flexible use of information does not imply that
there should not be more focused information-gathering techniques.

There may be natural ways to implement multiattribute assessment algorithms
within {\sc urp}'s framework through the introduction of question-asking
heuristics.  Sets of heuristics associated with particular model situations
may be switched in and out to provide for the ``execution'' of a procedure.
Any such assessment framework must be integrated with the single-attribute
assessment concepts developed in chapter~\ref{assess-c}, below.

\chapter{Assessment with Preference Choices}\label{assess-c}

\section{Model-Independent Interpretation}\label{model-i}

Traditional utility assessment relies heavily on expressed preference
choices to determine the parameters of a utility function.  The mechanisms
built into {\sc urp} deal exclusively with reasoning about the
form of the utility function, which is usually a precompiled component of
assessment tools.  {\sc Urp}'s flexibility in model structure affords
a less-constrained approach towards assessment, where hypothetical preference
choices are interpreted under a procedure which is independent of a particular
underlying utility
model.  Assessment programs that employ a prechosen model generally
implement a procedure for generating lottery questions that fill in the
parameters of the model with the fewest possible responses.  The interpretation
of the response is a direct translation to a particular parameter of
the model.

In {\sc urp}, interpretation of preference choices must be more general.  Since
the model structure may be changed at any time (due to assertion or retraction
of independence conditions or qualitative behaviors), {\sc urp} must be able
to compute the implications of a hypothetical preference choice for any utility
model.  The extra generality means that {\sc urp} will not be as good at
optimizing the set of questions generated for particular models, since programs
using static models can employ efficient question-asking strategies that
exploit
the special structure of their particular models.  This may not be as important
as it sounds,
however, because {\sc urp} does not require completely specified utility
functions.  The completeness requirement of traditional assessment tools
places an unfortunate emphasis on the coverage of a set of questions, at the
expense of their information content with respect to a particular decision, or
consideration of how easy they may be to answer.  In general, these efficient
question sets include lotteries involving outcomes at the extreme ranges of
the attributes, which are considered difficult to answer and prone to
biased responses.

In the remainder of this chapter I outline a framework for utility assessment
using hypothetical preference choices in {\sc urp}.  Keep in mind that this
chapter does not describe an implementation, rather it conveys an overall
attitude and some intriguing assessment capabilities which may be possible
under the {\sc urp} approach.

\section{Inequalities vs. Indifference Points}

A {\it lottery} is a choice presented to an assessor between two prospects,
each a probability distribution over outcomes.  I will use the notation
$L_1 \succ_c L_2$, where the ``$\succ_c$'' relation is read ``is
chosen over,''\footnote{The subscript $c$ is used to distinguish this relation
from the usual preference relation ``$\succ$,'' meaning ``is
preferred to.''  I make this distinction
to allow for the interpretation of elicited responses under a descriptive
model other than expected utility, discussed in
section~\ref{descriptive} below.} to describe the assertion that
the assessor expressed a preference for lottery $L_1$.  The lotteries
offered to the assessor are almost always simple---one or two possible
outcomes in each $L$---to limit the processing burden on both the assessor
and the program.  Complicating the outcome distributions does not provide
any information advantage to the reasoner.

A common device used by assessment procedures is the certainty or probability
equivalent, where the subject is given two lotteries ($L_1$ and $L_2$) with a
single parameter (a probability or outcome from one of the $L$s) unspecified,
and asked to indicate the value
which would make \mf{him}{her} indifferent between $L_1$ and $L_2$
($L_1 \sim_c L_2$).  Note that an answer to this sort of question yields more
constraint than a preference choice, since it specifies an equality point.  But
by dragging the assessor
all the way to the indifference point (perhaps converging from either side),
we are straining the limits of \mf{his}{her} judgmental confidence.
We would expect these questions to be more difficult and prone to errors, as
studies have shown~\cite{HersScho84}.  Moreover, without the restriction
to fully specified utility functions, indifference questions are often
unnecessarily precise.  Indeed, assessment algorithms generally stop after the
minimal number of questions are asked, because further questions inevitably
lead to contradictory conclusions.  In such cases it is necessary to resort
to statistical best-fit schemes to assign values to parameters based on
lottery choices.  Due to these concerns, assessment in {\sc urp} is
restricted
to inequality questions, with the required narrowness of bounds determined by
the particular decision at hand.

\section{Constraints on Utility Functions}\label{a-constraints}

Information in the form of hypothetical preference choices constrains the
space of possible utility functions by revealing portions of the underlying
preference relation ($\succ$).  By assuming that $\succ$ is the same as
$\succ_c$
(an assumption of every utility assessment program), each preference choice
yields a linear inequality among points on the utility function.  That is,
an assertion that $L_1 \succ L_2$ implies
\begin{equation}\label{choice-constraint}
\sum_{x\in X}p_{L_1}(x)u(x) > \sum_{x\in X}p_{L_2}(x)u(x)
\end{equation}
where $p_{L_1}$ and $p_{L_2}$ are probability mass functions corresponding to
the two lotteries.  Naturally, $\sum_X p_L(x) = 1$ for all lotteries.

Without any further information about $u$, we can use these linear constraints
to compute bounds for the utility of specific outcomes (those appearing in
at least one lottery), or distributions over
outcomes.  Treating each evaluation of $u$ at a point (generically
denoted by ``$u(\cdot )$'') as a variable, we calculate the lower bound
for an expression made up of a linear combination of utility values by solving
a linear program.  The objective function to minimize is simply this
expression, subject to the constraints derived from the lottery choices and
equation~\ref{choice-constraint}, augmented by constraints of the form
$0 \leq u(\cdot ) \leq 1$.  To compute the upper bound, we minimize the
negation of the expression.

Incorporating other kinds of constraints on $u$ complicate the computations.
Some of these, such as monotonicity of $u$ with respect to scalar outcomes,
can be represented as linear constraints (not necessarily very efficiently),
while others require nonlinear representations.  Combining preference choice
information with specific functional forms for $u$ will generally result in
a set of nonlinear constraints.  Computing bounds for nonlinear expressions
subject to nonlinear constraints is a much harder problem, closely related
to the dominance-proving problem discussed in section~\ref{known-forms}.
Algorithms for restricted
versions of the problem exist, but I have not explored the possibilities
for incorporating them in {\sc urp}.\footnote{One example is the algebraic
constraint manipulation system developed by Brooks for geometric reasoning in
vision~\cite{Broo}, which is based on a linear procedure called {\sc sup-inf}
originally due to Bledsoe~\cite{Bled75} and improved by
Shostak~\cite{Shos}.  While the usefulness of this system for the kinds
of problems that would come up in {\sc urp} is untested, I suspect it will
be able to reason about some of the multiattribute forms: bounding
multiattribute utility from single-attribute lotteries and vice-versa.
It should also be able to handle some of the nonlinearities arising in some
of the descriptive theories described below.
It appears, however, that this system would be incapable of reasoning about
some of
the more important single-dimension utility functions.}  Naturally, the most
general methods are least efficient and least inclined to converge, while
more powerful techniques only work on restricted classes of problems.  Choosing
a constraint reasoner for {\sc urp} will involve classifying assessment
subtasks according to the constraint types they involve.  This is an important
focus of the effort required for extending {\sc urp} to perform utility
assessment.

\section{Alternate Descriptive Theories}\label{descriptive}

The descriptive validity of expected utility theory has been a subject of much
controversy ever since the development of the model over forty years ago.  As
Schoemaker points out in his review of the field~\cite{Schoemaker},
researchers with different perspectives on or purposes for the model have
diverging views on the validity and importance of the descriptive aspects of
expected utility.  While it is legitimate to support the prescriptive
significance of
the model without making any descriptive claims, practical uses of the model
for decision making invariably require subjective preference judgments from an
individual to determine the utility function.  By incorporating these
assessed preferences in a formal utility model, the analyst is making an
assumption about the relation between professed preferences and utility: in
effect adopting a descriptive view of expected utility.

This prescriptive-descriptive cycle is disturbing, if not embarrassing.
Analysts tend to support their formal models as normative approaches toward
overcoming the failings of human judgment, yet their own models depend
crucially on the ability of humans to make certain judgments.  The only way
out is to demonstrate that the required judgments are significantly simpler
and less prone to error than the original decision problem.  But simpler may
not be simple enough; empirical studies using choices similar to those used
in utility assessment consistently reveal important cognitive
biases.\footnote{See Tversky and Kahneman~\cite{TverKahn81} and Hershey,
Kunreuther, and Schoemaker~\cite{HersKunr} for a general
flavor of the results.}  As Tversky~\cite{Tver} forcefully argues, decision
analysts need to worry a lot more about this.

In the remainder of this chapter, I will discuss some of these biases and how
the {\sc urp} framework offers an interesting way to address the problem.  The
basic idea is to exploit {\sc urp}'s flexibility to interpret preference
choices under descriptive theories other than maximization of expected utility.
That is, we do not need to assume that $\succ$ is equivalent to $\succ_c$.
Instead, we
define some other relationship between $\succ_c$ and $\succ$, corresponding
to a particular psychological theory of preference choice.  Though the
extra degrees of freedom often introduced by these alternate theories will
generally weaken the conclusions we can make from a given set of hypothetical
choices, I suspect that these should still provide useful constraint on the
utility function.

\subsection{Descriptive Theories of Preference Choice}

Psychologists, decision theorists, and economists have long noted discrepancies
between subjects' expressed preference choices (in the laboratory or the real
world) and normative decision theories.  Over the years a substantial
literature has developed, cataloging a large number of persistent biases
observed in typical utility measurement tasks.  While identification of
these cognitive effects is useful for developing bias-resistant assessment
procedures, a more significant benefit may be reaped through the development
of formal descriptive theories of preference choice.  The remainder of this
section outlines some of the potentially useful theories developed over the
last few years; my focus is on the structure of the theories rather than their
rationale or descriptive validity.  The description may get overly technical
at times, since illustrating the feasibility of turning these diverse theories
into assessment procedures requires a demonstration that their mathematical
structure may be incorporated into the {\sc urp} framework.\footnote{I
would suggest that the reader skim over the mathematical details that are not
of major concern while paying special attention to the {\it form} of the
models.  The individual theories are much better motivated in the cited papers
than in the presentation here.}  Implementation of interpreters for them is
discussed in the next section~(\ref{descriptive-interpreters}).

\subsubsection*{Prospect Theory}

Prospect theory~\cite{KahnTver79} attempts to account for observed
violations of expected utility
in expressed preference choices with a two-step process of editing and
evaluation of simple lotteries.  The first phase is an editing procedure,
where the lotteries are transformed in ways which may or may not preserve
their normative utility-theoretic properties.  Kahneman and Tversky describe
six editing operations, each a straightforward syntactic manipulation of
the lotteries.  The first operation, {\it coding}, requires identification
of a reference point, which dictates the perception of an outcome as a gain
or loss.\footnote{Fischhoff~\cite{Fischhoff} notes that it may not always be
possible in practice to determine the reference point used by assessors in this
editing step.  In particular, it seems that subjects' own impressions of their
reference point is often misleading (at least under a prospect theory
interpretation).  This may be a hindrance to its use for assessment, since
interpretation of preference choices under prospect theory will require us
to identify the reference point.}  Some of the other editing operations are
valid manipulations under expected utility, such as the removal of common
subcomponents.  This is equivalent to the transformation described earlier by
equation~\ref{common-c}.

Evaluation of the edited prospects requires a weighting function of
probability,
$\pi$, and a value function, $v$.  The value of a prospect with two nonzero
outcomes $x$ and $y$, associated with probabilities $p$ and $q$ respectively
is given by
\begin{equation}\label{prospect-value}
V(x,p; \; y,q) = \left\{
	\begin{array}{ll}
	   \pi (p)v(x)+ \pi (q)v(y) &
	   {\rm if} \;\; p+q<1 \;\; {\rm or} \;\; x \geq 0 \geq y \\
	   & \hspace{2em} {\rm or} \;\; x \leq 0 \leq y \\
	   v(y)+ \pi (p)\left[ v(x)-v(y)\right] &
	   {\rm if} \;\; p+q=1 \;\; {\rm and} \;\; {\rm either} \\
	   & \hspace{2em} x>y>0 \;\; {\rm or} \;\; x<y<0.
	\end{array} \right.
\end{equation}
The theory also dictates certain constraints on the functions $\pi$ and $v$.
For example,
subjects tend to exhibit risk aversion for gains and risk proneness for losses,
and losses loom larger than gains.  Thus, $v''(x) < 0$ for positive $x$,
$v''(x) > 0$ for negative $x$, and $0 < v'(x) < v'(-x)$ for all $x$ (if these
derivatives exist).

As for the probability weighting function, prospect theory asserts that $\pi$
is increasing in $p$, with $\pi(0) = 0$ and $\pi(1) = 1$ (though the endpoints
may not be continuous).  In addition,
$\pi(p) > p$ and $\pi(rp) > r\pi(p)$ for small $p$ and $0<r<1$.  For all $p$,
$\pi(p)+\pi(1-p)<1$ (subcertainty).

Karmarkar's subjectively weighted utility model~\cite{Karm} evaluates
lotteries by combining a classical expected utility function with a
transformation of the probabilities.  Unlike prospect theory's $\pi(p)$,
Karmarkar's probability weights are computed using a function of a single
parameter.  This restricted form may make assessment considerably more
tractable.

While discussion thus far has been confined to single-attribute
lotteries (as are assessment tools and descriptive theories in general), some
of these concepts may be extensible to multidimensional problems.  For example,
Payne, Laughhunn, and Crum~\cite{PaynLaug} discuss ways in which editing
operators similar to those of prospect theory may be applied to multiattribute
lotteries.

\subsubsection*{Regret Theories}

It has long been observed that decision makers may derive value or disutility
from the correctness of their decision, separate from the utility attributed to
the outcome itself.  This phenomenon---called {\it regret} or
{\it rejoice}---has been used to explain deviations from expected utility
theory, and has recently been the centerpiece of some formal models of
preference choice.

Bell's approach~\cite{Bell82a} is to model utility as a two-attribute
function of final assets $x$, and foregone assets $y$.  A series of
assumptions about preferences for the two attributes leads to the result
\begin{equation}\label{regret-e}
u(x,y) = v(x) + f(v(x)-v(y))
\end{equation}
where $v$ is a function measuring the incremental value of assets and $f$ is
an arbitrary function.  Further qualitative characteristics of regret
constrain the space of possible $f$s.  Note that direct use of this
two-attribute function requires that the joint probability distribution for
$x$ and $y$ is specified (that is, outcomes of foregone lotteries are
resolved).  In a sequel paper, Bell~\cite{Bell83} examines the special
case of independence between lotteries, and cases where foregone lotteries
are left unresolved.  In using regret theory for assessment, it is necessary
to choose a policy regarding the resolution of unchosen lotteries.

The regret theory of Loomes and Sugden~\cite{LoomSugd82}, while not
founded on a two-attribute utility-theoretic model, yields implications similar
to Bell's.

\subsubsection*{Consumer Choice Models}

Researchers in marketing are interested in a descriptive model of preference
choice to predict consumer behavior.  While much of their work involves
stochastic choice, or choice over aggregate populations, some of their
models may be applicable to deterministic individual behavior (in a modified
form, if not directly).  Of particular interest are those that have a
utility-theoretic basis (for example, the approach described by
Hauser~\cite{Haus}).  Possibilities for assessment can be envisioned
for those theories employing specific utility forms in conjunction with
measurement error models (that of Eliashberg and Hauser~\cite{Elia}
provides a recent example).  While these models may not have a compelling
psychological rationale, they may have value for assessment.  Treating these
models as descriptive theories and
using them for assessment is similar in spirit to statistical best-fit
approaches to utility modeling.

\subsubsection*{Accounting for Disappointment}

The final example of a descriptive theory that may be used for assessment is
Bell's recent model of disappointment effects~\cite{Bell85b}.  Disappointment
is conceptually similar to regret in that preference for outcomes is dependent
on structural features of the lottery.  The major difference is that here the
relevant comparison is to expectations, not foregone assets.  Decision makers
experience disappointment when outcomes are significantly worse than
expectations, and elation when outcomes are better.  These measures of
psychological satisfaction form a second component (in addition to the outcome
itself) of utility for a lottery.

Consider a lottery that offers a probability of $p$ of obtaining outcome $x$
and $1-p$ for a less-preferred outcome $y$.
In the simplest model---where preference for the outcome and for psychological
satisfaction are additive, expectations are linear in the outcome, and
disappointment-free preference is risk neutral---the certainty equivalent
is
\begin{equation}\label{disappointment-e}
y+(x-y)\pi(p)
\end{equation}
where $\pi$ may be interpreted as a subjective probability
measure.\footnote{Note the similarity to prospect theory.  Even though
prospect theory's $\pi$ arises from behavioral considerations of probability 
interpretation, when combined with editing of risk-free components it results
in the same model as disappointment (see the second clause of
equation~\ref{prospect-value}), ignoring the transformation by $v$.}  Using
this simple model, preference choices yield linear constraints on $\pi(\cdot)$,
resulting in straightforward assessment.  Bell~\cite{Bell85b} discusses
direct assessment of $\pi$ by indifference points, as well as less direct
methods requiring explicit tradeoffs between the outcome and
disappointment/elation.  This latter form of assessment employs questions
regarding the value of winning (or losing) lotteries instead of straight
preference choices.

\subsection{Interpreting Choices with Respect to a Theory}
\label{descriptive-interpreters}

The key thing to notice from the above descriptions is that several of
these alternate theories of preference choice have analytic forms that may
be related to traditional prescriptive models.  To implement an assessment
procedure based on one of them rather than maximization of expected utility,
we would simply replace the utility maximization criterion
(equation~\ref{choice-constraint}) with the choice criterion operating in
the descriptive theory (equation~\ref{prospect-value} for prospect theory,
\ref{regret-e} for regret theory,
or~\ref{disappointment-e} for disappointment).  An expressed
choice of
one lottery over another yields an inequality within that particular formalism;
constraint reasoning analogous to that described in
section~\ref{a-constraints} above may be applied to infer facts about
the model's components.

\subsubsection*{Example: Implementing Assessment Based on Prospect Theory}

An expressed choice in prospect theory constrains the
possibilities for $v$ and $\pi$, beyond the restrictions provided by
the theory.  {\sc Urp}'s mechanisms for reasoning about partially specified
utility
functions may be applied directly for dealing with incomplete representations
for functions like these.  To derive a prescriptive model from our
choice-constrained descriptive model, we need to apply transformations
specific to the particular theory.  For prospect theory (and similarly for
Karmarkar's weighted utility~\cite{Karm}), we might replace $\pi$ with the
identity mapping, in effect treating $v$ as the utility function.  In addition,
we probably would eliminate the prospect editing operations that are not
utility-preserving.  Deciding how (and whether) to adjust the reference point
is a tricky question.  This adjustment would have a serious impact on $v$,
which should be appropriate in many situations.

To illustrate assessment under prospect theory, consider an expressed
preference for the edited prospect $L_1=(x_1,p_1;\;y_1,q_1)$ over
$L_2=(x_2,p_2;\;y_2,q_2)$, with $p_1+q_1<1$, $p_2+q_2<1$, $x_1$ and $x_2$
positive, and $y_1$ and $y_2$ negative.  From this we may conclude
(from~\ref{prospect-value})
\begin{equation}\label{prospect-choice-1}
\pi (p_1)v(x_1)+ \pi (q_1)v(y_1) > \pi (p_2)v(x_2)+ \pi (q_2)v(y_2)
\end{equation}
which is a nonlinear constraint on eight values.  To simplify this for
assessment, we would typically ask questions in which some of the $p$s and
$q$s or $x$s and $y$s are the same (or known points of the functions, such as
$\pi(0)$, $\pi(1)$, or $v(0)$).  For example, suppose $x_1=300$, $p_1=.1$,
$x_2=100$, $p_2=.2$, and $y_1=y_2=0$ in~\ref{prospect-choice-1}.  This
constraint, together with prospect theory's subproportionality and
subadditivity conditions (which imply that $\pi(rp)>r\pi(p)$ for $0<r<1$)
result in the relation $v(300)>2v(100)$, the result that would be concluded
from expected utility theory.  In addition, the condition that $v$ is concave
for positive $x$ enables us to strengthen our result.
\[\frac{1}{3} \leq \frac{v(100)}{v(300)} < \frac{1}{2}\]
Additional prospect choices add further constraint on the shapes of $v$ and
$\pi$.  A constraint reasoner that is able to handle limited nonlinearity
(such as the one Brooks developed for {\sc acronym}~\cite{Broo}, noted above)
will be needed to perform this task in any useful assessment tool.

\subsubsection{Choosing a Descriptive Theory}

Once several assessment procedures based on different descriptive theories
have been implemented, we need to decide which interpretive model to use in
which situations.  Ideally, we would like to ``diagnose'' the types of
bias that are present for particular assessment sessions and apply the
theory that best explains that flavor of bias.  This is certainly beyond
the state-of-the-art, though I suspect that the capability of switching
between alternate theories may provide a useful tool for bias diagnosis.
But even without such sophistication, it may be possible to match descriptive
theories to assessment situations based on other criteria.  For example,
the type of attribute being assessed (financial, length of life, health
dimension) may indicate that certain psychological choice theories are more
relevant than others.  Most of the theories developed are specifically
geared toward preference for financial assets, though other work has looked
at related biases for other attributes.  An example is the study of
McNeil, Pauker, Sox, et al.\ \cite{McNePaukSox}, which found correspondences
between biases due to framing of health outcomes and prospect theory.

Another possible criterion is the setting for collecting the preference
choices.  While the theories described above are generally related to
answers to lottery questions similar to those used in traditional utility
assessment, often it is desirable to use preferences revealed through
real-world
observation of decision making (such as consumer behavior, safety
practices, public policy, or other economic activities).  In such cases it
would be a good
idea to consider some of the biases typically observed in real-world
economic behavior; the marketing models mentioned above may be particularly
suited to these situations.  Thaler~\cite{Thal} describes many biases that
seem to be widespread in economic behavior.  One of them, due to the
phenomenon of {\it self-control\/}, is incorporated in a model developed
by Thaler and Shefrin~\cite{ThalShef}.  Weinstein and
Quinn~\cite{WeinQuin} discuss biases which are prevalent in societal health
policy.

\subsubsection*{Conclusion}

By representing choices in a theory-independent manner, we may switch between
interpretive frameworks in a modular fashion.  Thus, this psychological
modeling serves as a form of structural sensitivity analysis, in which we
weaken the assumption of normative choice to examine its effect on the result.
If the decision proves invariant under a set of theories that admit various
sorts of response bias, we may be justifiably confident that our result
exhibits a novel form of robustness that would be difficult to demonstrate
any other way.

\chapter[Domain Preference Knowledge]
{Incorporating Domain Preference Knowledge}\label{domain-p}

In a previous section (\ref{1-step}) I put forth the contention
that the qualitative properties used by {\sc urp} are ``one step away''
from being intuitive.  In this chapter I argue that the reason the concepts
used by the program are not totally intuitive is that there is inevitably a
substantial gap between general knowledge about a modeling discipline and
knowledge of how to apply its models in a particular problem domain.  This
difficulty is quite
serious, since a consultation system that knows everything about a field of
mathematical modeling but nothing about relating those models to particular
real problems would be virtually useless to practitioners trying to solve these
real problems.  Nevertheless, we do not wish to create narrow systems designed
for modeling problems in only a restricted domain.  The aim is to separate
general modeling knowledge so that it can be employed in problems from a wide
variety of areas.

The sections below serve to define the nature of the gap between modeling and
domain knowledge more clearly.  I
provide a framework for spanning {\sc urp}'s gap by incorporating domain
preference knowledge, illustrated by examples relevant to medical decision
problems.

\section{Modeling and the Ground Domain}

The use of a mathematical modeling technique always involves an area of
application separate from the modeling discipline.  Gale and
Pregibon~\cite{GalePreg84} refer to this area as the {\it ground domain}.  They
point out
that relating modeling concepts to experts in a ground domain is a serious
challenge in building knowledge-based systems for statistics.  The approach
taken here is somewhat different: rather than building this relation on a
user interface, the idea is to bring concepts from the domain into the modeling
knowledge base.

\subsection{Modeling as Abstraction}

Whenever a mathematical formalism is used to model real world phenomena---for
decision making, prediction, theory formation, or whatever---there is
inevitably an abstraction from the objects of the real-world domain to objects
in the mathematical domain.  The modeling exercise is appropriate if and only
if the abstraction can be said to preserve the {\it essential} properties of
the real-world object, where essentiality is defined relative to the goals of
the modeling effort.  Since this requirement is central to any modeling
discipline, such disciplines have generally evolved rich vocabularies for
specifying the essential properties and relating them to the modeling tools
which comprise the discipline.  The essential properties are commonly referred
to as modeling assumptions.

\subsection{Technical Vocabularies}\label{vocabulary}

For modeling disciplines intended for
application in several domains (or even to varying problems in a single
domain), the vocabulary must be in a language with a technical level
more akin to the objects of the mathematical formalism than to the real-world
objects being modeled.  This is why a system like {\sc urp}, which contains
a substantial amount of knowledge about modeling and none about a ground
domain, must deal in
concepts that are one step away from those that would be intuitive to an
application expert using the program.  It seems ironic that the same generality
of the essential properties that made them qualitative and therefore closer
to intuitive principles in the first place also provides the argument that they
cannot be intuitive in the final sense.

I have spent the greatest portion of this thesis describing what I think
the {\it technical vocabulary} for preference modeling using utility theory
looks like, and
how it is possible to get a computer program to use it.  But while utility
theory provides an exemplary case of the vocabulary notion, the idea is by
no means limited to this particular theory or this particular modeling task.
I will further contend that {\it any} modeling formalism designed to work for
more than a single problem instance needs a technical vocabulary.

Perhaps this point will be strengthened with a few brief examples.  In
probability theory (a component of many modeling disciplines), there is
a fundamental abstraction from real-world phenomena to a
formal notion of events in a space of events.  Modelers use tools of
probabilistic analysis to make conclusions about the real world phenomena
represented by these abstract events.  The technical vocabulary in this case
includes
(among other things) the characterizations of events which make various tools
and methods appropriate or inappropriate.  Some very simple characterizations
(of collections of events) include mutual exclusion, collective exhaustion,
and various flavors of statistical independence.  Note that few programs that
perform so-called
``probabilistic reasoning'' have explicit knowledge of even these simple
characterizations.

The second example is in the area of statistical test design.  Although this
modeling task presents several important issues, one of the most fundamental
ones concerns the measurement scales of the parameters of the model.
In designing a test sequence, it is essential that the modeler (human or
computer program) choose only tests that manipulate the parameter in ways
meaningful with respect to measurement properties of its scale.  To a
statistician, the concepts of ordinal and interval scales, for
example, are very basic and simple to apply.  The scale type for a particular
parameter can be easily identified, and tests appropriate for that type
can be generated.  Nonetheless, the vocabulary is
technical, and there does not appear to be a simple one-line explanation that
would enable an expert from any domain to determine whether \mf{his}{her} scale
is ordinal.  A human statistician usually can solve the problem by resorting
to common sense or world knowledge; often it is not necessary to be an
expert in the ground domain to elicit the essential properties of the modeled
domain objects.

The two examples described were intentionally taken from extremely simple
modeling issues (the second issue---reasoning about measurement
properties---will be discussed in the context of utility modeling later in
this chapter).  The point is that if even the most simple of modeling
concepts require a technical language, the more sophisticated modeling
concepts will undoubtedly be beyond intuitive explanation for a particular
ground domain.

\subsection{Expressing Domain Concepts in a Technical Vocabulary}

Even with this serious limitation, reasoning in terms of qualitative properties
is substantially more explainable than strict quantitative reasoning.  The
vocabulary is still within the technical bounds of mathematics and the modeling
discipline, but it is a lot closer to the fringe.  Thus, the models will be
accessible to those with less modeling expertise and perhaps more
comprehensible even to modeling specialists.  And for application to particular
ground domains, or restricted problems within domains, it may be feasible to
build
in domain-specific knowledge about the mapping from domain principles to this
technical vocabulary.

This last option is particularly reassuring for incorporation of preference
modeling in decision-making knowledge-based systems.  These programs typically
operate over a narrow range of problem types in a highly restricted domain.
I suspect that it will often be reasonable to build in the ground domain
concepts necessary to maintain an interface to {\sc urp} in terms of its own
technical vocabulary.

\section{A Domain Preference Knowledge Base}

To test the expressive power of {\sc urp}'s technical vocabulary, I suggest
the development of a domain preference knowledge base: a collection of useful
knowledge about modeling preferences in a particular domain encoded for use
by {\sc urp}.  This knowledge base would act as an interface module for
programs using {\sc urp} and as a library of models and components for
a human analyst using the program.

In the remainder of this chapter I provide a framework for building this
knowledge base using examples from
preferences in medical decision problems.  None of these representations and
mechanisms have been implemented, but the design is compatible with {\sc urp}'s
overall framework.  I expect that many of the concepts proposed for inclusion
in the knowledge base can be incorporated into
{\sc urp} with little modification of the existing system.  Others will require
more substantial implementation effort.  The knowledge
base for medical preferences as developed in this chapter is summarized in
appendix~\ref{medical-ax}.

\section{Built-in Attributes}

\subsection{Specifying Attributes in {\sc Urp}}

The first step in encoding domain preference knowledge is to specify attributes
that will be relevant to decisions in that area.  Patterns for combining these
attributes constrain the base structure of preference models, and {\sc urp}
assertions about their utility-theoretic properties help determine the form of
these models.

\subsubsection*{Attribute Definition}

An attribute definition in {\sc urp} consists of a name, a measurement scale,
and a description.  Figure~\ref{attribute-definition} depicts a sample
{\sc urp} attribute definition for the {\it life-years} attribute used in
the medical example of chapter~\ref{r-exam}.  The name
``{\tt LIFE-YEARS}'' is simply the symbol used by {\sc urp} to refer to
the attribute, and {\bf value-set} defines the set of values possible for
that attribute.  This set may be any collection of real numbers or integers
(not necessarily contiguous).

\begin{figure}[htbp]
\begin{tt}
\begin{tabbing}
mmm\= (def\= :de\= '(\= \+ \kill
(defattribute LIFE-YEARS \\
\> :value-set '(real-range 0 max-life-years) \\
\> :scale-type 'ratio \\
\> :unit 'years \\
\> :description \\
\>\> '(life-years (\# of years from NOW until DEATH) \\
\>\>\> max-life-years (Largest possible value for life-years)))
\end{tabbing}
\end{tt}
\caption{An example of an attribute definition in {\sc urp}}
\label{attribute-definition}
\end{figure}

\label{measure-discussion}
The {\bf scale-type} specifies some measurement-theoretic properties of the
attribute scale.  Given a set of values and some interpretation of ordering
and combination (generally some kind of addition or concatenation) associated
with the attribute quantity, the scale-type defines the set of mathematical
transformations that preserve this interpretation.
Table~\ref{measure-t} associates some of the most common scales with
their class of permissible transforms.\footnote{The volume by Krantz,
Luce, Suppes, et al.\ \cite{Kran}
is the source for these definitions (except arbitrary naming), and is a good
general reference on the theory of measurement.}  This information is highly
useful
in model-building, since the class of transformations constrains the kinds of
concepts that make sense for a particular attribute.  For example, it is
reasonable
to talk about direction of preference along all of the depicted scales (except
arbitrary naming), since direction is invariant under all monotonic
transformations.  It is dangerous to consider the convexity (risk properties)
of preference for
attributes with ordinal scales, however, since this property may be changed
by nonlinear transformations.  While consideration of risk aversion for
attributes defined
by log-interval scales is not a good idea, the risk property of the logarithm
of that attribute may be a useful concept.

\begin{table}[htbp]
\begin{tabular}{ll}
\underline{scale-type} & \underline{permissible transformations} \\[.2cm]
arbitrary naming & all transformations (since no ordering exists) \\
ordinal & all monotonic transformations \\
interval & $\alpha x+\beta , \; \alpha >0$ \\
log-interval & $\alpha x^\beta , \; \alpha >0, \beta >0$ \\
ratio & $\alpha x, \; \alpha > 0$
\end{tabular}
\caption{Some useful measurement properties and their permissible
transformations ($x$ denotes the measured quantity)}
\label{measure-t}
\end{table}

Measurement properties are likely to be useful in several components of
the overall preference modeling task: formulation and explanation are two
that come to mind.  In general, I would argue that the measurement properties
of the quantities manipulated by a mathematical modeling program are an
essential part of the knowledge required to reason about them, and should
therefore be included in any system that works with different kinds of
quantities.  I have already noted the usefulness of measurement properties to
determine the applicability of statistical tests.  Specification of the
measurement scales provides a convenient way to indicate something
about the allowable intuitive interpretations of a quantity's magnitude
without a deeper knowledge of the real-world concept associated with the
quantity.  In other words, it describes the structure of
the informal interpretation of the quantity without requiring that the computer
understand what that intuitive meaning is.

The scale specification may need to be fairly complex, because many attributes
are described by membership in arbitrarily defined categories rather than by
continuously varying quantities, discrete gradations on a continuous scale, or
the cardinality of a set.  The {\bf unit} slot of an {\sc urp} attribute
definition measured by a quantity is
the semantic dimension of that quantity; for attributes measured by category
membership, {\bf unit} specifies the mapping from the attribute's value to
definitions for the various categories represented.
In the categorical case, we can still talk about the properties of numeric
functions by associating an index set of integers with the set of categories.
Recall that the main purpose of defining attributes is so that we can specify
utility-theoretic properties of preferences over them (discussed further
below).  Therefore, the indexing scheme should be chosen with these properties
in mind.  An obvious desideratum in specification should be to choose a scale
which provides the maximum structure for interpreting the value with respect
to preference.  Keeney~\cite{Keen81a} discusses issues in selecting and
constructing scales
for measuring objectives in preference models.  In trying to capture this
formulation knowledge in a program, the measurement properties of the scales
will undoubtedly play an important role.

The {\bf description} of an attribute conveys the interpretation of an
attribute's
value.  Typically this will consist merely of textual definitions associated
with the attribute name.  If other {\sc urp} symbols occur in the attribute
definition (for example, to parameterize the scale specification), these are
also described.

\subsubsection*{Combining Patterns}

Once a substantial number of attributes have been defined in {\sc urp}, it is
useful to constrain the ways in which they may be combined in formulating a
preference model.  This type of specification serves to assist
the user in selecting the {\sc urp} attributes to include in the model,
and may prevent some
potential errors arising from uses of the attributes in ways unintended by the
attribute definer.  Combining patterns may also affect the structure of
preferences over the chosen attributes.

Two mechanisms can be provided for specifying combining patterns.  The first
is to define {\it component relations}.  A component relation is used to
indicate that certain attributes are partial measures of other attributes.
For example, if attribute $Y_0$ can be defined as a function of attributes
$X_1,\ldots,X_k$, then the $X_i$s are components of $Y_0$.  In an {\sc urp}
formulation, $Y_0$ would automatically be treated as a vector attribute
containing the $X_i$s.  These component relations may be built up into a
hierarchical structure.

The second mechanism for specifying combining patterns is to define 
{\it inclusion links} between pairs of attributes.  We can think of these links
as specifying binary relations $R$ and $R'$, where $(X,Y) \in R$ implies that
any preference model containing attribute $X$ must also contain attribute $Y$.
Similarly, $(X,Y)\in R'$ implies that any preference model containing $X$
must {\it not} contain $Y$.  $R$ and $R'$ are of course exclusive.  Note that
$R'$ is symmetric, though $R$ may not be.

\subsection{Built-in Attributes for Medical Decision Making}

Although medical decision problems present a wide variety of issues and
criteria important to value judgments, it is possible and useful to define
a few of the more common attributes and their utility-theoretic properties.
Actual formulations for specific problems may use different combinations of
these attributes, and may introduce others which have not been predefined.
In this section, I will describe a few attributes which should be useful in
a wide variety of medical decisions.  Specification of the utility-theoretic
properties of these attributes in {\sc urp}'s technical vocabulary is the
subject of subsequent sections.

\subsubsection*{Life Years and Health Status}

The first common attribute, illustrated in
figure~\ref{attribute-definition}, is called {\it life-years}.  As one
would expect,
the length of the patient's life is a major factor in most difficult medical
decisions.  Inclusion in a preference model, however, depends on stochastic
relevance as
well as importance.  In a situation where the only difference between
alternative strategies pertaining to lifetime is in short-term risk (operative
mortality of a surgical procedure, for example), the appropriate attribute
may be one that only distinguishes between surviving or not surviving beyond a
certain time
horizon.  A program to help in the formulation task should have knowledge
about relevance patterns such as this.

Another ``generic'' attribute is {\it health-status}.  This attribute will
denote different criteria in various kinds of medical decisions.  In the
simplest case---where there is only one relevant health criterion in addition
to lifetime---{\it health-status} will simply represent that criterion.  In the
more general case, {\it health-status} will be a vector attribute consisting of
several lower-level medical criteria, or the value of some {\it health status
index} developed for specific kinds of problems.  For reasons that will become
apparent in section \ref{special-forms}, the attribute
{\it health-status} will only be used to describe states: conditions that exist
at a point or over an interval of time.

Unlike {\it life-years}, {\it health-status} does not have a
consistently defined
measurement scale.  For that reason, it is important to build in special
attributes for the particular measures of health status dimensions that will
be relevant in specific cases.  These attributes would be connected to
{\it health-status} through component relations.

An example of such a component attribute is the measure of physical function
used by Torrance, Boyle, and Horwood~\cite{TorrBoyl} in their study of health
state preferences.  Their scale for the attribute {\it physical-function} is
composed of six categories ranging from unrestricted mobility and physical
activity to being dependent on others for getting around and lacking control
of limbs.  We can define this attribute directly in {\sc urp}
with little difficulty.  The {\bf scale-type} would be {\it ordinal} with a
{\bf scale} of ({\it integer-range} $1$ $6$).  The {\bf unit} slot specifies
the mapping from the integer scale values to the categories.  In this example
we would use the value one for the most restricted category of
{\it physical-function} and six for the least.  The description of the
various categories can be taken directly from the English descriptions used
by the scale's developers.

Other component attributes include those introduced in the example of
section~\ref{m-extension}.  There we might consider the attributes
{\it disabling-stroke?}, {\it cabg-morbidity}, and {\it endart-morbidity}
($X_2$, $X_3$, and $X_4$) to collectively define {\it health-status}.  To
include these in the {\sc urp} domain preference knowledge base we would need
to generate attribute definitions similar to those described above.

\subsubsection*{Health Status Indices}

Researchers in medical decision making and public health have compiled a
considerable literature on health status indices and other
mechanisms for measuring the desirability of health states.\footnote{The
indices described by Parkerson et al.\ \cite{Park}, Torrance, Boyle, and
Horwood~\cite{TorrBoyl}, and Fryback and Keeney~\cite{FrybKeen} are just
a sampling.}  While the indices have been developed for different purposes
(health policy, clinical decisions, research evaluation) and under different
methodologies (Gustafson et al.\ \cite{Gust} compare indices developed
using utility theory, actuarial approaches, and more ad hoc methods), they all
provide a potentially useful scale for measuring difficult-to-quantify health
status attributes.

Encoding these various
measures as {\sc urp} attributes is a feasible task that would have substantial
value in bringing together a large body of research in a uniform framework.
Provided with such a knowledge base, a health preference modeler would be able
to pick and choose among a large variety of options in selecting attributes to
include in the model.  An additional advantage of predefined attributes
related to health status indices is that these are often associated with
well-tested measuring techniques (usually questionnaire responses or more
objective criteria), and empirical validation over large groups of patients.

\section{Predefined Qualitative Properties}

It will often be possible to specify qualitative constraints on preferences for
some of the built-in attributes for a particular application domain.  These
qualitative properties can sometimes be described directly in {\sc urp}'s
terminology.  Qualitative property assertions were described in
section~\ref{q-assertions};
a complete listing of the properties known to {\sc urp} is given in
appendix~\ref{q-appendix}.

\subsection{Monotonicity}\label{monotonicity}

Many of these properties are quite simple and intuitive.  For example, an
obvious property of the attribute {\it life-years} is that its utility
increases with the number of years.  The {\sc urp} assertion
({\bf monotonic-increasing} {\it life-years}\/) means simply that the patient
will always prefer a longer life to a shorter one, all other things being
equal.\footnote{Of course, even this is a simplification.  The possibility of
situations so bad as to make one prefer a shorter life is examined in
section~\ref{pre-independence}, on independence relations.}  Similarly,
for most measures of health status, the assertion
({\bf monotonic-increasing} {\it health-status}\/) will hold.  Recall from
table~\ref{measure-t} that
monotonicity assertions only make sense for certain types of measurement scales
specified in the attribute definition.  Constraints
like this are useful to {\sc urp} during model construction.

In many cases, it will be necessary to examine lower-level
components of health status directly.  These are very likely to have
measurement scales consisting of discrete categories, as in the example of
physical function described above.  When these categories have some ``natural''
ordering (degree of physical functionality in the example) this ordering
should be reflected by the index values.  These natural orderings are often
closely related to preference orders.

Preferences for {\it physical-function} are of course also monotonically
increasing, but for other lower-level components of {\it health-status},
smaller values may be preferred, for example, required hospital visits per
month.  In
still others, it is possible that there is an
optimal point, say $y_{normal}$, which is preferred to values either above or
below.  To represent direction of preference for such an attribute, we would
make two monotonicity assertions:
({\bf monotonic-increasing} $Y$ $\left[ y_{lb}\;\; y_{normal}\right]$), and
({\bf monotonic-decreasing} $Y$ $\left[ y_{normal}\;\; y_{ub}\right]$).  Here
$y_{normal}$
may be a constant or may vary depending on other aspects of the problem.

Naturally, these properties are an artifact of the measurement scale chosen to
represent the attribute.  Scales can be inverted to change increasing
preferences to decreasing ones and vice versa.\footnote{In fact, Torrance,
Boyle, and Horwood~\cite{TorrBoyl} numbered the {\it physical-function}
categories from one
(best) to six (worst), rather than from six to one as I described previously.
Using their indexing, utility for {\it physical-function} is decreasing.}
Often it may make sense to
transform the nonmonotonic attribute $Y$ to another called $Z$, where
$z = |y - y_{normal}|$.  In this case, preferences over $Z$ would be
monotonically decreasing.  In fact, the arbitrary nature of measurement scale
helps to illustrate why qualitative properties from {\sc urp}'s technical
vocabulary alone may not be intuitive.  The interpretation of qualitative
assertions depends critically on both the technical definition of the
property and the meaning of the scale describing the attribute.  Once again,
the scale specification in the attribute definition is useful, because it
tells us that a transform such as the one above results in a scale with a
very different intuitive interpretation.  Since the transform from $Y$ to $Z$
is nonmonotonic, relations between magnitudes of $Y$ are not invariant with
respect to $Z$.

\subsection{Risk Aversion}

The dependence of intuitive interpretation on both measurement scale and
technical definition is particularly important for the property of risk
aversion.  In purely mathematical terms, risk aversion corresponds directly
to concavity of the utility function.  To see how this technical definition
translates to the notions conjured up by the property's name, we will have to
look closer at the quantity measured by the utility attribute.

Bell~\cite{Bell81} points out the importance of separating the different
components of risk aversion.  Several conditions may contribute to the risk
aversion (concavity) of the utility function,\footnote{And correspondingly,
proneness or neutrality (convexity or linearity).  To simplify further
discussion, I will speak only of aversion and will assume that preferences
for the attribute in question are increasing.  Extension to the decreasing
case or to risk proneness is straightforward.} some of these with intuitive
interpretations seemingly unrelated to ``tendency to avoid uncertainty.''  For
example, Bell~\cite{Bell81} cites five influences on risk aversion
for financial outcomes: non-linear measurement of the attribute, decreasing
marginal value, effects of uncertainty on planning, risk anxiety, and decision
regret.  Although the legitimacy of regret and anxiety is questionable in a
prescriptive framework,\footnote{Unless the psychological factors behind
regret and anxiety (such as disappointment, hopes, or fears) or the tangible
effects on planning are explicitly
treated in the model, there is no guarantee that preferences can be
represented by a von Neumann-Morganstern utility function.  Generalizations
of expected utility (many of which are mentioned in a survey by
Machina~\cite{Mach}) do not offer a solution, in my opinion, since even
these usually require that all of the factors affecting hopes, fears, etc., are
summarized in the statement of the prospect.  Nevertheless, I believe that some
of these models as well as
psychological models of preference choice may turn out to be superior for
descriptive purposes and, therefore, useful in the assessment process.}  the
other factors may be applicable for a wide range
of attributes.  Gafni and Torrance~\cite{Gafn} partition risk aversion
into three components: a quantity effect (analogous to decreasing marginal
value), a gambling effect (intended to capture the ``attitude toward
uncertainty''; not a very well-defined notion here), and a time-preference
effect.  Of course, the precise definitions of these factors depend on
the particular attribute in question.  As we will see below, some
attributes may be associated with components of risk aversion in addition to
these.

To accommodate the possibility of multiple factors affecting qualitative
properties, {\sc urp} must provide a mechanism for defining {\it influences}.
An influence is an assertion that a particular factor tends to support or
refute the applicability of a qualitative property.  {\sc Urp} determines that
a property holds if all of its non-neutral influences are positive.  The
problem of resolving qualitative influences is similar to that faced by
qualitative reasoning programs (like those of Kuipers~\cite{Kuip84} and
Forbus~\cite{Forb}).

\subsubsection*{Risk Aversion for {\it life-years}}\label{averse-life}

Defining a qualitative property for a built-in attribute consists of
specifying its influences and asserting the ones that are valid.  The
influences I have chosen to define risk aversion for {\it life-years} are
{\it decreasing-marginal-value}, {\it time-preference}, and
{\it age-preference}.  This separation is far from obvious; the discussion
below serves to define and delimit the concept that each influence represents.

{\it Decreasing-marginal-value} corresponds to the well-known phenomenon
whereby agents derive smaller benefits from successive increments of
the same commodity.  The concept is particularly applicable for economic
resources such as money (as in Bell's example noted above), since the agent
is presumed to apply the resource to the most pressing needs or
most value-gaining activities first.  The value expected from each additional
dollar decreases, since there are no items yielding greater value than the
ones already purchased, neglecting effects of discrete purchases.

How does {\it decreasing-marginal-value} apply to {\it life-years}\/?
Consider the collection of achievements and experiences a person may hope to
amass in a long lifetime.  Premature ending of that life would generally
require that some of the items be removed from the collection---undoubtedly
those of least importance.  Progress toward goals may be viewed in a similar
way.  It makes most sense to take the steps yielding the most benefit, given
that there is not enough time to complete the goal.  In each case we reach the
conclusion that additional years have decreasing marginal value.

Of course, this conclusion is dependent on several further assumptions.
First, it is assumed that achievements, experiences, and progress toward goals
is linearly related to additional years.  This is at best an approximation,
and it is easy to think of several reasons it should be significantly violated.
Perhaps progress towards goals accelerates as they are approached, or
one learns to achieve faster with experience.

The second major simplification concerns the
continuity of these items.  Measuring them in
discrete milestones would be more realistic and would have a dramatic impact on
risk aversion.
We might still expect to see decreasing marginal value for life years in the
long-term, but would also expect dramatically {\it increasing} value for
lifetime increments in
the immediate future.  The usual example is the \mf{father}{mother}
who would pay a large
premium in life expectancy to achieve a greater probability of living through
\mf{his}{her} child's college graduation.  All-or-nothing goals present a
similar situation.

A third problem is uncertainty.  The decreasing marginal value argument works
for money partly because agents know for certain how much they have to
allocate towards consumption, at least in the short run.  People do not
generally have such reliable estimates of their lifetimes, so they cannot
plan their actions optimally.  This is perhaps a good argument for ordering
all efforts and experience-quests in decreasing value, therefore contributing
to risk aversion.  Unfortunately, inherent sequentialities of life and other
types of interactions may rule out this ordering in practice.

I have deliberately employed this narrow interpretation of
{\it decreasing-marginal-value} to minimize overlap with the other influences
on risk aversion for {\it life-years}.

These other influences are due to a peculiarity of the measurement scale for
lifetime.  Since {\it life-years} is a quantity of time, it is laid out in
a distinct fashion: all additional time is added on the end.  This
may seem a trivial point, but it has a substantial (perhaps unexpected)
effect on risk aversion.  

To illustrate, let us consider two values of {\it life-years}: $n$ and $n+k$.
The difference
is not just $k$ years, it is {\it those $k$ years from $1985+n$ to $1985+n+k$}.
Higher values of $n$ mean that the benefit from the extra $k$ years of life
will not be realized until further in the future.  It is widely accepted that
economic returns in the future have less value;\footnote{Though widely
accepted, the rationale behind discounting can be quite complex.  The presence
of positive interest rates is clear evidence that discounting is appropriate,
yet the underlying economic justifications combine several diverse components:
value of capital for production, uncertainty, risk aversion, variation in
income streams over lifetime, and irrational behavior are some of the
explanations.  Olson and Bailey~\cite{Olso} try to distill a notion of
time preference from this conglomeration, but it is not clear that their
results are
transferable to health attributes---especially {\it life-years}.} can this also
be true for {\it life-years}?  If so,
we will say that {\it time-preference} is an influence on risk aversion.

Health economists and policy analysts make a habit of assuming positive time
preference for {\it life-years}, usually by analogy to economic products.  The
validity of this analogy is questionable, since many of the
justifications are specific to this class of goods.\footnote{From the
standpoint
of {\it societal} preference for years of life the analogy may be more
realistic.  Raiffa, Schwartz, and Weinstein~\cite{RaifSchw} point out that
the discounting
of life years in cost-effectiveness analysis is justified under an assumption
that the dollar value of a current life year is time invariant.  While such
an assumption and its conclusion are valid for making resource allocation
policy, this does not necessarily have implications for the utility
function of an individual patient.}  Concern about legacy might
explain the phenomenon, since
earlier earnings have a greater contribution to the value of one's estate at
a fixed point in time.   Belief that the world will be a significantly better
or worse place in the future can also have an
impact on {\it time-preference}.  There may be more compelling justifications,
though none have occurred to me.  My aim here is not to argue for or against
the influence, only to suggest its potential applicability.

The final and possibly most important influence is
{\it age-preference}.  Each additional life year comes at a higher age, so
preferences for years at different ages will naturally affect risk aversion
properties.  There are many obvious reasons for having different values for
different ages, and some that are not so obvious.  Physical attributes would
tend to favor younger ages, though physical aspects taken account of in other
health status attributes should not be considered here; the tendency of
mental or emotional attributes are less clear.  The criteria that would
support influence in either direction are too numerous to discuss here.  In any
case, it is certainly an individual
matter, one deserving serious attention in considering preference for
{\it life-years}.

The purpose of this exercise has not been to decide whether individuals
should be risk averse for {\it life-years}, but to point out the surprising
complexity behind what was supposed to be an intuitive concept.  It should
be obvious at this point that the interpretation of the qualitative behavior
of a utility function is highly dependent on the attribute in question,
underscoring the need for a separate module for translating between domain
concepts and technical modeling vocabularies.

\subsubsection*{Risk Aversion for Other Health Attributes} 

It would also be useful to define risk aversion properties for health-related
attributes other than {\it life-years}.  In creating these definitions, it
would be necessary to proceed as above for each attribute, considering the
possible influences on risk posture and their applicability in particular
cases.  Of course, we must also heed the requirements imposed by the
measurement scales.

Consider, as a brief example, the attribute {\it hospital-confinement},
measured by the number of days spent in a hospital bed.  Note that preference
for {\it hospital-confinement} is {\bf monotonic-decreasing}.  Gafni and
Torrance~\cite{Gafn} suggest that preference in this case would also
be {\bf risk-averse}, since each successive day is considered worse as the
patient becomes weary of \mf{his}{her} situation.  If instead the patient
became accustomed to hospitalization (therefore deriving less disutility
each succeeding day), preference for {\it hospital-confinement} would be
{\bf risk-prone}.

\subsection{Other Qualitative Properties}

Similar definitions may be encoded for qualitative properties in addition
to monotonicity and risk posture.  These include the qualitative behaviors
of single-attribute functions described previously, or other qualitative
utility concepts not currently known to {\sc urp} (such as descriptions
of attribute dependencies, or multiattribute risk properties).

\section{Predefined Independence Conditions}\label{pre-independence}

In chapter~\ref{theorem} {\sc urp}'s extensive facilities for
reasoning about independence conditions were described.  To exploit this
capability, the health preference knowledge base should contain as much
knowledge as possible about the independence conditions that exist among
the built-in {\sc urp} attributes.  Defining this part of the knowledge
base is similar in spirit to the predefined qualitative properties; the
difference is only in the nature of the assertions represented.

Consider as an example our two favorite attributes, {\it life-years} and
{\it health-status}.  Earlier (section~\ref{monotonicity}) I claimed that
longer lives are preferred to shorter ones, and represented that as a
monotonicity assertion in {\sc urp}.  While this statement also includes
the qualifier ``all other things being equal,'' there was no qualification
regarding the level at which the other attributes were fixed.  To say that
this level does not matter is equivalent to an assertion of
{\bf preferential-independence} of {\it life-years} from the other
attributes (in this example only {\it health-status}\/).

But suppose that there is some value of {\it health-status} that is so bad that
one would prefer to die than to live in that state of health.  For example,
an individual might express a desire that life-support be discontinued if
\mf{he}{she} becomes a vegetable.  We would encode this preference in the
{\sc urp} knowledge base by including the following two assertions in place
of the original monotonicity assertion:
\begin{itemize}
\item[] ({\bf monotonic-increasing} {\it life-years} $|$ {\it health-status} $\not=$ brain-dead)
\item[] ({\bf monotonic-decreasing} {\it life-years} $|$ {\it health-status} $=$ brain-dead)\footnote{If the individual was merely indifferent to life
expectancy as a vegetable, \mf{he}{she} would not care if the plug was pulled
or not.  A decreasing conditional utility function for life years implies that
utility for immediate plug-pulling is strictly greater than that for delayed
plug-pulling, which in turn is strictly preferred to living the maximum
technological life.  Note that these direction assertions say nothing further
about the relative values of life under the different health states.}
\end{itemize}

Now that we have allowed a ``state worse than death'' we can no longer
assume {\bf preferential-independence}.  Instead we can assert a weaker
independence condition (introduced in section~\ref{weak-axioms})
\begin{itemize}
\item[] ({\bf generalized-preferential-independence} \{{\it life-years}\} \{{\it health-status}\})
\end{itemize}
by noting that the preference ordering for {\it life-years} is completely
reversed in the extremely morbid state.

These three assertions capture an important part of the individual's expressed
preferences directly in {\sc urp}'s technical vocabulary.  Just imagine how
much smoother deciding medical ethics questions would be for the law courts if
everyone recorded their
preferences in {\sc urp} assertions, rather than in casual remarks to family
members!

Many of the other attributes that may be considered in health decisions can
be uncontroversially declared to be independent (for some form of
independence); these declarations should be included in the {\sc urp} knowledge
base to save time on utility formulations.  For example, patients will not
care much about cost for medical care that is paid through insurance, and
society's preference for that money does not have any relation to the health
of the patient it is spent on.  Therefore, we can usually assert the strongest
independence axiom for cost
\begin{itemize}
\item[] ({\bf value-independence} \{{\it cost}\} {\it everything-else}\/)
\end{itemize}
or at least assert it when we know that the expense is not borne by the
patient.  Preference for everything else is also independent of cost, since
{\bf value-independence} is a symmetric relation.

\section{Special Functional Forms}\label{special-forms}

The final component of a domain preference knowledge base is a representation
for special-purpose functional forms that are considered useful for particular
attributes or combinations of built-in attributes.  Utility modelers in
specific domains have developed and tested many such models, and it would be
useful to incorporate these experiences in {\sc urp}.

\subsection{DEALE}\label{deale}

The importance of the attribute {\it life-years} in medical decision making
has been noted above.  However, deriving a precise probability distribution
over possible lifetime lengths is often difficult in practice.  Beck, Kassirer,
and Pauker~\cite{BeckKass} describe a simplified model of life years:
the declining exponential approximation of life expectancy, or DEALE.
The DEALE
is computed solely from actuarial mortality rates ($\mu_{ASR}$, the mortality
rate adjusted for age, sex, and race), combined with excess
mortality rates due to patient-specific disease conditions (the $\mu_i$s).
\begin{equation}\label{deale-e}
LE = \frac{1}{\mu_{ASR} + \sum_i \mu_i}
\end{equation}
The DEALE is a very convenient model, since it is determined completely by the
$\mu$s, which are relatively available in or computable from the literature
and may be collected in different combinations for various patient states.
Indeed, it is used routinely in decision analyses performed at NEMCH, including
the example discussed in chapter~\ref{r-exam}.

$LE$ in equation~\ref{deale-e} may be considered as a proxy measure for
{\it life-years}, or may be treated as a summary statistic for the distribution
over survival times implied by the DEALE model.  Note that $LE$ is a
{\it sufficient statistic}; there is exactly one DEALE survival
curve corresponding to any particular $LE$.  The interpretation decision is
important, since consideration of the qualitative behavior for preferences
over $LE$ often depends on the particular point of view.  In the example
analysis of preference for DEALE life expectancy in
section~\ref{behavior-x}, $LE$ was implicitly taken to be a proxy
for {\it life-years}.  It turns out that direction of preference (monotonicity
assertions) and the presence of risk aversion for {\it life-years} correspond
directly to monotonicity and risk aversion for DEALE $LE$ under its
interpretation as a summary statistic for a survival
distribution.  In general,
transformations like this may not preserve these properties.  It is important
to define these correspondences in the knowledge base along with specifications
for the special models.\footnote{In empiric tests of the DEALE approximation,
Beck, Kassirer, and Pauker~\cite{BeckKass} only considered its validity as a
measure of expectation---not as an approximation of the actual distribution of
{\it life-years}.  Therefore, extreme caution must be observed in taking the
distribution literally, especially in consideration of preference properties
of the attribute.  This is a compelling argument for sticking to qualitative
behaviors as much as possible, since few utility functions preserve
implications over different interpretations of survival distributions (the
risk neutral form is a notable exception).}

\subsection{Quality-Adjusted Life Years}\label{qaly}

One of the most widely employed utility scales of medical decision
analysis is the quality-adjusted life year (QALY)~\cite{Plis}.
A utility model based on QALYs is attractive to clinical decision analysts
because it is computationally simple, relatively easy to assess, and it offers
an intuitive interpretation for the numbers.  The intuitive notion is
based on the premise that a year spent in a morbid health state is ``worth''
some fraction of a year of good health.  Pliskin, Shepard, and
Weinstein~\cite{Plis} report necessary and sufficient utility-theoretic
conditions for applying a utility function based on QALYs, which may be
encoded directly in {\sc urp}'s technical vocabulary.  I will outline these
conditions below, following the development of Pliskin et al.

QALY may be appropriate when constructing a utility function for two
attributes: life-years and health-status.  It is assumed that health-status
is constant over the entire lifetime or that we can choose a health state
that would be equivalent to the particular time-stream of health states
(denoted by a vector ${\bf q}$) we are
faced with.  That is, if $u_{q|y}$ is the utility function for health status
given a particular number of life-years, $y$, then there exists a health
state $\overline{q}$ such that
$u_{q|y}(\overline{q},\overline{q},\ldots,\overline{q}) = u_{q|y}({\bf q})$.
For determining the applicability of QALY, we take the ability to choose
the constant health state equivalent of a time stream of states for granted.
Note that this task in itself may require a major preference modeling effort,
and that the value of $q$ may be a vector quantity made up of a variety
of health-status sub-attributes.

The simplest version of the quality-adjustment utility function is
\begin{equation}\label{qaly-1}
	u(y,q) = yh(q)
\end{equation}
where $h(q)$ is defined as the fraction of a year in the perfect health state
that the patient considers equivalent to a year in state $q$.  This form is
valid under the following conditions:\footnote{The assumption that preference
for life-years is {\bf monotonic-increasing} is already part of the knowledge
base.}
\begin{itemize}
\item[] ({\bf joint utility-independence} \{{\it life-years}\} \{{\it health-status}\})
\item[] ({\bf constant-proportional-tradeoff} {\it life-years} {\it health-status}\/)
\item[] ({\bf risk-neutral} {\it life-years}\/)
\end{itemize}

Conditions one and three are familiar {\sc urp} concepts, but
{\bf constant-proportional-tradeoff} is a qualitative property of attribute
interaction, a category of utility-theoretic knowledge not yet known to
the program.  Assertions like these can be very useful for validating or
constraining multiattribute forms, therefore future extensions of {\sc urp}
should exploit them extensively.  Reasoning about these kinds of properties
would not be very different from {\sc urp}'s manipulation of other utility
concepts.

In cases where {\bf risk-neutral} does not hold, the form of the QALY utility
model is
\begin{equation}\label{qaly-2}
u(y,q) = \left\{ \begin{array}{ll}
			\frac{1}{r}\left(\left[yh(q)\right]^r-1\right)+r &
				{\rm for}\;\;r\not= 0 \\
			\log \left[yh(q)\right] & {\rm for}\;\;r=0
	   \end{array} \right.
\end{equation}
where $r$ is a measure of risk aversion.  This follows from
{\bf constant-proportional-risk-posture} for life-years, implied
by the {\bf constant-proportional-tradeoff} assumption.  These results are
derived in the paper of Pliskin, Shepard, and Weinstein~\cite{Plis}.
I have restated them to illustrate how they may be incorporated in the
{\sc urp} knowledge base.

{\sc Urp} is already able to derive a two-dimensional form for $u(y,q)$ given
{\bf joint utility-independence}, and a single-attribute form for $u(y)$ under
assumed behaviors {\bf risk-neutral} or
{\bf constant-proportional-risk-posture}.
The leap comes in the use of the function $h$, a nonlinear transformation
of $u_q$, in equations~\ref{qaly-1} and~\ref{qaly-2}.  Thus, to implement
QALY in {\sc urp} we would have to give an interpretation for the
function $h$---how it is assessed and its relation to $u_q$.  More directly, we
would support
an assertion that QALY is appropriate at a high level, associating that
assertion with the three (or two) implied assumptions listed above and the
related functional form for life-years and health-status.

\subsection{Time Streams}

As illustrated in the utility model for health-status over a lifetime,
it can be important to model preferences for outcomes represented by streams
of states over time.  Consequently, utility theorists have developed special
models to deal with this kind of situation (see Meyer~\cite{Meye} for
a discussion of the general issues).  Due to the special structure of
time-period attributes (sequentiality, constant dimension), intuitive concepts
of preference may be stated succinctly---resulting in models far simpler than
the general case.  For example, for $n$-period streams of the form
$x = (x_1,\ldots,x_n)$, the concept of {\it successive pairwise preferential
independence} is equivalent to the {\sc urp} concept:
\begin{itemize}
\item[] ({\bf preferential-independence} ($X_i$ $X_{i+1}$) $X_{\overline{i,i+1}}$), $i=1,\ldots,n-1$
\end{itemize}

To build expertise about preference modeling over time into {\sc urp}, we would
include definitions for those concepts developed specifically for utility
analysis of outcome streams.  In general, these concepts are combinations of
general-purpose independence conditions, or other qualitative properties, that
are already known to {\sc urp}.  Therefore, we can represent these in the
knowledge base simply by using the concept name as a definition to be expanded
into lower-level assertions (similar to {\sc urp}'s handling of {\it joint}
independence described in section~\ref{joint-independence}).  Alternatively,
{\sc urp} can reason about these concepts at two levels: reduced to lowest
terms and as top-level concepts.  This latter possibility is advantageous
when the concepts are closely related to specific utility models.

Several analysts have developed their own models of preference over time for
specific application projects.  We could include these models with their
associated utility assumptions directly in the {\sc urp} knowledge base,
providing a wide variety of time models to choose from.  For example,
in an application of decision analysis to prostate cancer,
Higgins et al.\ \cite{Higg} employed an independence condition they called
the ``separability assumption'' to simplify time streams of health states to
an equivalent (with respect to preference) symptom-free outcome.
Bell~\cite{Bell77} gives sufficient conditions for a utility function
that allows certain limited dependencies of preference among elements of a time
stream.  While {\sc urp} can reason about the first principles from which both
of these
were derived, direct encoding of the special model leads to more efficient
model generation and superior assessment, interpretation, and explanation
ability.

\subsection{Value of Life}\label{l-value}

Economists and public policy analysts have long studied models for placing
economic values on life and health.  Some of these models are close enough
to utility-theoretic treatments that they may be encoded in the {\sc urp}
technical vocabulary for inclusion in a domain preference knowledge base.

For example, Howard's model for measuring the value of small risks of death
or disability~\cite{Howa} assumes that consumption and lifetime can be
traded off proportionately and that {\bf constant-risk-aversion} holds over
the
function combining consumption and lifetime.  From this he derives a measure
of the value associated with small risks of death.  The model is extended to
disability under assumptions about health states similar to those required
for the QALY model (described in section~\ref{qaly} above).  It might be
convenient to have this model, as well as other similar models, available in
{\sc urp} because of its simple structure and attractive explanatory power.
Indeed, Holtzman's rule-based system for decision analysis in the domain
of infertility problems~\cite{Holt85} uses Howard's model as part of its
underlying value function.

\section[Summary: Using the Knowledge Base]
{Summary: Using a Domain Preference Knowledge Base}

The purpose of this chapter was to demonstrate that while a domain-independent
mathematical modeling system like {\sc urp} must reason in terms of a technical
modeling vocabulary, it is possible to define a layer of domain knowledge that
can be combined with the modeling system to yield a more complete modeling
tool.  In introducing the {\sc urp} health preference knowledge base, I
suggested that such a corpus may be useful as both an interface to expert
systems and a library of model components for a human analyst.  Advantages of
separating the modeling kernel from concepts of the application domain are
described in detail in another paper~\cite{Well85b}; here I am more
interested in speculating about the content and form of knowledge about
preferences in a particular domain.

The module that maps between domain concepts to
the technical modeling vocabulary may in general consist of model templates,
model component
specifications, assertions about specific components, or special reasoning
strategies.  For {\sc urp}, I have suggested that the forms of domain knowledge
include:
\begin{itemize}
\item built-in attributes
\item predefined qualitative properties for single-attribute preference
\item predefined independence conditions among attributes
\item special-purpose functional forms
\item existing preference measures (e.g.\ health status indices) described in
the literature
\end{itemize}
The health preference knowledge base is summarized in
appendix~\ref{medical-ax}.

An expert system using {\sc urp} for preference modeling would communicate
with the modeler through the domain concept mapping module.  Reasoning events
in the program would be linked to preference concepts, directing
the model construction process.  For example, it would be up to the expert
domain program to decide which attributes are important for a particular
decision problem (for some expert systems this would be the same for every
problem instance), and to determine which qualitative properties apply.
We can easily envision a {\sc mycin}-like system containing rules such as
the ones illustrated in figure~\ref{rules-f}.

\begin{figure}[htbp]
\begin{tabbing}
m\= RUL\= THENm\= \+ \kill
RULE001: \\
\>\underline{IF}\> There are no states worse than death \\
\>\underline{THEN}\> ({\bf joint preferential-independence} \{{\it life-years}\} \{{\it health-status}\}) \\
\>\> ({\bf monotonic-increasing} {\it life-years}\/)
\\
RULE002: \\
\>\underline{IF}\> Financial costs are not borne by the patient \\
\>\underline{THEN}\> ({\bf value-independence} \{{\it cost}\} {\it everything else}\/) \\
\>\> ({\bf monotonic-decreasing} {\it cost}\/) \\
\end{tabbing}
\caption{Constructing preference models in a rule-based expert system.}
\label{rules-f}
\end{figure}

Similarly, the domain expert system would use the result of {\sc urp}'s
model analysis to make decisions, drive further preference modeling, and
generate explanations and justifications.  While it would be relatively
straightforward to give
a rule-based system access to {\sc urp}'s results (for example, by providing
a predicate to test dominance, or describing the qualitative structure of
the preference model), making intelligent use of the analyses is a subject
for future work.

\chapter{Conclusion}\label{con-c}

Having examined the mechanisms of preference modeling in some detail,
it is appropriate to step back and examine again the task as a whole.
In evaluating the contributions of this work from a larger perspective, it
helps to keep the following questions in mind:
\begin{enumerate}
\item What are the problems that {\sc urp} tries to solve?
\item How does {\sc urp}'s approach compare to related efforts?
\item What insights and specific achievements have evolved from this work?
\item What are the shortcomings of {\sc urp}, and how might they be remedied?
\item What is the practical potential for including preference models in
decision making programs?
\end{enumerate}

In the discussions below I address these and other issues.

\section{Perspectives on this Research}\label{per}

The goals and patterns of emphasis in this project have been influenced by
interests in several different fields.  I have found it useful to classify
the potential benefits of this line of research into three areas, each
representing a separate audience for this material.  In this section I discuss
what I believe are the important motivations and
contributions of this work from each perspective.

\subsection{Decision Making Programs}

It seems an inescapable fact of technology that more and more
decisions affecting society will be performed by computer programs, in one
capacity or another.
The spread of expert-systems-building methodology, including
commercially available generation tools, has spawned many projects seeking to
develop programs to make decisions in some specialized area
requiring considerable expertise.  These efforts have
demonstrated enough promise to indicate that computers will
play an increasingly large role in providing expert-level advice and
decisions to broader categories of users.

Much has been written about requirements for these systems to become
acceptable, particularly in sensitive areas like medicine.\footnote{Examples
in this section are taken from work
in knowledge-based systems for medicine.  Much of the pioneering work in
applied AI has been in medicine, and medical problems often have the
characteristics of difficult decisions that motivate formal approaches.
Besides, it is the area with which I am most familiar.} 
Writers of these papers (Szolovits and Pauker~\cite{SzolPauk79}, for example)
often point out that programs must be able to explain and
justify their conclusions and their knowledge bases should clearly
reflect knowledge used (or usable) by experts in the field.  But work on
explanation has been mainly concerned with the elucidation of reasoning
structures and mechanisms, providing justification for the program's inferences
about the state of the world.  At best, recommendations are justified
by explaining the program's beliefs about what would happen under various
strategies under consideration.  There is never any explanation of why the
program
considers one outcome to be more desirable than another, because such
comparisons are rarely (if ever) examined explicitly.

In using a decision-making program that employed preference models, the
consultee would be able to query the system about its underlying preference
assumptions.  This capability is especially important if
preferences can vary significantly among different decision
makers.\footnote{Studies by McNeil, Weichselbaum, and
Pauker~\cite{McNeWeic} and Pauker, Pauker, and McNeil~\cite{PaukPauk}
illustrate the widespread differences in patient preferences for
particular health outcomes, as well as the importance of these
differences for decision making.  A third paper~\cite{McNePauk}
highlights variations in preference for {\it life-years\/} and argues
that preferences are crucial in a large class of medical decisions.
Kassirer~\cite{Kass} argues more generally that preferences of
individual patients should play a central role in clinical decision making.}
Note that even a
program that explicitly considers tradeoffs may be unexplainable if its
conflict resolution method is sufficiently ad hoc.

Often, it is not necessary to have a sophisticated explicit preference model.
In fact, most AIM (for {\it AI\/} in {\it M\/}edicine) programs that make
decisions are in domains where a simplified
objective structure is sufficient.  For example, {\sc mycin}~\cite{Shor} has a
single objective---prescribe drugs to cover for all likely infecting organisms.
Since most of the drugs
in {\sc mycin}'s repertoire are fairly benign, this simple goal may produce
results very similar to a program embodying the real goals of the patient.
Here most of the effort is in determining the likelihoods of each
organism---what might be called the probabilistic model formulation stage in a
decision-analytic approach.  In general, problems where the decision
is uniquely determined by the result of the program's reasoning about the state
of the world are not prime candidates for a preference modeling approach.

Sometimes it is possible to deal with small deviations from the
single-objective case without resorting to full-fledged preference models.
{\sc Abet}~\cite{Brom} chooses a therapy designed to restore a patient's
proper electrolyte and pH levels.  Conflicts between the individual electrolyte
objectives are mediated through the use of an ad hoc urgency mechanism.
Imbalances of different electrolytes may be compared in terms of health risk,
in effect turning
the multiattribute problem into one of a single attribute.  Interactions
which would invalidate this translation are treated in a special-case
fashion.  Note that this method of modeling objectives is entirely implicit
in the program design, and it is doubtful that the designer thought of the
model in these terms.

Many decisions in medicine as well as other fields, however, cannot be
forced so easily into such a simple objective structure.  AIM has generally
avoided such problems, concentrating instead on diagnosis and reasoning about
physiology.  This is appropriate, since it represents the greatest part of
medical expertise.  And in cases where the diagnosis uniquely determines
the decision, it is a complete solution.  But for some important and difficult
decisions,
another type of expertise is required---a more fundamental decision making
expertise.  A necessary approach toward capturing that expertise is to
explicitly represent and reason about the desirability of the various possible
outcomes.

The argument for formal preference models is even more compelling for decisions
made by computers than for human decisions.  Those who object to the practical
use of utility analysis for decision making can claim that unaided human
decision makers may be taking into account criteria that are beyond our
abilities to model.  This claim does not hold that the decision making of
humans
is  superior in every respect, only that utility theory alone does not (and
fundamentally cannot) fully capture all of the subtleties of human preference
choices.  While decision analysts will argue that we do not want to imitate
most of these subtleties, we are undoubtedly missing some positive features.

Computer programs that make decisions are themselves formal objects.  For
this reason, it is more difficult to argue that we would miss
something by treating the preference structure formally.  If we cannot tell
what the preference model of a decision making program is by inspection and
analysis, it is because the model is buried within the knowledge and control
structures, not because there is anything magical or inherently unmodelable
going on.  The program designer has imposed an implicit preference structure
on the process, which may or may not conform to \mf{his}{her} own internal
model.

The idea of separate, explicit preference models is also a good policy from
the standpoint of modularity in knowledge-based system design.  Modifications
or additions to the knowledge base may have unpredictable and undesirable
effects on the program's objective structure if that structure is allowed
to be implicitly distributed throughout the program.  Once again, the use of ad
hoc tradeoff mechanisms shares many of the defects of using no explicit
mechanism at all.

In summary, the presence of an explicit objective structure enhances the
capabilities
of the system in three important ways.  First, the decisions are more
explainable and justifiable.  Second, explicit representation of objectives
greatly improves the modularity, and therefore the integrity, of the system.
Finally (and perhaps most importantly), the decisions will be better---at least
according to certain formal theories of decision making.  Any program working
within a reasonably complex decision space is almost certain to produce
contradictions (with respect to axiomatic expected utility theory) if it does
not expressly attempt to avoid them.

\subsection{Utility Analysis}\label{u-per}

Researchers in decision analysis, as well as other areas of Operations
Research and Management Science, often lament the fact that their techniques
are not in widespread use by real-world decision
makers.\footnote{Little~\cite{Litt} begins a discussion of modeling tools
(what would now be called Decision Support Systems) by declaring ``The big
problem with
management science models is that managers practically never use them.''
While the statement is a bit dated, the sentiment is still quite true.  The
proliferation of personal computers and spreadsheet software have made
the use of simple forecasting models more commonplace, but for the most
part the more sophisticated models see little application.  It is
fair to say that with respect to theory, practice has been left in the dust.}
This is certainly not because
these decision makers do well enough on their own, or because the theories have
not been developed enough.  Bell~\cite{Bell82b} points out that decision
analysts themselves fail to apply the methodology to their own problems.
There may be many reasons for this failure, but the main cause is undoubtedly
the tremendous effort and difficulty involved with using the formal models.

In the case of utility theory, there might be a question related to the
admissibility of the axioms on which it is based.  But this seems to be
a negligible problem, since the axioms are generally very weak and
acceptable to prospective decision makers.  Besides, analysts are often
extremely
willing to use much cruder models that have either no theoretical basis
or implicit assumptions that are demonstrably inappropriate for the problem
at hand.  Another problem is a general skepticism regarding the legitimacy
of techniques used to assess utility functions.  Formally the theory is
airtight, but in practice subjective judgments are an inextricable part of
the process.
Thus, the main barriers to the use of utility analysis are the practical
difficulties of constructing and interpreting utility functions and a lack
of confidence in the judgments required for their assessment.  In the rest of
this section, I will describe how {\sc urp} and the overall framework described
here may help to alleviate these problems.

\subsubsection*{Incomplete Specification of Preference Model}

By removing the restriction that requires utility functions to be completely
specified before analysis can begin, we add a great amount of
flexibility to an assessment system.  Even when employing the most simplifying
assumptions, the task of assessing a utility function in complete detail
is tedious, painful (requiring soul-wrenching decisions regarding unpleasant
events), and subject to serious cognitive biases.  If
we are able to derive a decision before specification is complete, we
alleviate much assessment effort.  We may feel more confident
in the result, because it depends on fewer and weaker assumptions.  The
inability
to use partial information is probably the major reason that the mathematically
complex models developed by utility theorists to represent weaker assumptions
are rarely used in applications.

We have seen above that {\sc urp} is able to derive some interesting
conclusions and sometimes decisions from incomplete single-attribute utility
functions.  The example used earlier is far from unique; the commonality
of situations where partially defined utility functions are adequate is
the impetus for research in stochastic dominance.  In a recent discussion
of the important future developments in decision analysis,
Winkler~\cite{Wink82} emphasizes the promise of utility analysis tools that
can take advantage of incomplete information.

In multiattribute utility, complexity, and correspondingly the strength of
underlying assumptions, is measured by the degree of
interdependence of preference among the attributes.  By relaxing the
restriction to complete specifications, we open up possibilities for applying
multiattribute decompositions that admit limited kinds of dependence (another
promising research area cited by Winkler~\cite{Wink82}).  Multiattribute
utility assessment using current methodology is
difficult enough in the simplest situation---to acknowledge attribute
interdependence is tantamount to acknowledging that utility analysis is
inappropriate.  In fact, I am not aware of a real-world application that
used anything more complex than a multiplicative utility function, or perhaps
nested combinations of multiplicative utility functions.  These
functions are valid only under fairly strong independence assumptions.  This
represents the feasibility limit under current utility assessment
methodology, which is clearly inadequate for credible preference modeling.

{\sc Urp} already has the facilities for generating decompositions based on
more realistic assumptions.  Combining this with the ability to reason about
partial models (still in the future for the multiattribute case) should help
to extend the feasibility frontier.

\subsubsection*{Reasoning About Underlying Assumptions}

The validity of any utility representation depends on assumptions about
the preference structure.  At the most basic level, use of {\sc urp}
requires acceptance of axioms that imply the existence of a utility
function.\footnote{On startup, {\sc urp} asserts the primitive proposition
``({\bf von-neumann-morganstern-axioms}).''  If this assertion is ever
retracted, then {\sc urp} will do something drastic like erase all
conclusions and halt.  Except for this and some assumptions like continuity and
differentiability employed by the mathematical reasoning system, all premises
are explicitly asserted by the user.}  Further conclusions about the utility
function are based on additional assumptions.  Clearly, these assumptions are
important building blocks for model construction.

The underlying premises of an {\sc urp} preference model (qualitative behaviors
and independence axioms) are maintained as propositions in a truth maintenance
system to provide for modular assertion and retraction.  At the very least,
modelers who use this program for developing a utility
function will be aware of what underlying assumptions they are making.
This may induce them to think more carefully about their
simplifications.  Further, examiners of the model can then see what
presuppositions
went into the formulation, and use that knowledge to decide whether to
believe it or not.  The whole process becomes more transparent and more
honest.

Another advantage is the explicit representation of the relations between
various types of assumptions.  This knowledge is built into the program,
to be used for both reasoning and explanation.  Modelers may find that
a particularly useful assumption is implied by several different sets of
weaker primitive axioms and can choose the set which appears most justifiable.
It may also prevent the analyst from making strong assumptions (or thinking
that \mf{he}{she} is making strong assumptions) that are unnecessary for the
model in question.

Further discussion about the importance of assumptions in a more general
mathematical modeling context may be found in a forthcoming
paper~\cite{Well85b}.

\subsubsection*{Structural Sensitivity Analysis}

Analysts will often attempt to validate their results by performing a
sensitivity analysis on their model.  The purpose of this analysis is to
examine the effect of perturbations in parameter values on the overall
result.  If it turns out that small changes of the parameters over their
realistic ranges does not have a large effect---that is, it does not change
the decision---then the analyst will be confident in the correctness of
the result.

It may be argued that the restriction to completely specified models is
not much of a restriction, since we can simply choose baseline values for
the parameters arbitrarily and use sensitivity analysis to account for
variations.  But this will not lead to a satisfactory validation, because only
a few parameters are
varied at a time.  In moderately complex decision analyses, there may be
dozens of parameters.  In such cases, the model may prove unjustifiably
insensitive to variations in only a few.  Variation of more than two or
three parameters turns out to be both computationally infeasible and
difficult to interpret.

One reason that the model may be unjustifiably insensitive is that there
may be couplings among the parameters that are not explicitly represented.
That is, a built-in redundancy or other interaction captured in the
estimates.  Part of
this may be eliminated by decomposing the higher-level parameters of the
decision to a smaller number of common ``influences'' \cite{Howa}
affecting them, and expressing the higher-level parameters as functions of the
lower-level ones (this mechanism is available in decision analysis tools).
But this does not solve the problem, since there may be obvious
relations among the parameters without any easily identifiable common
components.  Choice of parameters is often dictated by external factors such as
measurability, convention, or intuitive appeal, which may make them difficult
to decompose.  Perhaps these may be captured by some other sorts of
constraints,
using inequalities rather than definitions.
Something like this may be possible even within the current framework for
sensitivity analysis, but it is more natural in a system that avoids
baseline estimates in the first place.

A fundamental limitation of traditional sensitivity analysis is that
we can
vary the parameters, but not the underlying model.  It is impossible to
ask questions like ``What if this particular assumption is wrong?''
Recognizing the importance of such questions, Farquhar~\cite{Farq83}
has called for the development of procedures for performing {\it structural
sensitivity analysis} which would examine the effects of more fundamental
changes in the model.

The potential for structural sensitivity analysis in {\sc urp} has been pointed
out earlier in this thesis.  In the multiattribute decomposition example
(section~\ref{m-extension}), retraction of an assumption led to a significant
restructuring of the preference model.  Assertion and retraction of qualitative
behaviors may be handled dynamically, resulting in a wide range of functional
forms and parametric constraints.  The possibility for switching between
alternate psychological theories for interpreting preference choices was
discussed in section~\ref{descriptive-interpreters}.  This would be a
particularly novel form of structural sensitivity analysis.

Efficiency in structural sensitivity analysis is achieved through maintaining
dependencies between premises and derived inferences about the preference
model.  At the propositional level these dependencies are recorded by
{\sc rup}.  Dependency-directed reasoning has been a subject of much study
by AI researchers in recent years; it would be no surprise if a capability
for structural sensitivity analysis was first developed in systems employing AI
techniques.  It will be interesting to see how dependency-directed inference
may be incorporated into other aspects of {\sc urp}'s reasoning about
preference models.  McDermott \cite{McDe83} offers suggestions for
maintaining dependencies among inequality assertions.  His techniques
are likely to be useful in extending {\sc urp} to handle preference
choice information---basically assertions of inequalities among utility
function evaluations.

\subsubsection*{Explainability}

It is undoubtedly easier to describe in intuitive terms a preference model
that is based on qualitative characteristics than one that is a purely
mathematical object.  Each conclusion made in constructing the model is
traceable
to base-level premises, which should have some meaning to whoever asserted
them (a human user or some level of interface).  The program should be capable
of providing a good explanation of the model structure---after all,
the program constructed the model in the first place.  This is somewhat
analogous to the explanation work of Swartout~\cite{Swar83}, where
the program is more explainable because it is written by an automatic
programmer.  In our case, the model is more explainable because it is
constructed by an automatic modeler.

But of course, explainability does not come for free.  As Clancey points
out~\cite{Clan83b}, the knowledge that is best for reasoning is not
necessarily appropriate for explanation and justification.  And Swartout's
system~\cite{Swar83} would not work with just any automatic programmer.
{\sc Xplain} generates the expert system based on a detailed domain model
and a knowledge base of domain principles.  Special explanation problems
arise in mathematical modeling applications, particularly in describing
quantitative relationships.  Kosy and Wise~\cite{Kosy} have demonstrated
an approach for explaining simple spreadsheet models; it
may be possible to extend their methods to other quantitative relationships.
The major explanation issues have
not been explored extensively in {\sc urp}, but there is reason to suspect that
there will be some improvement over traditional approaches.  Decision-analytic
models which do not maintain ties between the
quantitative constructs and their qualitative justifications are notoriously
opaque.

\subsubsection*{Utility Analysis: Summary}

Some of the benefits of the {\sc urp} approach for utility analysis were
not discussed in this section, because they are described in some detail
elsewhere in the thesis:
\begin{itemize}
\item Encoding knowledge about utility theory (specifically multiattribute
decomposition) in an explicit representation (chapter~\ref{knowledge-base})
\item Interpretation-independent representation of assertions (sections
\ref{q-b} and~\ref{model-i})
\item Tying model assertions to domain knowledge
(chapter~\ref{domain-p})
\end{itemize}

In summary, facilities provided by {\sc urp} and potential capabilities of
future programs built within the {\sc urp} framework address many of the
problems associated with utility analysis under current methodology.
By emphasizing underlying assumptions and allowing partially specified
functions, {\sc urp} supports a qualitative view of utility.  This
qualitative basis in conjunction with {\sc urp}'s framework for
dominance-proving and structural sensitivity analysis provides a response,
or even a solution to each of the complaints about the multiattribute
utility approach enumerated by Starr and Zeleny~\cite{Star} in a
recent survey of decision making with multiple criteria.

\subsection{Mathematical Modeling}

The third and final perspective comes from viewing utility analysis as just
one kind of mathematical modeling.  Mathematical models are used extensively
in just about all branches of physical and social science, and one might
regard the skill and knowledge involved in creating and analyzing them
an important type of expertise.  Of course, this expertise is very different
for different modeling tasks, but undoubtedly there are some general
principles and mathematical capabilities that are broadly applicable.

I have found the preference modeling task to be a particularly good example
for studying mathematical modeling expertise, because it deals with many
of the central issues I believe arise more generally.  In addition to
the issues of reasoning with mathematics, there are a set of
issues pertaining more specifically to the construction of formal structures
representing a simplification of the real world.  The remainder of this section
highlights the features of {\sc urp} which may have implications for general
issues in building knowledge-based systems for mathematical modeling.

\subsubsection*{Mathematical Expertise}

A program that is expert at mathematical modeling should naturally be
competent in mathematical reasoning.  It is important to note the distinction
between
numerical computation and mathematical analysis.  We are interested here in the
latter, deeper type of mathematical capability.

{\sc Urp}'s mechanisms for reasoning about qualitative behaviors
represent a step in the direction of deeper mathematical knowledge.
Because the program reasons about behaviors in terms of their
mathematical definitions, the concept associated with them may be applied
in a variety of ways, some unanticipated during the original design of
the program.

Usually mathematical models are constructed to answer a set of questions
that may be expressed in a formal language.  If the types of questions
are known in advance or are of a highly restricted form, it is
feasible to develop algorithms to answer each type of allowable question
for each qualitatively distinct possible model structure.  But there is
often a substantial benefit to be gained by taking a more general
approach.  We may wish to restructure the models dynamically (as in
structural sensitivity analysis, discussed above), or permit a much
broader range of queries about the model.  In such cases, the strict
algorithmic approach breaks down, requiring a much more flexible kind of
problem-solving behavior.  To gain this flexibility, expert programs for
mathematical modeling will have to look a lot more like theorem provers than
like the model analysis packages of today.

\subsubsection*{Emphasis on Assumptions}

I have already discussed in some detail the benefits of reasoning
directly about assumptions underlying preference models.  The only thing
to add here is the observation that assumptions are a fundamental part
of virtually all modeling disciplines, therefore, we should expect
analogous benefits in the general case.

\subsubsection*{Measurement Properties}

As argued in section~\ref{measure-discussion}, programs that manipulate
quantities should know something about the measurement properties of those
quantities.  This can prevent some ``common sense'' errors as well as
indicate allowable operations and transformations that may help in
mathematical problem solving.

\subsubsection*{Technical Vocabularies}

The notion of a technical vocabulary developed in
section~\ref{vocabulary} is a useful concept in the design of
knowledge-based systems for mathematical modeling.  The vocabulary is
the language of the domain-independent modeling system, which ultimately
defines the scope of the modeler's expertise.  This language also
provides a basis for building knowledge bases specific to modeling in
particular domains, as illustrated by the health preference knowledge
base specified for {\sc urp}.  In general, a well-designed technical
vocabulary will lead to a clean separation of modeling and application-area
expertise.

\subsubsection*{Flexible Use of Algorithms}

When it is necessary to use algorithms coded directly in a
general-purpose programming language, it helps to provide the overall
modeling system with some knowledge about the algorithms available.
Though the ideas have not been developed very far, {\sc urp}'s facility
for specifying dominance-testing algorithms (section~\ref{d-routines})
illustrates some kinds of information that should be useful.  As
mentioned in section~\ref{k-b-model} above, several other programs,
particularly in statistics, have provided similar facilities for specifying
analysis algorithms.

\subsubsection*{Other Components of Modeling Expertise}

Work on {\sc urp} has scratched only the surface of the mathematical
modeling issues described above.
In addition to these, there are several kinds of knowledge not used by
{\sc urp} that are in general important for programs that reason about
mathematical models:
\begin{itemize}
\item Empirical verification of assumption validity 
\item Heuristics to direct search for valid model structures
\item Effects of approximations
\item Computational complexity of model analysis algorithms
\item Qualitative interpretation of model results
\end{itemize}
The possibility of including these components of modeling
expertise in knowledge-based systems has not been adequately explored.
All are probably necessary for a truly expert automatic modeler.

\section{Other Work}

\subsection{AI and Decision Analysis}

Considering the large amount of research that has been concerned with
computerized
decision making and decision aiding, it is surprising (and regrettable) that
there have been so few attempts to integrate approaches from artificial
intelligence (AI) and decision analysis (DA).\footnote{The use of probabilistic
methods in an AI program does not constitute an integration of DA into a
system.  At the very least there must be some principle of expected utility
maximization as a choice criterion.  Bayesian or pseudo-probabilistic inference
schemes are for managing beliefs, not for making decisions based on beliefs.}
I believe that this lack is due to the prevailing perception of the fields as
competitive---that it is necessary to choose one or the other as the ``better''
methodology.  Of course, neither strategy is clearly ``more right,'' rather
each has particular strengths and weaknesses which are highly dependent on the
situation.  Recognizing this, some researchers have attempted to
identify the features or stages of decision situations in which either
methodology is more or less appropriate.  An example is the discussion by
Szolovits and Pauker~\cite{SzolPauk78} of issues arising in trying to cope with
uncertainty in medical diagnostic programs.  While a method of deriving beliefs
does not necessarily imply a method of choosing actions based on beliefs, many
of the issues they discuss are relevant to the choice between AI and DA as an
overall approach.

A different kind of question to ask is ``How might ideas from either discipline
complement the other?''  There are many conceivable ways in which AI techniques
could enhance DA tools (the AI$\rightarrow$DA direction) and DA
approaches could be incorporated in AI programs (DA$\rightarrow$AI).  Although
some have recognized the potential of integrating the two
methodologies~\cite{FeldYaki},
serious attempts at this synthesis have been few and far between.  The
technical issues involved have not been adequately explored, and the precise
benefits to be gained from the integrated system have not been clearly
formulated.

The rest of this section presents some details of a few early attempts to
exploit AI techniques for the improvement of DA systems.  Though none of
these efforts are devoted primarily to utility analysis (and I know of no
other work that is), a review of these systems serves to develop a perspective
for the research described in this thesis.  Use of {\sc urp} for decision
analysis should be considered in the context of these integrated approaches.

\subsubsection*{Decision Tree Generation}

Structuring a decision problem in the form of a decision tree is one of the
primary tasks in performing an analysis.  One of the more promising
avenues for an AI$\rightarrow$DA approach is to use a domain knowledge
base to formulate a decision problem from a description of the
situation, for example, disease states of the patient.

Rutherford et al.\ \cite{RuthDavi} describe a decision analysis program for
Hodgkins disease which employs some novel methods for representing knowledge
for the generation and evaluation of decision trees.  Rather than directly
encoding the tree as a structure of nodes with associated probability and
utility expressions, the Hodgkins program uses predefined concepts of
tests and treatments to dynamically construct a decision tree at decision
evaluation time.  The structure of the tree is compiled into the interpreter,
in the sense that the decision at any point is a choice among the remaining
tests and the available treatments.  The effect of tests is to revise the
likelihood of the various patient conditions, perhaps exposing the patient to
some mortality risk.  Treatments are always terminal nodes of the decision
tree.  The expected utility of a treatment is calculated directly from the
input distribution of patient conditions.

Even though this simple decision structure is compiled into the program, the
system's use of test and treatment as high-level concepts provides a
flexibility not found in typical DA tools.  Characteristics of the patient
may be used to determine the list of available tests and treatments, or
these may be controlled directly by the user.  It is even possible for the
user to define \mf{his}{her} own tests and/or treatments, to modify existing
ones, and to specify new strategies or parts of strategies.  Since any of these
changes
results in widespread structural modifications of the decision tree, such a
task would be extremely cumbersome using traditional ``tree-defining'' DA
programs.  Algorithms designed specifically for optimizing test
selection sometimes avoid these difficulties.

Hollenberg's Decision Tree Builder ({\sc dtb})~\cite{Holl} generates decision
trees using a medical knowledge base of diseases and interventions (tests and
treatments).  Unlike the Hodgkins program, {\sc dtb} is intended to handle a
broad range of medical decision problems.  Consequently, its representations
are considerably more general, and its tree generation correspondingly more
flexible.  A disease may be parameterized by {\it attributes}, which in turn
may influence the applicability of various interventions as well as
probabilities and utilities in the model.  Tests and treatments may indicate
or modify the values of disease attributes.  A simple control structure
directs tree construction, employing a model of patient states for bookkeeping
purposes.

Hollenberg's work has also explored the use of {\it influence diagrams}, a
representation for decision structures developed by Howard and
Matheson~\cite{HowaMath}.  Influence diagrams offer several advantages over
decision
trees as an internal representation for a decision formulation in automatic
DA model-builders.  Like decision trees, influence diagrams are graphs where
the nodes represent decisions or chance events.  The links in influence
diagrams represent information and probabilistic dependencies among the nodes.
Because decision trees must be strictly hierarchical, they contain a
substantial duplication of structure that is unnecessary in influence
diagrams.  In fact, the number of nodes in a decision tree grows exponentially
with the size of
an influence diagram.  Furthermore, a decision tree representation cannot
take advantage of known independence relations, since a left-to-right
ordering is always imposed on events.  Though sometimes this ordering
reflects the temporal course of the situation, often the precedence choice is
quite arbitrary.

\subsubsection*{Consultation Systems}

The systems described thus far, including {\sc urp}, would be characterized
as primarily AI$\rightarrow$DA approaches.  Attempts to integrate AI and DA
in systems for direct consultation, on the other hand, contain elements of
both directions.

{\sc Rachel}, designed by Holtzman~\cite{Holt85}, is a program to aid in
decisions faced by infertile couples.  The program has a prespecified
formulation of the most general form of decision problem, represented as an
influence diagram.  For consultation, {\sc rachel} uses domain knowledge
encoded as production rules to determine
which parts of the internal model should be instantiated for particular
cases.  In establishing and parameterizing the model, the program is controlled
by a backward-chaining inference engine.  Parameters of the model are filled
in by user input or inference rules which may take the structure of the model
into account.

``Intelligent decision systems'' built along the lines of {\sc rachel}
incorporate domain knowledge to cover a well-defined class of decisions
(infertility in this case, end-stage renal disease in a precursor system also
developed by Holtzman~\cite{Holt83a}).  The domain knowledge is primarily
in the form of a general decision model, encoded as an influence diagram with
assessment functions for each node of the graph.  Constructing a model for a
particular decision is largely a matter of reducing the template model that is
built into the program.  Note the contrast between this and the tree generation
approach described above, where models are constructed by combining
primitive components in a controlled fashion.

Lehner and Donnell~\cite{Lehn} propose an architecture for a decision aiding
system based on a combination of DA models and rule-based expert systems.
Basically, their system consists of a prespecified utility model that is
parameterized by the application of inference rules.  Although this approach is
severely limited, it represents a simple kind of integration that can be
routinely implemented with current application technology.

It would be interesting to identify the domain-independent component of
modeling expertise and separate it from knowledge specific to the
decision-class supported by the consultation system.  Such a clean
division is not apparent in existing approaches.

\subsection{Knowledge-Based Approaches to Mathematical Modeling}
\label{k-b-model}

At a recent major AI conference (IJCAI 1983), four papers were presented
that described projects merging expert systems and mathematical
modeling.  Though differing widely in application area (oil-well data
interpretation~\cite{Bonn}, portfolio selection~\cite{Cohe}, flood
control~\cite{Cuen}, and macroeconomics~\cite{Roos}) as well as in the
mathematical modeling discipline employed, each takes a similar approach
toward integration: applying production rules to parameterize
model templates.  This sample is representative of the existing expert
systems that incorporate a mathematical modeling component.\footnote{I
am excluding from this discussion expert systems that perform tasks
(such as scheduling or inventory control) in areas where mathematical
models are traditionally employed.}

A rule-based system that fills in parameters often makes mathematical
models easier to use.  An extra layer is placed between the model and
the user, translating qualitative criteria to the numeric input required
by the model analysis package.  Or perhaps the translation is in the
other direction, from the model's numeric output to qualitative concepts
more intuitive to the user.  In either case, the rule base is useful for
connecting mathematical modeling to other sorts of automated reasoning
and certainly provides an improvement over unaided use of modeling
algorithms.  Some of the issues in developing these
interface layers are discussed by Weiss et al.\ \cite{Weis}.

Nevertheless, systems that treat the modeling algorithm as a black box
are unduly limited in the range of mathematical models they can construct and
the possible conclusions they can derive from the analysis.  This rigidity
typically restricts uses of the program's knowledge to modeling
in only one narrow application domain or even to a single problem instance.
For example, the portfolio selection program built by Cohen and Lieberman
({\sc folio})~\cite{Cohe} contains a template goal programming formulation
which it parameterizes and then solves by calling the black-box algorithm.
Since there is no domain-independent knowledge about goal programming,
it cannot adapt to different model {\it structures} that may be
appropriate for specific cases.  While sometimes it is possible to mimic a
structure by setting parameters of an overly general model appropriately, the
algorithm cannot take advantage of potential simplifications.  A more
serious problem is that the program is unable to deal with violations of the
assumptions underlying the model.  (The model in {\sc folio} is equivalent
to an additive-linear multiattribute utility function---a form that is
valid under only the strongest of independence conditions.)  A program with
a more general modeling expertise might be able to handle cases where
some of the default structural assumptions are inappropriate.

One important component of modeling expertise is to choose among alternative
analysis algorithms.  An expert system built specifically for this
purpose is {\sc sacon}~\cite{Benn}, a program that advises engineers in
the use of a structural analysis package.  The package is a large
collection of programs for specific modeling tasks.  {\sc Sacon} uses
knowledge about the package to determine which of its algorithms should be used
to analyze the structure that the engineer is interested in.  Knowledge about
algorithms includes items like error tolerance and the types of structural
phenomena that are considered (fatigue, for example).  This knowledge is
encoded in production rules.  {\sc Urp} makes use of the same types of
knowledge about dominance-testing algorithms but records the
information in a schematic data structure.  Similar
specifications for algorithms have been employed in knowledge-based
approaches to statistics (Blum's {\sc rx}~\cite{Blum82b} and a regression
system developed by Gale and Pregibon~\cite{GalePreg82}).

Other expert systems perform some kinds of quantitative reasoning.  Kunz's
AI/MM~\cite{Kunz} utilizes simple quantitative relations
between physiological parameters within a rule-based system.  The
mathematical modeling components of these systems are not nearly as
sophisticated
(that is, complex to apply and interpret) as those we are most concerned with
here, but the development of techniques for coupling categorical and
quantitative reasoning methods is potentially useful for our purposes.

\section{Limitations}\label{limit}

Deficiencies of {\sc urp} have been pointed out throughout this thesis report.
Many of these are due to time constraints; it was simply impossible within
the scope of this project to explore
every issue of the preference modeling problem that the approach described
here might address.  Of course, the implementation of even the
best-developed parts of the task leaves much to be
desired.  Other limitations are more fundamental in that it is difficult to
foresee their solution within the currently envisioned preference modeling
paradigm.  The sections below examine the weak points in more detail,
suggesting possibilities for improvement in some cases.

\subsection{Preference Modeling Issues}

While {\sc urp} is useful for a substantial part of the preference modeling
task, it does not quite cover the high-level view depicted in
figure~\ref{h-l-view} on page~\pageref{h-l-view}.  There is at least one
complete path from input assertions to a decision, though many of the paths
we would like to take using the system run into missing components along the
way.

Chapters \ref{assess-c} and~\ref{domain-p} discuss how the issues of
assessment and domain preference knowledge would be addressed within the
{\sc urp} framework.
The facilities described there have not been implemented, leaving
{\sc urp} with several gaps in its preference modeling ability.
Until an assessment facility is implemented, the proposition that we can
perform structural
sensitivity analysis and interpretation under descriptive theories of choice
must be regarded as an untested hypothesis, although I think there is a strong
case for believing that such capabilities can be achieved.  It is difficult to
argue forcefully that
{\sc urp} will be easy to use by expert systems or human analysts without
providing the
technical-vocabulary/domain-concept mapping supported by the domain preference
knowledge base.

Another large gap in {\sc urp} is its lack of support for asserting qualitative
behaviors of multiattribute utility functions and lack of any mathematical
reasoning about multiattribute forms.  In contrast to independence conditions,
multiattribute qualitative behaviors describe the nature of {\it dependencies}
among attributes in a utility function.  Like single-attribute behaviors, they
are useful for characterizing mathematical properties of the function as well
as indicating the validity of dominance-testing procedures.  While I do not
anticipate any
difficulties in defining these behaviors and performing logical inference based
on them, a significant extension of {\sc qm} would be required to represent and
reason about multivariate functions.  Nevertheless, an extended {\sc qm}
would undoubtedly be able to handle many of the kinds of inferences that
would be useful in multiattribute problems.  Qualitative behaviors of
these functions expressible as properties of partial derivatives (a
large class of the interesting behaviors) can be handled using {\sc
qm}'s single-variable representation.

There are as yet no general-purpose dominance-proving or constraint reasoning
procedures to address the problems of chapters \ref{s-do}
and~\ref{assess-c}.  While {\sc urp} should make use of its special-purpose
dominance knowledge as much as possible, it should be nevertheless be somewhat
competent at employing weaker methods in the more general cases.  Similarly,
it will be necessary to choose appropriate constraint manipulation methods to
implement the flexible assessment capability discussed above.

\subsection{The Implementation}

Even the parts of {\sc urp} that have been fully implemented could use quite
a bit of revising, tuning, extending, and fixing.  Because this was an
experimental project, pieces of the program were only developed to the point
that they could demonstrate that the desired capability was achievable.  The
major thrusts of improvements to {\sc urp}'s implementation should be toward
efficient use of existing mechanisms, an expanded knowledge base, and the
development of user interfaces.

The most pressing efficiency consideration is in the derivation of
multiattribute decompositions.  There is considerable opportunity for
optimization of the lower-level algorithms involved and for improvements to
the simple control structure currently in use.  Perhaps the most promising
avenue for efficiency gains is in the heuristic control mechanism suggested
in section~\ref{h-control}.

The knowledge base might be expanded in several directions: to include
more behaviors, more independence axioms and theorems, and more stochastic
dominance algorithms.  Of these, the last is probably most important; {\sc urp}
currently has a very limited repertoire of dominance-testing procedures.
Though investigations are preliminary, it appears that there is quite a
large body of useful results to draw from~\cite{Bawa}.

The existing program is a perfect example of ``user-hostile''
software.  Since the mechanisms were built without any precommitment to a
particular mode of usage, it is generally not possible to interact with
{\sc urp} without knowing something about the inner workings of the program.
This
situation will clearly have to be remedied before the system can be useful
as a utility analysis tool.

\subsection{The Approach}

Most troublesome are the limitations of preference modeling with {\sc urp}
that do not appear to be just a matter of gaps in the implementation.  This
section identifies a few of the more fundamental difficulties which I do not
have any particularly good ideas about resolving.

\subsubsection*{Driving Model Construction}

The first problem concerns {\sc urp}'s failure to cover the
full preference modeling task as diagrammed in figure~\ref{h-l-view}.  Recall
that in the figure there is a control link tying the results of model analysis
to goals of model construction.  Unfortunately, {\sc urp} does not actually
close that loop, and it is not obvious to me how to do so.  While there are
some fairly simple tactics which might be applied when analysis fails to derive
a decision, such as establishing preconditions for a more powerful dominance
routine or finding an incrementally simpler utility expression or
decomposition,
these do not take advantage of information derived from the failed analysis.

\subsubsection*{Complexity}

Probably the most apparent problem of the entire approach is that {\sc urp}
is certainly not a ``simple and elegant'' solution to the preference modeling
problem.  It is comprised of many complex mechanisms and relies
on some fairly sizable reasoning tools ({\sc rup} and {\sc qm}, which in turn
uses {\sc macsyma}) to do some of its work.  Extensions mentioned above would
require even more complexity and additional high-powered tools.

Part of this complexity is a conscious response to the overly simplified view
of preferences typically taken by decision-making programs.  One of the major
points of this thesis project was to demonstrate that it is possible and
desirable to
exploit the large body of theory concerning formal preference models.  Given
the present structure of utility theory, this
requires a lot of separate, complicated mechanisms.  It may be that some of
these mechanisms will turn out to be more useful than others---the fact that
they
are separate also implies that there should be some benefit to each mechanism
in isolation.  Thus, I expect that further work will concentrate on identifying
the pieces that are most important in particular preference modeling tasks.
These mechanisms could then be tuned to provide the best performance
for those tasks.

\subsubsection*{Formulation}

It is an unfortunate fact that {\sc urp}'s {\it model construction} starts with
considerably more than scratch.  A large part of the expertise of a utility
analyst is in choosing the right attributes to model.  Since
{\sc urp} abdicates this responsibility, any success it has might be attributed
to having fed it the right formulation to begin with.

This is a difficult problem, and I am not optimistic that it can be easily
solved.  Choosing attributes requires a great amount of domain and real-world
knowledge of the sort that cannot be contained in a general-purpose preference
modeling program.  Some of this knowledge may be supplied by a domain
preference
knowledge base of the sort outlined in chapter~\ref{domain-p}, though
the actual methods for using it (particularly for attribute
selection) have not been worked out.  There
are, in addition, some domain-independent principles which
may help to determine the applicability of a set of attributes for a given
problem \cite{Keen81a}~\cite{Keen81b}.  Defining measurement properties
(discussed in section~\ref{measure-discussion}) may help.  Formalizing these
principles is a challenging though worthwhile
exercise, crucial to the development of a truly useful utility analysis system.

\section{Future Work: Planning with Preferences}

Much has been said here about the potential for preference modeling in decision
making programs without any serious discussion of how it might be
incorporated in actual program designs.  {\sc Urp} is precisely what its
acronym suggests:  a collection of programs which perform various sorts
of reasoning about utility.  Embedding this reasoning in a larger
decision making system architecture would require a considerable
engineering effort.  And undoubtedly the issues involved in an
integration of preference modeling in AI programs would vary greatly
across different problem-solving paradigms.

To test the usefulness of some of the ideas developed in this project, I
will attempt to incorporate elements of preference reasoning in a
domain-independent planner and apply the program to problems in patient
management.  Planning is a particularly good framework for studying the
implications of preferences, since constructing a plan requires many
choices among alternative actions.  It is no coincidence that planning
spaces bear a close resemblance to decision trees.

Charniak and McDermott~\cite{CharMcDe} (page 524) point out that little AI
planning work has incorporated a decision-theoretic basis for
choice.\footnote{Feldman and Sproull~\cite{FeldSpro} argue for the use
of decision theory in robot planning.  Though their numerical approach
to utility shares many of the shortcomings of heuristic evaluation
functions, using outcome desirability to plan actions is shown to be
valuable for revealing tradeoffs, allocating planning effort, and
directing information acquisition.  As far as I know, their ideas have
not been incorporated in an actual planning system.}
Indeed, the problem of choice has received minimal attention of any kind.
State-of-the-art planners have no means to reason about partial or uncertain
satisfaction of goals, much less to explicitly consider tradeoffs in choosing
planning steps.  Developing such a capability would entail an expanded
language for describing objectives, a means for representing
uncertainty, and mechanisms for expressing and reasoning about the desirability
of outcomes.

From the point of view of the proposed planner, {\sc urp} is a vehicle for
exploring this last issue.  Experiments with {\sc urp} should help to identify
the most useful types of assertions about preferences and how to
reason about them.  The goal will be to select a subset of the
conceivable {\sc urp} assertions to include as primitives in the planning
system.  My expectation is that most of the qualitative behaviors and
independence conditions already defined in {\sc urp} will turn out to be
useful, in addition to qualitative multiattribute properties not yet
implemented.

Work in planning will also highlight an issue that has not been
explored much with {\sc urp}: how these preference assertions may be
used in {\it formulation}.  Knowledge about the decision maker's
objective structure will often be useful for determining whether a
tradeoff situation exists and which are the pivotal attributes of the
situation that must be included in the model.

Any more detailed discussion of how preference modeling in the {\sc urp}
framework would be accomplished in a planning environment would be purely
speculative at this stage.  In any case, the
ability for formulation (or even simply recognition) of tradeoff situations
alone would be a substantial advance in AI planning technology.

\section{Contributions}\label{con}

\subsection{Summary}

In my opinion, the important contribution of this work is in its overall
approach toward preference modeling, rather than in any of the particular
capabilities that have been described.  Nevertheless, in the course of
attempting to
demonstrate the potential advantages of a qualitative view of preferences and
a knowledge-based representation of utility theory, several more specific
goals were accomplished.  These achievements have all been chronicled in
the thesis body; the remainder of the section is a brief outline of what I
believe to be the most important contributions.

\subsubsection*{Qualitative Behaviors}

\begin{itemize}
\item Explicit maintenance of the qualitative premises underlying
single-attribute utility functions
\item Integration of logical and mathematical relations among behavior
assertions and function objects
\item Adaptation of {\sc qm} to handle some types of incompletely specified
functions
\end{itemize}

\subsubsection*{Stochastic Dominance}

\begin{itemize}
\item Knowledge-based approach tying dominance tests to qualitative
preconditions for their applicability
\item Framework for incorporating algorithms in the overall system
\end{itemize}

\subsubsection*{Multiattribute Decomposition}

\begin{itemize}
\item Language for describing independence axioms and decomposition theorems,
with interpreter/theorem prover
\item Encoding a substantial body of multiattribute utility theory in this
language, covering the major results of the field
\item Generation of hierarchical decompositions without prestructuring by the
user
\end{itemize}

\subsubsection*{Assessment}

\begin{itemize}
\item Framework for model-independent use of hypothetical preference choices
\item Potential for interpretation under descriptive theories of preference
choice
\end{itemize}

\subsubsection*{Domain Preferences}

\begin{itemize}
\item Notion of a technical vocabulary for domain-independent modeling systems;
nature of the mapping to domain concepts
\item Using properties of measurement scale to capture some ``common-sense''
features of a quantity
\item Construction of a fragmentary health preference knowledge base
\end{itemize}

\subsection{Outlook on Preference Modeling}

Of greater interest than the merits of the individual contributions themselves
is the potential for integrating them into a coherent and comprehensive
preference modeling system.  While there is quite a large disparity
between {\sc urp}'s capabilities and this ultimate objective, there are
several reasons to believe that the goal is a realistic one.  From the
vantage of the existing {\sc urp} implementation, there are some
obvious extensions which could be undertaken to cover a larger share of
the overall task.

Only a few of the limitations noted in section~\ref{limit} seem to be
fundamental.  Most would require substantial engineering
effort, but should be possible with off-the-shelf AI technology.  The
overall design is quite complex, but simplifications and generalizations are
likely to become apparent as more of utility theory is formalized.  Indeed,
experience in implementing {\sc urp} indicates that there may be
considerable ``hidden'' generality that can be exploited by an automated
reasoner.  Without a program that can flexibly apply the theory,
orthogonality of utility concepts does not get much attention in the
literature.  For example, two generalities of utility theory that do not
often get applied in practical model structuring (though they are exploited in
proving decomposition theorems) are the ability to treat sets of
attributes as single vector attributes and the extension of independence
relations to analogous relations with fewer conditioning attributes
({\sc urp} theorem~23).  Applying these together with knowledge of
two-attribute functional forms, {\sc urp} automatically generates
hierarchical decompositions.  This opportunity ``falls out'' of the
structure of the theory; it is not practically important without an
automatic model constructor.

We should also expect that the comprehensive modeling system will become
more feasible with the advancement of related AI technologies.  Work in
qualitative mathematics should result in more efficient and powerful
reasoners.  Continuing research in integrated AI and DA systems (both
AI$\rightarrow$DA and DA$\rightarrow$AI) will provide useful mechanisms
as well as a context for applying preference modelers.  And ideas from
other knowledge-based systems for mathematical modeling should be
transferable to the preference modeling task.

A distinguishing architectural feature of programs that employ preference
modeling is the separation of reasoning about
consequences of actions from reasoning about desirability of outcomes.
In itself this is a strong constraint on reasoning style;
it implies that decision making programs can never associate beliefs
directly with actions.  For example, a program for medical therapy
cannot implement policies of prescribing drugs based only on observations.
Rather, such programs must reason about the implications of these observations
combined with the consequences of possible actions (drug
recommendations) in terms of the patient state or other relevant attributes.
The resulting outcomes are compared with respect to preference to choose
the best recommendation.  In practice, we might wish to circumvent most
of this reasoning for ``obvious'' action indicators.  A {\it policy\/} may
be thought of as a conscious decision not to explicitly consider
consequences of actions and their desirability in certain common situations.
This notion will have to be developed further before preference
modeling can be practical for routine decision making.

In the introductory chapter I noted that research on {\sc urp} could be
viewed as a step toward the development of a ``calculus'' for preference
assertions.  To perform preference modeling, programs will need a
language to express their objective structures; {\sc urp}'s technical
vocabulary is an early design of that language.  The ability to define
the language also affords control over the scope of the preference reasoning
task.  Applications that refer to a constrained set of outcomes or
possible preference structures can get by with only a subset of the
language and therefore a smaller preference reasoner.  This is another
way to combat the complexity of the most general preference modeling problem.
Thus, some future work may be applied to the identification of simpler
preference reasoning tasks sufficient for specific applications.

Once proven preference reasoning capabilities are developed, it would not
be surprising to see preferences models used for purposes other than
decision making.  The value of explicit preferences for explanation and
justification of program behavior has already been discussed.  In
addition, preference representations may prove a useful basis for heuristics
for directing search or information acquisition, or for some kinds of
cognitive modeling.  Programs that model users' beliefs (for tutoring or
interactive consultation, for example) might also benefit from models of
users' preferences.

\renewcommand{\baselinestretch}{1.0}
\large
\normalsize

\bibliographystyle{custom}
\bibliography{bibcite:bibcite;bib.bib}

\appendix

\chapter[Qualitative Behaviors of Utility Functions]
{Qualitative Behaviors of Unidimensional Utility Functions}
\label{q-appendix}

Reasoning about qualitative behaviors of single-attribute utility functions
was discussed in chapter~\ref{q-behavior-r}.  This appendix describes the
qualitative behaviors currently implemented in {\sc urp}.

\section{Behavior Descriptions}

\begin{description}
\item [{\bf monotonic}:] $u$'s derivative is either nonpositive or nonnegative
over the entire domain
\item [{\bf strict-monotonic}:] $u$'s derivative is either positive or
negative
\item [{\bf monotonic-increasing}:] $u$'s derivative is strictly positive
\item [{\bf monotonic-nondecreasing}:] $u$'s derivative is nonnegative
\item [{\bf monotonic-decreasing}:] $u$'s derivative is strictly negative
\item [{\bf monotonic-nonincreasing}:] $u$'s derivative is nonpositive
\item [{\bf risk-averse}:] $u$ is concave (second derivative is negative)
\item [{\bf risk-neutral}:] $u$ is linear (zero second derivative); the
functional form {\tt linear} applies
\item [{\bf risk-prone}:] $u$ is convex (postive second derivative)
\item [{\bf constant-risk-averse}:] the risk aversion function ($r$ or $q$
from \ref{risk-up} or~\ref{risk-down}) is constant; the functional form
{\tt exponential} applies
\item [{\bf constant-proportional-risk-posture}:] the proportional risk
function $\rho(x)=xr(x)$ (or $xq(x)$ for decreasing $u$\/) is constant; one of
the functional forms {\tt power} or {\tt log} applies (intensity of risk
aversion distinguishes the cases)
\item [{\bf increasing-risk-posture}:] the risk function is
{\bf monotonic-increasing}
\item [{\bf decreasing-risk-posture}:] the risk function is
{\bf monotonic-decreasing}
\end{description}

The mathematical relations between the behaviors and $u$ is encoded in
the {\it pos}, {\it nec}, and {\it enf}\/ procedures described in
section~\ref{encoding-b}.  Logical relations among the behaviors are
encoded in {\sc rup}.  The functional forms mentioned above appear in
table~\ref{u-form-t}.

\section{Terminological Definitions}

\begin{tabular}{lcl}
\\ [.5cm]
{\bf constant-risk-averse} & $\;\equiv\;\;$ & {\bf constant-risk-posture} \\
& & $\wedge$ {\bf risk-averse} \\[.2cm]
{\bf constant-risk-prone} & $\;\equiv\;\;$ & {\bf constant-risk-posture} \\
& & $\wedge$ {\bf risk-prone} \\[.2cm]
{\bf constant-proportional-risk-averse} & $\;\equiv\;\;$ & {\bf constant-proportional-risk-posture} \\
& & $\wedge$ {\bf risk-averse} \\[.2cm]
{\bf constant-proportional-risk-prone} & $\;\equiv\;\;$ & {\bf constant-proportional-risk-posture} \\
& & $\wedge$ {\bf risk-prone} \\[.2cm]
{\bf increasing-risk-averse} & $\;\equiv\;\;$ & {\bf risk-averse} \\
& & $\wedge$ {\bf increasing-risk-posture} \\[.2cm]
{\bf increasing-risk-prone} & $\;\equiv\;\;$ & {\bf risk-prone} \\
& & $\wedge$ {\bf increasing-risk-posture} \\[.2cm]
{\bf decreasing-risk-averse} & $\;\equiv\;\;$ & {\bf risk-averse} \\
& & $\wedge$ {\bf decreasing-risk-posture} \\[.2cm]
{\bf decreasing-risk-prone} & $\;\equiv\;\;$ & {\bf risk-prone} \\
& & $\wedge$ {\bf decreasing-risk-posture} \\[.2cm]
\end{tabular}

\chapter{Axiom Schemata}\label{schema-ax}

Here is a complete alphabetized listing of the independence axioms currently
known to
{\sc urp}.  Some of these are not yet used in any significant reasoning
(they do not appear in any theorems).  The representation is described in
section~\ref{axiom-rep}, and the meanings of the individual axioms
are discussed in chapter~\ref{knowledge-base}.  The ``{\tt :definition}'' slots
are not filled in carefully (or at all) since there is as yet no explanation
facility.  Definitions from the literature
can be found in the document appearing in the ``{\tt :source}'' slot; pointers
are given in the references section.

\begin{verbatim}

(defaxiom 'additive-independence
  :source "Keeney & Raiffa p. 295"
  :special-case-of '(mutual-utility-independence)
  :arg-count 1
  :arg-relns '((nonempty 1)))

(defaxiom 'additive-value-function
  :definition "can use additive form for value function"
  :source "Farquhar 77 p. 64"
  :arg-count 1
  :arg-relns '((nonempty 1)))

(defaxiom 'bilateral-form
  :definition "functional form"
  :source "Farquhar 77 p. 71"
  :arg-count 1
  :arg-relns '((nonempty 1)))

(defaxiom 'bilateral-independence
  :source "Farquhar 77 p. 71"
  :special-case-of '(generalized-bilateral-independence
                     joint-interpolation-independence)
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2)))

\end{verbatim}
\newpage
\begin{verbatim}

(defaxiom 'conditional-preferential-independence
  :definition "PI given Y-(not ij)'"
  :source "Keeney and Raiffa p. 334"
  :arg-count 3
  :arg-relns '((exclusive-exhaustive-nonempty-subsets 1 2 3)))

(defaxiom 'conditional-utility-independence
  :definition "UI given Y-(not ij)'"
  :source "Keeney and Raiffa p. 334"
  :arg-count 3
  :arg-relns '((exclusive-exhaustive-nonempty-subsets 1 2 3)))

(defaxiom 'conditional-value-independence
  :definition "VI given Y-(not ij)'"
  :source "Keeney and Raiffa p. 336"
  :arg-count 3
  :arg-relns '((exclusive-exhaustive-nonempty-subsets 1 2 3)))

(defaxiom 'generalized-bilateral-independence
  :definition "BI with reversals allowed"
  :source "Farquhar 77 p. 71"
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2)))

(defaxiom 'generalized-preferential-independence
  :source "Fishburn & Keeney 74 p. 299"
  :special-case-of '(indifference-independence)
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2)))

(defaxiom 'generalized-utility-independence
  :source "Farquhar 77 p. 69"
  :special-case-of '(generalized-preferential-independence)
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2)))

\end{verbatim}
\newpage
\begin{verbatim}

(defaxiom 'indifference-independence
  :source "Fishburn & Keeney 74 p. 299"
  :restrictions "s-c-o GPI requires Axiom 1 from source"
  :special-case-of '(weak-indifference-independence
                      generalized-preferential-independence)
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2)))

(defaxiom 'interpolation-independence
  :definition "see Bell 79b p. 1056"
  :source "Bell 78, 79a, 79b"
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2)))

(defaxiom 'multilinear-form
  :definition "functional form"
  :source "Keeney & Raiffa p. 293"
  :arg-count 1
  :arg-relns '((nonempty 1)))

(defaxiom 'multilinear-generalization-form
  :definition "functional form"
  :source "Bell 79a p. 748"
  :arg-count 1
  :arg-relns '((nonempty 1)))

(defaxiom 'multiplicative-form
  :definition "functional form"
  :source "Keeney & Raiffa p. 289"
  :special-case-of '(multilinear-form)
  :arg-count 1
  :arg-relns '((nonempty 1)))

(defaxiom 'mutual-preferential-independence
  :definition "every subset PI its complement"
  :source "Keeney and Raiffa p. 111"
  :arg-count 1
  :arg-relns '((nonempty 1)))

\end{verbatim}
\newpage
\begin{verbatim}

(defaxiom 'mutual-utility-independence
  :source "Keeney & Raiffa p. 289"
  :arg-count 1
  :arg-relns '((nonempty 1)))

(defaxiom 'parametric-independence
  :source "Kirkwood"
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2)))

(defaxiom 'preferential-independence
  :source "Keeney & Raiffa p. 109"
  :special-case-of '(generalized-preferential-independence)
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2)))

(defaxiom 'utility-independence
  :source "Keeney & Raiffa p. 284"
  :special-case-of '(preferential-independence
                      generalized-utility-independence
                      bilateral-independence)
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2)))

(defaxiom 'value-independence
  :source "Fishburn & Keeney 74 p. 297"
  :restrictions "special-case of UI requires (5) from source"
  :special-case-of '(utility-independence)
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2))
  :op-prop '(symmetric))

(defaxiom 'weak-indifference-independence
  :source "Fishburn & Keeney 74 p. 300"
  :arg-count 2
  :arg-relns '((exclusive-nonempty-subsets 1 2)))

\end{verbatim}

\chapter{Multiattribute Theorems}\label{theorem-ax}

This appendix lists all of {\sc urp}'s decomposition theorems in numerical
order.  The theorem representation language is described in
section~\ref{theorem-rep}.  The numbering of theorems is arbitrary;
it only
refers to the order in which they were added to the {\sc urp} knowledge base.
The sources can be found in the reference list starting on
page~\pageref{references}.

\begin{small}
\begin{verbatim}

(deftheorem 'theorem001
  :source "Keeney & Raiffa p. 293"
  :premise '(for-all i in X
                     ((utility-independence (set-of i)
                                            (difference X (set-of i)))))
  :consequent '((multilinear-form X)))


(deftheorem 'theorem002
  :source "Keeney & Raiffa p. 292 #5"
  :premise '(for-some i in X
                (for-all j in (difference X (set-of i))
                    ((utility-independence (set-of i)
                                           (difference X (set-of i)))
                     (preferential-independence
                         (set-of j i) (difference X (set-of j i))))))
  :consequent '((mutual-utility-independence X)))


(deftheorem 'theorem003
  :source "Keeney & Raiffa p. 289"
  :premise '((mutual-utility-independence X))
  :consequent '((multiplicative-form X)))


(deftheorem 'theorem005
  :source "Keeney & Raiffa p. 292 #2"
  :premise '(for-all i in X
                     ((utility-independence (difference X (set-of i))
                                            (set-of i))))
  :consequent '((mutual-utility-independence X)))
\end{verbatim}
\newpage
\begin{verbatim}
(deftheorem 'theorem009
  :source "Keeney & Raiffa p. 316"
  :premise '(for-some-set Y1 in (subset X)
                (for-some-set Y2 in (overlapping-subset Y1 X)
                    ((utility-independence Y1 (difference X Y1))
                     (utility-independence Y2 (difference X Y2)))))
  :consequent '((utility-independence (union Y1 Y2)
                                      (difference X (union Y1 Y2)))
                (utility-independence (intersection Y1 Y2)
                                      (difference X (intersection Y1 Y2)))
                (utility-independence (sym-difference Y1 Y2)
                                      (difference X
                                                  (sym-difference Y1 Y2)))
                (utility-independence (difference Y1 Y2)
                                      (difference X (difference Y1 Y2)))
                (utility-independence (difference Y2 Y1)
                                      (difference X (difference Y2 Y1)))))


(deftheorem 'theorem010
  :source "Keeney & Raiffa p. 112"
  :premise '(for-some-set Y in (subset X)
                (for-some-set Z in (overlapping-subset Y X)
                    ((preferential-independence Y (difference X Y))
                     (preferential-independence Z (difference X Z)))))
  :consequent
  '((preferential-independence (union Y Z) (difference X (union Y Z)))
    (preferential-independence (intersection Y Z)
                               (difference X (intersection Y Z)))
    (preferential-independence (sym-difference Y Z)
                               (difference X (sym-difference Y Z)))
    (preferential-independence (difference Y Z)
                               (difference X (difference Y Z)))
    (preferential-independence (difference Z Y)
                               (difference X (difference Z Y)))))


(deftheorem 'theorem012
  :source "Keeney & Raiffa p. 289"
  :premise '(for-some-set Z in (subset X)
                          ((mutual-utility-independence X)))
  :consequent '((utility-independence Z (difference X Z))))
\end{verbatim}
\newpage
\begin{verbatim}
(deftheorem 'theorem013
  :source "Farquhar 77 Thm. 1"
  :premise '(for-some k in X
                (for-all j in (difference X (set-of k))
                         ((preferential-independence
                            (set-of j k) (difference X (set-of j K))))))
  :consequent '((additive-value-function X)))


(deftheorem 'theorem014
  :source "Farquhar 77 Thm. 5"
  :premise '(for-all i in X
                ((generalized-bilateral-independence
                              (set-of i) (difference X (set-of i)))))
  :consequent '((bilateral-form X)))


(deftheorem 'theorem016
  :source "Bell 79a p. 748"
  :premise '(for-all i in X
                ((joint interpolation-independence
                             (set-of i) (difference X (set-of i)))))
  :consequent '((multilinear-generalization-form X)))


(deftheorem 'theorem017
  :source "Fishburn and Keeney 74 Thm 1."
  :restrictions "Axiom 1, Y1 essential"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        ((weak-indifference-independence (union Y1 Y2)
                                                         Y3)
                         (value-independence Y1 (union Y2 Y3))))))
  :consequent '((value-independence (union Y1 Y2) Y3)
                (value-independence (union Y1 Y3) Y2)))
\end{verbatim}
\newpage
\begin{verbatim}
(deftheorem 'theorem018
  :source "Fishburn and Keeney 74 Thm 2."
  :restrictions "Axiom 1, Y1 essential"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        ((weak-indifference-independence (union Y1 Y2)
                                                         Y3)
                         (utility-independence Y1 (union Y2 Y3))))))
  :consequent '((utility-independence (union Y1 Y2) Y3)))


(deftheorem 'theorem019
  :source "Fishburn and Keeney 74 Thm. 3"
  :restrictions "Axiom 1, Y1 + Y2 essential, see also page 303"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        ((weak-indifference-independence (union Y1 Y2)
                                                         Y3)
                         (utility-independence (union Y1 Y3) Y2)))))
  :consequent '((utility-independence Y3 (union Y1 Y2))
                (generalized-utility-independence (union Y1 Y2) Y3)))


(deftheorem 'theorem020
  :source "Fishburn and Keeney 74 Thm. 3 corollary (at bottom)"
  :restrictions "Axiom 1, Y1 + Y2 essential, see also page 303"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        ((preferential-independence (union Y1 Y2) Y3)
                         (utility-independence (union Y1 Y3) Y2)))))
  :consequent '((utility-independence (union Y1 Y2) Y3)))

\end{verbatim}
\newpage
\begin{verbatim}
(deftheorem 'theorem021
  :source "Fishburn and Keeney 74 corollary p. 308"
  :restrictions "Axiom 1, Y1 essential"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        ((generalized-utility-independence Y1
                                                           (union Y2 Y3))
                         (preferential-independence (union Y1 Y2) Y3)
                         (preferential-independence (union Y1 Y3) Y2)))))
  :consequent '((utility-independence Y1 (union Y2 Y3))
                (utility-independence (union Y1 Y2) Y3)
                (utility-independence (union Y1 Y3) Y2)))


(deftheorem 'theorem023
  :source "Keeney and Raiffa Thm. 6.15"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        ((utility-independence Y1 (union Y2 Y3))))))
  :consequent '((utility-independence Y1 Y2)))


(deftheorem 'theorem024
  :source "Keeney and Raiffa Thm. 6.17"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        ((utility-independence Y1 Y2)
                         (conditional-utility-independence Y1 Y3 Y2)))))
  :consequent '((utility-independence Y1 (union Y2 Y3))))
\end{verbatim}
\newpage
\begin{verbatim}
(deftheorem 'theorem025
  :source "Keeney and Raiffa Thm. 6.18"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        ((utility-independence (union Y1 Y2) Y3)
                         (conditional-preferential-independence
                                                      Y1 Y2 Y3)))))
  :consequent '((preferential-independence Y1 (union Y2 Y3))))


(deftheorem 'theorem026
  :source "Keeney and Raiffa Thm. 6.19"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        ((utility-independence (union Y1 Y2) Y3)
                         (conditional-utility-independence Y1 Y2 Y3)))))
  :consequent '((utility-independence Y1 (union Y2 Y3))))


(deftheorem 'theorem027
  :source "special case of conditional UI"
  :premise '(for-some-set Y1 in X
                (for-some-set Y2 in (difference X Y1)
                    ((utility-independence Y1 Y2))))
  :consequent '((conditional-utility-independence
                            Y1 Y2 (difference X (union Y1 Y2)))))


(deftheorem 'theorem028
  :source "special case of conditional PI"
  :premise '(for-some-set Y1 in X
                (for-some-set Y2 in (difference X Y1)
                    ((preferential-independence Y1 Y2))))
  :consequent '((conditional-preferential-independence
                            Y1 Y2 (difference X (union Y1 Y2)))))
\end{verbatim}
\newpage
\begin{verbatim}
(deftheorem 'theorem029
  :source "Bell 77 Lemma 2"
  :restriction "I dropped the X4 but I think this still works"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3 in (subset (complement Y2))
                        ((joint utility-independence Y1 (union Y2 Y3))))))
  :consequent '((joint utility-independence Y1 Y2)
                (joint utility-independence Y1 Y3)))


(deftheorem 'theorem030
  :source "Bell 77 Lemma 2 extension"
  :restriction "I dropped the X4 but I think this still works"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3 in (subset (complement Y2))
                        ((utility-independence Y1 Y2)
                         (utility-independence Y1 Y3)))))
  :consequent '((utility-independence Y1 (union Y2 Y3))))


(deftheorem 'theorem031
  :source "Fishburn & Keeney 75 Lemma 1 p. 931"
  :restriction "Y1 essential"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        (for-some-set Y4
                            ((generalized-utility-independence
                                      (union Y1 Y2) (union Y3 Y4))
                             (generalized-utility-independence
                                      (union Y1 Y3) (union Y2 Y4)))))))
  :consequent '((generalized-utility-independence
                         (union Y1 (union Y2 Y3)) Y4)))
\end{verbatim}
\newpage
\begin{verbatim}
(deftheorem 'theorem032
  :source "Fishburn & Keeney 75 Thm 1 p. 934"
  :restriction "Yi essential"
  :premise '(for-some i in X
                (for-all j in (difference X (set-of i))
                    ((generalized-utility-independence
                             (set-of i j) (difference X (set-of i j))))))
  :consequent '((multiplicative-form X)))


(deftheorem 'theorem033
  :source "Keeney 74 Lemma 2 p. 24"
  :premise '(for-some-set Y1
                (for-some-set Y2
                    (for-some-set Y3
                        (for-some-set Y4
                            ((utility-independence (union Y1 Y2)
                                                   (union Y3 Y4))
                             (utility-independence (union Y1 Y3)
                                                   (union Y2 Y4)))))))
  :consequent '((utility-independence (union Y1 (union Y2 Y3)) Y4)))

\end{verbatim}
\end{small}

\chapter{Set Membership Constraints}\label{constraint-appendix}

The following is a complete list of set membership constraints appearing
in the current set of {\sc urp} multiattribute utility theorems.  Each is
defined in terms of the primitive constraints {\bf union} and {\bf complement},
described in section~\ref{m-constraint}.

The expressions defined below are shown as they appear in {\sc urp} theorems.
The set denoted by the expression is called $Z$ in the definition.  When
notation is given it is for use in subsequent constraint definitions.  The
predicate {\it nonempty}
on a set is used to indicate that {\bf min-size} for that set is restricted
to be greater than or equal to one.\footnote{Strictly speaking, {\it nonempty}
is not a constraint since it does not appear as an object in the network.  It
only influences the initial value for {\bf min-size} during network
construction.}

{\flushleft ({\bf intersection} {\tt Y1} {\tt Y2})}
\begin{quote}
notation:\hspace{3.5em} $Z = Y_1\cap Y_2$

definition:\hspace{3em} $Z = \overline{\overline{Y_1}\cup \overline{Y_2}}$
\end{quote}

{\flushleft ({\bf difference} {\tt X} {\tt Y})}
\begin{quote}
notation:\hspace{3.5em} $Z = X - Y$

definition:\hspace{3em} $Z = \overline{\overline{X}\cup Y}$
\end{quote}

{\flushleft ({\bf sym-difference} {\tt X} {\tt Y})}
\begin{quote}
definition:\hspace{3em} $Z = (X - Y) \cup (Y - X)$
\end{quote}

{\flushleft ({\bf subset} {\tt X})}
\begin{quote}
notation:\hspace{3.5em} $Z \subseteq X$

definition:\hspace{3em} $X = X \cup Z$
\end{quote}

{\flushleft ({\bf nonempty-subset} {\tt X})}
\begin{quote}
definition:\hspace{3em} $Z \subseteq X$;\hspace{2em} $nonempty(Z)$
\end{quote}	

{\flushleft ({\bf proper-subset} {\tt X})}
\begin{quote}
definition:\hspace{3em} $Z \subseteq X$;\hspace{2em} $nonempty(X-Z)$
\end{quote}	

{\flushleft ({\bf overlapping-subset} {\tt Y} {\tt X})}
\begin{quote}
definition:\hspace{3em} $Z \subseteq X$;\hspace{2em} $Y \subseteq X$;\hspace{2em} $nonempty(Z-Y)$;

\hspace{7em} $nonempty(Y-Z)$;\hspace{2em} $nonempty(Y\cap Z)$;

\hspace{7em} $nonempty(X-(Y\cup Z))$
\end{quote}

The following two constraints are used exclusively for type-checking the
arguments to {\sc urp} axioms.  They appear in the {\bf arg-relns} slot of
the axiom schemata.

{\flushleft ({\bf exclusive-nonempty-subsets} {\tt Y1} {\tt Y2})}
\begin{quote}
definition:\hspace{3em} $Y_1 \subseteq \overline{Y_2}$;\hspace{2em} $nonempty(Y_1)$;\hspace{2em} $nonempty(Y_2)$
\end{quote}

{\flushleft ({\bf exclusive-exhaustive-nonempty-subsets} {\tt Y1} {\tt Y2} {\tt Y3})}
\begin{quote}
definition:\hspace{3em} $Y_1 \subseteq \overline{Y_2}$;\hspace{2em} $Y_3 = \overline{Y_1\cup Y_2}$;\hspace{2em} $nonempty(Y_1)$;

\hspace{7em} $nonempty(Y_2)$; \hspace{2em} $nonempty(Y_3)$
\end{quote}

{\sc Urp} can also handle constraints that relate set nodes to element
nodes.  The only one used explicitly in theorems is {\bf set-of} (although
the definition below uses two arguments, the constraint may be used for
an arbitrary number of element variables):

{\flushleft ({\bf set-of} {\tt i} {\tt j})}
\begin{quote}
definition:\hspace{3em} $Z = \left\{i,j\right\}$
\end{quote}

\chapter{Multiattribute Functional Forms}\label{m-form-ax}

This appendix lists the multiattribute functional forms that may be part of
decompositions generated by {\sc urp}.  Each form (named for the independence
axiom it is associated with) is written in a mathematical notation and a
plausible {\sc urp} specification.  The specification is for
illustration only; no facilities for mathematical reasoning about
multiattribute functions has been implemented.

\section{Two-attribute Forms}\label{2-forms}

Several of {\sc urp}'s binary independence relations are associated directly
with
two-attribute decompositions.  This section lists those conditions, along with
a specification for the functional form they imply.  This listing is almost
identical to table~1 from Bell~\cite{Bell79b} (except for the {\sc urp}
specification, of course).  Conditialization is omitted for unidimensional
functions if the conditioning level of the fixed attribute is not significant.

\begin{itemize}
\item value-independence
\[au(x) + (1-a)u(y)\]

\begin{verbatim}
    ((+ (* a (u x))
        (* (- 1 a) (u y)))
     (where a (evaluation u (best x) (worst y))))
\end{verbatim}

\item joint utility-independence
\[au(x) + bu(y) + (1-a-b)u(x)u(y)\]

\begin{verbatim}
    ((+ (* a (u x))
        (* b (u y))
        (* (- 1 a b) (u x) (u y)))
     (where a (evaluation u (best x) (worst y))
            b (evaluation u (worst x) (best y))))
\end{verbatim}

\item utility-independence
\[au(x) + bu(x_*,y) - bu(x)u(x_*,y) + (1-a)u(x)u(x^*,y)\]

\begin{verbatim}
    ((+ (* a (u x))
        (* b (u y (worst x)))
        (* (- b) (u x) (u y (worst x)))
        (* (- 1 a) (u x) (u y (best x))))
     (where a (evaluation u (best x) (worst y))
            b (evaluation u (worst x) (best y))))
\end{verbatim}

\item bilateral-independence
\item [] $au(x,y_*) + bu(y,x_*)$
\item [] \hspace{3em} \( + \frac{1}{1-a-b} \cdot
	\left[ (1-b)u(x,y^*)-au(x,y_*)\right] \cdot
	\left[ (1-a)u(x,y^*)-bu(y,x_*)\right]	\)

\begin{verbatim}
    ((+ (* a (u x))
        (* b (u y (worst x)))
        (* (/ 1 (- 1 a b))
           (- (* (- 1 b) (u x (best y)))
              (* a (u x (worst y))))
           (- (* (- 1 a) (u y (best x)))
              (* b (u y (worst x))))))
     (where a (evaluation u (best x) (worst y))
            b (evaluation u (worst x) (best y))))
\end{verbatim}

\item joint interpolation-independence
\item [] \( au(x,y_*) + bu(y,x_*) - ku(x,y_*)u(y,x_*) \)
\item [] \hspace{3em} \( + (k-a)u(x,y_*)u(y,x^*) + (k-b)u(x,y^*)u(y,x_*) + (1-k)u(x,y^*)u(y,x^*)  \)

\begin{verbatim}
    ((+ (* a (u x))
        (* b (u y (worst x)))
        (* (- k) (u x (worst y)) (u y (worst x)))
        (* (- k a) (u x (worst y)) (u y (best x)))
        (* (- k b) (u x (best y)) (u y (worst x)))
        (* (- 1 k) (u x (best y)) (u y (best x)))
     (where a (evaluation u (best x) (worst y))
            b (evaluation u (worst x) (best y))))
\end{verbatim}
\end{itemize}

\section{$n$-attribute Forms}

\begin{itemize}
\item Additive:
\[\sum_{i=1}^{n} k_i u_i(x),\hspace{1em}{\rm where}\hspace{1em} k_i = u(x_i^*,x_{\overline{i}*})\]

\begin{verbatim}
  ((sum i (from-to 1 n)
        (* (k i) (u i)))
   (where (k i) (evaluation u (best i) (worst (comp i)))))
\end{verbatim}

For the following forms I will use the notation ${\bf i}_r$ to stand for
a collection of $r$ subscripts, and the symbol $S_r$ to denote the
space of all such subscript collections.

\item Multiplicative:
\[\sum_{r=1}^n \sum_{{\bf i}_r\in S_r} k^{r-1} \prod_{i\in {\bf i}_r} k_i u_i(x_i) \]
\begin{center}
where $\; 1+k = \prod_{i=1}^n (1 + k k_i)$, $k_i$ as above
\end{center}

\begin{verbatim}
  ((sum r (from-to 1 n)
        (sum i-subs (subscript-collns-of-size r n)
             (* (expt k (- r 1))
                (product i (subscripts-in i-subs)
                         (* (k i) (u i))))))
   (where (k i) (evaluation u (best i) (worst (comp i)))
          k (iterative-soln (- (product i (from-to 1 n)
                                        (+ 1 (* k (k i))))
                               1))))
\end{verbatim}

\item Multilinear:
\[\sum_{r=1}^n \sum_{{\bf i}_r\in S_r} k_{{\bf i}_r} \prod_{i\in {\bf i}_r} u_i(x_i) \]
\begin{center}
where $\; k_{{\bf i}_r} = u(x_{{\bf i}_r}^*,x_{\overline{{\bf i}_r}*}) - \sum_{r_0=1}^{r-1} \sum_{{\bf i}_{r_0}\in I_{r_0}} k_{{\bf i}_{r_0}}$ 
\end{center}

\newpage
\begin{verbatim}
  ((sum r (from-to 1 n)
        (sum i-subs (subscript-collns-of-size r n)
             (* (k i-subs)
                (product i (subscripts-in i-subs)
                         (u i)))))
   (where (k i-subs)
          (- (evaluation u (best i-subs) (worst (comp i-subs)))
             (sum r-zero (from-to 1 (- (length i-subs) 1))
                  (sum i-subs-zero
                       (subscript-collns-of-size r-zero n)
                       (k i-subs-zero))))))
\end{verbatim}

\item Multilinear Generalization:
\[\theta + \sum_{r=1}^n \sum_{{\bf i}_r\in S_r} k_{{\bf i}_r}' \prod_{i\in {\bf i}_r} v_i^*(x_i) \prod_{i\not\in {\bf i}_r} v_{i*}(x_i) \]
\begin{center}
where $\; k_{{\bf i}_r}' = u(x_{{\bf i}_r}^*,x_{\overline{{\bf i}_r}*}) - \theta$, $\theta$ is an interpolation constant, \\
$v^*$ and $v_*$ are as defined by Bell~\cite{Bell79a}, page 747.
\end{center}

\begin{verbatim}
  ((+ theta
      (sum r (from-to 1 n)
           (sum i-subs (subscript-collns-of-size r n)
                (* (k-prime i-subs)
                   (product i (subscripts-in i-subs)
                            (v-best i))
                   (product i (comp (subscripts-in i-subs))
                            (v-worst i))))))
   (where (k-prime i-subs)
          (- (evaluation u (best i-subs) (worst (comp i-subs)))
             theta)))
\end{verbatim}

\item Bilateral:
\[\theta + \sum_{r=1}^n \sum_{{\bf i}_r\in S_r} k_{{\bf i}_r}' \prod_{i\in {\bf i}_r} v_i^*(x_i) \prod_{i\not\in {\bf i}_r} v_{i*}(x_i) + \sum_{i=1}^n \frac{a_i(1-b_i)\left[ u(x_i,x_{\overline{i}*})-u(x_i,x_{\overline{i}}^*)\right]}{1-a_i-b_i} \]
\begin{center}
where $a_i$ and $b_i$ are also defined by Bell~\cite{Bell79a}
\end{center}

The bilateral form could be specified in a fashion similar to the above.
\end{itemize}

\chapter[Health Preference Knowledge]
{The Health Preference Knowledge Base}
\label{medical-ax}

This appendix summarizes the health preference knowledge base developed
in chapter~\ref{domain-p} (plus a few concepts not included there).
The representations are built from
{\sc urp}'s technical vocabulary, with some special-purpose mechanisms that
will be necessary to manage the knowledge base.  The concepts encoded here
are just for illustration; there is no claim that they are complete or
that they represent anyone's actual preferences.  This knowledge base has not
been implemented for {\sc urp}.

\section{Built-in Attributes}

\begin{tt}
\begin{tabbing}
\= (de\= :de\= '(\= \+ \kill
(defattribute LIFE-YEARS \\
\> :value-set '(real-range 0 max-life-years) \\
\> :scale-type 'ratio \\
\> :unit 'years \\
\> :description \\
\>\> '(life-years (\# of years from NOW until DEATH) \\
\>\>\> max-life-years (Largest possible value for life-years))) \\
\end{tabbing}

\begin{tabbing}
\= (de\= :de\= it '(\= \+ \kill
(defattribute PHYSICAL-FUNCTION \\
\> :source "Torrance, Boyle, and Horwood" \\
\> :value-set '(integer-range 1 6) \\
\> :scale-type 'ordinal \\
\> :unit '((1 (Needs help to get around; no control of limbs)) \\
\>\>\>   (2 (Needs help; needs mechanical aids to walk)) \\
\>\>\>   (3 (Needs help; limitations in physical activity)) \\
\>\>\>   (4 (Can get around; needs mechanical aids)) \\
\>\>\>   (5 (Can get around; limitations in activity)) \\
\>\>\>   (6 (Can get around; no limitations))) \\
\> :description \\
\>\> '(physical-function (Mobility and physical activity)))
\end{tabbing}
\end{tt}

\newpage

\begin{itemize}
\item[] (component {\it physical-function} {\it health-status})
\item[] (component {\it role-function} {\it health-status})
\item[] (component {\it social-emotional-function} {\it health-status})
\item[] (component {\it health-problem} {\it health-status})
\end{itemize}

Note: These components of health status are taken from the health state
classification system of Torrance, Boyle, and Horwood~\cite{TorrBoyl}.

\section{Predefined Qualitative Behaviors}

\begin{itemize}
\item[] ({\bf monotonic-increasing} {\it life-years})\footnote{Following the
development in section~\ref{pre-independence}, it might be desirable
to condition this on a health state other than ``brain-dead.''}
\item[] ({\bf monotonic-increasing} {\it physical-function})
\item[] ({\bf monotonic-decreasing} {\it hospital-confinement})
\item[] ({\bf monotonic-decreasing} {\it cost})
\end{itemize}

\begin{itemize}
\item[] (influence+ {\bf decreasing-marginal-value} {\it life-years} {\bf risk-averse})
\item[] (influence+ {\bf increasing-marginal-value} {\it life-years} {\bf risk-prone})
\item[] (influence+ {\bf time-preference} {\it life-years} {\bf risk-averse})
\item[] (influence+ {\bf youth-preference} {\it life-years} {\bf risk-averse})
\item[] (influence+ {\bf age-preference} {\it life-years} {\bf risk-prone})
\end{itemize}

Note: a positive influence on {\bf risk-averse} is equivalent to a
negative influence on {\bf risk-prone}, and vice-versa.

\section{Predefined Independence Conditions}

\begin{itemize}
\item[] ({\bf preferential-independence} \{{\it health-status}\} \{{\it life-years}\})
\item[] ({\bf generalized-preferential-independence} \{{\it life-years}\} \{{\it health-status}\})
\end{itemize}

Other independence conditions may be inferred from domain concepts using the
rules of section~\ref{rules}.

\section{Special Functional Forms}

\begin{tabbing}
\= ({\tt iff} \= ({\tt and} \= mmmmmmmm\= \+ \kill
({\bf monotonic-transform} {\it life-years} {\it deale-life-expectancy}) \\
\\
({\tt iff} ({\tt and} ({\bf joint utility-independence} \{{\it life-years}\} \{{\it health-status}\}) \\
\>\> ({\bf constant-proportional-tradeoff} {\it life-years} {\it health-status}) \\
\>\> ({\bf risk-neutral} {\it life-years})) \\
\> ({\bf QALY-form-1})) \\
\\
({\tt iff} ({\tt and} ({\bf joint utility-independence} \{{\it life-years}\} \{{\it health-status}\}) \\
\>\> ({\bf constant-proportional-tradeoff} {\it life-years} {\it health-status})) \\
\> ({\bf QALY-form-2})) \\
\\
({\tt iff} ({\bf successive-pairwise-preferential-independence} $T$) \\
\> ({\tt from-to i (1 (- n 1))} \\
\>\> ({\bf preferential-independence} \\
\>\>\> {\tt (set-of (nth i $T$) (nth (+ i 1) $T$))} \\
\>\>\> {\tt (difference $T$ (set-of (nth i $T$) (nth (+ i 1) $T$)))}))) \\
\\
({\tt iff} ({\tt and} ({\bf constant-proportional-tradeoff} {\it
consumption} {\it life-years}) \\
\>\> ({\bf constant-risk-averse} {\it life-years})) \\
\> ({\bf micromort-model}))
\end{tabbing}

Notes: The {\bf monotonic-transform} assertion on two attributes states that
behaviors that are invariant over monotonic transformations which hold for
the first attribute also hold for the second.  {\bf QALY-form-1} and
{\bf QALY-form-2} correspond to equations \ref{qaly-1} and~\ref{qaly-2},
respectively.  The micromort model is Howard's measure for the small-risk
value of life~\cite{Howa}, mentioned in section~\ref{l-value}.

\section{Relations to Domain Concepts}\label{rules}

The validity of these {\sc urp} assertions will often depend on the
characteristics of the medical situation.  Facts of the particular case
will indicate which attributes are relevant, features of preference for
these attributes, and valid independence assumptions.  This section
illustrates some simple rule encodings for these relations.  Through a
mechanism such as this, any of the above assertions may be tied to
triggering or exceptional situations.

\begin{tabbing}
m\= RUL\= THENm\= \+ \kill
RULE001: \\*
\>\underline{IF}\> There are no states worse than death \\*
\>\underline{THEN}\> ({\bf joint preferential-independence} \{{\it life-years}\} \{{\it health-status}\}) \\*
\>\> ({\bf monotonic-increasing} {\it life-years}) \\
\\
RULE002: \\*
\>\underline{IF}\> Financial costs are not borne by the patient \\*
\>\underline{THEN}\> ({\bf value-independence} \{{\it cost}\} {\it everything else}) \\*
\>\> ({\bf monotonic-decreasing} {\it cost}) \\
\\
RULE003: \\*
\>\underline{IF}\> Patient gets weary of staying in hospital \\*
\>\underline{THEN}\> ({\bf risk-averse} {\it hospital-confinement}) \\
\\
RULE004: \\*
\>\underline{IF}\> Patient gets accustomed to staying in hospital \\*
\>\underline{THEN}\> ({\bf risk-prone} {\it hospital-confinement}) \\
\end{tabbing}

\end{document}
