COMPUTATIONAL DECISION ANALYSIS
Computational decision analysis (CDA) as a subject has so far
not received that much attention. This is bound to change in the future since the demand for software to support decisions more independently can
only be met realistically by computational methods that are possible to realise in a
consistent and perspicuous manner. Apart from CDA, not many
formalisms and methods are understood by humans and computable by
machines at the same time. Even though software agents have been slower
than expected to permeate the Web, in the long run distributed computing
without decision power in the distributed elements will not be a
powerful enough mechanism. Once we stop looking at software objects as
entities created to execute in a well-defined ambience, general methods
for selecting courses of action at pivotal points in the combined
executional state of the object and its environment will become important
building blocks if provided with tools for their usage.
Each of the three
words in CDA is a keyword. Decision means that it deals with
selection problems, i.e. situations in which there are more than one
alternative course of action. Analysis means that there are not only
advice given, not only a single best alternative pointed out by a mechanised
procedure, but rather also aid in understanding the decision problem and
how the solutions relate to each other. Computational means that
there exist efficiently computable algorithms that perform the analysis
in a reasonably short time, to admit interactive analysis. This is equally
important for interfaces between man and machine.
Unlike many other formalisms, CDA coexists happily with most of
statistics, operations research, and utility theory to the extent of
relying on key results in these areas and introducing computationality
where needed.
The mandatory position paper, required for graduation at KTH, can be found here. It explains my research in relation to earlier research within the research group and positions it at the research frontier.
Ph.D. Thesis
Royal Institute of Technology
Stockholm, Sweden
ISSN: 1101-8526
Author: Mats Danielson
Title: Computational Decision Analysis
ISBN: 91-7153-613-2
DSV Report Series 97-011
ISRN: KTH/DSV/R-97/11-SE
Submitted: March 17, 1997
Defended: May 26, 1997
Summary
The thesis deals with Computational Decision Analysis.
The thesis presents the DELTA method for decision-making using
imprecise information. The objective is to present a method for
evaluating choices under uncertainty. The nature of most information
available to decision-makers is imprecise, be it information for human
managers in organisations or for process agents in a distributed computer
environment. In spite of this, most traditional models for decisions
disregard this state of affairs. Some more modern approaches, like fuzzy
decision analysis and Dempster-Shafer theory, address the problem of
vagueness. Many of these modern approaches concentrate more on
representation and less on evaluation. The emphasis in this thesis is
more on evaluation, and even though the representation used is that of
standard probability theory, there is nothing to prevent the use of any of
the other well-established formalisms instead.
Introduction
The first part introduces decision analysis in general and the DELTA
method in particular. Chapter 1 begins by surveying a number of
traditional decision models and discussing some of their properties. The
models are divided into three categories: risk-free, strictly uncertain, and
risk models. Following that, some approaches to imprecision in input
data are presented. Finally, appropriate research methods are discussed.
Chapter 2 presents a suggested decision method for human
decision-makers in work cycle form based on the DELTA method.
It attempts to
convey some feeling for how a decision-maker can utilise the method in
analysing a decision situation. It also tries to demonstrate that the
suggested method is realistic to work with.
Chapter 3 presents the DELTA Decision Tool (DDT), an interactive
graphical software implementation of the DELTA method intended for
aiding human decision-makers in understanding and analysing real-life
decision situations. It contains a description of the DDT software and
its architecture. The rest of the chapter is devoted to an industrial example,
which is used in presenting the features of DDT and its user
interaction.
Representation
The core of the thesis is the presentation of the DELTA method.
Chapter 4 starts with the structure of a decision problem and the
required representation of user statements. A model of the situation is
created with relevant courses of action and their consequences, should
certain events occur. The model is represented by a decision frame. The
courses of action will be called alternatives in the model, and they are
represented by consequence sets in the decision frame. Following the
establishment of a frame, the probabilities of the events and the values of
the consequences are filled in. The requirement is emphasised that all
statements have an interval form to reflect the imprecise nature of the
input data. Next, properties particular to bases (collections of statements)
of probability statements and then the value base counterparts are
discussed. Finally, the chapter also presents general properties of bases,
i.e. collections of constraints and estimates - properties that apply to
probability as well as to value bases. Further, the section on translations
shows the representation of numerical and qualitative statements of both
probability and value.
Evaluation
Chapter 5 presents evaluation methods in detail. The DELTA method is
presented step by step, beginning with the discussion of the expected
value rule for selection amongst a number of available courses of action.
Then a number of other evaluation rules to either replace or supplement
the expected value are discussed. They are discussed from a choice rather
than preference view. One of the conclusions is that there exists no
perfect rule, although the expected value seems to be at least as good as
many of its contenders. To improve that rule (or any other similar rule),
it is suggested that it is supplemented with other, qualitative rules rather
than engaging in further modifications in chase of the perfect rule. The
common characteristic of all qualitative rules is that they do not rely on
multiplying probabilities and values but treat them as separate numeric
entities. Once a rule has been agreed upon, it can be applied to all the
alternatives, provided there is a computational procedure for evaluating
the alternatives under that rule. The DELTA dominance is introduced as
a unifying concept for many of the dominance rules in current use.
Dominance and threshold methods are discussed and the kinship
between them is pointed out.
Dealing with imprecise statements means frequently encountering
decision situations where more than one alternative is to prefer in
different parts of the consistent solution space. Consequently,
dominance selection rules are not enough to indicate preferred choices.
Many ideas have emerged in response to the problem arising when the
information given is imprecise and overlaps in the sense that parts of the
information seem to favour one alternative (consequence set) while
other parts favours another one. This thesis conforms to statistical
decision theory and introduces some new concepts to aid the selections.
The concepts of maximal and minimal differences represent the most
and least favourable possibilities respectively. A new set of selection
rules is introduced - the concepts of strong, marked, and weak dominance.
The selection procedures suggested in this thesis are based on those
concepts and on the expansion and contraction principles.
Optimisation
Chapter 6 deals with computational algorithms for DELTA, especially
optimisation since they are the most demanding ones. It starts with linear
programming (LP) for determining properties of bases. For solving these
LP problems computationally, the Simplex method is used. The chapter
continues with bilinear programming, necessary to calculate the results
of the evaluation rules. First quadratic programming is discussed and
then three algorithms are presented that under mild constraints solve a
special bilinear programming problem (BLP1) with LP (Simplex) techniques
instead. Due to the unusual problem structure (a long sequence of
smaller problems rather than the usual single large one), each of the
Simplex techniques must be carefully considered in order to select which
ones to apply. Furthermore, hardware architectural issues are found to be
important for the implementation of the DELTA solver. The conclusion
is that a configuration program is necessary, which will measure the
relative speeds of different operations and configure the solver's source
code accordingly.
Applications
There are two appendices, each addressing one application area of
computational decision analysis. Appendix A deals with problems of
co-ordinating multi-agent systems and the applicability of DELTA to
that area. In dealing with rational agents and their ability to make
decisions,
it is once more emphasised that there is no universal rule with which
rationality could be equated. Instead, the conclusion is that a successful
agent must be good at analysing results from a set of reasonable decision
rules. Such analyses should ideally exploit several decision rules shown
appropriate for the particular domain of interest. Different suggestions
of decision rules are investigated in the appendix, but it should be noted
that these are not the only possible ones and the DELTA method could
use other decision rules as well.
Appendix B applies DELTA to the area of risk analysis as the concept
is understood within insurance and security by introducing the DEEP
(Damage Evaluation and Effective Prevention) method. A risk analysis
method is presented that substantially improves the evaluative phases
compared with other, earlier approaches. The presentation is focused on
the analysis and identification of threats and on the evaluation of the
suggested actions since those are the points where the DEEP method
differs the most from other methods. The idea behind DEEP is to offer
an analytical framework for risk management in the classic chain
identification-valuation-action without aiming at replacing it.
Thesis Chapters
The thesis is a monograph and is published in a limited printed edition.
To reach a wider audience, some of the chapters plus the references are
available as PDF files, updated to correct mistakes and typos stated in the errata sheet, found
after the thesis was printed but before or during it was defended. Formally, the corrected chapters are not
identical to the thesis chapters and should be regarded as separate
documents.
Introduction
- Decision Methods
-
Working with DELTA
-
The DELTA Decision Tool [see below]
The DELTA Method
- Representation
- Evaluation
- Optimisation
Applications
-
Multi-Agent Systems
-
Risk Management
-
References
Hopefully, these chapters will give you an overview of the
work and possibly satisfy your curiosity.
If not,
please obtain the complete thesis from the address below.
There have been problems with printing Chapter 3. It is generated
partly from Word 6.0 (pages 54-65) unlike the other chapters which
originate entirely from Word 5.1 files. Some readers seem to have
problems displaying it, and not all printers seem to print beyond page
55. The latter problem is due to timeouts in processing the PS file
so if you adjust the timers, you should be able to print it. For
example, it takes about 12 minutes on an HP LaserJet 4MV from a Power
Mac 7200 on EtherTalk. For these reasons, the reprint of this chapter has been abridged and moved to PDF.
UPDATE 1998: Unfortunately, the thesis is out of print.
Hopefully, it will be reprinted in 1999. If so, it may be ordered
for a nominal fee from:
Dept. of Computer and Systems Sciences
Secretary of Research
Royal Institute of Technology
Electrum 230, SE-164 40 Kista, SWEDEN
![[Back]](/icons/dsv-home.gif)
Back to my home page
Latest update 1998-05-27.
Comments to mad@dsv.su.se